Data classification and hierarchical clustering

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:

n

=

i

+

(

i

×

log

⁢

f

i

)

,

where i =number of training instances and f=total number of available size-1 patterns.

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.