大数据经典算法Kmeans讲解

大数据经典算法Kmeans讲解第1页，课件共30页，创作于2023年2月主要内容：Kmeans实战聚类算法简介Kmeans算法详解Kmeans算法的缺陷及若干改进Kmeans的单机实现与分布式实现策略

第2页，课件共30页，创作于2023年2月聚类算法简介123聚类的目标：将一组向量分成若干组，组内数据是相似的，而组间数据是有较明显差异。与分类区别：分类与聚类最大的区别在于分类的目标事先已知，聚类也被称为无监督机器学习聚类手段：传统聚类算法①划分法②层次方法③基于密度方法

④基于网络方法

⑤基于模型方法第3页，课件共30页，创作于2023年2月什么是Kmeans算法？Q1：K是什么？A1：k是聚类算法当中类的个数。Summary：Kmeans是用均值算法把数据分成K个类的算法！Q2：means是什么？A2：means是均值算法。第4页，课件共30页，创作于2023年2月Kmeans算法详解（1）步骤一：取得k个初始初始中心点第5页，课件共30页，创作于2023年2月Kmeans算法详解（2）MinofthreeduetotheEuclidDistance步骤二：把每个点划分进相应的簇第6页，课件共30页，创作于2023年2月Kmeans算法详解（3）MinofthreeduetotheEuclidDistance步骤三：重新计算中心点第7页，课件共30页，创作于2023年2月Kmeans算法详解（4）步骤四：迭代计算中心点第8页，课件共30页，创作于2023年2月Kmeans算法详解（5）步骤五：收敛第9页，课件共30页，创作于2023年2月Kmeans算法流程从数据中随机抽取k个点作为初始聚类的中心，由这个中心代表各个聚类计算数据中所有的点到这k个点的距离，将点归到离其最近的聚类里调整聚类中心，即将聚类的中心移动到聚类的几何中心（即平均值）处，也就是k-means中的mean的含义重复第2步直到聚类的中心不再移动，此时算法收敛最后kmeans算法时间、空间复杂度是：时间复杂度：上限为O(tKmn)，下限为Ω（Kmn）其中，t为迭代次数，K为簇的数目，m为记录数，n为维数空间复杂度：O((m+K)n)，其中，K为簇的数目，m为记录数，n为维数第10页，课件共30页，创作于2023年2月决定性因素Input¢roidsSelectedkMaxIterations&ConvergenceMeassures①数据的采集和抽象②初始的中心选择①最大迭代次数②收敛值①k值的选定①度量距离的手段factors？第11页，课件共30页，创作于2023年2月主要讨论初始中心点输入的数据及K值的选择距离度量我们主要研究的三个方面因素。第12页，课件共30页，创作于2023年2月初始中心点的划分讨论初始中心点意义何在？下面的例子一目了然吧？初始中心点收敛后你懂的…

第13页，课件共30页，创作于2023年2月如何衡量Kmeans算法的精确度？在进一步阐述初始中心点选择之前，我们应该先确定度量kmeans的算法精确度的方法。一种度量聚类效果的标准是：SSE(SumofSquareError，误差平方和)SSE越小表示数据点越接近于它们的质心，聚类效果也就越好。因为对误差取了平方所以更重视那些远离中心的点。一种可以肯定降低SSE的方法是增加簇的个数。但这违背了聚类的目标。因为聚类是在保持目标簇不变的情况下提高聚类的质量。现在思路明了了我们首先以缩小SSE为目标改进算法。第14页，课件共30页，创作于2023年2月改进的算法——二分Kmeans算法为了克服k均值算法收敛于局部的问题，提出了二分k均值算法。该算法首先将所有的点作为一个簇，然后将该簇一分为二。之后选择其中一个簇继续划分，选择哪个簇进行划分取决于对其划分是否可以最大程度降低SSE值。伪代码如下：将所有的点看成一个簇当簇数目小于k时对于每一个簇

计算总误差

在给定的簇上面进行K均值聚类(K=2)

计算将该簇一分为二后的总误差选择使得误差最小的那个簇进行划分操作第15页，课件共30页，创作于2023年2月二分Kmeans算法的效果双击此处添加文字内容既然是改进算法就要体现改进算法的优越性。为此控制变量，在相同的实验环境下，①取相同的k值取。②选取相同的的距离度量标准（欧氏距离）③在相同的数据集下进行测试。第16页，课件共30页，创作于2023年2月一组实验结果一组不好的初始点产生的Kmeans算法结果二分kmeans产生的结果要强调的是尽管只是这一组实验不得以得出二分kmeans的优越性，但是经过大量实验得出的结论却是在大多数情况下二分kmeans确实优于朴素的kmeans算法。第17页，课件共30页，创作于2023年2月全局最小值二分kmeans真的能使SSE达到全局最小值吗？从前面的讲解可以看到二分kmeans算法的思想有点类似于贪心思想。但是我们会发现贪心的过程中有不确定的因素比如：二分一个聚类时选取的两个中间点是随机的，这会对我们的策略造成影响。那么如此一来二分kmeans算法会不会达到全局最优解呢？答案是：会！尽管你可能惊诧于下面的说法，但全局最小值的定义却是：可能的最好结果。第18页，课件共30页，创作于2023年2月K值的选择以及坏点的剔除

