Agrupación basada en puntajes de similitud

17

Supongamos que tenemos un conjunto de elementos E y una similitud ( no lejos ) la función SIM (ei, ej) entre dos elementos de la IE, EJ ∈ E .

¿Cómo podríamos (eficientemente) agrupar los elementos de E , usando sim ?

k- significa, por ejemplo, requiere una k dada , Canopy Clustering requiere dos valores umbral. ¿Qué pasa si no queremos esos parámetros predefinidos?

Tenga en cuenta que sim no es necesariamente una métrica (es decir, la desigualdad del triángulo puede o no ser válida). Además, no importa si los grupos son disjuntos (particiones de E ).

clustering algorithms similarity vefthym
fuente
2
Me pregunto por qué enfatizaste que no tienes distancia. No soy un experto aquí, pero me pregunto si no debería ser posible convertir semejante similitud en una distancia, si es necesario, básicamente considerando su inverso. Independientemente de eso, dudo que haya algoritmos de agrupación que estén completamente libres de parámetros, por lo que es probable que sea necesario algún ajuste en todos los casos. Cuando consideró k-medias, ¿se puede suponer que tiene propiedades de valor real (en particular, que puede tomar la "media" de varios elementos)?
Marco13
44
No necesita saber k para realizar k medios. Puede agrupar con k variable y verificar la varianza del grupo para encontrar el óptimo. Alternativamente, puede pensar en buscar modelos de mezcla gaussiana u otro proceso de restaurante como cosas para ayudarlo a agrupar.
cwharland
2
Hice las preguntas por una razón específica: si pudieras aplicar k-Means, pero el único problema era encontrar la "k" inicial, entonces podrías considerar un en.wikipedia.org/wiki/Self-organizing_map como alternativa. Tiene algunas propiedades agradables, y básicamente se comporta "similar" a k-Means, pero no requiere que se establezca la "k" inicial. Probablemente no sea una solución lista para usar, ya que tiene parámetros de ajuste adicionales (y la capacitación puede ser computacionalmente costosa), pero vale la pena echarle un vistazo.
Marco13
2
La elección inicial de k influye en los resultados de la agrupación, pero puede definir una función de pérdida o, más probablemente, una función de precisión que le indica para cada valor de k que utiliza para agrupar, la similitud relativa de todos los sujetos en ese grupo. Eliges la k que minimiza la varianza en esa similitud. GMM y otros procesos dirichlet se ocupan bastante bien del problema de no saber k. Uno de los mejores recursos que he visto en esto es el tutorial de Edwin Chen .
cwharland
44
Solo un pensamiento: si su puntaje de similitud se normaliza a 1 , entonces 1-sim(ei, ej) = Distance. Con la métrica de distancia puede aplicar, por ejemplo, agrupamiento jerárquico. Bajando desde la raíz, verá a qué nivel de grupos de granularidad tendría sentido para su problema particular.
Olexandr Isayev

Respuestas:

