Avec des données catégorielles, peut-il y avoir des clusters sans que les variables soient liées?

En essayant d'expliquer les analyses de grappes, il est courant que les gens comprennent mal le processus comme étant lié à la corrélation des variables. Une façon d'amener les gens à surmonter cette confusion est un complot comme celui-ci:

Cela montre clairement la différence entre la question de savoir s'il existe des grappes et la question de savoir si les variables sont liées. Cependant, cela illustre seulement la distinction pour les données continues. J'ai du mal à penser à un analogue avec des données catégoriques:

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

Nous pouvons voir qu'il existe deux clusters clairs: les personnes ayant à la fois les propriétés A et B, et celles qui n'ont aucune des deux. Cependant, si nous regardons les variables (par exemple, avec un test du chi carré), elles sont clairement liées:

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

Je trouve que je ne sais pas comment construire un exemple avec des données catégoriques qui est analogue à celui avec des données continues ci-dessus. Est-il même possible d'avoir des clusters dans des données purement catégoriques sans que les variables soient également liées? Que faire si les variables ont plus de deux niveaux ou si vous avez un plus grand nombre de variables? Si le regroupement des observations implique nécessairement des relations entre les variables et vice versa, cela signifie-t-il que le regroupement ne vaut pas vraiment la peine d'être fait lorsque vous ne disposez que de données catégoriques (c.-à-d., Devriez-vous simplement analyser les variables à la place)?

Mise à jour: J'ai laissé beaucoup de choses hors de la question d'origine parce que je voulais simplement me concentrer sur l'idée qu'un exemple simple pourrait être créé qui serait immédiatement intuitif même pour quelqu'un qui n'était pas familier avec les analyses de cluster. Cependant, je reconnais que beaucoup de regroupements dépendent du choix des distances et des algorithmes, etc. Cela peut aider si je précise davantage.

Je reconnais que la corrélation de Pearson n'est vraiment appropriée que pour des données continues. Pour les données catégorielles, nous pourrions penser à un test du chi carré (pour une table de contingence bidirectionnelle) ou à un modèle log-linéaire (pour les tables de contingence multidirectionnelles) comme un moyen d'évaluer l'indépendance des variables catégorielles.

