k-means helper: Calculate a wrapping cluster of assigned points[microclusters].

@param assigned
@param dimensions
@return SphereCluster (with center and radius)
490671
private static SphereCluster calculateCenter(ArrayList<Cluster> assigned, int dimensions) {
		double[] result = new double[dimensions];
		for (int i = 0; i < result.length; i++) {
			result[i] = 0.0;
		}

		if (assigned.size() == 0) {
			return new SphereCluster(result, 0.0);
		}

		for (Cluster point : assigned) {
			double[] center = point.getCenter();
			for (int i = 0; i < result.length; i++) {
				result[i] += center[i];
			}
		}

		// Normalize
		for (int i = 0; i < result.length; i++) {
			result[i] /= assigned.size();
		}

		// Calculate radius: biggest wrapping distance from center
		double radius = 0.0;
		for (Cluster point : assigned) {
			double dist = distance(result, point.getCenter());
			if (dist > radius) {
				radius = dist;
			}
		}
		SphereCluster sc = new SphereCluster(result, radius);
		sc.setWeight(assigned.size());
		return sc;
	}
477409
public double evaluateClustering(Database db, Relation<O> rel, Clustering<?> cl) {
    final DistanceQuery<O> dq = rel.getDistanceQuery(distanceFunction);

    List<? extends Cluster<?>> clusters = cl.getAllClusters();
    final int numc = clusters.size();

    // DBCV needs a "dimensionality".
    @SuppressWarnings("unchecked")
    final Relation<? extends SpatialComparable> vrel = (Relation<? extends SpatialComparable>) rel;
    final int dim = RelationUtil.dimensionality(vrel);

    // precompute all core distances
    ArrayDBIDs[] cids = new ArrayDBIDs[numc];
    double[][] coreDists = new double[numc][];
    for(int c = 0; c < numc; c++) {
      Cluster<?> cluster = clusters.get(c);
      // Singletons are considered as Noise, because they have no sparseness
      if(cluster.isNoise() || cluster.size() < 2) {
        coreDists[c] = null;
        continue;
      }
      // Store for use below:
      ArrayDBIDs ids = cids[c] = DBIDUtil.ensureArray(cluster.getIDs());
      double[] clusterCoreDists = coreDists[c] = new double[ids.size()];
      for(DBIDArrayIter it = ids.iter(), it2 = ids.iter(); it.valid(); it.advance()) {
        double currentCoreDist = 0;
        int neighbors = 0;
        for(it2.seek(0); it2.valid(); it2.advance()) {
          if(DBIDUtil.equal(it, it2)) {
            continue;
          }
          double dist = dq.distance(it, it2);
          // Unfortunately, the DBCV definition has a division by zero.
          // We ignore such objects.
          if(dist > 0) {
            currentCoreDist += MathUtil.powi(1. / dist, dim);
            ++neighbors;
          }
        }
        // Average, and undo power.
        clusterCoreDists[it.getOffset()] = FastMath.pow(currentCoreDist / neighbors, -1. / dim);
      }
    }

    // compute density sparseness of all clusters
    int[][] clusterDegrees = new int[numc][];
    double[] clusterDscMax = new double[numc];
    // describes if a cluster contains any internal edges
    boolean[] internalEdges = new boolean[numc];
    for(int c = 0; c < numc; c++) {
      Cluster<?> cluster = clusters.get(c);
      if(cluster.isNoise() || cluster.size() < 2) {
        clusterDegrees[c] = null;
        clusterDscMax[c] = Double.NaN;
        continue;
      }
      double[] clusterCoreDists = coreDists[c];
      ArrayDBIDs ids = cids[c];
      double dscMax = 0; // Density Sparseness of the Cluster
      double[][] distances = new double[cluster.size()][cluster.size()];

      // create mutability distance matrix for Minimum Spanning Tree
      for(DBIDArrayIter it = ids.iter(), it2 = ids.iter(); it.valid(); it.advance()) {
        double currentCoreDist = clusterCoreDists[it.getOffset()];
        for(it2.seek(it.getOffset() + 1); it2.valid(); it2.advance()) {
          double mutualReachDist = MathUtil.max(currentCoreDist, clusterCoreDists[it2.getOffset()], dq.distance(it, it2));
          distances[it.getOffset()][it2.getOffset()] = mutualReachDist;
          distances[it2.getOffset()][it.getOffset()] = mutualReachDist;
        }
      }

      // generate Minimum Spanning Tree
      int[] nodes = PrimsMinimumSpanningTree.processDense(distances);

      // get degree of all nodes in the spanning tree
      int[] degree = new int[cluster.size()];
      for(int i = 0; i < nodes.length; i++) {
        degree[nodes[i]]++;
      }
      // check if cluster contains any internal edges
      for(int i = 0, e = nodes.length - 1; i < e; i += 2) {
        if(degree[nodes[i]] > 1 && degree[nodes[i + 1]] > 1) {
          internalEdges[c] = true;
        }
      }

      clusterDegrees[c] = degree;

      // find maximum sparseness in the Minimum Spanning Tree
      for(int i = 0, e = nodes.length - 1; i < e; i += 2) {
        final int n1 = nodes[i], n2 = nodes[i + 1];
        // We only consider edges where both vertices are internal nodes.
        // If a cluster has no internal nodes we consider all edges.
        if(distances[n1][n2] > dscMax && (!internalEdges[c] || (degree[n1] > 1 && degree[n2] > 1))) {
          dscMax = distances[n1][n2];
        }
      }
      clusterDscMax[c] = dscMax;
    }

    // compute density separation of all clusters
    double dbcv = 0;
    for(int c = 0; c < numc; c++) {
      Cluster<?> cluster = clusters.get(c);
      if(cluster.isNoise() || cluster.size() < 2) {
        continue;
      }
      double currentDscMax = clusterDscMax[c];
      double[] clusterCoreDists = coreDists[c];
      int[] currentDegree = clusterDegrees[c];

      // minimal Density Separation of the Cluster
      double dspcMin = Double.POSITIVE_INFINITY;
      for(DBIDArrayIter it = cids[c].iter(); it.valid(); it.advance()) {
        // We again ignore external nodes, if the cluster has any internal
        // nodes.
        if(currentDegree[it.getOffset()] < 2 && internalEdges[c]) {
          continue;
        }
        double currentCoreDist = clusterCoreDists[it.getOffset()];
        for(int oc = 0; oc < numc; oc++) {
          Cluster<?> ocluster = clusters.get(oc);
          if(ocluster.isNoise() || ocluster.size() < 2 || cluster == ocluster) {
            continue;
          }
          int[] oDegree = clusterDegrees[oc];
          double[] oclusterCoreDists = coreDists[oc];
          for(DBIDArrayIter it2 = cids[oc].iter(); it2.valid(); it2.advance()) {
            if(oDegree[it2.getOffset()] < 2 && internalEdges[oc]) {
              continue;
            }
            double mutualReachDist = MathUtil.max(currentCoreDist, oclusterCoreDists[it2.getOffset()], dq.distance(it, it2));
            dspcMin = mutualReachDist < dspcMin ? mutualReachDist : dspcMin;
          }
        }
      }

      // compute DBCV
      double vc = (dspcMin - currentDscMax) / MathUtil.max(dspcMin, currentDscMax);
      double weight = cluster.size() / (double) rel.size();
      dbcv += weight * vc;
    }

    EvaluationResult ev = EvaluationResult.findOrCreate(db.getHierarchy(), cl, "Internal Clustering Evaluation", "internal evaluation");
    MeasurementGroup g = ev.findOrCreateGroup("Distance-based Evaluation");
    g.addMeasure("Density Based Clustering Validation", dbcv, 0., Double.POSITIVE_INFINITY, 0., true);
    db.getHierarchy().resultChanged(ev);
    return dbcv;
  }
