Method and system for performing phrase/word clustering and cluster merging

• US 7,519,590 B2
• Filed: 06/09/2003
• Issued: 04/14/2009
• Est. Priority Date: 06/28/2000
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Chandrasekar, Raman, Steinkraus, David W.
• Primary Examiner(s): AL HASHEMI, SANA A
• Application Number:
  US10/457,686
• Publication Number:
  US 20030200198A1
• Time in Patent Office: 2,136 Days
• Field of Search: 707/100, 707/102, 707/104.1, 707/10, 707/2, 707 3- 6, 707/8, 704/240, 704/9, 704/245, 706/934, 715/532, 715/513
• US Class Current: 1/1
• CPC Class Codes: G06F 16/30 of unstructured textual data document management systems G06F16/93
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database

Abstract

Text classification has become an important aspect of information technology. Present text classification techniques range from simple text matching to more complex clustering methods. Clustering describes a process of discovering structure in a collection of characters. The invention automatically analyzes a text string and either updates an existing cluster or creates a new cluster. To that end, the invention may use a character n-gram matching process in addition to other heuristic-based clustering techniques. In the character n-gram matching process, each text string is first normalized using several heuristics. It is then divided into a set of overlapping character n-grams, where n is the number of adjacent characters. If the commonality between the text string and the existing cluster members satisfies a pre-defined threshold, the text string is added to the cluster. If, on the other hand, the commonality does not satisfy the pre-defined threshold, a new cluster may be created. Each cluster may have a selected topic name. The topic name allows whole clusters to be compared in a similar way to the individual clusters, and merged when a predetermined level of commonality exists between the subject clusters. The topic name also may be used as a suggested alternative to the text string. In this instance, the topic name of the cluster to which the text string was added may be outputted as an alternative to the text string.

Claims

1. A method for classifying character strings, comprising:

receiving at least one character string, wherein each character string comprises a word or a phrase;

clustering a first character string with another character string into a first group, when said first character string satisfies a predetermined degree of commonality with said another character string; and

selecting at least one of said character strings in each of said groups to be a topic.

2. The method of claim 1, further comprising creating another group when said first character string does not satisfy said predetermined level of commonality with said another character string.

3. The method of claim 1, further comprising outputting said topic.

4. The method of claim 1, wherein said selecting of said topic is a function of a frequency of said character strings within said group.

5. The method of claim 1, wherein said topic is a predetermined selection of at least one of said character strings.

6. The method of claim 1, further comprising segmenting said first character string into a first plurality of character sets and said another character string into another plurality of character sets, and comparing said first plurality of character sets with said another plurality of character sets.

7. The method of claim 6, wherein each of said character sets comprise more than one adjacent characters of said character string.

8. A system for classifying character strings, comprising:

an input device for receiving at least one character string;

a clustering component for placing a first character string with another character string into a group, when said first character string satisfies a predetermined degree of commonality with said another character string; and

a selection component for selecting at least one of said character strings in each of said groups to be a topic.

9. The system of claim 8, further comprising a database for storing said groups.

10. The system of claim 8, wherein said clustering component creates another group when said first character string does not satisfy said predetermined level of commonality with said another character string.

11. The system of claim 8, further comprising an output component for outputting said topic.

12. The system of claim 8, wherein said selection component selects said topic based on a frequency of said character strings within said group.

13. The system of claim 8, wherein said clustering component further segments said first character string into a first plurality of character sets and said another character string into another plurality of character sets, and compares said first plurality of character sets with said another plurality of character sets.

14. The system of claim 13, wherein each of said character sets comprise more than one adjacent characters of said character string.

15. A computer-readable medium having computer-executable instructions for steps comprising:

receiving at least one character string, wherein each character string comprises a word or a phrase;

clustering a first character string with another character string into a first group, when said first character string satisfies a predetermined degree of commonality with said another character string; and

selecting at least one of said character strings in each of said groups to be a topic.

16. The computer-readable medium of claim 15, having further computer-executable instructions for performing the steps of creating another group when said first character string does not satisfy said predetermined level of commonality with said another character string.

17. The computer-readable medium of claim 15, having further computer-executable instructions for performing the steps of outputting said topic.

18. The computer-readable medium of claim 15, wherein said step of selecting said topic is based on a frequency of said character strings.

19. The computer-readable medium of claim 15, having further computer-executable instructions for performing the steps of segmenting said first character string into a first plurality of character sets and said another character string into another plurality of character sets, and comparing said first plurality of character sets with said another plurality of character sets.

20. The computer-readable medium of claim 19, wherein each of said character sets comprise more than one adjacent characters of said character string.

21. A method for suggesting alternative words or phrases, comprising:

receiving a first word or phrase;

creating a cluster of said first word or phrase with another word or phrase; and

outputting a topic, wherein said topic is at least one of said words or phrases that satisfy a predetermined criteria.

22. The method of claim 21, wherein said predetermined criteria is a function of a frequency of occurrence of said topic within said cluster.

23. The method of claim 21, wherein said topic is a pre-selected word or phrase.

24. A method for searching a database, comprising:

receiving a first word or phrase;

clustering said first word or phrase with another word or phrase; and

searching said database for a topic, wherein said topic is at least one of said words or phrases that satisfy a predetermined criteria.

25. The method of claim 24, wherein said predetermined criteria is a function of a frequency of occurrence of said topic within said cluster.

26. The method of claim 24, wherein said topic is a pre-selected word or phrase.

27. A database search engine system, comprising:

an editorial database that stores one or more clusters of words and phrases, wherein each cluster is identified by one or more topic names;

a search engine database that stores a catalogue of items; and

a computer coupled to said editorial database and said search engine database, wherein said computer receives a query relevant to said catalogue of items and compares said query to said one or more clusters of words and phrases stored in said editorial database, and wherein said computer queries said search engine database with a modified query, wherein said modified query is one or more of said topic names that satisfy a predetermined commonality with said query.

28. The system of claim 27, further comprising a communication network in communication with said computer, wherein said communication network delivers said query to said computer.

29. The system of claim 28, wherein said communication network is the Internet.

30. The system of claim 28, further comprising a network appliance coupled to said communication network, wherein said network appliance allows a user to enter said query and to receive a search result.

31. The system of claim 28, wherein said network appliance is a computer that includes an Internet browser-based software application for entering said query.

32. The system of claim 27, wherein said items include Internet Web sites.

33. The system of claim 27, wherein said query includes words or phrases.

34. A system for suggesting alternative words or phrases, comprising:

an editorial database that stores one or more clusters of words and phrases, wherein each cluster is identified by one or more topic names;

a computer coupled to said editorial database, wherein said computer receives a query and segments said query into a first plurality of character sets and said words or phrases in said editorial database into another plurality of character sets, and wherein said computer further outputs at least one alternative word or phrase that satisfied a predetermined commonality with said query.