Pour un algorithme, nous pourrions imaginer utiliser k-medoids / PAM, qui peuvent être appliqués à la fois à la situation continue et aux données catégorielles. (Notez qu'une partie de l'intention derrière l'exemple continu est que tout algorithme de clustering raisonnable devrait être capable de détecter ces clusters, et sinon, un exemple plus extrême devrait être possible de construire.)

Concernant la conception de la distance. J'ai supposé euclidien pour l'exemple continu, car ce serait le plus basique pour un spectateur naïf. Je suppose que la distance qui est analogue pour les données catégorielles (en ce qu'elle serait la plus immédiatement intuitive) serait une simple correspondance. Cependant, je suis ouvert à des discussions sur d'autres distances si cela conduit à une solution ou simplement à une discussion intéressante.

Considérons le cas de cluster clair avec des variables d'échelle non corrélées - comme l'image en haut à droite de la question. Et catégorisez ses données.

Nous avons subdivisé la plage d'échelle des deux variables X et Y en 3 cases que nous traitons désormais comme des étiquettes catégoriques. De plus, nous les déclarerons nominaux, non ordinaux, car la question posée concerne implicitement et principalement les données qualitatives. La taille des spots est la fréquence dans une cellule de fréquence croisée; tous les cas dans la même cellule sont considérés comme identiques.

Intuitivement et le plus généralement, les «clusters» sont définis comme des caillots de points de données séparés par des régions clairsemées dans «l'espace» de données. C'était initialement avec des données d'échelle et cela reste la même impression dans le tableau croisé des données catégorisées. X et Y sont désormais catégoriques, mais ils ne semblent toujours pas corrélés: l'association chi carré est très proche de zéro. Et les clusters sont là.

Mais rappelez-vous que nous avons affaire à des catégories nominales dont l'ordre dans le tableau est arbitraire. Nous pouvons réorganiser des lignes et / ou des colonnes entières à notre guise, sans affecter la valeur du chi carré observée. Réorganisez-vous ...

... pour répondre à ces clusters vient de disparaître. Les quatre cellules, a1, a3, c1 et c3, pourraient être réunies en un seul cluster. Donc non, nous n'avons vraiment aucun cluster dans les données catégorielles.

Les cas des cellules a1 et c3 (ou de même a3 et c1) sont complètement différents: ils ne partagent pas les mêmes attributions. Pour induire des clusters dans nos données - a1 et c3 pour former les clusters - nous devons vider, dans une large mesure, la confusion des cellules a3 et c1, en supprimant ces cas de l'ensemble de données.

Désormais, les clusters existent. Mais en même temps, nous avons perdu la corrélation. La structure diagonale apparaissant dans le tableau indique que la statistique du chi-stare est loin d'être nulle.

Pitié. Essayons de préserver la non-corrélation et les clusters plus ou moins clairs en même temps. Nous pouvons décider de vider suffisamment la cellule a3, par exemple, puis de considérer a1 + c1 comme un cluster qui s'oppose au cluster c3:

Cette opération n'a pas amené le Chi carré loin de zéro ...

[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.]

... mais la situation avec les clusters est confuse. Le cluster a1 + c1 contient des cas en partie identiques, en partie à moitié dissemblables. Le fait qu'un cluster soit relativement peu homogène n'est pas en soi un obstacle à une structure de cluster clair dans un ensemble de données. Cependant, le problème avec nos données catégoriques est que le cluster a1 + c1 n'est en rien meilleur que le cluster c1 + c3, son analogue symétrique. Cela signifie que la solution de cluster est instable - cela dépendra de l'ordre des cas dans l'ensemble de données. Une solution instable, même si elle est relativement "claire", est une mauvaise solution, peu fiable.

La seule façon de surmonter le problème et de rendre la solution à la fois claire et stable sera de délier la cellule c3 de la cellule c1 en déplaçant ses données ci-dessous vers la cellule b3 (ou vers b2).

Nous avons donc des clusters clairs a1 + c1 vs b3. Mais regardez, là encore, le motif diagonal apparaît - et le chi carré de la table se situe bien au-dessus de zéro.

Conclusion . Il est impossible d'avoir simultanément deux variables nominales non associées au chi carré et de bons groupes de cas de données. Des clusters clairs et stables impliquent une association de variables inductives.

Il est également clair que si l'association est présente - c'est-à-dire que le modèle diagonal existe ou est réalisable par réorganisation - alors les groupes doivent exister. En effet, la nature des données catégorielles ("tout ou rien") ne permet pas les demi-teintes et les conditions limites, donc une image comme en bas à gauche dans la question du PO ne peut pas émerger avec des données nominales catégoriques.

Je présume que, comme nous obtenons de plus en plus de variables nominales (au lieu de deux seulement) qui ne sont pas liées khi- deux bivariées , nous nous rapprochons de la possibilité d'avoir des grappes. Mais zéro chi carré multivarié, je pense qu'il sera toujours incompatible avec les clusters. Cela doit encore être montré (pas par moi ou pas cette fois).

Enfin, une remarque sur la réponse de @ Bey (aka user75138) que j'ai en partie soutenue. Je l'ai commenté avec mon accord sur le fait que l'on doit d'abord décider de la métrique de distance et de la mesure d'association avant de pouvoir poser la question "l'association variable est-elle indépendante des groupes de cas?". En effet, il n'existe pas de mesure d'association universelle, ni de définition statistique universelle des grappes. J'ajouterais en outre qu'il doit également décider de la technique de clustering. Différentes méthodes de clustering définissent différemment les «clusters» qu'ils recherchent. Donc, toute la déclaration pourrait être vraie.

Cela dit, la faiblesse d'un tel dicton est qu'il est trop large. On devrait essayer de montrer concrètement, si et où un choix sur la méthode métrique de distance / mesure d'association / cluster ouvre la place pour réconcilier la non corrélation avec le clustering, pour les données nominales. Il garderait à l'esprit, en particulier, que tous les nombreux coefficients de proximité pour les données binaires n'ont pas de sens avec les données nominales, car pour les données nominales, "les deux cas n'ont pas cet attribut" ne peuvent jamais être le motif de leur similitude.

Mise à jour , rapportant mes résultats de simulation.

$.1$

$r$

Les résultats soutiennent généralement le raisonnement affiché ci-dessus dans la réponse. Il n'y a jamais eu de grappes très claires (comme cela pourrait se produire si l'association chi carré était forte). Et les résultats des différents critères de clustering se sont souvent contredits (ce qui n'est pas très probable quand les clusters sont vraiment clairs).

Parfois, le clustering hiérarchique offrirait une solution de k-cluster qui est quelque peu bonne, comme observé via un tracé de critère de clustering; cependant, le tester pour la stabilité ne montrera pas qu'il est stable. Par exemple, ces 4x4x3données à 3 variables

   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

lorsqu'ils sont regroupés par la méthode hiearchical de liaison complète, la similitude des dés, semblent être divisés - assez raisonnablement - en 9 groupes - dans ce cas en accord entre les trois juges de validité interne:

Mais la solution n'est pas stable, comme le montre la rareté incomplète de la matrice de confusion de la solution d'origine contre la solution permutée (réorganisée):

Si la solution avait été stable (comme ce serait probablement le cas si nous avions des données continues), nous aurions choisi la solution à 9 grappes comme suffisamment convaincante.

Le regroupement basé sur la distance log-vraisemblance (par opposition à la similitude des dés) peut donner des solutions stables et "pas mauvaises" (en interne tout à fait valides). Mais c'est parce que la distance, du moins comme c'est le cas dans le cluster TwoStep de SPSS, encourage et favorise les clusters à forte densité de population et néglige ceux à faible densité de population. Il ne demande pas que les clusters à très basse fréquence à l'intérieur soient denses à l'intérieur (cela semble être la "politique" de l'analyse de clusters TwoStep, qui a été conçue spécialement pour les mégadonnées et pour donner peu de clusters; donc les petits clusters sont considérés comme des valeurs aberrantes) . Par exemple, ces données à 2 variables

serait combiné par TwoStep en 5 clusters comme indiqué, de manière stable, et la solution à 5 clusters n'est pas du tout mauvaise, à en juger par certains critères de clustering. Parce que les quatre grappes peuplées sont très denses à l'intérieur (en fait, tous les cas sont identiques), et qu'une seule, cinquième grappe, qui comprend peu de cas, est extrêmement entropiée. Il apparaît donc en fait une solution à 12 grappes, et non à 5 grappes, mais 12 est le nombre total de cellules dans le tableau des fréquences, ce qui, en tant que «solution de grappe», est trivial et sans intérêt.

Comme je suis sûr que vous le savez, la corrélation est une mesure de la relation linéaire entre deux variables, et non la distance entre les points. Cela explique les quatre premiers chiffres.

Bien sûr, vous pouvez également créer des graphiques similaires pour des données discrètes à valeur réelle.

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

Vous devez définir une métrique pour l'espace catégoriel avant de pouvoir vraiment parler de clustering au sens géométrique.

Considérez la distance de Hamming - la distance de Hamming entre deux chaînes de longueur égale est le nombre de positions auxquelles les symboles correspondants sont différents. À partir de cette définition, il semble évident que nous pouvons produire des données pour lesquelles nous avons des grappes basées sur la distance de Hamming mais aucune corrélation entre les variables.

Un exemple suit en utilisant Mathematica.

Créez des données catégoriques (3 longues séquences de symboles d'échantillonnage aléatoire uniforme de 4 caractères):

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"} *)

Utilisez des graphiques en mosaïque pour la relation entre les variables (probabilités conditionnelles pour les paires de valeurs de différentes colonnes):

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]

Nous pouvons voir qu'il n'y a pas de corrélation.

Rechercher des clusters:

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"}} *)

Si nous remplaçons chaque caractère par un entier, nous pouvons voir sur ce graphique comment les grappes sont formées avec la distance de Hamming:

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]

Regroupement supplémentaire

Faisons un graphe en reliant les mots pour lesquels la distance de Hamming est 1:

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

Voyons maintenant les clusters communautaires:

CommunityGraphPlot[nngr]

Comparez les grappes de graphiques avec celle trouvée avec FindClusters(qui a été forcée de trouver 3). Nous pouvons voir que "bac" est très central, et "aad" peut appartenir au cluster vert, ce qui correspond au cluster 1 dans le tracé 3D.

Données graphiques

Voici la liste de bord de 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}

Le point de @ttnphns sur l' association par paire vs l' association multivariée est bien pris. Liée à cela, l'ancienne a vu l'importance de démontrer l'association avec des mesures simples avant de sauter dans un cadre multivarié. En d'autres termes, si de simples mesures d'association par paires ne montrent aucune relation, il devient de plus en plus improbable que les relations multivariées montrent quoi que ce soit. Je dis «de plus en plus improbable» en raison d'une réticence à utiliser le mot «impossible». De plus, je suis agnostique quant à la métrique utilisée, que ce soit une corrélation de Spearman monotone pour les données ordinales, Somer's D , Kendall's Tau, la corrélation polychorique, le MIC de Reshef, la corrélation de distance de Szelkey, peu importe. Le choix de la métrique n'est pas important dans cette discussion.

Le travail original effectué pour trouver la structure latente dans les informations catégoriques remonte au début des années 50 et Paul Lazersfeld, le sociologue de Columbia. Essentiellement, il a inventé une classe de modèles de variables latentes qui a connu un développement et des modifications importants depuis. Tout d'abord, avec les travaux des années 60 de James Coleman, économiste politique de l'Université de C, sur les tendances des élections latentes, suivis des contributions de feu Clifford Clogg, également sociologue, dont le logiciel MELISSA a été le premier logiciel gratuit de classe latente accessible au public.

Dans les années 80, les modèles de classes latentes ont été étendus, passant d'informations purement catégoriques à des modèles de mélanges finis, avec le développement d'outils tels que Latent Gold de Statistical Innovations. De plus, Bill Dillon, un scientifique du marketing, a développé un programme Gauss pour l'ajustement de modèles de mélanges finis discriminants latents. La littérature sur cette approche pour ajuster des mélanges d'informations catégoriques et continues est en fait assez vaste. Ce n'est pas aussi bien connu en dehors des domaines où il a été le plus largement appliqué, par exemple, la science du marketing où ces modèles sont utilisés pour la segmentation et le regroupement des consommateurs.

Cependant, ces approches de modèle de mélange fini pour le clustering latent et l'analyse de table de contingence sont considérées comme de la vieille école dans le monde actuel des données massives. L'état de l'art dans la recherche d'association parmi un vaste ensemble de tables de contingence sont les décompositions disponibles à partir du déploiement de modèles de tenseurs tels que ceux développés par David Dunson et d'autres Bayésiens de Duke. Voici le résumé d'un de leurs articles ainsi qu'un lien:

L'analyse des tables de contingence repose régulièrement sur des modèles logarithmiques linéaires, l'analyse de la structure latente fournissant une alternative commune. Les modèles de structure latente conduisent à une factorisation tensorielle de bas rang de la fonction de masse de probabilité pour les données catégorielles multivariées, tandis que les modèles log linéaires permettent de réduire la dimensionnalité par la rareté. On sait peu de choses sur la relation entre ces notions de réduction de la dimensionnalité dans les deux paradigmes. Nous dérivons plusieurs résultats reliant le support d'un modèle log-linéaire au rang non négatif du tenseur de probabilité associé. Motivés par ces résultats, nous proposons une nouvelle classe Tucker effondrée de décompositions tensorielles, qui relie les décompositions PARAFAC et Tucker existantes, fournissant un cadre plus flexible pour caractériser avec parcimonie les données catégorielles multivariées.

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