House-holding dilemma with Indian Data

House-holding or finding the records under the same house-hold is a typical data quality activity as far as linking individual records goes. According to Wikipedia, a house-hold is defined as “the basic residential unit in which economic production, consumption, inheritance, child rearing, and shelter are organized and carried out”. Typically, it refers to a family unit that stays in the same dwelling unit.

Household matches are found out using these properties:

1.       Last Name i.e. Family Name should be the same and

2.       Address (residential) on the records should be same

Let us look at the first point that is last name (or family name) matching. This is done under the assumption that the family members share the same family name. But this often fails in Indian context such as:

1.       Muslim families (well…most of them) do not have a family name concept.

2.      Traditionally family name concept was not present in South India.  Parents in south Indian families bestowed a single name to their child at birth and appended it with many initials. The abbreviations could stand for the ancestral village and the father’s first name in Karnataka, the house name in Kerala, for the caste name in Tamil Nadu and in Andhra Pradesh, the place of family origin.

I encountered this issue while performing name parsing for south Indian names. However, if we use a name component called last name instead of the family name (or surname) and use this component for individual matching then the complexity reduces a little when cross-matching is also used covering the name components. But for house-holding, this possesses a tough challenge.

Let us now look at the issues in address matching. We need to look at this keeping in mind the issues we saw in last name matching. The biggest issue in address matching is incomplete or partial addresses.

Let us look at the following addresses:

Address	Potentially Matching Address
Y 14, BLOCK EP, SECTOR V, SALT LAKE, KOLKATA, 700091	BLOCK EP, SECTOR V, SALT LAKE, KOLKATA, 700091
16A GARIAHAT ROAD, APT 1C, KOLKATA-19	16A GARIAHAT ROAD, KOLKATA 700019

Addresses on both the rows are close. But a detailed inspection reveals that the second address on these rows do not have the dwelling number. In fact, if these addresses appear on two records where names are matching then we would accept these as matches. But when there is no family name on the records then?
It’s a big question mark. Take for example the second address on the second row. It is a close match for the address 16A GARIAHAT ROAD, APT 2B, KOLKATA 700019 too.
Though residential telephone numbers are of much help, presence of such incomplete addresses possesses big challenges in house-holding. According to Graham Rhind (an expert in handling international data), house-holding should be avoided as far as possible (except some traditional anglo-saxon communities) because it hardly ever works.

Note: Discussion only includes individual house-holds and not corporate house-holds

Requirements for a Data Quality solution (updated on 6th August)

I have often come across questions like what could be the necessary properties for software that links records from my colleagues and clients and other associates. It largely depends on the objective of the record linking (please read my earlier post on Context Sensitiveness). However, I am giving a few points that can be considered as the necessary properties of such software.
For the ease of my convenience, I am dividing the properties into two exclusive sets of “Consolidation” and “Matching”. “Consolidation” is the data preparation steps that are carried out before any operation for matching begins. Steps followed in a typical “Consolidation” are:

Basic Cleanup
Here we do initial cleanup of the records like replacement or removal of special characters, replacing multiple consecutive spaces by a single whitespace.

·         Software should allow the users to write grammar rules for carrying out such cleanup. Grammar rules can be defined for any specific field.

·         Users should be able to write grammar rules applicable to the beginning/end of a field. Good matching software should be flexible enough to accept regular expressions.

Adjusting the misfielded information
Often values are put different fields such as Job Title values may be present in the name field even if there is a separate field in the system for Job Title. This routine should be able to identify such occurrences and rectify those.

·         Setting must accept at least two fields- one for the search and the other for the destination

·         Users will be able to decide in case the destination field is already populated

·         Solution can handle different requirements like pickup and adjust the search keyword or the portion of the field from the start till the keyword or the keyword till the end.

·         Users should be able to add/edit/delete different keywords.

·         Settings should be able to accept different sets of keywords for different search.

Misfielded data can be handled using parsing techniques and that is why a separate routine for handling these must be faster enough.

