How can I cluster based on the complementary categories?
Note: K-means does not assume an interpretation/label of the clusterings - in fact it is an unsupervised algorithm. The interpretations are a result of human analysis after running K-means.

For example, in the case of cats and dogs one would most definitely chose k = 2 - which provides an easy interpretation. However, what would it mean if we set k = 1000. We no longer have a "clean" interpretation of the centroids. 

Note: how I keep saying "interpretation." The algorithm simply assigns a data point to a cluster and calls it a day. Humans then look at the results and try to understand them with an interpretation. 

Continuing with the example where k = 2. One could easily interpret "is cat" as "not dog" and "is dog" as "not cat." The idea here is that the data is unlabeled beforehand and humans try to fathom the results retrospectively by assigning the resulting clusters with an understandable label.

I hope this clarifies the issue.