¿Existe un algoritmo similar al árbol de decisión para la agrupación no supervisada?

Question

Tengo un conjunto de datos que consta de 5 características : A, B, C, D, E. Todas ellas son valores numéricos. En lugar de hacer una agrupación basada en la densidad, lo que quiero hacer es agrupar los datos de una manera similar a un árbol de decisión.

El enfoque al que me refiero es algo así:

El algoritmo puede dividir los datos en X conglomerados iniciales basados en la característica C, es decir, los X conglomerados pueden tener valores de C pequeños, C medianos, C grandes y C muy grandes, etc. A continuación, en cada uno de los X nodos de clúster, el algoritmo divide los datos en Y clústeres en función de la característica A. El algoritmo continúa hasta que se utilizan todas las características.

El algoritmo que he descrito antes es como un algoritmo de árbol de decisión. Pero lo necesito para la agrupación no supervisada, en lugar de la clasificación supervisada.

Mis preguntas son las siguientes:

1. ¿Existen ya algoritmos de este tipo? ¿Cuál es el nombre correcto de dicho algoritmo?
2. ¿Existe algún paquete/biblioteca R/python que tenga una implementación de este tipo de algoritmos?

Answer 1

Tal vez desee considerar el siguiente enfoque:

• Utilice cualquier algoritmo de agrupación que sea adecuado para sus datos
• Supongamos que el conglomerado resultante son clases
• Entrenar un árbol de decisión en los clusters

Esto le permitirá probar diferentes algoritmos de agrupación, pero obtendrá una aproximación del árbol de decisión para cada uno de ellos.

Answer 2

Lo que buscas es un algoritmo de agrupación divisoria.

Los algoritmos más habituales son los aglomerativos, que agrupan los datos de abajo arriba: cada observación comienza como su propio conglomerado y los conglomerados se van fusionando. La agrupación divisiva es descendente: las observaciones comienzan en un clúster que se divide gradualmente.

El deseo de parecerse a un árbol de decisión limita las opciones, ya que la mayoría de los algoritmos operan sobre distancias dentro del espacio de datos completo en lugar de dividir una variable cada vez.

DIANA es el único algoritmo de clustering divisivo que conozco, y creo que está estructurado como un árbol de decisión. Me sorprendería que no hubiera otros por ahí.

Podría utilizar un algoritmo de árbol de decisión estándar si modifica la regla de división a una métrica que no considere una variable dependiente definida, sino que utilice una métrica de bondad de conglomerados.

Answer 3

El primer documento que me viene a la mente es éste: Clustering Via Decision Tree Construction https://pdfs.semanticscholar.org/8996/148e8f0b34308e2d22f78ff89bf1f038d1d6.pdf

Como ya se ha mencionado, tanto la "jerárquica" (de arriba abajo) como la "aglomeración jerárquica" (de abajo arriba) son técnicas bien conocidas que utilizan árboles para realizar la agrupación. Scipy tiene esto.

Si estás de acuerdo con el código personalizado porque no conozco ninguna biblioteca, hay dos técnicas que puedo recomendar. Tenga en cuenta que estos no son técnicamente agrupación debido a la mecánica que se basan en. Usted podría llamar a esto pseudo clustering.

1) Supervisado: Esto es algo similar a la ponencia (vale la pena leerla). Construir un único modelo de árbol de decisión para aprender algún objetivo (usted decide lo que tiene sentido). El objetivo podría ser una columna generada aleatoriamente (requiere repetir y evaluar qué iteración fue la mejor, ver más abajo). Defina cada ruta completa del árbol como un "cluster", ya que los puntos que caen a través de esa serie de ramas son técnicamente similares con respecto al objetivo. Esto sólo funciona bien en algunos problemas, pero es eficiente a gran escala. Al final se obtienen K clusters (véase más abajo).

2) Semisupervisado (algo así como no supervisado, pero supervisado mecánicamente), utilizando #1: puede intentar construir árboles para predecir columnas en un patrón de dejar una fuera. Es decir, si el esquema es [A,B,C], construya 3 modelos [A,B] -> C, [A,C] -> B, [B,C]->A. Se obtienen clusters KN (véase más abajo). N=len(esquema). Si algunas de estas características no son interesantes o están demasiado desequilibradas (en el caso de las categorías), no las utilice como objetivos.

Resumen: El modelo seleccionará las características por orden en función de la información o la pureza y las agrupaciones se basarán en unas pocas características en lugar de en todas. No existe el concepto de distancia en estos conglomerados, pero sin duda se podría idear uno basado en los centros.

Pros: fácil de entender y explicar, formación e inferencia rápidas, funciona bien con pocas características fuertes, funciona con categorías. Cuando las características son esencialmente heterogéneas y se dispone de muchas características, no hay que dedicar tanto tiempo a decidir cuáles utilizar en la función de distancia.

Contras: no es estándar, debe ser escrito, sesgo ingenuo, la colinealidad con el objetivo causa malos resultados, tener 1000 características igualmente importantes no funcionará bien (KMeans con distancia euclidiana es mejor aquí).

¿Cuántas agrupaciones tienes? Debe, absolutamente debe restringir el modelo DT para que no crezca demasiado. Por ejemplo, establezca muestras mínimas por hoja, nodos de hoja máximos (preferido) o profundidad máxima. Opcionalmente, establezca restricciones de pureza o entropía. Debe comprobar cuántos clusters le da y evaluar si este método es mejor que el clustering real.

¿Le han funcionado bien las técnicas y los parámetros? ¿Cuál fue el mejor? Para averiguarlo, hay que hacer una evaluación por conglomerados: Métricas de rendimiento para evaluar el aprendizaje no supervisado

Answer 4

Una idea a tener en cuenta es suponer que se tienen k características y n puntos. Puede construir árboles aleatorios utilizando (k-1) características y 1 característica como variable dependiente. Y. Puede seleccionar una altura h después de la cual tendrá puntos de datos en raíces. Usted puede tomar la votación tipo de árboles diferentes. Sólo una idea.