Clustering based text classification

• US 20050234955A1
• Filed: 08/16/2004
• Published: 10/20/2005
• Est. Priority Date: 04/15/2004
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Ma, Wei-Ying, Chen, Zheng, Wang, Xuanhui, Zhang, Benyu, Zeng, Hua-Jun
• Granted Patent: US 7,366,705 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/355 Class or cluster creation or modification

Abstract

Systems and methods for clustering-based text classification are described. In one aspect text is clustered as a function of labeled data to generate cluster(s). The text includes the labeled data and unlabeled data. Expanded labeled data is then generated as a function of the cluster(s). The expanded label data includes the labeled data and at least a portion of unlabeled data. Discriminative classifier(s) are then trained based on the expanded labeled data and remaining ones of the unlabeled data.

Claims

1. A method for text classification, the method comprising:

clustering text comprising labeled data and unlabeled data in view of the labeled data to generate cluster(s);

generating expanded labeled data as a function of the cluster(s), the expanded label data comprising the labeled data and at least a portion of unlabeled data; and

training discriminative classifier(s) based on the expanded labeled data and remaining ones of the unlabeled data.

2. A method as recited in claim 1, wherein the text exhibits high dimensionality and data sparseness.

3. A method as recited in claim 1, wherein the text exhibits a substantial number of low-density areas between positive and negative labeled examples.

4. A method as recited in claim 1, wherein a size of the labeled data is small as compared to a size of the unlabeled data.

5. A method as recited in claim 1, wherein the expanded labeled data provides information for latent class variable(s).

6. A method as recited in claim 1, wherein clustering the text further comprises

generating initial centroids based on the labeled data;

and

wherein generating the expanded labeled data is constrained by the initial centroids.

7. A method as recited in claim 1, wherein generating the expanded labeled data further comprises determining with a high confidence that the at least a portion of the unlabeled data can be viewed as labeled data, the high confidence being based on proximity of respective ones of the at least a portion to cluster centroids.

8. A method as recited in claim 1, wherein training the discriminative classifer(s) further comprises propagating label data to the unlabeled data as a function of clustering results to obtain a substantially low generalization error on unseen data.

9. A method as recited in claim 1, wherein training the discriminative classifer(s) further comprises combining clustering and classification through iterative reinforcement until all examples in a classifier of the classifier(s) are labeled.

10. A method as recited in claim 9, wherein the cluster(s) are based on all available data and represent an approximately correct classifier L₁, and wherein the iterative reinforcement comprises aspects of the generating and the training comprising:

selecting unlabeled data samples from the unlabeled data, the unlabeled data samples being confidently classified as a function of L₁;

combining the unlabeled data samples with original labeled data to train a new model L₂; and

performing operations of the selecting and the combining until all examples in the new model are labeled.

11. A computer-readable medium having stored thereon computer-program instructions for text classification, the computer-program instructions being executable by a processor, the computer-program instructions comprising instructions for:

clustering text comprising labeled data and unlabeled data in view of the labeled data to generate cluster(s);

generating expanded labeled data as a function of the cluster(s), the expanded label data comprising the labeled data and at least a portion of unlabeled data; and

training discriminative classifer(s) based on the expanded labeled data and remaining ones of the unlabeled data.

12. A computer-readable medium as recited in claim 11, wherein the text exhibits high dimensionality and data sparseness.

13. A computer-readable medium as recited in claim 11, wherein the text exhibits a substantial number of low-density areas between positive and negative labeled examples.

14. A computer-readable medium as recited in claim 11, wherein a size of the labeled data is small as compared to a size of the unlabeled data.

15. A computer-readable medium as recited in claim 11, wherein the expanded labeled data provides information for latent class variable(s).

16. A computer-readable medium as recited in claim 11, wherein the computer-program instructions for clustering the text further comprise instructions for:

generating initial centroids based on the labeled data; and

wherein generating the expanded labeled data is constrained by the initial centroids.

17. A computer-readable medium as recited in claim 11, wherein the computer-program instructions for generating the expanded labeled data further comprise instructions for determining with a high confidence that the at least a portion of the unlabeled data can be viewed as labeled data, the high confidence being based on proximity of respective ones of the at least a portion to cluster centroids.

18. A computer-readable medium as recited in claim 11, wherein the computer-program instructions for training the discriminative classifer(s) further comprise instructions for propagating label data to the unlabeled data as a function of clustering results to obtain a substantially low generalization error on unseen data.

19. A computer-readable medium as recited in claim 11, wherein the computer-program instructions for training the discriminative classifer(s) further comprise instructions for combining clustering and classification through iterative reinforcement until all examples in a classifier of the classifier(s) are labeled.

