System and Method for Matching Data Using Probabilistic Modeling Techniques

• US 20140052688A1
• Filed: 08/16/2013
• Published: 02/20/2014
• Est. Priority Date: 08/17/2012
• Status: Abandoned Application

• Current Assignee: Opera Solutions U.S.A., Llc
• Original Assignee: Opera Solutions, LLC.
• Inventors: Bansal, Shubh
• Application Number:
  US13/969,010
• Publication Number:
  US 20140052688A1
• Time in Patent Office: Days
• US Class Current: 706/52
• CPC Class Codes: G06N 7/02 using fuzzy logic computing arrangements based on biological models G06N3/00; computing arrangements using knowledge-based models G06N5/00

Abstract

A system and method for matching data using probabilistic modeling techniques is provided. The system includes a computer system and a data matching model/engine. The present invention precisely and automatically matches and identifies entities from approximately matching short string text (e.g., company names, product names, addresses, etc.) by pre-processing datasets using a near-exact matching model and a fingerprint matching model, and then applying a fuzzy text matching model. More specifically, the fuzzy text matching model applies an Inverse Document Frequency function to a simple data entry model and combines this with one or more unintentional error metrics/measures and/or intentional spelling variation metrics/measures through a probabilistic model. The system can be autonomous and robust, and allow for variations and errors in text, while appropriately penalizing the similarity score, thus allowing dataset linking through text columns.

Claims

1. A system for matching data comprising:

a computer system for electronically receiving a dataset;

a near-exact matching model, executed by the computer system, which pre-processes the dataset to generate a plurality of text strings and compares the text strings to identify matching data in the dataset;

a fingerprint matching model, executed by the computer system, which converts each entry of the dataset into a corresponding text fingerprint and compares resultant text fingerprints to identify matching data in the dataset; and

a fuzzy text matching model, executed by the computer system, which applies probabilistic modeling techniques to the dataset to identify matching data in the dataset,

wherein the system transmits the matching data to a user.

2. The system of claim 1, wherein the dataset comprises short string text.

3. The system of claim 1, wherein the near-exact matching model removes all non alpha-numeric characters and sets every remaining character to lowercase.

4. The system of claim 1, wherein the fingerprint matching model applies a key collision method of clustering to the dataset.

5. The system of claim 1, wherein the system removes all matches detected by the near-exact matching model and the fingerprint matching model prior to executing the fuzzy text matching model.

6. The system of claim 1, wherein the probabilistic modeling techniques applied by the fuzzy text matching model include at least one of:

developing a simple probabilistic model;

applying an inverse document frequency function to vary the likelihood of token deletion;

applying one or more token similarity metrics to calculate token misspelling match probabilities; and

generalizing the fuzzy text matching model for token misspellings.

7. The system of claim 6, wherein the one or more token similarity metrics includes one or more unintentional errors metrics.

8. The system of claim 7, wherein the one or more unintentional errors metrics includes at least one of Longest Common Subsequence metrics, Jaro Winkler Distance Metrics, or Levenshtein Edit Distance Metrics.

9. The system of claim 6, wherein the one or more token similarity metrics includes one or more intentional spelling variations metrics.

10. The system of claim 9, wherein the one or more intentional variation metrics includes at least one of a soundex algorithm or a double metaphone algorithm.

11. A method for matching data comprising the steps of:

electronically receiving a dataset at a computer system;

executing on the computer system a near-exact matching model which pre-processes the dataset to generate a plurality of text strings and compares the text strings to identify matching data in the dataset;

executing on the computer system a fingerprint matching model, executed by the computer system, which converts each entry of the dataset into a corresponding text fingerprint and compares resultant text fingerprints to identify matching data in the dataset;

executing on the computer system a fuzzy text matching model which applies probabilistic modeling techniques to the dataset to identify matching data in the dataset; and

transmitting any matching data identified by the system to a user.

12. The method of claim 11, wherein the dataset comprises short string text.

13. The method of claim 11, wherein the near-exact matching model removes all non alpha-numeric characters and sets every remaining character to lowercase.

14. The method of claim 11, wherein the fingerprint matching model applies a key collision method of clustering to the dataset.

15. The method of claim 11, further comprising removing all matches detected by the near-exact matching model and the fingerprint matching model before executing the fuzzy text matching model.

16. The method of claim 11, wherein the probabilistic modeling techniques applied by the fuzzy text matching model include at least one of:

