El algoritmo de agrupación jerárquica más popular (esquema divisivo)

Question

Mi pregunta: qué es un "algoritmo estándar de agrupación jerárquica divisoria".

Tengo una matriz de similitud bien definida, y ya he realizado un clustering (con algoritmos de clustering espectral + genético), pero es bastante complicado.

Me gustaría demostrar que un algoritmo de agrupación jerárquica divisoria corriente da peores resultados (tengo medios para decir qué resultados son mejores).

Lo importante: DEBE ser (por razones demasiado políticas para explicarlas) un algoritmo jerárquico divisivo, y DEBE utilizar una matriz de similitud (y no, por ejemplo, una matriz de distancia).

Agradecería mucho cualquier consejo.

Answer 1

Que yo sepa, no hay muchas agrupaciones jerárquicas divisorias. De hecho, conozco exactamente un algoritmo de este tipo: DIANA (DIvisive ANAlysis o así) y yo no lo llamaría "popular", sino exótico y sólo de interés histórico. Un esquema divisivo necesita encontrar la mejor de O(2^n) posibles divisiones - esto es muy caro, e incluso la heurística no ayuda mucho a obtener un buen resultado. Top-down no es el método elegido.

Los métodos aglomerativos son mucho más populares, pero siguen escalando mal, O(n^2) o peor (el HAC estándar es O(n^3) tiempo de ejecución, O(n^2) memoria). En muchos casos, cualquier método O(n^2) (en particular cualquiera que necesite una matriz completa de distancias o similitudes) será inaceptablemente caro, razón por la cual la gente sigue usando k-means.