Showing posts with label Matching Algorithms. Show all posts
Showing posts with label Matching Algorithms. Show all posts

Sunday, June 17, 2007

Char_Instr - Another Matching Algorithm

I've using Soundex, Double Metaphone, Levenshtein Distance and other string matching algorithms, but somethings it is the simple things that work best.

Here is a function I wrote in PL/SQL utilizing the INSTR() function to traverse through one string, checking each character as to whether or not it exists in the another string.

This has been useful in checking for duplicates in mailing lists as well as identifying potential duplicates that should be reviewed. The function returns the number of characters from the second string that are the same as the first string.

I've found the use of the Soundex to be too loose and the Levenshtein Distance algorithm to be lacking in its handling of transposed characters. Use of this function will give you a count of how many chars are the same regardless of position in the string.


/*==========================================================
Function: char_instr (str1, str2)

Purpose: To check how many characters from one string

exist in another string. The return value is the number
of characters that exist in the in both strings.
==========================================================*/

FUNCTION char_instr
(
str1 IN VARCHAR2,
str2 IN VARCHAR2
)
RETURN NUMBER
AS
v_exists NUMBER := 0;
v_occurs NUMBER := 0;
v_length NUMBER;
BEGIN
/*==========================================================
Get the length of the str2
==========================================================*/
v_length := LENGTH(str2);
/*==========================================================
Loop through str2 and check if char exists in str1
=========================================================*/
IF( v_length > 0 ) THEN
FOR x IN 1..v_length LOOP
v_exists := INSTR(UPPER(str1), SUBSTR(UPPER(str2), x, 1));
IF(v_exists>0) THEN
v_occurs := v_occurs + 1;
END IF;
END LOOP;
END IF;
RETURN v_occurs;
END char_instr;
*

Wednesday, February 07, 2007

Probabilistic Matching

Probabilistic matching uses likelihood ratio theory to assign comparison outcomes to the correct, or more likely decision.

Probabilistic matching enables one to use match scores and percentages on a field by field comparison to determine a match. There are three categories output from probabilistic matching and are set by the user based on the overall probability percentage:

1) Match - that can be automatically merged
2) Candidate Match - requiring manual review
3) Non Match

Artificial Intelligence and Machine Learning utilize probabilistic matching.

Monday, January 29, 2007

Record Linkage Graphical User Interfaces

Manual handling of duplicates in a database can be quite time consuming. It is important to find the right tool to help you speed this process. Or if you are building your own record linkage tool, it is always good to see what is out there, how GUIs are laid out and what the common features are.

The Link King:















The Link King’s graphical user interface (GUI) makes record linkage and unduplication easy for beginning and advanced users. The data linking neophyte will appreciate the easy-to-follow instructions. The Link King's artificial intelligence will assist in the selection of the most appropriate linkage/unduplication protocol.

Linkage Wiz:



LinkageWiz
is a powerful data matching and record de-duplication software program used by businesses, government agencies, hospitals and other organisations in the USA, Canada, UK, Australia and France. It makes it easy to link records across multiple databases and to identify and remove duplicate records within databases
TAILOR -
TAILOR is extensible, and hence any proposed searching method, comparison function, decision model, or measurement tool can be easily plugged into the system. We have proposed three machine learning record linkage models that raise the limitations of the existing record linkage models. Our extensive experimental study, using both synthetic and real data, shows that the machine learning record linkage models outperform the probabilistic record linkage model with respect to the accuracy and the completeness metrics, the probabilistic record linkage model identifies a lesser percentage of possibly matched record pairs, both the clustering and the hybrid record linkage models are very useful, especially in the case of real applications where training sets are not available or are very expensive to obtain, and Jaro's algorithm performs better than the other comparison functions.

The following three screen snapshots are the basic screens of TAILOR graphical user interface. The first screen allows the user to either generate a synthetic experiment using DBGen, perform a real experiment on a database, or repeat a previous experiment knowing its data files. The user then uses the second screen in order to select a searching method and a comparison function and tune their required parameters. Finally, the third screen allows the user to select the decision model he would like to apply and outputs the values of the measures if the experiment is on synthetic data.

Download PDF for screenshots of TAILOR here.

MatchIT -
matchIT incorporates our proprietary matching algorithms to ensure phonetic, miskeyed and abbreviated variations of data are detected. Results can be verified using comprehensive data auditing functions, drilling down to suspect data, identifying data anomalies, and filtering garbage and salacious words.














Fuzzy Dupes 2007

Did you know that your contact database typically contains 3-10% duplicates ?

These duplicate records result in unnecessary costs when sending out printed catalogs, are aggravating to your customers, create problems in the controlling, etc. With classical methods you have no possibility to locate these duplicates in your database.




Sunday, January 28, 2007

