Unsupervised information-based hierarchical clustering of big data
A hierarchical cluster analyzer identifies clusters in a big data set by identifying topological structure without distance-based metrics. The hierarchical cluster analyzer stochastically partitions the big data set to create pseudo-partitions of the big data set. The stochastic partitioning may be implemented with a random forest classifier that uses ensemble techniques to reduce variance and prevent overfitting. The hierarchical cluster analyzer implements random intersection leaves (RIL), a data mining technique that grows an intersection tree by intersecting candidate sets generated from the pseudo-partitions. The hierarchical cluster analyzer updates an association matrix according to co-occurrences of data points within each leaf node of the intersection tree. These co-occurring data points exhibit a high degree of similarity, which is recorded in the association matrix. A hierarchy of clusters may then be formed by finding community structure in the association matrix.
1 . A method, comprising:
stochastically partitioning a data set to create a plurality of pseudo-partitions of the data set, the data set comprising a plurality of data points, each of the plurality of pseudo-partitions comprising a plurality of subsets whose union is a subset of the data set;
forming each of a plurality of candidate sets based on one or more subsets selected from the plurality of subsets of each pseudo-partition of two or more pseudo-partitions of the plurality of pseudo-partitions;
creating each of a plurality of intersection sets based on two or more candidate sets selected from the plurality of candidate sets;
identifying, within each of the plurality of intersection sets, one or more co-occurrences of a plurality of co-occurrences of the plurality of data points;
constructing a graph having a plurality of vertices connected by a plurality of edges, each vertex of the plurality of vertices representing a respective one of the plurality of data points, each edge of the plurality of edges connecting two vertices of the plurality of vertices, said each edge representing a number of the co-occurrences for the two data points represented by the two vertices;
identifying a community in the graph, the community comprising member vertices of the plurality of vertices; and
outputting a cluster of the data set, the cluster comprising member data points, of the plurality of data points, that are represented by the member vertices of the community.
2 . The method of claim 1 , wherein said creating the plurality of pseudo-partitions comprises partitioning the data set.
3 . The method of claim 1 , wherein said forming each of the plurality of candidate sets comprises:
selecting the one or more subsets from the plurality of subsets of each pseudo-partition of the two or more pseudo-partitions; and
taking a union of the selected one or more subsets.
4 . The method of claim 3 , wherein said selecting comprises randomly selecting the one or more subsets.
5 . The method of claim 1 , wherein said creating each of the plurality of intersection sets comprises:
selecting the two or more candidate sets from the plurality of candidate sets; and
taking an intersection of the selected two or more candidate sets.
6 . The method of claim 5 , wherein said selecting comprises randomly selecting the two or more candidate sets.
7 . The method of claim 1 , wherein said identifying the one or more co-occurrences comprises generating an association matrix of the plurality of co-occurrences.
8 . The method of claim 7 , wherein said identifying the community comprises clustering the association matrix.
9 . The method of claim 1 , wherein said creating each of the plurality of intersection sets comprises growing an intersection tree with at least some of the plurality of candidate sets such that each of a plurality of leaf nodes of the intersection tree stores an intersection of several of the plurality of candidate sets.
10 . A system, comprising:
storage configured to store a data set comprising a plurality of data points;
a processor; and
a hierarchical clustering engine, implemented as machine-readable instructions stored in a memory in electronic communication with the processor, that, when executed by the processor, control the system to:
stochastically partition a data set to create a plurality of pseudo-partitions of the data set, each of the plurality of pseudo-partitions comprising a plurality of subsets whose union is a subset of the data set,
form each of a plurality of candidate sets based on one or more subsets selected from the plurality of subsets of each pseudo-partition of two or more pseudo-partitions of the plurality of pseudo-partitions,
create each of a plurality of intersection sets based on two or more candidate sets selected from the plurality of candidate sets,
identify, with each of the plurality of intersection sets, one or more co-occurrences of a plurality of co-occurrences of the plurality of data points,
construct a graph having a plurality of vertices connected by a plurality of edges, each vertex of the plurality of vertices representing a respective one of the plurality of data points, each edge of the plurality of edges connecting two vertices of the plurality of vertices, said each edge representing a number of the co-occurrences for the two data points represented by the two vertices,
identify a community in the graph, the community comprising member vertices of the plurality of vertices, and
output a cluster of the data set, the cluster comprising member data points, of the plurality of data points, that are represented by the member vertices of the community.
11 . The system of claim 10 , wherein the machine-readable instructions that, when executed by the processor, control the system to create the plurality of pseudo-partitions comprise machine-readable instructions that, when executed by the processor, control the system to partition the data set.
12 . The system of claim 10 , wherein the machine-readable instructions that, when executed by the processor, control the system to form each of the plurality of candidate sets comprise machine-readable instructions that, when executed by the processor, control the system to:
select the one or more subsets from the plurality of subsets of each pseudo-partition of the two or more pseudo-partitions, and
take a union of the selected one or more subsets.
13 . The system of claim 12 , wherein the machine-readable instructions that, when executed by the processor, control the system to select the one or more subsets comprise machine-readable instructions that, when executed by the processor, control the system to randomly select the one or more subsets.
14 . The system of claim 10 , wherein the machine-readable instructions that, when executed by the processor, control the system to create each of the plurality of intersection sets comprise machine-readable instructions that, when executed by the processor, control the system to:
select the two or more candidate sets from the plurality of candidate sets, and
take an intersection of the selected two or more candidate sets.
15 . The system of claim 14 , wherein the machine-readable instructions that, when executed by the processor, control the system to select the two or more candidate sets comprise machine-readable instructions that, when executed by the processor, control the system to randomly select the two or more candidate sets.
16 . The system of claim 10 , wherein the machine-readable instructions that, when executed by the processor, control the system to identify the one or more co-occurrences comprise machine-readable instructions that, when executed by the processor, control the system to generate an association matrix of the plurality of co-occurrences.
17 . The system of claim 16 , wherein the machine-readable instructions that, when executed by the processor, control the system to identify the community comprise machine-readable instructions that, when executed by the processor, control the system to cluster the association matrix.
18 . The system of claim 10 , wherein the machine-readable instructions that, when executed by the processor, control the system to create each of the plurality of intersection sets comprises machine-readable instructions that, when executed by the processor, control the system to grow an intersection tree with at least some of the plurality of candidate sets such that each of a plurality of leaf nodes of the intersection tree stores an intersection of several of the plurality of candidate sets.