Method and apparatus to cluster binary data transactions
View Patent ↗A database system is capable of clustering data in received transactions. Clustering is based on sparse distance computations and/or simplified sufficient statistics. Each of the received transactions contain attributes or dimensions that are binary data. In some implementations, a summary table is also output to enable convenient viewing of the results of clustering.
1. An article comprising at least one storage medium containing instructions that when executed cause a system to:
perform a K-means clustering technique on input data;
perform sparse distance computations in the K-means clustering technique;
define clusters with the K-means clustering technique using sparse distance computations;
wherein the input data is a data set D including a plurality of d-dimensional transactions, each d-dimensional transaction having d attributes, wherein the data set D is to be divided into k clusters, and wherein the instructions when executed cause the system to further produce a d×k matrix C, each element C lj ( =1 to d, j=1 to k) of the matrix C containing a percentage indicating probability of occurrence of attribute l in cluster k;
compute statistics including a k×1 matrix M containing a sum of points per cluster, and a k×1 matrix N containing a number of points per cluster; and
compute the matrix C based on M and N without using a matrix Q that contains a sum of squared points per cluster.
2. The article of claim 1 , wherein the instructions when executed cause the system to further produce a summary table that summarizes a portion of C.
3. The article of claim 2 , wherein the instructions when executed cause the system to further display the summary table.
4. The article of claim 2 , wherein the instructions when executed cause the system to further produce outlier data for insertion into the summary table.
5. The article of claim 2 , wherein the instructions when executed cause the system to further insert attributes of the data set D into the summary table that are associated with C lj being greater than a predetermined percentage.
6. The article of claim 5 , wherein the instructions when executed cause the system to further define cutoff points,
wherein inserting attributes of the data set D into the summary table comprises inserting attributes of the data set D into the summary table where attributes are associated with C lj within the ranges defined by the cutoff points.
7. A database system comprising:
a storage; and
a controller coupled to the storage to:
receive input transactions;
determine clusters of data from the input transactions;
compute data structures defining the clusters based on first and second statistics, the first statistic containing sums of points in corresponding clusters, and the second statistic containing numbers of points in corresponding clusters, wherein computing the data structures defining the clusters is performed based on the first and second statistics without using a third statistic that contains sums of squared points in corresponding clusters;
wherein the input transactions are part of a data set D including a plurality of d-dimensional transactions, each d-dimensional transaction having d attributes, wherein the controller is adapted to divide the data set D into k clusters, and wherein the data structures comprise a d×k matrix C, each element C lj ( =1 to d, j=1 to k) of matrix C containing a percentage indicating probability of occurrence of attribute l in cluster k;
compute statistics including a k×1 matrix M containing a sum of points per cluster, and a k×1 matrix N containing a number of points per cluster; and
compute the matrix C based on M and N without using a matrix Q that contains a sum of squared points per cluster.
8. A method of clustering data, comprising the steps of:
performing a K-means clustering technique on input data;
performing sparse distance computations in the K-means clustering technique;
defining clusters with the K-means clustering technique using sparse distance computations;
wherein the input data is a data set D including a plurality of d-dimensional transactions, each d-dimensional transaction having d attributes, wherein the data set D is to be divided into k clusters, and wherein the instructions when executed cause the system to further produce a d×k matrix C, each element C lj ( =1 to d, j=1 to k) of the matrix C containing a percentage indicating probability of occurrence of attribute l in cluster k;
computing statistics including a k×1 matrix M containing a sum of points per cluster and a k×1 matrix N containing a number of points per cluster; and
computing the matrix C based on M and N without using a matrix Q that contains a sum of squared points per cluster.
9. The method according to claim 8 , further comprising the step of:
producing a summary table that summarizes a portion of matrix C.
10. The method according to claim 9 , further comprising the step of:
displaying the summary table.
11. The method according to claim 9 , further comprising the step of:
producing outlier data for insertion into the summary table.
12. The method according to claim 9 , further comprising the step of:
inserting attributes of the data set D into the summary table that are associated with C lj being greater than a predetermined percentage.
13. The method according to claim 12 , further comprising the steps of defining cutoff points, and wherein said step of inserting attributes of the data set D into the summary table comprises inserting attributes of the data set D into the summary table where attributes are associated with C cj within the ranges defined by the cutoff points.