# With categorical data, can there be clusters without the variables being related?

When trying to explain cluster analyses, it is common for people to misunderstand the process as being related to whether the variables are correlated. One way to get people past that confusion is a plot like this:

This clearly displays the difference between the question of whether there are clusters and the question of whether the variables are related. However, this only illustrates the distinction for continuous data. I'm having trouble thinking of an analog with categorical data:

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


We can see that there are two clear clusters: people with both property A and B, and those with neither. However, if we look at the variables (e.g., with a chi-squared test), they are clearly related:

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


I find I am at a loss for how to construct an example with categorical data that is analogous to the one with continuous data above. Is it even possible to have clusters in purely categorical data without the variables being related as well? What if the variables have more than two levels, or as you have larger numbers of variables? If the clustering of observations does necessarily entail relationships between the variables and vice versa, does that imply that clustering is not really worth doing when you only have categorical data (i.e., should you just analyze the variables instead)?

Update: I left a lot out of the original question because I wanted to just focus on the idea that a simple example could be created that would be immediately intuitive even to someone who was largely unfamiliar with cluster analyses. However, I recognize that a lot of clustering is contingent on choices of distances and algorithms, etc. It may help if I specify more.

I recognize that Pearson's correlation is really only appropriate for continuous data. For the categorical data, we could think of a chi-squared test (for a two-way contingency table) or a log-linear model (for multi-way contingency tables) as a way to assess the independence of the categorical variables.

For an algorithm, we could imagine using k-medoids / PAM, which can be applied to both the continuous situation and the categorical data. (Note that, part of the intention behind the continuous example is that any reasonable clustering algorithm should be able to detect those clusters, and if not, a more extreme example should be possible to construct.)

Regarding the conception of distance. I assumed Euclidean for the continuous example, because it would be the most basic for a naive viewer. I suppose the distance that is analogous for categorical data (in that it would be the most immediately intuitive) would be simple matching. However, I am open to discussions of other distances if that leads to a solution or just an interesting discussion.

• I wonder if we have anything like clusters in categorical data at all. It's not as if the variance between clusters will be bigger than within clusters, or can talk about a density difference between clusters. So if the clostest match are frequent itemsets, then variables must be related for clusters to form. – Has QUIT--Anony-Mousse Jun 13 '16 at 6:05
• @Anony-Mousse, that's interesting. Why not develop that into an answer? BTW, I can image clusters actually existing (eg, in latent continuous variables that give rise to differing probabilities for various levels of nominal variables), but I suspect that isn't what you meant. – gung - Reinstate Monica Jun 13 '16 at 19:33
• You can transform a categorical distribution to a vector whose components are the normalized frequencies. Then the Euclidean metric can be applied. It's not the only option though:math.umn.edu/~garrett/m/fun/notes_2012-13/02_spaces_fcns.pdf and en.m.wikipedia.org/wiki/Normed_vector_space – user75138 Jun 14 '16 at 11:21
• @ttnphns, you seem to have added the [data-association] tag. I'm not sure what it's supposed to indicate & it has no excerpt / usage guidance. Do we really need this tag? Is seems like a good candidate for deletion. If we really do need it on CV & you know what it's supposed to be, could you at least add an excerpt for it? – gung - Reinstate Monica Jun 29 '19 at 12:11
• @gung, I too, don't quite understand what this tag might refer to. I added it because of the "association/correlation between attributes" topic of the question. You are free to delete the tag from the Q or altogether. On the other hand, it's time (I think) to re-think about our tags covering the whole correlation/association field. For example, should "correlation" be retained only for Pearson correlation? Should we create a new tag "variables-association" (in place of "data-association")? – ttnphns Jun 29 '19 at 12:43

Consider the clear-cluster case with uncorrelated scale variables - such as the top-right picture in the question. And categorize its data.

