5
$\begingroup$

I use hierarchical clustering to cluster users which are similar to each other based on a Jaccard coefficient.

I have now coded a solution to extract similar users based on hierarchical clustering: To group users that are similar I compute the Jaccard coefficient between all the different users. I then check each user for similarity based on their Jaccard score. So if user1 and user2 have a similarity score of .2 then these users are very similar. I perform same for all users building a similarity table of users. So once grouping is finished I have a table structure which shows which users are close to each other based on the Jaccard coefficient.

Is this the correct approach to extract similar users based on hierarchical clustering?

$\endgroup$
3
  • $\begingroup$ As far as I can tell, your solution has nothing to do w/ hierarchical clustering. It is not clear that you have done a HC. If you have done a HC, you can look at which users end up in the same group at different levels of the returned hierarchy, this is the cophenetic distance. Finding which users have the lowest CD is not necessarily terribly insightful, however, it is just the pairs that are initially joined. $\endgroup$ Mar 21 '14 at 15:37
  • $\begingroup$ @gung is hierarchical clustering not grouping users into same group based on some similarity score ? In my case jaccard coefficient. I'm using <=.2 as the cut off point to check if users are similar. $\endgroup$
    – blue-sky
    Mar 21 '14 at 16:24
  • $\begingroup$ I'm not sure what you mean. Running a HC outputs a dendrogram. It does start from a distance matrix (or perhaps raw data, depending on the algorithm used, but those that require raw data tend to be less recommended). $\endgroup$ Mar 21 '14 at 16:35
5
$\begingroup$

If you have done a hierarchical clustering, it outputs a progressive series of more inclusive clusters. If you want to use the hierarchical clustering to determine which users are similar, you can simply look at the returned dendrogram to see which users are joined at the lowest levels. The cophenetic distance makes this idea concrete. It is the inter-group distance when the clusters containing two objects are merged into a single cluster. To see this, here is a simple demonstration in R:

set.seed(9)       # this makes the example exactly reproducible
x1 = runif(10)    # these data are simple uniform on 2 dimensions
x2 = runif(10)    #  (i.e., they actually have no cluster structure)

Here is what these data look like:

enter image description here

These are the Euclidean distances between all points:

round(dist(cbind(x1, x2)), digits=3)  
       1     2     3     4     5     6     7     8     9
2  0.226                                                
3  0.766 0.894                                          
4  0.184 0.350 0.582                                    
5  0.436 0.641 0.457 0.298                              
6  0.393 0.504 0.390 0.216 0.310                        
7  0.331 0.538 0.515 0.202 0.105 0.275                  
8  0.872 1.028 0.187 0.693 0.490 0.531 0.575            
9  0.508 0.733 0.699 0.457 0.262 0.553 0.281 0.687      
10 0.856 1.082 0.877 0.799 0.548 0.858 0.608 0.790 0.350

Here I run a hierarchical clustering:

HC = hclust(dist(cbind(x1, x2)), method="complete")      

Here is what the hierarchical clustering looks like:

enter image description here

To get the cophenetic distance between two points, you follow the lines from those points upwards until the two paths meet. The y-value of the horizontal line where the two paths come together is the cophenetic distance between those two points. This is the distance between the two largest clusters that contain each of the points, but not the other. This is simplest to see at the bottom when each cluster contains only 1 point. For example, the smallest cophenetic distance is between 5 & 7 ($d_c = .105$). Cases like that, where you are joining only two initial points, the cophenetic distance is necessarily equal to the original distance that you used to form the hierarchical clustering, so it isn't very interesting. Perhaps a more interesting case is the cophenetic distance between 3 & 5. Although the original distance between these two points is their Euclidean distance ($d_E = .457$), their cophenetic distance is the distance between the two clusters of which those points are members, just before the clusters are merged into a larger cluster in the hierarchy that encompasses them both. For points 3 & 5, those clusters are {3, 8} & {5, 7, 9, 10}, respectively. The cophenetic distance between those clusters is the complete linkage distance (the maximum distance between any two points in the lower-level clusters) because that's the method I used to form the clustering (i.e., $d_c(3,5) = .877 = d_E(3,10) = .877$).

These are the cophenetic distances between all points based on the output of the hierarchical clustering:

round(cophenetic(HC), digits=3)       
       1     2     3     4     5     6     7     8     9
2  0.350                                                
3  1.082 1.082                                          
4  0.184 0.350 1.082                                    
5  1.082 1.082 0.877 1.082                              
6  0.504 0.504 1.082 0.504 1.082                        
7  1.082 1.082 0.877 1.082 0.105 1.082                  
8  1.082 1.082 0.187 1.082 0.877 1.082 0.877            
9  1.082 1.082 0.877 1.082 0.281 1.082 0.281 0.877      
10 1.082 1.082 0.877 1.082 0.608 1.082 0.608 0.877 0.608

We can examine the relationship between the two types of distances by correlating them, and by making a scatterplot of the two distances for each unique pair of points:

cor(cophenetic(HC), dist(cbind(x1, x2)))  
[1] 0.5726733

enter image description here

We see that there is a fairly strong correlation ($r = .57$), but we can see other things as well. The points only exist in the upper / left triangular half of the plot because the cophenetic distance cannot be less than the original distance. Cophenetic distances only occur in discrete values and there are lots of ties. At the top of the scatterplot on the left, we also notice that there are some points whose Euclidean distances are quite small, but whose cophenetic distance is quite large (e.g., 4 & 7, with $d_E = .202$ & $d_c = 1.082$).

Note that the cophenetic distances you get will depend on the method used in the hierarchical clustering (here complete) and the underlying distance metric (here Euclidean). If you only want to know which users are most similar, this may or may not help you. First (crucially) determine which distance metric (Euclidean, Jaccard, etc.) best captures the sense of similarity you want to measure, and then that the clustering method is appropriate. Whether the clustering's cophenetic distance should be used depends on whether you think the user's cluster membership should take precedence in some ontological sense.

$\endgroup$
3
  • $\begingroup$ thanks very much. What I'm trying to achieve is generate recommendations based on how similar users are. So if user A and B have a similarity score of .2 then I suggest content that is not common to each of the users. I assumed this was related to hierarchical clustering. $\endgroup$
    – blue-sky
    Apr 16 '14 at 17:36
  • 1
    $\begingroup$ "we also notice that there are some points whose Euclidean distances are quite small, but whose cophenetic distance is quite large " I think this an important point as it seems to suggest should use the original distance function, in this case euclidean instead of cophenetic if the euclidean distance function offers a more accurate value for how similar two users are. $\endgroup$
    – blue-sky
    Apr 16 '14 at 17:45
  • 1
    $\begingroup$ That's a perfectly reasonable thing to do, but it means you aren't using the hierarchical clustering, you are just sidestepping it. $\endgroup$ Apr 16 '14 at 18:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.