5
$\begingroup$

Suppose I have a multitude of sets with (unordered) combinations of elements and I want to determine which elements tend to appear together.

For example

Given the following sets:

{a,e,g}
{a,e,h}
{a,e,i}
{b,f,j}
{b,f,k}
{b,f,l}
{d,c,m}
{d,c,n}
{d,c,o}

Element-pairs where both elements tend to occur in the same sets will have lower distance:

# Low-distance pairs:
{a,e}, {b,f}, {d,c}

# Medium-distance pairs
{a,g}, {b,j}, {d,m}, ...

# High-distance pairs:
{g,h}, {j,n}, {b,f}, ...

Currently

I'm implementing DBSCAN with a custom distance metric. I use the following distance metric between two elements:

d(a,b) = 1 - numsets(a, b) / (numsets(a,!b) + numsets(b,!a))

Where d(a,b) denote the distance between elements a and b. While numsets denotes how many sets fulfill some conditions:

  • numsets(a, b) - the number of sets that contain a and b
  • numsets(a,!b) - the number of sets that contain a but not b

This solution should achieve the goal however it's not a pretty solution and I couldn't find this problem on SE. In terms of solving the problem, is there a more sensible distance metric? In terms of implementation, is there a nicer way to do this?

| improve this question | |
$\endgroup$
1
$\begingroup$

That is a data mining problem, specifically affinity analysis.

One common method to solve it is the Apriori algorithm.

| improve this answer | |
$\endgroup$
0
$\begingroup$

Notice that your metric might suffer division by zero, or have negative values. It's pretty close to Jaccard distance, so maybe consider that. See also http://curtis.ml.cmu.edu/w/courses/index.php/Co-occurrence_metrics

You might also have success with a graph clustering approach, see for a start
http://www.ecography.org/blog/clustering-or-network-methods-comparing-different-methods-bioregionalisation

| improve this answer | |
$\endgroup$
-1
$\begingroup$

Levenshtein distance (and its cousing Jaro, Hemming etc...)

Levenshtein distance for measuring the difference between two sequences between two words is the minimum number of single-character edits (insertions, deletions or substitutions) required to change one word (your case one set of characters) into the other.

There are a couple implementations, for example here, its the "edit_distance" function.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Given that the sets of combinations are unordered, Levenstein is not a good metric. $\endgroup$ – DannyDannyDanny Dec 30 '19 at 10:37
  • $\begingroup$ True, but you can sort them (if thats possible given the task-in the example yes) $\endgroup$ – Noah Weber Dec 30 '19 at 10:39
  • 1
    $\begingroup$ I've tried to mull it over. Levenstein measures distance between sequences. I need the distance between elements. $\endgroup$ – DannyDannyDanny Dec 30 '19 at 11:01

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.