K-oznacza grupowanie mieszanych danych liczbowych i kategorialnych


133

Mój zestaw danych zawiera szereg atrybutów liczbowych i jeden kategoryczny.

Powiedzieć NumericAttr1, NumericAttr2, ..., NumericAttrN, CategoricalAttr,

gdzie CategoricalAttrzajmuje jedną z trzech możliwych wartości: CategoricalAttrValue1, CategoricalAttrValue2lub CategoricalAttrValue3.

Używam domyślnej implementacji algorytmu klastrowania k-średnich dla Octave https://blog.west.uni-koblenz.de/2012-07-14/a-working-k-means-code-for-octave/ . Działa tylko z danymi numerycznymi.

Więc moje pytanie: czy poprawne jest podzielenie atrybutu kategorycznego CategoricalAttrna trzy zmienne numeryczne (binarne), takie jak IsCategoricalAttrValue1, IsCategoricalAttrValue2, IsCategoricalAttrValue3?


7
Tak, użycie kodowania 1-z-n jest również poprawne.
Sean Owen

1
Być może takie podejście byłoby przydatne: zeszyty-naukowe.wwsi.edu.pl/zeszyty/zeszyt12/…

Czy masz pojęcie o mieszaniu klastrów „TIME SERIES” w kategoriach danych liczbowych i liczbowych?
Leila Yousefi,

Odpowiedzi:


122

Standardowy algorytm k-średnich nie ma bezpośredniego zastosowania do danych kategorycznych z różnych powodów. Przykładowa przestrzeń dla danych kategorycznych jest dyskretna i nie ma naturalnego pochodzenia. Euklidesowa funkcja odległości na takiej przestrzeni nie ma tak naprawdę znaczenia. Jak ktoś to powiedział: „Fakt, że wąż nie ma kół ani nóg, nie pozwala nam nic powiedzieć o względnej wartości kół i nóg”. ( stąd )

Istnieje odmiana k-średnich, znana jako tryby k, wprowadzona w tym artykule przez Zhexue Huang, która jest odpowiednia dla danych kategorycznych. Zwróć uwagę, że otrzymane rozwiązania są wrażliwe na warunki początkowe, jak omówiono tutaj (PDF).

Artykuł Huanga (link powyżej) zawiera także sekcję dotyczącą „k-prototypów”, która dotyczy danych z mieszanką cech kategorycznych i liczbowych. Wykorzystuje miarę odległości, która mierzy odległość Hamminga dla cech jakościowych i odległość euklidesową dla cech liczbowych.

Wyszukiwarka Google dla „k-średnich miksu danych kategorycznych” ujawnia całkiem sporo najnowszych artykułów na temat różnych algorytmów klastrowania podobnego do k-średnich z mieszanką danych kategorycznych i liczbowych. (Jeszcze ich nie przeczytałem, więc nie mogę komentować ich zalet).


W rzeczywistości to, co sugerujesz (konwersja atrybutów kategorialnych na wartości binarne, a następnie wykonanie k-średnich, jakby były to wartości liczbowe), to inne podejście, które zostało wypróbowane wcześniej (wcześniejsze tryby k). (Patrz Ralambondrainy, H. 1995. Koncepcyjna wersja algorytmu k-średnich. Pattern Recognition Letters, 16: 1147–1157). Uważam jednak, że preferowane jest podejście k-modowe z powodów, które wskazałem powyżej.


10
Jeśli skalujesz cechy liczbowe do tego samego zakresu, co binarne cechy kategorialne, podobieństwo kosinusowe zwykle daje bardzo podobne wyniki do powyższego podejścia Hamminga. Nie mam solidnego sposobu na sprawdzenie, czy to działa we wszystkich przypadkach, więc kiedy mam mieszane dane cat i num, zawsze sprawdzam klastrowanie na próbce za pomocą prostej metody cosinusowej, o której wspomniałem, i bardziej skomplikowanej kombinacji z Hammingiem. Jeśli różnica jest nieznaczna, wolę prostszą metodę.
cwharland

1
To brzmi jak rozsądne podejście, @cwharland. Przy dalszym rozważaniu zauważam również, że jedna z zalet Huang w podejściu do trybu K w porównaniu z Ralambondrainy - że nie musisz wprowadzać osobnej cechy dla każdej wartości zmiennej kategorialnej - naprawdę nie ma znaczenia Przypadek OP, w którym ma tylko jedną zmienną kategorialną z trzema wartościami. Lepiej iść z najprostszym działającym działaniem.
Tim Goodman

