System and method for using a statistical classifier to score contact entities

• US 9,646,246 B2
• Filed: 02/21/2013
• Issued: 05/09/2017
• Est. Priority Date: 02/24/2011
• Status: Active Grant

• Current Assignee: Salesforce.com, Inc.
• Original Assignee: Salesforce.com, Inc.
• Inventors: Jagota, Arun Kumar
• Primary Examiner(s): Spieler, William
• Application Number:
  US13/773,141
• Publication Number:
  US 20130166489A1
• Time in Patent Office: 1,538 Days
• Field of Search: 707755, 707756
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: G06N 5/02 Knowledge representation; Symbolic representation
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising

Abstract

A system and method for associating a character string with one or more defined entities of a contact record. An input character string is received. The string is first evaluated to see if the structure of the string is recognized. If not, then the string is compared to entries in a look up table. If the string format is not recognized, and the string is not found in the look up table, then a posterior probability is calculated for a set of defined entities over a limited set of string processing features. The result of probabilistic scoring determines which of the defined entities to associate with the character string.

Claims

1. A method for associating an entity of a contact with a character string, wherein a database stores a plurality of contacts, and each contact has a defined set of entities, comprising:

determining, for a first subgroup of the defined set of entities, using a processor, whether the character string comprises a structure associated with the first subgroup of the defined set of entities, prior to any probabilistic approximation, wherein the structure comprises at least one character other than alphanumeric characters;

replacing all numerical digits in the character string with a corresponding digit placeholder to generate a blurred character string in response to a determination that the character string does not comprise the structure associated with the first subgroup; and

determining, for a second subgroup of the defined set of entities, using a processor, a probabilistic approximation that the blurred character string is associated with at least one of the defined set of entities in the second subgroup by scoring the blurred character string for each of the defined set of entities associated with the blurred character string; and

identifying the character string as one of the set of defined entities having a highest score that satisfies a predetermined score threshold.

2. The method of claim 1, wherein the step of evaluating whether the character string comprises the structure further comprises matching the character string to a known entity structure with a probability higher than a predetermined threshold.

3. The method of claim 1, wherein the step of evaluating whether the character string comprises the structure further comprises comparing the character string to known entity entries in a table to detect a match with a near certainty.

4. The method of claim 1, wherein the step of evaluating a probabilistic approximation further comprises calculating a posterior probability over a limited set of character string features.

5. The method of claim 4, wherein the limited set of character string features include a last-word feature, a digit-blurring feature, a words feature, a full-string feature, and an address-line feature.

6. The method of claim 5, in response to the character string being evaluated to not comprise the structure, further comprising applying the full-string feature, the digit-blurring feature, the last-word feature, the address-line feature, and the word feature to determine if the character string is associated with one of the entities of the second subgroup.

7. A method for identifying entities of a contact associated with a character string, comprising:

receiving a character string;

determining whether the character string comprises a structure associated with a first defined entity, prior to any probabilistic approximation, wherein the structure comprises at least one character other than alphanumeric characters;

determining whether the character string is found in a look up table in response to an evaluation that the character string does not comprise the structure associated with the first defined entity;

replacing all numerical digits in the character string with a corresponding digit placeholder to generate a blurred character string in response to a determination that the character string is not found in the look up table;

calculating, based on the blurred character string, a posterior probability to generate a score for each of a set of defined entities, and

identifying the character string as one of the set of defined entities having a highest score that satisfies a predetermined score threshold.

8. The method of claim 7, the step of calculating a posterior probability further comprising:

first evaluating a full string feature applied to the character string;

then evaluating a digit blurring feature applied to the character string;

then evaluating a last word feature applied to the character string;

then evaluating an address line feature applied to the character string; and

then evaluating a word feature applied to the character string.

9. The method of claim 8, wherein the step of evaluating a full string feature further comprises calculating a posterior probability for all entities around the full string feature when an instance of a first defined entity meeting the full string feature is found in a training set, wherein when the posterior probability is higher than a full string threshold, the character string is determined to be the first defined entity.

10. The method of claim 8, wherein the step of evaluating a digit blurring feature further comprises calculating a posterior probability for all entities around the digit blurring feature when an instance of a second defined entity meeting the digit blurring feature is found in a training set, wherein when the posterior probability is higher than a digit blurring threshold, the character string is determined to be the second defined entity.

11. The method of claim 8, wherein the step of evaluating a last word feature further comprises calculating a posterior probability for all entities around the last word feature, wherein selected values of the posterior probability indicate that the entity is company name.

12. The method of claim 8, wherein the step of evaluating an address line feature further comprises calculating a posterior probability for all entities around the address line feature, wherein selected values of the posterior probability indicate that the entity is address line.

13. The method of claim 8, wherein the step of evaluating a word feature further comprises calculating a posterior probability for all entities around the word feature, wherein selected values of the posterior probability indicate that the entity is first name.

14. The method of claim 7, wherein the step of calculating a posterior probability further comprises:

evaluating a full string feature of the character string, and if an instance of a first defined entity meeting the full string feature is found in a training set, then calculating a posterior probability for all entities around the full string feature, wherein if the posterior probability is higher than a full string threshold, the character string is determined to be the first defined entity, and if not;

evaluating a digit blurring feature of the character string, and if an instance of a second defined entity meeting the digit blurring feature is found in the training set, then calculate a posterior probability for all entities around the digit blurring feature, wherein if the posterior probability is higher than a digit blurring threshold, the character string is determined to be the second defined entity, and if not;

calculating a posterior probability for all entities around a last word feature, wherein if the posterior probability is higher than a last word threshold, the character string is determined to be a third defined entity, and if not;

calculating a posterior probability for all entities around an address line feature, wherein if the posterior probability is higher than an address line threshold, the character string is determined to be a fourth defined entity, and if not;

calculating a posterior probability for all entities around a first name feature, wherein if the posterior probability is higher than a first name threshold, the character string is determined to be a fifth defined entity, and if not the character string is likely an eighth defined entity.

15. A non-transitory computer-readable medium encoded with instruction for identifying entities of a contact associated with a character string, the instructions when executed by a processor comprise the steps of:

receiving a character string;

evaluating whether the character string comprises a structure associated with a first defined entity, prior to any probabilistic approximation, wherein the structure comprises at least one character other than alphanumeric characters;

evaluating whether the character string is found in a look up table in response to an evaluation that the character string does not comprise the structure associated with the first defined entity;

replacing all numerical digits in the character string with a corresponding digit placeholder to generate a blurred character string in response to a determination that the character string is not found in the look up table;

calculating, based on the blurred character string, a posterior probability to generate a score for each of a set of defined entities; and

identifying the character string as one entity of the set of defined entities having a highest score that satisfies a predetermined score threshold.

16. The computer-readable medium of claim 15, the step of calculating a posterior probability further comprising:

first evaluating a full string feature applied to the character string;

then evaluating a digit blurring feature applied to the character string;

then evaluating a last word feature applied to the character string;

then evaluating an address line feature applied to the character string; and

then evaluating a word feature applied to the character string.

17. The computer-readable medium of claim 16, wherein the step of evaluating a full string feature further comprises calculating a posterior probability for all entities around the full string feature when an instance of a first defined entity meeting the full string feature is found in a training set, wherein when the posterior probability is higher than a full string threshold, the character string is determined to be the first defined entity.

18. The computer-readable medium of claim 16, wherein the step of evaluating a digit blurring feature further comprises calculating a posterior probability for all entities around the digit blurring feature when an instance of a second defined entity meeting the digit blurring feature is found in a training set, wherein when the posterior probability is higher than a digit blurring threshold, the character string is determined to be the second defined entity.

19. The computer-readable medium of claim 16, wherein the step of evaluating a last word feature further comprises calculating a posterior probability for all entities around the last word feature, wherein selected values of the posterior probability indicate that the entity is company name.

20. The computer-readable medium of claim 16, wherein the step of evaluating an address line feature further comprises calculating a posterior probability for all entities around the address line feature, wherein selected values of the posterior probability indicate that the entity is address line.

21. The computer-readable medium of claim 16, wherein the step of evaluating a word feature further comprises calculating a posterior probability for all entities around the word feature, wherein selected values of the posterior probability indicate that the entity is first name.

22. The computer-readable medium of claim 15, the step of calculating a posterior probability further comprising:

evaluating a full string feature of the character string, and if an instance of a first defined entity meeting the full string feature is found in a training set, then calculating a posterior probability for all entities around the full string feature, wherein if the posterior probability is higher than a full string threshold, the character string is determined to be the first defined entity, and if not;

evaluating a digit blurring feature of the character string, and if an instance of a second defined entity meeting the digit blurring feature is found in the training set, then calculate a posterior probability for all entities around the digit blurring feature, wherein if the posterior probability is higher than a digit blurring threshold, the character string is determined to be the second defined entity, and if not;

calculating a posterior probability for all entities around a last word feature, wherein if the posterior probability is higher than a last word threshold, the character string is determined to be a third defined entity, and if not;

calculating a posterior probability for all entities around an address line feature, wherein if the posterior probability is higher than an address line threshold, the character string is determined to be a fourth defined entity, and if not;

calculating a posterior probability for all entities around a first name feature, wherein if the posterior probability is higher than a first name threshold, the character string is determined to be a fifth defined entity, and if not the character string is likely an eighth defined entity.

23. An apparatus for identifying entities of a contact associated with a character string, comprising:

a processor; and

one or more stored sequences of instructions which, when executed by the processor, cause the processor to carry out the steps of;

receiving a character string;

evaluating the character string first for structure, without calculating any posterior probability, wherein the structure comprises at least one character other than alphanumeric characters, then evaluating the character string as a look up, and

replacing all numerical digits in the character string with a corresponding digit placeholder to generate a blurred character string in response to a determination that the character string does not comprise structure and is not found in the look up table;

calculating, based on the blurred character string, a posterior probability to generate a score for each of a set of defined entities; and

identifying the character string as one entity of the set of defined entities having a highest score that satisfies a predetermined score threshold.