System and method for adaptive categorization for use with dynamic taxonomies

• US 20100145961A1
• Filed: 12/05/2008
• Published: 06/10/2010
• Est. Priority Date: 12/05/2008
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Mojsilovic, Aleksandra, Hu, Jianying, Singh, Moninder
• Granted Patent: US 8,161,028 B2
• Time in Patent Office: Days
• US Class Current: 707/758
• CPC Class Codes: G06F 16/355 Class or cluster creation or modification

Abstract

A system, method and computer program product provides a solution to a class of categorization problems using a semi-supervised clustering approach, the method employing performing a Soft Seeded k-means algorithm, which makes effective use of the side information provided by seeds with a wide range of confidence levels, even when they do not provide complete coverage of the pre-defined categories. The semi-supervised clustering is achieved through the introductions of a seed re-assignment penalty measure and model selection measure.

Claims

1. A computer-implemented method for categorizing data points belonging to a dataset, each data point having a set of basic features associated therewith, said method comprising:

matching a textual description of a data point of said data set to category descriptions relating to a pre-defined set of categories,

for said data point having said textual description, generating a soft seed data structure based on a result of said matching; and

,

assigning each said data points into a predefined number of clusters corresponding to the predefined categories using the generated soft seed data structures and the set of basic features, said cluster assigning including using a semi-supervised clustering framework.

2. The computer-implemented method of claim 1, wherein said assigning includes implementing a semi-supervised k-means algorithm.

3. The computer-implemented method of claim 2, where in said soft seed data structure includes a label to one of the predefined categories, and a confidence score.

4. The computer-implemented method of claim 3, wherein said implementing said semi-supervised k-means algorithm comprises:

a) assigning an initial centroid to each predefined cluster, wherein, an initial centroid ε

_j of a particular cluster “

j”

is computed based on seeds representing labeled data points, and for a cluster ε

_j not covered by seeds, the initial centroid is computed based on random sampling from all unlabeled data points;

b) assigning each said data points to a cluster in a manner to minimize a distortion measure;

said assigning performed by iterating over the set of data points, and at each iteration;

determining violation of a soft seeding constraint of a data point assigned to a cluster, and one of;

incurring a penalty value based on said confidence score, if violated; and

, incurring no penalty if not violated; and

,

determining a cluster model for said assigned data points, and generating a fitness score based on said cluster model; and

,

repeating steps a) and b) a plurality of times, and determining a cluster model and corresponding fitness score for said assigned data points at each iteration; and

,

selecting the cluster model corresponding to the highest fitness score as the final assignment of all data points to the predefined categories.

5. The computer-implemented method as claimed in claim 4, wherein said distortion measure comprises a pairwise distance measure D(x_i, ε

_j) between a data point x_i of the data set and a calculated centroid ε

_j of a particular cluster “

j”

.

6. The computer-implemented method as claimed in claim 4, further comprising, at each iteration:

updating a centroid ε

_j value for each cluster “

j”

to which a labeled or unlabled datapoint has been assigned.

7. The computer-implemented method as claimed in claim 4, further including:

computing each initial centroid covered by seeds using the labeled datapoints having associated seeds; and

,

computing each initial centroids of remaining clusters through random sampling of unlabeled data points having no associated seeds.

8. The computer-implemented method as claimed in claim 4, wherein at each iteration of performing steps a) and b), computing the initial centroids of remaining clusters according to a different random sampling of unlabeled data points

9. The computer-implemented method as claimed in claim 4, wherein said incurred penalty value comprises a value determined in accordance with a sigmoid function P( ) of said seed score, said sigmoid function P( ) computed, at said computing device, according to:

P(j, li, si)=0 if j=0 or j=l_i;

otherwise

10. The computer-implemented method as claimed in claim 4, wherein said fitness score is based on said cluster model according to:

(D_l*|D_l−

D_ul|)<sup>−

1</sup>

where D_l represents a distortion measure of the labeled data points, and D_u represents a distortion measure of the unlabeled data points.