3
Dobra odpowiedź. Potencjalnie pomocny: zaimplementowałem tryby k i prototypy Huanga (i niektóre odmiany) w Pythonie: github.com/nicodv/kmodes
Def_Os

2
Nie polecam przekształcania atrybutów kategorialnych na wartości liczbowe. Wyobraź sobie, że masz dwie nazwy miast: NY i LA. Jeśli zastosujesz NY numer 3 i LA numer 8, odległość wynosi 5, ale ta 5 nie ma nic do zauważenia z różnicą między NY i LA.
adesantos

@adesantos Tak, to jest problem z reprezentowaniem wielu kategorii za pomocą jednej funkcji numerycznej i używaniem odległości euklidesowej. Korzystanie z odległości Hamminga jest jednym podejściem; w takim przypadku odległość wynosi 1 dla każdej cechy, która się różni (zamiast różnicy między wartościami liczbowymi przypisanymi do kategorii). Nadanie każdej kategorii osobnej cechy to inne podejście (np. 0 lub 1 dla „czy to NY” i 0 lub 1 dla „czy to LA”).
Tim Goodman

24

Moim zdaniem istnieją rozwiązania dotyczące danych kategorycznych w klastrach. R ma określoną odległość dla danych jakościowych. Odległość ta nazywa się Gower ( http://www.rdocumentation.org/packages/StatMatch/versions/1.2.0/topics/gower.dist ) i działa całkiem dobrze.


2
Jest to podejście, którego używam do mieszanego zestawu danych - partycjonowanie wokół medoidów zastosowanych do macierzy odległości Gowera (patrz r-bloggers.com/clustering-mixed-data-types-in-r ). Problem polega na tym, że obliczanie macierzy odległości wymaga dużo pamięci, proporcjonalnej do O (n ^ 2), dlatego dla zbiorów danych większych niż 10 lub 20 000 rekordów patrzę na warianty k-oznacza grupowania, które wymagają mniej pamięci i mogą sobie poradzić mieszane dane.
RobertF

@RobertF to samo tutaj. Rzeczywisty rozmiar danych jest niestety zbyt niski dla większości problemów.
skarbonka

20

(Oprócz doskonałej odpowiedzi Tima Goodmana)

Wybór trybów K jest zdecydowanie drogą do stabilności używanego algorytmu klastrowania.

  1. Algorytm grupowania może dowolnie wybrać dowolny wskaźnik odległości / podobieństwo. Euklides jest najpopularniejszy. Można jednak użyć dowolnej innej metryki, która skaluje się zgodnie z rozkładem danych w każdym wymiarze / atrybucie, na przykład metryki Mahalanobisa. Ilustrowanie odległości punktów danych od centrum na podstawie zastosowanej metryki odległości.

  2. Jeśli chodzi o klastrowanie mieszane (numeryczne i kategoryczne), dobrym dokumentem, który może pomóc jest: INCONCO: Interpretable Clustering of Numberical and Categorical Objects

  3. Więcej niż k-średnich: Ponieważ zwykłe waniliowe k-średnie zostało już wykluczone jako odpowiednie podejście do tego problemu, odważę się myśleć o klastrowaniu jako problemie dopasowania modelu. Różne miary, takie jak metryka teoretyczna informacji: dywergencja Kullbacka-Lieblera działa dobrze, gdy próbuje się zbliżyć model parametryczny do rozkładu danych. (Oczywiście techniki parametrycznego grupowania, takie jak GMM, są wolniejsze niż Kmeans, więc należy wziąć pod uwagę wady)

  4. Grupowanie rozmytych trybów k również wydaje się atrakcyjne, ponieważ opracowano techniki logiki rozmytej, aby radzić sobie z czymś w rodzaju danych kategorycznych. Aby uzyskać więcej informacji, zobacz Rozmyte grupowanie danych kategorycznych za pomocą rozmytych centroidów .

Zobacz także: ROCK: Solidny algorytm grupowania atrybutów kategorycznych


17

To pytanie wydaje się dotyczyć reprezentacji, a nie klastrowania.

Dane kategoryczne stanowią problem w przypadku większości algorytmów uczenia maszynowego. Załóżmy na przykład, że masz zmienną kategoryczną o nazwie „kolor”, która może przyjmować wartości czerwony, niebieski lub żółty. Jeśli po prostu zakodujemy je liczbowo odpowiednio jako 1,2 i 3, nasz algorytm pomyśli, że czerwony (1) jest w rzeczywistości bliższy niebieskiemu (2) niż żółtemu (3). Musimy użyć reprezentacji, która pozwoli komputerowi zrozumieć, że wszystkie te rzeczy są tak samo różne.

Jednym prostym sposobem jest użycie tak zwanej „ gorącej reprezentacji” i dokładnie to, co Twoim zdaniem powinieneś zrobić. Zamiast mieć jedną zmienną, taką jak „kolor”, która może przyjmować trzy wartości, dzielimy ją na trzy zmienne. Byłyby to „kolor czerwony”, „kolor niebieski” i „kolor żółty”, które wszystkie mogą przyjmować tylko wartość 1 lub 0.

Zwiększa to wymiarowość przestrzeni, ale teraz możesz użyć dowolnego algorytmu klastrowania, który ci się podoba. Czasami ma sens zscore lub wybielanie danych po wykonaniu tego procesu, ale twój pomysł jest zdecydowanie uzasadniony.


Zgadzam się z twoją odpowiedzią. HotEncoding jest bardzo przydatny.
Pramit

4

Możesz także wypróbować algorytm grupowania Expectation Maximization. Może działać na danych kategorycznych i da ci statystyczne prawdopodobieństwo, że wartość (lub wartości) klastrowe najprawdopodobniej przyjmie.


2
Czy mógłbyś to sprecyzować? EM odnosi się do algorytmu optymalizacji, który można wykorzystać do tworzenia klastrów. Można to zrobić na wiele sposobów i nie jest oczywiste, co masz na myśli.
bayer

@ayer, myślę, że wspomniane tutaj grupowanie jest modelem mieszanki gaussowskiej. GMM zwykle używa EM.
goh

1
Nie sądzę, że o to mu chodzi, ponieważ GMM nie zakłada zmiennych kategorialnych.
bayer

3

To zależy od zastosowanej zmiennej jakościowej. W przypadku zmiennych porządkowych, np. Złych, średnich i dobrych, sensowne jest użycie jednej zmiennej i posiadanie wartości 0,1,2, a odległości mają tutaj sens (średnia jest bliższa złej i dobrej). Jeśli jednak nie ma zamówienia, najlepiej użyć jednego kodowania na gorąco, jak wspomniano powyżej.


3

Nie należy używać klastrowania k-średnich w zestawie danych zawierającym mieszane typy danych. Istnieje raczej szereg algorytmów klastrowych, które mogą odpowiednio obsługiwać mieszane typy danych. Niektóre możliwości obejmują:

1) Algorytmy oparte na partycjonowaniu: prototypy k, Squeezer
2) Algorytmy hierarchiczne: ROCK, połączenie aglomeracyjne pojedyncze, średnie i pełne
3) Algorytmy oparte na gęstości: HIERDENC, MULIC, CLIQUE
4) Algorytmy oparte na modelu: klastrowanie SVM, Self -organizowanie map