Identification
This routine can classify records into various types based on the presence of some keywords. An example of this would be to classify and flag individual customer records (B2C records) and Corporate/SME records (B2B records).

·         Users must be able to add/edit/delete keywords for each classification/identification.

Branching
This routine is closely related to identification. Often different type of records need to be treated differently down the line and hence need to be put in separate buckets. Branching does exactly this.

Parsing
Parsing is the process of splitting the words in a field like Name or Address into multiple component fields and is discussed in detail in my earlier posts in June 2011.

·         Users must be able to add/edit/delete keywords in the lookup tables for parsing

·         Users must be able to add new mask characters, lookup tables

·         Users must be able to add/edit/delete parsing rules

·         A good software must be able to handle partial parsing (see my earlier post on the topic)

·         Users must be able to create new parsing routines for any field

·         Software must be able to generate reports of parsing so that the quality can be assessed by the users and settings may be fine-tuned.

Genderization
The process of determining the gender of individual records based on various name components like Title or Given Name etc. is called Genderization.

·         Users should be able to prioritize the name components to be evaluated for Genderization

·         Users should be able to add/edit/delete gender codes corresponding various name words

·         Software must provide Genderization report that includes the percentages of records for which gender code could be assigned and the percentages of records for which gender codes could not be assigned, a sample of names where gender codes could be assigned and a sample of names where gender code could not be assigned

Augmentation
It is the process of enriching the data. One of the major data quality concern is the missing values for important fields. Augmentation or Enrichment is the process by which a data quality solution can take care of a portion of this. Besides filling up the missing information, this routine can also be used for validating the existing information e.g. a record might show the state name as NJ while the name of the city may be Dallas.
This routine can be divided into two sub-routines viz. internal augmentation and external augmentation.

1.       Internal Augmentation: It is the process of enriching information using the data values itself. For example, on a particular record, the name of the city may reside in the address lines instead of the city field.

2.       External Augmentation: It is the process of enriching/validating information using external data such as postal information, telephone directory etc.

·         Users must be able to select the validation/enrichment options from a list

·         Software will  flag the records where validation fails for a particular setting

·         A report must be generated showing the percentages of enriched records, percentages of records that could not be enriched, sample of enriched records etc.

Standardization
It is the process of transforming similar data values into a unique format. For example, different spellings and abbreviations for city names, state names etc. are made into a standard format.

·         Users must be able to select the fields which are going to be standardized

·         For every field to be standardized, users must be able to specify lookup tables that contain the variations and the standard format.

·         Each lookup table containing possible variations and the standard format need to be editable.

Rejection Routines
This routine can reject/flag records based on user defined rules like use of profanity, having information on which validation failed etc.

·         Users must be able to define rejection rules involving one or more fields and one or more lookup tables

·         All the lookup tables must be editable by the users

·         Users must be able to specify if rejection or flagging will be done

·         Software must be able to generate reports containing sample records (that got rejected or flagged) for each setting.

Once the “Consolidation” steps are executed, steps in the “Matching” process are followed for the surviving records. Steps followed in the “matching” routine are:

Defining Match Groups/Hierarchy
Users define the match hierarchy here. For example, the matching software can find the address matches and then for the records with matching addresses, it can probe further and can find out house-holds etc. So, defining more than one match groups requires a relation among these match groups. Some of the match groups may be unrelated while some others may be related

Two-step matching
A good matching software is able to perform matching in two steps. First step is called primary matching where hard keys defined for each record are compared to arrive at a match. Readers can refer to my earlier post on key-based matching in May 2011.

1.       Primary Matching

·         Users must be able to define one or more match keys

·         Users must be able to specify, for each key, what would be done in case a key element is missing for a record.

·         Users must be able to specify the string modes in which a field (or a portion of it) should be included in a match key. Two strings can be compared in various string modes such as

o   Consonated Mode: In this case, all the vowels are dropped from the string

