Clustering by discrete, unrelated properties?

Question

I have a large number of objects that have unrelated properties such as

• color=yellow
• material=stone
• is_important=true
• etc.

The properties are basically random, whatever the users thought would be nice to have. There's no practical way to coerce these properties into something that has a semblance of euclidean distance.

I think that there's conceptually no point in thinking about clustering objects by such properties if some kind of a distance metric isn't present (is this correct?) but I'm hoping something exists that could produce outputs like

"90% of objects with color=yellow also have material=plastic and is_important=false"

Is there something out there that does such analysis, other than brute forcing through the data set?

Answer 1

If the features are really independent with each other with no underlying structure, then a clustering algorithm will just segment our sample space arbitrarily. Unsurprisingly, that won't be very informative, as there will be no underlying structure to be discovered. The clustering algorithm might even appear "stable" for a given choice of hyperparameters, despite the absence of a meaningful grouping.

That said, if we are dealing with binary variables (0/1s) then we could use something like logistic PCA where one minimises the Bernoulli deviance; the relevant reference for us was Dimensionality reduction for binary data through the projection of natural parameters by Landgraf & Lee (2020). Following that, we get the PC score and then cluster the scores. Logistic PCA is implemented in the R package logisticPCA if you want to try it yourself. Prior to that, Tipping's (1998) Probabilistic Visualisation of High-Dimensional Binary Data was an early attempt much closer to the now-classical view of a latent Gaussian model for PCA.

Finally, do note that aside the Bernoulli deviance advocate above, we can define multiple other meaningful similarity measurements between binary (or mixed-typed) entries. Some of the obvious one are the Cosine similarity and Jaccard similarity (or Gower's distance for mixed type data). All of which allow us to create a distance/dissimilarity matrix $D$ directly and use a clustering algorithm directly on $D$.

(Thank you to Nick Cox and Christian Henning for calling out shortcomings to my initial answer.)

Answer 2

A central issue to understand here is that generally there is no unique way to define a clustering from data. Different clustering methods are based on different implicit clustering concepts and will give you different things, for Euclidean data or other. None of these is per se right or wrong, and the data themselves are not going to tell us what the best clustering is without a user's decision regarding what kind of clusters are required. The starting point for this should be, from a pragmatic point of view, the question what the clustering is needed for and will be used for. As this is not specified in the question, it is hard to say whether there is "conceptually a point in clustering these data", as you as the user are the one who needs to specify the "point". For example, in a marketing context it can be useful to have different groups of similar consumers regarding their preferences, even if in fact the data may not strongly suggest such groups, i.e., there are no clear "gaps" separating them, and various different clusterings could have very similar quality.

One can construct such clusters for example in a distance-based manner, i.e., computing the simple matching distance (basically the percentage of agreements between any two observations) and then feed it into any distance-based clustering algorithm such as average linkage. A different approach is latent class mixtures, where clusters are defined by local independence., i.e., a distribution mixture is fitted, typically by an EM-algorithm, where the different features are assumed independent within each cluster (if your features are indeed independent in the whole data set, the BIC should tell you that everything belongs to the same cluster if you follow this approach). Whether these are any good for you will depend on your clustering aim.

I should say that in the case of distance-based clustering, both the choice of a distance measure and the choice of a clustering method given the distance will have an impact, and both choices are best made with reference to the clustering aim.

Looking at your later description what kind of statement you want, you may be more interested in MONA (coding all the possible outcomes as dummy variables), or association rule learning (which isn't actually clustering).