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

（优选）大数据经典算法Kmeans讲解
1页，共28页，星期二。
聚类算法简介
1
2
3
聚类的目标：将一组向量分成若干组行测试。
15页，共28页，星期二。
一组实验结果
一组不好的初始点产生的Kmeans算法结果
二分kmeans产生的结果
要强调的是尽管只是这一组实验不得以得出二分kmeans的优越性，但是经过大量实验得出的结论却是在大多数情况下二分kmeans确实优于朴素的kmeans算法。
16页，共28页，星期二。
全局最小值
二分kmeans真的能使SSE达到全局最小值吗？
从前面的讲解可以看到二分kmeans算法的思想有点类似于贪心思想。但是我们会发现贪心的过程中有不确定的因素比如：二分一个聚类时选取的两个中间点是随机的，这会对我们的策略造成影响。那么如此一来二分kmeans算法会不会达到全局最优解呢？答案是：会！尽管你可能惊诧于下面的说法，但全局最小值的定义却是：可能的最好结果。
17页，共28页，星期二。
K值的选择以及坏点的剔除
讨论k值、剔除坏点的意义何在？下面以一个例子来说明k值的重要性。
18页，共28页，星期二。
为什么会出错？
上面的例子当中出错的原因很明显。凭直觉我们很容易知道不可能有这样的天气——它的气温是100℃，湿度是1100%。可见坏点对kmeans的影响之大。另一方面，季节有春夏秋冬之分，而我们强行的把它们分为夏冬两个类也是不太合理的。如果分为四个类我们也许可以“中和”掉坏点的影响。
究竟哪里错了！！！
19页，共28页，星期二。
带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为空结束
20页，共28页，星期二。
带canopy预处理的kmeans算法的优点
21页，共28页，星期二。
带canopy预处理的kmeans算法的新挑战
Canopy预处理这么好，我们以后就用它好了！
我看不见得，它虽然解决kmeans当中的一些问题，但其自身也引进了新的问题：t1、t2的选取。
22页，共28页，星期二。
大数据下kmeans算法的并行策略
VS
单挑OR群殴？！
23页，共28页，星期二。
大数据下kmeans算法的并行策略
面对海量数据时，传统的聚类算法存在着单位时间内处理量小、面对大量的数据时处理时间较长、难以达到预期效果的缺陷以上算法都是假设数据都是在内存中存储的，随着数据集的增大，基于内存的ＫＭｅａｎｓ就难以适应．ＭａｐＲｅｄｕｃｅ是一个为并行处理大量数据而设计的编程模型。
Kmeans算法都是假设数据都是在内存中存储的，随着数据集的增大，基于内存的ＫＭｅａｎｓ就难以适应．ＭａｐＲｅｄｕｃｅ是一个为并行处理大量数据而设计的编程模型，它将工作划分为独立任务组成的集合。
24页，共28页，星期二。
Map-reduce的过程简介
25页，共28页，星期二。
Map函数设计
１Ｍａｐ函数的设计
ＭａｐＲｅｄｕｃｅ框架中Ｍａｐ 函数的输入为〈ｋｅｙ，ｖａｌｕｅ〉对，其中：ｋｅｙ为输入数据记录的偏移量；ｖａｌｕｅ为当前样本的各维坐标值组成的向量．
首先计算该向量到各个聚簇中心点的距离，然后选择最小的距离的聚簇作为该样本所属的簇，之后输出〈ｋｅｙ′，ｖａｌｕｅ′〉，其中ｋｅｙ′是距最近的聚簇的标识符，ｖａｌｕｅ′为表示该样本的向量．
26页，共28页，星期二。
Combine函数设计
Ｃｏｍｂｉｎｅ函数的设计Ｃｏｍｂｉｎｅ函数的输入为〈ｋｅｙ′，ｖａｌｕｅ′〉对，即Ｍａｐ函数的输出．首先，从ｖａｌｕｅ中解析出各个向量，然后将解析出的向量相加并记录集合中向量的个数．输出是〈ｋｅｙ１′，ｖａｌｕｅ１′〉对，其中：ｋｅｙ１′是聚簇的标识符；ｖａｌｕｅ１′是以上集合中所有的向量相加所得的向量及集合中向量的数目
27页，共28页，星期二。
Reduce函数设计
Ｒｅｄｕｃｅ函数的输入是〈ｋｅｙ２，ｖａｌｕｅ２〉键