o   Vowelized Mode: In this case, all the consonants are dropped from the string

o   Numeric Mode: In this case, all the non-numeric characters are dropped from the string

o   Phonetized Mode: In this case, the entire string is phonetically transformed (for details, please read my earlier post in June 2011)

o   Alpha Mode: In this case, all the numeric and special characters are dropped from the string

o   Alpha-Numeric Mode: In this case, all the special characters are dropped from the string

·         Users must be able to review the primary match results by generating sample reports

1.       Fuzzy Matching
Fuzzy Matching works on the probable matches discovered after primary matching. In this matching probable match pairs are classified into three subsets of definite matches, definite non-matches and suspected matches. This type of matching is also called probabilistic matching and can be implemented in many ways.

·         Fuzzy matching should be an optional step. Users may define the primary keys in a satisfactory way and may decide to consider the output of primary matching as final set of matches.

·         This routine must allow the users to specify the action(s) in case blank values are required to be compared to another blank or non-blank value. This setting may be different in case of different fields.

·         Fuzzy matching must allow the users to specify the string modes in which fields will be compared

·         This routine must allow users to specify the possible cross-matching options (for details please my earlier post in may 2011)

·         Users must be able to decide, for each fuzzy matching rule, the associated fields to be compared

·         At the end of fuzzy matching, users should be able to generate sample reports containing the matched and/or un-matched records for each group in the hierarchy.

Manual Decision/Review
Manual review is an important part of a data quality tool. System must provide the appropriate interface to the users so that each of the matches can be reviewed and the following decisions can be made:

1.       Mark as match

2.       Mark as un-match (This option will make sure that the concerned records are never matched in future, if that is the case)

3.       Hold a case for further verification and review by higher authority

Consolidation of indirect matches
After the final matching (Fuzzy matching in case of a 2-step matching or the primary matching in case of a 1-step matching), the matched records need to be consolidated. This routine, besides doing that, must be able to assign unique cluster number to every record such that matching records in a group (or cluster) get the same number. For more detail, please read my earlier post “Indirect Matching” in June 2011.

·         At the end of this consolidation, users must be able to generate sample match/un-match reports corresponding to each match group to review the results.

RaRationalization or selecting the survivo
This routine works after the consolidation of final matches is done and entire set of records are put into several clusters where each cluster contains matching records. Obviously, each un-matched record forms a cluster of size one.
Often business requires a single record representing a cluster of matching records. This was discussed in detail in my earlier post “Constructing the Survivor Record” posted in June 2011.

·         Users must be able to write code snippets to build the routine in case, it is complicated. System must provide the users with the code editor and available functions and fields and the logical operators.

Data Profiling is an important function of a good data quality software. Requirements around this would be:

Column analysis
This routine, given a table will generate the following reports:

·         Percentages of NULL or blank

·         Percentages of initials

·         Percentages of numeric values

·         Percentages of alpha values

·         Percentages of unique values

Frequency analysis
This routine, given a table will generate the following reports:

·         Frequency Report

·         Pattern frequency Report

Table analysis
Given two tables, this routine should be able to identify:

·         Common unique key between the tables

·         Orphan records i.e. records present in child table but not in master

Generate alerts
This routine will allow the users to define business rules and will generate compliance reports. Optionally this routine can generate failure alerts and send e-mails.

There are, of course, detail level requirements around each topic mentioned above.

We have discussed so far the technical requirements of the good matching software. But there are a few more requirements for this software depending upon the context. These are:

Input and Output
System should be able to read data from a number of sources including

1.       Text files

2.       Delimited files

3.       Excel files

4.       RDBMS files

Similarly, system should be able to output data in several formats.

GUI
System must have a good GUI. The steps we discussed earlier can be arranged in any order depending upon the requirement. Good to have a GUI that is drag-drop facility.