We subdivided the scale range of both variables X and Y into 3 bins which now onward we treat as categorical labels. Moreover, we'll declare them nominal, not ordinal, because the question asked is implicitly and primarily about qualitative data. The spots' size is the frequency in a frequency cross-table cell; all cases in the same cell are considered identical.

Intuitively and most generally, "clusters" are defined as clots of data points separated by sparse regions in the data "space". It was initially with scale data and it remain same impression in the cross-tabulation of the categorized data. X and Y now categorical, but they still look uncorrelated: chi-square association is very near to zero. And clusters are there.

But recall we're dealing with nominal categories which order in the table is arbitrary. We may reorder whole rows and/or columns as we like, without affecting the observed chi-square value. Do reordering...

...to meet that clusters just dissapeared. The four cells, a1, a3, c1 and c3, could be united in a single cluster. So no, we really don't have any clusters in the categorical data.

Cases of cells a1 and c3 (or likewise of a3 and c1) are complete-dissimilar: they don't share same attribures. To induce clusters in our data - a1 and c3 to form the clusters - we have to empty, to some great extent, confounding cells a3 and c1, by dropping these cases from the dataset.

Now clusters do exist. But at the same time we lost uncorrelatedness. The diagonal structure showing up in the table signals that chi-stare statistic got far from zero.

Pity. Let us attempt to preserve uncorrelatedness and more or less clear clusters at the same time. We may decide to sufficiently empty just cell a3, for example, and then to consider a1+c1 as a cluster which opposes cluster c3:

That operation didn't bring Chi-square any far from zero...

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


...but the situation with clusters is confused. Cluster a1+c1 contains cases that partly identical, partly half-dissimilar. That a cluster is relatively low-homogeneous is itself not a preclusion for a clear-cluster structure in a dataset. However, the problem with our, categorical data is that cluster a1+c1 is in no way better than cluster c1+c3, its symmetric analogue. That means that the cluster solution is unstable - it will depend on the case order in the dataset. An unstable solution, even it is relatively "clear-clustered", is a bad solution, unreliable.

The only way to overcome the problem and to make solution both clear and stable will be to untie cell c3 from cell c1 by moving its data below to cell b3 (or to b2).

So we have clear clusters a1+c1 vs b3. But look, here again the diagonal pattern shows up - and chi-square of the table bounds high above zero.

Conclusion. It is impossible to have two chi-square-unassociated nominal variables and good clusters of the data cases simultaneously. Clear & stable clusters imply inducing variable association.

It is also clear that if the association is present - i.e. diagonal pattern exists or achievable by reordering - then clusters must exist. This is because the nature of categorical data ("all or nothing") doesn't permit half tones and borderline conditions, therefore picture like bottom-left in the OP's question can't emerge with categorical, nominal data.

I surmise that as we get more and more nominal variables (instead of just two) which are bivariately chi-square unrelated, we come closer to the possibility to have clusters. But zero multivariate chi-square, I expect still will be incompatible with clusters. That yet has to be shown (not by me or not this time).

Finally, a remark on @Bey's (aka user75138) answer which I partly supported. I've commented it with my agreement on that one has first to decide on the distance metric and the association measure before he can put the question "is variable association independent from case clusters?". This is because no universal association measure exist, nor universal statistical definition of clusters. I would further add, he must also decide on the clustering technique. Various methods of clustering differently define what are "clusters" they are after. So, the whole statement might be true.

That said, the weakness of such a dictum is that it's too broad. One should attempt to show concretely, whether and where a choice on distance metric / association measure / cluster method opens room to reconcile uncorrelatedness with clusteredness, for nominal data. He would keep in mind, particular, that not all the many proximity coefficients for binary data make sense with nominal data, since for nominal data, "both cases lack this attribute" can never be the ground for their similarity.

Update, reporting my simulations findings.

