edu.ucla.sspace.clustering.seeding

Class OrssSeed

java.lang.Object

edu.ucla.sspace.clustering.seeding.OrssSeed

All Implemented Interfaces:

KMeansSeed

public class OrssSeed
extends Object
implements KMeansSeed

Select seeds using a modification of the ORSS algorithm. Seeds are selected from the data such that they are well scattered. This implementation has a runtime of O(nkd) and is is based on the following paper:

Rafail Ostrovsky , Yuval Rabani , Leonard J. Schulman , Chaitanya Swamy, "The effectiveness of lloyd-type methods for the k-means problem," in 47th IEEE Symposium on the Foundations of Computer Science, 2006 This involves 4 steps:

1. First, the cost of an optimal solution to the K-Means problem is solved for the 1 cluster case along (called optimalSingleCost) with the centroid for this case (called c).
2. Then, an intial seed is selected from the set of data points (X) with probability p((optimalSingleCost + n*euclieanDist(x,c)^2)/2*n*optimalSingleCost)
3. The second centroid is selected from X with probability p(euclideanDist(x, c_1)^2/(optimalSingleCost + n*euclideanDist(c, c_1)^2))
4. The remaining k-2 centroids are selected from X with probability p(euclideanDist(x, c_nearest)^2)

Author:

Keith Stevens