Agrupación de K-medias para datos numéricos y categóricos mixtos


133

Mi conjunto de datos contiene varios atributos numéricos y uno categórico.

Decir NumericAttr1, NumericAttr2, ..., NumericAttrN, CategoricalAttr,

donde CategoricalAttrtiene uno de los tres valores posibles: CategoricalAttrValue1, CategoricalAttrValue2o CategoricalAttrValue3.

Estoy usando la implementación predeterminada del algoritmo de agrupación k-means para Octave https://blog.west.uni-koblenz.de/2012-07-14/a-working-k-means-code-for-octave/ . Funciona solo con datos numéricos.

Entonces mi pregunta: ¿es correcto dividir el atributo categórico CategoricalAttren tres variables numéricas (binarias), como IsCategoricalAttrValue1, IsCategoricalAttrValue2, IsCategoricalAttrValue3?


77
Sí, usar la codificación 1 de n también es válido.
Sean Owen

1
Quizás este enfoque sea útil: zeszyty-naukowe.wwsi.edu.pl/zeszyty/zeszyt12/…

¿Tiene alguna idea sobre la combinación de agrupación de datos categóricos y numéricos de 'SERIE DE TIEMPO'?
Leila Yousefi

Respuestas:


122

El algoritmo estándar k-means no es directamente aplicable a datos categóricos, por varias razones. El espacio muestral para datos categóricos es discreto y no tiene un origen natural. Una función de distancia euclidiana en tal espacio no es realmente significativa. Como alguien dijo: "El hecho de que una serpiente no posea ruedas ni patas no nos permite decir nada sobre el valor relativo de ruedas y patas". (desde aquí )

Hay una variación de los medios k conocidos como modos k, introducidos en este documento por Zhexue Huang, que son adecuados para datos categóricos. Tenga en cuenta que las soluciones que obtiene son sensibles a las condiciones iniciales, como se discute aquí (PDF), por ejemplo.

El documento de Huang (vinculado anteriormente) también tiene una sección sobre "prototipos k" que se aplica a los datos con una combinación de características categóricas y numéricas. Utiliza una medida de distancia que mezcla la distancia de Hamming para entidades categóricas y la distancia euclidiana para entidades numéricas.

Una búsqueda en Google de la "mezcla de datos categóricos k-means" arroja bastantes artículos más recientes sobre varios algoritmos para la agrupación de k-means-like con una mezcla de datos categóricos y numéricos. (Todavía no los he leído, así que no puedo comentar sobre sus méritos).


En realidad, lo que sugiere (convertir atributos categóricos en valores binarios y luego hacer k-means como si fueran valores numéricos) es otro enfoque que se ha intentado antes (anterior a los modos k). (Ver Ralambondrainy, H. 1995. Una versión conceptual del algoritmo k-means. Pattern Recognition Letters, 16: 1147–1157.) Pero creo que se prefiere el enfoque de los modos k por las razones que indiqué anteriormente.


10
Si escala sus características numéricas al mismo rango que las características categóricas binarizadas, la similitud de coseno tiende a producir resultados muy similares al enfoque de Hamming anterior. No tengo una forma sólida de validar que esto funcione en todos los casos, por lo que cuando mezclo datos cat y num siempre verifico el agrupamiento en una muestra con el método simple de coseno que mencioné y la mezcla más complicada con Hamming. Si la diferencia es insignificante, prefiero el método más simple.
cwharland

1
Eso suena como un enfoque sensato, @cwharland. En una consideración adicional, también noto que una de las ventajas que Huang brinda para el enfoque de los modos k sobre Ralambondrainy's, que no tiene que introducir una característica separada para cada valor de su variable categórica, realmente no importa en el El caso de OP donde solo tiene una variable categórica única con tres valores. Es mejor ir con el enfoque más simple que funcione.
Tim Goodman

3
Buena respuesta. Potencialmente útil: he implementado los modos k y prototipos k de Huang (y algunas variaciones) en Python: github.com/nicodv/kmodes
Def_Os

2
No recomiendo convertir atributos categóricos a valores numéricos. Imagine que tiene dos nombres de ciudades: NY y LA. Si aplica NY número 3 y LA número 8, la distancia es 5, pero ese 5 no tiene nada que ver con la diferencia entre NY y LA.
adesantos

@adesantos Sí, es un problema representar varias categorías con una sola función numérica y usar una distancia euclidiana. Usar la distancia de Hamming es un enfoque; en ese caso, la distancia es 1 para cada característica que difiere (en lugar de la diferencia entre los valores numéricos asignados a las categorías). Hacer que cada categoría tenga su propia característica es otro enfoque (por ejemplo, 0 o 1 para "es it NY", y 0 o 1 para "es it LA").
Tim Goodman

