US6115708A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for refining the initial conditions for clustering with applications to small and large database clustering
Assignee: Microsoft Technology Licensing LLC
•
Filing: 1998-03-04
•
Granted: 2000-09-05
•
Expires: 2018-03-04
Abstract
Abstract As an optimization problem, clustering data (unsupervised learning) is known to be a difficult problem. Most practical approaches use a heuristic, typically gradient-descent, algorithm to search for a solution in the huge space of possible solutions. Such methods are by definition sensitive to starting points. It has been well-known that clustering algorithms are extremely sensitive to initial conditions. Most methods for guessing an initial solution simply make random guesses. In this paper we present a method that takes an initial condition and efficiently produces a refined starting condition. The method is applicable to a wide class of clustering algorithms for discrete and continuous data. In this paper we demonstrate how this method is applied to the popular K-means clustering algorithm and show that refined initial starting points indeed lead to improved solutions. The technique can be used as an initializer for other clustering solutions. The method is based on an efficient technique for estimating the modes of a distribution and runs in time guaranteed to be less than overall clustering time for large data sets. The method is also scalable and hence can be efficiently used on huge databases to refine starting points for scalable clustering algorithms in data mining applications.
Inventors
- 👤 Usama Fayyad
- 👤 Paul S. Bradley
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-03 04:55
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/30; G06F16/35; G06F2216/00; G06F2216/03; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933; Y10S707/99934; Y10S707/99935; Y10S707/99936
Claims Analysis
Total Claims: 32
Claim 1
Independent Claim
129 words
A method for evaluating data in a database that is stored on a storage medium, wherein the database has a data set to be evaluated, and wherein the data set is comprised of a plurality of records, comprising the steps of: a) obtaining a multiple number of data subsets comprising a plurality of records from the data set, b) performing clustering analysis on the data records that make up each of the subsets to provide a multiple number of candidate clustering starting points; c) choosing one of the multiple candidate clustering starting points to be used in clustering the data set to be evaluated; and d) using the one chosen candidate clustering starting point as a starting point to perform clustering analysis on the data set to be evaluated.
Claim 2
Independent Claim
129 words
A method for evaluating data in a database that is stored on a storage medium, wherein the database has a data set to be evaluated, and wherein the data set is comprised of a plurality of records, comprising the steps of: a) obtaining a multiple number of data subsets comprising a plurality of records from the data set, b) performing clustering analysis on the data records that make up each of the subsets to provide a multiple number of candidate clustering starting points; c) choosing one of the multiple candidate clustering starting points to be used in clustering the data set to be evaluated; and d) using the one chosen candidate clustering starting point as a starting point to perform clustering analysis on the data set to be evaluated.
Claim 3
Dependent Claim
34 words
The method of claim 1 wherein the step of performing clustering analysis on each of the subsets is performed from an initial starting point which is refined to determine said candidate clustering starting point.
Claim 4
Dependent Claim
34 words
The method of claim 1 wherein the step of choosing one of the candidate clustering starting points comprises the step of performing additional data clustering on the multiple number of candidate clustering starting points.
Claim 5
Dependent Claim
59 words
The method of claim 1 wherein the step of choosing one of the candidate clustering starting points comprises the step of performing additional data clustering on the multiple number of candidate clustering starting points and wherein one of said multiple number of candidate clustering starting points is chosen as a refined clustering starting point to perform the data clustering.
Claim 6
Dependent Claim
13 words
The method of claim 2 wherein the initial starting point is randomly determined.
Claim 7
Dependent Claim
48 words
The method of claim 2 wherein the step of performing clustering analysis on each of the subsets is performed by removing sparsely populated clusters, merging the sparsely populated clusters with clusters that are more densely populated and determining a new initial starting point for subsequent clustering of data.
Claim 8
Dependent Claim
59 words
The method of claim 2 wherein if at the end of the clustering of each of the subsets, any of the clusters have zero membership, then the corresponding initial choice for this empty cluster centroid is adjusted to a solution set to a data point in the sample farthest from the initial choice that resulted in the empty cluster.
Claim 9
Dependent Claim
43 words
The method of claim 2 wherein if at the end of the clustering of each of the subsets any of the clusters have zero membership a new cluster mean for the empty cluster is chosen from the mean of the entire data sample.
Claim 10
Dependent Claim
73 words
The method of claim 2 wherein if at the end of the clustering the data records that make up each of the subsets, any of the clusters have zero membership a new cluster mean for the empty cluster is chosen by picking the mean of the entire data set and perturbing that mean by a small random amount corresponding to a variance in the data mean in each dimension of the data sample.
Claim 11
Dependent Claim
41 words
The method of claim 1 wherein the step of performing a clustering analysis on each of the subsets uses a different clustering process than the clustering process that is used to perform clustering analysis on the data set to be evaluated.
Claim 12
Dependent Claim
141 words
In a computer data mining system, apparatus for evaluating data in a database comprising: a) one or more data storage devices for storing a database of records on a storage medium; b) a computer having an interface to the storage devices for reading data from the storage medium and bring the data into a rapid access memory for subsequent evaluation; and c) said computer comprising a processing unit for evaluating at least some of the data in the database and for clustering the data into multiple numbers of data clusters; said processing unit programmed to retrieve multiple subsets of data from the database, find multiple candidate clustering starting points from the multiple data subsets retrieved from the database and choosing an optimum solution from the multiple number of candidate clustering starting points to begin subsequent clustering on data in the database.
Claim 13
Dependent Claim
141 words
In a computer data mining system, apparatus for evaluating data in a database comprising: a) one or more data storage devices for storing a database of records on a storage medium; b) a computer having an interface to the storage devices for reading data from the storage medium and bring the data into a rapid access memory for subsequent evaluation; and c) said computer comprising a processing unit for evaluating at least some of the data in the database and for clustering the data into multiple numbers of data clusters; said processing unit programmed to retrieve multiple subsets of data from the database, find multiple candidate clustering starting points from the multiple data subsets retrieved from the database and choosing an optimum solution from the multiple number of candidate clustering starting points to begin subsequent clustering on data in the database.
Claim 14
Dependent Claim
133 words
In a computer database system, a method for use in choosing starting conditions in a data clustering procedure comprising the steps of: a) choosing a cluster number K for use in categorizing the data in the database into K different data clusters; b) choosing an initial centroid for each of the K data clusters; c) sampling a portion of the data in the database from a storage medium and performing a clustering on the data sampled from the database based on the K centroids to form K characterizations of the database; d) repeating the sampling and clustering steps until a plurality of clustering solutions have been determined; and e) choosing a best solution from said plurality of clustering solutions to use as a starting point in further clustering of data from the database.
Claim 15
Dependent Claim
133 words
In a computer database system, a method for use in choosing starting conditions in a data clustering procedure comprising the steps of: a) choosing a cluster number K for use in categorizing the data in the database into K different data clusters; b) choosing an initial centroid for each of the K data clusters; c) sampling a portion of the data in the database from a storage medium and performing a clustering on the data sampled from the database based on the K centroids to form K characterizations of the database; d) repeating the sampling and clustering steps until a plurality of clustering solutions have been determined; and e) choosing a best solution from said plurality of clustering solutions to use as a starting point in further clustering of data from the database.
Claim 16
Dependent Claim
128 words
Apparatus for evaluating data in a database that is stored on a storage medium, wherein the database has a data set to be evaluated, and wherein the data set is comprised of a plurality of records, the apparatus comprising: a) means for obtaining a multiple number of data subsets comprising a plurality of records from the data set, b) means for performing clustering analysis on the data records that make up each of the subsets to provide a multiple number of candidate clustering starting points; c) means for choosing one of the multiple candidate clustering starting points to be used in clustering the data set to be evaluated; and d) means for using the chosen starting point to perform clustering analysis on the data set to be evaluated.
Claim 17
Dependent Claim
128 words
Apparatus for evaluating data in a database that is stored on a storage medium, wherein the database has a data set to be evaluated, and wherein the data set is comprised of a plurality of records, the apparatus comprising: a) means for obtaining a multiple number of data subsets comprising a plurality of records from the data set, b) means for performing clustering analysis on the data records that make up each of the subsets to provide a multiple number of candidate clustering starting points; c) means for choosing one of the multiple candidate clustering starting points to be used in clustering the data set to be evaluated; and d) means for using the chosen starting point to perform clustering analysis on the data set to be evaluated.
Claim 18
Dependent Claim
23 words
The apparatus of claim 13 additionally comprising means to randomly choose an initial starting point for use in clustering the multiple data subsets.
Claim 19
Dependent Claim
32 words
The apparatus of claim 13 additionally comprising means to choose an initial starting point for use in performing clustering analysis on the multiple data subsets based on data contained in the database.
Claim 20
Dependent Claim
36 words
The apparatus of claim 13 wherein the means for choosing comprises means for clustering the multiple number of candidate clustering starting points using each starting point as an interim starting point for clustering said starting points.
Claim 21
Dependent Claim
49 words
The apparatus of claim 16 wherein the means for choosing comprises means for determining a best refined candidate clustering starting point from an intermediate clustering of the data sample solutions based upon a distance from the data points of said multiple solutions to a set of intermediate clustering solutions.
Claim 22
Dependent Claim
120 words
A computer-readable medium having computer-executable instructions for performing steps for evaluating a database wherein the database has a data set to be evaluated, and wherein the data set is comprised of a plurality of records, comprising the steps of: a) obtaining a multiple number of data subsets comprising a plurality of records from the data set, b) performing clustering analysis on the data records that make up each of the subsets to provide a multiple number of candidate clustering starting points; c) choosing one of the multiple candidate clustering starting points to be used in clustering the data set to be evaluated; and d) using the chosen starting point to perform clustering analysis on the data set to be evaluated.
Claim 23
Dependent Claim
120 words
A computer-readable medium having computer-executable instructions for performing steps for evaluating a database wherein the database has a data set to be evaluated, and wherein the data set is comprised of a plurality of records, comprising the steps of: a) obtaining a multiple number of data subsets comprising a plurality of records from the data set, b) performing clustering analysis on the data records that make up each of the subsets to provide a multiple number of candidate clustering starting points; c) choosing one of the multiple candidate clustering starting points to be used in clustering the data set to be evaluated; and d) using the chosen starting point to perform clustering analysis on the data set to be evaluated.
Claim 24
Independent Claim
126 words
A method for evaluating data in a database that is stored on a storage medium, wherein the database has a data set to be evaluated, and wherein the data set is comprised of a plurality of records, comprising the steps of: a) obtaining a multiple number of data subsets comprising a plurality of records from the data set, b) performing clustering analysis on the data records that make up each of the subsets to provide a multiple number of candidate clustering starting points; c) choosing a clustering starting point based on the multiple candidate clustering starting points to be used in clustering the data set to be evaluated; and d) using the chosen starting point to perform clustering analysis on the data set to be evaluated.
Claim 25
Independent Claim
126 words
A method for evaluating data in a database that is stored on a storage medium, wherein the database has a data set to be evaluated, and wherein the data set is comprised of a plurality of records, comprising the steps of: a) obtaining a multiple number of data subsets comprising a plurality of records from the data set, b) performing clustering analysis on the data records that make up each of the subsets to provide a multiple number of candidate clustering starting points; c) choosing a clustering starting point based on the multiple candidate clustering starting points to be used in clustering the data set to be evaluated; and d) using the chosen starting point to perform clustering analysis on the data set to be evaluated.
Claim 26
Dependent Claim
49 words
The method of claim 19 wherein each of the multiple number of candidate clustering starting points is used as an intermediate starting point for clustering the candidate starting points and wherein a resulting solution of said clustering of candidate starting points is used as a refined clustering starting point.
Claim 27
Dependent Claim
36 words
The method of claim 20 wherein the refined clustering starting point is chosen by determining a distance from multiple intermediate clustering solutions and a set of data points made up of the candidate clustering starting points.
Claim 28
Dependent Claim
32 words
The method of claim 21 wherein the refined clustering starting point is an optimum solution to the clustering of the multiple candidate clustering starting points wherein optimum is based on said distance.
Claim 29
Dependent Claim
110 words
The method of claim 1 wherein the step of choosing one of the multiple candidate clustering starting points is performed by: a) choosing a candidate clustering starting point; b) using the chosen candidate clustering starting point to perform an interim clustering analysis on an interim data set; c) determining the quality of the cluster solution resulting from the interim clustering analysis; d) repeating steps a) through c) until all candidate clustering starting points have been used in interim clustering analysis; and e) selecting the candidate starting point which yielded the best quality cluster solution as a refined starting point for performing clustering analysis on the data set to be evaluated.
Claim 30
Dependent Claim
18 words
The method of claim 23 wherein the interim data set is a plurality of unchosen candidate starting points.
Claim 31
Dependent Claim
22 words
The method of claim 23 wherein the interim data set is a plurality of data records that make up the data subsets.
Claim 32
Dependent Claim
36 words
The method of claim 23 wherein the step of determining the quality of the interim clustering analysis if performed by calculating a degree of fit of the chosen candidate starting point with the interim data set.
References Cited (Backward Citations)
US5442778A
Cited
US5758147A
Cited
US5787422A
Cited
US5832182A
Cited
US5920856A
Cited
US5884305A
Cited
US5930784A
Cited
US5983224A
Cited
US6012058A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-09-05 | 2004-03-06 | 2004-09-05 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-09-05 | 2008-03-06 | 2008-09-05 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-09-05 | 2012-03-06 | 2012-09-05 | $7700.00 | Window Closed / Lapsed |