Agrupamiento--Intuición detrás de Kleinberg ' s Teorema de imposibilidad

Question

He estado pensando en escribir una entrada en el blog sobre este interesante análisis por Kleinberg (2002) , que explora la dificultad de la agrupación. Kleinberg se describen tres aparentemente intuitiva desiderata para una función de agrupamiento y luego la prueba de que no existe una función. Hay muchos algoritmos de clustering que satify dos de los tres criterios; sin embargo, la función no puede satisfacer a todos los tres de forma simultánea.

Brevemente y de manera informal, los tres desiderata que él describe son:

• Escala de Invariancia: Si queremos transformar los datos de modo que todo se estira igual en todas las direcciones, a continuación, la agrupación resultado no se debe cambiar.
• Consistencia: Si la estiramos los datos de modo que las distancias entre los grupos de los aumentos y/o de las distancias dentro de los grupos disminuye, entonces la agrupación no se debe cambiar.
• Riqueza: La función de agrupamiento teóricamente debería ser capaz de producir cualquier partición/agrupación de puntos de datos (a falta de saber los pares distancia entre dos puntos)

Preguntas:

(1) hay una buena intuición, la imagen geométrica que puede mostrar la inconsistencia entre estos tres criterios?

(2) Esto se refiere a los detalles técnicos para el papel. Usted tendrá que leer el enlace de arriba para entender esta parte de la pregunta.

En el papel, la prueba en el teorema 3.1 es un poco difícil para mí seguir en los puntos. Estoy atascado en: "Vamos a $f$ ser una función de agrupamiento que satisface Consistencia. Pretendemos que para cualquier partición $\Gamma \in \text{Range}(f)$, existen números reales positivos $a < b$ tal manera que el par $(a, b)$ $\Gamma$- forzar."

No veo cómo esto puede ser el caso... no es la partición por debajo de un contra-ejemplo donde $a > b$ (es decir, la distancia mínima entre los grupos es mayor que la distancia máxima dentro de los grupos)?

---

Otros documentos:

• Ackerman & Ben-David (2009). Medidas de la Calidad de la Agrupación: Un Trabajo Conjunto de Axiomas para la Agrupación de
  • Señala algunos problemas con la "consistencia" axioma

Answer 1

Esta es la intuición que se me ocurrió (un fragmento de mi blog aquí).

Una consecuencia de la riqueza axioma es que podemos definir dos distancias distintas funciones, $d_1$ (superior izquierda) y $d_2$ (abajo a la izquierda), que respectivamente poner todos los puntos de datos en los grupos y en algunos otros de la agrupación. Entonces podemos definir una tercera función de distancia $d_3$ (arriba y abajo a la derecha) que simplemente escalas de $d_2$, de modo que la distancia mínima entre los puntos en $d_3$ espacio es mayor que la distancia máxima en $d_1$ espacio. Entonces, llegamos a una contradicción, ya que por la consistencia de la agrupación debe ser el mismo para el $d_1 \rightarrow d_3$ transformación, pero también de la misma para el $d_2 \rightarrow d_3$ transformación.