Jeśli chcesz dowiedzieć się więcej o tych algorytmach, rękopis „Survey of Clustering Algorytmy” napisany przez Rui Xu oferuje kompleksowe wprowadzenie do analizy skupień.


2

Celem K-Meansa jest zmniejszenie wariancji wewnątrz gromady, a ponieważ oblicza ona centroidy jako średni punkt gromady, konieczne jest użycie odległości euklidesowej , aby właściwie zbiegać się. Dlatego jeśli chcesz bezwzględnie używać K-Means, musisz upewnić się, że Twoje dane dobrze z nim współpracują.

Reprezentacja

K-Means i ogólnie klastrowanie próbuje podzielić dane na znaczące grupy, upewniając się, że instancje w tych samych klastrach są do siebie podobne. Dlatego potrzebujesz dobrego sposobu na przedstawienie swoich danych, abyś mógł łatwo obliczyć znaczącą miarę podobieństwa.

Używanie kodowania typu „hot” na zmiennych kategorialnych jest dobrym pomysłem, gdy kategorie są w równej odległości od siebie. Na przykład, jeśli masz kolor jasnoniebieski, ciemnoniebieski i żółty, użycie kodowania „na gorąco” może nie dać najlepszych rezultatów, ponieważ ciemnoniebieski i jasnoniebieski są prawdopodobnie „bliżej” niż do żółtego.

