K-Means Clustering für gemischte numerische und kategoriale Daten

133

Mein Datensatz enthält eine Reihe numerischer und eine kategoriale Attribute.

Sagen Sie NumericAttr1, NumericAttr2, ..., NumericAttrN, CategoricalAttr,

wo CategoricalAttrnimmt einen von drei möglichen Werten: CategoricalAttrValue1, CategoricalAttrValue2oder CategoricalAttrValue3.

Ich verwende die standardmäßige Implementierung des k-means-Clustering-Algorithmus für Octave https://blog.west.uni-koblenz.de/2012-07-14/a-working-k-means-code-for-octave/ . Es funktioniert nur mit numerischen Daten.

Also meine Frage: Ist es richtig, das kategoriale Attribut CategoricalAttrin drei numerische (binäre) Variablen aufzuteilen , wie IsCategoricalAttrValue1, IsCategoricalAttrValue2, IsCategoricalAttrValue3?

IharS
quelle
7
Ja, die 1-aus-n-Kodierung ist ebenfalls gültig.
Sean Owen
1
Vielleicht wäre dieser Ansatz nützlich: zeszyty-naukowe.wwsi.edu.pl/zeszyty/zeszyt12/…
Haben Sie eine Idee zum Clustering-Mix "TIME SERIES" von kategorialen und numerischen Daten?
Leila Yousefi

Antworten:

122

Der standardmäßige k-means-Algorithmus ist aus verschiedenen Gründen nicht direkt auf kategoriale Daten anwendbar. Der Beispielbereich für kategoriale Daten ist diskret und hat keinen natürlichen Ursprung. Eine euklidische Distanzfunktion auf einem solchen Raum ist nicht wirklich sinnvoll. Wie jemand sagte: "Die Tatsache, dass eine Schlange weder Räder noch Beine besitzt, erlaubt es uns, nichts über den relativen Wert von Rädern und Beinen zu sagen." (von hier )

Es gibt eine Variation von k-Mitteln, die als k-Modi bekannt sind und in diesem Artikel von Zhexue Huang vorgestellt wurden und für kategoriale Daten geeignet sind. Beachten Sie, dass die Lösungen, die Sie erhalten, empfindlich auf Anfangsbedingungen reagieren, wie hier beschrieben (PDF).

Huangs Artikel (oben verlinkt) enthält auch einen Abschnitt über "k-Prototypen", der sich auf Daten mit einer Mischung aus kategorialen und numerischen Merkmalen bezieht. Es wird ein Abstandsmaß verwendet, das den Hamming-Abstand für kategoriale Merkmale und den euklidischen Abstand für numerische Merkmale mischt.

Bei einer Google-Suche nach "k-means mix of categorical data" werden einige neuere Arbeiten zu verschiedenen Algorithmen für k-means-like clustering mit einer Mischung aus kategorialen und numerischen Daten angezeigt. (Ich habe sie noch nicht gelesen, daher kann ich ihre Verdienste nicht kommentieren.)


Tatsächlich ist das, was Sie vorschlagen (Konvertieren von kategorialen Attributen in Binärwerte und dann Ausführen von k-means, als ob dies numerische Werte wären), ein anderer Ansatz, der zuvor versucht wurde (vor k-Modi). (Siehe Ralambondrainy, H. 1995. Eine konzeptionelle Version des k-means-Algorithmus. Pattern Recognition Letters, 16: 1147–1157.) Ich glaube jedoch, dass der k-mode-Ansatz aus den oben genannten Gründen bevorzugt wird.