讨论k值、剔除坏点的意义何在？下面以一个例子来说明k值的重要性。第19页，课件共30页，创作于2023年2月为什么会出错？上面的例子当中出错的原因很明显。凭直觉我们很容易知道不可能有这样的天气——它的气温是100℃，湿度是1100%。可见坏点对kmeans的影响之大。另一方面，季节有春夏秋冬之分，而我们强行的把它们分为夏冬两个类也是不太合理的。如果分为四个类我们也许可以“中和”掉坏点的影响。究竟哪里错了！！！第20页，课件共30页，创作于2023年2月带canopy预处理的kmeans算法（1）将数据集向量化得到一个list后放入内存，选择两个距离阈值：T1和T2。

（2）从list中任取一点P，用低计算成本方法快速计算点P与所有Canopy之间的距离（如果当前不存在Canopy，则把点P作为一个Canopy），如果点P与某个Canopy距离在T1以内，则将点P加入到这个Canopy；

（3）如果点P曾经与某个Canopy的距离在T2以内，则需要把点P从list中删除，这一步是认为点P此时与这个Canopy已经够近了，因此它不可以再做其它Canopy的中心了；

（4）重复步骤2、3，直到list为空结束

第21页，课件共30页，创作于2023年2月带canopy预处理的kmeans算法的优点第22页，课件共30页，创作于2023年2月带canopy预处理的kmeans算法的新挑战Canopy预处理这么好，我们以后就用它好了！我看不见得，它虽然解决kmeans当中的一些问题，但其自身也引进了新的问题：t1、t2的选取。第23页，课件共30页，创作于2023年2月大数据下kmeans算法的并行策略

VS单挑OR群殴？！第24页，课件共30页，创作于2023年2月大数据下kmeans算法的并行策略

面对海量数据时，传统的聚类算法存在着单位时间内处理量小、面对大量的数据时处理时间较长、难以达到预期效果的缺陷以上算法都是假设数据都是在内存中存储的，随着数据集的增大，基于内存的ＫＭｅａｎｓ就难以适应．ＭａｐＲｅｄｕｃｅ是一个为并行处理大量数据而设计的编程模型。Kmeans算法都是假设数据都是在内存中存储的，随着数据集的增大，基于内存的ＫＭｅａｎｓ就难以适应．ＭａｐＲｅｄｕｃｅ是一个为并行处理大量数据而设计的编程模型，它将工作划分为独立任务组成的集合。第25页，课件共30页，创作于2023年2月Map-reduce的过程简介第26页，课件共30页，创作于2023年2月Map函数设计１Ｍａｐ函数的设计ＭａｐＲｅｄｕｃｅ框架中Ｍａｐ函数的输入为〈ｋｅｙ，ｖａｌｕｅ〉对，其中：ｋｅｙ为输入数据记录的偏移量；ｖａｌｕｅ为当前样本的各维坐标值组成的向量．首先计算该向量到各个聚簇中心点的距离，然后选择最小的距离的聚簇作为该样本所属的簇，之后输出〈ｋｅｙ′，ｖａｌｕｅ′〉，其中ｋｅｙ′是距最近的聚簇的标识符，ｖａｌｕｅ′为表示该样本的向量．第27页，课件共30页，创作于2023年2月Combine函数设计Ｃｏｍｂｉｎｅ函数的设计Ｃｏｍｂｉｎｅ函数的输入为〈ｋｅｙ′，ｖａｌｕｅ′〉对，即Ｍａｐ函数的输出．首先，从ｖａｌｕｅ中解析出各个向量，然后将解析出的向量相加并记录集合中向量的个数．输出是〈ｋｅｙ１′，ｖａｌｕｅ１′〉对，其中：ｋｅｙ１′是聚簇的标识符；ｖａｌｕｅ１′是以上集合中所有的向量相加所得的向量及集合中向量的数目第28页，课件共30页，创作于2023年2月Reduce函数设计Ｒｅｄｕｃｅ函数的输入是〈ｋｅｙ２，ｖａｌｕｅ２〉键值对，其中：ｋｅｙ２为聚簇的标识符；ｖａｌｕｅ２为ｍａｐ节点处理的聚簇中含有的样本的个数及用向量表示的聚簇的中心点ｖｅ