Bisecting K-means can often be much faster than regular K-means, but it will generally produce a different clustering.

Bisecting k-means is a kind of [hierarchical clustering](https://en.wikipedia.org/wiki/Hierarchical_clustering).

Hierarchical clustering is one of the most commonly used method of cluster analysis which seeks to build a hierarchy of clusters.

Strategies for hierarchical clustering generally fall into two types:

- Agglomerative: This is a "bottom up" approach: each observation starts in its own cluster, and pairs of clusters are merged as one moves up the hierarchy.

- Divisive: This is a "top down" approach: all observations start in one cluster, and splits are performed recursively as one moves down the hierarchy.

Bisecting k-means algorithm is a kind of divisive algorithms.

The implementation in MLlib has the following parameters:

* *k*: the desired number of leaf clusters (default: 4). The actual number could be smaller if there are no divisible leaf clusters.

* *maxIterations*: the max number of k-means iterations to split clusters (default: 20)

* *minDivisibleClusterSize*: the minimum number of points (if >= 1.0) or the minimum proportion of points (if < 1.0) of a divisible cluster (default: 1)

* *seed*: a random seed (default: hash value of the class name)

**Examples**

<div class="codetabs">

<div data-lang="scala" markdown="1">

Refer to the [`BisectingKMeans` Scala docs](api/scala/index.html#org.apache.spark.mllib.clustering.BisectingKMeans) and [`BisectingKMeansModel` Scala docs](api/scala/index.html#org.apache.spark.mllib.clustering.BisectingKMeansModel) for details on the API.

{% include_example scala/org/apache/spark/examples/mllib/BisectingKMeansExample.scala %}

</div>

<div data-lang="java" markdown="1">

Refer to the [`BisectingKMeans` Java docs](api/java/org/apache/spark/mllib/clustering/BisectingKMeans.html) and [`BisectingKMeansModel` Java docs](api/java/org/apache/spark/mllib/clustering/BisectingKMeansModel.html) for details on the API.

{% include_example java/org/apache/spark/examples/mllib/JavaBisectingKMeansExample.java %}

</div>

</div>

* [bisecting k-means](mllib-clustering.html#bisecting-kmeans)

package org.apache.spark.examples.mllib;

import java.util.ArrayList;

import com.google.common.collect.Lists;

import org.apache.spark.SparkConf;

import org.apache.spark.api.java.JavaSparkContext;

import org.apache.spark.api.java.JavaRDD;

import org.apache.spark.mllib.clustering.BisectingKMeans;

import org.apache.spark.mllib.clustering.BisectingKMeansModel;

import org.apache.spark.mllib.linalg.Vector;

import org.apache.spark.mllib.linalg.Vectors;

public class JavaBisectingKMeansExample {

public static void main(String[] args) {

SparkConf sparkConf = new SparkConf().setAppName("JavaBisectingKMeansExample");

JavaSparkContext sc = new JavaSparkContext(sparkConf);

// $example on$

ArrayList<Vector> localData = Lists.newArrayList(

Vectors.dense(0.1, 0.1), Vectors.dense(0.3, 0.3),

Vectors.dense(10.1, 10.1), Vectors.dense(10.3, 10.3),

Vectors.dense(20.1, 20.1), Vectors.dense(20.3, 20.3),

Vectors.dense(30.1, 30.1), Vectors.dense(30.3, 30.3)

);

JavaRDD<Vector> data = sc.parallelize(localData, 2);

BisectingKMeans bkm = new BisectingKMeans()

.setK(4);

BisectingKMeansModel model = bkm.run(data);

System.out.println("Compute Cost: " + model.computeCost(data));

for (Vector center: model.clusterCenters()) {

System.out.println("");

}

Vector[] clusterCenters = model.clusterCenters();

for (int i = 0; i < clusterCenters.length; i++) {

Vector clusterCenter = clusterCenters[i];

System.out.println("Cluster Center " + i + ": " + clusterCenter);

}

// $example off$

sc.stop();

}

}

package org.apache.spark.examples.mllib

import org.apache.spark.mllib.clustering.BisectingKMeans

import org.apache.spark.mllib.linalg.{Vector, Vectors}

import org.apache.spark.{SparkConf, SparkContext}

object BisectingKMeansExample {

def main(args: Array[String]) {

val sparkConf = new SparkConf().setAppName("mllib.BisectingKMeansExample")

val sc = new SparkContext(sparkConf)

// $example on$

// Loads and parses data

def parse(line: String): Vector = Vectors.dense(line.split(" ").map(_.toDouble))

val data = sc.textFile("data/mllib/kmeans_data.txt").map(parse).cache()

// Clustering the data into 6 clusters by BisectingKMeans.

val bkm = new BisectingKMeans().setK(6)

val model = bkm.run(data)

// Show the compute cost and the cluster centers

println(s"Compute Cost: ${model.computeCost(data)}")

model.clusterCenters.zipWithIndex.foreach { case (center, idx) =>

println(s"Cluster Center ${idx}: ${center}")

}

// $example off$

sc.stop()

}

}