developing a simple probabilistic model;

applying an inverse document frequency function to vary the likelihood of token deletion;

applying one or more token similarity metrics to calculate token misspelling match probabilities; and

generalizing the fuzzy text matching model for token misspellings.

17. The method of claim 16, wherein the one or more token similarity metrics includes one or more unintentional errors metrics.

18. The method of claim 17, wherein the one or more unintentional errors metrics includes at least one of Longest Common Subsequence metrics, Jaro Winkler Distance Metrics, or Levenshtein Edit Distance Metrics.

19. The method of claim 16, wherein the one or more token similarity metrics includes one or more intentional spelling variations metrics.

20. The method of claim 19, wherein the one or more intentional variation metrics includes at least one of a soundex algorithm or a double metaphone algorithm.

21. A computer-readable medium having computer-readable instructions stored thereon which, when executed by a computer system, cause the computer system to perform the steps of:

electronically receiving a dataset at the computer system;

executing on the computer system a near-exact matching model which pre-processes the dataset to generate a plurality of text strings and compares the text strings to identify matching data in the dataset;

executing on the computer system a fingerprint matching model which converts each entry of the dataset into a corresponding text fingerprint and compares resultant text fingerprints to identify matching data in the dataset;

executing on the computer system a fuzzy text matching model which applies probabilistic modeling techniques to the dataset to identify matching data in the dataset; and

transmitting any matching data identified by the system to a user.

22. The computer-readable medium of claim 21, wherein the dataset comprises short string text.

23. The computer-readable medium of claim 21, wherein the near-exact matching model removes all non alpha-numeric characters and sets every remaining character to lowercase.

24. The computer-readable medium of claim 21, wherein the fingerprint matching model applies a key collision method of clustering to the dataset.

25. The computer-readable medium of claim 21, further comprising removing all matches detected by the near-exact matching model and the fingerprint matching model before executing the fuzzy text matching model.

26. The computer-readable medium of claim 21, wherein the probabilistic modeling techniques applied by the fuzzy text matching model include at least one of:

developing a simple probabilistic model;

applying an inverse document frequency function to vary the likelihood of token deletion;

applying one or more token similarity metrics to calculate token misspelling match probabilities; and

generalizing the fuzzy text matching model for token misspellings.

27. The computer-readable medium of claim 26, wherein the one or more token similarity metrics includes one or more unintentional errors metrics.

28. The computer-readable medium of claim 27, wherein the one or more unintentional errors metrics includes at least one of Longest Common Subsequence Metrics, Jaro Winkler Distance Metrics, or Levenshtein Edit Distance Metrics.

29. The computer-readable medium of claim 26, wherein the one or more token similarity metrics includes one or more intentional spelling variations metrics.

30. The computer-readable medium of claim 29, wherein the one or more intentional variation metrics includes at least one of a soundex algorithm or a double metaphone algorithm.

31. A method for matching data comprising the steps of:

electronically receiving a dataset at a computer system;

executing on the computer system a fuzzy text matching model which applies probabilistic modeling techniques to the dataset to identify matching data in the dataset; and

transmitting any matching data identified by the system to a user.

32. The method of claim 31, further comprising executing by the computer system a near-exact matching model which pre-processes the dataset to generate a plurality of text strings and compares the text strings to identify matching data in the dataset.

33. The method of claim 31, further comprising executing by the computer system a fingerprint matching model which converts each entry of the dataset into a corresponding text fingerprint and compares resultant text fingerprints to identify matching data in the dataset;

34. The method of claim 31, wherein the dataset comprises short string text.

35. The method of claim 31, wherein the probabilistic modeling techniques applied by the fuzzy text matching model include at least one of:

developing a simple probabilistic model;

applying an inverse document frequency function to vary the likelihood of token deletion;

applying one or more token similarity metrics to calculate token misspelling match probabilities; and

generalizing the fuzzy text matching model for token misspellings.

36. The method of claim 35, wherein the one or more token similarity metrics includes one or more unintentional errors metrics.

37. The method of claim 36, wherein the one or more unintentional errors metrics includes at least one of Longest Common Subsequence metrics, Jaro Winkler Distance Metrics, or Levenshtein Edit Distance Metrics.

38. The method of claim 35, wherein the one or more token similarity metrics includes one or more intentional spelling variations metrics.

39. The method of claim 38, wherein the one or more intentional variation metrics includes at least one of a soundex algorithm or a double metaphone algorithm.