Czy w przypadku danych kategorycznych mogą istnieć klastry bez powiązanych zmiennych?

Próbując wyjaśnić analizy skupień, ludzie często błędnie rozumieją ten proces jako związany z korelacją zmiennych. Jednym ze sposobów na ominięcie tego zamieszania jest taki spisek:

To wyraźnie pokazuje różnicę między pytaniem, czy istnieją klastry, a pytaniem, czy zmienne są powiązane. Ilustruje to jednak tylko rozróżnienie dla ciągłych danych. Mam problem z myśleniem o analogu z danymi kategorycznymi:

ID  property.A  property.B
1   yes         yes
2   yes         yes
3   yes         yes
4   yes         yes
5   no          no
6   no          no
7   no          no
8   no          no

Widzimy, że istnieją dwa wyraźne klastry: ludzie o właściwościach A i B oraz ci, którzy nie mają żadnej. Jednak jeśli spojrzymy na zmienne (np. Za pomocą testu chi-kwadrat), są one wyraźnie powiązane:

tab
#      B
# A     yes no
#   yes   4  0
#   no    0  4
chisq.test(tab)
# X-squared = 4.5, df = 1, p-value = 0.03389

Uważam, że nie potrafię skonstruować przykładu z danymi kategorycznymi, analogicznymi do tego z ciągłymi danymi powyżej. Czy możliwe jest nawet tworzenie klastrów w danych czysto kategorialnych bez powiązania również zmiennych? Co jeśli zmienne mają więcej niż dwa poziomy lub gdy masz większą liczbę zmiennych? Jeśli grupowanie obserwacji niekoniecznie pociąga za sobą relacje między zmiennymi i odwrotnie, czy oznacza to, że grupowanie obserwacji nie jest tak naprawdę warte, gdy masz tylko dane kategoryczne (tj. Czy zamiast tego powinieneś po prostu przeanalizować zmienne)?

Aktualizacja: Wiele z pierwotnego pytania pozostawiłem, ponieważ chciałem skupić się na idei, że można stworzyć prosty przykład, który byłby natychmiast intuicyjny nawet dla kogoś, kto w dużej mierze nie był zaznajomiony z analizami skupień. Zdaję sobie jednak sprawę, że wiele klastrów zależy od wyboru odległości i algorytmów itp. Może to pomóc, jeśli podam więcej.

Rozumiem, że korelacja Pearsona jest naprawdę odpowiednia tylko dla ciągłych danych. W przypadku danych kategorycznych moglibyśmy pomyśleć o teście chi-kwadrat (dla dwukierunkowej tabeli kontyngencji) lub modelu logarytmiczno-liniowym (dla wielowymiarowych tabel kontyngencji) jako sposób oceny niezależności zmiennych kategorialnych.

W przypadku algorytmu możemy sobie wyobrazić stosowanie k-medoidów / PAM, które można zastosować zarówno do sytuacji ciągłej, jak i do danych kategorycznych. (Należy zauważyć, że częścią tego ciągłego przykładu jest to, że każdy rozsądny algorytm klastrowania powinien być w stanie wykryć te klastry, a jeśli nie, należy stworzyć bardziej ekstremalny przykład).

Odnośnie koncepcji odległości. Jako ciągły przykład założyłem euklidesowy, ponieważ byłby najbardziej podstawowy dla naiwnego widza. Przypuszczam, że odległość, która jest analogiczna dla danych kategorycznych (w tym, że byłaby najbardziej natychmiast intuicyjna), byłaby prostym dopasowaniem. Jestem jednak otwarty na dyskusje na inne odległości, jeśli prowadzi to do rozwiązania lub po prostu interesującej dyskusji.

Rozważ przypadek wyraźnego skupienia z nieskorelowanymi zmiennymi skalowymi - takimi jak prawy górny obraz w pytaniu. I kategoryzuj jego dane.