24

En mi opinión, existen soluciones para tratar con datos categóricos en clustering. R viene con una distancia específica para datos categóricos. Esta distancia se llama Gower ( http://www.rdocumentation.org/packages/StatMatch/versions/1.2.0/topics/gower.dist ) y funciona bastante bien.


2
Este es el enfoque que estoy usando para un conjunto de datos mixto: particionamiento alrededor de medoides aplicados a la matriz de distancia de Gower (ver r-bloggers.com/clustering-mixed-data-types-in-r ). El problema es que el cálculo de la matriz de distancia requiere mucha memoria, proporcional a O (n ^ 2), por lo tanto, para conjuntos de datos de más de 10 o 20,000 registros, estoy buscando variantes en el agrupamiento de k-medias que requieren menos memoria y pueden manejar Datos mixtos.
RobertF

@RobertF igual aquí. Desafortunadamente, el tamaño de datos factible es demasiado bajo para la mayoría de los problemas.
piggybox

20

(Además de la excelente respuesta de Tim Goodman)

La elección de los modos k es definitivamente el camino a seguir para la estabilidad del algoritmo de agrupamiento utilizado.

  1. El algoritmo de agrupamiento es libre de elegir cualquier puntaje de distancia / similitud. Euclidiana es la más popular. Pero se puede utilizar cualquier otra métrica que se escale de acuerdo con la distribución de datos en cada dimensión / atributo, por ejemplo, la métrica de Mahalanobis. Ilustra la distancia de los puntos de datos desde el centro según la métrica de distancia utilizada

  2. Con respecto a la agrupación mixta (numérica y categórica), un buen artículo que podría ayudar es: INCONCO: Agrupación interpretable de objetos numéricos y categóricos

  3. Más allá de k-means: dado que ya se ha descartado k-means de vainilla como un enfoque apropiado para este problema, me aventuraré más allá con la idea de pensar en la agrupación como un problema de ajuste de modelo. Diferentes medidas, como la métrica teórica de la información: la divergencia Kullback-Liebler funciona bien cuando se trata de converger un modelo paramétrico hacia la distribución de datos. (Por supuesto, las técnicas de agrupamiento paramétrico como GMM son más lentas que Kmeans, por lo que hay inconvenientes a considerar)

  4. La agrupación de modos K ​​difusos también suena atractiva, ya que las técnicas de lógica difusa se desarrollaron para tratar con datos categóricos. Consulte Agrupación difusa de datos categóricos utilizando centroides difusos para obtener más información.

También echa un vistazo a: ROCK: un algoritmo de agrupamiento robusto para atributos categóricos


17

Esta pregunta parece realmente sobre la representación, y no tanto sobre la agrupación.

Los datos categóricos son un problema para la mayoría de los algoritmos en el aprendizaje automático. Supongamos, por ejemplo, que tiene una variable categórica llamada "color" que podría adoptar los valores rojo, azul o amarillo. Si simplemente los codificamos numéricamente como 1,2 y 3 respectivamente, nuestro algoritmo pensará que el rojo (1) está realmente más cerca del azul (2) que del amarillo (3). Necesitamos usar una representación que le permita a la computadora entender que estas cosas son realmente igualmente diferentes.

Una manera simple es usar lo que se llama una representación única , y es exactamente lo que pensabas que deberías hacer. En lugar de tener una variable como "color" que puede tomar tres valores, la separamos en tres variables. Estos serían "color rojo", "color azul" y "color amarillo", que solo pueden tomar el valor 1 o 0.

Esto aumenta la dimensionalidad del espacio, pero ahora podría usar cualquier algoritmo de agrupación que desee. A veces tiene sentido zscore o blanquear los datos después de hacer este proceso, pero su idea es definitivamente razonable.


Estoy de acuerdo con tu respuesta HotEncoding es muy útil.
Pramit

4

También puede probar el algoritmo de agrupación de Expectation Maximization. Puede funcionar en datos categóricos y le dará una probabilidad estadística de qué valor (o valores) categóricos es más probable que tome un clúster.


2
¿Puedes ser mas específico? EM se refiere a un algoritmo de optimización que se puede usar para la agrupación. Hay muchas maneras de hacer esto y no es obvio lo que quieres decir.
bayer

@bayer, creo que la agrupación mencionada aquí es un modelo de mezcla gaussiana. GMM usualmente usa EM.
goh

1
No creo que eso sea lo que quiere decir, porque GMM no asume variables categóricas.
bayer

3

Depende de la variable categórica que se use. Para las variables ordinales, digamos como malo, promedio y bueno, tiene sentido usar una sola variable y tener valores de 0,1,2 y las distancias tienen sentido aquí (Avarage está más cerca de malo y bueno). Sin embargo, si no hay un orden, lo ideal sería usar una codificación activa como se mencionó anteriormente.


3

No debe usar la agrupación de k-means en un conjunto de datos que contenga tipos de datos mixtos. Por el contrario, hay una serie de algoritmos de agrupación que pueden manejar adecuadamente los tipos de datos mixtos. Algunas posibilidades incluyen lo siguiente:

1) Algoritmos basados ​​en particiones: prototipos k, exprimidor
2) Algoritmos jerárquicos: ROCK, enlace aglomerativo simple, promedio y completo
3) Algoritmos basados ​​en densidad: HIERDENC, MULIC, CLIQUE
4) Algoritmos basados ​​en modelos: agrupación SVM, Self -organizando mapas

