0
$\begingroup$

Let's say I have a list of n items - i1, i2, ..., in.

These items are similar to one another based on some similarity function, say similar_func(item_x,item_y) where item_x,item_y belong to list i1, i2, ... in. This function returns a number that ranges from 0 to 1, where 0 means not similar at all and 1 means exactly similar.

Now I would like a create a number of groups, each of which may contain items from the above list. Each group having items that are similar to each other items of the group by let's say 0.5.

I could run a double loop on the list, comparing each item to one another and creating a group whenever I find two items with similarity more than 0.5. Of course I would need to check if the item already exists in a group already created and with all the other items in that group.

This brute force method is possible and will give the right answer.

But I would like to do this more efficiently. Is there a efficient method for solving this problem?

Edit: There can be any number of groups and an item can be in multiple groups.

If similarity(x,y) = 0.6 and similarity(x,z) = 0.6, but similarity(y,z) = 0.4, then there will be two groups -> [x,y] and [x,z]

Also if x is similar to y AND x is similar to z, then it doesnt mean that y is similar to z. The similarity between two items solely depends on the the return value of similarity function when those items are passed as arguments to it.

$\endgroup$
  • $\begingroup$ What happens for example if similarity(x,y) = 0.6 and similarity(x,z) = 0.6 but similarity(y,z) = 0.4? Does x go in one group with either y or z and the other is alone or does x go in two different groups? Do all items need to be in some group? Also, is there some transitivity-like property to similarity? (If x is similar to y and y similar to z then x is somewhat similar to z) $\endgroup$ – Tassle Mar 4 at 11:31
  • $\begingroup$ @Tassle if similarity(x,y) = 0.6, similarity(x,z) = 0.6 but similarity(y,z) = 0.4 there will be two groups -> Group1 [x,y] and Group2 [x,z]. There is no transitivity like property. Similairty solely depends upon the return value of similarity function. Thanks for the comment, I will try to edit the question to reflect these points. $\endgroup$ – vijit Mar 4 at 11:45
2
$\begingroup$

Suppose you represent your items as vertices in a graph and two vertices are connected by an edge if they have a similarity greater than $0.5$. Then, a possible group corresponds to a clique in this graph (i.e all vertices in the group are connected). You probably only care about the "largest" groups (for example, if $\{x,y,z\}$ is a group then you don't care about the group $\{x,y\}$), which correspond to maximal cliques in the graph.

Thus, your problem amounts to listing all maximal cliques in this graph. Unfortunately, there can be exponentially many such maximal cliques so you won't be able to do this in polynomial time. The Wikipedia article I link to mentions a few sources and ways to do this either in asymptotically optimal time for the worst case or in time polynomial per maximal clique, which might be of interest if the graph happens to have relatively few maximal cliques.

| cite | improve this answer | |
$\endgroup$

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.