1279285
public <E extends WeightedEdge> MultiMap<Integer,Integer> cluster(
              final WeightedGraph<E> graph, int numClusters, Properties props) {
        if (props.getProperty(KEEP_WEIGHT_VECTORS_PROPERTY) != null)
            keepWeightVectors = Boolean.parseBoolean(
                props.getProperty(KEEP_WEIGHT_VECTORS_PROPERTY));
        vertexToWeightVector.clear();
        return super.cluster(graph, numClusters, props);
    }
38686
def _assign_clusters(self):
        
        self.clusters = np.array([self._closest_centroid(x) for x in self._X])
17089
@SuppressWarnings("WeakerAccess")
  public Cluster resizeCluster(String instanceId, String clusterId, int numServeNodes) {
    return ApiExceptions.callAndTranslateApiException(
        resizeClusterAsync(instanceId, clusterId, numServeNodes));
  }
413533
public static MeanVariance[] newArray(int dimensionality) {
    MeanVariance[] arr = new MeanVariance[dimensionality];
    for(int i = 0; i < dimensionality; i++) {
      arr[i] = new MeanVariance();
    }
    return arr;
  }
463781
public Assignments cluster(Matrix m,
                               int maxClusters,
                               Properties props) {
        int startSize = Integer.parseInt(props.getProperty(
                NUM_CLUSTERS_START, DEFAULT_NUM_CLUSTERS_START));
        int numGaps = Integer.parseInt(props.getProperty(
                NUM_REFERENCE_DATA_SETS, DEFAULT_NUM_REFERENCE_DATA_SETS));
        int numIterations = maxClusters - startSize;
        String criterion = props.getProperty(METHOD_PROPERTY, DEFAULT_METHOD);

        verbose("Transforming the original data set");
        Transform tfidf = new TfIdfDocStripedTransform();
        Transform rowMag = new RowMagnitudeTransform();
        m = rowMag.transform(tfidf.transform(m));

        verbose("Generating the reference data set");
        // Generate the reference data sets.
        ReferenceDataGenerator generator = new ReferenceDataGenerator(m);
        Matrix[] gapMatrices = new Matrix[numGaps];
        for (int i = 0; i < numGaps; ++i)
            gapMatrices[i] = rowMag.transform(tfidf.transform(
                    generator.generateTestData()));

        double[] gapResults = new double[numIterations];
        double[] gapStds = new double[numIterations];
        Assignments[] gapAssignments = new Assignments[numIterations];

        Assignments bestAssignments = null;
        double bestGap = Double.NEGATIVE_INFINITY;
        int bestK = 0;
        // Compute the gap statistic for each iteration.
        for (int i = 0; i < numIterations; ++i) {
            clusterIteration(i, startSize, criterion, m, gapMatrices,
                             gapResults, gapStds, gapAssignments);
            if (bestGap >= (gapResults[i] - gapStds[i])) {
                break;
            }

            // Otherwise, continue clustering with higher values of k.
            bestGap = gapResults[i];
            bestAssignments = gapAssignments[i];
            bestK = i + startSize;
        }

        return bestAssignments;
    }
