Regroupement K-Means pour des données numériques et catégoriques mixtes

Mon ensemble de données contient un certain nombre d'attributs numériques et un catégorique.

Dis NumericAttr1, NumericAttr2, ..., NumericAttrN, CategoricalAttr,

où CategoricalAttrprend l' une des trois valeurs possibles: CategoricalAttrValue1, CategoricalAttrValue2ou CategoricalAttrValue3.

J'utilise l'algorithme de clustering k-means par défaut pour Octave https://blog.west.uni-koblenz.de/2012-07-14/a-working-k-means-code-for-octave/ . Cela fonctionne uniquement avec des données numériques.

Ma question est donc la suivante: est-il correct de scinder l’attribut catégorique CategoricalAttren trois variables numériques (binaires), par exemple IsCategoricalAttrValue1, IsCategoricalAttrValue2, IsCategoricalAttrValue3?

L'algorithme k-means standard n'est pas directement applicable aux données catégorielles, pour diverses raisons. L'espace échantillon pour les données catégorielles est discret et n'a pas d'origine naturelle. Une fonction de distance euclidienne sur un tel espace n'a pas vraiment de sens. Comme quelqu'un l'a dit, "le fait qu'un serpent ne possède ni roues ni jambes ne nous permet de rien dire sur la valeur relative des roues et des jambes". (à partir d' ici )

Il existe une variation de k-moyennes connue sous le nom de k-modes, présentée dans cet article par Zhexue Huang, qui convient aux données catégorielles. Notez que les solutions que vous obtenez sont sensibles aux conditions initiales, comme expliqué ici (PDF), par exemple.

L'article de Huang (lien ci-dessus) contient également une section sur les "k-prototypes" qui s'applique aux données combinant des caractéristiques catégorielles et numériques. Il utilise une mesure de distance qui mélange la distance de Hamming pour les entités qualitatives et la distance euclidienne pour les entités numériques.

Une recherche sur Google "mélange de données catégorielles avec k-means" donne quelques articles plus récents sur divers algorithmes pour la mise en cluster de type k-means avec un mélange de données catégoriques et numériques. (Je ne les ai pas encore lues, je ne peux donc pas en parler.)

En fait, ce que vous suggérez (convertir les attributs catégoriques en valeurs binaires, puis faire k-means comme s'il s'agissait de valeurs numériques) est une autre approche qui a été essayée auparavant (avant les k-modes). (Voir Ralambondrainy, H. 1995. Une version conceptuelle de l'algorithme k-means. Pattern Recognition Letters, 16: 1147–1157.) Mais je crois que l'approche des modes k est préférable pour les raisons que j'ai indiquées ci-dessus.

À mon avis, il existe des solutions pour traiter les données catégorielles dans le clustering. R vient avec une distance spécifique pour les données catégorielles. Cette distance s'appelle Gower ( http://www.rdocumentation.org/packages/StatMatch/versions/1.2.0/topics/gower.dist ) et cela fonctionne plutôt bien.

(En plus de l'excellente réponse de Tim Goodman)

Le choix des k-modes est certainement la voie à suivre pour la stabilité de l'algorithme de classification utilisé.

1. L'algorithme de clustering est libre de choisir n'importe quel métrique de distance / score de similarité. Euclidien est le plus populaire. Mais vous pouvez utiliser n'importe quelle autre métrique qui évolue en fonction de la distribution des données dans chaque dimension / attribut, par exemple la métrique de Mahalanobis.

2. En ce qui concerne le regroupement mixte (numérique et catégorique), voici un bon document qui pourrait vous aider: INCONCO: regroupement interprétable d'objets numériques et catégoriques

3. Au-delà de k-means: Puisque k-means a déjà été exclu en tant qu'approche appropriée de ce problème, j'irai au-delà de l'idée de penser à la mise en cluster comme un problème d'ajustement de modèle. Différentes mesures, telles que la métrique de la théorie de l'information: la divergence de Kullback-Liebler fonctionnent bien lorsque vous essayez de faire converger un modèle paramétrique vers la distribution de données. (Bien sûr, les techniques de classification paramétrique telles que GMM sont plus lentes que Kmeans, il y a donc des inconvénients à prendre en compte)

4. La mise en grappes des modes k flous semble également intéressante, car des techniques de logique floue ont été développées pour traiter quelque chose comme des données catégoriques. Reportez-vous à la rubrique Classification floue de données catégoriques à l'aide de centroïdes floues pour plus d'informations.

Consultez également: ROCK: un algorithme de classification robuste pour les attributs catégoriques

Cette question semble vraiment concerner la représentation et pas tellement le clustering.

Les données catégoriques sont un problème pour la plupart des algorithmes d'apprentissage automatique. Supposons, par exemple, que vous ayez une variable catégorique appelée "couleur" pouvant prendre les valeurs rouge, bleu ou jaune. Si nous les codons simplement numériquement respectivement 1,2 et 3, notre algorithme pensera que le rouge (1) est plus proche du bleu (2) que du jaune (3). Nous devons utiliser une représentation qui permet à l’ordinateur de comprendre que ces éléments sont en réalité également différents.

Un moyen simple consiste à utiliser ce que l'on appelle une représentation one-hot , et c'est exactement ce que vous pensiez devoir faire. Plutôt que d'avoir une variable comme "couleur" pouvant prendre trois valeurs, nous la séparons en trois variables. Celles-ci seraient "couleur rouge", "couleur bleu" et "couleur jaune", qui ne peuvent toutes prendre que la valeur 1 ou 0.

Cela augmente la dimensionnalité de l'espace, mais vous pouvez maintenant utiliser n'importe quel algorithme de clustering de votre choix. Il est parfois utile de supprimer ou de blanchir les données après avoir effectué ce processus, mais votre idée est tout à fait raisonnable.

Vous pouvez également donner l’essai à l’algorithme de classification d’optimisation d’espérance. Il peut fonctionner sur des données catégorielles et vous donnera une probabilité statistique de déterminer quelle (s) valeur (s) catégorielle (s) une grappe est la plus susceptible de prendre.

Cela dépend de votre variable catégorique utilisée. Pour les variables ordinales, telles que mauvaises, moyennes et bonnes, il est logique d’utiliser une seule variable et d’avoir les valeurs 0,1,2 et les distances ont un sens ici (la moyenne est plus proche de la valeur mauvaise et bonne). Cependant, s'il n'y a pas d'ordre, vous devriez idéalement utiliser un codage à chaud comme mentionné ci-dessus.

Vous ne devez pas utiliser la mise en cluster de k-means sur un ensemble de données contenant des types de données mixtes. Au lieu de cela, un certain nombre d'algorithmes de clustering peuvent gérer de manière appropriée des types de données mélangés. Certaines possibilités incluent les suivantes:

1) Algorithmes basés sur le partitionnement: k-Prototypes, Squeezer
2) Algorithmes hiérarchiques: ROCK, couplage simple, moyen et complet aggloméré
3) Algorithmes basés sur la densité: HIERDENC, MULIC, CLIQUE
4) Algorithmes basés sur un modèle: Mise en cluster de SVM, Self -organiser des cartes