Podzieliliśmy zakres skali obu zmiennych X i Y na 3 przedziały, które teraz traktujemy jako etykiety kategoryczne. Ponadto zadeklarujemy je jako nominalne, a nie porządkowe, ponieważ zadawane pytanie dotyczy w sposób dorozumiany i przede wszystkim danych jakościowych. Rozmiar plamek to częstotliwość w komórce tabeli częstotliwości; wszystkie przypadki w tej samej komórce są uważane za identyczne.

Intuicyjnie i najogólniej „klastry” są zdefiniowane jako skrzepy punktów danych oddzielone rzadkimi regionami w „przestrzeni” danych. Początkowo dotyczyło to danych w skali i pozostaje to samo wrażenie w zestawieniu danych skategoryzowanych. X i Y są teraz kategoryczne, ale nadal wyglądają na nieskorelowane: asocjacja chi-kwadrat jest bardzo bliska zeru. I są tam klastry.

Ale pamiętajmy, że mamy do czynienia z kategoriami nominalnymi, których kolejność w tabeli jest dowolna. Możemy zmieniać kolejność całych wierszy i / lub kolumn, jak chcemy, bez wpływu na obserwowaną wartość chi-kwadrat. Dokonaj zmiany kolejności ...

... aby sprostać tym klastrom, które właśnie zniknęły. Cztery komórki, a1, a3, c1 i c3, mogą być zjednoczone w jednym klastrze. Więc nie, naprawdę nie mamy żadnych klastrów w danych kategorycznych.

Przypadki komórek a1 i c3 (lub podobnie a3 i c1) są całkowicie odmienne: nie dzielą tych samych atrybutów. Aby zaindukować klastry w naszych danych - a1 i c3, aby utworzyć klastry - musimy w dużym stopniu opróżnić mylące się komórki a3 i c1, usuwając te przypadki z zestawu danych.

Teraz istnieją klastry. Ale jednocześnie straciliśmy nieskorelację. Diagonalna struktura pokazano w tabeli sygnałów, że statystyka chi-Stare dostał daleko od zera.

Szkoda. Spróbujmy zachować jednocześnie nieskorelację i mniej lub bardziej wyraźne klastry. Możemy na przykład zdecydować o wystarczającym opróżnieniu samej komórki a3, a następnie uznać a1 + c1 za klaster przeciwny do klastra c3:

Ta operacja nie zbliżyła Chi-kwadrat do zera ...

[Indeed, table such as for example
 6   6   1
 6   6   1
 1   1   0
retains about the same very low chi-square association after
dividing 2nd column by 3 and multiplying 2nd row by 3, which gives
 6   2   1
18   6   3
 1  1/3  0
Cell (1,2) got thrice lower frequency. We had, however, to upheave
cell (2,1) frequency thrice, to keep Chi-sq almost as before.]

... ale sytuacja z klastrami jest zagmatwana. Klaster a1 + c1 zawiera przypadki częściowo identyczne, a częściowo częściowo odmienne. To, że klaster jest stosunkowo mało homogeniczny, samo w sobie nie jest wykluczeniem dla struktury jasnego klastra w zbiorze danych. Problem z naszymi kategorycznymi danymi polega jednak na tym, że klaster a1 + c1 nie jest w żaden sposób lepszy niż klaster c1 + c3, jego symetryczny analog. Oznacza to, że rozwiązanie klastrowe jest niestabilne - będzie zależeć od kolejności spraw w zbiorze danych. Niestabilne rozwiązanie, nawet jeśli jest względnie „zgrupowane”, jest złym rozwiązaniem, zawodnym.

Jedynym sposobem na rozwiązanie problemu i uczynienie rozwiązania zarówno klarownym, jak i stabilnym będzie rozwiązanie komórki c3 z komórki c1 poprzez przeniesienie jej danych poniżej do komórki b3 (lub b2).

Mamy więc czyste klastry a1 + c1 vs b3. Ale spójrz, tutaj znowu pojawia się ukośny wzór - a chi-kwadrat stołu ogranicza się powyżej zera.

