Method, system and computer program product for organizing data

• US 20070143235A1
• Filed: 12/21/2005
• Published: 06/21/2007
• Est. Priority Date: 12/21/2005
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Kummamuru, Krishna, Kankar, Pankaj
• Granted Patent: US 7,502,765 B2
• Time in Patent Office: Days
• US Class Current: 706/15
• CPC Class Codes: G06F 16/81 Indexing, e.g. XML tags; Data structures therefor; Storage structures
• CPC Class Codes: G06F 18/231 Hierarchical techniques, i.e. dividing or merging pattern sets so as to obtain a dendrogram

Abstract

Methods, systems and computer program products for organizing semi-structured data into taxonomies are described. The semi-structured data is clustered into a plurality of clusters based on a plurality of attributes and the clusters are ranked relative to each other. The attributes are also ranked relative to each other based on a common ranking measure suitable for each of the attributes. The taxonomy may be represented as a hierarchical tree structure comprising a root node and a plurality of child nodes with the root node containing the semi-structured data and each of the child nodes containing data points of a cluster generated from the semi-structured data.

Claims

1. A method for organizing semi-structured data into a taxonomy, said method comprising:

clustering said semi-structured data into a plurality of clusters based on a plurality of attribute types;

ranking said plurality of clusters relative to each other; and

ranking said attributes relative to each other based on a ranking measure.

2. The method of claim 1, wherein said clustering is performed using a plurality of monothetic clustering algorithms, wherein said algorithms are selected based on said attribute types.

3. The method of claim 1, wherein said plurality of attribute types comprise at least one of:

numerical attributes;

categorical attributes;

text attributes; and

annotated text attributes.

4. The method of claim 1, wherein said clusters are ranked based on at least one criterion comprising at least one of:

coverage provided by the number of data points in a cluster;

distinctiveness of a cluster from other clusters; and

average intra-cluster distance.

5. The method of claim 1, wherein said attributes are ranked based on entropy of data for each attribute.

6. The method of claim 1, further comprising representing said taxonomy as a hierarchical tree structure comprising a root node and a plurality of child nodes, said root node containing said semi-structured data and said each of said child nodes containing data points of a cluster generated from said semi-structured data.

7. A method for organizing semi-structured data into a taxonomy, said method comprising:

generating a vocabulary of items from said semi-structured data based on a plurality of different attribute types; and

clustering said semi-structured data by applying monothetic clustering to items in said vocabulary and data samples of said semi-structured data that comprise said items.

8. The method of claim 7, wherein said plurality of different attribute types comprise at least one of:

numerical attributes;

categorical attributes;

text attributes; and

annotated text attributes.

9. The method of claim 8, wherein said generating a vocabulary comprises:

for each numerical attribute of said plurality of attributes;

clustering said semi-structured data based on said numerical attribute; and

treating said numerical attribute based cluster as a categorical attribute; and

adding all possible values of each of said plurality of attributes to said vocabulary.

10. The method of claim 7, wherein said generating a vocabulary of items comprises:

for each categorical attribute, adding attribute value pairs corresponding to all possible values of the categorical attribute to the vocabulary;

for each numerical attribute, clustering the data based on the numerical attribute, considering the numerical-attribute-based clusters as categorical attributes and adding corresponding attribute value pairs to the vocabulary;

for each textual attribute, extracting all possible words or phrases occurring in the values of the attribute and adding corresponding attribute word/phrase pairs to the vocabulary; and

for each annotated textual attribute, adding all possible attribute tag tagged text triplets to the vocabulary.

11. The method of claim 7, wherein said clustering is performed using a plurality of monothetic clustering algorithms, wherein said algorithms are selected based on said attribute types.

12. The method of claim 7, further comprising representing said taxonomy as a hierarchical tree structure comprising a root node and a plurality of child nodes, said root node containing said semi-structured data and each of said child nodes containing data points of a cluster generated from said semi-structured data.

13. An apparatus for organizing semi-structured data into a taxonomy, said apparatus comprising:

a memory unit for storing data and instructions; and

a processing unit coupled to said memory unit, said processing unit programmed to;

perform said instructions;

cluster said semi-structured data into a plurality of clusters based on a plurality of attribute types;

rank said plurality of clusters relative to each other; and

rank said attributes relative to each other based on a ranking measure.

14. The apparatus of claim 13, wherein said processing unit is programmed to perform said clustering using a plurality of monothetic clustering algorithms, wherein said algorithms are selected based on said attribute types.

15. An apparatus for organizing semi-structured data into a taxonomy, said apparatus comprising:

a memory unit for storing data and instructions; and

a processing unit coupled to said memory unit, said processing unit programmed to;

perform said instructions;

generate a vocabulary of items from said semi-structured data based on a plurality of different attribute types; and

cluster said semi-structured data by applying monothetic clustering to items in said vocabulary and data samples of said semi-structured data that comprise said items.

16. The apparatus of claim 15, wherein said processing unit is programmed to:

for each categorical attribute, add attribute value pairs corresponding to all possible values of the categorical attribute to the vocabulary;

for each numerical attribute, cluster the data based on the numerical attribute, treat the numerical-attribute-based clusters as categorical attributes and add corresponding attribute value pairs to the vocabulary;

for each textual attribute, extract all possible words or phrases occurring in the values of the attribute and add corresponding attribute word/phrase pairs to the vocabulary; and

for each annotated textual attribute, add all possible attribute tag tagged text triplets to the vocabulary.

17. A computer program product comprising a computer readable medium comprising a computer program recorded therein for organizing semi-structured data into a taxonomy, said computer program product performing a method comprising:

computer program code for clustering said semi-structured data into a plurality of clusters based on a plurality of attribute types;

ranking said plurality of clusters relative to each other; and

ranking said attributes relative to each other based on a ranking measure.

18. The computer program product of claim 17, wherein said clustering comprises a plurality of monothetic clustering algorithms, wherein said algorithms are selected based on said attribute types.

19. A computer program product comprising a computer readable medium comprising a computer program recorded therein for organizing semi-structured data into a taxonomy, said computer program product perform ing a method comprising:

generating a vocabulary of items from said semi-structured data based on a plurality of different attribute types; and

clustering said semi-structured data by applying monothetic clustering to items in said vocabulary and data samples of said semi-structured data that comprise said items.

20. The computer program product of claim 19, wherein said method further comprises:

computer program code for adding attribute value pairs corresponding to all possible values of each categorical attribute to the vocabulary;

computer program code for clustering the data based on each numerical attribute, treating the numerical-attribute-based clusters as categorical attributes and adding corresponding attribute value pairs to the vocabulary;

computer program code for extracting all possible words or phrases occurring in the values of each textual attribute and adding corresponding attribute word/phrase pairs to the vocabulary; and

computer program code for adding all possible attribute tag tagged text triplets for each annotated textual attribute to the vocabulary.