Clustering a collection using an inverted index of features

Patent metadata

Field	Value
Publication number	US-10083230-B2
Application number	US-96669810-A
Country	US
Kind code	B2
Filing date	Dec 13, 2010
Priority date	Dec 13, 2010
Publication date	Sep 25, 2018
Grant date	Sep 25, 2018

Abstract

Provided are techniques for creating an inverted index for features of a set of data elements, wherein each of the data elements is represented by a vector of features, wherein the inverted index, when queried with a feature, outputs one or more data elements containing the feature. The features of the set of data elements are ranked. For each feature in the ranked list, the inverted index is queried for data elements having the feature and not having any previously selected feature and a cluster of the data elements is created based on results returned in response to the query.

First claim

The invention claimed is:

1. A method, comprising:
storing, using a processor of a computer, data elements, wherein each of the data elements is represented by a vector of features from a set of features;
creating an inverted index for the set of features;
forming a ranked list of the features in the set of features; and
creating clusters by performing for each of the features in the ranked list of the features:
selecting a feature in the ranked list of the features that has not been previously selected to create the clusters;
issuing a query against the inverted index to retrieve those data elements that have the selected feature and that do not have any of the features that were previously selected to create the clusters; and
creating a new cluster of the retrieved data elements that have the selected feature and that do not have any of the features that were previously selected to create the clusters; and

generating a hierarchy of the clusters by:
for a cluster at a level of the hierarchy having a first feature,
selecting a second feature;
issuing a new query against the inverted index to retrieve other data elements having the first feature, having the second feature, and not having any previously selected feature that has been used to create another sub-cluster at the level of the hierarchy; and
creating a new sub-cluster with the other data elements having the first feature, having the second feature, and not having any previously selected feature that has been used to form another sub-cluster at the level of the hierarchy.

2. The method of claim 1 , further comprising:
in response to determining that a number of the retrieved data elements is greater than a threshold, creating the new cluster having a label of the selected feature.

3. The method of claim 1 , wherein the features in the set of features comprise noun phrases of different lengths.

4. The method of claim 1 , further comprising:
in response to determining that a number of the other data elements is greater than a new threshold, creating the new sub-cluster having a label of the second feature as a child.

5. A system, comprising:
a processor; and
an index-based clustering system coupled to the processor and performing operations, the operations comprising:
storing data elements, wherein each of the data elements is represented by a vector of features from a set of features;
creating an inverted index for the set of features;
forming a ranked list of the features in the set of features; and
creating clusters by performing for each of the features in the ranked list of the features:
selecting a feature in the ranked list of the features that has not been previously selected to create the clusters;
issuing a query against the inverted index to retrieve those data elements that have the selected feature and that do not have any of the features that were previously selected to create the clusters; and
creating a new cluster of the retrieved data elements that have the selected feature and that do not have any of the features that were previously selected to create the clusters; and

generating a hierarchy of the clusters by:
for a cluster at a level of the hierarchy having a first feature,
selecting a second feature;
issuing a new query against the inverted index to retrieve other data elements having the first feature, having the second feature, and not having any previously selected feature that has been used to create another sub-cluster at the level of the hierarchy; and
creating a new sub-cluster with the other data elements having the first feature, having the second feature, and not having any previously selected feature that has been used to form another sub-cluster at the level of the hierarchy.

6. The system of claim 5 , wherein the operations further comprise:
in response to determining that a number of the retrieved data elements is greater than a threshold, creating the new cluster having a label of the selected feature.

7. The system of claim 5 , wherein the features in the set of features comprise noun phrases of different lengths.

8. The system of claim 5 , wherein the operations further comprise:
in response to determining that a number of the other data elements is greater than a new threshold, creating the new sub-cluster having a label of the second feature as a child.

9. A computer program product, the computer program product comprising:
a non-transitory computer readable storage medium having computer readable program code embodied therewith, the computer readable program code, when executed by a processor of a computer, performs:
storing data elements, wherein each of the data elements is represented by a vector of features from a set of features;
creating an inverted index for the set of features;
forming a ranked list of the features in the set of features; and
creating clusters by performing for each of the features in the ranked list of the features:
selecting a feature in the ranked list of the features that has not been previously selected to create the clusters;
issuing a query against the inverted index to retrieve those data elements that have the selected feature and that do not have any of the features that were previously selected to create the clusters; and
creating a new cluster of the retrieved data elements that have the selected feature and that do not have any of the features that were previously selected to create the clusters; and

generating a hierarchy of the clusters by:
for a cluster at a level of the hierarchy having a first feature,
selecting a second feature;
issuing a new query against the inverted index to retrieve other data elements having the first feature, having the second feature, and not having any previously selected feature that has been used to create another sub-cluster at the level of the hierarchy; and
creating a new sub-cluster with the other data elements having the first feature, having the second feature, and not having any previously selected feature that has been used to form another sub-cluster at the level of the hierarchy.

10. The computer program product of claim 9 , wherein the computer readable program code is configured to perform:
in response to determining that a number of the retrieved data elements is greater than a threshold, creating the new cluster having a label of the selected feature.

11. The computer program product of claim 9 , wherein the features in the set of features comprise noun phrases of different lengths.

12. The computer program product of claim 9 , wherein the computer readable program code is configured to perform:
in response to determining that a number of the other data elements is greater than a new threshold, creating the new sub-cluster having a label of the second feature as a child.

Assignees

• Contractor Danish
• Hampp Bahnmueller Thomas
• Joshi Sachindra
• Krishnapuram Raghuram
• Ng Kenney
• IBM

Inventors

• Contractor Danish
• Hampp-Bahnmueller Thomas
• Joshi Sachindra
• Krishnapuram Raghuram
• Ng Kenney

Classifications

• G06F16/355 Primary

  Creation or modification of classes or clusters · CPC title

• G06F16/319

  Inverted lists · CPC title

• G06F16/285

  Clustering or classification · CPC title

• G06F17/30622

  Physics · mapped topic

• G06F17/3071 Primary

  Physics · mapped topic