Clustering based text classification

• US 7,366,705 B2
• Filed: 08/16/2004
• Issued: 04/29/2008
• Est. Priority Date: 04/15/2004
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Ma, Wei-Ying, Chen, Zheng, Zhang, Benyu, Zeng, Hua-Jun, Wang, Xuanhui
• Primary Examiner(s): Holmes; Michael B.
• Application Number:
  US10/921,477
• Publication Number:
  US 20050234955A1
• Time in Patent Office: 1,352 Days
• Field of Search: 706/20
• US Class Current: 706/20
• 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 one or more clusters;

generating expanded labeled data as a function of the one or more clusters, the expanded label data comprising the labeled data and at least a portion of the unlabeled data;

training one or more discriminative classifiers based on the expanded labeled data and remaining ones of the unlabeled data; and

generating, using the one or more discriminative classifiers, classified text for information retrieval.

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 one or more latent class variables.

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 a t 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 a t least a portion of the unlabeled data to cluster centroids.

8. A method as recited in claim 1, wherein training the one or more discriminative classifiers 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 one or more discriminative classifiers further comprises combining clustering and classification through iterative reinforcement until all examples in a particular classifier of the one or more discriminative classifiers are labeled.

10. A method as recited in claim 9, wherein the one or more clusters 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 one or more clusters;

generating expanded labeled data as a function of the one or more clusters, the expanded label data comprising the labeled data and at least a portion of the unlabeled data;

training one or more discriminative classifiers based on the expanded labeled data and remaining ones of the unlabeled data; and

generating, using the one or more discriminative classifiers, classified text for information retrieval;

wherein a size of the labeled data is small as compared to a size 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 the expanded label data provides information for one or more latent class variables.

15. 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.

16. 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 of the unlabeled data to cluster centroids.

17. A computer-readable medium as recited in claim 11, wherein the computer-program instructions for training the one or more discriminative classifiers 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.

18. A computer-readable medium as recited in claim 11, wherein the computer-program instructions for training the one or more discriminative classifiers further comprise instructions for combining clustering and classification through iterative reinforcement until all examples in a particular classifier of the one or more discriminative classifiers are labeled.

19. A computer-readable medium as recited in claim 18, wherein the one or more clusters 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.

20. 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 one or more clusters;

generating expanded labeled data as a function of the one or more clusters, the expanded label data comprising the labeled data and at least a portion of the unlabeled data;

training one or more discriminative classifiers based on the expanded labeled data and remaining ones of the unlabeled data; and

generating, using the one or more discriminative classifiers, classified text for information retrieval.

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

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

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

24. A computing device as recited in claim 20, wherein the expanded labeled data provides information for one or more latent class variables.

25. A computing device as recited in claim 20, 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.

26. A computing device as recited in claim 20, 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 of the unlabeled data to cluster centroids.

27. A computing device as recited in claim 20, wherein the computer-program instructions for training the one or more discriminative classifiers 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.

28. A computing device as recited in claim 20, wherein the computer-program instructions for training the one or more discriminative classifiers further comprise instructions for combining clustering and classification through iterative reinforcement until all examples in a particular classifier of the one or more discriminative classifiers are labeled.

29. A computing device as recited in claim 28, wherein the one or more discriminative clusters 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.

30. A computing device comprising:

clustering means to cluster text comprising labeled data and unlabeled data in view of the labeled data to generate one or more clusters;

generating means to generate expanded labeled data as a function of the one or more clusters, the expanded label data comprising the labeled data and at least a portion of the unlabeled data;

training means to train one or more discriminative classifiers based on the expanded labeled data and remaining ones of the unlabeled data; and

generating means to classify text based on the one or more discriminative classifiers to create classified text for information retrieval.

31. A computing device as recited in claim 30, 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.

32. A computing device as recited in claim 30, 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 of the unlabeled data to cluster centroids.

33. A computing device as recited in claim 30, wherein the means to train the one or more discriminative classifiers 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.

34. A computing device as recited in claim 30, wherein the means to train the one or more discriminative classifiers further comprises combining means to combine clustering and classification through iterative reinforcement until all examples in a particular classifier of the one or more discriminative classifiers are labeled.

35. A computing device as recited in claim 34, wherein the one or more discriminative clusters 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.