Si desea obtener más información sobre estos algoritmos, el manuscrito 'Survey of Clustering Algorithms' escrito por Rui Xu ofrece una introducción completa al análisis de clústeres.


2

El objetivo de K-Means es reducir la varianza dentro del grupo, y debido a que calcula los centroides como el punto medio de un grupo, es necesario usar la distancia euclidiana para converger adecuadamente. Por lo tanto, si desea usar K-Means, debe asegurarse de que sus datos funcionen bien con ellos.

Representación

K-Means, y la agrupación en general, intenta dividir los datos en grupos significativos asegurándose de que las instancias en los mismos grupos sean similares entre sí. Por lo tanto, necesita una buena forma de representar sus datos para poder calcular fácilmente una medida de similitud significativa.

Usar una codificación única en variables categóricas es una buena idea cuando las categorías son equidistantes entre sí. Por ejemplo, si tiene el color azul claro, azul oscuro y amarillo, el uso de una codificación en caliente podría no brindarle los mejores resultados, ya que el azul oscuro y el azul claro probablemente estén "más cerca" entre sí que al amarillo.

En caso de que los valores categóricos no sean "equidistantes" y se puedan ordenar, también puede asignar un valor numérico a las categorías. Por ejemplo, niño, adolescente, adulto, podría representarse potencialmente como 0, 1 y 2. Esto tendría sentido porque un adolescente está "más cerca" de ser un niño que un adulto.

K-medoides

Un enfoque más genérico de K-Means es K-Medoids. K-Medoids funciona de manera similar a K-Means, pero la principal diferencia es que el centroide para cada grupo se define como el punto que reduce la suma de distancias dentro del grupo. Hacer cumplir esto le permite usar cualquier medida de distancia que desee y, por lo tanto, puede crear su propia medida personalizada que tendrá en cuenta qué categorías deben estar cerca o no.


1

Si consideramos un escenario en el que la variable categórica no puede codificarse en caliente como la variable categórica tiene más de 200 categorías.

En tales casos, puede usar un paquete clustMixType

Puede manejar datos mixtos (numéricos y categóricos), solo necesita alimentar los datos, segrega automáticamente los datos categóricos y numéricos.

Si encuentra algún problema, como que algunos valores numéricos están bajo categórico, puede as.factor () / viceversa as.numeric (), en ese campo respectivo y convertirlo en un factor e introducir esos nuevos datos en el algoritmo.

Calcule lambda, de modo que pueda ingresar como entrada en el momento de la agrupación.

incluso podemos obtener un WSS (dentro de la suma de cuadrados), trazar (gráfico de codo) para encontrar el número óptimo de Clusters.

Espero que esta respuesta te ayude a obtener resultados más significativos.


1

Muchos de los anteriores señalaron que k-means se puede implementar en variables categóricas y continuas, lo cual es incorrecto y los resultados deben tomarse con una pizca de sal.

Como se mencionó anteriormente en @Tim arriba, no tiene sentido calcular la distancia euclidiana entre los puntos que no tienen escala ni orden. Cuando uno codifica las variables categóricas, genera una matriz dispersa de 0 y 1. Como el rango de los valores es fijo y entre 0 y 1, deben normalizarse de la misma manera que las variables continuas. Los puntajes Z están acostumbrados a encontrar la distancia entre los puntos. Lo que sigue siendo, no del todo correcto. Explicaré esto con un ejemplo. Como las categorías son mutuamente excluyentes, la distancia entre dos puntos con respecto a las variables categóricas, toma uno de los dos valores, alto o bajo, es decir, los dos puntos pertenecen a la misma categoría o no lo son. Debido a estos valores extremos, el algoritmo termina dando más peso a las variables continuas para influir en la formación del clúster. Esto se puede verificar mediante una simple verificación al ver qué variables están influyendo y se sorprenderá al ver que la mayoría de ellas serán variables categóricas. (Formas de encontrar las variables más influyentes [1])

