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.
1. A method implemented by a processor coupled to a memory, comprising:
collecting a plurality of n observations of users interacting with an electronic-commerce website and storing the n observations as a plurality of n data records in a database;
retrieving the n data records from the database, each data record comprising a plurality of elements, said plurality of elements including at least one quantitative element and at least one qualitative element;
identifying a subset of k candidate medoids from the n data records;
selecting a subset of s sample records at random from the n data records;
computing an approximate clustering cost as a distance between each of the s sample records and a nearest one of the k candidate medoids;
replacing one of the k candidate medoids with one of the n data records not part of the k candidate medoids to produce a new set of k′ candidate medoids;
recomputing an updated approximate clustering cost as a distance between each of the s sample points to a nearest one of the k′ candidate medoids; and
repeating the replacing and recomputing operations to identify an approximately-optimal subset of k medoids from the n data records and a lowest approximate clustering cost of the approximately-optimal subset of k medoids, wherein
the updated approximate clustering cost is lower than the approximate clustering cost, and
displaying the approximately-optimal subset of k medoids to show k specific user interactions with the electronic-commerce website that are approximately most-similar to clusters among the plurality of n observations stored in the database, wherein
n, k, k′ and s are positive integers.
2. The method of claim 1 , further comprising:
estimating an error discrepancy between the lowest approximate clustering cost and a true clustering cost computed as a distance between each of the data records and the approximately-optimal subset of medoids; and
if the error discrepancy exceeds a predetermined value, then
increasing a size of the subset of s sample records; and
repeating the identifying, selecting, computing, replacing and recomputing operations to identify an improved-accuracy subset of medoids.
3. The method of claim 1 wherein identifying comprises selecting candidate medoids at random from the plurality of data records.
4. The method of claim 1 wherein identifying comprises selecting candidate medoids by a —means++ algorithm from the plurality of data records.
5. The method of claim 1 wherein the repeating implements a greedy search for the approximately-optimal subset of medoids.
6. The method of claim 1 wherein the repeating implements an exhaustive search for the approximately-optimal subset of medoids.
7. The method of claim 1 , further comprising:
repeating the identifying, selecting, computing, replacing and recomputing operations for a series of integer values for to produce a corresponding series of approximately-optimal sets of medoids; and
emitting a preferred value for where an approximate clustering cost for the preferred value for decreases by less from ( to +1) than the approximate clustering cost decreased from ( −1 to ).
8. The method of claim 1 wherein is equal to a number of elements of a data record of the data records.
9. The method of claim 1 wherein selecting a subset of s sample records is selecting s data records from the plurality of data records with replacement.
10. The method of claim 1 wherein s is between 5% of and 15% of .
11. The method of claim 1 wherein each data record of the plurality of data records comprises a quantitative size element and a qualitative color element.
12. A tangible computer-readable medium containing data and instructions to cause a programmable processor to perform operations comprising:
collecting a plurality of n observations of users interacting with an electronic-commerce website and storing the n observations as a plurality of n data records in a database;
electronically accessing the plurality of n data records stored in the computer database, each data record comprising a plurality of elements, said plurality of elements including at least one quantitative element and at least one qualitative element;
identifying a subset of k candidate medoids from the n data records;
selecting a subset of s sample records at random from the n data records;
computing an approximate clustering cost as a distance between each of the s sample records and a nearest one of the k candidate medoids;
replacing one of the k candidate medoids with one of the n data records not part of the k candidate medoids to produce a new set of k′ candidate medoids;
recomputing an updated approximate clustering cost as a distance between each of the s sample points to a nearest one of the k′ candidate medoids, and
repeating the computing and replacing operations to identify an approximately-optimal subset of k medoids from the n data records and a lowest approximate clustering cost of the approximately-optimal subset of k medoids, wherein
the updated approximate clustering cost is lower than the approximate clustering cost; and
emitting the approximately-optimal subset of k medoids as best representative data records of k clusters of records among the n data records, wherein
n, k, k′ and s are positive integers.