Comparing set relations

Question

Sorry for repeating this very basic concept here, I just want to give some context:

Relations are nonnegative ordered pairs. A relation consists of a domain and range.A domain is a set of all first coordinates(x) of a relation, while a range is the set of all second coordinates(y).

E.G. Relation is {(1,10),(2,20),(3,30),(4,40)}

We are working with classification problems whose output is a relation with discrete domain and range. The domain is conformed by the elements to be classified, and the range is made of labels. All what's matter about the label is its identity.

We want to compare two relations for the same domain. For example, relation $A_1=\{(1,2),(2,1),(3,1)\}$ and relation $A_2=\{(1,1),(2,2),(3,2)\}$, which are both defined over the domain $\{1,2,3\}$. We consider two relations equivalent if one can be obtained from the other by a bijection over the labels. In this example, $A_1$ and $A_2$ would be equivalent. We need a measure $\mu$ that can compare this kind of relations, scoring their similarity continuously from 0 to 1. "0" would mean that the two relations are unrelated, and "1" that they are equivalent.

My questions are:

• Which methods are usually employed for comparing two relations for similarity, if the two relations are given explicitly as sets?

• In which scenarios this need arise?

• We certainly have a definition of equivalence that fixes the upper bound of the measure, but we don't have any definition of "utterly dissimilar" to associate with the lower bound "0". Any ideas here?

My second questions is because, although we need to compare such relations, we don't know where to look for previous solutions to this problem.

Anyway, thoughts, opinions and partial answers are very much appreciated.

---

Bigger examples?

Imagine that the classified set is big enough. Given a relation/classification $A$ generated by an algorithm, if a second algorithm gets wrong only a few tuples of $A$ and also uses its own different-up-to-a-renaming label names, you would expect that a measure comparing $A$ with the output of the second algorithm would be very close to "1", or whatever the value for "equivalent" be in the concrete similarity measure.

What we are trying to solve:

Here is the only known-by-me previous attempt in this direction:

https://sites.google.com/site/andrealancichinetti/mutual

Hypothetical use cases

Here are a few scenarios where this need arises, although I don't know of any attempts to use it.

• Two phylogenetic trees over the same set of species. Each specie is member of several -- nested -- taxonomical groups (the labels). This scenario can be further complicated if horizontal gene transfer is accounted for: in that case, two sibling groups can overlap in a few species. There are several methods in the literature to generate phylogenetic trees from sequence data, and a measure of similarity between them would be useful to create a consensus tree.

• Comparing outputs of fuzzy classifiers, when they do soft labeling: http://www.scholarpedia.org/article/Fuzzy_classifiers .

Answer 1

If you're comparing two relations $R$ and $S$, try choosing a maximal relation $T$ such that $T$ is equivalent to a subrelation $T'$ of $R$ and to a subrelation $T''$ of $S$. Then let the "distance" $d(R,S)$ from $R$ to $S$ be the cardinality of $(R\setminus T')\cup (S\setminus T'')$ (i.e. $|R|+|S|-2|T|$); this defines a metric on the set of relations, and it is the number of ordered pairs you have to add and subtract from $R$ to get something equivalent to $S$.

Or if you would rather have a similarity "measure", try setting $\mu(R,S)=2|T|/(|R|+|S|)$, with $T$ as above. This equals 1 iff $|T|=|R|=|S|$, i.e. $R$ and $S$ are equivalent, and equals 0 iff $R$ and $S$ label nonoverlapping sets of objects.

---

Edit: For phylogenetic trees, you might want something slightly different, as the relations you get have the following property: for the sets of objects picked out by any two distinct labels, either they are disjoint, or one is strictly contained in the other. Perhaps you wouldn't mind allowing two relations to be equivalent up to reordering of labels and deleting duplicate labels?

In that case, each of the steps in the following path are distance 1 and the trees on either end are distance 2 apart, which agrees more with intuition than the earlier prescription of distances 2, 3, and 3, respectively.

     (source)

(Picture from John Baez's post on Operads and the Tree of Life, which discusses work done on the topological space of phylogenetic trees.)

Answer 2

You might see how some notions fit with your intuition when small cases are examined. In the case of 1 object with n labels, similarity depends only on the number of labels given, and not which labels they are. In the case of 1 label for many objects, the dual notion of how many objects are labeled is key. Does your study favor one notion over the other?

Supposing that you temporarily study relations where each object is assigned at most one label. Now similarity can be measured by which objects share a label, and which do not. Is there an intuition as to what pair of relations is most dissimilar?

If you consider other properties you may want this measure to have, you may be able to classify and then later select which measure or measures best suit your purpose. Fortunately you have the restriction that the domain (the row order) is invariant, so that will simplify certain enumerations that you may want to classify your measure. For example, call the l-signature of a relation R that tuple such that the alpha-th coordinate is the number of labels assigned to alpha. How different can relations with the same l-signature be?

When you form and answer a number of questions of these types, then you can (or come back with your findings and we can) form your own class of measures which fit your intuition. Even just coming up with a set of signatures and saying which ones the measure should care about and which ones the measure can ignore will be progress.

Gerhard "Ask Me About System Design" Paseman, 2012.02.14