11. A computer program product for categorizing data points belonging to a dataset, each data point having a set of basic features associated therewith, said computer program product comprising:

a computer usable medium having computer usable program code embodied therewith, the computer usable program code comprising;

computer usable program code configured to match a textual description of a data point of said data set to category descriptions relating to a pre-defined set of categories,

computer usable program code configured to generate, for said data point having said textual description, a soft seed data structure based on a result of said matching; and

,

computer usable program code configured to assign each said data point into a predefined number of clusters corresponding to the predefined categories using the generated soft seed data structures and the set of basic features, said cluster assigning including using a semi-supervised clustering framework.

12. The computer program product of claim 11, wherein said computer usable program code configured to assign each said data point includes computer usable program code configured to implement a semi-supervised k-means algorithm.

13. The computer program product of claim 12, wherein said soft seed data structure includes a label to one of the predefined categories, and a confidence score.

14. The computer program product of claim 13, wherein said computer usable program code configured to implement said semi-supervised k-means algorithm comprises:

a) computer usable program code configured to assign an initial centroid to each predefined cluster, wherein, an initial centroid ε

_j of a particular cluster “

j”

is computed based on seeds representing labeled data points, and for a cluster ε

_j not covered by seeds, the initial centroid is computed based on random sampling from all unlabeled data points;

b) computer usable program code configured for assigning each said data point to a cluster in a manner to minimize a distortion measure;

said assigning performed by iterating over the set of data points, and at each iteration;

determining violation of a soft seeding constraint of a data point assigned to a cluster, and one of;

incurring a penalty value based on said confidence score, if violated; and

, incurring no penalty if not violated; and

,

determining a cluster model for said assigned data points, and generating a fitness score based on said cluster model; and

,

computer usable program code configured for repeating steps a) and b) a plurality of times, and determining a cluster model and corresponding fitness score for said assigned data points at each iteration; and

,

computer usable program code configured for selecting the cluster model corresponding to the highest fitness score as the final assignment of all data points to the predefined categories.

15. The computer program product of claim 14, wherein said distortion measure comprises a pairwise distance measure D(x_i, ξ

_j) between a data point x_i of the data set and a calculated centroid ε

_j of a particular cluster “

j”

.

16. The computer program product of claim 14, further comprising:

computer usable program code configured to update a centroid ε

_j value for each cluster “

j”

to which a labeled or unlabled datapoint has been assigned at each iteration.

17. The computer program product of claim 14, further including:

computer usable program code configured to compute each initial centroid covered by seeds using the labeled datapoints having associated seeds; and

,

computer usable program code configured to compute each initial centroids of remaining clusters through random sampling of unlabeled data points having no associated seeds.

18. The computer program product of claim 14, wherein at each iteration of performing steps a) and b), computer usable program code configured to compute each initial centroids further computes the initial centroids of remaining clusters according to a different random sampling of unlabeled data points

19. The computer program product of claim 14, wherein said incurred penalty value comprises a value determined in accordance with a sigmoid function P( ) of said seed score, said sigmoid function P( ) computed, at said computing device, according to:

P(j, li, si)=0 if j=0 or j=l_i;

otherwise

20. The computer program product of claim 14, wherein said fitness score is based on said cluster model according to:

(D_l*|D_l−

D_ul|)<sup>−

1</sup>

where D_l represents a distortion measure of the labeled data points, and D_u represents a distortion measure of the unlabeled data points.

21. A method of deploying a computer program product for categorizing data points belonging to a dataset, each data point having a set of basic features associated therewith, wherein, when executed, the computer program performs the steps of:

matching a textual description of a data point of said data set to category descriptions relating to a pre-defined set of categories,

for said data point having said textual description, generating a soft seed data structure based on a result of said matching; and

,

assigning each said data points into a predefined number of clusters corresponding to the predefined categories using the generated soft seed data structures and the set of basic features, said cluster assigning including using a semi-supervised clustering framework.