K均值（K-means）算法
K-means 算法是最为经典的基于划分的聚类方法，是十大经典数据挖掘算法之一。K-means算法的基本思想是：以空间中k个点为形心进行聚类，对最靠近他们的对象归类。通过迭代的方法，逐次更新各簇的形心的值，直至得到最好的聚类结果。（形心可以是实际的点、或者是虚拟点）
假设要把样本集分为c个簇，算法描述如下：
（1）适当选择c个簇的初始形心；
（2）在第k次迭代中，对任意一个样本，求其到c个形心的欧氏距离或曼哈顿距离，将该样本归类到距离最小的形心所在的簇；
（3）利用均值等方法更新该簇的形心值；
（4）对于所有的c个簇形心，如果利用（2）（3）的迭代法更新后，当形心更新稳定或误差平方和最小时，则迭代结束，否则继续迭代。（误差平方和即簇内所有点到形心的距离之和）
1. 欧氏距离(Euclidean Distance)
(1)二维平面上两点a(x1,y1)与b(x2,y2)间的欧氏距离：
(2)三维空间两点a(x1,y1,z1)与b(x2,y2,z2)间的欧氏距离：
(3)两个n维向量a(x11,x12,…,x1n)与 b(x21,x22,…,x2n)间的欧氏距离：
也可以用表示成向量运算的形式：
(4)Matlab计算欧氏距离
Matlab计算距离主要使用pdist函数。若X是一个M×N的矩阵，则pdist(X)将X矩阵M行的每一行作为一个N维向量，然后计算这M个向量两两间的距离。
例子：计算向量(0,0)、(1,0)、(0,2)两两间的欧式距离
X = [0 0 ; 1 0 ; 0 2]
D = pdist(X,'euclidean')
结果：
D =
2. 曼哈顿距离(Manhattan Distance)
(1)二维平面两点a(x1,y1)与b(x2,y2)间的曼哈顿距离
(2)两个n维向量a(x11,x12,…,x1n)与 b(x21,x22,…,x2n)间的曼哈顿距离
(3) Matlab计算曼哈顿距离
例子：计算向量(0,0)、(1,0)、(0,2)两两间的曼哈顿距离
X = [0 0 ; 1 0 ; 0 2]
D = pdist(X, 'cityblock')
结果：
D = 1
算法的优缺点：
1、优点
（1）k-平均算法是解决聚类问题的一种经典算法，算法简单、快速。
（2）对处理大数据集，该算法是相对可伸缩的和高效率的，因为它的复杂度大约是O（nkt），其中n 是所有对象的数目，k 是簇的数目,t 是迭代的次数。通常k<<n。这个算法经常以局部最优结束。
（3）算法尝试找出使平方误差函数值最小的k 个划分。当簇是密集的、球状或团状的，而簇与簇之间区别明显时，它的聚类效果很好。
2、缺点
（1）要求用户必须事先给出要生成的簇的数目k,这个K值的选定是非常难以估计的。很多时候，事先并不知道给定的数据集应该分成多少个类别才最合适。（ISODATA算法通过类的自动合并和分裂，得到较为合理的类型数目K）
（2）K-Means算法需要用初始随机种子点选择初始聚类中心。这个随机种子点太重要，不同的随机种子点会有得到完全不同的结果。（K-Means++算法可以用来解决这个问题，其可以有效地选择初始点）
（3）对初值敏感，对于不同的初始值，可能会导致不同的聚类结果。
（4）不适合于发现非凸面形状的簇，或者大小差别很大的簇。
（5）对于"噪声"和孤立点数据敏感，少量的该类数据能够对平均值产生极大影响。
K-Means++算法
先从我们的数据库随机挑个随机点当“种子点”。
对于每个点，我们都计算其和最近的一个“种子点”的距离D(x)并保存在一个数组里，然后把这些距离加起来得到Sum(D(x))。
选择一个新的数据点作为新的聚类中心，选择的原则是：D(x)较大的点，被选取作为聚类中心的概率较大（一种方法：再取一个随机值，用权重的方式来取计算下一个“种子点”。这个算法的实现是，先取一个能落在Sum(D(x))中的随机值Random，然后用Random -= D(x)，直到其<=0，此时的点就是下一个“种子点”。）
重复第（2）和第（3）步直到所有的K个种子点都被选出来。
进行K-Means算法。
Spark官方提供 kmeans例子：
import org.apache.spark.ml.clustering.KMeans
import org.apache.spark.ml.evaluation.ClusteringEvaluator
import org.apache.spark.sql.SparkSession
object KmeansDemo {
def main(args:Array[String]): Unit ={
val spark = SparkSession
.builder
.appName("KmeansDemo").master("local")
.config("spark.sql.warehouse.dir", "C:\\study\\sparktest")
.getOrCreate()
// Loads data.
val dataset=spark.read.format("libsvm").load("data/mllib/sample_kmeans_data.txt")
// Trains a k-means model.
val kmeans=new KMeans().setK(2).setSeed(1L)
val model=kmeans.fit(dataset)//Make predictions
val predictions=model.transform(dataset)// Evaluate clustering by computing Silhouette score
val evaluator = new ClusteringEvaluator()val silhouette = evaluator.evaluate(predictions)
println(s"Silhouette with squared euclidean distance = $silhouette")// Shows the result.
println("Cluster Centers: ")
model.clusterCenters.foreach(println)spark.stop()
}
}
运行结果：
18/10/23 15:41:31 INFO BlockManagerInfo: Removed broadcast_25_piece0 on 10.200.78.114:60410 in memory (size: 519.0 B, free: 1992.8 MB)
Silhouette with squared euclidean distance = 0.9997530305375207
Cluster Centers:
[0.1,0.1,0.1]
[9.1,9.1,9.1]
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。