W przypadku, gdy wartość kategoryczna nie jest „w równej odległości” i można ją zamówić, można również nadać kategoriom wartość liczbową. Na przykład dziecko, nastolatek, dorosły może potencjalnie być reprezentowane jako 0, 1 i 2. To miałoby sens, ponieważ nastolatek jest „bliższy” byciu dzieckiem niż dorosły.

K-Medoidy

Bardziej ogólne podejście do K-średnich to K-Medoidy. K-Medoidy działają podobnie jak K-średnie, ale główna różnica polega na tym, że środek ciężkości każdej gromady jest zdefiniowany jako punkt, który zmniejsza sumę odległości wewnątrz gromady. Egzekwowanie tego pozwala na użycie dowolnej miary odległości, a zatem możesz zbudować własną miarę, która będzie uwzględniać, które kategorie powinny być zbliżone, czy nie.


1

Jeśli weźmiemy pod uwagę scenariusz, w którym zmienna kategorialna nie może być zakodowana na gorąco, tak jak zmienna kategorialna ma ponad 200 kategorii.

W takich przypadkach możesz użyć pakietu clustMixType

Może obsługiwać mieszane dane (numeryczne i kategoryczne), wystarczy tylko wprowadzić dane, automatycznie segreguje dane kategoryczne i numeryczne.

Jeśli stwierdzisz, że jakieś problemy, takie jak niektóre wartości liczbowe, są kategoryczne, możesz as.factor () / vice-versa as.numeric (), w tym odpowiednim polu i przekonwertować to na czynnik i wprowadzić nowe dane do algorytmu.

Oblicz lambda, abyś mógł wprowadzić dane wejściowe w momencie grupowania.

możemy nawet uzyskać WSS (w ramach sumy kwadratów), wykres (wykres łokciowy), aby znaleźć optymalną liczbę klastrów.

Mam nadzieję, że ta odpowiedź pomoże Ci uzyskać bardziej znaczące wyniki.


1

Wiele z powyższych wskazało, że k-średnich można zaimplementować na zmiennych, które są kategoryczne i ciągłe, co jest błędne, a wyniki należy wziąć ze szczyptą soli.

Jak wspomniano powyżej przez @Tim powyżej, nie ma sensu obliczać odległości euklidesowej między punktami, które nie mają skali ani porządku. Kiedy jednokrotnie kodujesz zmienne jakościowe, generujesz rzadką macierz zer i jedynek. Ponieważ zakres wartości jest stały i między 0 a 1, należy je znormalizować w taki sam sposób, jak zmienne ciągłe. Z-score służy do określania odległości między punktami. Co nadal nie jest do końca właściwe. Wyjaśnię to na przykładzie. Ponieważ kategorie wzajemnie się wykluczają, odległość między dwoma punktami w odniesieniu do zmiennych kategorialnych przyjmuje jedną z dwóch wartości, wysoką lub niską, tj. Albo dwa punkty należą do tej samej kategorii, albo nie. Ze względu na te ekstremalne wartości algorytm daje większą wagę nad zmiennymi ciągłymi, wpływając na tworzenie klastrów. Można to zweryfikować poprzez proste sprawdzenie, które zmienne mają wpływ, a będziesz zaskoczony, że większość z nich będzie zmiennymi kategorialnymi. (Sposoby znalezienia najbardziej wpływających zmiennych [1])

Przykład: Rozważ kategoryczny zmienny kraj. Teraz, jak wiemy, odległość (odmienność) między obserwacjami z różnych krajów jest równa (zakładając, że nie ma innych podobieństw, takich jak kraje sąsiednie lub kraje z tego samego kontynentu). Ale w przeciwieństwie do tego, jeśli obliczymy odległości między obserwacjami po normalizacji wartości zakodowanych na gorąco, będą one niespójne (choć różnica jest niewielka) wraz z faktem, że przyjmują wysokie lub niskie wartości.

Ostatecznie najlepszą dostępną opcją dla Pythona są prototypy k, które mogą obsługiwać zarówno zmienne jakościowe, jak i ciągłe.

[1]: Znajdowanie najbardziej wpływowych zmiennych w tworzeniu klastrów: https://stackoverflow.com/a/53081779/8224401


0

Modele mieszanin mogą być używane do grupowania zestawu danych złożonego ze zmiennych ciągłych i jakościowych.

