大数据十大经典算法节解.ppt

LOGO The algorithm of Kmeans 小组成员：徐佳、张俊飞、刘志伟、孔祥玉 主要内容： Kmeans实战 聚类算法简介 Kmeans算法详解 Kmeans算法的缺陷及若干改进 Kmeans的单机实现与分布式实现策略 聚类算法简介 1 2 3 聚类的目标：将一组向量分成若干组，组内数据是相似的，而组间数据是有较明显差异。 与分类区别：分类与聚类最大的区别在于分类的目标事先已知，聚类也被称为无监督机器学习 聚类手段：传统聚类算法 ①划分法 ②层次方法 ③基于密度方法 ④基于网络方法 ⑤基于模型方法 什么是Kmeans算法？ Q1：K是什么？A1：k是聚类算法当中类的个数。 Summary：Kmeans是用均值算法把数据分成K个类的算法！ Q2：means是什么？A2：means是均值算法。 Kmeans算法详解（1） 步骤一：取得k个初始初始中心点 Kmeans算法详解（2） Min of three due to the EuclidDistance 步骤二：把每个点划分进相应的簇 Kmeans算法详解（3） Min of three due to the EuclidDistance 步骤三：重新计算中心点 Kmeans算法详解（4） 步骤四：迭代计算中心点 Kmeans算法详解（5） 步骤五：收敛 Kmeans算法流程 从数据中随机抽取k个点作为初始聚类的中心，由这个中心代表各个聚类 计算数据中所有的点到这k个点的距离，将点归到离其最近的聚类里 调整聚类中心，即将聚类的中心移动到聚类的几何中心（即平均值）处，也就是k-means中的mean的含义 重复第2步直到聚类的中心不再移动，此时算法收敛 最后kmeans算法时间、空间复杂度是： 时间复杂度：上限为O(tKmn)，下限为Ω（Kmn）其中，t为迭代次数，K为簇的数目，m为记录数，n为维数 空间复杂度：O((m+K)n)，其中，K为簇的数目，m为记录数，n为维数 决定性因素 Input centroids Selected k MaxIterations Convergence Meassures ①数据的采集和抽象 ②初始的中心选择 ①最大迭代次数 ②收敛值 ① k值的选定 ①度量距离的手段 factors？ 主要讨论 初始中心点 输入的数据及K值的选择 距离度量 我们主要研究的三个方面因素。 初始中心点的划分 讨论初始中心点意义何在？下面的例子一目了然吧？ 初始中心点 收敛后 你 懂 的 … 如何衡量Kmeans算法的精确度？ 在进一步阐述初始中心点选择之前，我们应该先确定度量kmeans的算法精确度的方法。一种度量聚类效果的标准是：SSE(Sum of Square Error，误差平方和) SSE越小表示数据点越接近于它们的质心，聚类效果也就越好。因为对误差取了平方所以更重视那些远离中心的点。 一种可以肯定降低SSE的方法是增加簇的个数。但这违背了聚类的目标。因为聚类是在保持目标簇不变的情况下提高聚类的质量。 现在思路明了了我们首先以缩小SSE为目标改进算法。 改进的算法——二分Kmeans算法 为了克服k均值算法收敛于局部的问题，提出了二分k均值算法。该算法首先将所有的点作为一个簇，然后将该簇一分为二。之后选择其中一个簇继续划分，选择哪个簇进行划分取决于对其划分是否可以最大程度降低SSE值。 伪代码如下： 将所有的点看成一个簇 当簇数目小于k时 对于每一个簇 计算总误差 在给定的簇上面进行K均值聚类(K=2) 计算将该簇一分为二后的总误差 选择使得误差最小的那个簇进行划分操作 二分Kmeans算法的效果 既然是改进算法就要体现改进算法的优越性。为此控制变量，在相同的实验环境下，①取相同的k值取。 ②选取相同的的距离度量标准（欧氏距离） ③在相同的数据集下进行测试。 一组实验结果 一组不好的初始点产生的Kmeans算法结果 二分kmeans产生的结果 要强调的是尽管只是这一组实验不得以得出二分kmeans的优越性，但是经过大量实验得出的结论却是在大多数情况下二分kmeans确实优于朴素的kmeans算法。 全局最小值 二分kmeans真的能使SSE达到全局最小值吗？ 从前面的讲解可以看到二分kmeans算法的思想有点类似于贪心思想。但是我们会发现贪心的过程中有不确定的因素比如：二分一个聚类时选取的两个中间点是随机的，这会对我们的策略造成影响。那么如此一来二分kmeans算法会不会达到全局最优解呢？答案是：会！尽管你可能惊诧于下面的说法，但全局最小值的定义却是：可能的最好结果。 K值的选择以及坏点的剔除 讨论k值、剔除坏点的意义何在？下面以一个