1
$\begingroup$

I'm trying to figure out how to group elements of a binary matrix based on a given Jaccard distance cutoff. For example, suppose that I have information on the types of food carried by various grocery stores, and I want to group the stores in such a way that each store in the group is at least 30% similar to at least one other store in the same group.

The input looks like this:

> groceries
       food1 food2 food3 food4 food5 food6 food7
store1     1     1     0     0     0     0     0
store2     1     0     1     1     0     0     0
store3     1     0     0     1     0     0     0
store4     1     1     0     0     0     0     0
store5     0     0     0     0     1     1     1
store6     0     0     0     0     1     0     1

And I'm able to calculate the Jaccard distances like so:

> d=dist((groceries), method="binary")
> d
          store1    store2    store3    store4    store5
store2 0.7500000                                        
store3 0.6666667 0.3333333                              
store4 0.0000000 0.7500000 0.6666667                    
store5 1.0000000 1.0000000 1.0000000 1.0000000          
store6 1.0000000 1.0000000 1.0000000 1.0000000 0.3333333

I can eyeball the distance object and see that some of the stores meet my 30% similarity cutoff (Jaccard distance <= 0.7):

store1 & store3
store1 & store4
store2 & store3
store3 & store4
store5 & store6

So I'd like there to be two groups: one made up of stores 1, 2, 3, and 4, and another made up of stores 5 and 6. Eyeballing the distance matrix obviously doesn't scale, though - is there a way to do this automatically?

[I'm particularly interested in being able to do it in R, so if there's an R function that can do it automatically, that would be most useful.]

$\endgroup$

2 Answers 2

1
$\begingroup$

This is the components you get with single linkage clustering at cutoff 0.7, which is the exact same thing as constructing a graph with edge weight cutoff 0.7 and computing the connected components of that graph.

$\endgroup$
2
$\begingroup$

Just do it.

Try hierarchical agglomerative clustering, it seems to be exactly what you have been asking. (And it's in every textbook, too!)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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