第十章_聚类分析3.ppt

划分方法（Partitioning method） 缺陷： 不同的初始值，结果可能不同 有些k均值算法的结果与数据输入顺序有关，如在线k均值算法 用爬山式技术（hill-climbing）来寻找最优解，容易陷入局部极小值 基于距离的方法进行聚类只能发现球状类，当类的形状是任意的时候怎么识别？（黑板图示） 下面介绍其中一种常用的算法： 主要有DBSCAN，OPTICS法 思想： 只要临近区域的密度超过一定的阀值，就继续聚类 特点： 可以过滤噪声和孤立点outlier，发现任意形状的类 把样本空间量化为有限数目的单元，形成一个网络结构，聚类操作都在这个网格结构（即量化空间）上进行 为每个类假定一个模型，寻找数据对给定模型的最佳拟合。 此不详述，有兴趣可以参考《DataMing Concepts and Techniques》即《数据挖掘概念于技术》Jiawei Han Micheline Kamber机械工业出版社 不稳定的聚类方法 受所选择变量的影响 如果去掉或者增加一些变量,结果会很不同.因此，聚类之前一定要明确目标，选择有意义的变量。 变量之间的相关性也会影响聚类结果，因此可以先用主成分或因子分析法把众多变量压缩为若干个相互独立的并包含大部分信息的指标，然后再进行聚类。 不稳定的聚类方法 输入参数凭主观导致难以控制聚类的质量 很多聚类算法要求输入一定的参数，如希望产生的类的数目，使得聚类的质量难以控制，尤其是对于高维的，没有先验信息的庞大数据。 首先要明确聚类的目的，就是要使各个类之间的距离尽可能远，类中的距离尽可能近，聚类算法可以根据研究目的确定类的数目，但分类的结果要有令人信服的解释。 在实际操作中，更多的是凭经验来确定类的数目，测试不同类数的聚类效果，直到选择较理想的分类。 不稳定的聚类方法 算法的选择没有绝对 当聚类结果被用作描述或探查工具时，可以对同样的数据尝试多种算法，以发现数据可能揭示的结果。 不稳定的聚类方法 聚类分析中权重的确定 当各指标重要性不同的时候，需要根据需要调整权重。如加权欧式距离，权重可以用专家法确定。 * 动态聚类法 系统聚类法是一种比较成功的聚类方法。然而当样本点数量十分庞大时，则是一件非常繁重的工作，且聚类的计算速度也比较慢。比如在市场抽样调查中，有4万人就其对衣着的偏好作了回答，希望能迅速将他们分为几类。这时，采用系统聚类法就很困难，而动态聚类法就会显得方便，适用。 动态聚类使用于大型数据。 基本思想：选取若干个样品作为凝聚点，计算每个样品和凝聚点的距离，进行初始分类，然后根据初始分类计算其重心，再进行第二次分类，一直到所有样品不再调整为止。 选择凝聚点 分 类 修改分类 分类是否合理 分类结束 Yes No 用一个简单的例子来说明动态聚类法的工作过程。例如我们要把图中的点分成两类。快速聚类的步骤： 1、随机选取两个点 和 作为凝聚点。 2、对于任何点 ，分别计算 3、若 ，则将 划为第一类，否则划给第二类。于是得图（b）的两个类。 4、分别计算两个类的重心，则得 和 ，以其为新的凝聚点，对空间中的点进行重新分类，得到新分类。 (b) 任取两个凝聚点 (c) 第一次分类 (d) 求各类中心 （a）空间的群点 (e) 第二次分类 动态聚类法 优点：计算量小，方法简便，可以根据经验，先作主观分类。 缺点：结果受选择凝聚点好坏的影响，分类结果不稳定。 选择凝聚点和确定初始分类 凝聚点就是一批有代表性的点，是欲形成类的中心。凝聚点的 选择直接决定初始分类，对分类结果也有很大的影响，由于凝聚点 的不同选择，其最终分类结果也将出现不同。故选择时要慎重．通 常选择凝聚点的方法有： (1) 人为选择，当人们对所欲分类的问题有一定了解时，根据经验，预先确定分类个数和初始分类，并从每一类中选择一个有代表性的样品作为凝聚点。 (2) 重心法 将数据人为地分为A类，计算每一类的重心，将重心作为凝聚点。 (3) 密度法 以某个正数d为半径，以每个样品为球心，落在这个球内的样品数(不包括作为球心的样品)称为这个样品的密度。计算所有样品点的密度后，首先选择密度最大的样品为第一凝聚点。然后选出密度次大的样品点，若它与第一个凝 聚点的距离大于2d ，则将其作为第二个凝聚点；否则舍去这点。这样，按密度由大到小依次考查，直至全部样品考查完毕为止．此方法中，