大数据十大经典算法讲解

1、The algorithm of Kmeans小组成员：徐佳、张俊飞、刘志伟、孔祥玉主要内容容：Kmeans实战聚类算法法简介Kmeans算法详解解Kmeans算法的缺缺陷及若若干改进进Kmeans的单机实实现与分分布式实实现策略略 聚类算法法简介123聚类的目目标：将一组向向量分成成若干组组，组内内数据是是相似的的，而组组间数据据是有较较明显差差异。与分类区区别：分类与聚聚类最大大的区别别在于分分类的目目标事先先已知，聚类也也被称为为无监督督机器学学习聚类手段段：传统统聚类算算法划分法法层次次方法基基于密度度方法基于网网络方法法基于模模型方法法什么是Kmeans算法？Q1：K是什么？A1：k

2、是聚类算算法当中中类的个个数。Summary：Kmeans是用均值值算法把把数据分分成K个类的算算法！Q2：means是什么？A2：means是均值算算法。Kmeans算法详解解（1）步骤一：取得k个初始初初始中心心点Kmeans算法详解解（2）MinofthreeduetotheEuclidDistance步骤二：把每个个点划分分进相应应的簇Kmeans算法详解解（3）MinofthreeduetotheEuclidDistance步骤三：重新计计算中心心点Kmeans算法详解解（4）步骤四：迭代计计算中心心点Kmeans算法详解解（5）步骤五：收敛Kmeans算法流程程从数据中中随机抽抽取

3、k个点作为为初始聚聚类的中中心，由由这个中中心代表表各个聚聚类计算数据据中所有有的点到到这k个点的距距离，将将点归到到离其最最近的聚聚类里调整聚类类中心，即将聚聚类的中中心移动动到聚类类的几何何中心（即平均均值）处处，也就就是k-means中的mean的含义重复第2步直到聚聚类的中中心不再再移动，此时算算法收敛敛最后kmeans算法时间间、空间间复杂度度是：时间复杂杂度：上上限为O(tKmn)，下限为为（Kmn）其中，t为迭代次次数，K为簇的数数目，m为记录数数，n为维数空间复杂杂度：O(m+K)n)，其中，K为簇的数数目，m为记录数数，n为维数决定性因因素Input¢roidsSel

4、ectedkMaxIterations &ConvergenceMeassures数据的的采集和和抽象初始的的中心选选择最大迭迭代次数数收敛值值k值的选定定度量距距离的手手段factors？主要讨论论初始中心心点输入的数数据及K值的选择择距离度量量我们主要要研究的的三个方方面因素素。初始中心心点的划划分讨论初始始中心点点意义何何在？下下面的例例子一目目了然吧吧？初始中心心点收敛后你懂的 如何衡量量Kmeans算法的精精确度？在进一步步阐述初初始中心心点选择择之前，我们应应该先确确定度量量kmeans的算法精精确度的的方法。一种度度量聚类类效果的的标准是是：SSE(Sum of SquareEr

5、ror，误差平平方和)SSE越小表示示数据点点越接近近于它们们的质心心，聚类类效果也也就越好好。因为为对误差差取了平平方所以以更重视视那些远远离中心心的点。一种可以以肯定降降低SSE的方法是是增加簇簇的个数数。但这这违背了了聚类的的目标。因为聚聚类是在在保持目目标簇不不变的情情况下提提高聚类类的质量量。现在思路路明了了了我们首首先以缩缩小SSE为目标改改进算法法。改进的算算法二分Kmeans算法为了克服服k均值算法法收敛于于局部的的问题，提出了了二分k均值算法法。该算算法首先先将所有有的点作作为一个个簇，然然后将该该簇一分分为二。之后选选择其中中一个簇簇继续划划分，选选择哪个个簇进行行划分取取

6、决于对对其划分分是否可可以最大大程度降降低SSE值。伪代码如如下：将所有的的点看成成一个簇簇当簇数目目小于k时对于每一一个簇计算总误误差在给定的的簇上面面进行K均值聚类类(K=2)计算将该该簇一分分为二后后的总误误差选择使得得误差最最小的那那个簇进进行划分分操作二分Kmeans算法的效效果双击此处处添加文文字内容容既然是改改进算法法就要体体现改进进算法的的优越性性。为此此控制变变量，在在相同的的实验环环境下，取相相同的k值取。选取相相同的的的距离度度量标准准（欧氏氏距离）在相同同的数据据集下进进行测试试。一组实验验结果一组不好好的初始始点产生生的Kmeans算法结果果二分kmeans产生的结结

