Me preguntaba si alguien tenía alguna idea o intuición detrás de la diferencia entre la variación de información y el índice Rand para comparar agrupaciones.
He leído el documento " Comparación de agrupamientos: una distancia basada en la información " de Marina Melia (Journal of Multivariate Analysis, 2007), pero, aparte de notar la diferencia en las definiciones, no entiendo qué es esa variación de información captura que el índice rand no captura.
machine-learning
clustering
metric
Amelio Vazquez-Reina
fuente
fuente
En mi opinión, hay grandes diferencias. El índice Rand se ve muy afectado por la granularidad de las agrupaciones en las que opera. En lo que sigue usaré la distancia de Mirkin, que es una forma ajustada del índice Rand (fácil de ver, pero vea, por ejemplo, Meila). También usaré la distancia de división / unión, que también se menciona en algunos de los documentos de Meila (descargo de responsabilidad: la distancia de división / unión fue propuesta por mí). Supongamos un universo de cien elementos. Usaré Top para denotar la agrupación con un solo clúster que contiene todos los elementos, Bottom para denotar la agrupación donde todos los nodos están en conjuntos de singleton separados, Izquierda para denotar la agrupación {{1,2, .. 10}, {11, 12..20}, {21,22..30}, ..., {91,92, .. 100}} , y derecho para denotar la agrupación {{1,11, .. 91}, {2, 12, .. 92}, {3,13, .. 93}, ..., {10,20, .. 100}}.
En mi opinión, Bottom y Top son grupos consistentes (de anidación), mientras que Left y Right son grupos con conflictos máximos. Las distancias de las métricas mencionadas para estas dos comparaciones por pares son las siguientes:
De ello se deduce que Mirkin / Rand consideran el par superior-inferior consistente mucho más separado que el par izquierda-derecha máximamente conflictivo. Este es un ejemplo extremo para ilustrar el punto, pero Mirkin / Rand en general se ven muy afectados por la granularidad de las agrupaciones en las que opera. La razón subyacente es una relación cuadrática entre esta métrica y los tamaños de los conglomerados, explicada por el hecho de que está involucrado el conteo de pares de nodos. En efecto, la distancia de Mirkin es una distancia de Hamming entre conjuntos de bordes de uniones de gráficos completos inducidos por agrupaciones (creo que esta es la respuesta a su pregunta).
Con respecto a las diferencias entre la variación de la información y la división / unión, la primera es más sensible a ciertas situaciones de conflicto como lo demuestra Meila. Es decir, Split / Join solo considera la mejor coincidencia para cada clúster y no tiene en cuenta la fragmentación que podría ocurrir en la parte restante de ese clúster, mientras que la variación de información lo recogerá. Dicho esto, Split / Join es fácilmente interpretable como el número de nodos que deben moverse para obtener un clúster del otro , y en ese sentido su rango se entiende más fácilmente; En la práctica, el problema de la fragmentación tampoco es tan común.
Cada una de estas métricas se puede formar como la suma de dos distancias, es decir, las distancias desde cada uno de los dos agrupamientos hasta su mayor subclúster común. Siento que a menudo es beneficioso trabajar con esas partes separadas en lugar de solo su suma. La tabla anterior se convierte en:
La relación de subsunción entre Arriba y Abajo se vuelve clara de inmediato. A menudo es bastante útil saber si dos agrupaciones son consistentes (es decir, una es (casi) una sub-agrupación de la otra) como una relajación de la cuestión de si están cerca . Una agrupación puede estar bastante distante de un estándar de oro, pero aún así ser consistente o casi consistente. En tal caso, puede que no haya razón para considerar que el agrupamiento es malo con respecto a ese estándar de oro. Por supuesto, los agrupamientos triviales Superior e Inferior serán consistentes con cualquier agrupación, por lo que esto debe tenerse en cuenta.
Finalmente, creo que las métricas como Mirkin, Variation of Information y Split / Join son las herramientas naturales para comparar agrupaciones. Para la mayoría de las aplicaciones, los métodos que intentan incorporar independencia estadística y corregir el azar son demasiado ingeniosos y confusos en lugar de aclarar.
Segundo ejemplo Considere los siguientes pares de agrupamientos: C1 = {{1, 2, 3, 4, 5, 6, 7, 8}, {9, 10, 11, 12, 13, 14, 15, 16}} con C2 = {{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, {11, 12, 13, 14, 15, 16}}
y C3 = {{1, 2, 3, 4}, {5, 6, 7, 8, 9, 10}, {11, 12, 13, 14, 15, 16}} con {{1, 2, 3 , 4}, {5, 6, 7, 8, 9, 10, 11, 12}, {13, 14, 15, 16}}
Aquí C2 puede formarse a partir de C1 moviendo los nodos 9 y 10 y C3 puede formarse a partir de C3 moviendo los nodos 11 y 12. Ambos cambios son idénticos ("mover dos nodos") excepto por el hecho de que los tamaños de los grupos involucrados difieren . La tabla de métricas de agrupación para estos dos ejemplos es esta:
Se puede ver que Mirkin / Rand y la variación de la información se ven afectados por los tamaños de clúster (y Mirkin en mayor medida; esto será más pronunciado a medida que los tamaños de clúster diverjan), mientras que la distancia de división / unión no lo es (su valor es 4 ya que "mueve" los nodos de un clúster al otro siempre a través del subclúster común más grande). Esto puede ser un rasgo deseable dependiendo de las circunstancias. Vale la pena tener en cuenta la interpretación simple de Split / Join (número de nodos para mover) y su independencia del tamaño del clúster. Entre Mirkin y la variación de la información, creo que esta última es muy preferible.
fuente