Repearedly, 2- or 3-variable nominal data were randomly generated, with the number of categories in a variable varying from 3 to 5, and the total sample size varying from 300 to 600. Bivariate chi-square association was very low in all the generated datasets (Cramer's V almost never above $.1$). Also, for 3-variable data 3-way chi-square association (main effects multinomial model), Pearson and Log-likelihood, was low and never significant.

Two methods of cluster analysis were used to cluster cases in each of the generated datasets - Hierarchical clustering (complete method, Dice similarity measure), and TwoStep clustering (basing on log-likelihood distance). Then a range of cluster solutions (varying by the number of clusters in a solution) from each analysis was checked by some internal clustering criterions (silhouette statistic, point-biserial $r$, AIC & BIC) in search of a relatively "good" solution, indicating the presence of clear clusters. A liked solution was then tested for stability by means of permuting case order in the dataset and redoing the clustering on it.

Findings generally support reasoning displayed above within the answer. There was never very clear clusters (such as might occure if the chi-square association be strong). And the results of the different clustering criterions often contradicted each other (which isn't very likely to expect when clusters are really clear).

Sometimes hierarchical clustering would offer a k-cluster solution that is somewhat good, as observed via a clustering criterion plot; however, testing it for stability will fail to show it is stable. For example, this 3-variable 4x4x3 data

   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


when clustered by the complete linkage hiearchical method, Dice similarity, seem to be split - quite reasonably - into 9 clusters - in this case in agreement among the three internal validity judges:

But the solution is not stable, as seen from the noncomplete sparsity of the confusion matrix of the original solution against the permuted (case-reordered) solution:

If the solution had been stable (as it would likely be had we continuous data) we would have chosen the 9-cluster solution as sufficiently persuasive one.

Clustering based on log-likelihood distance (as opposed to Dice similarity) may give stable and "not bad" (internally quite valid) solutions. But that is because the distance, at least as it is in TwoStep cluster of SPSS, encourage and foster high-populated clusters and neglect low-populated ones. It does not demand clusters with very low frequency inside to be dense inside (that seem to be the "policy" of TwoStep cluster analysis, which was designed specially for big data and to give few clusters; so small clusters are seen as if outliers). For example, these 2-variable data

would be combined by TwoStep into 5 clusters as shown, stably, and the 5-cluster solution is not at all bad as judged by some clustering criterions. Because the four populated clusters are very dense inside (actually, all cases identical), and only one, fifth cluster, which includes few cases, is extremely entropy'ed. So apparent actually is 12-cluster solution, not 5-cluster, but 12 is the total number of cells in the frequency table, which, as a "cluster solution" is trivial and uninteresting.

• +1, this is what I suspected. The pairwise unassociated vs multivariate unassociated is an interesting point. Considering this issue more broadly, does this imply that there isn't really any point in trying to cluster purely nominal data? Ie, should we just always analyze the variables if we don't have any continuous data? – gung - Reinstate Monica Jun 17 '16 at 17:13
• @gung, don't you know the maxim that correlation between variables is the other side of the coin of cases' polarization ("diagolness")? This is true, as maxim, also for continuous data. But for continuous, polarization may not imply clusters. For categorical, it appears it implies. Due to discrete nature. So probably yes, if categorical variables correlate, there are clusters to find. But you have to do clustering in order to get the clusters the better way. That's my tentative opinion for your great question. – ttnphns Jun 17 '16 at 17:31
• I'm not familiar with that. Maybe I'll ask about it later. This is good information to chew on for now, I think. – gung - Reinstate Monica Jun 17 '16 at 17:33

As I'm sure you know, correlation is a measure of the linear relationship between two variables, not how close the points are to each other. This explains the top four figures.

Of course, you could also create similar graphs for discrete, real-valued data as well.

The problem with more abstract distributions, such as $X \in \{A,B,C,D\}$ is that, unlike variables taking values in $\mathbb{R}$, we cannot assume that the image of a categorical random variable forms a metric space. We get this automatically when $X \subset \mathbb{R}$, but not so when we have $X$ taking values on some arbitrary set.

You'd need to define a metric for the categorical space before you can really even talk about clustering in the geometric sense.

• I would support this answer and would reformulate it, if both @gung and Bey allow, in intuitive terms. Clustered data are defined by "small distances in cluster but long distances between clusters". On his pictures, the OP selected, implicitly, euclidean distance to illustrate this idea of clusteredness. He also selected the notion of Pearson correlation or something similar to it - to illustrate the idea of association between variables. These are two particular/arbitrary choices among many alternatives. – ttnphns Jun 13 '16 at 9:39
• (cont.) I might even imagine that there could be chosen such distance measure and such association measure where "case clusteredness" conception and "variable associations" conception are not orthogonal. And now, for categorical data. Before one can check & show whether the two conceptions can be independent or are related he must select a specific distance measure for categorical data points and a specific association measure for categorical variables. There's many alternatives to select from! And the answer will depend. – ttnphns Jun 13 '16 at 9:39
• @ttnphns (+1) I like how you framed the two main choices: distance and association metrics. Not sure what about my explanation was not intuitive though...you can't define clusters without a notion of distance. – user75138 Jun 13 '16 at 13:25
• @ttnphns, I think it's up to Bey. Why don't you turn some of your ideas into your own answer? I'd be interested in the idea that the "case clusteredness" & "variable associations" become non-orthogonal for the continuous data given some choices. Bey & ttnphns, I have added some clarifications to the question regarding distance & association measures, but you should feel free to go in a different direction, if you prefer. Let me know if it needs more. My preference is that the question remain as 'loose' as possible to give answerers the flexibility to go in a different direction. – gung - Reinstate Monica Jun 13 '16 at 19:40
• @Bey, there are, of course, many other possible distance and association measures for categorical data, so you're free to suggest something esoteric that makes it work. – gung - Reinstate Monica Jun 16 '16 at 13:31

Consider the Hamming distance -- the Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different. From this definition it seems obvious that we can produce data for which we have clusters based on the Hamming distance but no correlations between the variables.

An example follows using Mathematica.

Create some categorical data (3 symbols long sequences of uniform random sampling of 4 characters):

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


Use mosaic plots for the relationship between the variables (conditional probabilities for pairs of values from different columns):

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]


We can see that there is no correlation.

Find clusters:

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

"caa", "cab", "cac", "cad", "cbb", "ccb", "cda", "cdb", "dab",
"dbb"}, {"aca", "acd", "bcc", "bcd", "dba", "dbd", "dca", "dcc", "dcd"}} *)