1262481
def cluster(self, dist_type='cosine', run_clustering=True,
                 dendro=True, views=['N_row_sum', 'N_row_var'],
                 linkage_type='average', sim_mat=False, filter_sim=0.1,
                 calc_cat_pval=False, run_enrichr=None, enrichrgram=None):
    '''
    
    '''
    initialize_net.viz(self)

    make_clust_fun.make_clust(self, dist_type=dist_type, run_clustering=run_clustering,
                                   dendro=dendro,
                                   requested_views=views,
                                   linkage_type=linkage_type,
                                   sim_mat=sim_mat,
                                   filter_sim=filter_sim,
                                   calc_cat_pval=calc_cat_pval,
                                   run_enrichr=run_enrichr,
                                   enrichrgram=enrichrgram)
1196532
def init_pp(X, n_clusters, random_state):
    
    x_squared_norms = row_norms(X, squared=True).compute()
    logger.info("Initializing with k-means++")
    with _timer("initialization of %2d centers" % n_clusters, _logger=logger):
        centers = sk_k_means._k_init(
            X, n_clusters, random_state=random_state, x_squared_norms=x_squared_norms
        )

    return centers
554718
@Override
	public Clustering getClusteringResult() {
		List<double[]> microClustering;
		// If the buffer phase is active then the buffer (without duplicates) is
		// equal to the micro clustering
		if (this.bufferPhase) {
			microClustering = new ArrayList<double[]>(this.buffer.size());
			for (double[] pointA : this.buffer) {
				// Searches for a duplicate of the current point
				boolean duplicate = false;
				for (double[] pointB : microClustering) {
					int i;
					for (i = 0; i < pointA.length; i++) {
						if (pointA[i] != pointB[i + 1]) {
							break;
						}
					}
					if (i == pointA.length) {
						duplicate = true;
						pointB[0] += 1;
						break;
					}
				}

				if (!duplicate) {
					// Copies the point to an array with the weight in the first
					// element
					double[] pointWeighted = new double[pointA.length + 1];
					pointWeighted[0] = 1;
					System.arraycopy(pointA, 0, pointWeighted, 1, pointA.length);
					microClustering.add(pointWeighted);
				}
			}
		} else {
			// Collects all nodes as arrays with the weight in the first element
			microClustering = this.root
					.addToClusteringCenters(new ArrayList<double[]>(this.rootCount));
		}
		// Runs the k-means algorithm five times on the micro clustering
		List<double[]> result = null;
		double minValue = Double.POSITIVE_INFINITY;
		for (int i = 0; i < 5; i++) {
			// Creates the starting centroids
			List<double[]> newResult = CoresetKMeans
					.generatekMeansPlusPlusCentroids(this.numClusters,
							microClustering, this.clustererRandom);
			// Runs the k-means algorithm with changing the starting centroids
			double newValue = CoresetKMeans.kMeans(newResult, microClustering);
			// Selects the result with minimum costs
			if (newValue < minValue) {
				result = newResult;
				minValue = newValue;
			}
		}

		// Prepares the points for the clustering result
		AutoExpandVector<Cluster> resultClustering = new AutoExpandVector<Cluster>(
				result.size());
		for (double[] point : result) {
			resultClustering.add(new SphereCluster(point, 0.0));
		}
		return new Clustering(resultClustering);
	}
