Clustering for Categorical Data?
You can use distance metrics that are better suited to boolean values such as Jaccard, or Manhattan. Usually K-means uses mean as the metric to re-adjust the centroid of the current cluster, but I think you could change this to majority vote.
I think if you one-hot encoded the categorical features, you could use Jaccard for similarity and then majority vote for updating the centroid. Jaccard would be good if your data is quite sparse. Can you reform your data so that it is one-hot encoded? What does the distribution look like of the count per row?