Method and system for data clustering for very large databases

• US 5,832,182 A
• Filed: 04/24/1996
• Issued: 11/03/1998
• Est. Priority Date: 04/24/1996
• Status: Expired due to Term

• Current Assignee: Wisconsin Alumni Research Foundation (University of Wisconsin System)
• Original Assignee: Wisconsin Alumni Research Foundation (University of Wisconsin System)
• Inventors: Zhang, Tian, Ramakrishnan, Raghu, Livny, Miron
• Primary Examiner(s): MacDonald, Allen R.
• Assistant Examiner(s): Shah, Sanjiv
• Application Number:
  US08/690,876
• Time in Patent Office: 923 Days
• Field of Search: 395/10, 395/11, 395/800.17, 395/703, 395/800, 382/226, 382/145, 364/581, 364/555, 707/101, 348/606, 345/440
• US Class Current: 706/50
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 16/5838 using colour
• CPC Class Codes: G06F 18/23213 with fixed number of clusters, e.g. K-means clustering
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

Multi-dimensional data contained in very large databases is efficiently and accurately clustered to determine patterns therein and extract useful information from such patterns. Conventional computer processors may be used which have limited memory capacity and conventional operating speed, allowing massive data sets to be processed in a reasonable time and with reasonable computer resources. The clustering process is organized using a clustering feature tree structure wherein each clustering feature comprises the number of data points in the cluster, the linear sum of the data points in the cluster, and the square sum of the data points in the cluster. A dense region of data points is treated collectively as a single cluster, and points in sparsely occupied regions can be treated as outliers and removed from the clustering feature tree. The clustering can be carried out continuously with new data points being received and processed, and with the clustering feature tree being restructured as necessary to accommodate the information from the newly received data points.

Claims

1. A method of clustering data, provided by a data source, in a computer processor having a main memory with a limited capacity, comprising the steps of:

(a) receiving data points from the data source;

(b) determining clusters of the data points that are within a selected threshold and determining a clustering feature for each such cluster, the clustering feature comprising the number of data points in the cluster, the linear sum of the data points in the cluster, and the square sum of the data points in the cluster, and storing the clustering feature for each cluster in the main memory; and

(c) forming a clustering feature tree comprised of leaf nodes including leaf entries and at least one level of nodes joined to the leaf nodes, the leaf entries of the tree comprising the clustering features of the clusters, the next highest nodes in the tree above the leaves comprising nonleaf nodes that are each joined to a selected number of different leaves, the selected number comprising a branch number, each nonleaf node distinguished by identifiers stored in the main memory comprising the clustering features of each leaf to which the nonleaf node is joined and pointers indicating the leaves to which the node is joined, and further comprising, as necessary, higher level nodes joined to the branch number of lower level nodes, each higher level node distinguished by identifiers that are stored to main memory which comprise the clustering features for each lower node to which the higher node is joined and pointers indicating the lower nodes to which the higher node is joined, the tree terminating at a root node.

2. The method of claim 1 further comprising the steps of:

(1) receiving a new data point and assigning it to the clustering feature tree by, starting at the root node, assigning the data point to the lower level node that is closest to the data point in accordance with a selected distance measurement using the clustering feature for the lower level node, and continuing down through each of the levels in the tree by assigning the new data point to the closest lower level node by a selected distance measurement until the closest leaf is found in accordance with the selected distance measurement; and

(2) testing the new data point to determine if the new data point is within the threshold to the closest leaf entry in accordance with a selected distance measurement and, if the new data point is within the threshold, revising the clustering feature for the closest leaf entry by adding to it the clustering feature values for the new data point and writing the revised clustering feature for the closest leaf entry to main memory, and if the new data point is not within the threshold, identifying the new data point as a new cluster and a new leaf entry, and if the leaf node containing the new leaf entry cannot accommodate the total number of leaf entries, splitting the leaf node to form two leaf nodes which comprise the leaf entries, and then updating all of the clustering feature identifiers for higher nodes which are on a path to the leaf node and if a split of a leaf node has occurred, splitting higher nodes if necessary to accommodate the split leaf node so that the branch number is not exceeded.

3. The method of claim 2 wherein each node in the clustering feature tree has a given page size in memory, and wherein, at the step of testing a new data point to determine if it is within the threshold, a new leaf cluster is created and one or more higher nodes above the leaves are split, with the split stopping at a higher node, then determining the two closest lower node entries in the node at which the splitting stops and if they are not the pair of lower node entries corresponding to the split, attempting to merge such closest lower nodes corresponding to the two lower node entries, comprising child nodes, and if there are more entries in the two child nodes than one page can hold, splitting the merging result again and if one of the child nodes has sufficient merged entries to fill a page, putting the rest of the entries with the other child node comprising a seed node.