Wnioski . Niemożliwe jest jednoczesne posiadanie dwóch niepowiązanych zmiennych chi-kwadrat i dobrych klastrów przypadków danych. Przejrzyste i stabilne klastry sugerują indukowanie zmiennych skojarzeń.

Oczywiste jest również, że jeśli powiązanie jest obecne - tzn. Istnieje wzorzec diagonalny lub można go osiągnąć przez zmianę kolejności - wówczas klastry muszą istnieć. Wynika to z faktu, że charakter danych kategorycznych („wszystko albo nic”) nie dopuszcza półtonów i warunków granicznych, dlatego obraz taki jak lewy dolny w pytaniu PO nie może pojawić się z kategorycznymi, nominalnymi danymi.

Przypuszczam, że ponieważ mamy coraz bardziej zmienne nominalne (zamiast tylko dwóch), które są bivariately chi-kwadrat niepowiązane, możemy zbliżyć się do możliwości mają klastry. Ale zero wielowymiarowego chi-kwadrat, oczekuję, że nadal będzie niezgodny z klastrami. To jeszcze musi zostać wykazane (tym razem nie przeze mnie lub nie).

Na koniec uwaga na odpowiedź @ Bey (aka user75138), którą częściowo poparłem. Skomentowałem to za moją zgodą, że najpierw trzeba zdecydować o metodzie odległości i miary asocjacji, zanim będzie mógł zadać pytanie „czy asocjacja zmienna jest niezależna od klastrów przypadków?”. Wynika to z faktu, że nie istnieje uniwersalna miara asocjacji ani uniwersalna statystyczna definicja klastrów. Chciałbym dodać, że on także musi zdecydować o technice klastrowania. Różne metody klastrowania w różny sposób definiują, czym są „klastry”. Całe stwierdzenie może być prawdziwe.

To powiedziawszy, słabość takiego powiedzenia polega na tym, że jest ono zbyt szerokie. Należy konkretnie pokazać, czy i gdzie wybór metryki odległości / miary asocjacji / metody skupienia otwiera pole do pogodzenia nieskorelacji z klastrowaniem dla danych nominalnych. W szczególności pamięta, że ​​nie wszystkie współczynniki bliskości dla danych binarnych mają sens w przypadku danych nominalnych, ponieważ w przypadku danych nominalnych „w obu przypadkach brak tego atrybutu” nigdy nie może być podstawą ich podobieństwa.

Zaktualizuj , zgłaszając wyniki moich symulacji.

$.1$

$r$

Ustalenia zasadniczo potwierdzają rozumowanie przedstawione powyżej w odpowiedzi. Nigdy nie było bardzo wyraźnych skupisk (takich, które mogłyby wystąpić, gdyby silna asocjacja chi-kwadrat) była silna. Wyniki różnych kryteriów klastrowania często są ze sobą sprzeczne (czego nie można się spodziewać, gdy klastry są naprawdę jasne).

Czasami hierarchiczne tworzenie klastrów oferowałoby rozwiązanie k-klastrowe, które jest nieco dobre, co zaobserwowano za pomocą wykresu kryteriów klastrowania; jednak przetestowanie go pod kątem stabilności nie wykaże, że jest stabilny. Na przykład te 3-zmienne 4x4x3dane

   V1  V2  V3   Count
    1   1   1   21
            2   24
            3   1
        2   1   22
            2   26
            3   1
        3   1   1
            2   1
            3   1
        4   1   17
            2   20
            3   1
    2   1   1   10
            2   12
            3   1
        2   1   10
            2   12
            3   1
        3   1   1
            2   1
            3   1
        4   1   8
            2   9
            3   1
    3   1   1   24
            2   28
            3   1
        2   1   25
            2   30
            3   1
        3   1   1
            2   1
            3   1
        4   1   19
            2   23
            3   1
    4   1   1   24
            2   28
            3   1
        2   1   26
            2   30
            3   1
        3   1   1
            2   1
            3   1
        4   1   19
            2   23
            3   1

