Merging two data sets vertically is sometimes called a data append. Usually when a vertical merge works best is when we have two datasets with the same columns, in the same order, and we just stack one dataset on top of the other. The resulting dataset may require duplication identification and purging of the duplicate data. Traditionally, for example in a relational database environment, vertical merging requires that both datasets have the same columns, or else there will be null values. Here is an example of a vertical merge between Dataset 1 and Dataset 2.

Dataset 1:

Dataset 2:

The vertically merged dataset is shown here:

The task following a vertical merge is to identify whether Laura Hartley on row 3 is the same Laura Hartley on row 6. If these two people are the same, we may wish to remove one of the rows so that we do not have a duplicate. However, it may not be obvious at first which row is the correct one to keep, since these two entities show different ages, but the same street address. Is Laura 18 or is she 20? Depending on our goals, we may want to merge the data first and remove duplicates second, or we may want to identify duplicates before creating the merged dataset. Or, we may wish to leave both records in, and somehow identify or tag them as being possible duplicates. Different strategies will work for different datasets and different problem domains.

A horizontal merge is used when we have datasets that represent the same type of entity, but we have different attributes that describe each one. In this case, a vertical merge will not work because there are too many attributes in one dataset that are not in the other one. Here is an example. Notice that there are some attributes in Dataset 1 that do not appear in Dataset 2.

Dataset 1:

Dataset 2:

This problem definitely requires entity matching and consolidation. Ideally, we will end up with a dataset that has the attributes from both datasets, and one row for each entity, like the following horizontally merged dataset:

Horizontal merging does not require that both datasets have all the same columns, but there should be something to match on, in order to ensure that we have only one row per entity. In this example case, the Name column is unique and serves as the column in common between the two sets. However, in a real entity matching scenario, we may not be so lucky. Columns may have to be split, transformed, combined, adjusted, or otherwise tweaked in order to find a match.

This method has some strengths in that it is quite flexible and can be used on many different types of data. However, as we learned in Chapter 2, Association Rule Mining, any time we need to perform pairwise comparisons, we are looking at a very large number of possible combinations. This means we need to take pains to reduce the set of possible matches, and we may need to use persistent storage (as we did in Chapter 2, Association Rule Mining) to remember the comparisons we have already made in the past.