4. The method of claim 2 wherein if a new data point is received which fills the main memory in the computer, increasing the selected threshold, and rebuilding a new and smaller clustering feature tree by reinserting the leaf entries of the old tree into the new tree using the new threshold.

5. The method of claim 4 wherein, when main memory becomes filled, a leaf entry in the tree which has a selected number fewer data points than an average leaf entry is designated as an outlier, and including the step of writing the clustering features for the outlier to an ancillary memory and removing it from the main memory.

6. The method of claim 5 wherein after data points available from the data source have been received and added to the clustering feature tree, when the threshold increases due to a new data point being read after an outlier is written to the disk, if the outlier entry may be absorbed into the new clustering, feature tree using the new threshold without causing the tree to grow in size, absorbing the outlier into the new clustering feature tree.

7. The method of claim 5 wherein the ancillary memory has a limited capacity, and if the capacity of the ancillary memory is filled before all data available from the data source have been received, examining the outliers in the ancillary memory to determine if any of them can be absorbed into the leaves in the current tree as a result of increases in the threshold, and if so, erasing such outliers from the ancillary memory and absorbing each such outlier into the closest leaf entry by adding its clustering feature to the clustering feature of that leaf entry.

8. The method of claim 5 wherein the ancillary memory is a magnetic disk memory.

9. The method of claim 2 wherein the selected threshold is a threshold value for a radius of a cluster, and wherein in the step of testing the new data point, a new radius of the leaf cluster is determined with the new data point included in the cluster and the resulting new radius is compared to the threshold value.

10. The method of claim 2 wherein the selected threshold is a threshold value for a diameter of a cluster, and wherein in the step of testing the new data point a new diameter of the leaf cluster is determined with the new data point included in the cluster and the resulting new diameter compared to the threshold value.

11. The method of claim 2 wherein, after all data points available from the data source have been received and processed, further comprising the steps of:

(1) given a desired number of leaf entries in the clustering feature tree, comparing the actual number of leaf entries in the clustering feature tree to the desired number and if the actual number exceeds the desired number, selecting a new threshold in accordance with a selected distance measurement which is expected to result in a clustering feature tree which has less than the desired number of leaf entries;

(2) freeing the non-leaf nodes of the clustering feature tree;

(3) using the new threshold distance, grouping leaf entries which are within the threshold of each other into single leaf entries and writing the clustering feature of such new leaf entries to main memory, and forming a new clustering feature tree with the new leaf entries so determined;

(4) comparing the number of leaf entries in the new clustering feature tree to the desired number of leaf entries and, if the number is equal to or less than the desired number, stopping the processing, and if the number is greater than the desired number of leaf entries, increasing the threshold to provide a revised threshold, and rebuilding a new and smaller clustering feature tree until the clustering feature tree has less than or equal to the desired number of leaves.

12. The method of claim 11 further comprising the steps of utilizing the clustering features of the leaf entires of the clustering feature tree as initial data objects and applying a selected clustering process to the leaf entry clustering features to provide a cluster result which has a selected number of clusters.

13. The method of claim 12 further comprising the steps of determining the centroids of the final clusters found after the process of claim 12, identifying such centroids as seed points, then reading all of the data points that have been utilized to form the clustering feature tree and determining the clusters of the data points that are closest to the seed points and determining a clustering feature for each such cluster.

14. The method of claim 2 further comprising the steps of utilizing the clustering features of the leaf entries of the clustering feature tree as initial data objects and applying a selected clustering process to the leaf entry clustering features to provide a cluster result which has a selected number of clusters.

15. A processing system for clustering data points provided by a data source, comprising:

(a) a computer processor;

(b) a main memory connected to the processor;

(c) an ancillary memory connected to the processor;

(d) means for receiving the data points from the data source for access by the processor;

(e) means in the processor for analyzing the data points to determine clusters of the data points and to determine a clustering feature for each such cluster which comprises the number of data points in the cluster, the linear sum of the data points in the cluster, and the square sum of the data points in the cluster, and means for storing the clustering feature so determined for each cluster in the main memory.