If we replace every character with an integer we can see from this plot how the clusters are formed with Hamming distance:

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]


## Further clustering

Let us make a graph by connecting the words for which the Hamming distance is 1:

mat = Clip[Outer[HammingDistance, words, words], {0, 1}, {0, 0}];


Now let us find the community clusters:

CommunityGraphPlot[nngr]


Compare the graph clusters with the one found with FindClusters (which was forced to find 3). We can see "bac" is highly central, and "aad" can belong to the green cluster, which corresponds to cluster 1 in 3D plot.

### Graph data

Here is the edge list of 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}

• Welcome to the site! Just a pair of remarks: What language is the code? (which is not annotated, besides). How do you define relationship between the variables (correlation)? – ttnphns Jun 13 '16 at 9:48
• This is interesting. Unfortunately, I don't know Mathematica (& am less familiar with edit distance), so I need to play with this to be sure I understand it. I haven't had a chance yet, but I intend to soon. – gung - Reinstate Monica Jun 13 '16 at 19:42
• @gung I was thinking to do it in R but I thought that the crucial part is the 3D plot and rotating it in the right angle(s) to get an insight of the clusters formation. Good question, by the way! – Anton Antonov Jun 13 '16 at 19:48
• So you have "clusters" here. But are they meaningful? Are they better than other clusters? From the plot, I'd say cluster 1 is pretty random. So why is that a cluster? – Has QUIT--Anony-Mousse Jun 14 '16 at 0:19
• Random uniform (!) generated data clearly should not have clusters. The "community" plot is misleading because it does not preserve distances. The graph with 1-distance emphasizes these problems. It also shows another such example, cda. Sorry, I'm not "buying" these "clusters". The data is uniform, it is supposed to not have clusters. – Has QUIT--Anony-Mousse Jun 14 '16 at 22:14