Si vous souhaitez en savoir plus sur ces algorithmes, le manuscrit "Survey of Clustering Algorithms" de Rui Xu propose une introduction complète à l'analyse par cluster.

L'objectif de K-Means est de réduire la variance au sein d'une grappe. Etant donné qu'il calcule les centroïdes comme le point moyen d'une grappe, il est nécessaire d'utiliser la distance euclidienne pour converger correctement. Par conséquent, si vous souhaitez utiliser absolument K-Means, vous devez vous assurer que vos données fonctionnent correctement.

Représentation

K-Means, et le clustering en général, essaie de partitionner les données en groupes significatifs en s'assurant que les instances dans les mêmes clusters sont semblables les unes aux autres. Par conséquent, vous avez besoin d'un bon moyen de représenter vos données afin de pouvoir facilement calculer une mesure de similarité significative.

Utiliser l'encodage à chaud sur les variables catégorielles est une bonne idée lorsque les catégories sont à égale distance les unes des autres. Par exemple, si vous avez les couleurs bleu clair, bleu foncé et jaune, utiliser un encodage à chaud ne donnera pas les meilleurs résultats car le bleu foncé et le bleu clair sont probablement plus proches l'un de l'autre qu'ils ne le sont en jaune.

Si les valeurs catégorielles ne sont pas "équidistantes" et peuvent être commandées, vous pouvez également attribuer une valeur numérique aux catégories. Par exemple, enfant, adolescent, adulte pourrait potentiellement être représenté par 0, 1 et 2. Cela aurait du sens, car un adolescent est «plus proche» d’être un enfant que l’adulte.

