Clásico agglomerative la agrupación jerárquica de los métodos se basan en un algoritmo voraz. Esto significa que ellos (muchos de ellos) son propensas a dar a los sub-óptimas soluciones en lugar de la global resultado óptimo, especialmente en los pasos posteriores de la aglomeración. Para aclarar: cada uno de los agglomerative métodos convierte en la mejor elección de que dos grupos para combinar en un paso dado $q$, la opción que minimiza (a valor de $\delta_q$) el coeficiente de colligation $\delta$ sobre el paso; sin embargo, no es imposible que si algo había elegido no es el mejor pero un poco peor elección en las paso(s) a continuación, habría sido capaz de reducir el coeficiente de paso de $q$ a un valor menor que el $\delta_q$, mientras que la preservación monotonical crecimiento de $\delta$. Globalmente óptima solución en el paso de $q$ corresponde a lo absolutamente mínimo de tal manera alcanzable valor de $\delta_q$ con la restricción restante que $\delta_q \ge \delta_{q-1} \ge \delta_{q-2} \cdots$.
El riesgo de sub-optimalidad es la razón principal por la agrupación jerárquica es comúnmente no se recomienda con gran cantidad de objetos (por ejemplo, más de varios cientos): el investigador normalmente quiere pocos racimos y por lo tanto se ve en los pasos posteriores, pero si un paso posterior es, digamos, un 1000 a uno, es más sospechoso por haber extraviado globalmente óptima partición posible en el 1000 paso que, por ejemplo, un 100 paso pasado de nivel mundial óptimos partición posible en el 100º paso. Esto parece una cuestión de dictamen.
Mi pregunta es, ¿qué piensa usted acerca de que entre las conocidas agglomerative métodos - single de vinculación, unión completa, la media de la unión (dentro de los grupos), la media de la unión (entre grupos), centro de gravedad, la mediana, el Barrio de la suma de cuadrados - estoy mencionando aquellos en SPSS, pero hay otras variantes similares, así como son más y que son menos propensos a la sub-optimalidad defecto como el paso número crece. La intuición me sugiere que individual o completa de vinculación no son propensas a todos y siempre dan sus globalmente mejores soluciones, ya que estos métodos no participan en el cálculo de las estadísticas derivadas de las distancias (por ejemplo, los centroides). Yo puede ser tanto a la derecha como que no. ¿Qué pasa con el resto de métodos? Puede alguien aquí intento de analizar la (relativa) grado de local-óptima de riesgo de las anteriores concreto algoritmos voraces?
De la ilustración. Afortunadamente, para el Barrio método nos han pistas para observar cómo sub-optimalidad se acumula como $q$ crece. Porque no es bien conocido como un método iterativo que intenta optimizar la misma función $\delta$ como Ward hace; esto es K-means clustering: ambos tratan de minimizar agrupado en clúster suma de cuadrados$^1$. Podemos hacer del Barrio de la agrupación y en cada paso guardar clúster de centros, y utilizarlos como inicial de los centros en el procedimiento K-medios. Se K significa mejorar el Barrio las soluciones en términos de suma de cuadrados?
[$^1$ Nota: el Objetivo de las funciones de los dos no son exactamente lo mismo, si de ser la correcta. Barrio minimiza el aumento en la suma de cuadrados. Otro método jerárquico, método de varianza MIVAR (ver Podany, J., 1989, por diversos métodos jerárquicos), que es menos conocida, que minimiza la media de cuadrados dentro de los grupos.]
Nota. Esta ilustración pruebas de Ward observó $\delta_q$ valores no en contra de su propia óptimo global de los valores que no sabemos porque no podemos probar, por cada paso, todos los innumerables alternativas reconstrucciones de los pasos anteriores con el fin de encontrar la mínima posible $\delta_q$; las pruebas contra K-medios de optimalidad (que es casi su mundial aquí porque iniciales centros proporcionada por el Barrio puede considerarse razonablemente buen comienzo para las iteraciones).
Aquí hay algunos datos (5 no bien separados de los clústeres, 183 puntos). Los datos se sometieron tanto del Barrio de clústeres de sesión y K-means clustering sesiones, tal como se describe.
Resultados (valor de $\delta$) para grupos de 50 a través de los 2 se muestran a continuación. Aunque los 2 curvas están cerca el uno del otro, K-means " los valores son algo mejores. Es decir, K-means es más óptimo de Barrio.
La última imagen parcelas $\delta^{Ward}/\delta^{Kmeans}$. La tendencia es claramente a la vista: como el número de clústeres disminuye (es decir, paso $q$ para el Barrio crece), Ward tiende a ser menos óptima en relación a K-means.
Una tentadora pregunta sería si la relación de sub-optimalidad de Ward (el valor de $\delta^{Ward}/\delta^{Kmeans}$) en estos últimos 49 pasos de la aglomeración sería mayor si que he analizado en la misma forma de 1830 puntos de datos en lugar de sólo 183.