Workflow
I have mentioned requirements corresponding to a number of subject areas for the entire software. Users should be able to create workflows incorporating one or more source files and the required processes/functions and settings. These processes/settings should be flexible enough so that different workflows may use these in different order or even may not use some of these as per the context.

Integration
Such a matching tool can be used stand alone or another application may use the services.

Performance
Functional requirements for matching software require a lot of string manipulation. But the software must be quick enough to process large volume of data files.

Context Sensitiveness in Matching

At present there is a serious discussion going on in the Linekdin group “Matching” (You need to be a member of the networking site Linekdin and also a member of the group “Matching” to access the thread) on the subject of Context Sensitiveness in matching. The subject is closely related to probable errors in matching. Looking at the richness of the content in this discussion and the vastness of the topic itself, I am tempted to share my understanding in this regard.

Let me begin by sharing an experience I had a few years back while implementing a data quality solution in a private bank. This bank was in the process of implementing a data quality solution for its large customer base.  In order to fine-tune the matching algorithm, it gave us a control/test file (consisting of a few hundred records) and with this, we tried various possible algorithms. It took us some time before we came up with the proper match algorithm for the control file. Both the business users and the IT users were happy with the result displayed for the control file. But to our horror, the same algorithm became a disaster when a portion of the customer data was processed. We finally had to realign the algorithm from the start.

Before I explain the scenario, let me give one example of the disparity. Consider the two individual records (only a few fields) in the table below:

Name	Address	City	Tel1	Tel2
ABHISEK C KOTCHER	C TOWER, UNO 12, JEEVAN MANZIL	SURAT	1111111111	2222222222
AVISEK C	C12 OFF MG RD, NEAR JEEVAN MANZIL	SURAT	3333333333

Above two records were matched by the algorithm developed using the control file. But for the customer data integration activity these records were not a match as we realized later.

We wanted to know if this one was a one of case or there was something fundamentally wrong. To our shock, we found that the control file given by this bank was a portion taken out from their fraud detection de-duplication database which was prepared by another vendor earlier. Unfortunately this vendor did not make the bank aware of the effect of using the same or similar match algorithm under different context.

In case you can spare some time, you may refer to my earlier post “Errors in matching” posted during May 2011.
In a nutshell, there are two types of possible error when we say; there is a match (or no match) between two specific records. When the algorithm says it’s a match but actually the records represent two different entities, the error is called a false positive. And when the algorithm says that there is no match between the records but actually the records represent the same entity then the error called a false negative. Depending on the context in which the match results will be used there are two types of match objectives. One situation demands that a slight similarity should be captured by the match algorithm and thereby the corresponding objective becomes to reduce false negatives. Another type of scenario demands that two records should match only when there is strong similarity and the corresponding objective in this case becomes to reduce false positives.

In a fraud detection type of context, the objective is to capture a slight similarity so that none is escaped. But in a typical customer data integration type of context, the objective is to allow two records to match only when there is strong evidence that these represent the same entity.

I do not think there is any strategy to improve the match algorithm in a way so that both false positives and false negatives reduce (unless of course you change the input file/files!). Unfortunately there is no mathematical proof of this but experience of people in this field tells so.  And that is why we have these two possible objectives rather than just one that requires reduction of both false positives and false negatives.

The idea is when one adjusts the match algorithm to reduce false positives as in the case of a typical CDI type of situation by making the match settings stricter, one increases the risk of having more false negatives. On the other hand, when one adjusts the match algorithm to reduce false negatives as in the case of a typical fraud detection type of situation by making the match settings relaxed, one increases the risk of having more false positive.

So, before you start working on the match algorithm (setting), be sure of the objective.

Compound Words

[I will use many examples in this discussion. Most of these examples are taken from Indian files but a few are from international files.]

While trying to de-dupe records, issues with compound words crop up often. A nice post on this is written by Henrik Liliendahl Sørensen.Such issues come up when we need to match two field values with at least one field value consisting of more than one words. For ease of discussion, I will split the topic into two. Firstly, we will talk about compound words in name matching.
Let me give a few examples of names:

Name – Record1	Matching Name-Record2
JOHN P SMITH	JOHNP SMITH
DADAN BHAI BOTTLEWALA	DADANBHAI BOTTLEWALA
AMAL KANTI SEN	AMALK SEN

After parsing, these names will be

Name – Record1			Matching Name-Record2
First Name	Middle Name	Last Name	First Name	Middle Name	Last Name
JOHN	P	SMITH	JOHNP		SMITH
DADAN	BHAI	BOTTLEWALA	DADANBHAI		BOTTLEWALA
AMAL	KANTI	SEN	AMALK		SEN

Notice that in each of these three cases, matching names do not have a middle name. Also on the first two instances, the concatenated values of first name and middle name of the first record matches to the first name of the second record.
Names on the third row, on the other hand are a bit different. Ideally speaking the two names do not exactly match. But since we know that the use of initials for the middle names is frequent, we need to allow these two names to match but with a probability less than 100%.
This is because we need to allow the two words KANTI and K to match as middle names with probability less than 100%.

Names in this table can be matched by using the following rule:

1.      For all probable match pair of record

1.1.   If the middle name is empty in exactly one record in a pair

1.1.1.      If the two first names, when compared, do not give adequate match probability     
    then carry out the following

1.1.1.1.            Concatenate the first name and middle name of the other record in the
        pair and compare this string with the first name of the record where
        middle name is blank

1.1.1.2.            If the probability in the comparison above do not give good result, see if
        the first name on the record where middle name is not blank, is a subset
        (from the beginning) of the other first name then

1.1.1.2.1.                  Consider the remaining substring from the first name where
             middle name is blank. If the length of this substring is 1 then see
             if there is an initial match between this character and the middle
             name on the other record.

There are several types of occurrences of compound words in addresses.
Let us consider the following examples:

Case #	Address Word – Record1	Matching Address Word-Record2
1	25 MAIN ROAD NEAR IIT CAMPUS	25 MAIN ROAD NEAR I I T CAMPUS
2	21 MG ROAD BOWBAZAR	21 M G ROAD BOWBAZAR
3	SCHORBACHSTRASSE 9	SCHORBACH STRASSE 9
4	NEW YORK	NEWYORK

In the first two instances (case # 1 & 2) refer to one style of issues involving compound words where abbreviations of place names using the initials are written differently.
In the next instance (case # 3) refer to another style of issues involving compound words street names and the corresponding street types are combined together.

Let us see what happens to these addresses (case # 1, 2 and 3) after proper parsing

Original Address	Hse. No.	St. Nm.	St. Typ.	Location	Landmark
25 MAIN ROAD NEAR IIT CAMPUS	25	MAIN	ROAD		IIT CAMPUS
25 MAIN ROAD NEAR I I T CAMPUS	25	MAIN	ROAD		I I T CAMPUS
21 MG ROAD BOWBAZAR	21	MG	ROAD	BOWBAZAR
21 M G ROAD BOWBAZAR	21	M G	ROAD	BOWBAZAR
SCHORBACHSTRASSE 9	9	SCHORBACHSTRASSE
SCHORBACH STRASSE 9	9	SCHORBACH	STRASSE

In the first case, we need to match IIT CAMPUS to I I T CAMPUS. We can drop the keyword CAMPUS for matching and then remove the whitespace characters if the field contains only initials.
In the second case we can adopt the same technique.
Third case is unique. This is an address example from picked up from data file from Germany.
STRASSE is a popular street type in this country which is often clubbed with the corresponding street name. One way to handle this would be if the street type is STRASSE then combine street name and street type together and compare this value to the street name of the other record in a probable match pair.

Last instance (case # 4) is an example of the city field which can be tackled using standardization.

Lastly, I have seen many cases of typo that lead to issues involving compound words in matching. I prefer using a separate match technique built on the earlier match technique where we compared two strings where each string contained one word. I will briefly discuss this in my next post.