Tim Goodman
quelle
10
Wenn Sie Ihre numerischen Features auf den gleichen Bereich skalieren wie die binärisierten kategorialen Features, führt die Cosinus-Ähnlichkeit tendenziell zu sehr ähnlichen Ergebnissen wie der oben beschriebene Hamming-Ansatz. Ich habe keine solide Methode, um zu bestätigen, dass dies in allen Fällen funktioniert. Wenn ich also cat- und num-Daten gemischt habe, überprüfe ich das Clustering einer Stichprobe immer mit der einfachen Kosinusmethode, die ich erwähnt habe, und der komplizierteren Mischung mit Hamming. Wenn der Unterschied unbedeutend ist, bevorzuge ich die einfachere Methode.
Cwharland
1
Das klingt nach einem vernünftigen Ansatz, @cwharland. Bei näherer Betrachtung stelle ich auch fest, dass einer der Vorteile, die Huang für den k-Modi-Ansatz gegenüber Ralambondrainys bietet, darin besteht, dass Sie nicht für jeden Wert Ihrer kategorialen Variablen ein separates Merkmal einführen müssen OPs Fall, in dem er nur eine einzige kategoriale Variable mit drei Werten hat. Besser mit dem einfachsten Ansatz, der funktioniert.
Tim Goodman
3
Gute Antwort. Möglicherweise hilfreich: Ich habe Huangs k-Modi und k-Prototypen (und einige Variationen) in Python
implementiert
2
Ich empfehle nicht, kategoriale Attribute in numerische Werte umzuwandeln. Stellen Sie sich vor, Sie haben zwei Städtenamen: NY und LA. Wenn Sie NY Nummer 3 und LA Nummer 8 anwenden, ist die Entfernung 5, aber diese 5 hat nichts zu sehen, mit dem Unterschied zwischen NY und LA.
Adesantos
@adesantos Ja, das ist ein Problem bei der Darstellung mehrerer Kategorien mit einem einzigen numerischen Merkmal und der Verwendung einer euklidischen Distanz. Die Verwendung der Hamming-Distanz ist ein Ansatz; In diesem Fall beträgt der Abstand 1 für jedes Feature, das sich unterscheidet (und nicht die Differenz zwischen den numerischen Werten, die den Kategorien zugewiesen sind). Jede Kategorie zu einem eigenen Merkmal zu machen, ist ein anderer Ansatz (z. B. 0 oder 1 für "ist es NY" und 0 oder 1 für "ist es LA").
Tim Goodman
24

