src/algorithm/kmeans.js
function chooseInitialCenters(points) {

    // Convert to list for indexed access. Make it unmodifiable, since removal of items
    // would screw up the logic of this method.
    var pointList = points;
    // The number of points in the list.
    var numPoints = pointList.length;

    // Set the corresponding element in this array to indicate when
    // elements of pointList are no longer available.
    var taken = new Array(numPoints);
    for (var i = 0; i < taken.length; i++) {
      taken[i] = false;
    }

    // The resulting list of initial centers.
    var resultSet = [];

    // Choose one center uniformly at random from among the data points.
    var firstPointIndex = nextInt(numPoints);
    var firstPoint = pointList[firstPointIndex];
    resultSet.push(new CentroidCluster(firstPoint));
    // Must mark it as taken
    taken[firstPointIndex] = true;

    // To keep track of the minimum distance squared of elements of
    // pointList to elements of resultSet.

    var minDistSquared = new Float32Array(numPoints);

    // Initialize the elements.  Since the only point in resultSet is firstPoint,
    // this is very easy.
    for (var i = 0; i < numPoints; i++) {
      if (i !== firstPointIndex) { // That point isn't considered
        var d = distance(firstPoint, pointList[i]);
        minDistSquared[i] = d * d;
      }
    }

    while (resultSet.length < k) {
      // Sum up the squared distances for the points in pointList not
      // already taken.
      var distSqSum = 0.0;

      for (var i = 0; i < numPoints; i++) {
        if (!taken[i]) {
          distSqSum += minDistSquared[i];
        }
      }

      // Add one new data point as a center. Each point x is chosen with
      // probability proportional to D(x)2
      var r = nextDouble() * distSqSum;

      // The index of the next point to be added to the resultSet.
      var nextPointIndex = -1;

      // Sum through the squared min distances again, stopping when
      // sum >= r.
      var sum = 0.0;
      for (var i = 0; i < numPoints; i++) {
        if (!taken[i]) {
          sum += minDistSquared[i];
          if (sum >= r) {
            nextPointIndex = i;
            break;
          }
        }
      }

      // If it's not set to >= 0, the point wasn't found in the previous
      // for loop, probably because distances are extremely small.  Just pick
      // the last available point.
      if (nextPointIndex === -1) {
        for (var i = numPoints - 1; i >= 0; i--) {
          if (!taken[i]) {
            nextPointIndex = i;
            break;
          }
        }
      }

      // We found one.
      if (nextPointIndex >= 0) {

        var p = pointList[nextPointIndex];

        resultSet.push(new CentroidCluster(p));

        // Mark it as taken.
        taken[nextPointIndex] = true;

        if (resultSet.length < k) {
          // Now update elements of minDistSquared.  We only have to compute
          // the distance to the new center to do this.
          for (var j = 0; j < numPoints; j++) {
            // Only have to worry about the points still not taken.
            if (!taken[j]) {
              var d = distance(p, pointList[j]);
              var d2 = d * d;
              if (d2 < minDistSquared[j]) {
                minDistSquared[j] = d2;
              }
            }
          }
        }

      } else {
        // None found --
        // Break from the while loop to prevent
        // an infinite loop.
        break;
      }
    }
    return resultSet;
  }
function chooseInitialCenters(points) {

    // Convert to list for indexed access. Make it unmodifiable, since removal of items
    // would screw up the logic of this method.
    var pointList = points;
    // The number of points in the list.
    var numPoints = pointList.length;

    // Set the corresponding element in this array to indicate when
    // elements of pointList are no longer available.
    var taken = new Array(numPoints);
    for (var i = 0; i < taken.length; i++) {
      taken[i] = false;
    }

    // The resulting list of initial centers.
    var resultSet = [];

    // Choose one center uniformly at random from among the data points.
    var firstPointIndex = nextInt(numPoints);
    var firstPoint = pointList[firstPointIndex];
    resultSet.push(new CentroidCluster(firstPoint));
    // Must mark it as taken
    taken[firstPointIndex] = true;

    // To keep track of the minimum distance squared of elements of
    // pointList to elements of resultSet.

    var minDistSquared = new Float32Array(numPoints);

    // Initialize the elements.  Since the only point in resultSet is firstPoint,
    // this is very easy.
    for (var i = 0; i < numPoints; i++) {
      if (i !== firstPointIndex) { // That point isn't considered
        var d = distance(firstPoint, pointList[i]);
        minDistSquared[i] = d * d;
      }
    }

    while (resultSet.length < k) {
      // Sum up the squared distances for the points in pointList not
      // already taken.
      var distSqSum = 0.0;

      for (var i = 0; i < numPoints; i++) {
        if (!taken[i]) {
          distSqSum += minDistSquared[i];
        }
      }

      // Add one new data point as a center. Each point x is chosen with
      // probability proportional to D(x)2
      var r = nextDouble() * distSqSum;

      // The index of the next point to be added to the resultSet.
      var nextPointIndex = -1;

      // Sum through the squared min distances again, stopping when
      // sum >= r.
      var sum = 0.0;
      for (var i = 0; i < numPoints; i++) {
        if (!taken[i]) {
          sum += minDistSquared[i];
          if (sum >= r) {
            nextPointIndex = i;
            break;
          }
        }
      }

      // If it's not set to >= 0, the point wasn't found in the previous
      // for loop, probably because distances are extremely small.  Just pick
      // the last available point.
      if (nextPointIndex === -1) {
        for (var i = numPoints - 1; i >= 0; i--) {
          if (!taken[i]) {
            nextPointIndex = i;
            break;
          }
        }
      }

      // We found one.
      if (nextPointIndex >= 0) {

        var p = pointList[nextPointIndex];

        resultSet.push(new CentroidCluster(p));

        // Mark it as taken.
        taken[nextPointIndex] = true;

        if (resultSet.length < k) {
          // Now update elements of minDistSquared.  We only have to compute
          // the distance to the new center to do this.
          for (var j = 0; j < numPoints; j++) {
            // Only have to worry about the points still not taken.
            if (!taken[j]) {
              var d = distance(p, pointList[j]);
              var d2 = d * d;
              if (d2 < minDistSquared[j]) {
                minDistSquared[j] = d2;
              }
            }
          }
        }

      } else {
        // None found --
        // Break from the while loop to prevent
        // an infinite loop.
        break;
      }
    }
    return resultSet;
  }
