Limitations in the Parsing approach (updated on 11th. June 2011)

In the earlier post, we saw how parsing can be automated (with the help of name parsing). Why did we use name parsing as example? Well… I used it because a name string has less number of possible components in an address string (usually).
It can be appreciated that the total number of possible combination increases with the number of possible components.
Let us have an idea about the magnitude of such possible combination.
Suppose the original string has n number of tokens and there are m possible components.
We also assume that a valid string will have minimum p number of components.
Case1: Each component appears only once in the string (and m > n).
Here, the total number of possible patterns is: m!/n!
Case2: Each component can be repeated.
Here, the total number of possible patterns is: mⁿ

So, we see that in either case, for fixed n, total number of possible patterns increases with m
Well… in reality, none of the above cases is applicable in full. There are complex relationships among the components though such relationships are kind of probabilistic in nature. Such as: in US a street type usually appears after a street name.

So, we see the first limitation of this kind of automation. It is that the number of possible patterns is potentially high. In fact, in developing countries i.e. where the addressing conventions are not standardized, the number of address components (and thus patterns) is very high. To give an idea, even 50K different patterns were not sufficient to process address data from India.
High number of patterns impacts an automated solution in two ways:

1.        It takes more effort to develop the vocabulary and the table containing the parsing rules.

2.       High volume of vocabulary and high number of entries in the table containing the parsing rules makes the processing window time (for the automated solution) high.

Apart from the above, there is one more limitation in the parsing approach described earlier.
Let us consider the initial A in an address string. Usually, it is an abbreviation for the word APARTMENT and is used as an apartment identifier. But many times it also appears to denote something else. The initial A might be a part of the house number (or street number), bock or even a street name.
Similarly, the token KUMAR may be a person’s first name or middle name or last name.
The word MD at the end of a name string may denote a job title. It may also be an abbreviation for the word MOHAMMED.

One more issue that is seen during parsing is (actually an issue in matching) the use of compound words in names (personal names as well as names of street, city, locality, company etc.). Let us give one name example:

Name	First Name	Middle Name	Last Name
ATULPRASAD SEN	ATULPRASAD		SEN
ATUL PRASAD SEN	ATUL	PRASAD	SEN

These names are taken from Indian data. Clearly, these Names are equal but a space in between ATUL and PRASAD in the given name is creating a big issue here. Even if we have a soft-key based matching we will end up getting much less than 100% comparison probability for first name comparison between these two records and much less than 100% comparison probability for first name cross middle name comparison between these two records.
But one look at the given names in these records tells us that these should match with a very high probability (close to 100%, if not 100%).

 In the next post, we will see how the parsing approach can be improvised to address these limitations.

Discovering the hidden dimensions - Parsing

We have discussed the matching or record linking so far. I have said that if n fields from a set of records are used in matching then these records can be considered as points in an n-dimensional space.
Suppose a record has n fields to start with. Parsing is a process that splits these n fields into m fields where m > n. In other words, parsing increases the granularity in a record.
For example, a record might come in with a name field. Parsing process may generate additional fields like Title, First Name, Middle Name, Last Name Prefix, Last Name, Suffix etc.
Similarly, an address field might be split into multiple granular fields.

Let us look at the following examples (three names from a US file) first and then, we will see how parsing is done when we review records manually.

Name	Title	First Name	Middle Name	Last Name	Suffix
ROBERT CANNING		ROBERT		CANNING
MR. STUART ROGER BINNY	MR.	STUART	RODGER	BINNY
ARNOLD JONES SR.		ARNOLD		JONES	SR.

If we check the first record, we find that

1.       ROBERT is a standard given name and CANNING is a standard last name.  

2.       General convention says, last name is written after the first name.

3.       Our conclusion is ROBERT is the first name and CANNING is the last name

For the second record,

1.       We immediately identify MR. as a title, STUART and RODGER as both given names while BINNY remains unidentified.

2.       General convention says title precedes the first name and usually middle name is written in between the first name and last name.

3.       As per the general convention, the unidentified word (or token) seems to be the last name.
Two given name words follow the title; the first one is the first name while the second one is the middle name. So the entire parsing is: MR. goes in the title field, STUART in the first name field, RODGER in the middle name field and BINNY in the last name field.

As for the third record,

1.       ARNOLD is a standard given name, JONES is a standard last name and SR. is a standard name suffix.

2.       General convention says, last name follows the first name which is followed by the suffix.

3.       Our conclusion is ARNOLD is the first name and JONES is the last name and SR. is the suffix.

From these examples, we see that for name parsing, we use two rules.

1.       Initially we identify each word or token in the name as one of the name components.

2.       We also use the general convent ions of writing names.

Note both these rules are dependent on the underlying region from which names are taken.

Armed with this idea, let us see how automation can be used to do name parsing.
Let us use the following three tables for the automation.

Title MR. MRS. MS.

Given Name ROBERT STUART RODGER ARNOLD

Last Name CANNING JONES

Suffix SR. JR.

For each of the records, we evaluate the names with the above four tables and in the order in which these tables appear from left to right. We designate a token that matched to the title table by T, given name table by G, last name table by L and suffix table by S. We also use the symbol U to mark any unidentified token.

Once such evaluation is done, we get the patterns as displayed in the following table:

Name	Identified Pattern
ROBERT CANNING	GL
MR. STUART ROGER BINNY	TGGU
ARNOLD JONES SR.	GLS

Once this pattern identification is done, we require rules corresponding to each pattern to tell us how the pattern is to be parsed. This approach gives us ability to parse all the names with same pattern with one rule.
To create these rules (we need three rules for now) we require a few more symbols. Let T denote a title, F denote a first name, M denote a middle name, L denote a last name and S denote a suffix.
We now, build up the following name parsing rules using the general conventions of writing names in US:

Identified Pattern	Parsing Rule
GL	FL
TGGU	TFML
GLS	FLS

Using the four tables to identify tokens (viz. title table, given name table, last name table and the suffix table) along with the table with parsing rules and the, we can automate name parsing to generate results mentioned earlier.



For our reference, we will call the tables to identify tokens as vocabulary and the symbols used to represent the tokens matched to any such table (including U) as mask characters.
It is obvious that to be able to parse more and more names we need to correctly identify more and more tokens. That is, we need to add more entries to the tables in our vocabulary. This way, we will identify more patterns and in order to process those, we need to have more entries in our rule table.

As we discussed earlier, name parsing largely depend on the customs and conventions of writing names in the underlying region or country, we will see different name components. To give an example, we will see that many names in Mexico have last name prefix field. There are countries where we have two last name fields. Sometimes, you will encounter multiple names separated by some delimiter in the name field. For example, you might get names like MR. & MRS. CLARK. One way to handle such data issues is to break the original record into two having two different names. On both the records, we will keep the remaining information same.

We can easily use similar technique to automate address parsing or parsing of any other field.

Constructing the Survivor Record

So far, we have discussed many things about matching or record linking. At the end of this process, we get a few groups of matching records besides the bunch of non-matches.
Let us look at the following example:

Id.	Record
1	Record1
2	Record2
3	Record3
4	Record4
5	Record5
6	Record6
7	Record7
8	Record8

Suppose after matching, we see that record1, record4 and record6 are matching while record3 and record5 are matching and record2, record7 and record8 are unmatched.
This is expressed by assigning the same identifier to the matching records as in the following table:

Master Id.	Id.	Record
1	1	Record1
3	2	Record2
2	3	Record3
1	4	Record4
2	5	Record5
1	6	Record6
4	7	Record7
5	8	Record8

Now, if we are told to give the record corresponding to master id. 1, we are at a loss as we have three such records.
What we need is to have one representative record for each master id. This is a non issue in case of an unmatched record like record7 in the above table. But it is really a challenging task for the cases where we have a cluster of records under one master id. Such record is called a surviving record or survivor.
There are ways of building this survivor record corresponding to a cluster of matching records depending upon the situation or context. It is a business decision.
We will briefly discuss one such method.
Suppose records are coming in from several channels. In an environment where these records are customer records captured by a manufacturing firm, channels could be different types of POS (point of sale) or in a mass-mailing scenario, channels could be various third-party organizations etc. Let us also suppose that each record bears a time-stamp representing time date-time when it was last updated.
Let us suppose that there are fields like Name, Address, City, State, Post Code, Phone and E-Mail in a record (in reality there could be much more).

For a cluster, Name field of the survivor record will be built using a logic similar to the following example:

Use the name from the latest channel1 record (if it is not blank) or if there is no channel1 record in the cluster then take the name from the latest channel3 record (if it is not blank) else take the name from the latest record.

This way we can have rules defined for each field on the survivor record. Such rules, obviously, are business decisions and must be defined along with the users of the system.

Indirect Matching

Consider the following records:

#	Given Name	Middle Name	Last Name	St. No.	St. Name	St. Type	Apt	Cell No.	City	ZIP
1	John	Peter	Morkel	25	Main	Street	Apt 225	1234567890	Kansas	11111
2	Jon	P	Morkel	25	Main	Street	Ste 225	1212121212	Kansas	11111
3	J	P	Morkel	1750	Collins	Blvd	102	1212121212	Richardson	75068

In this case, the key-based matching we discussed earlier will declare the first two records to be a match and the last two records a match. But ideally, we want all the three records to be considered a match and they should form one cluster/group of matched records.

This can only be done by performing an indirect match according to the rule:
For any three records A, B and C; if A matches B and B matches C then A indirectly matches C.

If n fields are being used for linking records then we can consider a record to be a point in the n-dimensional space and also visualize and define a distance between two such points.

Actually, our key-based matching will consider two records to be a match provided they are close enough i.e. the distance between the records is not bigger than a predefined number.

A distance function can easily be defined for two records using the highest comparison probability returned by the match keys.
Suppose the highest comparison probability for the two records A and B be λ_AB. We can define the distance function D (A, B) = 1 – λ_AB to measure the distance between A and B.

Now, A and B will match only if D (A, B) < δ where δ ε [0, 1] is a pre-defined number.

In our example in this section, distance between the first two records and the distance between the last two records are less than the pre-defined number δ. But the distance between the first and third records is more than δ

In Data Quality in general and in record linking especially, though mathematics plays the central role, it never is the ultimate decision maker. We will see this in the example below:

#	Given Name	Middle Name	Last Name	St. No.	St. Name	St. Type	Apt	Cell No.	City	ZIP
1	John	Peter	Morkel	25	Main	Street	Apt 225	1234567890	Kansas	11111
2	J		Morkel	25	Main	Street	Ste 225	1212121212	Kansas	11111
3	Jessie		Morkel	25	Main	Street	Ste 225	1212121212	Kansas	11111

As per the rule of indirect matching, all the three records will be put under the same cluster and will be assigned the same master identifier.
But we have an issue here. Clearly, the first and the third records are not matching. Probably each of these represents the same house-hold.
So what’s the issue here? Obviously, either the first two records are not matching in reality or the last two records are not matching in reality. But unfortunately these two matches were concluded using the same logic. In fact, when we review the records manually, it is not possible to decide if the match between first two records is correct or the match between the last two records is correct.
In reality, we look for other pieces of information which could be DOB, TAX Id, SSN or any other identifier. If nothing works then we just contact the customers and find out.
Automatic matching cannot resolve situations where even manual review fails.