7、果要强调的的是尽管管只是这这一组实实验不得得以得出出二分kmeans的优越性性，但是经过大量量实验得得出的结结论却是是在大多多数情况况下二分分kmeans确实优于于朴素的的kmeans算法。全局最小小值二分kmeans真的能使使SSE达到全局局最小值值吗？从前面的的讲解可可以看到到二分kmeans算法的思思想有点点类似于于贪心思思想。但但是我们们会发现现贪心的的过程中中有不确确定的因因素比如如：二分分一个聚聚类时选选取的两两个中间间点是随随机的，这会对对我们的的策略造造成影响响。那么么如此一一来二分分kmeans算法会不不会达到到全局最最优解呢呢？答案案是：会会！尽管管你可能能惊诧于于下面的的

8、说法，但全局局最小值值的定义义却是：可能的最好结结果。K值的选择择以及坏坏点的剔剔除 讨论k值、剔除除坏点的的意义何何在？下下面以一一个例子子来说明明k值的重要要性。有一组关于湿度和温度的数据想把它划分为冬天和夏天两部分。（k=2）气象学家打了个盹不小心把（100,1000%）和（101,1100%）加入了数据，并不幸选取（100,1000%）作为其中一个初始点于是得到两个很不靠谱的聚类结果。为什么会会出错？上面的例例子当中中出错的的原因很很明显。凭直觉觉我们很很容易知知道不可可能有这这样的天天气它的气温温是100，湿度度是1100%。可见坏坏点对kmeans的影响之之大。另另一方面面，季节节

9、有春夏夏秋冬之之分，而而我们强强行的把把它们分分为夏冬冬两个类类也是不不太合理理的。如如果分为为四个类类我们也也许可以以“中和和”掉坏坏点的影影响。究竟哪里里错了！带canopy预处理的的kmeans算法（1）将数据据集向量量化得到到一个list后放入内内存，选选择两个个距离阈阈值：T1和T2。（2）从list中任取一一点P，用低计计算成本本方法快快速计算算点P与所有Canopy之间的距距离（如如果当前前不存在在Canopy，则把点点P作为一个个Canopy），如果果点P与某个Canopy距离在T1以内，则则将点P加入到这这个Canopy；（3）如果点点P曾经与某某个Canopy的距离在在T2

10、以内，则则需要把把点P从list中删除，这一步步是认为为点P此时与这这个Canopy已经够近近了，因因此它不不可以再再做其它它Canopy的中心了了；（4）重复步步骤2、3，直到list为空结束束带canopy预处理的的kmeans算法的优优点canopy可以自动帮我我们确定k值。有多少canopy，k值就选取多少。Canopy可以帮我们去除“坏点”。去除离群的canopy带canopy预处理的的kmeans算法的新新挑战Canopy预处理这这么好，我们以以后就用用它好了了！我看不见见得，它它虽然解解决kmeans当中的一一些问题题，但其其自身也也引进了了新的问问题：t1、t2的选取。大数据下

11、下kmeans算法的并并行策略略VS单挑OR群殴？！大数据下下kmeans算法的并并行策略略面对海量量数据时时，传统统的聚类类算法存存在着单单位时间间内处理理量小、面对大大量的数数据时处处理时间间较长、难以达达到预期期效果的的缺陷以以上算法法都是假假设数据据都是在在内存中中存储的的，随着数据据集的增增大，基基于内存存的就难难以适应应是一一个为并并行处理理大量数数据而设设计的编编程模型型。Kmeans算法都是是假设数数据都是是在内存存中存储储的，随随着数据据集的增增大，基基于内存存的就难难以适应应是一一个为并并行处理理大量数数据而设设计的编编程模型型，它将将工作划划分为独独立任务务组成的的集合。

12、Map-reduce的过程简简介Map函数设计计函数的的设计框框架中函函数的的输入为为，对，其中中：为输输入数据据记录的的偏移量量；为当前前样本的的各维坐坐标值组组成的向向量首先计算算该向量量到各个个聚簇中中心点的的距离，然后选选择最小小的距离离的聚簇簇作为该该样本所所属的簇簇，之后后输出，其中是距最近近的聚簇簇的标识识符，为表示该该样本的的向量Combine函数设计计函数的的设计函数的的输入为为，对，即函函数的输输出首首先，从从中中解析出出各个向向量，然然后将解解析出的的向量相相加并记记录集合合中向量量的个数数输出出是，对，其中中：是聚簇的的标识符符；是以上集集合中所所有的向向量相加加所得的的向量及及集合中中向量的的数目Reduce函数设计计函函数的输输入是，键值对，其中：为聚聚簇的标标识符；为节点点处理的的聚簇中中含有的的样本的的个数及及用向量量表示的的聚簇的的中心点点输输出为，对，其中中：为聚簇的的标识符符；为新的聚聚簇中心心函数数首先从从函数的的输入中中解析出出属于同同一个聚聚簇的样样本的个个数及各各个节点点传过来来的，然后将将个数及及各个相加，之后将将所得到到的向量量除以个个数得到到新的中中心点坐坐标。一个运行行结果一个实验验所有实验验都是在在实验室室搭建的的平台上运行的的平台台有台台机器器，都是是四核处处理器，内存版本，版本每台机机器之间间用