Method and system for efficient clustering of combined numeric and qualitative data records
An optimized and efficient method of identifying one or more points within a dataset that are close to the centers of clumps similar records in a large, multi-element dataset uses Monte Carlo techniques to compute approximate clustering costs at significantly reduced computational expense. The inaccuracy caused by the approximate methods is also estimated, and if it is too high, the method may be repeated with a larger Monte Carlo sample size to improve accuracy. Portions of the algorithm that are independent are distributed among a number of cooperating computing nodes so that the full algorithm can be completed in less time.
1. A method for improving the performance of a group of cooperating computers working together to find approximately-optimal cluster medoids for a dataset of a plurality of multi-element records, the method performed by a master computer and a plurality of slave computers, comprising:
assigning a segment of a dataset to each slave computer of the plurality of slave computers;
choosing an initial set of candidate medoids from the dataset to serve as a current candidate medoid set;
choosing a Monte Carlo subset of records of the dataset and sending the Monte Carlo subset of records to each of the plurality of slave computer; and
iteratively improving the current candidate medoid set based on interim results from the plurality of slave computers to obtain an acceptable-quality candidate medoid set, wherein each slave:
receives the current candidate medoid set;
computes a exact clustering cost as a sum of a distance between each record of the slave's segment of the dataset and a nearest candidate medoid of the current candidate medoid set;
computes an approximate clustering cost as a sum of a distance between each record of the Monte Carlo subset of records and the nearest candidate medoid of the current candidate medoid set;
identifies a slave-best medoid swap from among data records of the slave's segment of the dataset, and
transmits the slave-best medoid swap to the master computer.
2. The method of claim 1 , further comprising:
choosing a best medoid swap from among the plurality of slave-best medoid swaps received from each slave computer of the plurality of slave computers;
replacing the current candidate medoid set with the best medoid swap to produce a next candidate medoid set; and
performing another iteration of the iteratively improving operation using the next candidate medoid set.
3. The method of claim 2 , wherein each slave-best medoid swap comprises swap-quality information, the method further comprising:
evaluating the swap-quality information to determine whether the method has converged; and
if the method has converged, emitting the current candidate medoid set as an approximate best candidate medoid set for the dataset.
4. The method of claim 3 wherein the swap-quality information includes an estimate of a noise in the slave-best medoid swap.
5. The method of claim 3 wherein the swap-quality information includes an estimate of an expected potential improvement in the slave-best medoid swap.
6. A non-transitory tangible computer-readable medium containing data and instructions to cause a master computer and a plurality of cooperating slave computers to perform operations comprising:
establishing communications between the master computer and the plurality of cooperating slave computers;
dividing a dataset comprising a plurality of multi-element records among the plurality of cooperating slave computers, each slave computer thus having a portion of the dataset;
selecting k initial candidate medoids from the dataset and sending the k initial candidate medoids to the cooperating slave computers; wherein k is a positive integer;
selecting n random Monte Carlo multi-element records from the dataset and sending the n records to the cooperating slave computers; wherein n is a positive integer;
receiving a plurality of partial clustering costs from the cooperating slave computers, each said partial clustering cost computed by a cooperating slave computer as a sum of distances from the slave's portion of the dataset to a nearest candidate medoid of the k initial candidate medoids;
summing the plurality of partial clustering costs to obtain an exact clustering cost of the k initial candidate medoids;
accepting a plurality of slave-best medoid swaps from the plurality of cooperating slave computers;
selecting a best swap from among the slave-best medoid swaps; and
repeating the receiving, summing, accepting and selecting operations to identify an improved set of medoids for the dataset.
7. The tangible computer-readable medium of claim 6 , containing additional data and instructions to cause the master computer and plurality of cooperating slave computers to perform further operations comprising:
evaluating a quality of the best swap; and
if the quality of the best swap exceeds a predetermined level, discontinuing the repeating operation.
8. The tangible computer-readable medium of claim 6 wherein each slave computer has an equal-sized portion of the dataset.
9. The tangible computer-readable medium of claim 6 wherein at least one slave computer has a different-sized portion of the dataset from at least one other slave computer.
10. The tangible computer-readable medium of claim 6 wherein at least one of the random Monte Carlo multi-element records is not part of the dataset portion of at least one of the slave computers.
11. The tangible computer-readable medium of claim 6 wherein at least one of the initial candidate medoids is not part of the dataset portion of at least one of the slave computers.