po zgrupowaniu za pomocą pełnej hierarchicznej metody łączenia podobieństwo kości wydaje się być podzielone - całkiem rozsądnie - na 9 klastrów - w tym przypadku w zgodzie między trzema wewnętrznymi sędziami ważności:

Jednak rozwiązanie nie jest stabilne, co widać na podstawie niepełnej rzadkości macierzy pomieszania oryginalnego rozwiązania w stosunku do permutowanego (zamienionego ze względu na wielkość liter) rozwiązania:

Gdyby rozwiązanie było stabilne (co byłoby prawdopodobne, gdybyśmy mieli ciągłe dane), wybralibyśmy rozwiązanie 9-klastrowe jako wystarczająco przekonujące.

Grupowanie oparte na odległości prawdopodobieństwa dziennika (w przeciwieństwie do podobieństwa kości) może dać stabilne i „niezłe” (wewnętrznie całkiem poprawne) rozwiązania. Jest tak, ponieważ odległość, przynajmniej tak jak w klastrze TwoStep SPSS, zachęca i wspiera klastry o dużej gęstości zaludnienia i zaniedbuje te o niskiej gęstości zaludnienia. Nie wymaga, aby klastry o bardzo niskiej częstotliwości wewnątrz były gęste w środku (wydaje się, że jest to „polityka” analizy klastrów TwoStep, która została zaprojektowana specjalnie dla dużych zbiorów danych i daje niewiele klastrów; więc małe klastry są postrzegane jak wartości odstające) . Na przykład te 2-zmienne dane

zostanie połączony przez TwoStep w 5 klastrów, jak pokazano, stabilnie, a rozwiązanie 5-klastrowe wcale nie jest złe, jak sądzą niektóre kryteria klastrowania. Ponieważ cztery zaludnione klastry są bardzo gęste w środku (właściwie wszystkie przypadki są identyczne), a tylko jedna piąta gromada, która obejmuje kilka przypadków, jest wyjątkowo entropijna. Widoczne jest tak naprawdę rozwiązanie 12-klastrowe, a nie 5-klastrowe, ale 12 to całkowita liczba komórek w tabeli częstotliwości, co jako „rozwiązanie klastrowe” jest trywialne i nieciekawe.

Jak zapewne wiesz, korelacja jest miarą liniowej zależności między dwiema zmiennymi, a nie odległości między punktami. To wyjaśnia cztery najlepsze liczby.

Oczywiście można również tworzyć podobne wykresy dla dyskretnych danych o wartości rzeczywistej.

$X \in \{A,B,C,D\}$$\mathbb{R}$$X \subset \mathbb{R}$$X$

Musisz zdefiniować metrykę dla przestrzeni kategorycznej, zanim naprawdę będziesz mógł mówić o grupowaniu w sensie geometrycznym.

Weźmy pod uwagę odległość Hamminga - odległość Hamminga między dwoma strunami o równej długości jest liczbą pozycji, w których odpowiednie symbole są różne. Z tej definicji wydaje się oczywiste, że możemy wytwarzać dane, dla których mamy klastry oparte na odległości Hamminga, ale bez korelacji między zmiennymi.

Poniższy przykład ilustruje użycie Mathematica.

Utwórz niektóre dane kategoryczne (długie 3 symbole z jednolitym losowym próbkowaniem 4 znaków):

chs = CharacterRange["a", "d"];
words = StringJoin @@@ Union[Table[RandomChoice[chs, 3], 40]];
Length[words]
words

(* 29 *)

(* {"aac", "aad", "abb", "aca", "acb", "acd", "adb", "adc", "baa", "bab", "bac", "bad", "bcc", "bcd", "caa", "cab", "cac", "cad", "cbb", "ccb", "cda", "cdb", "dab", "dba", "dbb", "dbd", "dca", "dcc", "dcd"} *)

Użyj wykresów mozaiki do relacji między zmiennymi (prawdopodobieństwa warunkowe dla par wartości z różnych kolumn):

