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

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值、剔除坏点的意义何在？下面以一个例子来说明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函数设计,函数的输入是，键值对，其中：为聚簇的标识符；为节点处理的聚簇中含有的样本的个数及用向量表示的聚簇的中心点输出为，对，其中：为聚簇的标识符；为新的聚簇中心函数首先从函数的输入中解析出属于同一个聚簇的样本的个数及各个节点传过来的，然后将个数及各个相加，之后将所得到的向量除以个数得到新的中心点坐标。,一个运行结果,一个实验,所有实验都是在实验室搭建的平台 上运行的平台有 台机器，都是四核 处理器，内存版本， 版本每台机器之间用千兆以太网 卡，通过