THE MATCHBOX ALGORITHM FOR - University Of Regina

CHAPTER 4 44 EXPERIMENTAL RESULTS. RESULTS EXPERIMENTAL 44 4.1 Introduction. Introduction 4.2 Independent Independentapplication applicationoof f CC-rules -rules. 45 47 f aasequence f CC-rules -rules.47 Applicationoof sequenceoof 4.3 Application 50 4.4 Varying Varyingthe theorder orderoof thesequence sequenceoof f the f CC-rules -rules.50 4.5 for HAS HAS and and LA LAS Confusion S. 52 Confusion matrix matrix for 4.6 Spousal es. 53 Spousal ordering ordering and and canonical canonical first first nam names 4.7 55 the size size ooff the the repaired repaired secondary secondary list. list Increasing Increasing the Matchboxand andMMP-SNM f Matchbox P-SN M . 56 4.8 Comparison Comparisonoof CHAPTER 5 62 FUTURE WORK. WORK CONCLUSIONS AND AND FUTURE CONCLUSIONS 62 f contributions.62 contributions 5.1 Summary Summaryoof 5.2 63 Suggestions for for future future research. research Suggestions R eferences. References vii R ep ro d u ced with permission p erm ission of o f the copyright owner. ow ner. Further reproduction reproduction prohibited without w ithout permission. perm ission. Reproduced 65

List of Tables Table 1.1 1.1 Tworecords recordsthat thatare aremissing Two missingcrucial crucialinformation. information 9 Table 2.1 Primary 12 Primarylist. list 12 Table 2.2 Secondarylist. list Secondary 13 13 Table 2.3 Repaired Repairedsecondary secondarylist.14 list 14 Table 2.4 Matchlist. list Match 15 15 Table 2.5 Novel 15 Novellist. list 15 Table 2.6 Partiallist listoof nicknamesfor forfirst firstnam names Partial f nicknames es.17 17 Table 2.7 Individual 19 Individualand andspousal spousalname namevariations. variations 19 Table 2.8 Summary Summaryof ofmethods methodsfor forsynonymous synonymousrecords.26 records 26 Table 3.1 Attributesused usedininC-rules C-rulesininthis thisthesis.33 thesis Attributes 33 Table 3.2 Example Exampleset setfor forSNM SNMstep step 1.41 1 41 Table 3.3 Exampleset setfor forSNM Example SNMstep step22.42 42 Table 4.1 Performancefor forconditional conditionalrules rules(No (NoSequence). Sequence) 46 Performance Table 4.2 High HighAccuracy AccuracySequence Sequence(HAS): (HAS):Sequence Sequenceand andperformance.48 performance . 48 Table 4.3 Summaryoof accuracycomparison comparisonfor for20 20sequences. sequences Summary f accuracy 50 Table 4.4 LowAccuracy AccuracySequence Sequence(LAS): (LAS):Sequence Sequenceand andperformance. performance Low 51 Table 4.5 Confusionmatrices matricesfor forHAS HASand andLAS.52 LAS 52 Confusion Table 4.6 Effectiveness f SO Effectivenessoof SOand andCFN CFN (for (for step step 11 only). only) 54 Table 4.7 Effectivenessoof SOand andCFN CFN (for Effectiveness f SO ).54 (for both both step 1and andstep step22) 54 Table 4.8 Comparison f time, Comparisonoof time,precision, precision,and andaccuracy. accuracy 56 Table 4.9 Comparisonoof resultsbetween betweenMP-SNM MP-SNMand andMatchbox.57 Comparison f results Matchbox 57 Table 4.10 Feature Featurecomparison. comparison 61 viii Reproduced R ep ro d u ced with permission p erm ission of o f the th e copyright owner. ow ner. Further reproduction reproduction prohibited without w ithout permission. perm ission.

