System and method for category discovery

1. A method executed by a computer for category discovery, comprising:

receiving an information collection including a set of strings;

identifying positively predictive pairs of strings;

identifying negatively predictive pairs of strings;

joining positively predictive pairs of strings into a category;

splitting negatively predictive pairs of strings into different categories; and

according to the joining and splitting, providing a set of categories to enable categorization of information in a database,

wherein the information collection is a document collection.

2. The method of claim 1 :

wherein identifying elements include identifying the positively and negatively predictive pairs of strings using a string prediction matrix.

3. The method of claim 2 , further comprising:

ordering the positively predictive pairs within a positive pair list according to a position of a positively predictive pair's predictive value within the string prediction matrix; and

performing the joining and splitting elements in an order which depends on how the positively predictive pairs are listed on the positive pair list.

4. The method of claim 2 , further comprising:

ordering the negatively predictive pairs within a negative pair list according to a position of a negatively predictive pair's predictive value within the string prediction matrix; and

performing the joining and splitting elements in an order which depends on how the negatively predictive pairs are listed on the negative pair list.

5. The method of claim 2 , wherein the string prediction matrix includes prediction values that indicate how well strings in the set predict each other, the method further comprising:

clamping a predictive value within the string prediction matrix to a predetermined value, if an absolute value of the predictive value is below a predetermined threshold.

6. The method of claim 5 , further comprising:

disregarding clamped pairs of strings when performing the joining and splitting elements.

7. The method of claim 1 :

further comprising, enumerating a set of most frequently occurring strings within the information collection; and

wherein the identifying elements include, identifying the positively and negatively predictive pairs of strings only for the set of most frequently occurring strings.

8. The method of claim 1 , wherein the identifying elements include:

generating a string bit vector for each corresponding individual string in the set of strings;

using a first label in a string bit vector to identify those information sets within the information collection which contain the corresponding string;

using a second label in the string bit vector to identify those information sets within the information collection which do not contain the corresponding string;

combining the string bit vectors for the set of strings into a bit vector matrix;

defining All_Positives as a number of first labels within a first string bit vector for a first string;

defining All_Negatives as a number of second labels within the first string bit vector,

defining True_Positives as a number of rows in the bit vector matrix in which both the first string bit vector and a second string bit vector, for a second string, have the first label;

defining False_Negatives as a number of rows in the bit vector matrix in which the first

string bit vector has the first label but the second string bit vector has the second label;

defining False_Positives as a number of rows in the bit vector matrix in which the first string bit vector has the second label but the second string bit vector has the first label;

defining the first string and second string as a pair of strings;

setting a predictive value corresponding to the pair of strings within a string prediction matrix proportional to F(True_Positives/All_Positives)-P(False_Positives/All_negatives), wherein F( ) is a function.

9. The method of claim 8 , wherein:

F( ) is an inverse cumulative distribution function of a Normal curve.

10. The method of claim 8 , wherein:

F( ) is a discretized inverse cumulative distribution function of a Normal curve.

11. The method of claim 1 :

further comprising,

combining the positively predictive pairs into a positive pair list;

combining the negatively predictive pairs into a negative pair list; and

defining as a first category those strings within a first positive pair within the positive pair list; and

wherein joining includes,

adding strings from a second positive pair from the positive pair list to the first category if (a) one of the strings within the second positive pair matches at least one string in the first category, and (b) none of the strings within the second positive pair are negatively predictive of the strings within the first category.

12. The method of claim 1 :

further comprising,

combining the positively predictive pairs into a positive pair list;

combining the negatively predictive pain into a negative pair list; and

defining as a first category those strings within a first positive pair within the positive pair list; and

wherein if (a) one of the strings within a second positive pair matches at least one string in the first category, and (b) one of the strings within the second positive pair is negatively predictive of a string within the first category, then splitting includes,

duplicating the first category;

defining the duplicate as a second category;

