# K-Modes Clustering with Partially-Overlapping, Variable-Length Data?

I'm working on a project that's attempting to cluster books using machine learning. I'm using the K-Prototypes algorithm for clustering data that has both numerical and class-based data. Under the hood it uses the K-Modes algorithm for class-based book fields (such as genre), and K-Means for numerical data (such as year published).

I'm running into an issue with the genre data on a book. A book can have a variable length of assigned genres, and those genres are not all overlapping. For example:

Book A genres: ["Sci-Fi", "Fantasy", "Futuristic"]

Book B genres: ["Sci-Fi", "Horror"]

Book C genres: ["Historical", "Fantasy", "Romance", "Love", "Fiction"]

Most of the literature online discusses class-based data for a single potential class, that's shared across multiple instances. For example: car color could be one of the following: ["Red", "Green", "Blue"] and every car item is assigned one of those three values for 'color'. What's the proper way of using K-Prototypes (and K-Modes really) with dynamically fetched, variable length, non-overlapping classes like the genre example above?

Thanks for the help!

I don't know how if there's a "proper" way to do this, but defining a similarity measure between two bags of "words" is a well-trodden path in information retrieval.

Let $$B$$ be the set of all books, and $$G$$ be the set of all genres. For some $$b \in B$$ and some $$g \in G$$, denote the term count $$f_{g,b}$$ to be:

$$f_{g,b} = \begin{cases}1,\,\hbox{if book }b\hbox{ has genre }g\\0,\,\hbox{otherwise}\end{cases}$$

(Note that you can easily generalise this to "books" where the number of times a "genre" appears is important. This is how it's used in information retrieval, where a document that uses a word like "football" a lot is probably more relevant to the topic of football than one that uses the word only once.)

Then one simple measure of similarity between two books $$b_1$$ and $$b_2$$ could just be the inner product of these two vectors. This is called the cosine measure, because the dot product of two vectors in Euclidean space is proportional to the cosine between the two vectors:

$$\mathrm{cosine}_{\mathrm{simple}}(b_1,b_2) = \sum_{g \in G} f_{g,b_1} f_{g,b_2}$$

This measure, however, would artificially weight books which have a lot of genres listed higher. More common is to use the relative frequency of a genre within a book, called the term frequency:

$$\mathrm{tf}(g,b) = \frac{f_{g,b}}{\sum_{g' \in G} f_{g',b}}$$

And then:

$$\mathrm{cosine}_{\mathrm{weighted}}(b_1,b_2) = \sum_{g \in G} \mathrm{tf}(g,b_1) \cdot \mathrm{tf}(g,b_2)$$

Next step up in complexity is tf-idf, short for "term frequency, inverse document frequency". The theory behind this one is that some genres (e.g. "fiction") probably shouldn't weigh as highly as others (e.g. "historical").

To weight each genre, we use a little information theory. The probability that a randomly picked book will have the genre $$g$$ is:

$$P(g) = \frac{\left| \left\{ b \in B : f_{g,b} > 0 \right\}\right|}{\left|B\right|}$$

So the information content of the message "a randomly-chosen book has genre $$g$$" is $$-\log P(g)$$. We call this the inverse document frequency:

$$\mathrm{idf}(g) = -\log P(g) = \log \frac{\left|B\right|}{\left| \left\{ b \in B : f_{g,b} > 0 \right\}\right|}$$

Then the similarity measure is simply these two functions multiplied together:

$$\mathrm{ifidf}(g,b) = \mathrm{tf}(g,b) \cdot \mathrm{idf}(g)$$

And then the similarity of two books is simply the weighted sum over all genres:

$$\mathrm{similarity}(b_1,b_2) = \sum_{g \in G} \mathrm{tfidf}(b_1,g) \cdot \mathrm{tfidf}(b_2,g)$$

These are just two possibilities. BM25 is a popular similarity measure used in information retrieval.

But there are other options. Once you are thinking of each book as a frequency histogram of genres, a whole world of similarity measures opens up. Some method based on the Kullback-Leibler divergence might work, for example.

All of these methods are principled, but perhaps there's more art than science here...