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

Question

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.

Answer 1

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 remains 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-square 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.

Answer 2

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]

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

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}];
nngr = AdjacencyGraph[mat, 
  VertexLabels -> Thread[Range[Length[words]] -> words]]

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}

Answer 3

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.

Answer 4

@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