Computer implemented scalable, incremental and parallel clustering based on weighted divide and conquer

• US 6,907,380 B2
• Filed: 12/01/2003
• Issued: 06/14/2005
• Est. Priority Date: 05/10/2001
• Status: Expired due to Term

• Current Assignee: Micro Focus LLC (Open Text Corporation)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Guha, Sudipto, O'Callaghan, Liadan, Mishra, Nina, Motwani, Rajeev
• Primary Examiner(s): Hoff, Marc S.
• Assistant Examiner(s): Barbee, Manuel L.
• Application Number:
  US10/726,254
• Publication Number:
  US 20040122797A1
• Time in Patent Office: 561 Days
• Field of Search: 702/80, 702/97, 702/1.58, 702179-181, 702/187, 707/6, 707/7
• US Class Current: 702/179
• CPC Class Codes: G06F 18/23 Clustering techniques
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99937 Sorting

Abstract

A technique that uses a weighted divide and conquer approach for clustering a set S of n data points to find k final centers. The technique comprises 1) partitioning the set S into P disjoint pieces S₁, . . . , S_p; 2) for each piece S_i, determining a set D_i of k intermediate centers; 3) assigning each data point in each piece S_i to the nearest one of the k intermediate centers; 4) weighting each of the k intermediate centers in each set D_i by the number of points in the corresponding piece S_i assigned to that center; and 5) clustering the weighted intermediate centers together to find said k final centers, the clustering performed using a specific error metric and a clustering method A.

Claims

1. A method for clustering a set S of n data points to find k final centers, comprising:

partitioning said set S into P disjoint pieces S₁, . . . ,S_P;

for each said piece S_i, determining a set D_i of k intermediate centers;

assigning each data point in each piece S_i to the nearest one of said k intermediate centers;

weighting each of said k intermediate centers in each set D_i by the number of points in the corresponding piece S_i assigned to that center; and

clustering said weighted intermediate centers together to find said k final centers, said clustering performed using a specific error metric and a clustering method A.

2. The method according to claim 1 wherein P is sufficiently large enough such that each piece Si obeys the constraint |S_i|<

M, where M is the size of a physical memory or a portion thereof to be used in processing said each piece.

3. The method according to claim 1 wherein said clustering is performed upon iteratively obtained weighted intermediate clusters.

4. The method according to claim 1 wherein said set S is replaced by weighted intermediate centers of the previous iteration when iteratively performing said partitioning, determining, assigning, and weighting.

5. The method according to claim 1 wherein said determining is performed using said specific error metric and said clustering method A.

6. The method according to claim 1 wherein said specific error metric is the minimizing of the sum of the squares of the distances between points and their nearest centers.

7. The method according to claim 6 wherein the distance is the Euclidean distance.

8. The method according to claim 1 wherein said specific error metric is the minimizing of the sum of the distances between points and their nearest centers.

9. The method according to claim 8 wherein the distance is the Euclidean distance.

10. The method according to claim 1 wherein said clustering method is an approximation-based method.

11. The method according to claim 1 further comprising:

considering a second set of data points for obtaining a second k final centers after said set S is clustered;

repeating partitioning, determining, assigning and weighting for said second set of data points; and

clustering weighted intermediate centers obtained from said second set of data points together with said weighted intermediate centers obtained from said data set S, said clustering performed using said specific error metric and said clustering method A.

12. The method according to claim 1 wherein said partitioning, detennining, assigning and weighting is performed in parallel for each piece S_i.

13. An article comprising a computer readable medium having instructions stored thereon which when executed causes clustering a set S of n data points to find k final centers, said clustering implemented by:

partitioning said set S into P disjoint pieces S₁, . . . ,S_P;

for each said piece S_i, determining a set D_i of k intermediate centers;

assigning each data point in each piece S_i to the nearest one of said k intermediate centers;

weighting each of said k intermediate centers in each set D_i by the number of points in the corresponding piece S_i, assigned to that center; and

clustering said weighted intermediate centers together to find said k final centers, said clustering performed using a specific error metric and a clustering method A.

14. The article according to claim 13 wherein P is sufficiently large enough such that each piece S_i, obeys the constraint |S_i|<

M, where M is the size of a physical memory or a portion thereof to be used in processing said each piece.

15. The article according to claim 13 further implemented by:

considering a second set of data points for obtaining a second k final centers after said set S is clustered;

repeating partitioning, determining, assigning and weighting for said second set of data points; and

clustering weighted intermediate centers obtained from said second set of data points together with said weighted intermediate centers obtained from said data set S, said clustering performed using said specific error metric and said clustering method A, resulting in said second k final clusters.

16. The article according to claim 13 wherein said partitioning, determining, assigning and weighting is performed in parallel for each piece S.

17. An apparatus for clustering a set S of n data points to find k final centers, said apparatus comprising:

a main memory;

a processor coupled to said memory, said processor configured to partition said set S into P disjoint pieces S_i, . . . , S_P such that each piece S_i fits in main memory, said each piece S_i first stored separately in said main memory and then clustered by said processor performing;

for each said piece S_i, determining a set D_i of k intermediate centers;

assigning each data point in each piece S_i, to the nearest one of said k intermediate centers;

weighting each of said k intermediate centers in each set D_i by the number of points in the corresponding piece S_i, assigned to that center; and

clustering said weighted intermediate centers together to find said k final centers, said clustering performed using a specific error metric and a clustering method A.

18. An apparatus for clustering a set S of n data points to find k final centers, said apparatus comprising:

a main memory;

a plurality of processors coupled to said main memory, one of said processors configured to partition said set S into P disjoint pieces S₁, . . . , S_P such that each piece S_i, fits in main memory, said each piece S_i, first stored separately in said main memory and then clustered by each said processor performing;

for each said piece S_i, determining a set D_i of k intermediate centers;

assigning each data point in each piece S_i, to the nearest one of said k intermediate centers; and

weighting each of said k intermediate centers in each set D_i by the number of points in the corresponding piece S_i, assigned to that center, further wherein after said weighting, one of said processors finally clustering said weighted intermediate centers together to find said k final centers, said clustering performed using a specific error metric and a clustering method A.