20. A computer-readable medium as recited in claim 19, wherein the cluster(s) are based on all available data and represent an approximately correct classifier L₁, and wherein the iterative reinforcement comprises aspects of the computer-program instructions for the generating and the training, the iterative reinforcement comprising instructions for:

selecting unlabeled data samples from the unlabeled data, the unlabeled data samples being confidently classified as a function of L₁;

combining the unlabeled data samples with original labeled data to train a new model L₂; and

performing operations of the selecting and the combining until all examples in the new model are labeled.

21. A computing device comprising:

a processor; and

a memory coupled to the processor, the memory comprising computer-program instructions executable by the processor for text classification, the computer-program instructions comprising instructions for;

clustering text comprising labeled data and unlabeled data in view of the labeled data to generate cluster(s);

generating expanded labeled data as a function of the cluster(s), the expanded label data comprising the labeled data and at least a portion of unlabeled data; and

training discriminative classifer(s) based on the expanded labeled data and remaining ones of the unlabeled data.

22. A computing device as recited in claim 21, wherein the text exhibits high dimensionality and data sparseness.

23. A computing device as recited in claim 21, wherein the text exhibits a substantial number of low-density areas between positive and negative labeled examples.

24. A computing device as recited in claim 21, wherein a size of the labeled data is small as compared to a size of the unlabeled data.

25. A computing device as recited in claim 21, wherein the expanded labeled data provides information for latent class variable(s).

26. A computing device as recited in claim 21, wherein the computer-program instructions for clustering the text further comprise instructions for:

generating initial centroids based on the labeled data; and

wherein generating the expanded labeled data is constrained by the initial centroids.

27. A computing device as recited in claim 21, wherein the computer-program instructions for generating the expanded labeled data further comprise instructions for determining with a high confidence that the at least a portion of the unlabeled data can be viewed as labeled data, the high confidence being based on proximity of respective ones of the at least a portion to cluster centroids.

28. A computing device as recited in claim 21, wherein the computer-program instructions for training the discriminative classifer(s) further comprise instructions for propagating label data to the unlabeled data as a function of clustering results to obtain a substantially low generalization error on unseen data.

29. A computing device as recited in claim 21, wherein the computer-program instructions for training the discriminative classifer(s) further comprise instructions for combining clustering and classification through iterative reinforcement until all examples in a classifier of the classifier(s) are labeled.

30. A computing device as recited in claim 29, wherein the cluster(s) are based on all available data and represent an approximately correct classifier L₁, and wherein the iterative reinforcement comprises aspects of the computer-program instructions for the generating and the training, the iterative reinforcement comprising instructions for:

selecting unlabeled data samples from the unlabeled data, the unlabeled data samples being confidently classified as a function of L₁;

combining the unlabeled data samples with original labeled data to train a new model L₂; and

performing operations of the selecting and the combining until all examples in the new model are labeled.

31. A computing device comprising:

clustering means to cluster text comprising labeled data and unlabeled data in view of the labeled data to generate cluster(s);

generating means to generate expanded labeled data as a function of the cluster(s), the expanded label data comprising the labeled data and at least a portion of unlabeled data; and

training means to train discriminative classifer(s) based on the expanded labeled data and remaining ones of the unlabeled data.

32. A computing device as recited in claim 31, wherein the means for clustering the text further comprise:

generating means to generate initial centroids based on the labeled data; and

wherein generating the expanded labeled data is constrained by the initial centroids.

33. A computing device as recited in claim 31, wherein the means to generate the expanded labeled data further comprises determining means to determine with a high confidence that the at least a portion of the unlabeled data can be viewed as labeled data, the high confidence being based on proximity of respective ones of the at least a portion to cluster centroids.

34. A computing device as recited in claim 31, wherein the means to train the discriminative classifer(s) further comprises propagating means to propagate label data to the unlabeled data as a function of clustering results to obtain a substantially low generalization error on unseen data.

35. A computing device as recited in claim 31, wherein the means to train the discriminative classifer(s) further comprises combining means to combine clustering and classification through iterative reinforcement until all examples in a classifier of the classifier(s) are labeled.

36. A computing device as recited in claim 35, wherein the cluster(s) are based on all available data and represent an approximately correct classifier L₁, and wherein the iterative reinforcement comprises aspects of the means to generate and the means to train, the iterative reinforcement comprising:

selecting means to select unlabeled data samples from the unlabeled data, the unlabeled data samples being confidently classified as a function of L₁;

combining means to combine the unlabeled data samples with original labeled data to train a new model L₂; and

performing means to implement the selecting and combining means until all examples in the new model are labeled.