Import["https://raw.githubusercontent.com/antononcube/MathematicaForPrediction/master/MosaicPlot.m"]
wordSeqs = Characters /@ words;
opts = {ColorRules -> {2 -> ColorData[7, "ColorList"]}, ImageSize -> 400};
Grid[{{MosaicPlot[wordSeqs[[All, {1, 2}]], 
    "ColumnNames" -> {"column 1", "column 2"}, opts],
   MosaicPlot[wordSeqs[[All, {2, 3}]], 
    "ColumnNames" -> {"column 2", "column 3"}, opts],
   MosaicPlot[wordSeqs[[All, {1, 3}]], 
    "ColumnNames" -> {"column 1", "column 3"}, opts]}}, Dividers -> All]

Widzimy, że nie ma korelacji.

Znajdź klastry:

cls = FindClusters[words, 3, DistanceFunction -> HammingDistance]

(* {{"aac", "aad", "adc", "bac"}, {"abb", "acb", "adb", "baa", "bab", "bad", 
  "caa", "cab", "cac", "cad", "cbb", "ccb", "cda", "cdb", "dab", 
  "dbb"}, {"aca", "acd", "bcc", "bcd", "dba", "dbd", "dca", "dcc", "dcd"}} *)

Jeśli zastąpimy każdą postać liczbą całkowitą, z tego wykresu zobaczymy, jak powstają klastry z odległością Hamminga:

esrules = Thread[chs -> Range[Length[chs]]]; gr1 = 
 ListPointPlot3D[Characters[cls] /. esrules, 
  PlotStyle -> {PointSize[0.02]}, PlotLegends -> Automatic, 
  FaceGrids -> {Bottom, Left, Back}];