Możesz użyć pakietu R VarSelLCM (dostępnego w CRAN), który modeluje w ramach każdego klastra zmienne ciągłe według rozkładów Gaussa oraz zmienne porządkowe / binarne. Zachowaj ostrożność, aby przechowywać dane w ramce data.frame, gdzie zmienne ciągłe są „numeryczne”, a zmienne kategorialne „czynnik”.

Samouczek jest dostępny na stronie: http://varsellcm.r-forge.r-project.org/

Ponadto brakującymi wartościami można zarządzać w danym modelu.


0

Natknąłem się na ten sam problem i próbowałem obejść go (nie wiedząc, że istniało k-prototypy). Bogata literatura, z którą się zetknąłem, zrodziła się z pomysłu, by w ogóle nie mierzyć zmiennych o tej samej metodzie odległości. Ponadto mogą istnieć różne źródła informacji, które mogą sugerować różne struktury lub „widoki” danych. Jest to naturalny problem, ilekroć masz do czynienia z relacjami społecznymi, takimi jak na Twitterze / stronach internetowych itp.

Jednym z możliwych rozwiązań jest osobne zajęcie się każdym podzbiorem zmiennych (tj. Liczbowym i kategorialnym). Łatwo jest zrozumieć, co robi miara odległości w skali numerycznej. Same dane kategoryczne mogą być równie łatwo zrozumiałe: rozważ binarne wektory obserwacyjne: Tabela kontyngencji na 0/1 między dwoma wektorami obserwacyjnymi zawiera wiele informacji na temat podobieństwa między tymi dwiema obserwacjami. Istnieje bogata literatura na temat różnych niestandardowych miar podobieństwa wektorów binarnych - większość począwszy od tabeli awaryjnej.

Biorąc pod uwagę obie macierze odległości / podobieństwa, obie opisujące te same obserwacje, można wyodrębnić wykres na każdym z nich (Multi-View-Graph-Clustering) lub wyodrębnić pojedynczy wykres z wieloma krawędziami - każdy węzeł (obserwacja) z tyloma krawędziami do inny węzeł, ponieważ istnieją matryce informacyjne (klastrowanie wielu krawędzi). Każda krawędź ma przypisany ciężar odpowiedniej miary podobieństwa / odległości. Zacznij tutaj: lista Github algorytmów klastrowania grafów i ich artykułów. Ponieważ w ramach jednej obserwacji dostępnych jest wiele zestawów informacji, należy je przeplatać przy użyciu np. Potomków analizy spektralnej lub faktoryzacji macierzy połączonej. Analiza spektralna jest domyślną metodą znajdowania silnie połączonych lub ważonych części pojedynczych wykresów. Po osadzeniu widmowym przeplecionych danych dowolny algorytm grupowania danych liczbowych może z łatwością działać. Domyślnie literatura to kmeany ze względu na prostotę, ale o wiele bardziej zaawansowane - i nie istnieją tak restrykcyjne algorytmy, które można stosować zamiennie w tym kontekście.

Podobało mi się piękno i ogólność w tym podejściu, ponieważ można je łatwo rozszerzyć na wiele zestawów informacji, a nie tylko na dyptyki, i dalej szanować konkretną „miarę” w każdym podzbiorze danych. Nie ułatwia to dostrojenia modelu za pomocą różnych wskaźników odległości i podobieństwa lub skalowania zmiennych (w kontekście mojej analizy skalowałem zmienne numeryczne do zmiennych skalowanych w stosunku)

Z perspektywy skalowalności należy wziąć pod uwagę, że istnieją głównie dwa problemy:

  1. Przybliżenie problemu własnego (tam gdzie istnieje bogata literatura algorytmów)
  2. Szacowanie macierzy odległości (problem czysto kombinatoryczny, który bardzo szybko rośnie - nie znalazłem jeszcze skutecznego sposobu na obejście go)

Baw się dobrze!


0

Możesz przyjrzeć się automatycznej inżynierii funkcji: http://www.orges-leka.de/automatic_feature_engineering.html . Metoda oparta jest na osadzaniu Bourgaina i może być używana do uzyskiwania cech numerycznych z mieszanych ramek danych kategorycznych i liczbowych lub do dowolnego zestawu danych, który obsługuje odległości między dwoma punktami danych. Po przekształceniu danych tylko w funkcje numeryczne można bezpośrednio użyć grupowania metodą K-średnich

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.