Resumen

El diámetro de un clúster es la máxima distancia intraclúster entre pares de instancias dentro del mismo clúster, y la división de un clúster es la mínima distancia entre instancias dentro del clúster e instancias fuera del clúster. Dadas unas pocas instancias etiquetadas, este trabajo incluye dos aspectos. En primer lugar, presentamos un algoritmo de clustering sencillo y rápido con la siguiente propiedad: si la relación entre la división mínima y el diámetro máximo (RSD) de la solución óptima es mayor que uno, el algoritmo devuelve soluciones óptimas para tres criterios de clustering. En segundo lugar, estudiamos el problema de aprendizaje métrico: aprender una métrica de distancia para que el RSD sea lo más grande posible. En comparación con los algoritmos de aprendizaje métrico existentes, uno de nuestros algoritmos de aprendizaje métrico es eficiente desde el punto de vista computacional: se trata de un modelo de programación lineal en lugar de un modelo de programación semidefinida utilizado por la mayoría de los algoritmos existentes. Demostramos empíricamente que la supervisión y la métrica aprendida pueden mejorar la calidad del clustering.

• Materias:Inteligencia artificial Algoritmos genéticos Ingeniería civil Neurociencia Cognitiva
• Subjects:Artificial intelligence Genetic algorithms Civil engineering Cognitive Neuroscience
• Palabras claves:algoritmo de aprendizaje métrico, modelo de programación lineal, par de instancia, problema de aprendizaje métrico, modelo de programación semidefinida, algoritmo, distancia máxima intracluster, métrica aprendida, soluciones óptimas, cluster
• Keywords:metric learning algorithm, linear programming model, pair of instance, metric learning problem, semidefinite programming model, algorithm, maximum intracluster distance, learned metric, optimal solutions, cluster