聚类算法讲解.ppt

主要内容 Kmeans实战 聚类算法简介 Kmeans算法详解 Kmeans算法的缺陷及若干改进 Kmeans的单机实现与分布式实现策略 聚类算法简介 1 2 3 聚类的目标 将一组向量分成若干组 组内数据是相似的 而组间数据是有较明显差异 与分类区别 分类与聚类最大的区别在于分类的目标事先已知 聚类也被称为无监督机器学习 聚类手段 传统聚类算法 划分法 层次方法 基于密度方法 基于网络方法 基于模型方法 什么是Kmeans算法 Q1 K是什么 A1 k是聚类算法当中类的个数 Summary Kmeans是用均值算法把数据分成K个类的算法 Q2 means是什么 A2 means是均值算法 Kmeans算法详解 1 步骤一 取得k个初始初始中心点 Kmeans算法详解 2 MinofthreeduetotheEuclidDistance 步骤二 把每个点划分进相应的簇 Kmeans算法详解 3 MinofthreeduetotheEuclidDistance 步骤三 重新计算中心点 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 Selectedk MaxIterations Convergence Meassures 数据的采集和抽象 初始的中心选择 最大迭代次数 收敛值 k值的选定 度量距离的手段 factors 主要讨论 初始中心点 输入的数据及K值的选择 距离度量 我们主要研究的三个方面因素 初始中心点的划分 讨论初始中心点意义何在 下面的例子一目了然吧 初始中心点 收敛后 你懂的 如何衡量Kmeans算法的精确度 在进一步阐述初始中心点选择之前 我们应该先确定度量kmeans的算法精确度的方法 一种度量聚类效果的标准是 SSE SumofSquareError 误差平方和 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函数设计 函数的输入是 键值对 其中 为聚簇的标识符 为 节点处理的聚簇中含有的样本的个数及用向量表示的聚簇的中心点 输出为 对 其中 为聚簇的标识符 为新的聚簇中心 函数首先从函数的输入中解析出属于同一个聚簇的样本的个数及各个 节点传过来的 然后将个数及各个 相加 之后将所得到的向量除以个数得到新的中心点坐标 一个运行结果 一个实验 所有实验都是在实验室搭建的 平台上运行的 平台有 台机器 都是四核 处理器 内存 版本 版本 每台机器之间用千兆以太网卡 通过交换机连接 实验