大数据经典算法Kmeans讲解优品文档.ppt

,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,大数据经典算法,Kmeans,讲解,主要内容：,Kmeans,实战,聚类算法简介,Kmeans,算法详解,Kmeans,算法的缺陷及若干改进,Kmeans,的单机实现与分布式实现策略,Kmeans的单机实现与分布式实现策略,因为聚类是在保持目标簇不变的情况下提高聚类的质量。,Min of three,如果分为四个类我们也许可以“中和”掉坏点的影响。,为了克服k均值算法收敛于局部的问题，提出了二分k均值算法。,步骤一：取得k个初始初始中心点,选取相同的的距离度量标准（欧氏距离）,Map-reduce的过程简介,如何衡量Kmeans算法的精确度？,什么是Kmeans算法？,凭直觉我们很容易知道不可能有这样的天气它的气温是100，湿度是1100%。,Min of three,聚类算法简介,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,算法。,计算将该簇一分为二后的总误差,在给定的簇上面进行K均值聚类(K=2),因为聚类是在保持目标簇不变的情况下提高聚类的质量。,重复第2步直到聚类的中心不再移动，此时算法收敛,首先计算该向量到各个聚簇中心点的距离，然后选择最小的距离的聚簇作为该样本所属的簇，之后输出，其中是距最近的聚簇的标识符，为表示该样本的向量,due to the EuclidDistance,与分类区别：分类与聚类最大的区别在于分类的目标事先已知，聚类也被称为无监督机器学习,输入的数据及K值的选择,Kmeans算法详解（2）,Map-reduce的过程简介,函数的设计函数的输入为，对，即函数的输出首先，从中解析出各个向量，然后将解析出的向量相加并记录集合中向量的个数输出是，对，其中：是聚簇的标识符；,步骤四：迭代计算中心点,要强调的是尽管只是这一组实验不得以得出二分kmeans的优越性，但是经过大量实验得出的结论却是在大多数情况下二分kmeans确实优于朴素的kmeans算法。,聚类手段：传统聚类算法 划分法 层次方法 基于密度方法 基于网络方法 基于模型方法,是以上集合中所有的向量相加所得的向量及集合中向量的数目,SSE越小表示数据点越接近于它们的质心，聚类效果也就越好。,什么是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,函数设计,函数的输入是,，,键值对，其中：为聚簇的标识符；为节点处理的聚簇中含有的样本的个数及用向量表示的聚簇的中心点输出为,，,对，其中：,为聚簇的标识符；,为新的聚簇中心函数首先从函数的输入中解析出属于同一个聚簇的样本的个数及各个节点传过来的，然后将个数及各个相加，之后将所得到的向量除以个数得到新的中心点坐标。,一个运行结果,感谢观看,