178294
private void logClusterSizes(String m, int dimensionality, Object2ObjectOpenCustomHashMap<long[], List<ArrayModifiableDBIDs>> clustersMap) {
    if(LOG.isVerbose()) {
      final StringBuilder msg = new StringBuilder(1000).append(m).append('\n');
      for(ObjectIterator<Object2ObjectMap.Entry<long[], List<ArrayModifiableDBIDs>>> iter = clustersMap.object2ObjectEntrySet().fastIterator(); iter.hasNext();) {
        Object2ObjectMap.Entry<long[], List<ArrayModifiableDBIDs>> entry = iter.next();
        msg.append(BitsUtil.toStringLow(entry.getKey(), dimensionality)).append(" sizes:");
        for(ArrayModifiableDBIDs c : entry.getValue()) {
          msg.append(' ').append(c.size());
        }
        msg.append('\n');
      }
      LOG.verbose(msg.toString());
    }
  }
611351
def cluster_assignments(self):
        
        array = javabridge.call(self.jobject, "getClusterAssignments", "()[D")
        if array is None:
            return None
        else:
            return javabridge.get_env().get_double_array_elements(array)
699998
private void clusterTerm(String senseName,
                             List<SparseDoubleVector> contextSet,
                             Properties props) {
        // Convert the data points to a sparse matrix.
        SparseMatrix contexts = Matrices.asSparseMatrix(contextSet);

        // Cluster the context set.
        LOG.info("Clustering term: " + senseName);
        Assignments assignments = (numClusters > 0) 
            ? clustering.cluster(contexts, numClusters, props)
            : clustering.cluster(contexts, props);
        LOG.info("Finished clustering term: " + senseName);

        SparseDoubleVector[] centroids = assignments.getSparseCentroids();

        // Add the centroids to the splitSenses map.
        for (int index = 0; index < centroids.length; ++index) {
            String sense = (index > 0)
                    ? senseName + "-" + index
                    : senseName;
            wordSpace.put(sense, centroids[index]);
        }

        LOG.info("Finished creating centroids for term: " + senseName);

        // Empty out the stored contexts to free up memory for later processes.
        contextSet.clear();

        // If the reporter is null, avoid making any report.
        if (reporter == null)
            return;

        // Generate the secondary context labels for each data point.
        String[] contextLabels = reporter.contextLabels(senseName);
        if (contextLabels.length == 0)
            return;

        LOG.info("Making assignment report: " + senseName);
        // Report the assignments for each clustered data point.  Note that some
        // data points might not have been clustered (Cluto based clustering
        // does this on occasion) so we must check for the number of assignments
        // first.
        for (int i = 0; i < assignments.size(); ++i)
            if (assignments.get(i).assignments().length > 0)
                reporter.updateAssignment(senseName, contextLabels[i],
                                          assignments.get(i).assignments()[0]);
        LOG.info("Finished making assignment report: " + senseName);
    }
231143
public double getHullDistance(SphereCluster other) {
		double distance = 0.0;
		//get the center through getCenter so subclass have a chance
		double[] center0 = getCenter();
		double[] center1 = other.getCenter();
		distance = distance(center0, center1);

		distance = distance - getRadius() - other.getRadius();
		return distance;
	}
867924
function(k,assignments) {
        this.logger = Logger.getLogger("PowerIterationClusteringModel_js");
        var jvmObject;
        if (k instanceof org.apache.spark.mllib.clustering.PowerIterationClusteringModel) {
            jvmObject = k;
        } else {
            jvmObject = new org.apache.spark.mllib.clustering.PowerIterationClusteringModel(k,assignments);
        }

         JavaWrapper.call(this, jvmObject);

    }