removing those strings within the second category that are negatively predictive of a string in the second positive pair; and

adding the strings in the second positive pair to the second category.

13. The method of claim 1 :

further comprising,

combining the positively predictive pairs into a positive pair list;

combining the negatively predictive pairs into a negative pair list; and

defining as a first category those strings within a first positive pair within the positive pair list; and

wherein if (a) not one string within a second positive pair matches a string in the first category, and (b) at least one of the strings within the second positive pair is negatively predictive of a string within the first category, then splitting includes,

defining a third category as including the strings within the second positive pair.

14. The method of claim 13 :

wherein the third category is a Singleton category.

15. The method of claim 1 , wherein the information collection is in the database, and wherein categorizing of information in the database comprises categorizing of the information collection.

16. The method of claim 1 , wherein:

providing the set of categories comprises providing the set of categories that represent issues of a company.

17. A method executed by a computer for category discovery, comprising:

receiving an information collection including a set of strings;

identifying positively predictive pairs of strings;

identifying negatively predictive pairs of strings;

joining positively predictive pairs of strings into a category;

splitting negatively predictive pairs of strings into different categories; and

according to the joining and splitting, providing a set of categories to enable categorization of information in a database,

labeling a particular category as a concatenated set of those strings within the particular category.

18. The method of claim 17 , wherein the labeling produces a label for the particular category, and wherein the labeling includes:

ordering the strings within the label according to each string's frequency of occurrence within the information collection.

19. A method executed by a computer for category discovery, comprising:

receiving an information collection including a set of strings;

identifying positively predictive pairs of strings;

identifying negatively predictive pairs of strings;

joining positively predictive pairs of strings into a category;

splitting negatively predictive pairs of strings into different categories; and

according to the joining and splitting, providing a set of categories to enable categorization of information in a database,

wherein the identifying elements include identifying the positively and negatively predictive pairs of strings using a Bi-Normal Separation matrix.

20. A method executed by a computer for category discovery, comprising:

receiving an information collection including a set of strings;

identifying positively predictive pairs of strings;

identifying negatively predictive pairs of strings;

joining positively predictive pairs of strings into a category;

splitting negatively predictive pairs of strings into different categories; and

according to the joining and splitting, providing a set of categories to enable categorization of information in a database,

wherein the set of strings is a set of terms.

21. A method executed by a computer for category discovery, comprising:

receiving an information collection including a set of strings;

identifying positively predictive pairs of strings;

identifying negatively predictive pairs of strings;

joining positively predictive pairs of strings into a category;

splitting negatively predictive pairs of strings into different categories; and

producing a set of categories that represent issues of a company; and

wherein the identifying elements include:

generating a string bit vector for individual strings in the set of strings;

using a first label in a string bit vector to identify those information sets within the information collection which contain the string;

using a second label in the string bit vector to identify those information sets within the information collection which do not contain the string;

combining the string bit vectors for the set of strings into a bit vector matrix;

defining All_Positives as a number of first labels within a first string bit vector for a first string;

defining All_Negatives as a number of second labels within the first string bit vector;

defining True_Positives as a number of rows in the bit vector matrix in which both the first string bit vector and a second string bit vector, for a second string, have the first label;

defining False_Negatives as a number of rows in the bit vector matrix in which the first string bit vector has the first label but the second string bit vector has the second label;

defining False_Positives as a number of rows in the bit vector matrix in which the first string bit vector has the second label but the second string bit vector has the first label;

defining the first string and second string as a pair of strings;

setting a predictive value corresponding to the pair of strings within a string prediction matrix proportional to F(True_Positives/All_Positives)-F(False_Positives/All_negatives), wherein F( ) is an inverse cumulative distribution function of a Normal curve.

22. A method executed by a computer for category discovery, comprising:

receiving an information collection including a set of strings;

identifying positively predictive pairs of strings;

identifying negatively predictive pairs of strings;

joining positively predictive pairs of strings into a category;

