文 | 杨翔宇 段伟玮 来源 | IBM Developerworks
算法流程
随机的取 k 个点作为 k 个初始质心;
计算其他点到这个 k 个质心的距离;
如果某个点 p 离第 n 个质心的距离更近,则该点属于 cluster n,并对其打标签,标注 point p.label=n,其中 n<>
计算同一 cluster 中,也就是相同 label 的点向量的平均值,作为新的质心;
迭代至所有质心都不变化为止,即算法结束。
K 值估计
算法实现
测试数据
层次聚类简介
算法流程
每次选最近的两个簇合并,我们将这两个合并后的簇称之为合并簇。
若采用 MAX 准则,选择其他簇与合并簇中离得最远的两个点之间的距离作为簇之间的邻近度。若采用 MIN 准则,取其他簇与合并簇中离得最近的两个点之间的距离作为簇之间的邻近度。若组平均准则,取其他簇与合并簇所有点之间距离的平均值作为簇之间的邻近度。
重复步骤 1 和步骤 2,合并至只剩下一个簇。
算法过程举例
算法实现
测试数据
设定扫描半径 Eps, 并规定扫描半径内的密度值。若当前点的半径范围内密度大于等于设定密度值,则设置当前点为核心点;若某点刚好在某核心点的半径边缘上,则设定此点为边界点;若某点既不是核心点又不是边界点,则此点为噪声点。
删除噪声点。
将距离在扫描半径内的所有核心点赋予边进行连通。
每组连通的核心点标记为一个簇。
将所有边界点指定到与之对应的核心点的簇总。
算法过程举例
P0 点为边界点,因为在以其为中心的扫描半径内只有两个点 P0 和 P1;
P1 点为核心点,因为在以其为中心的扫描半径内有四个点 P0,P1,P2,P4 ;
P8 为噪声点,因为其既非核心点,也非边界点;
其他点依次类推。
算法实现
测试数据
BIRCH 算法
聚类特征 CF=(N,LS,SS),其中 N 代表簇中点的个数,LS 代表簇中代表簇中各点线性和,SS 代表簇中各点的平方和距离。聚类特征被应用于 CF 树中,CF 树是一种高度平衡树,它具有两个参数:平衡因子 B 和簇半径阈值 T。其中平衡因子 B 代表每一个非叶子节点最多能够引入 B 个实体条目。
叶子节点最多只能包含 L 个实体条目,并且它们具有前向后向指针,这样可以彼此链接起来。
树的大小取决于簇半径阈值 T 的大小。
从根节点开始,递归查找与要插入的数据点距离最近的叶子节点中的实体条目,递归过程选择最短路径。
比较上述计算出的数据点与叶子节点中实体条目间的最近距离是否小叶簇半径阈值 T,小于则吸收该数据点。否则执行下一步。
判断当前条目所在的叶节点个数是否小于 L,若小于则直接将该数据点插入当前点。否则分裂叶子节点,分裂过程是将叶子节点中距离最远的两个实体条目变为新的两个叶子节点,其他条目则根据距离最近原则重新分配到这两个新的叶子节点中。删除原来的叶子节点并更新 CF 树。
若不能将所有数据点加入 CF 树中,则考虑增加簇半径阈值 T,并重新更新 CF 树直至所有的数据点被加入 CF 树为止。
CURE 算法
在数据集中选择样本数据。
将上述样本数据划分为 P 个同样大小的划分。
将每个划分中的点聚成 m/pq 个簇,共得到 m/q 个簇。过程中需删除噪声点。
对上述 m/q 个簇进行聚类直至剩下 k 个簇。
继续删除离群点。
将剩下的点指派到最近的簇完成聚类过程。
参考资料 《数据挖掘导论》 《大数据-互联网大规模数据挖掘与分布式处理》
原文链接:http://www.ibm.com/developerworks/cn/analytics/library/ba-1607-clustering-algorithm/index.html
联系客服