Meiner Meinung nach gibt es Lösungen für den Umgang mit kategorialen Daten beim Clustering. R hat einen bestimmten Abstand für kategoriale Daten. Diese Distanz heißt Gower ( http://www.rdocumentation.org/packages/StatMatch/versions/1.2.0/topics/gower.dist ) und funktioniert ziemlich gut.

adesantos
quelle
2
Dies ist der Ansatz, den ich für einen gemischten Datensatz verwende - Partitionierung um Medoide, die auf die Gower-Distanzmatrix angewendet werden (siehe r-bloggers.com/clustering-mixed-data-types-in-r ). Das Problem ist, dass das Berechnen der Distanzmatrix viel Speicher benötigt, proportional zu O (n ^ 2), daher suche ich für Datensätze mit mehr als 10 oder 20.000 Datensätzen nach Varianten von k-Means-Clustering, die weniger Speicher benötigen und damit umgehen können gemischte Daten.
RobertF
@RobertF gleich hier. Die realisierbare Datengröße ist leider für die meisten Probleme viel zu gering.
Piggybox
20

(Neben der hervorragenden Antwort von Tim Goodman)

Die Wahl der k-Modi ist definitiv der richtige Weg, um die Stabilität des verwendeten Clustering-Algorithmus zu gewährleisten.

  1. Der Clustering-Algorithmus kann eine beliebige Distanzmetrik / Ähnlichkeitsbewertung auswählen. Euklidisch ist das beliebteste. Es kann jedoch auch jede andere Metrik verwendet werden, die gemäß der Datenverteilung in jeder Dimension / jedem Attribut skaliert wird, z. B. die Mahalanobis-Metrik. Darstellung des Abstands von Datenpunkten vom Mittelpunkt basierend auf der verwendeten Abstandsmetrik.

  2. In Bezug auf gemischte (numerische und kategoriale) Clustering ist ein gutes Papier, das helfen könnte: INCONCO: Interpretierbare Clustering von numerischen und kategorialen Objekten

  3. Jenseits von k-means: Da ein einfacher Vanille-k-means-Ansatz als angemessener Ansatz für dieses Problem bereits ausgeschlossen wurde, werde ich über die Idee hinausgehen, Clustering als Modellanpassungsproblem zu betrachten. Verschiedene Maße, wie die informationstheoretische Metrik: Die Kullback-Liebler-Divergenz funktioniert gut, wenn versucht wird, ein parametrisches Modell in Richtung Datenverteilung zu konvergieren. (Natürlich sind parametrische Clustering-Techniken wie GMM langsamer als Kmeans, daher sind einige Nachteile zu berücksichtigen.)

  4. Das Clustering von Fuzzy-k-Modi klingt ebenfalls ansprechend, da Fuzzy-Logik-Techniken entwickelt wurden, um mit so etwas wie kategorialen Daten umzugehen. Weitere Informationen finden Sie unter Fuzzy-Clustering von kategorialen Daten mithilfe von Fuzzy-Zentroiden .

Schauen Sie sich auch Folgendes an : ROCK: Ein robuster Clustering-Algorithmus für kategoriale Attribute

Dynamischer Sternenstaub
quelle
17

Diese Frage scheint sich wirklich um Repräsentation und nicht so sehr um Clustering zu handeln.

Kategoriale Daten sind für die meisten Algorithmen beim maschinellen Lernen ein Problem. Angenommen, Sie haben eine kategoriale Variable namens "color", die die Werte "red", "blue" oder "yellow" annehmen könnte. Wenn wir diese Zahlen einfach als 1,2 bzw. 3 kodieren, wird unser Algorithmus annehmen, dass Rot (1) tatsächlich näher an Blau (2) liegt als an Gelb (3). Wir müssen eine Darstellung verwenden, die dem Computer verständlich macht, dass diese Dinge tatsächlich alle gleich unterschiedlich sind.

Eine einfache Möglichkeit besteht darin, eine so genannte One-Hot- Darstellung zu verwenden, und genau das haben Sie sich vorgenommen. Anstatt eine Variable wie "color" zu haben, die drei Werte annehmen kann, teilen wir sie in drei Variablen auf. Dies wären "Farbe-Rot", "Farbe-Blau" und "Farbe-Gelb", die alle nur den Wert 1 oder 0 annehmen können.

Dies vergrößert die Dimensionalität des Raums, aber jetzt können Sie jeden beliebigen Clustering-Algorithmus verwenden. Es ist manchmal sinnvoll, die Daten nach diesem Vorgang zu zscoren oder aufzuhellen, aber Ihre Idee ist auf jeden Fall vernünftig.

Jordan A
quelle
Ich stimme Ihrer Antwort zu. HotEncoding ist sehr nützlich.
Pramit
4

Sie können auch den Expectation Maximization-Clustering-Algorithmus ausprobieren. Es kann mit kategorialen Daten arbeiten und gibt Ihnen eine statistische Wahrscheinlichkeit, welchen kategorialen Wert (oder welche Werte) ein Cluster am wahrscheinlichsten annimmt.

user490
quelle
2
Kannst du genauer sein? EM bezieht sich auf einen Optimierungsalgorithmus, der zum Clustering verwendet werden kann. Es gibt viele Möglichkeiten, dies zu tun, und es ist nicht offensichtlich, was Sie meinen.
Bayer
@bayer, ich denke das hier erwähnte Clustering ist ein Gauß'sches Mischungsmodell. GMM verwendet normalerweise EM.
Goh
1
Ich denke nicht, dass er das meint, weil GMM keine kategorialen Variablen annimmt.
Bayer
3

Dies hängt von Ihrer verwendeten kategorialen Variablen ab. Für ordinale Variablen, wie schlecht, durchschnittlich und gut, ist es sinnvoll, nur eine Variable zu verwenden und Werte von 0,1,2 zu haben, und Entfernungen sind hier sinnvoll (Durchschnitt ist eher schlecht als gut). Wenn jedoch keine Bestellung vorliegt, sollten Sie im Idealfall eine Hot-Codierung verwenden, wie oben erwähnt.

RAM
quelle
3

Sie sollten k-means Clustering nicht für ein Dataset verwenden, das gemischte Datentypen enthält. Vielmehr gibt es eine Reihe von Clustering-Algorithmen, die gemischte Datentypen angemessen verarbeiten können. Einige Möglichkeiten umfassen Folgendes:

1) Partitionierungsbasierte Algorithmen: k-Prototypen, Squeezer
2) Hierarchische Algorithmen: ROCK, Agglomerative Single, Average und
Complete Linkage 3) Dichtebasierte Algorithmen: HIERDENC, MULIC, CLIQUE
4) Modellbasierte Algorithmen: SVM Clustering, Self Karten organisieren