List of Figures Figure 2.1 24 mergephase. phase Window Windowscan scanduring duringthe themerge Figure 3.1 30 Matchbox Matchboxalgorithm algorithm-— Step Step 1.30 1 Figure 3.2 Steps22 and and33. 31 Matchbox Matchboxalgorithm algorithm-— Steps Figure 3.3 Canonical first firstname namequery.35 query Canonical 35 Figure 3.4 Algorithm 37 The The Soundex SoundexAlgorithm. Figure 4.1 secondary list list on onelapsed elapsed size oof therepaired repairedsecondary Effect f the Effect of ofincreasing increasingthe the size time tim e .55 55 Figure 4.2 Comparison f precision.59 Comparisonoof precision 59 Figure 4.3 Comparison f accuracy. accuracy Comparisonoof 59 Figure 4.4 Comparisonoof elapsedtim time Comparison f elapsed e. 60 ix R ep ro d u ced with permission p erm ission of o f the th e copyright owner. ow ner. Further reproduction reproduction prohibited without w ithout permission. perm ission. Reproduced

List of Abbreviations and Acronyms AC: Accuracy. CA: Compare All. CF: Certainty Factor. CFN: Canonical First Name. C-rule: Conditional Rule. DB-P: Primary Contact List. DB-S: Repaired Secondary Contact List. DE-SNM: DE-SNM: Duplicate Elimination Sorted Neighborhood Method. FP: False Positive. HAS: Highest Accuracy Sequence. LAS: Lowest Accuracy Sequence. LLLK algorithm: Lee, Lu, Ling, and Ko algorithm. MP-SNM: MP-SNM: Multi Pass Sorted Neighborhood Method. P: Precision. RFM: Recursive Field Matching. SNM: Sorted Neighborhood Method. SO: Spousal Ordering. SQL: Structured Query Language. TH: Threshold. TP: True Positive. x R ep ro d u ced with permission p erm ission of o f the th e copyright owner. ow ner. Further Further reproduction reproduction prohibited prohibited without w ithout permission. perm ission. Reproduced

CHAPTER 11 INTRODUCTION This chapter provides an introduction to the thesis in Section 1.1. 1.1. An outline of o f the remainder of o f the thesis is given in Section 1.2. 1.2. 1.1 1.1 Introduction to the thesis The general problem addressed in this thesis is ensuring that data inserted into a o f high quality. According to the original definition, a data warehouse data warehouse is of is a subject-oriented, integrated, time-variant, and non-volatile collection of o f data in o f management's decision making process [15]. Currently, the term data support of warehouse is used to refer to a relational database that contains historical data collected from several data sources [1]. A data warehouse is a relational database that is designed for query and analysis purposes [15]. Ensuring that data in a data warehouse is of o f high quality simplifies the update and other maintenance operations such as development of of new services that utilize the data warehouse and facilitate the provision of o f excellent customer service. Users may view the same data from a data warehouse in different forms. In this thesis, we focus on data viewed as contact lists. A contact list is a file or a database containing uniquely identifiable records, each o f which describes how to make contact with a person or group of o f people via telephone, of mail, email, etc. The best known type of o f contact list is a mailing list. Contact information can be maintained in a data warehouse to allow organization wide access to this valuable resource. A particular contact list can be extracted from the data warehouse using criteria based on its purpose or the current direct marketing strategy. For example, When a phone contact list is extracted from the data warehouse, the required fields may be the 1 Reproduced R ep ro d u ced with permission p erm ission of o f the th e copyright owner. ow ner. Further reproduction reproduction prohibited without w ithout permission. perm ission.

salutation, the last name, and the telephone number. On the other hand, when a mailing list is extracted, the required fields may be the salutation, the first name, the last name, the street address, the city name, and the postal code. Lee et al. emphasizes the need for setting up a data warehouse [16]. According to Han and Kamber, data should be pre-processed before it is stored in a data warehouse [8]. Preprocessing can improve the quality of o f data and thus the quality of o f the results obtained from all subsequent analyses based on the data in the data warehouse. According to one definition [7], data cleaning is the task of o f detection and correcting errors in a data set. Typically, data cleaning occurs before the data is placed in the data warehouse [8]. Thus, data cleaning can be viewed as a kind of o f preprocessing applied before data are loaded into a data warehouse. The process of o f data cleaning is crucial because of o f the "garbage “garbage in, out” principle [11]. [11], garbage out" o f data cleaning typically applied to contact lists are as follows: Some types of updating the addresses for those customers who recently moved (based on change of o f an address address information filed with the post office), verifying the accuracy of (based on lists of o f valid street addresses, city names, and postal codes maintained by the post office or other organization), and removing extra records for the same person or group. Data cleaning permits better customer service, because cleaning increases the accuracy and completeness of o f the data. Some typical benefits that an organization can obtain from data cleaning are as follows (adapted from [13]): 1. Reduced mailing costs from identifying unique customers and removing duplicated 1. information from the database. 2 Reproduced R ep ro d u ced with permission p erm ission of o f the th e copyright owner. ow ner. Further reproduction reproduction prohibited without w ithout permission. perm ission.

