Una agrupación comprensible

Question

Tengo un conjunto de datos. Cada elemento de este conjunto consta de variables numéricas y categóricas. Las variables categóricas son nominales y ordinales. Hay una estructura natural en este conjunto de datos. Comúnmente, los expertos agrupan conjuntos de datos como el mío utilizando su "conocimiento experto", pero quiero automatizar este proceso de clúster.

La mayoría de los algoritmos para la agrupación utilizan la distancia (euclidiana, Mahalanobdis, etc.) entre los objetos para agruparlos en clústeres. Pero es difícil encontrar algunas métricas razonables para los tipos de datos mixtos, es decir, no podemos encontrar una distancia entre 'vidrio' y 'acero'. Así que llegué a la conclusión de que tengo que usar probabilidades condicionalesP(feature = 'something' | Class) y alguna función de utilidad que dependa de ellas. Es razonable para variables categóricas, y funciona bien con variables numéricas asumiendo que se distribuyan normalmente.

Me di cuenta de que los algoritmos como K-means no producirán buenos resultados.

En este momento trato de trabajar con el algoritmo COBWEB, que coincide completamente con mis ideas sobre el uso de probabilidades condicionales. Pero me enfrenté a otros obsacles: los resultados de la agrupación son realmente difíciles de interpretar, si no imposible. Como resultado, quería obtener algo así como un conjunto de reglas que describan cada grupo (por ejemplo, if feature1 = 'a' and feature2 in [30, 60], it is cluster1), como árboles de clasificación para la clasificación.

lo tanto, mi pregunta es:

¿Hay algún algoritmo de clusterización existente que funciona con el tipo de datos mixtos y produce una descripción comprensible (y razonable para los humanos) de las agrupaciones.

Otros detalles:

Como entiendo que mi tarea es en el campo de agrupamiento conceptual. No puedo definir una función de similitud como se sugirió (como un objetivo final del proyecto whoal), debido al campo de estudio: es muy complicado y sin misericordia en términos de formalización. Por lo que yo entiendo, el enfoque más razonable es el que se usa en COBWEB, pero no estoy seguro de cómo adaptarlo, por lo que puedo obtener una descripción inmejorable de los clusters.

árbol de decisión

Como se sugirió, he tratado de entrenar a un árbol de decisión en la salida de la agrupación, obteniendo así una descripción de los clusters como un conjunto de reglas. Pero, lamentablemente, la interpretación de estas reglas es casi tan difícil como con la salida de clúster en bruto. El primero de unos pocos primeros niveles de reglas del nodo raíz tiene sentido: más cerca del sentido sin hojas que tenemos. En segundo lugar, estas reglas no coinciden con ningún conocimiento experto.

Por lo tanto, llegué a la conclusión de que la agrupación es una caja negra, y vale la pena no tratar de interpretar sus resultados.

también

tenía una idea interesante para modificar un 'árbol de decisión para la regresión' algoritmo de cierta manera: Istead de calcular una varianza intra-grupo calcualte un category utility function y utilizarlo como criterio dividida.Como resultado, deberíamos tener un árbol de decisiones con racimos de hojas y descripción de clusters listos para usar. Pero no he tratado de hacerlo, y no estoy seguro de la precisión y todo lo demás.

Answer 1

Para la mayoría de los algoritmos, deberá definir la similitud. No necesita ser una función de distancia adecuada (por ejemplo, satisfacer la desigualdad del triángulo).

K-means es especialmente malo, porque también necesita calcular means. Por lo tanto, es mejor mantenerse alejado de él si no puede calcular los medios, o si está utilizando una función de distancia diferente a Euclidiana.

Sin embargo, considere definir una función de distancia que capture el conocimiento de similitud de su dominio. Puede estar compuesto por otras funciones de distancia, digamos que usa la media armónica de la distancia euclidiana (tal vez ponderada con algún factor de escalamiento) y una función de similitud categorial.

Una vez que tenga una función de similitud decente, un montón de algoritmos estarán disponibles para usted. p.ej. DBSCAN (Wikipedia) o OPTICS (Wikipedia). ELKI puede ser de su interés, tienen un Tutorial on writing custom distance functions.

La interpretación es algo separado. Desafortunadamente, algunos algoritmos de agrupamiento le darán una interpretación legible de lo que encontraron. Pueden darle cosas como un representante (por ejemplo, la media de un grupo en k-means), pero poco más. Pero, por supuesto, puede siguiente entrenar un árbol de decisión en la salida de clúster y tratar de interpretar el árbol de decisión aprendido de la agrupación. Porque el realmente bueno característica sobre los árboles de decisión, es que son algo humanamente comprensible. Pero al igual que una Máquina de Vector de Soporte no le dará una explicación, la mayoría (si no todos) los algoritmos de agrupamiento tampoco lo harán, lo siento, a menos que haga este tipo de procesamiento posterior. Además, en realidad funcionará con cualquier algoritmo de clúster, que es una buena propiedad si desea comparar múltiples algoritmos.