Un ejemplo: considere un país variable categórico. Ahora, como sabemos, la distancia (disimilitud) entre las observaciones de diferentes países es igual (suponiendo que no haya otras similitudes como los países vecinos o los países del mismo continente). Pero, al contrario de esto, si calcula las distancias entre las observaciones después de normalizar los valores codificados en caliente, serán inconsistentes (aunque la diferencia es menor) junto con el hecho de que toman valores altos o bajos.

En última instancia, la mejor opción disponible para python son los prototipos k que pueden manejar variables categóricas y continuas.

[1]: Encontrar las variables más influyentes en la formación del clúster: https://stackoverflow.com/a/53081779/8224401


0

Los modelos de mezcla se pueden usar para agrupar un conjunto de datos compuesto por variables continuas y categóricas.

Puede usar el paquete R VarSelLCM (disponible en CRAN) que modela, dentro de cada grupo, las variables continuas por distribuciones gaussianas y las variables ordinales / binarias. Tenga cuidado de almacenar sus datos en un data.frame donde las variables continuas son "numéricas" y las variables categóricas son "factor".

Un tutorial está disponible en: http://varsellcm.r-forge.r-project.org/

Además, los valores perdidos pueden ser gestionados por el modelo en cuestión.


0

Me encontré con el mismo problema e intenté resolverlo (sin saber que existían los prototipos k), la rica literatura con la que me encontré se originó a partir de la idea de no medir las variables con la misma métrica de distancia. Además, pueden existir varias fuentes de información, que pueden implicar diferentes estructuras o "vistas" de los datos. Este es un problema natural, cada vez que enfrenta relaciones sociales como las de Twitter / sitios web, etc.

Una de las posibles soluciones es abordar cada subconjunto de variables (es decir, numérico y categórico) por separado. Es fácilmente comprensible lo que hace una medida de distancia en una escala numérica. Los datos categóricos por sí solos se pueden entender fácilmente: considere tener vectores de observación binarios: la tabla de contingencia en 0/1 entre dos vectores de observación contiene mucha información sobre la similitud entre esas dos observaciones. Existe abundante literatura sobre las diversas medidas de similitud personalizadas en vectores binarios, la mayoría a partir de la tabla de contingencia.

Dadas ambas matrices de distancia / similitud, ambas describiendo las mismas observaciones, uno puede extraer un gráfico en cada una de ellas (Multi-View-Graph-Clustering) o extraer un solo gráfico con múltiples bordes: cada nodo (observación) con tantos bordes para otro nodo, ya que hay matrices de información (Multi-Edge-Clustering). A cada borde se le asigna el peso de la medida de similitud / distancia correspondiente. Empieza aqui: listado de Github de algoritmos de agrupamiento de gráficos y sus documentos. Como hay múltiples conjuntos de información disponibles en una sola observación, estos deben entrelazarse utilizando, por ejemplo, descendientes de análisis espectral o factorización de matriz vinculada. El análisis espectral es el método predeterminado para encontrar partes altamente conectadas o muy ponderadas de gráficos individuales. Al tener una incorporación espectral de los datos entretejidos, cualquier algoritmo de agrupación en datos numéricos puede funcionar fácilmente. El valor predeterminado de la literatura es kmeans por cuestiones de simplicidad, pero mucho más avanzado, y no como algoritmos restrictivos que se pueden usar indistintamente en este contexto.

Me gustó la belleza y la generalidad de este enfoque, ya que es fácilmente extensible a múltiples conjuntos de información en lugar de simples tipos y además respeta la "medida" específica en cada subconjunto de datos. Esto no lo alivia al ajustar el modelo con varias métricas de distancia y similitud o al escalar sus variables (me encontré escalando las variables numéricas a escalas de relación en el contexto de mi análisis)

Desde una perspectiva de escalabilidad, considere que existen principalmente dos problemas:

  1. Aproximación del problema de Eigen (donde también existe una rica literatura de algoritmos)
  2. Estimación de la matriz de distancia (un problema puramente combinatorio, que crece mucho muy rápidamente, todavía no he encontrado una manera eficiente de solucionarlo)

¡Diviértete con eso!


0

Es posible que desee ver la ingeniería automática de características: http://www.orges-leka.de/automatic_feature_engineering.html . El método se basa en Bourgain Embedded y se puede utilizar para derivar características numéricas de marcos de datos mixtos categóricos y numéricos o para cualquier conjunto de datos que admita distancias entre dos puntos de datos. Después de haber transformado los datos solo en características numéricas, se puede usar el agrupamiento de K-means directamente en ese momento