splitting negatively predictive pairs of strings into different categories;

combining the positively predictive pairs into a positive pair list;

combining the negatively predictive pairs into a negative pair list; and

defining as a first category those strings within a first positive pair within the positive pair list; and

wherein joining includes,

adding strings from a second positive pair from the positive pair list to the first category if (a) one of the strings within the second positive pair matches at least one string in the first category, and (b) none of the strings within the second positive pair are negatively predictive of the strings within the first category; and

wherein if (a) one of the strings within a second positive pair matches at least one string in the first category, and (b) one of the strings within the second positive pair is negatively predictive of a string within the first category, then splitting includes,

duplicating the first category;

defining the duplicate as a second category;

removing those strings within the second category that are negatively predictive of a string in the second positive pair; and

adding the strings in the second positive pair to the second category, which are not already members of the second category; and

wherein if (a) not one string within a second positive pair matches a string in the first category, and (b) at least one of the strings within the second positive pair is negatively predictive of a string within the first category, then splitting includes,

defining a third category as including the strings within the second positive pair,

wherein the first, second, and third categories are part of a set of categories that represent issues of a company.

23. A method executed by a computer for category discovery, comprising:

receiving an information collection including a set of strings;

identifying positively predictive pairs of strings;

identifying negatively predictive pairs of strings;

joining positively predictive pairs of strings into a category;

splitting negatively predictive pairs of strings into different categories; and

according to the joining and splitting, providing a set of categories to enable categorization of information in a databas,

wherein the identifying elements include identifying the positively and negatively predictive pairs of strings using a term correlation matrix.

24. A computer-readable storage medium containing instructions that when executed by a computer perform category discovery, comprising:

receiving an information collection including a set of strings;

identifying positively predictive pairs of strings;

identifying negatively predictive pairs of strings;

joining positively predictive pairs of strings into a category;

splitting negatively predictive pairs of strings into different categories;

according to the joining and splitting, providing a set of categories to enable categorization of information in a database;

combining the positively predictive pairs into a positive pair list;

combining the negatively predictive pairs into a negative pair list; and

defining as a first category those strings within a first positive pair within the positive pair list; and

wherein joining includes,

add strings from a second positive pair from the positive pair list to the first category if (a) one of the strings within the second positive pair matches at least one string in the first category, and (b) none of the strings within the second positive pair are negatively predictive of the strings within the first category.

25. The computer-readable storage medium of claim 24 , wherein the instructions when executed cause the computer to further:

wherein if (a) one of the strings within the second positive pair matches at least one string in the first category, and (b) one of the strings within the second positive pair is negatively predictive of a string within the first category, then splitting includes,

duplicating the first category;

defining the duplicate as a second category;

removing those strings within the second category that are negatively predictive of a string in the second positive pair; and

adding the strings in the second positive pair to the second category, which are not already members of the second category.

26. The computer-readable storage medium of claim 24 , wherein the instructions when executed cause the computer to further:

wherein if (a) not one string within the second positive pair matches a string in the first category, and (b) at least one of the strings within the second positive pair is negatively predictive of a string within the first category, then splitting includes,

defining a third category as including the strings within the second positive pair.

27. The instructions of claim 24 , wherein:

providing the set of categories comprises providing the set of categories that represent issues of a company.

28. A computer-readable storage medium containing instructions that when executed by a computer perform category discovery, comprising:

receiving an information collection including a set of strings;

identifying positively predictive pairs of strings;

identifying negatively predictive pairs of strings;

joining positively predictive pairs of strings into a category;

splitting negatively predictive airs of stings into different categories;

according to the joining and splitting, providing a set of categories to enable categorization of information in a database; and

labeling a particular category as a concatenated set of those strings within the particular category.

29. The computer-readable storage medium of claim 28 , wherein the labeling produces a label for the particular category, and wherein labeling includes:

ordering the strings within the label according to each string's frequency of occurrence within the information collection.