K-Medoids

K-Medoids est une approche plus générique de K-Means. K-Medoids fonctionne de la même manière que K-Means, à la différence que le centre de gravité de chaque cluster est défini comme le point qui réduit la somme des distances au sein d'un cluster. L'application de cette règle vous permet d'utiliser n'importe quelle mesure de distance et vous pouvez donc créer votre propre mesure personnalisée qui tiendra compte des catégories qui doivent être proches ou non.

Si nous considérons un scénario dans lequel la variable catégorielle ne peut pas être codée à chaud, comme la variable catégorielle contient plus de 200 catégories.

Dans ce cas, vous pouvez utiliser un package clustMixType

Il peut gérer des données mixtes (numériques et catégoriques), il vous suffit de les introduire, il sépare automatiquement les données catégorielles et numériques.

Si vous rencontrez des problèmes tels que des valeurs numériques sont sous-catégories, vous pouvez alors as.factor () / vice-versa as.numeric (), convertir ce facteur en facteur et insérer ces nouvelles données dans l'algorithme.

Calculez lambda pour pouvoir alimenter en entrée au moment de la mise en cluster.

nous pouvons même obtenir un WSS (dans la somme des carrés), un graphique (diagramme en coude) pour trouver le nombre optimal de grappes.

J'espère que cette réponse vous aidera à obtenir des résultats plus significatifs.

Un grand nombre des réponses ci-dessus ont indiqué que k-moyennes peut être implémenté sur des variables catégoriques et continues, ce qui est faux et les résultats doivent être pris avec une pincée de sel.

Comme mentionné ci-dessus par @Tim ci-dessus, le calcul de la distance euclidienne entre les points qui n'ont ni échelle ni ordre n'a pas de sens. Lorsque vous codez les variables catégoriques à chaud, vous générez une matrice fragmentée de 0 et de 1. Comme la plage de valeurs est fixe et comprise entre 0 et 1, elles doivent être normalisées de la même manière que les variables continues. Les Z-scores sont utilisés pour trouver la distance entre les points. Ce qui n'est toujours pas parfaitement correct. Je vais expliquer cela avec un exemple. Comme les catégories s’excluent mutuellement, la distance entre deux points par rapport aux variables catégorielles prend deux valeurs, haute ou basse, c’est-à-dire que les deux points appartiennent à la même catégorie ou ne le sont pas. En raison de ces valeurs extrêmes, l'algorithme finit par donner plus de poids que les variables continues pour influencer la formation de la grappe. Cela peut être vérifié par une simple vérification en identifiant les variables qui influencent et vous serez surpris de voir que la plupart d'entre elles seront des variables catégoriques. (Moyens de trouver les variables les plus influentes [1])

Un exemple: considérons une variable catégorique pays. Maintenant, comme nous le savons, la distance (dissimilarité) entre les observations de différents pays est égale (en supposant qu’aucune autre similitude ne ressemble à celle des pays voisins ou des pays du même continent). Mais contrairement à cela, si vous calculez les distances entre les observations après normalisation des valeurs codées à chaud, elles seront incohérentes (bien que la différence soit mineure), ainsi que le fait qu'elles prennent des valeurs hautes ou basses.

En définitive, la meilleure option disponible pour python est k-prototypes, qui peuvent gérer des variables tant catégoriques que continues.

[1]: Recherche des variables les plus influentes dans la formation d'un cluster: https://stackoverflow.com/a/53081779/8224401

Les modèles de mélange peuvent être utilisés pour regrouper un ensemble de données composé de variables continues et catégorielles.