Machine Learning and the Hidden Markov Models (HMM)

What is a Hidden Markov Model? (from Answers.com)

A hidden Markov model (HMM) is a statistical model where the system being modeled is assumed to be a Markov process with unknown parameters, and the challenge is to determine the hidden parameters from the observable parameters. The extracted model parameters can then be used to perform further analysis, for example for pattern recognition applications. A HMM can be considered as the simplest dynamic Bayesian network.

In a regular Markov model, the state is directly visible to the observer, and therefore the state transition probabilities are the only parameters. In a hidden Markov model, the state is not directly visible, but variables influenced by the state are visible. Each state has a probability distribution over the possible output tokens. Therefore the sequence of tokens generated by an HMM gives some information about the sequence of states.

Hidden Markov models are especially known for their application in temporal pattern recognition such as speech, handwriting, gesture recognition and bioinformatics.

 State transitions in a hidden Markov model (example) x — hidden states y — observable outputs a — transition probabilities b — output probabilities
State transitions in a hidden Markov model (example)
x — hidden states
y — observable outputs
a — transition probabilities
b — output probabilities

Resources:

Machine Learning Links

Record Linkage and List Quality

What is Record Linkage:

Record linkage is the task of quickly and accurately identifying records corresponding to the same entity from one or more data sources. Record linkage is also known as data cleaning, entity reconciliation or identification and the merge/purge problem. This paper presents the “standard” probabilistic record linkage model and the associated algorithm. Recent work in information retrieval, federated database systems and data mining have proposed alternatives to key components of the standard algorithm. The impact of these alternatives on the standard approach are assessed. The key question is whether and how these new alternatives are better in terms of time, accuracy and degree of automation for a particular record linkage application.


Other names that mean the same thing: entity heterogeneity, entity identification, object isomerism, instance identification, merge/purge, entity reconciliation,
list washing, match/consolidate and data cleaning. I like the term "record linkage" and will refer to it as such from this point forward in this blog.

Seems clear that if you want to be thorough in your record linkage efforts you would implement a combination of deterministic and probabilistic matching methodologies. Using a straightforward name and address match such as the Firstlogic (now Business Objects) approach will usually be sufficient if you are a list vendor or mailhouse. But if you are at all serious about identity management you will step into the deep end and implement a probabilistic matching method. I've downloaded the Ferbl open source probablistic matching tool, but have yet to experiment with it.

But whatever method you use or software package you buy, the quality of your record linkage always ends up in how good you have configured your rules. This is not an off-the-shelf solution - it requires work.

I bet most organizations "record linkage problems" could have been avoided if enough forsight and initiative had been put on the original database systems, in establishing that unique key.

Well, I guess hindsight is in fact - 20/20.

One product that definitely contributes to an increased percentage of record linkage is the SSA-NAME3 product. As you'll see from their site, they have developed this name search tool which uses probabilistic matching but factors in how common or uncommon the name is. For example matching two Jose Garcia's in the city of Los Angeles is not the same as matching two Jose Garcia's in Iceland. They are probably the same person in Iceland and most likely not, in LA.

Monday, January 15, 2007

Machine Learning and Artificial Intelligence

Machine Learning is a topic that has come up a lot during my CDI (Customer Data Integration) research. Specifically when diving into the domain of Probabilistic Matching. From the Initiate website:

Probabilistic matching

Probabilistic matching uses likelihood ratio theory to assign comparison outcomes to the correct, or more likely decision. This method leverages statistical theory and data analysis and, thus, can establish more accurate links than deterministic systems between records that have more complex typographical errors and error patterns.

Typically, probabilistic systems assign a percentage (such as 75 percent) indicating the probability of a match. Because these systems pinpoint variation and nuances to a much finer degree than a deterministic approach, they are better suited for businesses that have complex data systems with multiple databases. Due to the size of these data systems, the potential for duplicates, human error and discrepancies is far greater, making a system designed to establish links between records with complex error patterns much more effective.
Probabilistic matching enables one to use match scores and percentages on a field by field comparison to determine a match. There are three categories output from probabilistic matching and are set by the user based on the overall probability percentage:

1) Match - that can be automatically merged
2) Candidate Match - requiring manual review
3) Non Match

The topic of Machine Learning and artificial intelligence enters in with the manual review process of the candidate matches. The idea is that computer can learn from the users decisions of what was manually determined to be a match or non-match and build these into its future decisions and probability scores.

If an expert system--brilliantly designed, engineered and implemented--cannot learn not to repeat its mistakes, it is not as intelligent as a worm or a sea anemone or a kitten.
-Oliver G. Selfridge, from The Gardens of Learning.

"Find a bug in a program, and fix it, and the program will work today. Show the program how to find and fix a bug, and the program will work forever."
- Oliver G. Selfridge, in AI's Greatest Trends and Controversies

