Github user mengxr commented on a diff in the pull request: https://github.com/apache/spark/pull/5267#discussion_r42820990 --- Diff: mllib/src/main/scala/org/apache/spark/mllib/clustering/BisectingKMeans.scala --- @@ -0,0 +1,690 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package org.apache.spark.mllib.clustering + +import scala.collection.{Map, mutable} + +import breeze.linalg + .{SparseVector => BSV, Vector => BV, any => breezeAny, norm => breezeNorm, sum => breezeSum} + +import org.apache.spark.{Logging, SparkException} +import org.apache.spark.annotation.Since +import org.apache.spark.mllib.linalg.{Vector, Vectors} +import org.apache.spark.rdd.RDD + + +/** + * This is a divisive hierarchical clustering algorithm based on bisecting k-means algorithm. + * + * The main idea of this algorithm is based on "A comparison of document clustering techniques", + * M. Steinbach, G. Karypis and V. Kumar. Workshop on Text Mining, KDD, 2000. + * http://cs.fit.edu/~pkc/classes/ml-internet/papers/steinbach00tr.pdf + * + * However, we modified it to fit for Spark. This algorithm consists of the two main parts. + * + * 1. Split clusters until the number of clusters will be enough to build a cluster tree + * 2. Build a cluster tree as a binary tree by the splitted clusters + * + * First, it splits clusters to their children clusters step by step, not considering a cluster + * will be included in the final cluster tree or not. That's because it makes the algorithm more + * efficient on Spark and splitting a cluster one by one is very slow. It will keep splitting until + * the number of clusters will be enough to build a cluster tree. Otherwise, it will stop splitting + * when there are no dividable clusters before the number of clusters will be sufficient. And + * it calculates the criterions, such as average cost, entropy and so on, for building a cluster + * tree in the first part. The criterion means how large the cluster is. That is, the cluster + * whose criterion is maximum of all the clusters is the largest cluster. + * + * Second, it builds a cluster tree as a binary tree by the result of the first part. + * First of all, the cluster tree starts with only the root cluster which includes all points. + * So, there are two candidates which can be merged to the cluster tree. Those are the children of + * the root. Then, it picks up the larger child of the two and merge it to the cluster tree. + * After that, there are tree candidates to merge. Those are the smaller child of the root and + * the two children of the larger cluster of the root. It picks up the largest cluster of the tree + * and merge it to the * cluster tree. Like this, it continues to pick up the largest one of the + * candidates and merge it to the cluster tree until the desired number of clusters is reached. + * + * @param k tne desired number of clusters + * @param clusterMap the pairs of cluster and its index as Map + * @param maxIterations the number of maximal iterations to split clusters + * @param seed a random seed + */ +@Since("1.6.0") +class BisectingKMeans private ( + private var k: Int, + private var clusterMap: Map[BigInt, BisectingClusterNode], + private var maxIterations: Int, + private var seed: Long) extends Logging { + --- End diff -- `import BisectingKMeans._`
--- If your project is set up for it, you can reply to this email and have your reply appear on GitHub as well. If your project does not have this feature enabled and wishes so, or if the feature is enabled but not working, please contact infrastructure at infrastruct...@apache.org or file a JIRA ticket with INFRA. --- --------------------------------------------------------------------- To unsubscribe, e-mail: reviews-unsubscr...@spark.apache.org For additional commands, e-mail: reviews-h...@spark.apache.org