protected static Clustering kMeans()

in samoa-api/src/main/java/org/apache/samoa/moa/clusterers/clustream/WithKmeans.java [297:348]

• 41 lines of code
• 10 McCabe index (conditional complexity)

  protected static Clustering kMeans(int k, Cluster[] centers, List<? extends Cluster> data) {
    assert (centers.length == k);
    assert (k > 0);

    int dimensions = centers[0].getCenter().length;

    ArrayList<ArrayList<Cluster>> clustering = new ArrayList<ArrayList<Cluster>>();
    for (int i = 0; i < k; i++) {
      clustering.add(new ArrayList<Cluster>());
    }

    while (true) {
      // Assign points to clusters
      for (Cluster point : data) {
        double minDistance = distance(point.getCenter(), centers[0].getCenter());
        int closestCluster = 0;
        for (int i = 1; i < k; i++) {
          double distance = distance(point.getCenter(), centers[i].getCenter());
          if (distance < minDistance) {
            closestCluster = i;
            minDistance = distance;
          }
        }

        clustering.get(closestCluster).add(point);
      }

      // Calculate new centers and clear clustering lists
      SphereCluster[] newCenters = new SphereCluster[centers.length];
      for (int i = 0; i < k; i++) {
        newCenters[i] = calculateCenter(clustering.get(i), dimensions);
        clustering.get(i).clear();
      }

      // Convergence check
      boolean converged = true;
      for (int i = 0; i < k; i++) {
        if (!Arrays.equals(centers[i].getCenter(), newCenters[i].getCenter())) {
          converged = false;
          break;
        }
      }

      if (converged) {
        break;
      } else {
        centers = newCenters;
      }
    }

    return new Clustering(centers);
  }