Wenn Sie mehr über diese Algorithmen erfahren möchten, bietet das von Rui Xu verfasste Manuskript 'Survey of Clustering Algorithms' eine umfassende Einführung in die Clusteranalyse.

SR_ml
quelle
2

Das Ziel von K-Means ist es, die Varianz innerhalb des Clusters zu verringern. Da die Schwerpunkte als Mittelwert eines Clusters berechnet werden, muss der euklidische Abstand verwendet werden, um ordnungsgemäß zu konvergieren. Wenn Sie also unbedingt K-Means verwenden möchten, müssen Sie sicherstellen, dass Ihre Daten gut damit funktionieren.

Darstellung

K-Means und Clustering im Allgemeinen versuchen, die Daten in sinnvolle Gruppen zu unterteilen, indem sichergestellt wird, dass Instanzen in denselben Clustern einander ähnlich sind. Daher benötigen Sie eine gute Möglichkeit, Ihre Daten darzustellen, damit Sie auf einfache Weise ein aussagekräftiges Ähnlichkeitsmaß berechnen können.

Die One-Hot-Codierung für kategoriale Variablen ist eine gute Idee, wenn die Kategorien gleich weit voneinander entfernt sind. Wenn Sie beispielsweise die Farben Hellblau, Dunkelblau und Gelb verwenden, erzielen Sie mit der One-Hot-Codierung möglicherweise nicht die besten Ergebnisse, da Dunkelblau und Hellblau wahrscheinlich näher beieinander liegen als bei Gelb.

Falls der kategoriale Wert nicht "äquidistant" ist und bestellt werden kann, können Sie den Kategorien auch einen numerischen Wert geben. Beispielsweise können Kinder, Jugendliche und Erwachsene möglicherweise als 0, 1 und 2 dargestellt werden. Dies ist sinnvoll, da ein Teenager dem Kind näher ist als ein Erwachsener.

K-Medoids

Ein allgemeinerer Ansatz für K-Means ist K-Medoids. K-Medoids funktioniert ähnlich wie K-Means, aber der Hauptunterschied besteht darin, dass der Schwerpunkt für jeden Cluster als der Punkt definiert wird, der die Summe der Entfernungen innerhalb des Clusters verringert. Wenn Sie dies erzwingen, können Sie jede gewünschte Abstandsmessung verwenden. Daher können Sie eine eigene benutzerdefinierte Messung erstellen, die berücksichtigt, welche Kategorien nah sein sollten oder nicht.

Valentin Calomme
quelle
1

Wenn wir ein Szenario betrachten, in dem die kategoriale Variable nicht im laufenden Betrieb codiert werden kann, wie die kategoriale Variable über 200 Kategorien hat.

In solchen Fällen können Sie ein Paket clustMixType verwenden

Es kann mit gemischten Daten (numerisch und kategorial) umgehen, Sie müssen nur die Daten eingeben, es trennt automatisch kategoriale und numerische Daten.

Wenn Sie feststellen, dass Probleme wie numerische Probleme unter kategorial liegen, können Sie as.factor () / vice versa as.numeric () in das entsprechende Feld eingeben und dies in einen Faktor umwandeln und die neuen Daten in den Algorithmus einspeisen.

Berechnen Sie das Lambda, damit Sie es beim Clustering als Eingabe einspeisen können.