2. More efficient data maintenance and consequently increased operational savings through ongoing data quality controls and data integrity. For example, in a credit check application, high quality data will improve the decision-making concerning the customer's customer’s credit status and thus lower the overall operational cost. 3. Increased fraction of responses from contact campaigns run by the organization. Clean data helps the organization target the right customers at the right time. 4. Enhanced customer satisfaction and loyalty via consolidated customer profiling. Clean data helps an organization understand its customer likes and dislikes. A major difficulty faced by direct marketing, non-profit, political, and charitable organizations is the synonymous record problem, where multiple records in a contact list represent the same real world entity in different forms. Whenever this problem exists, it is o f the crucial that it be addressed by data cleaning. The most common version of synonymous record problem occurs when the same person is represented in a contact list with slightly varying names or addresses. The major reasons for synonymous records and other problems in data quality are as follows (adapted from [8] and [16]): 1. Typographical errors in data entry and data recording: for example, the first name 1. may be recorded as "Hohn" “Hohn” instead of o f "John". “John”. 2. Inconsistent data entry formats or naming conventions: for example, the apartment number may be recorded as a separate field in one list, but it may be combined with address line 11 in another list. 3 Reproduced R ep ro d u ced with permission p erm ission of o f the th e copyright owner. ow ner. Further reproduction reproduction prohibited without w ithout permission. perm ission.

3. Inconsistent updates: for example, two lists may both include product codes to o f product codes may have been changed, resulting in categorize items, but the set of two different codes for the same product in the list. 4. Poor database design: for example, a field may not have been provided to record middle names. 5. Faulty data collection instrument: for example, due to poor software design the first name may always be stored as the last name and the last name as the first name. 6. Errors in data transmission: for example, a credit card processing mechanism with a limited buffer size may drop significant information, such as the last letters from names longer than 20 characters. 7. Missing updates: for example, a woman who changed her name when she got married may not have made an explicit request that her last name be updated. 8. Misleading information deliberately provided by customer: for example, a person o f his legal first name in an effort to be treated may have given his nickname instead of as two different individuals. 9. An incomplete or missing data value: for example, a customer may not have provided his middle name. Organizations that do not address the synonymous record problem waste significant amounts of o f time, money, and other resources. For example, extra mailing costs are incurred for every letter sent to a duplicated or incorrect address. These costs are repeated for every direct mail campaign. Updates to the contact list are also complicated by the synonymous record problem. Sincere efforts to respond to change of o f address requests, spelling corrections, death notices, last name changes due to marriage, and 4 Reproduced R ep ro d u ced with permission p erm ission of o f the th e copyright owner. ow ner. Further reproduction reproduction prohibited without w ithout permission. perm ission.

requests for removal from the mailing list may be ineffective, because only one of o f the synonymous records is adjusted. For example, consider a contact list that contains two records that represent the same person. If the organization learns that the person has died, o f the records, it may subsequently try to contact the dead person. but it updates only one of This attempted contact wastes effort and money and may offend potential customers. The synonymous record problem often results after two contact lists are merged. A specific version of the problem with three notable features is investigated in this thesis. First, one of o f the contact lists is of o f much higher quality and value than the other. Secondly, o f standard names. Thirdly, the name field of o f a record nicknames are often used instead of o f a group of o f people

Matchbox is based on conditional rules (or C-rules) for matching records based on combinations of attributes such as names, addresses, name aliases, and spousal units. As indicated in other studies, the probability of cleaning 100% of the errors from data is very slim. Matchbox can be used as an automatic method that can efficiently find a high