Expediting K-means cluster analysis data mining using subsample elimination preprocessing
Improved efficiencies of data mining clustering techniques are provided by preprocessing a sample set of data points taken from a complete data set to provide seeds for centroid calculations of the complete data set. Such seeds are generated by selecting a uniform sample set of data points from a set of multi-dimensional data and then seed values for the cluster determination calculation are determined using a centroid analysis on the sample set of data points. The number of seeds calculated corresponds to a number of data clusters expected in the set of multi-dimensional data points. Seed values are determined using subsample elimination techniques.
1. A computer-implemented method comprising:
selecting a sample set of data points from a set of multidimensional data points;
selecting a number of data clusters to determine in the set of multidimensional data points;
determining seed values for a cluster centroid calculation of the number of data clusters using the sample set of data points; and
performing the cluster centroid calculation for the set of multidimensional data points using the seed values.
2. The method of claim 1 wherein said determining the seed values comprises:
selecting a first data point of the sample set of data points;
determining a set of nearest neighbor data points to the first data point, wherein
the set of nearest neighbor data points is selected from the sample set of data points;
calculating a first mean location value of the set of nearest neighbor data points and the first data point; and
setting a first seed value of the seed values equal to the first mean location value.
3. The method of claim 2 wherein the set of nearest neighbor data points comprises a pre-defined number of data points.
4. The method of claim 2 further comprising:
determining a distance between the first data point and the nearest neighbor data point farthest from the first data point; and
removing all data points of the sample set of data points that are located within a region defined by the first mean location value and the distance between the first data point and the nearest neighbor data point farthest from the first data point.
5. The method of claim 4 wherein the region comprises a circle for a two-dimensional set of multidimensional data points.
6. The method of claim 4 wherein the region comprises a sphere for a three-dimensional set of multidimensional data points.
7. The method of claim 4 further comprising:
selecting a second data point of the sample set of data points, after performing said removing all data points located within the region defined by the first mean location value and the distance between the first data point and the nearest neighbor data point farthest from the first data point;
determining a second set of nearest neighbor data points to the second data point, wherein
the second set of nearest neighbor data points is selected from the sample set of data points;
calculating a second mean location value of the set of nearest neighbor data points and the second data point; and
setting a second seed value of the seed values equal to the second mean location value.
8. The method of claim 1 wherein the cluster centroid calculation comprises a k-means analysis of the set of multidimensional data points.
9. A computer-readable storage medium storing instructions executable by a processor, the instructions comprising:
a first set of instructions configured to select a sample set of data points from a set of multidimensional data points, wherein the set of multidimensional data points is stored in a second computer-readable storage medium;
a second set of instructions configured to select a number of data clusters to determine in the set of multidimensional data points;
a third set of instructions configured to determine seed values for a cluster centroid calculation of the number of data clusters using the sample set of data points; and
a fourth set of instructions configured to perform the cluster centroid calculation for the set of multidimensional data points using the seed values.
10. The computer-readable storage medium of claim 9 wherein said third set of instructions further comprises:
a fifth set of instructions configured to select a first data point of the sample set of data points;
a sixth set of instructions configured to determine a set of nearest neighbor data points to the first data point, wherein
the set of nearest neighbor data points is selected from the sample set of data points;
a seventh set of instructions configured to calculate a first mean location value of the set of nearest neighbor data points and the first data point; and
a eighth set of instructions configured to set a first seed value of the seed values equal to the first mean location value.
11. The computer-readable storage medium of claim 10 wherein the set of nearest neighbor data points comprises a pre-defined number of data points.
12. The computer readable storage medium of claim 10 storing instructions further comprising:
a ninth set of instructions configured to determine a distance between the first data point and the nearest neighbor data point farthest from the first data point; and
a tenth set of instructions configured to remove all data points of the sample set of data points that are located within a region defined by the first mean location value and the distance between the first data point and the nearest neighbor data point farthest from the first data point.
13. The computer-readable storage medium of claim 12 wherein the region comprises a circle for a two-dimensional set of multidimensional data points.
14. The computer-readable storage medium of claim 12 wherein the region comprises a sphere for a three-dimensional set of multidimensional data points.
15. The computer-readable storage medium of claim 12 storing instructions further comprising:
an eleventh set of instructions configured to select a second data point of the sample set of data points, after performing said removing all data points located within the region defined by the first mean location value and the distance between the first data point and the nearest neighbor data point farthest from the first data point;
a twelfth set of instructions configured to determine a second set of nearest neighbor data points to the second data point, wherein
the second set of nearest neighbor data points is selected from the sample set of data points;
a thirteenth set of instructions configured to calculate a second mean location value of the set of nearest neighbor data points and the second data point; and
a fourteenth set of instructions configured to set a second seed value of the seed values equal to the second mean location value.
16. The computer-readable storage medium of claim 9 wherein the fourth set of instructions further comprises a fifth set of instructions configured to perform a k-means analysis of the set of multidimensional data points.
17. An apparatus comprising:
a processor; and
a memory, coupled to the processor, storing instructions executable by the processor and configured to
select a sample set of data points from a set of multidimensional data points, wherein the set of multidimensional data points is stored in a storage volume coupled to the processor,
select a number of data clusters to determine in the set of multidimensional data points,
determine seed values for a cluster centroid calculation of the number of data clusters using the sample set of data points, and
perform the cluster centroid calculation for the set of multidimensional data points using the seed values.
18. The apparatus of claim 17 wherein the instructions for determining the seed values further comprise instructions executable by the processor and configured to:
select a first data point of the sample set of data points;
determine a set of nearest neighbor data points to the first data point, wherein
the set of nearest neighbor data points is selected from the sample set of data points;
calculate a first mean location value of the set of nearest neighbor data points and the first data point; and
set a first seed value of the seed values equal to the first mean location value.
19. The apparatus of claim 18 further comprising instructions stored in the memory and configured to:
determine a distance between the first data point and the nearest neighbor data point farthest from the first data point; and
remove all data points of the sample set of data points that are located within a region defined by the first mean location value and the distance between the first data point and the nearest neighbor data point farthest from the first data point.
20. The apparatus of claim 19 further comprising instructions stored in the memory and configured to:
select a second data point of the sample set of data points, after performing said removing all data points located within the region defined by the first mean location value and the distance between the first data point and the nearest neighbor data point farthest from the first data point;
determine a second set of nearest neighbor data points to the second data point, wherein
the second set of nearest neighbor data points is selected from the sample set of data points;
calculate a second mean location value of the set of nearest neighbor data points and the second data point; and
set a second seed value of the seed values equal to the second mean location value.