Machine learning refers to a system capable of the autonomous acquisition and integration of knowledge. This capacity to learn from experience, analytical observation, and other means, results in a system that can continuously self-improve and thereby offer increased efficiency and effectiveness.

(read full article on Machine Learning here)


Companies like Purisma and Siperian offer machine learning techniques built into their software.

A primary goal of machine learning would be to reduce the amount of manual review needed to determine matches and continuously improve the software's ability to accurately detect and consolidate duplicate records.

An open source tool that can be used for probabilistic record matching is Febrl (Freely Extensible Biomedical Record Linkage). Written in Python anyone can download this from sourceforge.net and get your feet wet with probabilistic matching.

Friday, January 05, 2007

CDI - Matching Engines

Another tip from CDI expert Jill Dyche on the subject of matching engines and whether or not to base your CDI software decision entirely on the quality of the match engine:

Here are some other things to keep in mind when assessing matching engines:

  • Test with lots of real data; compare and benchmark results. Organizations testing CDI hubs should test with as much data as possible to get a more real-world test of the system, Levy said. DataFlux's Gidley also recommends profiling data sources to assess the accuracy and completeness of data. This can help with tuning the matching engine's business rules. For example, if 50% of the phone number fields in a database are empty, it might not be a good matching attribute.
  • Consider the interface. When a system isn't sure whether records match, it generally refers the matter to a human data steward to make the call. So the interface for data stewards is an important part of a tool decision, Gidley said.
  • Think globally and futuristically. Language differences, industry-specific requirements, and future infrastructure plans -- such as moving to a service-oriented architecture -- can also affect matching engine choices, according to Dyche.
Overall, Dyche said, the matching engine should be only a part of the overall CDI tool choice.

"Matching is one of many decisions to make," Dyche said. "When we see these vendor bake-offs and companies get down to [which CDI vendor] has the most accurate match, that's still only one component of the decision."

So, in some cases, the CDI tool with the most accurate matching engine might not be the final choice. Companies must consider the big picture, including data volumes, processing speed and functional requirements, Dyche said.

CDI - Project Research

A great post about CDI project research and what you should ask yourself before diving too deep into the CDI pool covers the following:

What is the "need, pain or problem" that we're trying to solve?
What are our requirements, both from a business as well as a functional perspective?
What data sources have critical customer information in them?
What's the current system of record for customer data?
Who are the current de facto data owners in the company?
What are the ideal matching algorithms for our particular data?
What is the potential impact on existing technology architecture and systems?
How and when will data stewardship be addressed?

"Eight must-ask questions for CDI projects by Jill Dyche


Tuesday, January 02, 2007

Matching Algorithms for CDI

It generally understood that between 2%-5% of a customer database will contain undetected duplicates after a standard merge/merge routine is run. As stated in CRM Today, most merge-purge algorithms are 20 years old...

Most merge/purge processes were developed over 20 years ago and were never conceived to recognize the fluidity of movement, name change, and channels in which customers interact today. Even the most advanced de-duplication processes use character based logic and look up tables that are ill-equipped to assess the totality of a customers’ name and address permutations that accumulate through multiple customer interaction channels. These processes are easily deceived by minor variations in the name and address elements such as married/maiden, nick names, typos, and mis-keys. A typical file will contain 2 to 5% unidentified duplicate customers after a standard merge/purge process.
Instead of the common approach of only using one matching algorithm (I am guilty of this one) modern approaches are utilizing many algorithms to isolate duplicate records.
No single algorithm can efficiently and effectively power a matching technology due to the multiple culprits of customer identity and data quality error. Advanced solutions incorporate not one, but several advanced matching algorithms, each designed to group records into temporal data sets for the purpose of bringing visibility to distinct patterns of repetitious error. Once patterns of error are identified, the records can be referenced to consumer data sources, allowing for the remediation of the error and recognition of the true identity of the customer.
An integral part of any CDI product is its matching capability. Match rules will vary from organization to organization so using a standard template or built-in rules usually will not suffice if you want thorough duplicate detection and handling.

Firstlogic (now Business Objects) has a sophisticated match engine and beyond the standard match capabilities are "Extended Matching" which allows the user to set up custom rules for different match scenarios. I believe that simply using rule based matching you can solve 80% of your data consolidation issues.

Companies like Purisma or Siperian offer much more sophisticated match engines that utilize match clusters and larger "match footprints" which ease the process, but for the most part, if you know what you are trying to do, any rule based matching engine will do. And remember:
"The computer is no better than the organization that feeds it." - L. Ron Hubbard
The moral is first work out all your match rules and then see if you can solve your problems using your existing match engine software before looking elsewhere to solve these match related problems.