Fuzzy Clustering for Categorical Data

Fuzzy C-means is implemented in Python and you just need to google it e.g. this one, however you can implement it yourself as well.

My answer will be more about your task. You have categorical data which means any data point in your problem is on the corner of a high-dimensional simplex. A simple example is 3 points on three vertices of a triangle. How would you cluster them and even more, how would you fuzzy cluster them? (because they are always ON EACH OTHER which makes fuzzy clustering a bit meaningless)

I suggest this: Find a similarity score between your points. For instance, as a very initial and simple approach, capture the normalized number of attributes in which two points have the same value.

a = [1,0,0]
b = [1,0,1]
similarity = 2/3

You can think of more similarity measures (what about Chi-Squared test?). When you have these scores between sample pairs, you can construct the affinity matrix and apply spectral clustering on it.

But where is the "Fuzzy" term? (or soft-clustering characteristic)

Spectral clustering works as follows:

1. You get the affinity matrix
2. Capture the eigen vector corresponding to the second smallest eigen value
3. That eigen vector is a representation of your data. Cluster that instead of data itself! Here you can use soft-clustering methods for clustering eigenvector elements.
4. See these steps in Section.2 of this.