8

  1. Creo que una serie de algoritmos de agrupación que normalmente usan una métrica, en realidad no se basan en las propiedades de la métrica (aparte de la conmutatividad, pero creo que lo tendrías aquí). Por ejemplo, DBSCAN usa vecindarios epsilon alrededor de un punto; No hay nada allí que diga específicamente que la desigualdad del triángulo es importante. Por lo tanto, probablemente pueda usar DBSCAN, aunque es posible que tenga que hacer algún tipo de índice espacial no estándar para realizar búsquedas eficientes en su caso. Su versión de epsilon-neighborhood probablemente será sim> 1 / epsilon en lugar de al revés. Misma historia con k-means y algoritmos relacionados.

  2. ¿Puedes construir una métrica a partir de tu similitud? Una posibilidad: dist (ei, ej) = min (sim (ei, ek) + sim (ek, ej)) para todos los k ... Alternativamente, ¿puede proporcionar un límite superior tal que sim (ei, ej) <sim (ei, ek) + sim (ek, ej) + d, para todos k y alguna constante positiva d? Intuitivamente, los valores sim grandes significan estar más juntos: ¿es 1 / sim como una métrica? ¿Qué pasa con 1 / (sim + constante)? ¿Qué pasa con min (1 / sim (ei, ek) + 1 / sim (ek, ej)) para todos los k? (se garantiza que esta última sea una métrica, por cierto)

  3. Una construcción alternativa de una métrica es hacer una incrustación. Como primer paso, puede intentar mapear sus puntos ei -> xi, de modo que xi minimice la suma (abs (sim (ei, ej) - f (dist (xi, xj))), para alguna función adecuada f y métrica dist. La función f convierte la distancia en la incrustación a un valor similar a la similitud; tendrías que experimentar un poco, pero 1 / dist o exp ^ -dist son buenos puntos de partida. También tendrías que experimentar con el mejor dimensión para xi. A partir de ahí, puede usar la agrupación convencional en xi. La idea aquí es que casi puede (en el mejor sentido de ajuste) convertir sus distancias en la incrustación a valores de similitud, para que se agrupen correctamente.

  4. Sobre el uso de parámetros predefinidos, todos los algoritmos tienen algunos ajustes. DBSCAN puede encontrar el número de clústeres, pero aún necesita darle algunos parámetros. En general, el ajuste requiere múltiples ejecuciones del algoritmo con diferentes valores para los parámetros ajustables, junto con alguna función que evalúa la bondad de la agrupación (ya sea calculada por separado, proporcionada por el algoritmo de agrupación en sí, o simplemente ignorada :) Si el carácter de sus datos no cambian, puede sintonizar una vez y luego usar esos parámetros fijos; si cambia, entonces debe ajustar para cada ejecución. Puede averiguarlo ajustando cada ejecución y luego comparando qué tan bien funcionan los parámetros de una ejecución en otra, en comparación con los parámetros ajustados específicamente para eso.

Alex I
fuente
7

Alex hizo una serie de buenos puntos, aunque podría tener que retrasar un poco su implicación de que DBSCAN es el mejor algoritmo de agrupamiento para usar aquí. Dependiendo de su implementación, y si está utilizando o no índices acelerados (muchas implementaciones no lo hacen), su complejidad de tiempo y espacio será O(n2), lo que está lejos de ser ideal.

Personalmente, mis algoritmos de agrupación son OpenOrd para la agrupación del ganador se lleva todo y FLAME para la agrupación difusa. Ambos métodos son indiferentes a si las métricas utilizadas son similitud o distancia (FLAME en particular es casi idéntico en ambas construcciones). La implementación de OpenOrd en Gephi es O(nlogn)y se sabe que es más escalable que cualquiera de los otros algoritmos de agrupamiento presentes en el paquete Gephi.

FLAME, por otro lado, es excelente si está buscando un método de agrupación difusa. Si bien la complejidad de FLAME es un poco más difícil de determinar ya que es un proceso iterativo, se ha demostrado que es subcuadrático y similar en velocidad de ejecución a knn.

indico
fuente
4

DBSCAN (ver también: DBSCAN generalizado) no requiere una distancia. Todo lo que necesita es una decisión binaria . Comúnmente, uno usaría "distancia <epsilon" pero nada dice que no se puede usar "similitud> epsilon" en su lugar. No se requieren desigualdades de triángulos, etc.

La propagación de afinidad, como su nombre lo indica, usa similitudes.

La agrupación jerárquica, excepto tal vez el vínculo Ward, no supone nada. En muchas implementaciones, puede usar distancias negativas cuando tiene similitudes, y funcionará bien. Porque todo lo que se necesita es min, max y <.

Kernel k-means podría funcionar SI su similitud es una buena función del kernel. Piense en ello como calcular k-means en un espacio vectorial diferente, donde la distancia euclidiana corresponde a su función de similitud. Pero entonces necesitas saber k.

PAM (K-medoides) debería funcionar. Asigne cada objeto al medoide más similar, luego elija el objeto con la mayor similitud promedio como nuevo medoide ... no se necesita desigualdad de triángulo.

... y probablemente muchos, muchos más. Hay literalmente cientos de algoritmos de agrupamiento. La mayoría debería trabajar en mi humilde opinión. Muy pocos parecen requerir realmente propiedades métricas. K-means tiene probablemente los requisitos más estrictos: minimiza la varianza (no la distancia o similitud), y debe poder calcular los medios.

Anony-Mousse -Reinstate a Monica
fuente