(完整版)聚类算法总结.doc

1.聚类定义 “聚类是把相似的对象通过静态分类的方法分成不同的组别或者更多的子集（ subset）,这样让在同一个子集中的成员对象都有一些相似的属性” —— wikipedia “聚类分析指将物理或抽象对象的集合分组成为由类似的对象组 成的多个类的分析过程。 它是一种重要的人类行为。 聚类是将数据分类到不同的类或者簇这样的一个过程， 所以同一个簇中的对 象有很大的相似性，而不同簇间的对象有很大的相异性。 ” —— 百度百科 说白了，聚类（ clustering）是完全可以按字面意思来理解的 —— 将相同、相似、相近、相关的对象实例聚成一类的过程。简单理 解，如果一个数据集合包含 N 个实例，根据某种准则可以将这 N 个实例划分为 m 个类别，每个类别中的实例都是相关的，而不同类别之间是区别的也就是不相关的，这个过程就叫聚类了。 2.聚类过程 : 数据准备 :包括特征标准化和降维 . 特征选择 :从最初的特征中选择最有效的特征 ,并将其存储于向量中 . 特征提取 :通过对所选择的特征进行转换形成新的突出特征. 聚类 (或分组 ):首先选择合适特征类型的某种距离函数 (或构造新的距离函数 )进行接近程度的度量 ;而后执行聚类或分组 . 聚类结果评估 :是指对聚类结果进行评估 .评估主要有 3 种 :外 部有效性评估、内部有效性评估和相关性测试评估. 聚类算法的类别 没有任何一种聚类技术 (聚类算法 )可以普遍适用于揭示各种多维 数据集所呈现出来的多种多样的结构， 根据数据在聚类中的积聚 规则以及应用这些规则的方法 ,有多种聚类算法 .聚类算法有多种 分类方法将聚类算法大致分成层次化聚类算法、划分式聚类算 法、基于密度和网格的聚类算法和其他聚类算法  ,如图  1  所示 的  4  个类别  . 3.聚类算法 基于层次聚类算法： 采用抽样技术先对数据集 D随机抽取样本，再 CURE： 采用分区技术对样本进行分区， 然后对每个分 区局部聚类，最后对局部聚类进行全局聚类 ROCK： 也采用了随机抽样技术， 该算法在计算两个对 象的相似度时，同时考虑了周围对象的影响 首先由数据集构造成一个 K- 最近邻图 Gk , 再 CHEMALOEN（变色龙 通过一个图的划分算法将图 Gk 划分成大量 的子图 , 每个子图代表一个初始子簇 , 最后用 算法）： 一个凝聚的层次聚类算法反复合并子簇， 找到 真正的结果簇 SBAC算法则在计算对象间相似度时，考虑了 SBAC： 属性特征对于体现对象本质的重要程度， 对于 更能体现对象本质的属性赋予较高的权值 BIRCH算法利用树结构对数据集进行处理， 叶 结点存储一个聚类， 用中心和半径表示， 顺序 BIRCH： 处理每一个对象， 并把它划分到距离最近的结 点，该算法也可以作为其他聚类算法的预处理 过程 BUBBLE： BUBBLE算法则把 BIRCH算法的中心和半径概 念推广到普通的距离空间 BUBBLE-FM： BUBBLE-FM算法通过减少距离的计算次数， 提 基于划分聚类算法（ partition clustering) 是一种典型的划分聚类算法，它用一个聚类的 中心来代表一个簇，即在迭代过程中选择的聚 k-means： 点不一定是聚类中的一个点，该算法只能处理数值型数据 K-Means 算法的扩展，采用简单匹配方法来度量 k-modes： 分类型数据的相似度 k-medoids CLARA： CLARANS： k-prototypes 高了 BUBBLE算法的效率 结合了 K-Means 和 K-Modes 两种算法，能够处 ： 理混合型数据 在迭代过程中选择簇中的某点作为聚点， PAM ： 是典型的 k-medoids 算法 CLARA算法在 PAM的基础上采用了抽样技术， 能 够处理大规模数据 CLARANS算法融合了 PAM和 CLARA两者的优点， 是第一个用于空间数据库的聚类算法 采用了空间索引技术提高了 CLARANS算法的效 Focused CLARAN： 率 模糊集合理论引入聚类分析中并提出了 PCM模 PCM： 糊聚类算法 基于密度聚类算法： DBSCAN算法是一种典型的基于密度的聚类算法， 该算法采用空间索引技术来有哪些信誉好的足球投注网站对象的邻域， 引入 DBSCAN： 了“核心对象”和“密度可达”等概念， 从核心对象出发，把所有密度可达的对象组成一个簇 算法通过泛化 DBSCAN算法中邻域的概念，以适应 GDBSCAN： 空间对象的特点 DBLASD： OPTICS 算法结合了聚类的自动性和交互性，先生 OPTICS： 成聚类的次序，可以对不同的聚类设置不同的参 数，来得到用户满意的结果 FDC算法通过构造 k-d tree 把整个数据空间划分 FDC：