Data classification and hierarchical clustering

• US 8,407,164 B2
• Filed: 06/11/2008
• Issued: 03/26/2013
• Est. Priority Date: 10/02/2006
• Status: Expired due to Fees

• Current Assignee: Trustees Of Columbia University In The City Of New York (Columbia University)
• Original Assignee: Trustees Of Columbia University In The City Of New York (Columbia University)
• Inventors: Malik, Hassan Haider, Kender, John Ronald
• Primary Examiner(s): Chaki, Kakali
• Assistant Examiner(s): HANCHAK, WALTER P
• Application Number:
  US12/602,908
• Publication Number:
  US 20100174670A1
• Time in Patent Office: 1,749 Days
• Field of Search: None
• US Class Current: 706/12
• CPC Class Codes: G06F 16/35 Clustering; Classification
• CPC Class Codes: G06F 18/231 Hierarchical techniques, i.e. dividing or merging pattern sets so as to obtain a dendrogram

Abstract

Apparatus, systems, and methods can operate to provide efficient data clustering, data classification, and data compression. A method comprises training set of training instances can be processed to select a subset of size-1 patterns, initialize a weight of each size-1 pattern, include the size-1 patterns in classes in a model associated with the training set, and then include a set of top-k size-2 patterns in a way that provides an effective balance between local, class, and global significance patterns. A method comprises processing a dataset to compute an overall significance value of each size-2 pattern in each instance in the dataset, sort the size-2 patterns, and select the top-k size-2 patterns to be represented in clusters, which can be refined into a clustered hierarchy. A method comprises creating an uncompressed bitmap, reordering the bitmap, and compressing the bitmap. Additional apparatus, systems, and methods are disclosed.

Claims

1. A computer-implemented method comprising:

using a computer comprising a processor to perform;

initializing a model, the model including a plurality of classes;

selecting subsets of patterns from a set of available patterns in a training instance selected from a training set of training instances, the selecting subsets including selecting a subset of size-1 patterns and selecting a subset of size-2 patterns;

initializing a weight of each size-1 pattern in the subset of size-1 patterns;

including each size-1 pattern in the subset of size-1 patterns in each class in the plurality of classes in the model;

calculating an overall significance value of each size-2 pattern in the training instance;

sorting the size-2 patterns using the overall significance;

selecting the highest k sorted size-2 patterns;

initializing a weight of each selected highest k size-2 pattern;

adjusting the weights on the size-1 and size-2 patterns; and

presenting the model organized with the plurality of classes, each class including the size-1 patterns, the highest k size-2 patterns, and the weights of the size-1 and size-2 patterns.

2. The computer-implemented method of claim 1, comprising:

calculating a local, class, and global significance value for each size-2 pattern in the training instance, wherein at least the local and global significance values are calculated using different methods; and

using the local, class, and global values to calculate the overall significance.

3. The computer-implemented method of claim 2, wherein the local significance value is calculated by calculating a central tendency of the term frequency values of a first size-1pattern and a second size-1 pattern that compose the size-2 pattern, the term frequency indicating how frequently a size-1 pattern occurs in a particular training instance.

4. The computer-implemented method of claim 2, wherein the global significance value is calculated by applying an interestingness measure to the size-2 pattern with respect to the training instance.

5. The computer-implemented method of claim 4, wherein the interestingness measure is selected from the group consisting of:

Added Value, Mutual Information, Chi-Square, and Yule'"'"'s Q.

6. The computer-implemented method of claim 1, wherein selecting the subset of size-1 patterns comprises:

determining a number n of size-1 patterns to use for classification;

including the top n globally significant size-1 patterns from the training set in the selected subset of size-1 patterns; and

adding size-1 patterns that are locally significant to each training instance in the training set to the selected subset of size-1 patterns.

7. The computer-implemented method of claim 6, wherein the number n is calculated using number of training instances and a total number of available size-1 patterns.

8. The computer-implemented method of claim 7, wherein the number n is calculated using the equation:

9. The computer-implemented method of claim 2, wherein selecting globally significant features comprises:

selecting size-1 patterns having a frequency in the training set between a specified lower bound and a specified upper bound;

sorting the selected size-1 patterns according to their Information Gain values; and

selecting the resulting top-n size-1 patterns as being globally significant size-1 patterns.

10. The computer-implemented method of claim 1, wherein adjusting the weights on the size-1 and size-2 patterns comprises using z-score normalization.

11. The computer-implemented method of claim 1, comprising:

creating an uncompressed bitmap representation of each training instance in, each bitmap representation including a plurality of n ordered bits, each bit indicating whether a corresponding item selected from a set of n items is present in the corresponding instance;

reordering the bitmap representations of the instances into an order that reduces or minimizes Hamming-distances; and

compressing the reordered bitmap representations.

12. A system comprising:

a memory; and

a control module coupled to the memory, the control module comprising;

a first initialization module to initialize a model, the model including a plurality of classes;

a first selection module to select subsets of patterns from a set of available patterns in a training instance selected from a training set of training instances, the selecting subsets including selecting a subset of size-1 patterns and selecting a subset of size-2 patterns;

a second initialization module to initialize a weight of each size-1 pattern in the subset of size-1 patterns;

an organization module to include each size-1 pattern in the subset of size-1 patterns in each class in the plurality of classes in the model;

a first calculation module to calculate an overall significance value of each size-2 pattern in the training instance;

a sorting module to sort the size-2 patterns using the overall significance;

a second selection module to select the highest k sorted size-2 patterns;

a third initialization module to initialize a weight of each selected highest k size-2 pattern;

an adjustment module to adjust the weights on the size-1 and size-2 patterns; and

a presentation module to present the model organized with the plurality of classes, each class including the size-1 patterns, the highest k size-2 patterns, and the weights of the size-1 and size-2 patterns.