gr2 = Graphics3D[
   Map[Text[#, Characters[#] /. esrules, {1, 1}] &, Flatten[cls]]];
Show[gr1, gr2]

Dalsze grupowanie

Zróbmy wykres, łącząc słowa, dla których odległość Hamminga wynosi 1:

mat = Clip[Outer[HammingDistance, words, words], {0, 1}, {0, 0}];
nngr = AdjacencyGraph[mat, 
  VertexLabels -> Thread[Range[Length[words]] -> words]]

Teraz znajdźmy klastry społeczności:

CommunityGraphPlot[nngr]

Porównaj klastry wykresów z tymi, które znaleziono FindClusters(dla których zmuszono znaleźć 3). Widzimy, że „bac” jest bardzo centralny, a „aad” może należeć do zielonej gromady, która odpowiada gromadzie 1 na wykresie 3D.

Dane wykresu

Oto lista krawędzi nngr:

{1 <-> 2, 1 <-> 8, 1 <-> 11, 1 <-> 17, 2 <-> 6, 2 <-> 12, 2 <-> 18, 
 3 <-> 5, 3 <-> 7, 3 <-> 19, 3 <-> 25, 4 <-> 5, 4 <-> 6, 4 <-> 27, 
 5 <-> 6, 5 <-> 7, 5 <-> 20, 6 <-> 14, 6 <-> 29, 7 <-> 8, 7 <-> 22, 
 9 <-> 10, 9 <-> 11, 9 <-> 12, 9 <-> 15, 10 <-> 11, 10 <-> 12, 
 10 <-> 16, 10 <-> 23, 11 <-> 12, 11 <-> 13, 11 <-> 17, 12 <-> 14, 
 12 <-> 18, 13 <-> 14, 13 <-> 28, 14 <-> 29, 15 <-> 16, 15 <-> 17, 
 15 <-> 18, 15 <-> 21, 16 <-> 17, 16 <-> 18, 16 <-> 19, 16 <-> 20, 
 16 <-> 22, 16 <-> 23, 17 <-> 18, 19 <-> 20, 19 <-> 22, 19 <-> 25, 
 20 <-> 22, 21 <-> 22, 23 <-> 25, 24 <-> 25, 24 <-> 26, 24 <-> 27, 
 25 <-> 26, 26 <-> 29, 27 <-> 28, 27 <-> 29, 28 <-> 29}

Punkt @ttnphnsa na temat powiązania parami i wielowymiarowymi jest dobrze przyjęty. Powiązane z tym jest stare zdanie na temat znaczenia wykazania skojarzenia z prostymi miernikami przed przeskoczeniem do struktury wielowymiarowej. Innymi słowy, jeśli proste pary miar asocjacji nie wykazują związku, staje się coraz bardziej mało prawdopodobne, że relacje wielowymiarowe również coś pokażą. Mówię „coraz bardziej mało prawdopodobne” z powodu niechęci do używania słowa „niemożliwe”. Ponadto jestem agnostyczny co do zastosowanej metryki, czy będzie to monotoniczna korelacja Spearmana dla danych porządkowych, Somer D , Tau Kendalla, korelacja polichoryczna, MIC Reshefa, korelacja odległości Szelkeya, cokolwiek. Wybór metryki nie jest ważny w tej dyskusji.

Oryginalna praca nad znalezieniem ukrytej struktury w informacjach kategorycznych sięga wczesnych lat 50. i Paula Lazersfelda, socjologa z Kolumbii. Zasadniczo wynalazł klasę ukrytych modeli zmiennych, które od tego czasu były szeroko rozwijane i modyfikowane. Po pierwsze, z pracami Jamesa Colemana, ekonomisty politycznego z Wielkiej Brytanii z lat 60., na temat ukrytych skłonności do głosowania w wyborach, a następnie wkładem zmarłego Clifforda Clogga, również socjologa, którego oprogramowanie MELISSA było pierwszym ogólnodostępnym ukrytym darmowym oprogramowaniem.

W latach 80. modele klasy utajonej zostały rozszerzone z informacji czysto kategorycznych na modele o skończonej mieszance dzięki opracowaniu takich narzędzi, jak Latent Gold z innowacji statystycznych. Ponadto Bill Dillon, naukowiec zajmujący się marketingiem, opracował program Gaussa do dopasowania ukrytych dyskryminacyjnych modeli skończonej mieszanki. Literatura na temat tego podejścia do dopasowywania mieszanin informacji kategorycznych i ciągłych jest w rzeczywistości dość obszerna. Po prostu nie jest tak dobrze znany poza dziedzinami, w których był najczęściej stosowany, np. W naukach marketingowych, w których modele te są wykorzystywane do segmentacji i grupowania konsumentów.

Jednak te modele mieszanki skończonej do ukrytego grupowania i analizy tabeli awaryjnej są uważane za starą szkołę w dzisiejszym świecie ogromnych danych. Najnowocześniejszym sposobem znajdowania powiązań między ogromnym zestawem tabel awaryjnych są dekompozycje dostępne przy wdrażaniu modeli tensorów, takich jak te opracowane przez Davida Dunsona i innych Bayesian w Duke. Oto streszczenie jednego z ich artykułów oraz link:

Analiza tabeli awaryjnej rutynowo opiera się na logicznych modelach liniowych, a analiza struktury utajonej stanowi powszechną alternatywę. Modele struktury utajonej prowadzą do faktoryzacji tensora niskiej rangi funkcji masy prawdopodobieństwa dla danych zmiennych wielowymiarowych, podczas gdy logiczne modele liniowe osiągają zmniejszenie wymiarów poprzez rzadkość. Niewiele wiadomo o związku między tymi pojęciami zmniejszenia wymiarów w tych dwóch paradygmatach. Wyciągamy kilka wyników dotyczących powiązania logarytmiczno-liniowego modelu z nieujemną rangą powiązanego tensora prawdopodobieństwa. Zmotywowani tymi odkryciami, proponujemy nową zwiniętą klasę dekompozycji tensorów, które łączą istniejące dekompozycje PARAFAC i Tucker, zapewniając bardziej elastyczne ramy dla oszczędnego charakteryzowania wielowymiarowych danych kategorycznych.

https://arxiv.org/pdf/1404.0396.pdf