Aggregate categorical feature by the target
Interesting problem... 

If I understand correctly you'd like to obtain clusters of states which have similar patterns/proportions of symptom+diagnosis, right? 

If yes, I would suggest you reorganize the data so that one instance represents a state, with its features being the frequency of each pair (symptom, diagnosis). Based on this representation you could cluster states which have similar prevalence for a pair.

The disadvantage of this idea is that it considers pairs (symptom, diagnosis) as distinct even if only one of the two is different. Of course the same process could be done by considering only symptoms or only diagnosis. There are probably better approaches but this simple one might already provide some insight.