16. The system of claim 15 including means in the processor for forming a clustering feature tree comprised of leaf nodes including leaf entries and at least one level of nodes joined to the leaf nodes, the leaf entries of the tree comprising the clustering features of the clusters, the next highest nodes in the tree above the leaves comprising nonleaf nodes that are each joined to a selected number of different leaves, the selected number comprising a branch number, means for storing in the main memory identifiers for each nonleaf node comprising the clustering features of each leaf to which the nonleaf node is joined and pointers indicating the leaves to which the node is joined, and means for forming, as necessary, higher level nodes joined to the branch number of lower level nodes, each higher level node distinguished by identifiers that are stored to main memory which comprise the clustering features for each lower node to which the higher node is joined and pointers indicating the lower nodes to which the higher node is joined, the tree terminating at a root node.

17. The system of claim 16 further comprising:

(1) means in the processor for assigning a newly received data point to the clustering feature tree by, starting at the root node, assigning the data point to the lower level node that is closest to the data point in accordance with a selected distance measurement using the clustering feature for the node, and continuing down through each of the lower levels in the tree by assigning the new data point to the closest lower level node by a selected distance measurement until the closest leaf is found in accordance with the selected distance measurement; and

(2) means in the processor for testing the new data point to determine if the new data point is within a selected threshold to the closest leaf entry in accordance with a selected distance measurement and, if the new data point is within the threshold, revising the clustering feature for the closest leaf entry by adding to it the clustering feature values for the new data point and writing the revised clustering feature for the closest leaf entry to the main memory, and if the new data point is not within the threshold, identifying the new data as a new cluster and a new leaf, and if the leaf node containing the new leaf entry cannot accommodate the total number of leaf entries, splitting the leaf node to form two leaf nodes which comprise the leaf entries, and then updating all of the cluster feature identifiers for higher nodes which are on a path to the leaf node and if a split of a leaf node has occurred, splitting higher nodes if necessary to accommodate the split leaf node so that the branch number is not exceeded.

18. The system of claim 17 wherein each node in the clustering feature tree has a given page size in memory, and wherein the means for testing a new data point to determine if it is within the threshold creates a new leaf cluster and splits one or more higher nodes above the leaves, with the split stopping at a higher node, and then determines the two closest lower node entries in the node at which the splitting stops and if they are not the pair of lower node entries corresponding to the split, attempts to merge such closest lower nodes, comprising child nodes, and if there are more entries in the two child nodes than one page can hold, then splits the merging result again and if one of the child nodes has sufficient merged entries to fill a page, then puts the rest of the entries with the other child node comprising a seed node.

19. The system of claim 17 including means for determining if a new data point is received which fills the main memory in the computer, and, if so, for increasing the selected threshold, and rebuilding a new and smaller clustering feature tree by reinserting the leaf entries of the old tree into the new tree using the new threshold distance.

20. The system of claim 19 wherein, when the main memory becomes filled, a leaf entry in the tree which has a selected number fewer data points than an average leaf cluster is designated as an outlier, and including means for writing the clustering features for the outlier to an ancillary memory and removing it from the main memory.

21. The system of claim 20 further including means for determining after data points available from the data source have been received and added to the clustering feature tree, when the threshold increases due to a new data point being read after an outlier is written to the disk, if the outlier may be absorbed into the new clustering feature tree using the new threshold without causing the tree to grow in size, absorbing the outlier into the clustering feature tree.

22. The system of claim 20 wherein the ancillary memory has a limited capacity, and including means for determining if the capacity of the ancillary memory is filled before all data available from the data source have been received and for then examining the outliers in the ancillary memory to determine if any of them can be absorbed into the leaves in the current tree as a result of increases in the threshold, and if so, erasing such outliers from the ancillary memory and absorbing each such outlier into the closest leaf entry by adding its clustering feature to the clustering feature of that leaf entry and storing the result in the main memory.

23. The system of claim 20 wherein the ancillary memory is a magnetic disk memory.

24. The system of claim 17 wherein the selected threshold is a threshold value for a radius of a cluster, and wherein in the means for testing the new data point, a new radius of the leaf cluster is determined with the new data point included in the cluster and the resulting new radius is compared to the threshold value.

25. The system of claim 17 wherein the selected threshold is a threshold value for a diameter of a cluster, and wherein in the step of testing the new data point a new diameter of the leaf cluster is determined with the new data point included in the cluster and the resulting new diameter compared to the threshold value.

26. A processing system for clustering data points provided by a data source comprising:

(a) a computer processor;

