大数据十大经典算法讲解13772.pptx

The algorithm of Kmeans小组成员：徐佳、张俊飞、刘志伟、孔祥玉主要内容：主要内容：Kmeans实战实战聚类算法简介聚类算法简介Kmeans算法详解算法详解Kmeans算法的缺陷及若干改进算法的缺陷及若干改进Kmeans的单机实现与分布式实现策略的单机实现与分布式实现策略 聚聚类类算算法法简简介介123聚类的目标：聚类的目标：将一组向量分成若干组，组内数据是相似的，将一组向量分成若干组，组内数据是相似的，而组间数据是有较明显差异。而组间数据是有较明显差异。与分类区别：与分类区别：分类与聚类最大的区别在于分类的目标事先已分类与聚类最大的区别在于分类的目标事先已知，聚类也被称为无监督机器学习知，聚类也被称为无监督机器学习聚类手段：传统聚类算法聚类手段：传统聚类算法划分法划分法层次方法层次方法基于密度基于密度方法方法基于网络方法基于网络方法基于模型方法基于模型方法什什么么是是Kmeans算算法法？Q1Q1：K K是什么？是什么？是什么？是什么？A1A1：k k是聚类算法当中类的个数。是聚类算法当中类的个数。是聚类算法当中类的个数。是聚类算法当中类的个数。Summary：Kmeans是用均值算法把数是用均值算法把数据分成据分成K个类的算法！个类的算法！Q2 Q2：meansmeans是什么？是什么？是什么？是什么？A2A2：meansmeans是均值算法。是均值算法。是均值算法。是均值算法。Kmeans算法详解（算法详解（1）步骤一：取得步骤一：取得k个初始初始中心点个初始初始中心点Kmeans算法详解（算法详解（2）MinofthreeduetotheEuclidDistance步骤二：把每个点划分进相应的簇步骤二：把每个点划分进相应的簇Kmeans算法详解（算法详解（3）MinofthreeduetotheEuclidDistance步骤三：重新计算中心点步骤三：重新计算中心点Kmeans算法详解（算法详解（4）步骤四：迭代计算中心点步骤四：迭代计算中心点Kmeans算法详解（算法详解（5）步骤五：收敛步骤五：收敛Kmeans算算法法流流程程1.从数据中随机抽取从数据中随机抽取k个点作为初始聚类的个点作为初始聚类的中心，由这个中心代表各个聚类中心，由这个中心代表各个聚类2.计算数据中所有的点到这计算数据中所有的点到这k个点的距离，个点的距离，将点归到离其最近的聚类里将点归到离其最近的聚类里3.调整聚类中心，即将聚类的中心移动到调整聚类中心，即将聚类的中心移动到聚类的几何中心（即平均值）处，也就是聚类的几何中心（即平均值）处，也就是k-means中的中的mean的含义的含义4.重复第重复第2步直到聚类的中心不再移动，此步直到聚类的中心不再移动，此时算法收敛时算法收敛最后最后kmeans算法时间、空间复杂度是：算法时间、空间复杂度是：1.时间复杂度：上限为时间复杂度：上限为O(tKmn)，下限为，下限为（Kmn）其中，）其中，t为迭代次数，为迭代次数，K为簇的为簇的数目，数目，m为记录数，为记录数，n为维数为维数2.空间复杂度：空间复杂度：O(m+K)n)，其中，其中，K为为簇的数目，簇的数目，m为记录数，为记录数，n为维数为维数决决定定性性因因素素Input&centroidsInput&centroidsSelectedkSelectedkMaxIterations&ConvergenceMaxIterations&ConvergenceMeassuresMeassures数据的采集和抽象初始的中心选择最大迭代次数收敛值 k值的选定 度量距离的手段factorsfactors？主主要要讨讨论论初始中初始中心点心点输入的数输入的数据及据及K值值的选择的选择距离度距离度量量我们主要研究的三个方面因素。我们主要研究的三个方面因素。初初始始中中心心点点的的划划分分讨论初始中心点意义何在？下面的例子一目了然吧？讨论初始中心点意义何在？下面的例子一目了然吧？初始中心点初始中心点收敛后收敛后你你懂懂的的如如何何衡衡量量Kmeans算算法法的的精精确确度度？在进一步阐述初始中心点选择在进一步阐述初始中心点选择之前，我们应该先确定度量之前，我们应该先确定度量kmeans的算法精确度的方法。的算法精确度的方法。一种度量聚类效果的标准是：一种度量聚类效果的标准是：SSE(SumofSquareError，误差平方和误差平方和)SSE越小表示数据点越接近于越小表示数据点越接近于它们的质心，聚类效果也就越它们的质心，聚类效果也就越好。因为对误差取了平方所以好。因为对误差取了平方所以更重视那些远离中心的点。更重视那些远离中心的点。一种可以肯定降低一种可以肯定降低SSE的方法的方法是增加簇的个数。但这违背了是增加簇的个数。但这违背了聚类的目标。因为聚类是在保聚类的目标。因为聚类是在保持目标簇不变的情况下提高聚持目标簇不变的情况下提高聚类的质量。类的质量。现在思路明了了我们首先以缩现在思路明了了我们首先以缩小小SSE为目标改进算法。为目标改进算法。改进的算法改进的算法二分二分Kmeans算法算法为了克服为了克服k均值算法收敛于局部的问题，提出了二分均值算法收敛于局部的问题，提出了二分k均值算法。该算法首先将所有的点作为一个簇，然后均值算法。该算法首先将所有的点作为一个簇，然后将该簇一分为二。之后选择其中一个簇继续划分，选将该簇一分为二。之后选择其中一个簇继续划分，选择哪个簇进行划分取决于对其划分是否可以最大程度择哪个簇进行划分取决于对其划分是否可以最大程度降低降低SSE值。值。伪代码如下：伪代码如下：将所有的点看成一个簇将所有的点看成一个簇当簇数目小于当簇数目小于k时时对于每一个簇对于每一个簇计算总误差计算总误差在给定的簇上面进行在给定的簇上面进行K均值聚类均值聚类(K=2)计算将该簇一分为二后的总误差计算将该簇一分为二后的总误差选择使得误差最小的那个簇进行划分操作选择使得误差最小的那个簇进行划分操作二二分分Kmeans算算法法的的效效果果既然是改进算法就要体现改既然是改进算法就要体现改进算法的优越性。为此控制进算法的优越性。为此控制变量，在相同的实验环境下，变量，在相同的实验环境下，取相同的取相同的k值取。值取。选取相同的的距离度量标选取相同的的距离度量标准（欧氏距离）准（欧氏距离）在相同的数据集下进行测在相同的数据集下进行测试。试。一一组组实实验验结结果果一组不好的初始点产生的一组不好的初始点产生的Kmeans算法结果算法结果二分二分kmeans产生的结果产生的结果要强调的是尽管只是这一组实验不得以得出二分要强调的是尽管只是这一组实验不得以得出二分kmeans的的优越性，优越性，但是但是经过大量实验得出的结论却是在大多数情况下经过大量实验得出的结论却是在大多数情况下二分二分kmeans确实优于朴素的确实优于朴素的kmeans算法。算法。全局最小值全局最小值二分二分kmeans真真的能使的能使SSE达到达到全局最小值吗？全局最小值吗？从前面的讲解可以看到二分从前面的讲解可以看到二分kmeans算法的思想有点类算法的思想有点类似于贪心思想。但是我们会似于贪心思想。但是我们会发现贪心的过程中有不确定发现贪心的过程中有不确定的因素比如：二分一个聚类的因素比如：二分一个聚类时选取的两个中间点是随机时选取的两个中间点是随机的，这会对我们的策略造成的，这会对我们的策略造成影响。那么如此一来二分影响。那么如此一来二分kmeans算法会不会达到全算法会不会达到全局最优解呢？答案是：会！局最优解呢？答案是：会！尽管你可能惊诧于下面的说尽管你可能惊诧于下面的说法，但全局最小值的定义却法，但全局最小值的定义却是：是：可能可能的最好结果。的最好结果。K值值的的选选择择以以及及坏坏点点的的剔剔除除讨论讨论k值、剔除坏点的意义何在？下面以一个例值、剔除坏点的意义何在？下面以一个例子来说明子来说明k值的重要性。值的重要性。为什么会出错？为什么会出错？上面的例子当中出错的原因上面的例子当中出错的原因很明显。凭直觉我们很容易很明显。凭直觉我们很容易知道不可能有这样的天气知道不可能有这样的天气它的气温是它的气温是100，湿度是，湿度是1100%。可见坏点对。可见坏点对kmeans的影响之大。另一的影响之大。另一方面，季节有春夏秋冬之分，方面，季节有春夏秋冬之分，而我们强行的把它们分为夏而我们强行的把它们分为夏冬两个类也是不太合理的。冬两个类也是不太合理的。如果分为四个类我们也许可如果分为四个类我们也许可以以“中和中和”掉坏点的影响。掉坏点的影响。究竟哪里错了！究竟哪里错了！带带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为空结为空结束束带带canopy预处理的预处理的kmeans算法的优点算法的优点带带canopy预处理的预处理的kmeans算法的新挑战算法的新挑战Canopy预处理这么好，预处理这么好，我们以后就用它好了！我们以后就用它好了！我看不见得，它虽然解决我看不见得，它虽然解决kmeans当中的一些问题，当中的一些问题，但其自身也引进了新的问题：但其自身也引进了新的问题：t1、t2的选取。的选取。大数据下大数据下kmeans算法的并算法的并行策略行策略VS单挑单挑OR群殴群殴？！？！大数据下大数据下kmeans算法的并算法的并行策略行策略面对海量数据时，传统的聚类算法存在着单位时面对海量数据时，传统的聚类算法存在着单位时间内处理量小、面对大量的数据时处理时间较长、间内处理量小、面对大量的数据时处理时间较长、难以达到预期效果的缺陷以上算法都是假设数据都难以达到预期效果的缺陷以上算法都是假设数据都是在内存中存储的，是在内存中存储的，随着数据集的增大，基于内存随着数据集的增大，基于内存的就难以适应的就难以适应是一个为并行处理大量数据而设计的编程模型。是一个为并行处理大量数据而设计的编程模型。Kmeans算法都是假设数据都是在内存中存储的，算法都是假设数据都是在内存中存储的，随着数据集的增大，基于内存的就难随着数据集的增大，基于内存的就难以适应是一个为并行处理大以适应是一个为并行处理大量数据而设计的编程模型，它将工作划分为独立任量数据而设计的编程模型，它将工作划分为独立任务组成的集合。务组成的集合。Map-reduce的过程简介的过程简介Map函数设计函数设计函数的设计函数的设计框框架架中中函函数数的的输输入入为为，对对，其其中中：为为输输入入数数据据记记录录的的偏偏移移量量；为为当当前前样样本本的的各各维维坐坐标标值值组组成成的的向量向量首首先先计计算算该该向向量量到到各各个个聚聚簇簇中中心心点点的的距距离离，然然后后选选择择最最小小的的距距离离的的聚聚簇簇作作为为该该样样本本所所属属的的簇簇，之之后后输输出出，其其中中是是距距最最近近的的聚聚簇簇的的标标识识符符，为为表表示示该该样样本本的的向向量量Combine函数设计函数设计函数的设计函数的设计函数的输入为函数的输入为，对，即函数的输出首先，对，即函数的输出首先，从中解析出各个向量，然后从中解析出各个向量，然后将解析出的向量相加并记录集合中向量将解析出的向量相加并记录集合中向量的个数输出是的个数输出是，对，其中：对，其中：是聚簇的标是聚簇的标识符；识符；是以上集合中所有是以上集合中所有的向量相加所得的向量及集合中向量的的向量相加所得的向量及集合中向量的数目数目Reduce函数设计函数设计函数的输入是函数的输入是，键值对，其中：为聚簇的键值对，其中：为聚簇的标识符；为节点处理的聚标识符；为节点处理的聚簇中含有的样本的个数及用向量表示的聚簇的簇中含有的样本的个数及用向量表示的聚簇的中心点输出为中心点输出为，对，其中：对，其中：为为聚簇的标识符；聚簇的标识符；为新的聚簇中心为新的聚簇中心函数首先从函数的输入中解析出函数首先从函数的输入中解析出属于同一个聚簇的样本的个数及各个节属于同一个聚簇的样本的个数及各个节点传过来的，然后将个点传过来的，然后将个数及各个相加，之后将数及各个相加，之后将所得到的向量除以个数得到新的中心点坐标。所得到的向量除以个数得到新的中心点坐标。一一个个运运行行结结果果一一个个实实验验所有实验都是在实验室搭建的平台所有实验都是在实验室搭建的平台上上运运行行的的平平台台有有台台机机器器，都都是是四四核核处处理理器器，内内存存版本，版本，版版本本每每台台机机器器之之间间用用千千兆兆以太网以太网卡，通过交换机连接实验所用的数据是人工数卡，通过交换机连接实验所用的数据是人工数据据，维维度度是是维维为为了了测测试试算算法法的的性性能能，实实验验中中构构造了分别含有造了分别含有104，105,106，2*106条条记记录录的的数数据据来来进进行行测测试试由由于于算算法法中中有有随机初始化中心点的操作，因此对每一组实验重随机初始化中心点的操作，因此对每一组实验重复执行次，取其平均执行时间作为最终实验结复执行次，取其平均执行时间作为最终实验结果果算算法法改改进进后后的的实实效效可以看出：基于可以看出：基于的算法的算法的运行效率要的运行效率要远远高于高于传统的的算法算法Q&A谢谢谢谢！