572300
public static double kMeans(List<double[]> centroids, List<double[]> input) {
		int k = centroids.size();
		assert (k > 0);
		int d = centroids.get(0).length;
		int size = input.size();

		double[][] center = new double[k][];
		Iterator<double[]> iIter = centroids.iterator();
		for (int i = 0; i < k; i++) {
			center[i] = iIter.next();
		}

		double[][] newCenter = new double[k][d];
		double[] newCenterWeight = new double[k];
		int[] nearestCluster = new int[size];
		boolean converged;
		do {
			for (int i = 0; i < k; i++) {
				for (int j = 0; j < d; j++) {
					newCenter[i][j] = 0.0;
				}
				newCenterWeight[i] = 0.0;
			}
			Iterator<double[]> lIter = input.iterator();
			for (int l = 0; l < size; l++) {
				// Calculates the distance from all points to all centroids
				double[] point = lIter.next();
				assert (d == point.length - 1);
				double minDistance = Double.POSITIVE_INFINITY;
				int closestCluster = -1;
				for (int i = 0; i < k; i++) {
					double distance = Metric.distance(center[i], point, 1);
					if (distance < minDistance) {
						closestCluster = i;
						minDistance = distance;
					}
				}

				// Sums up all points for the new centroids
				assert (closestCluster >= 0 && closestCluster < k);
				for (int j = 0; j < d; j++) {
					newCenter[closestCluster][j] += point[0] * point[j + 1];
				}
				newCenterWeight[closestCluster] += point[0];
				nearestCluster[l] = closestCluster;
			}

			// Calculates the new centroids
			converged = true;
			for (int i = 0; i < k; i++) {
				for (int j = 0; j < d; j++) {
					if (newCenterWeight[i] != 0.0) {
						double newValue = newCenter[i][j] / newCenterWeight[i];
						if (newValue != center[i][j]) {
							converged = false;
						}
						center[i][j] = newValue;
					}
				}
			}
		} while (!converged);
		// Replaces the old centroids with the new ones
		for (int i = 0; i < k; i++) {
			centroids.set(i, center[i]);
		}

		// Calculates the costs of the solution
		double costs = 0.0;
		Iterator<double[]> lIter = input.iterator();
		for (int l = 0; l < size; l++) {
			double[] point = lIter.next();
			costs += point[0]
					* Metric.distanceSquared(center[nearestCluster[l]], point,
							1);
		}
		return costs;
	}
877320
def _spherical_kmeans_single_lloyd(
    X,
    n_clusters,
    sample_weight=None,
    max_iter=300,
    init="k-means++",
    verbose=False,
    x_squared_norms=None,
    random_state=None,
    tol=1e-4,
    precompute_distances=True,
):
    
    random_state = check_random_state(random_state)

    sample_weight = _check_sample_weight(X, sample_weight)

    best_labels, best_inertia, best_centers = None, None, None

    # init
    centers = _init_centroids(
        X, n_clusters, init, random_state=random_state, x_squared_norms=x_squared_norms
    )
    if verbose:
        print("Initialization complete")

    # Allocate memory to store the distances for each sample to its
    # closer center for reallocation in case of ties
    distances = np.zeros(shape=(X.shape[0],), dtype=X.dtype)

    # iterations
    for i in range(max_iter):
        centers_old = centers.copy()

        # labels assignment
        # TODO: _labels_inertia should be done with cosine distance
        #       since ||a - b|| = 2(1 - cos(a,b)) when a,b are unit normalized
        #       this doesn't really matter.
        labels, inertia = _labels_inertia(
            X,
            sample_weight,
            x_squared_norms,
            centers,
            precompute_distances=precompute_distances,
            distances=distances,
        )

        # computation of the means
        if sp.issparse(X):
            centers = _k_means._centers_sparse(
                X, sample_weight, labels, n_clusters, distances
            )
        else:
            centers = _k_means._centers_dense(
                X, sample_weight, labels, n_clusters, distances
            )

        # l2-normalize centers (this is the main contibution here)
        centers = normalize(centers)

        if verbose:
            print("Iteration %2d, inertia %.3f" % (i, inertia))

        if best_inertia is None or inertia < best_inertia:
            best_labels = labels.copy()
            best_centers = centers.copy()
            best_inertia = inertia

        center_shift_total = squared_norm(centers_old - centers)
        if center_shift_total <= tol:
            if verbose:
                print(
                    "Converged at iteration %d: "
                    "center shift %e within tolerance %e" % (i, center_shift_total, tol)
                )
            break

    if center_shift_total > 0:
        # rerun E-step in case of non-convergence so that predicted labels
        # match cluster centers
        best_labels, best_inertia = _labels_inertia(
            X,
            sample_weight,
            x_squared_norms,
            best_centers,
            precompute_distances=precompute_distances,
            distances=distances,
        )

    return best_labels, best_inertia, best_centers, i + 1