function chooseInitialCenters ( points ) { // Convert to list for indexed access. Make it unmodifiable, since removal of items // would screw up the logic of this method. var pointList = points ; // The number of points in the list. var numPoints = pointList . length ; // Set the corresponding element in this array to indicate when // elements of pointList are no longer available. var taken = new Array ( numPoints ) ; for ( var i = 0 ; i < taken . length ; i ++ ) { taken [ i ] = false ; } // The resulting list of initial centers. var resultSet = [ ] ; // Choose one center uniformly at random from among the data points. var firstPointIndex = nextInt ( numPoints ) ; var firstPoint = pointList [ firstPointIndex ] ; resultSet . push ( new CentroidCluster ( firstPoint ) ) ; // Must mark it as taken taken [ firstPointIndex ] = true ; // To keep track of the minimum distance squared of elements of // pointList to elements of resultSet. var minDistSquared = new Float32Array ( numPoints ) ; // Initialize the elements.  Since the only point in resultSet is firstPoint, // this is very easy. for ( var i = 0 ; i < numPoints ; i ++ ) { if ( i !== firstPointIndex ) { // That point isn't considered var d = distance ( firstPoint , pointList [ i ] ) ; minDistSquared [ i ] = d * d ; } } while ( resultSet . length < k ) { // Sum up the squared distances for the points in pointList not // already taken. var distSqSum = 0.0 ; for ( var i = 0 ; i < numPoints ; i ++ ) { if ( ! taken [ i ] ) { distSqSum += minDistSquared [ i ] ; } } // Add one new data point as a center. Each point x is chosen with // probability proportional to D(x)2 var r = nextDouble ( ) * distSqSum ; // The index of the next point to be added to the resultSet. var nextPointIndex = - 1 ; // Sum through the squared min distances again, stopping when // sum >= r. var sum = 0.0 ; for ( var i = 0 ; i < numPoints ; i ++ ) { if ( ! taken [ i ] ) { sum += minDistSquared [ i ] ; if ( sum >= r ) { nextPointIndex = i ; break ; } } } // If it's not set to >= 0, the point wasn't found in the previous // for loop, probably because distances are extremely small.  Just pick // the last available point. if ( nextPointIndex === - 1 ) { for ( var i = numPoints - 1 ; i >= 0 ; i -- ) { if ( ! taken [ i ] ) { nextPointIndex = i ; break ; } } } // We found one. if ( nextPointIndex >= 0 ) { var p = pointList [ nextPointIndex ] ; resultSet . push ( new CentroidCluster ( p ) ) ; // Mark it as taken. taken [ nextPointIndex ] = true ; if ( resultSet . length < k ) { // Now update elements of minDistSquared.  We only have to compute // the distance to the new center to do this. for ( var j = 0 ; j < numPoints ; j ++ ) { // Only have to worry about the points still not taken. if ( ! taken [ j ] ) { var d = distance ( p , pointList [ j ] ) ; var d2 = d * d ; if ( d2 < minDistSquared [ j ] ) { minDistSquared [ j ] = d2 ; } } } } } else { // None found -- // Break from the while loop to prevent // an infinite loop. break ; } } return resultSet ; }
Use K-means++ to choose the initial centers.

@param points the points to choose the initial centers from
@return the initial centers
Use K - means ++ to choose the initial centers .