Hubo una publicación relacionada el año pasado. Es un poco oscuro y experimental (en un taller en ECML-PKDD), y requiere que el conjunto de datos tenga una verdad de terreno bastante extensa en forma de clasificaciones. En el ejemplo, usaron clasificaciones de similitud de colores y algunas etiquetas. La idea clave es analizar el clúster y encontrar la mejor explicación con la (s) verdad (s) terrestre (s) dada (s). Estaban tratando de usarlo, por ej. diga "este grupo encontrado se basa principalmente en este tono particular de verde, por lo que no es muy interesante, pero el otro grupo no puede explicarse muy bien, necesita investigarlo más de cerca - tal vez el algoritmo descubrió algo nuevo aquí". Pero fue muy experimental (los talleres son para el tipo de investigación de trabajo en progreso). Usted podría ser capaz de utilizar esto, simplemente usando sus características como verdad de la tierra. Luego debe detectar si un clúster puede explicarse fácilmente por elementos como "atributo5 es aproximadamente 0.4 con baja varianza". ¡Pero no creará esa explicación a la fuerza!

• H.-P. Kriegel, E. Schubert, A. Zimek
  la evaluación de múltiples soluciones de clustering
  En segundo MultiClust taller: el descubrimiento, el resumen y el uso de múltiples agrupamientos cabo en conjunto con CELV PKDD 2011.http://dme.rwth-aachen.de/en/MultiClust2011

Answer 2

Para los vectores heterogéneas, no euclidianas de datos que usted describe, hierarchical clustering algorithms menudo funcionan mejor. La condición de probabilidad condicional que usted describe se puede incorporar como un orden de los atributos utilizados para realizar la aglomeración o división de un grupo. La semántica de los clusters resultantes es fácil de describir.

Answer 3

Un enfoque común para resolver este tipo de problema de agrupamiento es definir un modelo estadístico que capture las características relevantes de sus datos. Las asignaciones de conglomerados se pueden derivar utilizando un modelo de mezcla (como en el Modelo de mezcla gaussiano) y luego encontrar el componente de mezcla con la probabilidad más alta para un punto de datos particular.

En su caso, cada ejemplo es un vector tiene componentes tanto reales como categóricos. Un enfoque simple es modelar cada componente del vector por separado.

He generado un pequeño conjunto de datos de ejemplo donde cada ejemplo es un vector de dos dimensiones. La primera dimensión es una variable con distribución normal y el segundo es una opción de cinco categorías (véase el gráfico):

Hay un número de marcos que están disponibles para ejecutar monte carlo inferencia para los modelos estadísticos. BUGS es probablemente el más popular (http://www.mrc-bsu.cam.ac.uk/bugs/). Creé este modelo en Stan (http://mc-stan.org/), que utiliza una técnica de muestreo diferente de los insectos y es más eficiente para muchos problemas:

data { 
    int<lower=0> N; //number of data points 
    int<lower=0> C; //number of categories 

    real x[N]; // normally distributed component data 
    int y[N]; // categorical component data 
} 
parameters { 
    real<lower=0,upper=1> theta; // mixture probability 
    real mu[2]; // means for the normal component 
    simplex[C] phi[2]; // categorical distributions for the categorical component 
} 

transformed parameters { 
    real log_theta; 
    real log_one_minus_theta; 
    vector[C] log_phi[2]; 
    vector[C] alpha; 

    log_theta <- log(theta); 
    log_one_minus_theta <- log(1.0 - theta); 

    for(c in 1:C) 
    alpha[c] <- .5; 

    for(k in 1:2) 
    for(c in 1:C) 
     log_phi[k,c] <- log(phi[k,c]); 
} 
model { 
    theta ~ uniform(0,1); // equivalently, ~ beta(1,1); 
    for (k in 1:2){ 
    mu[k] ~ normal(0,10); 
    phi[k] ~ dirichlet(alpha); 
    } 

    for (n in 1:N) { 
    lp__ <- lp__ + log_sum_exp(log_theta + normal_log(x[n],mu[1],1) + log_phi[1,y[n]], 
           log_one_minus_theta + normal_log(x[n],mu[2],1) + log_phi[2,y[n]]); 
    } 
} 

Compilé y corrió el modelo Stan y utilizan los parámetros de la muestra final para calcular la probabilidad de cada punto de datos debajo de cada componente de mezcla. entonces asignado a cada punto de datos al componente de mezcla (cluster) con una mayor probabilidad de recuperar las asignaciones de racimo a continuación:

Básicamente, los parámetros para cada componente de la mezcla le dará las características básicas de cada clúster si ha creado un modelo apropiado para su conjunto de datos.