Another interesting feature of attribute-based similarity matching is that very rare values can be leveraged to increase accuracy of the match. In other words, it is easier to find a match between two entities with very rare values, than it is to match entities with common values. We can use this knowledge to adjust the probability of matching entities based on the rarity or commonness of the attribute values. A common illustration of this idea given by geneticist Howard Newcombe in a 1959 Science paper (Automatic Linkage of Vital Records), and expanded in later highly-cited papers (such as Winkler's The State of Record Linkage and Current Research Problems) is to compare the ease of matching entities where there is a rare first and last name with the difficulty of matching a common name. For example, it will be easier to match two entities with the name Finklestein McGlockenspiel, which is a very rare name in English-speaking countries. It will be relatively difficult to match people who have a common name, for example John Smith.

When working with numeric values or dates, close enough could be indicated by setting a range or a distance from the target. For example, in some domain dealing with age, we may declare any value in the low 40s is good enough to match the age 43. In another domain, we may decide that the eye colors green and hazel are close enough to be counted as matching. The rules governing this type of rule-based proximity matching will often depend on the domain and the goals of the problem.

Measuring the approximate equality of two strings is a very interesting exercise. How close are the names Jones and James?

There are a number of basic string metrics that can quantify the amount of edit distance between two strings. The edit distance is the number of edits that would transform one string into another. Two commonly-used methods for measuring the edit distance between two strings are the Hamming distance and the Levenshtein distance.

For strings of equal length, the Hamming distance is a measure of the number of character substitutions needed to turn one string into the other. The Hamming distance between blue and glue is 1, since there is only a single edit needed to change the b character to a g. The Hamming distance is not designed for strings of different lengths, so we can pad the shorter word with dummy characters to account for this problem. To get the Hamming distance between cat and catch, we can turn cat into cat**, which has a Hamming distance of 2 from catch.

For any two strings, the Levenshtein distance is a measure of the minimum number of substitutions, deletions, or insertions required to change one string into another. The Levenshtein distance between blue and glue is also 1. And the Levenshtein distance between cat and catch is 2, since there are two additions, zero deletions, and zero changes. The Levenshtein distance between catch and cap is 3, since there are two deletions and one substitution. The Hamming distance between catch and cap is also 3, using the padding method described previously.

Do Hamming and Levenshtein always return the same value? No. Since the Hamming distance does not allow for insertions or deletions, sometimes it requires more actions than Levenshtein. Consider the strings scat and cats. The Hamming distance is 4 since this transformation requires the following substitutions: s changes to c, c changes to a, a changes to t, and t changes to s. The Levenshtein distance between scat and cats is only 2: delete s from the first position, insert s at the final position. So while the Hamming distance has the potential to be greater than the Levenshtein distance, the Hamming distance is less complicated, and easier to estimate than Levenshtein.

There are many other variations on edit distance calculation, and different techniques will work in different scenarios. Does your data only have strings of the same length? Do you need to handle fuzzy (approximate) string matches, or are you more interested in exact string matches? No matter what technique we choose, we must remember that for this chapter, our overarching goal is matching entities, and the purpose of the string metrics is to determine how similar the string attributes are between some pair of entities. Knowing how similar these string attributes are is just one additional clue as to how similar the entities are. Are there other ways of measuring the similarity of strings?

Invented in 1918, Soundex is another rudimentary technique for measuring how similar two strings are to each other. But, just as its name suggests, Soundex is a measure of how phonetically similar the strings are. Soundex only works with English pronunciations. With Soundex, each word can be encoded into a character sequence, for example a traditional four-character Soundex algorithm encodes the name Peters as P362. The encoding rules are fairly simple. The first letter of a word is retained as the first letter of the new code. Subsequent vowels are ignored, along with the letters W, Y, and H. Consonants are assigned numbers in groups, chosen from a list as follows:

Smith thus becomes S530. The first letter S is retained, the M becomes a 5, the I is dropped, the T becomes a 3, and the H is dropped. A 0 character is added to pad the code to four characters. Smythe also becomes S530. The first letter S is retained, the M becomes a 5, the Y is dropped, the T becomes a 3, the H is dropped, and the E is dropped.

James becomes J520. The first letter J is retained, the M becomes a 5, the S becomes a 2, and the vowels A and E are dropped. Since M and N are both in the same group, the code for James and Jones are exactly the same.

Consider a longer word, such as Ellington. Its code will be E452. Here we retain the E as the starting letter, substitute 4 for the letter L, drop the second 4 representing the second letter L, drop the I, substitute 5 for N, substitute 2 for G, substitute 3 for T, drop the O, and substitute 5 for the final N. Drop any digits that follow the first four characters. The result for Ellington is E452.

For our purposes, calculating the Soundex of strings is just another way to prepare data so that we can compare values. We are seeking entity matches, and, depending on the data we have, a Soundex comparison between two strings may be a very useful determinant of similarity. Another good application for Soundex is to use it to narrow down which strings should be compared. Rather than performing pairwise comparisons on every pair of strings in a database, we may find efficiency gains by only comparing pairs of strings that have similar Soundex codes.

Both edit distances and Soundex can be used in an entity matching scenario where we are trying to use the attributes of each entity as the matching criteria. But what happens when we do not have enough attributes, or where the attributes are different across our different sets of entities?

How long it takes to execute the entity matching exercise, called its execution time or runtime, is a critically important factor in choosing and evaluating an entity matching strategy. Without taking specific precautions to reduce the size of the sets being compared, the bulk of the execution time will likely be spent doing pairwise comparisons. This is a similar situation to where we found ourselves in Chapter 2, Association Rule Mining when finding frequent itemsets. Just like with the frequent itemset generation, we need to put some concerted effort into finding ways to limit the number of comparisons we have to make. Herman Wells is not likely the same person as Edward White, so we should not waste time comparing them, but Herman Wells and Harmon Walls might be the same person after all.

The good news is that we have many strategies for reducing the size of the lists of pairs that have to be compared. Numeric ranges, date ranges, string edit distances, and Soundex were mentioned earlier as very simple ways of reducing the number of comparisons. In the research literature, these techniques - and many, many more - are called blocking methods. A good blocking method will reduce the number of possible comparisons just enough to impact efficiency in a positive way, but will not reduce the comparisons to the point that it is impossible to find a match.

Aside from blocking to reduce the number of entities to be compared, we also want to reduce the number of attributes that need to be compared, as well as the number and complexity of the comparisons in the procedure overall. A matching task that relies on a single, simple numeric test will be more efficient than a matcher that relies on a half-dozen blockers and complicated string matches.

Assuming that our procedure manages to propose some candidate matches, how do we know they are correct? We would like entities that are the same to be correctly matched (true positives), entities that are not the same to remain unmatched (true negatives), and we would like to minimize both types of incorrectly matched entities (false positives and false negatives).

We can measure the effectiveness of our procedure with classical information retrieval terms: accuracy, precision, recall, and specificity. Precision is the number of correct guesses (true positives) divided by the number of guesses that we proposed. Our proposals are comprised of both true positives and false positives.

Recall is the number of correct guesses (true positives) divided by the total number of actual matches. The total number of actual matches is comprised of both true positives and false negatives.

Accuracy is simply the number of correct guesses divided by the total number of all guesses. Specificity is the actual negatives divided by the sum of the guessed negatives and the actual negatives.

To clarify these important concepts, an example is probably in order. Consider the following table showing various proposed entity matches and the result given by our (fictitious) matching procedure. The right-most column shows whether the proposed match was a true positive, true negative, false positive, or false negative:

In this example, we got six guesses correct out of 10 possible, for an overall accuracy of 6/10 or .60. The specificity of our method is calculated as two true negatives divided by four total negatives, which yields 2/4 or .50.

We can calculate precision as follows:

precision = tp/(tp+fp)
precision = 4/(4+1)
precision = 4/5 = .80

A perfect precision score of 1.0 means that there were no false positives, which is good, but precision does not take into account false negatives.

Recall, on the other hand, does take into account false negatives. We can calculate recall as follows:

recall = tp/(tp+fn)
recall = 4/(4+2)
recall = 4/6 = 2/3 = .66

A perfect recall score of 1.0 means that there were no false negatives, which is also good, although it does not take into account false positives like precision did.

The F-measure, abbreviated as F1, takes both precision and recall into account, producing the harmonic mean of the two:

f1 = 2((precision * recall) / (precision + recall))
f1 = 2((.8*.66) / (.8 + .66))
f1 = .72

These measures, accuracy, precision, recall, specificity, and F-measure, can be used to compare two classification procedures, such as entity match procedures, to each other. With these, we are able to determine which procedure produces results with the highest values.

It is worth remembering at this point that in order to calculate these values, we have to know whether the class we chose (is a match, is not a match) is actually correct. This means one of two things will need to happen: if we have a small enough set of matched entities, we will need to be able to check them by hand to see whether they are correct, or if we have a large set of matches, we will need to practice by using a test set in which we have pre-coded the correct results.

Ideally, a matching procedure will be efficient, effective, and practical. What do we mean by practical? A practical procedure will be both generalizable and composed of minimal manual steps. Generalizable means that the entity matching procedure is broadly applicable to many situations. These various situations could include different domains, different times, or different systems. For example, if we design a procedure that matches person entities based on names, but we use a dataset comprised of book characters from Victorian fiction, it might work well for a particular academic project, but probably will not be of much use to a global social media platform in 2016. Similarly, a procedure designed for a niche test scenario may not be easily applied to real-world data. It is not always required that a procedure be generalizable to every possible situation, but we need to at least acknowledge in advance the likely boundaries of the thing we are designing.

Additionally, if the procedure we design has a lot of manual steps, it may not be practical to expect that using the procedure is sustainable into the future, as it will be very time-consuming and tedious. While manual procedures may promise higher accuracy, the time it takes to do the manual work does threaten overall the efficiency of a matching procedure. Even in a machine learning scenario, we should take into account whether or not the training sets are being constructed manually, and how long this takes. To increase efficiency, it is tempting to try to automate manual procedures. However, automation of a manual process can result in higher errors, which will defeat any gains made in accuracy. Correcting those errors then leads to less efficiency. As with many things in life, it seems like there is always a tradeoff!

At this point, we have considered different strategies for finding matching entities, and we have learned how to evaluate the matches we found. It is time to put our learning into practice with a real-world application.