Instance matching is the problem of nding instances that co-describe the same topic. The performance of an instance matching system relies on the speci ed con guration, which is optimally designed for each particular dataset. We propose cLearn, a heuristic-based algorithm that automatically searches for the most appropriate matching con guration for the given repositories. cLearn is e ective when being tested on OAEI benchmarks and outperforms previous supervised systems.
Finding co-reference instances is an important problem of knowledge discovery
and data mining. It has a large application in data integration and linked data
publication. Many approaches have been proposed for instance matching. Among
them, supervised instance matching has been revealed as the most accurate
approach [
Fig. 1 illustrates the general architecture of supervised and con gurationbased instance matching. Given two input repositories, Rsource and Rtarget, the property alignment generator creates the property alignments which are expected to describe the same attribute. The similarity function generator uses the property alignments to create a list of initial similarity functions. A similarity function is speci ed by two pieces of information: a property alignment [psource; ptarget] and a similarity measure S (e.g. Levenshtein, Jaro-Winkler, and TF-IDF). For two instances: x and y, a similarity function calculates the similarity S(value(x; psource); value(y; ptarget)) where value(a; p) extracts the attribute
Property alignment generator e c r u o s R t e g r a t
value declared by p of a. The candidate generator reduces the huge number of
pairwise alignments between instances of input repositories by selecting only
pairs of potentially co-referent instances [
A con guration speci es the combination of similarity functions Fsim, the similarity aggregator Agg, and the acceptance threshold of the co-reference lter. Given series of initial similarity functions Isim and similarity aggregators Iagg, and the labeled candidates, the mission of cLearn is to select the optimal Fsim, Agg, and .
The pseudo code of cLearn is written in Algorithm 11. Labeled candidates are divided into training set T and validation set V before inputting into cLearn. Init creates a con guration by assigning Agg, Fsim, and with given values. M atch executes the similarity aggregator and co-reference lter in order to obtain the detected co-referent instances. F indT hreshold automatically assigns a value to . This function rst selects the top jT +j candidates with highest matching score, where jT +j is the number of the actual co-references (positive candidates) in T . Then, it assigns the lowest score of the correctly detected co-reference to . Evaluate computes the performance of entity resolution by comparing the generated results with the labeled data. In cLearn, F 1 score is used as the default performance metric because F 1 it is the main expectation of general instance matching task. The metric can be easily changed (e.g, precision and recall) to adapt with the objectives of particular task.
cLearn begins with the consideration of each single similarity function and then checks their combinations. This algorithm works with two underlying heuristics. The rst one is the limitation of the number of single similarity functions to Ktop (line 10), which is set to 16 by default. The second one is the direct enhancement assumption (line 20). The performance of using a new combination 1 In this pseudo code, we use dot (`.') notation to indicate the member accessor.
A Heuristic Approach for Con guration Learning of Instance Matching Algorithm 1: cLearn
Input: Training set T , validation set V , integer paramerter Ktop list of similarity functions Isim, list of similarity aggregators Iagg
Output: Optimal con guration Copt 1 Cagg ; 2 foreach A 2 Iagg do 3 visited ; 4 foreach sim 2 Isim do 5 c Init(Agg A; Fsim sim; 0) 6 links M atch(c; T ) 7 c: F indT hreshold(links; T ) 8 F 1 Evaluate(links; T ) 9 visited visited [ f[c; F 1]g must not be less than that of the components. This heuristic does not guarantee an identical result with exhaustive search. However, it is reasonable as a series of similarity functions that reduces the performance has little possibility of generating a further combination with improvement. Meanwhile, the exhaustive search is extremely expensive.
cLearn is implemented as part of ScSLINT framework, and its source code is available at http://ri-www.nii.ac.jp/ScSLINT. 3
We use OAEI 2010 dataset to compare ScSLINT+cLearn with ObjectCoref [
0.464 spective subset for the comparisons. Adaboost uses 5% candidates for training and ObjectCoref uses 20 actual co-references, which is respectively equivalent to 2.3%, 11.6% and 1.2% candidates for the rst three subsets. The results on the last two subsets of ObjectCoref are missing. In order to reduce the random noise, for each subset, we repeat the test 10 times and compute the average results, which are reported in Table 1. According to this table, ScSLINT+cLearn consistently outperforms other systems. Compared to ObjectCoref, ScSLINT+cLearn remarkably improves the results. Compared to Adaboost, cLearn is much better on two subsets related to DailyMed, a repository by itself contains the highest number of co-references.
cLearn is e cient as the average numbers of con gurations that cLearn
has to check before stopping is only 246. This number is promising because it
is much smaller than that of using genetic algorithm, which is reported in [
With the e ciency, e ectiveness, and small training data requirement of cLearn on a real dataset like OAEI 2010, we believe that cLearn has promising application in supervised instance matching, including using active learning strategy to even reduce the annotation e ort.