@ttnphns' point about pairwise vs multivariate association is well taken. Related to that is the old saw about the importance of demonstrating association with simple metrics before leaping into a multivariate framework. In other words, if simple pairwise measures of association show no relationship then it becomes increasingly unlikely that multivariate relationships will show anything either. I say "increasingly unlikely" because of a reluctance to use the word "impossible." In addition, I am agnostic as to the metric employed whether it be a monotonic Spearman correlations for ordinal data, Somer's D, Kendall's Tau, polychoric correlation, the Reshef's MIC, Szelkey's distance correlation, whatever. The choice of metric is not important in this discussion.

The original work done on finding latent structure in categorical information dates back to the early 50s and Paul Lazersfeld, the Columbia sociologist. Essentially, he invented a class of latent variable models that has seen extensive development and modification since. First, with the 60s work of James Coleman, the U of C political economist, on latent voter election propensities, followed by the contributions of the late Clifford Clogg, also a sociologist, whose MELISSA software was the first publicly available latent class freeware.

In the 80s, latent class models were extended from purely categorical information to finite mixture models with development of tools such as Latent Gold from Statistical Innovations. In addition, Bill Dillon, a marketing scientist, developed a Gauss program for fitting latent discriminant finite mixture models. The literature on this approach to fitting mixtures of categorical and continuous information is actually quite extensive. It's just not as well known outside of the fields where it has been most widely applied, e.g., marketing science where these models are used for consumer segmentation and clustering.

However, these finite mixture model approaches to latent clustering and contingency table analysis are considered old school in today's world of massive data. The state-of-the-art in finding association among a huge set of contingency tables are the decompositions available from deploying tensor models such as those developed by David Dunson and other Bayesians at Duke. Here is the abstract from one of their papers as well as a link:

Contingency table analysis routinely relies on log linear models, with latent structure analysis providing a common alternative. Latent structure models lead to a low rank tensor factorization of the probability mass function for multivariate categorical data, while log linear models achieve dimensionality reduction through sparsity. Little is known about the relationship between these notions of dimensionality reduction in the two paradigms. We derive several results relating the support of a log-linear model to the nonnegative rank of the associated probability tensor. Motivated by these findings, we propose a new collapsed Tucker class of tensor decompositions, which bridge existing PARAFAC and Tucker decompositions, providing a more flexible framework for parsimoniously characterizing multivariate categorical data. Taking a Bayesian approach to inference, we illustrate advantages of the new decompositions in simulations and an application to functional disability data.

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

• This is interesting information. I'm not as clear on how it connects to the question. – gung - Reinstate Monica Jun 17 '16 at 19:13
• gung Given the wide ranging discussion and the fundamental questions raised as to whether clusters of categorical data "even exist," your lack of clarity as to the relevance of my contribution is puzzling. In my view, the information provided illuminates areas of methodology and knowledge discovery previously ignored. May I also point out my initial observation -- explicitly addressed to the OPs question -- regarding the leap from pairwise to multivariate association being highly unlikely in the absence of association at the simpler level. – Mike Hunter Jun 17 '16 at 20:08
• I didn't mean any offense, @DJohnson. I am (somewhat) familiar w/ latent models for clustering categorical data (ie, latent class analysis). I alluded to it in my comment above. I was not as familiar w/ the history, researchers, & software. That is interesting. I don't quite see how it answers the question of whether there can be detectable clusters in nominal data where the variables don't show any association. If that's what you're getting at, an example would be helpful. Can you provide one? – gung - Reinstate Monica Jun 17 '16 at 20:23
• @gung Of course not and none taken. – Mike Hunter Jun 17 '16 at 20:25