private List<CentroidCluster<T>> chooseInitialCenters(final Collection<T> points){
  final List<T> pointList=Collections.unmodifiableList(new ArrayList<T>(points));
  final int numPoints=pointList.size();
  final boolean[] taken=new boolean[numPoints];
  final List<CentroidCluster<T>> resultSet=new ArrayList<CentroidCluster<T>>();
  final int firstPointIndex=random.nextInt(numPoints);
  final T firstPoint=pointList.get(firstPointIndex);
  resultSet.add(new CentroidCluster<T>(firstPoint));
  taken[firstPointIndex]=true;
  final double[] minDistSquared=new double[numPoints];
  for (int i=0; i < numPoints; i++) {
    if (i != firstPointIndex) {
      double d=distance(firstPoint,pointList.get(i));
      minDistSquared[i]=d * d;
    }
  }
  while (resultSet.size() < k) {
    double distSqSum=0.0;
    for (int i=0; i < numPoints; i++) {
      if (!taken[i]) {
        distSqSum+=minDistSquared[i];
      }
    }
    final double r=random.nextDouble() * distSqSum;
    int nextPointIndex=-1;
    double sum=0.0;
    for (int i=0; i < numPoints; i++) {
      if (!taken[i]) {
        sum+=minDistSquared[i];
        if (sum >= r) {
          nextPointIndex=i;
          break;
        }
      }
    }
    if (nextPointIndex == -1) {
      for (int i=numPoints - 1; i >= 0; i--) {
        if (!taken[i]) {
          nextPointIndex=i;
          break;
        }
      }
    }
    if (nextPointIndex >= 0) {
      final T p=pointList.get(nextPointIndex);
      resultSet.add(new CentroidCluster<T>(p));
      taken[nextPointIndex]=true;
      if (resultSet.size() < k) {
        for (int j=0; j < numPoints; j++) {
          if (!taken[j]) {
            double d=distance(p,pointList.get(j));
            double d2=d * d;
            if (d2 < minDistSquared[j]) {
              minDistSquared[j]=d2;
            }
          }
        }
      }
    }
 else {
      break;
    }
  }
  return resultSet;
}

private List < CentroidCluster < T > > chooseInitialCenters ( final Collection < T > points ) { final List < T > pointList = Collections . unmodifiableList ( new ArrayList < T > ( points ) ) ; final int numPoints = pointList . size ( ) ; final boolean [ ] taken = new boolean [ numPoints ] ; final List < CentroidCluster < T > > resultSet = new ArrayList < CentroidCluster < T > > ( ) ; final int firstPointIndex = random . nextInt ( numPoints ) ; final T firstPoint = pointList . get ( firstPointIndex ) ; resultSet . add ( new CentroidCluster < T > ( firstPoint ) ) ; taken [ firstPointIndex ] = true ; final double [ ] minDistSquared = new double [ numPoints ] ; for ( int i = 0 ; i < numPoints ; i ++ ) { if ( i != firstPointIndex ) { double d = distance ( firstPoint , pointList . get ( i ) ) ; minDistSquared [ i ] = d * d ; } } while ( resultSet . size ( ) < k ) { double distSqSum = 0.0 ; for ( int i = 0 ; i < numPoints ; i ++ ) { if ( ! taken [ i ] ) { distSqSum += minDistSquared [ i ] ; } } final double r = random . nextDouble ( ) * distSqSum ; int nextPointIndex = - 1 ; double sum = 0.0 ; for ( int i = 0 ; i < numPoints ; i ++ ) { if ( ! taken [ i ] ) { sum += minDistSquared [ i ] ; if ( sum >= r ) { nextPointIndex = i ; break ; } } } if ( nextPointIndex == - 1 ) { for ( int i = numPoints - 1 ; i >= 0 ; i -- ) { if ( ! taken [ i ] ) { nextPointIndex = i ; break ; } } } if ( nextPointIndex >= 0 ) { final T p = pointList . get ( nextPointIndex ) ; resultSet . add ( new CentroidCluster < T > ( p ) ) ; taken [ nextPointIndex ] = true ; if ( resultSet . size ( ) < k ) { for ( int j = 0 ; j < numPoints ; j ++ ) { if ( ! taken [ j ] ) { double d = distance ( p , pointList . get ( j ) ) ; double d2 = d * d ; if ( d2 < minDistSquared [ j ] ) { minDistSquared [ j ] = d2 ; } } } } } else { break ; } } return resultSet ; }
use k - means + + to choose the initial centers .
