US6049797A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method, apparatus and programmed medium for clustering databases with categorical attributes
Assignee: Nokia of America Corp
•
Filing: 1998-04-07
•
Granted: 2000-04-11
•
Expires: 2018-04-07
Abstract
Abstract The present invention relates to a computer method, apparatus and programmed medium for clustering databases containing data with categorical attributes. The present invention assigns a pair of points to be neighbors if their similarity exceeds a certain threshold. The similarity value for pairs of points can be based on non-metric information. The present invention determines a total number of links between each cluster and every other cluster bases upon the neighbors of the clusters. A goodness measure between each cluster and every other cluster based upon the total number of links between each cluster and every other cluster and the total number of points within each cluster and every other cluster is then calculated. The present invention merges the two clusters with the best goodness measure. Thus, clustering is performed accurately and efficiently by merging data based on the amount of links between the data to be clustered.
Inventors
- 👤 Sudipto Guha
- 👤 Rajeev Rastogi
- 👤 Kyuseok Shim
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-27 23:18
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/28; G06F16/284; G06F16/285; G06F18/00; G06F18/20; G06F18/23; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99932; Y10S707/99933; Y10S707/99935; Y10S707/99936; Y10S707/99941; Y10S707/99942; Y10S707/99944; Y10S707/99945
Claims Analysis
Total Claims: 63
Claim 1
Independent Claim
171 words
A computer based method of clustering related data stored in a computer database, said computer database stored on a computer readable medium and including a set of data points having categorical attributes, the method comprising the steps of: a) determining all neighbors for every data point within said computer database; b) establishing a cluster for every data point in said computer database; c) determining a total number of links between each cluster and every other cluster based on a number of common neighbors between each cluster and every other cluster; d) calculating a goodness measure between each cluster and every other cluster based upon the total number of links between each cluster and every other cluster and an estimated number of links between each cluster and every other cluster; e) merging a pair of clusters having the best goodness measures into a merged cluster; f) repeating steps c) through e) until a predetermined termination condition is met; and g) storing clusters which remain after step f) in a computer readable medium.
Claim 2
Dependent Claim
171 words
A computer based method of clustering related data stored in a computer database, said computer database stored on a computer readable medium and including a set of data points having categorical attributes, the method comprising the steps of: a) determining all neighbors for every data point within said computer database; b) establishing a cluster for every data point in said computer database; c) determining a total number of links between each cluster and every other cluster based on a number of common neighbors between each cluster and every other cluster; d) calculating a goodness measure between each cluster and every other cluster based upon the total number of links between each cluster and every other cluster and an estimated number of links between each cluster and every other cluster; e) merging a pair of clusters having the best goodness measures into a merged cluster; f) repeating steps c) through e) until a predetermined termination condition is met; and g) storing clusters which remain after step f) in a computer readable medium.
Claim 3
Dependent Claim
17 words
The method of claim 1 wherein the predetermined termination condition is obtaining a desired number of clusters.
Claim 4
Dependent Claim
24 words
The method of claim 1 wherein the predetermined termination condition is obtaining remaining clusters that do not have any links between said remaining clusters.
Claim 5
Dependent Claim
30 words
The method of claim 1 wherein the step of determining all neighbors for every data point within said computer database is determined by calculating a similarity between said data points.
Claim 6
Dependent Claim
37 words
The method of claim 4 wherein calculating the similarity between said data points comprises the steps of: a1) calculating a similarity ratio; and a2)assigning said points to be neighbors if said similarity ratio exceeds a similarity threshold.
Claim 7
Dependent Claim
18 words
The method of claim 5 wherein said similarity threshold is selected from the range of 0.5 to 0.8.
Claim 8
Dependent Claim
29 words
The method of claim 5 wherein the calculation of said similarity ratio is performed by dividing an intersection of said data points by a union of said data points.
Claim 9
Dependent Claim
191 words
A computer based method of clustering related data in a large computer database, said large computer database stored on a computer readable medium and including a set of data points having categorical attributes, the method comprising the steps of: a) selecting a random set of data points from said large computer database; b) determining all neighbors for every data point within said random set of data points; c) establishing a cluster for every data point within said random set of data points; d) determining a total number of links between each cluster and every other cluster based on a number of common neighbors between each cluster and every other cluster; e) calculating a goodness measure between each cluster and every other cluster based upon the total number of links between each cluster and every other cluster and an estimated number of links between each cluster and every other cluster; f) merging a pair of clusters having the best goodness measures into a merged cluster; g) repeating steps d) through f) until a predetermined termination condition is met; and h) storing clusters which remain after step g) in a computer readable medium.
Claim 10
Dependent Claim
191 words
A computer based method of clustering related data in a large computer database, said large computer database stored on a computer readable medium and including a set of data points having categorical attributes, the method comprising the steps of: a) selecting a random set of data points from said large computer database; b) determining all neighbors for every data point within said random set of data points; c) establishing a cluster for every data point within said random set of data points; d) determining a total number of links between each cluster and every other cluster based on a number of common neighbors between each cluster and every other cluster; e) calculating a goodness measure between each cluster and every other cluster based upon the total number of links between each cluster and every other cluster and an estimated number of links between each cluster and every other cluster; f) merging a pair of clusters having the best goodness measures into a merged cluster; g) repeating steps d) through f) until a predetermined termination condition is met; and h) storing clusters which remain after step g) in a computer readable medium.
Claim 11
Dependent Claim
19 words
The method of claim 8 wherein said random set of data points has a size determined by Chernoff bounds.
Claim 12
Dependent Claim
29 words
The method of claim 8 further comprising the step of: i) assigning a cluster label to said data points not included in said random set of said data points.
Claim 13
Dependent Claim
82 words
The method of claim 10 wherein the step of assigning a cluster label to said data points not included in said random set of data points comprises the steps of: i1) selecting a set of labeling points for each of said remaining clusters; and i2) assigning a cluster label to said data points not included in said random set of data points in which said data points have a maximum amount of neighbors with the labeling points of one of said clusters.
Claim 14
Dependent Claim
17 words
The method of claim 8 wherein the predetermined termination condition is obtaining a desired number of clusters.
Claim 15
Dependent Claim
24 words
The method of claim 8 wherein the predetermined termination condition is obtaining remaining clusters that do riot have any links between said remaining clusters.
Claim 16
Dependent Claim
33 words
The method of claim 8 wherein the step of determining all neighbors for every data point within said random set of data points is determined by calculating a similarity between said data points.
Claim 17
Dependent Claim
38 words
The method of claim 14 wherein calculating the similarity between said data points comprises the steps of: b1) calculating a similarity ratio; and b2) assigning said points to be neighbors if said similarity ratio exceeds a similarity threshold.
Claim 18
Dependent Claim
18 words
The method of claim 15 wherein said similarity threshold is selected from the range of 0.5 to 0.8.
Claim 19
Dependent Claim
29 words
The method of claim 15 wherein the calculation of said similarity ratio is performed by dividing an intersection of said data points by a union of said data points.
Claim 20
Dependent Claim
16 words
The method of claim 8 further including the step of: i) eliminating clusters comprised of outliers.
Claim 21
Dependent Claim
33 words
The method of claim 18 wherein the step of eliminating clusters comprised of outliers is performed by deleting clusters having a number of links less than a predetermined threshold from said remaining clusters.
Claim 22
Dependent Claim
13 words
The method of claim 19 wherein the predetermined threshold is 5 or less.
Claim 23
Dependent Claim
29 words
The method of claim 18 further comprising the step of: j) assigning a cluster label to said data points not included in said random set of said data points.
Claim 24
Dependent Claim
82 words
The method of claim 21 wherein the step of assigning a cluster label to said data points not included in said random set of data points comprises the steps of: j1) selecting a set of labeling points for each of said remaining clusters; and j2) assigning a cluster label to said data points not included in said random set of data points in which said data points have a maximum amount of neighbors with the labeling points of one of said clusters.
Claim 25
Dependent Claim
172 words
A computer readable storage medium containing a computer readable code for operating a computer to perform a clustering method on a computer database, said computer database including data points having categorical attributes, said clustering method comprises the steps of: a) determining all neighbors for every data point within said computer database; b) establishing a cluster for every data point in said computer database; c) determining a total number of links between each cluster and every other cluster based on a number of common neighbors between each cluster and every other cluster; d) calculating a goodness measure between each cluster and every other cluster based upon the total number of links between each cluster and every other cluster and an estimated number of links between each cluster and every other cluster; e) merging a pair of clusters having the best goodness measures into a merged cluster; f) repeating steps c) through e) until a predetermined termination condition is met; and g) storing clusters which remain after step f) in a computer readable medium.
Claim 26
Dependent Claim
172 words
A computer readable storage medium containing a computer readable code for operating a computer to perform a clustering method on a computer database, said computer database including data points having categorical attributes, said clustering method comprises the steps of: a) determining all neighbors for every data point within said computer database; b) establishing a cluster for every data point in said computer database; c) determining a total number of links between each cluster and every other cluster based on a number of common neighbors between each cluster and every other cluster; d) calculating a goodness measure between each cluster and every other cluster based upon the total number of links between each cluster and every other cluster and an estimated number of links between each cluster and every other cluster; e) merging a pair of clusters having the best goodness measures into a merged cluster; f) repeating steps c) through e) until a predetermined termination condition is met; and g) storing clusters which remain after step f) in a computer readable medium.
Claim 27
Dependent Claim
24 words
The computer readable storage medium of claim 23 wherein the predetermined termination condition of said clustering method is obtaining a desired number of clusters.
Claim 28
Dependent Claim
31 words
The computer readable storage medium of claim 23 wherein the predetermined termination condition of said clustering method is obtaining remaining clusters that do not have any links between said remaining clusters.
Claim 29
Dependent Claim
30 words
The computer readable storage medium of claim 23 wherein said clustering method determines all neighbors of every data point within said database by calculating a similarity between said data points.
Claim 30
Dependent Claim
40 words
The computer readable storage medium of claim 26 wherein said clustering method performs calculates the similarity between said data points by calculating a similarity ratio and assigning said points to be neighbors if said similarity ratio exceeds a similarity threshold.
Claim 31
Dependent Claim
21 words
The computer readable storage medium of claim 27 wherein said similarity threshold is selected from the range of 0.5 to 0.8.
Claim 32
Dependent Claim
31 words
The computer readable storage medium of claim 27 wherein said clustering method calculates said similarity ratio by dividing the intersection of said data points by a union of said data points.
Claim 33
Dependent Claim
194 words
A computer readable storage medium containing a computer readable code for operating a computer to perform a clustering method on a large database, said large database including a set of data points having categorical attributes, said clustering method comprises the steps of: a) selecting a random set of data points from said large computer database; b) determining all neighbors for every data point within said random set of data points; c) establishing a cluster for every data point within said random set of data points; d) determining a total number of links between each cluster and every other cluster based on a number of common neighbors between each cluster and every other cluster; e) calculating a goodness measure between each cluster and every other cluster based upon the total number of links between each cluster and every other cluster and an estimated number of links between each cluster and every other cluster; f) merging a pair of clusters having the best goodness measures into a merged cluster; g) repeating steps d) through f) until a predetermined termination condition is met; and h) storing clusters which remain after step g) in a computer readable medium.
Claim 34
Dependent Claim
194 words
A computer readable storage medium containing a computer readable code for operating a computer to perform a clustering method on a large database, said large database including a set of data points having categorical attributes, said clustering method comprises the steps of: a) selecting a random set of data points from said large computer database; b) determining all neighbors for every data point within said random set of data points; c) establishing a cluster for every data point within said random set of data points; d) determining a total number of links between each cluster and every other cluster based on a number of common neighbors between each cluster and every other cluster; e) calculating a goodness measure between each cluster and every other cluster based upon the total number of links between each cluster and every other cluster and an estimated number of links between each cluster and every other cluster; f) merging a pair of clusters having the best goodness measures into a merged cluster; g) repeating steps d) through f) until a predetermined termination condition is met; and h) storing clusters which remain after step g) in a computer readable medium.
Claim 35
Dependent Claim
22 words
The computer readable storage medium of claim 30 wherein said random set of data points has a size determined by Chernoff bounds.
Claim 36
Dependent Claim
36 words
The computer readable storage medium of claim 30 wherein said clustering method further comprises the step of: i) assigning a cluster label to said data points not included in said random set of said data points.
Claim 37
Dependent Claim
85 words
The computer readable storage medium of claim 32 wherein the step of assigning a cluster label to said data points not included in said random set of data points comprises the steps of: i1) selecting a set of labeling points for each of said remaining clusters; and i2) assigning a cluster label to said data points not included in said random set of data points in which said data points have a maximum amount of neighbors with the labeling points of one of said clusters.
Claim 38
Dependent Claim
24 words
The computer readable storage medium of claim 30 wherein the predetermined termination condition of said clustering method is obtaining a desired number of clusters.
Claim 39
Dependent Claim
31 words
The computer readable storage medium of claim 30 wherein the predetermined termination condition of said clustering method is obtaining remaining clusters that do not have any links between said remaining clusters.
Claim 40
Dependent Claim
34 words
The computer readable storage medium of claim 30 wherein said clustering method step of determining all neighbors for every data point within said database is determined by calculating a similarity between said data points.
Claim 41
Dependent Claim
38 words
The computer readable storage medium of claim 36 wherein said clustering method calculates the similarity between said data points calculating a similarity ratio and assigning said points to be neighbors if said similarity ratio exceeds a similarity threshold.
Claim 42
Dependent Claim
21 words
The computer readable storage medium of claim 37 wherein said similarity threshold is selected from the range of 0.5 to 0.8.
Claim 43
Dependent Claim
23 words
The computer readable storage medium of claim 30 wherein said clustering method further includes the step of: i) eliminating clusters comprised of outliers.
Claim 44
Dependent Claim
38 words
The computer readable storage medium of claim 39 wherein the clustering method step of eliminating clusters comprised of outliers is performed by deleting clusters having a number of links less than a predetermined threshold from said remaining clusters.
Claim 45
Dependent Claim
16 words
The computer readable storage medium of claim 40 wherein the predetermined threshold is 5 or less.
Claim 46
Dependent Claim
36 words
The computer readable storage medium of claim 41 wherein said clustering method further comprises the step of: j) assigning a cluster label to said data points not included in said random set of said data points.
Claim 47
Dependent Claim
144 words
A programmed computer database clustering system comprising: means for determining all neighbors for every data point within a computer database stored on a computer readable medium, said computer database including data points having categorical attributes; means for establishing a cluster for every data point in said computer database; means for determining a total number of links between each cluster and every other cluster based on a number of common neighbors between each cluster and every other cluster; means for calculating a goodness measure between each cluster and every other cluster based upon the total number of links between each cluster and every other cluster and an estimated number of links between each cluster and every other cluster; means for merging a pair of clusters having the best goodness measures into a merged cluster; means for storing clusters which remain in a computer readable medium.
Claim 48
Dependent Claim
144 words
A programmed computer database clustering system comprising: means for determining all neighbors for every data point within a computer database stored on a computer readable medium, said computer database including data points having categorical attributes; means for establishing a cluster for every data point in said computer database; means for determining a total number of links between each cluster and every other cluster based on a number of common neighbors between each cluster and every other cluster; means for calculating a goodness measure between each cluster and every other cluster based upon the total number of links between each cluster and every other cluster and an estimated number of links between each cluster and every other cluster; means for merging a pair of clusters having the best goodness measures into a merged cluster; means for storing clusters which remain in a computer readable medium.
Claim 49
Dependent Claim
39 words
The programmed computer database clustering system of claim 43 wherein said means for means for determining all neighbors for every data point within a computer database stored on a computer readable medium calculates a similarity between said data points.
Claim 50
Dependent Claim
54 words
The programmed computer database clustering system of claim 43 wherein said means for determining all neighbors for every data point within a computer database stored on a computer readable medium comprises: means for calculating a similarity ratio; and means for assigning said points to be neighbors if said similarity ratio exceeds a similarity threshold.
Claim 51
Dependent Claim
39 words
The programmed computer database clustering system of claim 45 wherein said means for assigning said points to be neighbors if said similarity ratio exceeds a similarity threshold uses a similarity threshold selected from the range of 0.5 to 0.8.
Claim 52
Dependent Claim
36 words
The programmed computer database clustering system of claim 46 wherein said means for calculating a similarity ratio calculates a similarity ratio by dividing an intersection of said data points by a union of said data points.
Claim 53
Dependent Claim
160 words
A programmed computer database clustering system comprising: means for selecting a random set of data points from a large computer database stored on a computer readable medium, said large computer database including data points having categorical attributes; means for determining all neighbors for every data point within said large computer database; means for establishing a cluster for every data point in said computer database; means for determining a total number of links between each cluster and every other cluster based on a number of common neighbors between each cluster and every other cluster; means for calculating a goodness measure between each cluster and every other cluster based upon the total number of links between each cluster and every other cluster and an estimated number of links between each cluster and every other cluster; means for merging a pair of clusters having the best goodness measures into a merged cluster; means for storing clusters which remain in a computer readable medium.
Claim 54
Dependent Claim
160 words
A programmed computer database clustering system comprising: means for selecting a random set of data points from a large computer database stored on a computer readable medium, said large computer database including data points having categorical attributes; means for determining all neighbors for every data point within said large computer database; means for establishing a cluster for every data point in said computer database; means for determining a total number of links between each cluster and every other cluster based on a number of common neighbors between each cluster and every other cluster; means for calculating a goodness measure between each cluster and every other cluster based upon the total number of links between each cluster and every other cluster and an estimated number of links between each cluster and every other cluster; means for merging a pair of clusters having the best goodness measures into a merged cluster; means for storing clusters which remain in a computer readable medium.
Claim 55
Dependent Claim
31 words
The programmed computer database clustering system of claim 48 further comprising: means for assigning a cluster label to said data points not included in said random set of said data points.
Claim 56
Dependent Claim
72 words
The programmed computer database clustering system of claim 49 wherein said means for assigning a cluster label comprises: means for selecting a set of labeling points for each of said remaining clusters; and means for assigning a cluster label to said data points not included in said random set of data points in which said data points have a maximum amount of neighbors with the labeling points of one of said clusters.
Claim 57
Dependent Claim
39 words
The programmed computer database clustering system of claim 49 wherein said means for means for determining all neighbors for every data point within a computer database stored on a computer readable medium calculates a similarity between said data points.
Claim 58
Dependent Claim
54 words
The programmed computer database clustering system of claim 49 wherein said means for determining all neighbors for every data point within a computer database stored on a computer readable medium comprises: means for calculating a similarity ratio; and means for assigning said points to be neighbors if said similarity ratio exceeds a similarity threshold.
Claim 59
Dependent Claim
39 words
The programmed computer database clustering system of claim 52 wherein said means for assigning said points to be neighbors if said similarity ratio exceeds a similarity threshold uses a similarity threshold selected from the range of 0.5 to 0.8.
Claim 60
Dependent Claim
36 words
The programmed computer database clustering system of claim 53 wherein said means for calculating a similarity ratio calculates a similarity ratio by dividing an intersection of said data points by a union of said data points.
Claim 61
Dependent Claim
21 words
The programmed computer database clustering system of claim 48 wherein said program further comprises: means for eliminating clusters comprised of outliers.
Claim 62
Dependent Claim
34 words
The programmed computer database clustering system of claim 55 wherein said means for eliminating clusters comprised of outliers deleting clusters having a number of links less than a predetermined threshold from said remaining clusters.
Claim 63
Dependent Claim
34 words
The programmed computer database clustering system of claim 56 wherein the program further comprises: means for assigning a cluster label to said data points not included in said random set of said data points.
References Cited (Backward Citations)
US5325466A
Cited
US5706503A
Cited
US5675791A
Cited
US5839105A
Cited
US5710915A
Cited
US5790426A
Cited
US5884282A
Cited
US5861891A
Cited
US5960435A
Cited
US5884305A
Cited
US5983224A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-04-11 | 2003-10-11 | 2004-04-11 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-04-11 | 2007-10-11 | 2008-04-11 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-04-11 | 2011-10-11 | 2012-04-11 | $7700.00 | Window Closed / Lapsed |