数据挖掘6聚类.ppt

离异点分析（Outlier Analysis） 离异点挖掘的描述：给定一个n个数据点的集合以及预期的离异点的数目k，发现与剩余的数据相比是显著相异的、异常的或不一致的前k个对象。 离异点挖掘可以被看作两个子问题：（1）在给定的数据集合中定义什么样的数据可以被认为是不一致的；（2）找到一个有效的方法来挖掘这样的离异点。 §6.4 聚类算法的一些典型要求 可伸缩性 有的算法当数据对象少时处理很好, 但对大量数据对象偏差较大 大型数据库包含数百万个对象 处理不同属性类型的能力 许多算法专门用于数值类型的数据 实际应用涉及不同的数据类型 发现任意形状的聚类 基于距离的聚类趋向于发现具有相近尺度和密度的球状簇 一个簇可能是任意形状的 数据挖掘对聚类的要求(续) 用于决定输入参数的领域知识最小化 许多聚类算法要求用户输入一定的参数, 如希望产生的簇的数目.聚类结果对于输入参数十分敏感 参数难以确定, 增加了用户的负担, 使聚类质量难以控制 处理噪声数据和孤立点的能力 一些聚类算法对于噪音数据敏感, 可能导致低质量的聚类结果 现实世界中的数据库大都包含了孤立点, 空缺, 或者错误的数据 对于输入记录的顺序不敏感 一些聚类算法对于输入数据的顺序是敏感的, 以不同的次序输入会导致不同的聚类 数据挖掘对聚类的要求(续) 高维性（high dimensionality） 许多聚类算法擅长处理低维的数据, 可能只涉及两到三维 数据库或者数据仓库可能包含若干维或者属性, 数据可能非常稀疏, 而且高度偏斜 整合用户指定的约束 现实世界的应用可能需要在各种约束条件下进行聚类 要找到既满足特定的约束, 又具有良好聚类特性的数据分组是一项具有挑战性的任务 可解释性和可用性 用户希望聚类结果是可解释的, 可理解的, 和可用的 聚类可能需要和特定的语义解释和应用相联系 * * * * 　离差平方和是各项与平均项之差的平方的总和。 * * * * 缺陷： 不同的初始值，结果可能不同 有些k均值算法的结果与数据输入顺序有关，如在线k均值算法 对离异点很敏感，对于凹状的数据格式不合适 (2) K-Medoids 方法 Basic strategy： First, 任意选定k个样本点聚类中心，其他的样本根据与中心点的相似度确立类别号。 Then，在每一步都进行一个选择的中心点Oj与任意的非中心点Or之间的交换，这样的交换导致聚类质量的改进。 Total Cost = 20 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 K=2 Arbitrary choose k object as initial medoids Assign each remaining object to nearest medoids Randomly select a nonmedoid object,Oramdom Compute total cost of swapping 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 Total Cost = 26 Swapping O and Oramdom If quality is improved. Do loop Until no change 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 A Typical K-Medoids Algorithm (PAM) 为了评价Oj和Or之间的交换效果，为所有的非中心点的样本P准备了一个代价函数，根据P属于下面哪种情况，定义为等式中的一种: （1）、设P当前属于Oj代表的聚类，再假设Oi是P的第二相似聚类中心，则有d（P，Or）d（P，Oi）。即若由Or代替Oj，P就属于由Oi代表的聚类。此时涉及P的代价就为：CPjh＝d（P，Oi）－d（P，Oj） （2）、P当前属于由Oj所代表的聚类，而且P的第二相似聚类中心是Or。即若由Or代替Oj，P就属于由Or代表的聚类。此时涉及P的代价就为： CPjh ＝d（P，Or）－d（P，Oj） （3）、P当前不属于由Oj所代表的聚类，而是属于Oi聚类中心。设Oi与Or相比，P更相似于Oi，即，即使Or替换Oj，P仍属于Oi聚类。此时涉及P的代价就为： CPjh ＝0 （4）、 P当前不属于由Oj所代表的聚类，而是属于Oi聚类中心。设Oi与Or相比，P更相似于Or ，即，Or替换Oj后，P属于Or聚类。此时涉及P的代价就为： CPjh ＝ d（P，Or）－d（P，Oi） PAM Clustering: 原中心点是t和i，用h代替iTotal s