Calculating the accuracy of matching between two sets of strings lists

To give some background - the question is about measuring the accuracy of name disambiguation algo results (and not about the algo itself)

Let's say we have three groups of entities, each corresponding to the same name (instead of real names they will be represented as numeric ids, just for simplicity). This is our ground truth:

+---------+------------+
| Groups  | Duplicates |
+---------+------------+
| Group 1 | [1, 2, 3]  |
| Group 2 | [4, 5, 6]  |
| Group 3 | [7, 8]     |
+---------+------------+


That means, that [1, 2, 3] correspond to one name, [4, 5, 6] for another one and so on.

Then, the results of our matching algo (not real data, just for example) look this way:

+---------+------------+
| Groups  | Candidates |
+---------+------------+
| Group 1 | [1, 2]     |
| Group 2 | [3, 5, 6]  |
| Group 3 | [4, 7, 8]  |
+---------+------------+


Knowing which candidates group corresponds to which group from he ground truth we can measure F1 easily:

But what if we don't know which candidates group corresponds to which ground-truth group?

At first I tried "unpacking" groups, meaning I've created pairs of id: other ids from the same group, for example, for ground truth 1: [2, 3], 2: [1, 3] and so on, and measure the F1 for each such pair (between truth and prediction):

That gave me a result pretty far from the "real" one (the one where I knew the connections between groups)

Then I tried to create one-to-one pairs - id: single id from the group, for example for ground truth 1: 2, 1: 3, 2: 3 and so on. Which gave me result far from desired as well (if I interpret it right, in this particular case accuracy equals precision, recall and f1)

And finally the question is - is there any way to measure how accurate the prediction is (without knowing which prediction corresponds to which group from ground truth) and at the same time to have that measure as close to the one where we knew the relations as possible?

• Important question: When calculating prediction accuracy, do you know which words are duplicates of each other (i.e ground truth) or not ? In the former case it is a classification problem (which variable class name), in the second case a clustering problem. (To reviewers: Please give some time, do not close question in a hurry) Commented Aug 1, 2018 at 7:29
• @steffen not sure if I understood your question right, but I'm not using ground truth in prediction calculation, only in prediction accuracy testing. All words (ids in this particular case) within one group in ground truth are considered to be the duplicates. Commented Aug 1, 2018 at 9:04

As it sounds to me the question is simply about comparing two classifications. I this case - one is "true", the other is "artificial".

Out of the n=8 objects create all the n(n-1)/2=28 pairs. Calculate the 2x2 confusion table of counts which in this case is called the comembership confusion table. The rows dimension is True classification, the columns is Prediction classification, both with labels "In the same group", "Not in the same group". Thus, cell (1,1) contains the count of pairs of objects where both objects belong to the same group both in T and P classification. Cell (1,2) is the count of pairs where both objects belong to the same group in T classification but not in P classification. Cell (2,1) is the count of pairs where both objects belong to the same group in P classification but not in T classification. Finally, cell (2,2) is the count of pairs where both objects do not belong to the same group neither in T nor in P. The sum in the table will be 28, number of pairs.

The comembership confusion table in your example is:

                     Predicted
SameGr  NotSameGr
True  SameGr      3         4
NotSameGr   4        17


Then, based on this confusion table you can compute a number of "matching coefficients" or "external clustering criterions" (other names are used in literature too), including F1, Rand index, Jaccard, Dice, Fowlkes-Mallows, McNemar, Phi correlation, etc etc (the many association measures based on a 2x2 contingency table). I think that you know some of them. They are used to compare classifications or partitions - any, not necessarily "true" one with "predicted" one. The key point here was that the indices are computed based in the confusion table which unit of count is pair of objects and the table labels are "in the same class" vs "in different class" - rather than a confusion table where count unit is object and the table labels are "true/positive" vs "false/negative".

From this point of view, an object was classified "correctly" or "accurately" if it met in one group in P classification with the same objects as it meets with in T classification; one don't have to know group (classes) labels and their correspondence between the two classifications (the number of groups can even be different in T and P). Groups identity are determined by their members togetherness.