13. The system of claim 12, comprising:

a second calculation module to calculat a local, class, and global significance value for each size-2 pattern in the training instance, wherein at least the local and global significance values are calculated using different methods; and

a second organization module to use the local, class, and global values to calculate the overall significance.

14. The system of claim 13, wherein the local significance value is calculated by calculating a central tendency of the term frequency values of a first size-1 pattern and a second size-1 pattern that compose the size-2 pattern, the term frequency indicating how frequently a size-1 pattern occurs in a particular training instance.

15. A non-transitory machine-readable medium including instructions, which when executed by a machine, cause the machine to perform operations comprising:

initializing a model, the model including a plurality of classes;

selecting subsets of patterns from a set of available patterns in a training instance selected from a training set of training instances, the selecting subsets including selecting a subset of size-1 patterns and selecting a subset of size-2 patterns;

initializing a weight of each size-1 pattern in the subset of size-1 patterns;

including each size-1 pattern in the subset of size-1 patterns in each class in the plurality of classes in the model;

calculating an overall significance value of each size-2 pattern in the training instance;

sorting the size-2 patterns using the overall significance;

selecting the highest k sorted size-2 patterns;

initializing a weight of each selected highest k size-2 pattern;

adjusting the weights on the size-1 and size-2 patterns; and

presenting the model organized with the plurality of classes, each class including the size-1 patterns, the highest k size-2 patterns, and the weights of the size-1 and size-2 patterns.

16. A computer-implemented method comprising:

using a computer comprising a processor to perform;

receiving a dataset comprising a plurality of instances, each instance including a plurality of size-2 patterns;

for each instance in the dataset;

computing an overall significance value of each size-2 pattern in the instance;

sorting the plurality of size-2 patterns in the instance based on the overall significance value;

selecting the top-k size-2 patterns, the k value being specified; and

including the top-k size-2 patterns in a cluster in a set of clusters; and

presenting the set of clusters of top-k size-2 patterns.

17. The computer-implemented method of claim 16, comprising:

calculating a local and global significance value for each size-2 pattern in the instance, wherein at least the local and global significance values are calculated using different methods; and

using the local and global values to calculate the overall significance.

18. The computer-implemented method of claim 16, comprising:

reducing the dimensionality of the dataset before processing the instances, the reducing the dimensionality performed to provide a reduced dataset.

19. The computer-implemented method of claim 18, wherein reducing the dimensionality comprises:

selecting size-1 patterns having a frequency in the dataset that is between a specified lower bound and a specified upper bound;

sorting the selected size-1 patterns according to the frequency of the pattern in the dataset; and

including the top-t sorted size-1 patterns in the reduced dataset, wherein t is a specified value.

20. The computer-implemented method of claim 16, wherein selecting the top-k size-2 patterns comprises:

determining whether a size-2 pattern has a significance value above a minimum acceptable significance value; and

including the size-2 pattern in the selected top-k size-2 patterns when the significance value is above the minimum acceptable significance value.

21. The computer-implemented method of claim 20, wherein the minimum acceptable significance value is calculated as a function of a measure of centrality and a measure of dispersion of the overall significance values.

22. The computer-implemented method of claim 16, comprising pruning duplicate clusters after all instances in the dataset have been processed.

23. The computer-implemented method of claim 16, comprising refining the set of clusters, wherein refining the set of clusters comprises:

identifying cluster pairs from non-atomic clusters that share at least one instance; and

merging the shared instances into a child cluster in the set of clusters.

24. The computer-implemented method of claim 16, wherein selecting the top-k size-2 patterns comprises allowing each instance to “

vote”

for a specified number of representative size-2 patterns.

25. The computer-implemented method of claim 16, wherein selecting the top-k size-2 patterns is performed without using a global threshold that applies across the entire dataset.

26. The computer-implemented method of claim 16, comprising:

creating an uncompressed bitmap representation of each instance in the dataset, each bitmap representation including a plurality of n ordered bits, each bit indicating whether a corresponding item selected from a set of n items is present in the corresponding instance;

reordering the bitmap representations of the instances into an order that reduces or minimizes at least approximate Hamming-distances; and

compressing the reordered bitmap representations.

27. A system comprising:

a memory; and

a control module coupled to the memory, the control module comprising;

a receiving module to receive a dataset comprising a plurality of instances, each instance including a plurality of size-2 patterns;

a looping module to loop for each instance in the dataset;

a computation module to compute an overall significance value of each size-2 pattern in the instance;

a sorting module to sort the plurality of size-2 patterns in the instance based on the overall significance value;

a selection module to select the top-k size-2 patterns, the k value being specified; and

an organization module to include the top-k size-2 patterns in a cluster in a set of clusters; and

a presentation module to present the set of clusters of top-k size-2 patterns.

28. The system of claim 27, wherein the selection module is further configured to:

determine whether a size-2 pattern has a significance value above a minimum acceptable significance value; and

include the size-2 pattern in the selected top-k size-2 patterns when the significance value is above the minimum acceptable significance value.

29. The system of claim 28, wherein the minimum acceptable significance value is calculated as a function of a measure of centrality and a measure of dispersion of the overall significance values.

30. A non-transitory machine-readable medium including instructions, which when executed by a machine, cause the machine to perform operations comprising:

receiving a dataset comprising a plurality of instances, each instance including a plurality of size-2 patterns;

for each instance in the dataset;

computing an overall significance value of each size-2 pattern in the instance;

sorting the plurality of size-2 patterns in the instance based on the overall significance value;

selecting the top-k size-2 patterns, the k value being specified; and

including the top-k size-2 patterns in a cluster in a set of clusters; and

presenting the set of clusters of top-k size-2 patterns.