Automatic record linkage using seeded nearest neighbour and support vector machine classification

ABSTRACT

The task of linking databases is an important step in an increasing number of data mining projects, because linked data can contain information that is not available otherwise, or that would require time-consuming and expensive collection of specific data. The aim of linking is to match and aggregate all records that refer to the same entity. One of the major challenges when linking large databases is the efficient and accurate classification of record pairs into matches and non-matches. While traditionally classification was based on manually-set thresholds or on statistical procedures, many of the more recently developed classification methods are based on supervised learning techniques. They therefore require training data, which is often not available in real world situations or has to be prepared manually, an expensive, cumbersome and time-consuming process.

The author has previously presented a novel two-step approach to automatic record pair classification [6, 7]. In the first step of this approach, training examples of high quality are automatically selected from the compared record pairs, and used in the second step to train a support vector machine (SVM) classifier. Initial experiments showed the feasibility of the approach, achieving results that outperformed k-means clustering. In this paper, two variations of this approach are presented. The first is based on a nearest-neighbour classifier, while the second improves a SVM classifier by iteratively adding more examples into the training sets. Experimental results show that this two-step approach can achieve better classification results than other unsupervised approaches.

REFERENCES

• 1: R. Baxter, P. Christen, and T. Churches. A comparison of fast blocking methods for record linkage. In ACM KDD'03 workshop on Data Cleaning, Record Linkage and Object Consolidation, pages 25--27, Washington DC, 2003.
• 2: Indrajit Bhattacharya , Lise Getoor, Collective entity resolution in relational data, ACM Transactions on Knowledge Discovery from Data (TKDD), v.1 n.1, p.5-es, March 2007 [doi>10.1145/1217299.1217304]
• 3: Mikhail Bilenko , Raymond J. Mooney, Adaptive duplicate detection using learnable string similarity measures, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956759]
• 4: C.-C. Chang and C.-J. Lin. LIBSVM: A library for support vector machines. Manual, Department of Computer Science, National Taiwan University, 2001. Software available at: http://www.csie.ntu.edu.tw/~cjlin/libsvm.
• 5: P. Christen. Probabilistic data generation for deduplication and data linkage. In IDEAL'05, Springer LNCS 3578, pages 109--116, Brisbane, 2005.
• 6: Peter Christen, A two-step classification approach to unsupervised record linkage, Proceedings of the sixth Australasian conference on Data mining and analytics, December 03-04, 2007, Gold Coast, Australia
• 7: P. Christen. Automatic training example selection for scalable unsupervised record linkage. In PAKDD'08, Springer LNAI 5012, pages 511--518, Osaka, 2008.
• 8: Peter Christen, Febrl: a freely available record linkage system with a graphical user interface, Proceedings of the second Australasian workshop on Health data and knowledge management, January 01-01, 2008, Wollongong, NSW, Australia
• 9: P. Christen and K. Goiser. Quality and complexity measures for data linkage and deduplication. In F. Guillet and H. Hamilton, editors, Quality Measures in Data Mining, volume 43 of Studies in Computational Intelligence. Springer, 2007.
• 10: T. Churches, P. Christen, K. Lim, and J. X. Zhu. Preparation of name and address data for record linkage using hidden Markov models. BioMed Central Medical Informatics and Decision Making, 2(9), 2002.
• 11: W. Cohen, P. Ravikumar, and S. Fienberg. A comparison of string distance metrics for name-matching tasks. In IJCAI'03 workshop on Information Integration on the Web (IIWeb-03), pages 73--78, Acapulco, 2003.
• 12: William W. Cohen , Jacob Richman, Learning to match and cluster large high-dimensional data sets for data integration, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775116]
• 13: TAILOR: A Record Linkage Tool Box, Proceedings of the 18th International Conference on Data Engineering, p.17, February 26-March 01, 2002
• 14: Ahmed K. Elmagarmid , Panagiotis G. Ipeirotis , Vassilios S. Verykios, Duplicate Record Detection: A Survey, IEEE Transactions on Knowledge and Data Engineering, v.19 n.1, p.1-16, January 2007 [doi>10.1109/TKDE.2007.9]
• 15: I. Fellegi and A. Sunter. A theory for record linkage. Journal of the American Statistical Society, 64(328):1183--1210, 1969.
• 16: Karl Goiser , Peter Christen, Towards automated record linkage, Proceedings of the fifth Australasian conference on Data mining and analystics, p.23-31, November 29-30, 2006, Sydney, Australia
• 17: L. Gu and R. Baxter. Decision models for record linkage. In Selected Papers from AusDM, Springer LNCS 3755, pages 146--160, 2006.
• 18: J. Jonas and J. Harper. Effective counterterrorism and the limited role of predictive data mining. Policy Analysis, (584), 2006.
• 19: U. Y. Nahm, M. Bilenko, and R. J. Mooney. Two approaches to handling noisy variation in text mining. In TextML'02, pages 18--27, Sydney, 2002.
• 20: J. S. Sanchez, J. M. Sotoca, and F. Pla. Efficient nearest neighbor classification with data reduction and fast search algorithms. In IEEE International Conference on Systems, Man and Cybernetics, volume 5, pages 4757--4762, 2004.
• 21: Sunita Sarawagi , Anuradha Bhamidipaty, Interactive deduplication using active learning, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775087]
• 22: Sheila Tejada , Craig A. Knoblock , Steven Minton, Learning domain-independent string transformation weights for high accuracy object identification, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775099]
• 23: W. E. Winkler. Using the EM algorithm for weight computation in the Fellegi-Sunter model of record linkage. Technical Report RR2000/05, US Bureau of the Census, 2000.
• 24: William E. Winkler, Methods for evaluating and creating data quality, Information Systems, v.29 n.7, p.531-550, October 2004 [doi>10.1016/j.is.2003.12.003]
• 25: Hwanjo Yu , ChengXiang Zhai , Jiawei Han, Text classification from positive and unlabeled documents, Proceedings of the twelfth international conference on Information and knowledge management, November 03-08, 2003, New Orleans, LA, USA [doi>10.1145/956863.956909]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

General Terms:
Algorithms, Experimentation, Performance

Keywords:
data linkage, data matching, deduplication, entity resolution, nearest neighbour, support vector machine