Wir können sogar ein WSS (innerhalb der Summe der Quadrate) und ein Diagramm (Ellbogendiagramm) erstellen, um die optimale Anzahl von Clustern zu ermitteln.

Ich hoffe, diese Antwort hilft Ihnen dabei, aussagekräftigere Ergebnisse zu erzielen.

Toros91
quelle
1

Viele der oben genannten Punkte wiesen darauf hin, dass k-means für Variablen implementiert werden kann, die kategorisch und kontinuierlich sind, was falsch ist und die Ergebnisse mit einer Prise Salz genommen werden müssen.

Wie oben von @Tim erwähnt, ist es nicht sinnvoll, den euklidischen Abstand zwischen den Punkten zu berechnen, die weder eine Skala noch eine Ordnung haben. Wenn Sie die kategorialen Variablen einmalig codieren, erzeugen Sie eine dünne Matrix aus Nullen und Einsen. Da der Bereich der Werte fest und zwischen 0 und 1 liegt, müssen sie wie kontinuierliche Variablen normalisiert werden. Mit den Z-Scores wird der Abstand zwischen den Punkten ermittelt. Welches ist immer noch nicht ganz richtig. Ich werde dies an einem Beispiel erläutern. Da sich die Kategorien gegenseitig ausschließen, nimmt der Abstand zwischen zwei Punkten in Bezug auf kategoriale Variablen entweder zwei Werte an, hoch oder niedrig, dh, entweder gehören die beiden Punkte zur gleichen Kategorie oder sie gehören nicht zur selben Kategorie. Aufgrund dieser Extremwerte Der Algorithmus gibt den stetigen Variablen letztendlich mehr Gewicht bei der Beeinflussung der Clusterbildung. Dies kann durch eine einfache Überprüfung überprüft werden, indem festgestellt wird, welche Variablen Einfluss haben, und Sie werden überrascht sein, dass die meisten davon kategorische Variablen sind. (Möglichkeiten, die einflussreichsten Variablen zu finden [1])

Ein Beispiel: Betrachten Sie ein kategoriales variables Land. Wie wir jetzt wissen, sind die Entfernungen (Unähnlichkeiten) zwischen Beobachtungen aus verschiedenen Ländern gleich (vorausgesetzt, es bestehen keine weiteren Ähnlichkeiten wie in Nachbarländern oder Ländern desselben Kontinents). Wenn Sie jedoch die Abstände zwischen den Beobachtungen nach dem Normalisieren der einen heiß codierten Werte berechnen, sind diese inkonsistent (obwohl der Unterschied geringfügig ist) und nehmen hohe oder niedrige Werte an.

Die beste Option für Python sind letztendlich k-Prototypen, die sowohl kategoriale als auch kontinuierliche Variablen verarbeiten können.

[1]: Ermittlung der einflussreichsten Variablen bei der Clusterbildung: https://stackoverflow.com/a/53081779/8224401

Tarun Kumar Yellapu
quelle
0

Mischmodelle können verwendet werden, um einen Datensatz zu gruppieren, der aus kontinuierlichen und kategorialen Variablen besteht.

Sie können das R-Paket VarSelLCM (verfügbar auf CRAN) verwenden, das innerhalb jedes Clusters die stetigen Variablen nach Gauß-Verteilungen und die Ordinal- / Binärvariablen modelliert. Achten Sie darauf, Ihre Daten in einem data.frame zu speichern, in dem fortlaufende Variablen "numerisch" und kategoriale Variablen "Faktor" sind.

Ein Tutorial finden Sie unter: http://varsellcm.r-forge.r-project.org/

Darüber hinaus können fehlende Werte vom vorliegenden Modell verwaltet werden.

user200668
quelle
0

Ich bin auf dasselbe Problem gestoßen und habe versucht, mich damit zu beschäftigen (ohne zu wissen, dass es k-Prototypen gibt). Die reiche Literatur, mit der ich selbst zu tun hatte, entstand aus der Idee, die Variablen überhaupt nicht mit derselben Abstandsmetrik zu messen. Weiterhin können verschiedene Informationsquellen existieren, die unterschiedliche Strukturen oder "Ansichten" der Daten implizieren können. Dies ist ein natürliches Problem, wenn Sie mit sozialen Beziehungen konfrontiert sind, z. B. auf Twitter / Websites usw.

