Spark-K-Means算法

机器学习算法大体分为三类：监督学习（supervised learning）、无监督学习（unsupervised learning）和半监督学习（semi-supervised learning）。监督学习是指我们利用带有类别属性标注的数据去训练、学习，用于预测未知数据的类别属性。例如，根据用户之前的购物行为去预测用户是否会购买某一商品。常用的算法有决策树，支持向量机SVM，朴素贝叶斯分类器，K-近邻算法KNN，线性回归和逻辑回归等.无监督学习是指在无人工干预的情况下将数据按照相似程度划分，而聚类算法就是非常典型的无监督学习方法，通常要处理的数据没有标签信息，可以通过计算数据之间的相似性来自动划分类别。

K-Means算法

算法的思想是初始随机给定K个簇中心，按照距离最近原则把待分类的样本点分到各个簇，然后按平均法重新计算各个簇的质心，从而确定新的簇心，迭代计算，直到簇心的移动距离小于某个给定的误差值。使用算法描述语言，只要四个步骤：

任意选择K个点作为初始聚类中心；
计算每个样本点到聚类中心的距离，将每个样本点划分到离该点最近的聚类中去；
计算每个聚类中所有点的坐标平均值，并将这个平均值作为新的聚类中心；
反复执行2、3，直到聚类中心的移动小于某误差值或者聚类次数达到要求为止。

这里计算距离的方法通常是计算欧几里得距离，假设中心点center是(x1, y1)，需要计算的样本点point是(x2, y2)：

另外，给出损失函数（Cost Function），每一次选取好新的中心点，我们就要计算一下当前选好的中心点损失为多少，这个损失代表着偏移量，越大说明当前聚类的效果越差，计算公式称为（Within-Cluster Sum of Squares, WCSS）：

其中，xi表示某一对象，ck表示该对象所属类别的中心点。整个式子的含义就是对各个类别下的对象，求对象与中心点的欧式距离的平方，把所有的平方求和就是L(C)。

测试数据： 0.0 0.0 0.1 0.1 0.2 0.2 3.0 3.0 3.1 3.1 3.2 3.2 9.0 9.0 9.1 9.1 9.2 9.2

import org.apache.spark.mllib.clustering.KMeans import org.apache.spark.mllib.linalg.Vectors import org.apache.spark.{SparkConf, SparkContext} object KMeansTest { def main(args: Array[String]) { val conf = new SparkConf() val sc = new SparkContext(conf) val data =sc.textFile(args(0)) val parsedData =data.map(s => Vectors.dense(s.split(' ').map(_.trim.toDouble))).cache() //设置簇的个数为3 val numClusters =3 //迭代20次 val numIterations= 20 //运行10次,选出最优解 val runs=10 //设置初始K选取方式为k-means++ val initMode = "k-means||" val clusters = new KMeans(). setInitializationMode(initMode). setK(numClusters). setMaxIterations(numIterations). run(parsedData) //打印出测试数据属于哪个簇 println(parsedData.map(v=> v.toString() + " belong to cluster :" +clusters.predict(v)).collect().mkString("\n")) // Evaluateclustering by computing Within Set Sum of Squared Errors val WSSSE = clusters.computeCost(parsedData) println("WithinSet Sum of Squared Errors = " + WSSSE) val a21 =clusters.predict(Vectors.dense(1.2,1.3)) val a22 =clusters.predict(Vectors.dense(4.1,4.2)) //打印出中心点 println("Clustercenters:") for (center <-clusters.clusterCenters) { println(" "+ center) } println("Prediction of (1.2,1.3)-->"+a21) println("Prediction of (4.1,4.2)-->"+a22) } }

提交spark执行（standalone）： spark-submit --class KMeansTest --master local[4] KMeansTest.jar ../data/kmeans_data.txt

K-Means算法有两个重大缺陷：

K-Means属于无监督学习，最大的特别和优势在于模型的建立不需要训练数据。在日常工作中，很多情况下没有办法事先获取到有效的训练数据，这时采用K-Means是一个不错的选择。K值是预先给定的，属于预先知识，很多情况下K值的估计是非常困难的，对于像计算全部微信用户的交往圈这样的场景就完全的没办法用K-Means进行。对于可以确定K值不会太大但不明确精确的K值的场景，可以进行迭代运算，然后找出Cost Function最小时所对应的K值，这个值往往能较好的描述有多少个簇类。
K-Means算法对初始选取的聚类中心点是敏感的，不同的随机种子点得到的聚类结果完全不同。可以用K-Means++算法来解决这个问题
K-Means++算法选择初始聚类中心的思想是：初始的聚类中心之间的相互距离要尽可能远。算法步骤如下：

随机挑选一个点作为第一个聚类中心；
对于每一个点x，计算和其最近的一个聚类中心的距离D(x)，将所有距离求和得到Sum(D(x))；
然后，再取一个随机值，用权重的方式来取计算下一个“种子点”。这个算法的思想是，先取一个能落在Sum(D(x))中的随机值Random，然后用Random -= D(x)，直到其<=0，此时的点就是下一个“种子点”（其思想是，D(x)较大的点，被选取作为聚类中心的概率较大）；
重复2和3，直到K个聚类中心被选出来；
利用这K个初始聚类中心进行K-Means算法。

Spark的MLlib库中也支持K-Means++初始化方法，只需增加初始模式设置：

val initMode = "k-means||" val clusters = new KMeans(). setInitializationMode(initMode). setK(numClusters). setMaxIterations(numIterations). run(parsedData)