How do i cluster binarized categorial data, without knowing the number of clusters?

Question

I have a dataset of categorical data, and I need to cluster it without knowing k. I know algos for clustering data without knowing the number of centroids, like G-mean, but none works for categorial data. I think that DBSCAN is also bad because of density. My dataset is typically a marketing dataset, each row is a customer, and each column corresponds to an attribute, like eyes color. So, I need to binarize this dataset before any algorithm. Any ideas??

Answer 1

For categorical data, robust hierarchical clustering algorithm ( ROCK) will work better that employs links and not distances when merging clusters, which improves quality of clusters of categorical data. Boolean and categorical are two types of attributes that are most suited in this algorithm.

ROCK is a static model that combines nearest neighbor, relocation, and hierarchical agglomerative methods. In this algorithm, cluster similarity is based on the number of points from different clusters that have neighbors in common.

You can use CBA Package in R to perform the ROCK clustering.

Algorithm Steps:

Data----->Draw Random Sample----->Cluster with Links----->Label Data in DIsk

1. A random sample is drawn from the database
2. A hierarchical clustering algorithm employing links is applied to the samples
3. This means: Iteratively merge clusters Ci, Cj that maximise the goodness function merge(point1,point2) = total number of crosslinks /expected number of crosslinks Stop merging once there are no more links between clusters or the required number of clusters has been reached.
4. Clusters involving only the sampled points are used to assign the remaining data points on disk to the appropriate clusters

Hope it helps!!

For more details with examples, refer the following links: https://www.cis.upenn.edu/~sudipto/mypapers/categorical.pdf https://en.wikibooks.org/wiki/Data_Mining_Algorithms_In_R/Clustering/RockCluster