大数据十大经典算法讲解

,#,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,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）,Minofthree,duetotheEuclidDistance,步骤二,：,：把每,个,个点划,分,分进相,应,应的簇,Kmeans算法详,解,解（3）,Minofthree,duetotheEuclidDistance,步骤三,：,：重新,计,计算中,心,心点,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,&,¢roids,Selectedk,MaxIterations&Convergence,Meassures,数据,的,的采集,和,和抽象,初始,的,的中心,选,选择,最大,迭,迭代次,数,数,收敛,值,值,k值的选,定,定,度量,距,距离的,手,手段,factors？,主要讨,论,论,初始中,心,心点,输入的,数,数据及K值的选,择,择,距离度,量,量,我们主,要,要研究,的,的三个,方,方面因,素,素。,初始中,心,心点的,划,划分,讨论初,始,始中心,点,点意义,何,何在？,下,下面的,例,例子一,目,目了然,吧,吧？,初始中,心,心点,收敛后,你,懂,的,如何衡,量,量Kmeans算法的,精,精确度,？,？,在进一,步,步阐述,初,初始中,心,心点选,择,择之前,，,，我们,应,应该先,确,确定度,量,量kmeans的算法,精,精确度,的,的方法,。,。一种,度,度量聚,类,类效果,的,的标准,是,是：SSE,(,(Sum of SquareError，误差,平,平方和),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值的重,要,要性。,有一组关于湿度和温度的数据想把它划分为冬天和夏天两部分。（,k=2,）,气象学家打了个盹不小心把（,100,1000%,）和（,101,1100%,）加入了数据，并不幸选取（,100,1000%,）作为其中一个初始点,于是得到两个很不靠谱的聚类结果。,为什么,会,会出错,？,？,上面的,例,例子当,中,中出错,的,的原因,很,很明显,。,。凭直,觉,觉我们,很,很容易,知,知道不,可,可能有,这,这样的,天,天气它的气,温,温是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,可以自动帮我我们确定,k,值。,有多少,canopy,，,k,值就选取多少。,Canopy,可以帮我们去除“坏点”。,去除离群的,canopy,带canopy预处理,的,的kmeans算法的,新,新挑战,Canopy预处理,这,这么好,，,，我们,以,以后就,用,用它好,了,了！,我看不,见,见得，,它,它虽然,解,解决kmeans当中的,一,一些问,题,题，但,其,其自身,也,也引进,了,了新的,问,问题：t1、t2的选取,。,。,大数据,下,下kmeans算法的,并,并行策,略,略,VS,单挑OR群殴？！,大数据,下,下kmeans算法的,并,并行策,略,略,面对海,量,量数据,时,时，传,统,统的聚,类,类算法,存,存在着,单,单位时,间,间内处,理,理量小,、,、面对,大,大量的,数,数据时,处,处理时,间,间较长,、,、难以,达,达到预,期,期效果,的,的缺陷,以,以上算,法,法都是,假,假设数,据,据都是,在,在内存,中,中存储,的,的，随着数,据,据集的,增,增大，,基,基于内,存,存的,就,难,难以适,应,应,是,一,一个为,并,并行处,理,理大量,数,数据而,设,设计的,编,编程模,型,型。,Kmeans算法都,是,是假设,数,数据都,是,是在内,存,存中存,储,储的，,随,随着数,据,据集的,增,增大，,基,基于内,存,存的,就,难,难以适,应,应,是,一,一个为,并,并行处,理,理大量,数,数据而,设,设计的,编,编程模,型,型，它,将,将工作,划,划分为,独,独立任,务,务组成,的,的集合,。,。,Map,-,-reduce的过程,简,简介,Map函数设,计,计,函数,的,的设计,框,框架中,函,函数,的,的输入,为,为,，,，,对，其,中,中：,为,输,输入数,据,据记录,的,的偏移,量,量；,为当,前,前样本,的,的各维,坐,坐标值,组,组成的,向,向量,首先计,算,算该向,量,量到各,个,个聚簇,中,中心点,的,的距离,，,，然后,选,选择最,小,小的距,离,离的聚,簇,簇作为,该,该样本,所,所属的,簇,簇，之,后,后输出，,，其中,是距最,近,近的聚,簇,簇的标,识,识符，,为表示,该,该样本,的,的向量,Combine函数设,计,计,函数,的,的设计,函数,的,的输入,为,为，,对，即,函,函数的,输,输出,首,首先，,从,从,中,中解析,出,出各个,向,向量，,然,然后将,解