数据挖掘第10章--聚类分析：基本概念和方法

1、数据挖掘与商务智能范勤勤范勤勤物流研究中心物流研究中心第十章 聚类分析1聚类分析2划分方法3层次方法4基于密度的方法1 聚类分析28聚类分析：基本概念簇：每个子集是一个簇 簇中的对象彼此相似 与其他簇中的对象不相似典型应用 作为一个独立的工具观察数据分布的情况，观察每个簇的特点，集中对特定的某些簇做进一步分析 作为其他算法（如分类等）的一个预处理步骤，这些算法再在生成的簇上进行处理聚类分析 是一个把数据对象划分成子集的过程，由聚类分析产生的簇的集合称作一个聚类 聚类被称为无监督学习，因为没有提供类标号信息428聚类分析：应用示例Marketing 在商业上，聚类能帮助市场分析人员从客户基本库中

2、发现不同的客户群Biology 在生物学上，聚类能用于推导植物和动物的分类，对基因进行分类，获得对种群中固有结构的认识Land use 在地球观测数据库中相似地区的确定528数据挖掘对聚类的典型要求 可伸缩性：在大数据集合样本上进行聚类会导致有偏的结果 处理不同属性类型的能力：如图、序列、图像等 发现任意形状的簇：许多聚类算法基于欧式或曼哈顿距离，球状簇 对于确定输入参数的领域知识的要求：对参数设定十分敏感 处理噪声数据的能力：对数据敏感，可能导致低质量的聚类结果 增量聚类（新数据）和对输入次序不敏感：不能将新数据合并到已有的聚类结构中，对于输入数据的顺序是敏感的 聚类高维数据的能力：高维数据

3、有可能是非常稀疏和高度倾斜 基于约束的聚类：现实中有很多约束条件 可解释性和可用性628可以用于比较聚类方法的诸方面划分准则 分层或不分层相似性度量 虽然基于距离的方法常常可以利用最优化技术，但是基于密度或基于连通性的方法常常可以发现任意形状的簇簇的分离性 作为簇的主题可能不是互斥的聚类空间 子空间聚类发现揭示对象相似性的簇和子空间728基本聚类方法概述划分方法(Partitioning approach) 基本思想：给定一个n个样本的数据库，划分方法将数据划分为k个划分（k=n），每个划分表示一个簇，同时满足：（1）每个簇至少包含一个样本；（2）每个样本必须属于且仅属于一个层次方法(Hier

4、archical approach) 创建给定数据对象集的层次分解8基于密度的方法 对给定簇中的每个数据点，在给定半径的领域中必须至少包含最少数目的点289基本聚类方法概述方法一般特点划分方法 发现球形互斥的簇 基于距离 可以用均值或中心点等代表簇中心 对中小规模数据集有效层次方法 聚类是一个层次分解（即多层） 不能纠正错误的合并或划分 可以集成其他技术，如微聚类或考虑对象“连接”基于密度的方法 可以发现任意形状的簇 簇是对象空间中被低密度区域分隔的稠密区域 簇密度：每个点的“邻域”内必须具有最少个数的点 可能过滤离群点2 划分方法28划分方法给定一个n个对象或元组的数据库，一个划分方法构建数

5、据的k个划分，每个划分表示一个簇，并且k=n。 每个组至少包含一个对象 每个对象属于且仅属于一个组簇的表示 k-平均算法（由簇的平均值来代表整个簇） k中心点算法（由处于簇的中心区域的某个值代表整个簇）划分准则 同一个聚类中的对象尽可能的接近或相关，不同聚类中的对象尽可能的远离或不同1128K-均值：一种基于形心的技术假设数据集D包含n个欧式空间中的对象，划分把D中的对象分配到k个簇中。簇Ci的质量可以用簇内变差度量，它是Ci中所有对象和形心ci之间的误差的平方和，定义为1221,ikiiEdist pCp c28K-均值：一种基于形心的技术算法 K - 均值。用于划分的k 均值算法，其中每个

6、簇的中心都用簇中所有对象的均值来表示方法 从D中任意选择k个对象作为初始簇中心 Repeat 根据簇中对象的均值，将每个对象分配到最相似的簇 更新簇均值，即重新计算每个簇中对象的均值 Until不再发生变化输入 k：簇的数目 D：包含n个对象的数据集1328K-均值：例子-步骤114k1k2k3XY随机选择3个簇中心28K-均值：例子-步骤215k1k2k3XY分配每个点到最近的簇中心28K-均值：例子-步骤316XY移动每个簇中心到每个簇的平均位置k1k2k2k1k3k328K-均值：例子-步骤417XY把对象重新分布到离簇中心最近的簇中k1k2k328K-均值：例子-步骤418XYA: t

7、hree points with animationk1k3k228K-均值：例子-步骤4b19XY重新计算簇的均值k1k3k228K-均值：例子-步骤520XY把簇的中心移到簇的均值k2k1k328K-均值：缺点21n 是局部最优，不是全局最优n 要求用户必须事先给出要生成的簇的数目，选择初始划分的最佳方向、更新分区和停止准则n 不适合发现大小很不相同的簇或具有凹状的簇n 算法只有在簇的平均值被定义的情况下才能使用，这不适合涉及有类属性的数据n 对噪音和异常点非常敏感n 孤立点（极大值）的存在，会大幅度扭曲数据的分布28K-中心点：一种基于代表对象的技术k 中心点聚类：首先为每个簇随意选择选

