question: 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 ; }
target:  Use K-means++ to choose the initial centers.