# How do I identify clusters that match on categorical data?

I am seeking some directions for a proper path to research the solve for this problem:

My company made all our employees take a "StrengthFinders" test, which results in every employee being assigned their top five (ordered) "strengths" from a possible list of 34 strengths. We have 500 employees. I am supposed to identify all the employees that match each other for the same 5 strengths (order not important), and also for employees that match each other for 4 out of 5 strengths (again, order doesn't matter). I could potentially have multiple groups matching on different sets of strengths, e.g.: Group 1: Billy, Sally, Michael have strengths A, H, I, K, Z Group 2: Bobby and Suzy have strengths A, B, L, S, W

For the case where strengths match for 4 out of 5, I might have the same people from Group 1 above, plus Joe, whose strengths are A, H, M, K, Z; and Seth, whose strengths are A, H, G, K, Z. I would expect more groupings for the case of 4 out of 5 than the 5 out of 5 case.

The strengths are categorical in nature, so what I've read so far has largely revolved around clustering of continuous numerical variables.

I am looking for an algorithmic way to identify clusters and the members of those clusters for this situation. I think I could do this brute force by repeatedly sorting data in Excel, but I'm confident that a better way must exist, and I ask you to point me in that direction. Thank you.

You have just 500 data points...

Excel of course is the worst possible tool though.

Anyway, build a dictionary. Put everybody in there 6 times: 1 with all five strengths, and 5 times with one strength omitted. Then you can easily identify the largest groups, and you can also perform various completion operations easily: if you have identified a group with strengths A B C D E, you can add all that have ABCD etc. using the dictionary.

• @wackojacko1997 I think this is the solution. Noting that if each key is a string, strengths need to be sorted alphabetically to place ABCD and CABD in the same group. Mar 30, 2019 at 22:25
• While I need to think about the coding with the Dictionary a little bit, this answer does makes sense to me. When I look at @QuantifiedMe's answer (which I perceive as essentially the same thing, but using prime numbers), I think I can use that even without coding (directly in Excel). I'm inclined to mark this the answer, though, as the more general approach. Apr 3, 2019 at 20:20
• Yes, he is suggesting the same thing, using a prime factor coding instead of a string coding. Apr 3, 2019 at 21:16
• Okay, thank you. I am accepting this answer as the general case then. Apr 4, 2019 at 1:18

Assign each of the 34 traits a unique prime number.

Compute the product of the 5 prime numbers of each person.

Compare every person's value to find a match.

To find 4 matching traits out of 5, make the product from 4 of the 5 traits. You'll find 5 unique combinations. 1*2*3*4 , 1*2*3*5, 1*2*4*5, 2*3*4*5, and 1*3*4*5. Compare the values again to find the 4th degree matches.

• I like this approach for the simplicity and the ease of employing it. Apr 3, 2019 at 20:21

You can try k-modes or ROCK which are specifically made to work with categorical values. I don't have experience with them myself but you can look at:

Implementations:

If I were you, I would approach this as an Association Mining problem. You most likely will have to pre-process your data for this type of analysis, but it shouldn't be too difficult.

Here is an example in R