8、择一个代表对象mediod ；剩余的对象根据其与代表对象的距离分配给最近的一个簇。然后反复地用非代表对象来替代代表对象，以改进聚类的质量。聚类结果的质量用一个代价函数来估算，该函数评估了对象与其参照对象之间的平均相异度。围绕中心点划分（PAM） 与k 均值算法一样，初始代表对象任意选取。考虑用一个非代表对象替换一个代表对象 是否能够提高聚类质量 PAM在小型数据集上运行良好，但是不能很好地用于大数据集22PAM的改善 CLARA：大型应用聚类 CLARANS：基于随机搜索的聚类大型应用28K-中心点：一种基于代表对象的技术23012345678910012345678910K=2任意选取 k

9、个对象作为初始 medoids将其余对象分配到最近的medoids所代表的类随机选取一非中心对象,Oramdom计算交换代价012345678910012345678910如果聚类质量被提高,则代替原medoidDo loopUntil no change0123456789100123456789103 层次方法28凝聚的与分裂的层次聚类对给定数据对象集合进行层次分解 自底向上方法（凝聚）：开始将每个对象作为单独的一个组，然后相继的合并相近的对象或组，直到所有的组合并为一个，或者达到一个终止条件 自顶向下方法（分裂）：开始将所有的对象置于一个簇中，在迭代的每一步，一个簇被分裂为多个更小的簇，

10、直到最终每个对象在一个单独的簇中，或达到一个终止条件 缺点：合并或分裂的步骤不能被撤销2528层次方法将距离矩阵作为聚类标准 这种方法不需要把簇k的数量作为一个输入，但是需要一个终止条件26Step 0Step 1Step 2Step 3Step 4bdceaa bd ec d ea b c d eStep 4Step 3Step 2Step 1Step 0凝聚的(AGNES)分裂的(DIANA)28算法方法距离度量最小距离均值距离最大距离平均距离2728BIRCH:使用聚类特征树的多阶段聚类BIRCH 聚类特征CF=LS表示n个点的线性和，而SS是数据点的平方和 采用了一种多阶段聚类技术：数

11、据集的单遍扫描产生一个基本的好聚类，而一或多遍的额外扫描可以进一步的改进聚类质量 阶段一：BIRCH扫描数据库，建立一棵存放于内存的初始CF-树，它可以被看做数据的多层压缩，试图保留数据的内在聚类结构 阶段二：BIRCH采用某个（选定的）聚类算法对CF树的叶节点进行聚类，把稀疏的簇当作离群点删除，而把稠密的簇合并为更大的簇282829CF树结构CF1child1CF3child3CF2child2CF6child6CF1child1CF3child3CF2child2CF5child5CF1CF2CF6prevnextCF1CF2CF4prevnextB = 7L = 6Non-leaf no

12、deLeaf nodeLeaf node28Chameleon:使用动态建模的多阶段层次聚类Chameleon（变色龙） 是一种层次聚类算法，它采用动态建模来确定一对簇之间的相似度 如果两个簇的互联性都很高并且它们之间又靠的很近就将其合并3028概率层次聚类算法层次聚类的缺点 很难选择一个好的距离度量 数据对象不能有缺失的属性值 结果聚类层次结构的优化目标可能不清晰概率层次聚类 使用概率模型度量簇之间的距离 生成模型：把待聚类的数据对象集看做要分析的基础数据生成机制的一个样本 聚类的任务是使用待聚类的观测数据对象，尽可能准确地估计该生成模型314 基于密度的方法28基于密度的方法基于距离的聚类

13、方法的缺点 只能发现球状的簇，难以发现任意形状的簇基于密度的据类 只要临近区域的密度（对象或数据点的数目）超过某个临界值，就继续聚类 优点：可以过滤掉“噪声”和“孤立点”，发现任意形状的簇3328DBSCAN:一种基于高密度连通区域的基于密度的聚类DBSCAN 找出核心对象，即其邻域稠密的对象。它连接核心对象和它们的邻域，形成稠密区域作为簇 密度可达：点 p 关于Eps, MinPts 是从 q密度可达的, 如果 存在一个节点链 p1, , pn, p1 = q, pn = p 使得 pi+1 是从pi直接密度可达的 密度相连：点 p关于 Eps, MinPts 与点 q是密度相连的, 如果存

14、在点o使得, p 和 q 都是关于Eps, MinPts 是从 o 密度可达的34pqopqp1密度可达密度相连28DBSCAN:一种基于高密度连通区域的基于密度的聚类DBSCAN缺点 对用户定义的参数是敏感的，参数难以确定（特别是对于高维数据，设置的细微不同可能导致差别很大的聚类）3528OPTICS:通过点排序识别聚类结构OPTICS:并不显式地产生数据集聚类，而是输出簇排序 这个排序是所有分析对象的线性表，并且代表了数据的基于密度的聚类结构 这个排序等价于从广泛的参数设置中得到的基于密度的聚类 簇排序可以用来提取基本的聚类信息，导出内在的聚类结构，也可以提供聚类的可视化36每个对象需要存

15、储两个值n 对象对象p的的核心距离核心距离(core-distance)是使得是使得p成为核心对象的最小成为核心对象的最小 。如果如果p不是核心对象不是核心对象, p的核心距离没有定义的核心距离没有定义 n 对象对象q关于另一个对象关于另一个对象p的的可达距离可达距离(reachability-distance )是是p的核的核心距离和心距离和p与与q的欧几里得距离的欧几里得距离之间的较大值之间的较大值. 如果如果p不是一个核心不是一个核心对象对象, p和和q之间的可达距离没有定义之间的可达距离没有定义 28OPTICS:通过点排序识别聚类结构37例例: 设设 =6(mm), MinPts=5.p的的核心距离核心距离是是p与第四个最近的数据对象之间的距离与第四个最近的数据对象之间的距离 。q1关于关于p的可达距离是的可达距离是p的核心距离的核心距离(即即 =3mm), 因为它比从因为它比从p到到q1的欧几的欧几里得距离要大。里