Eine der möglichen Lösungen besteht darin, jede Teilmenge von Variablen (dh numerisch und kategorisch) separat zu behandeln. Es ist leicht nachvollziehbar, was ein Entfernungsmesser auf einer numerischen Skala bewirkt. Kategoriale Daten für sich allein können genauso gut verstanden werden: Betrachten Sie binäre Beobachtungsvektoren: Die Kontingenztabelle auf 0/1 zwischen zwei Beobachtungsvektoren enthält viele Informationen über die Ähnlichkeit zwischen diesen beiden Beobachtungen. Es gibt eine umfangreiche Literatur zu den verschiedenen benutzerdefinierten Ähnlichkeitsmaßen für binäre Vektoren - die meisten beginnen mit der Kontingenztabelle.

Wenn beide Entfernungs- / Ähnlichkeitsmatrizen dieselben Beobachtungen beschreiben, kann man auf jeder einen Graphen extrahieren (Multi-View-Graph-Clustering) oder einen einzelnen Graphen mit mehreren Kanten extrahieren - jeder Knoten (Beobachtung) mit so vielen Kanten wie möglich ein weiterer Knoten, da es Informationsmatrizen gibt (Multi-Edge-Clustering). Jeder Kante wird das Gewicht des entsprechenden Ähnlichkeits- / Entfernungsmaßes zugewiesen. Beginnen Sie hier: Github-Auflistung der Graph Clustering Algorithmen und ihrer Artikel. Da für eine Beobachtung mehrere Informationssätze verfügbar sind, müssen diese unter Verwendung von z. B. Nachkommen der Spektralanalyse oder der verknüpften Matrixfaktorisierung miteinander verwoben werden. Die Spektralanalyse ist die Standardmethode zum Auffinden stark verbundener oder schwer gewichteter Teile einzelner Diagramme. Mit einer spektralen Einbettung der verwobenen Daten kann jeder Cluster-Algorithmus für numerische Daten problemlos funktionieren. Die Standardeinstellung der Literatur ist aus Gründen der Einfachheit km, aber weit fortgeschrittener - und nicht, da es restriktive Algorithmen gibt, die in diesem Zusammenhang austauschbar sind.

Ich mochte die Schönheit und Allgemeingültigkeit dieses Ansatzes, da er leicht auf mehrere Informationsmengen anstatt auf bloße Datentypen erweiterbar ist und außerdem die spezifische "Kennzahl" in jeder Datenuntermenge berücksichtigt. Dies erleichtert Ihnen nicht die Feinabstimmung des Modells mit verschiedenen Abstands- und Ähnlichkeitsmetriken oder die Skalierung Ihrer Variablen (ich habe festgestellt, dass ich die numerischen Variablen im Kontext meiner Analyse in verhältnisskalierte Variablen skaliert habe).

Aus Sicht der Skalierbarkeit gibt es hauptsächlich zwei Probleme:

  1. Eigenproblemannäherung (wo auch eine reiche Literatur von Algorithmen existiert)
  2. Distanzmatrixschätzung (ein rein kombinatorisches Problem, das sehr schnell groß wird - ich habe noch keinen effizienten Weg gefunden, es zu umgehen)

Viel Spass damit!

Tim Ruhkopf
quelle
0

Möglicherweise möchten Sie sich das automatische Feature-Engineering ansehen: http://www.orges-leka.de/automatic_feature_engineering.html . Die Methode basiert auf Bourgain Embedding und kann verwendet werden, um numerische Merkmale aus gemischten kategorialen und numerischen Datenrahmen oder für jeden Datensatz abzuleiten, der Abstände zwischen zwei Datenpunkten unterstützt. Nachdem die Daten nur in numerische Merkmale umgewandelt wurden, kann man dann direkt K-Mittel-Clustering verwenden

orgesleka
quelle