Vous pouvez utiliser le package R VarSelLCM (disponible sur CRAN) qui modélise, au sein de chaque cluster, les variables continues par distributions gaussiennes et les variables ordinales / binaires. Veillez à stocker vos données dans un data.frame où les variables continues sont "numériques" et les variables catégorielles sont "factorielles".

Un tutoriel est disponible sur: http://varsellcm.r-forge.r-project.org/

De plus, les valeurs manquantes peuvent être gérées par le modèle en question.

Je suis tombé sur le même problème et j'ai essayé d'y réfléchir (sans savoir que les k-prototypes existaient). La littérature abondante à laquelle je me trouvais confrontée est née de l'idée de ne pas mesurer les variables avec la même métrique de distance. De plus, il peut exister diverses sources d’informations, pouvant impliquer différentes structures ou "vues" des données. C'est un problème naturel, chaque fois que vous rencontrez des relations sociales telles que celles sur Twitter / sites Web, etc.

L'une des solutions possibles consiste à traiter chaque sous-ensemble de variables (c.-à-d. Numériques et catégoriques) séparément. Il est facile de comprendre ce qu’une mesure de distance fait sur une échelle numérique. Les données catégoriques en elles-mêmes peuvent tout aussi bien être comprises. Envisagez d’avoir des vecteurs d’observation binaires: Le tableau de contingence à 0/1 entre deux vecteurs d’observation contient de nombreuses informations sur la similarité entre ces deux observations. Il existe une littérature abondante sur les différentes mesures de similarité personnalisées sur des vecteurs binaires - la plupart à partir du tableau de contingence.

Étant donné les deux matrices de distance / similarité, décrivant les mêmes observations, on peut extraire un graphe sur chacune d’elles (Multi-View-Graph-Clustering) ou extraire un seul graphe avec plusieurs arêtes - chaque nœud (observation) avec autant d’arêtes à un autre nœud, car il existe des matrices d’information (Multi-Edge-Clustering). Chaque bord se voit attribuer le poids de la mesure simmilarity / distance correspondante. Commencez ici: Liste Github des algorithmes de clustering de graphes et leurs papiers. Comme il existe plusieurs ensembles d'informations disponibles sur une seule observation, ceux-ci doivent être entrelacés en utilisant, par exemple, les descendants de l'analyse spectrale ou de la factorisation matricielle liée. L'analyse spectrale étant la méthode par défaut pour trouver des parties fortement connectées ou fortement pondérées de graphes simples. Avec une incorporation spectrale des données entrelacées, tout algorithme de regroupement sur des données numériques peut facilement fonctionner. Le défaut de la littérature est kméen pour des raisons de simplicité, mais beaucoup plus avancé - et non comme algorithmes restrictifs sont disponibles qui peuvent être utilisés de manière interchangeable dans ce contexte.

J'ai aimé la beauté et la généralité de cette approche, car elle peut facilement être étendue à de multiples ensembles d'informations plutôt qu'à de simples types et à son respect pour la "mesure" spécifique de chaque sous-ensemble de données. Cela ne vous dispense pas de peaufiner le modèle avec diverses métriques de distance et de similarité ou de redimensionner vos variables (je me suis retrouvé à redimensionner les variables numériques à des ratios à échelle proportionnelle dans le cadre de mon analyse).

Du point de vue de l'évolutivité, il y a principalement deux problèmes:

1. Approximation de problème propre (où existe aussi une riche littérature d'algorithmes)
2. Estimation de la distance matricielle (problème purement combinatoire, qui s'agrandit très rapidement - je n'ai pas encore trouvé de solution efficace)

Aie du plaisir avec ça!

Vous voudrez peut-être vous intéresser à l'ingénierie automatique des fonctionnalités: http://www.orges-leka.de/automatic_feature_engineering.html . La méthode est basée sur l’incorporation de Bourgain et peut être utilisée pour dériver des caractéristiques numériques à partir de trames de données numériques et catégoriques mixtes ou pour n’importe quel jeu de données prenant en charge les distances entre deux points de données. Après avoir transformé les données en fonctions numériques seulement, on peut utiliser directement la classification K-means