(b) a main memory connected to the processor, the main memory having a clustering feature tree stored therein comprised of leaf nodes including leaf entries and at least one level of nodes joined to the leaf nodes, the leaf entries of the tree comprising clustering features of the cluster, each clustering feature comprising the number of data points in the cluster, the linear sum of the data points in the cluster, and the square sum of the data points in the cluster, the next highest nodes in the tree above the leaves comprising nonleaf nodes that are each joined to a selected number of different leaves, the selected number comprising a branch number, each nonleaf node distinguished by identifiers stored in the main memory comprising the clustering features of each leaf to which the nonleaf node is joined and pointers indicating the leaves to which the node is joined, and further comprising, as necessary, higher level nodes joined to the branch number of lower level nodes, each higher level node distinguished by identifiers that are stored to main memory which comprise the clustering features for each lower node to which the higher node is joined and pointers indicating the lower nodes to which the higher node is joined, the tree terminating at a root node;

(c) an ancillary memory connected to the processor;

(d) means for receiving the data points from the data source for access by the processor;

(e) means in the processor for receiving a new data point and assigning it to the clustering feature tree by, starting at the root node, assigning the data point to the lower level node that is closest to the data point in accordance with a selected distance measurement using the clustering feature for the lower level node, and continuing down through each of the levels in the tree by assigning the new data point to the closest lower level node by a selected distance measurement until the closest leaf is found in accordance with the selected distance measurement; and

(f) means for testing the new data point to determine if the new data point is within a selected threshold distance to the closest leaf entry in accordance with the selected distance measurement and if so, revising the clustering feature for the closest leaf entry by adding to it the clustering feature values for the new data point and writing the revised clustering feature for the closest leaf entry to main memory, and if the new data point is not within the threshold, identifying the new data as a cluster and a new leaf entry, and if the leaf node containing the new leaf entry cannot accommodate the total number of leaf entries, splitting the leaf node to form two leaf nodes which are comprised of leaf entries, and then updating all of the clustering feature identifiers for higher nodes which are on a path to the leaf node and if a split of a leaf node has occurred, splitting higher nodes if necessary to accommodate the split leaf node so that the branch number is not exceeded.

27. The system of claim 26 wherein each node in the clustering feature tree has a given page size in memory, and wherein the means for testing a new data point to determine if it is within the threshold creates a new leaf cluster and splits one or more higher nodes above the leaves, with the split stopping at a higher node, and then determines the two closest lower node entries in the node at which the splitting stops and, if they are not the pair of lower node entries corresponding to the split, attempts to merge such closest lower node entries, comprising child nodes, and if there are more entries in the two child nodes than one page can hold, then splits the merging result again and if one of the child nodes has sufficient merged entries to fill a page, puts the rest of the entries with the other child node comprising a seed node.

28. The system of claim 26 including means for determining if a new data point is received which fills the main memory in the computer, and, if so, for increasing the selected threshold, and rebuilding a new and smaller clustering feature tree by reinserting the leaf entries of the old tree into the new tree using the new threshold.

29. The system of claim 26 wherein, when the main memory becomes filled, a leaf entry in the old tree which has a selected number of fewer data points than an average leaf entry is designated as an outlier, and including means for writing the clustering features for the outlier to the ancillary memory and removing it from the main memory.

30. The system of claim 29 further including means for determining after data points available from the data source have been received and added to the clustering feature tree, when the threshold increases due to a new data point being read after an outlier is written to the ancillary memory, if the outlier entry may be absorbed into the new clustering feature tree using the new threshold, absorbing the outlier into the clustering feature tree.

31. The system of claim 29 wherein the ancillary memory has a limited capacity, and including means for determining if the capacity of the ancillary memory is filled before all data available from the data source have been received and for then examining the outliers in the ancillary memory to determine if any of them can be absorbed into the leaves in the current tree as a result of increases in the threshold, and if so, erasing such outliers from the ancillary memory and absorbing each such outlier into the closest leaf entry by adding its clustering feature to the clustering feature of that leaf entry and storing the result in the main memory.

32. The system of claim 29 wherein the ancillary memory is a magnetic disk memory.

33. The system of claim 27 wherein the selected threshold is a threshold value for a radius of a cluster, and wherein in the means for testing the new data point, a new radius of the leaf cluster is determined with the new data point included in the cluster and the resulting new radius is compared to the threshold value.

34. The system of claim 27 wherein the selected threshold is a threshold value for a diameter of a cluster, and wherein in the step of testing the new data point a new diameter of the leaf cluster is determined with the new data point included in the cluster and the resulting new diameter compared to the threshold value.