x 离群点挖掘.ppt

定义6-7 给定簇C，C的摘要信息CSI (Cluster Summary Information)定义为： 其中kind为簇的类别(取值‘normal’或‘outlier’)， 为簇C的大小, Cluster为簇C中对象标识的集合，Summary由分类属性中不同取值的频度信息和数值型属性的质心两部分构成，即： 定义6-8 假设据集D被聚类算法划分为k个簇 ，簇 离群因子(Outlier Factor) 定义为簇 其它所有簇间距离的加权平均值： 如果一个簇离几个大簇的距离都比较远，则表明该簇偏离整体较远，其离群因子也较大。 度量了簇 偏离整个数据集的程度，其值越大，说明 偏离整体越远。 基于聚类的离群挖掘方法(CBOD) CBOD方法由两个阶段构成： 第一阶段是利用一趟聚类算法对数据集进行聚类； 第二阶段是计算每个簇的离群因子，并按离群因子对簇进行排序，最终确定离群簇，也即确定离群对象。 CBOD算法描述如下： 第一阶段，聚类：对数据集D进行聚类，得到聚类结果 ； 第二阶段，确定离群簇：计算每个簇 的离群因子 ，按 递减的顺序重新排列 ，求满足： 的最小 ，将簇 标识为‘outlier’类(即其中每个对象均看成离群)，而将 标识为‘normal’类(即其中每个对象均看成正常)。 例6-6 基于聚类的离群点检测示例2 对例6-5中的数据集，聚类后得到三个簇C={C1、C2、C3}， 簇心分别为：C1(5.5,7.5)、C2(5,2)、C3(1.75,2.25)。 簇之间的距离分别为 进一步计算三个簇的离群因子，具体如下： 例6-6 基于聚类的离群点检测示例2 可见簇C1的离群因子最大，其中包含的对象判 定为离群点，与例6-5得到的结论相同。 基于聚类的动态数据的离群点检测 基本思想如下： 在对训练集聚类的基础上，按照簇的离群因子排序簇，并按一定比例将簇标识为”normal”或”outlier”，以标识的簇作为分类模型，按照对象与分类模型中最接近簇的距离判断它是否离群点。 基于聚类的动态数据的离群点检测 第一步，聚类：对训练集 进行聚类，得到聚类结果 ； 第二步，给簇作标记：计算每个簇 的离群因子 ，按 递减的顺序重新排列 ，求满足： 的最小b，将簇 标识为离群簇，而将 标识为正常簇。 第三步，确定模型：以每个簇的摘要信息，聚类半径阈值r作为模型。 (1) 模型建立 (2) 模型评估 利用改进的最近邻分类方法INN(Improved Nearest Neighbor) 评估测试集中的每个对象。INN方法具体描述如下： 对于测试集 中对象p，计算p与每个簇的距离 若 ，则说明p是已知类型的行为，将簇 的标识作为p的标识，否则说明p是一种新的行为，将p标识为可疑对象——候选离群点 。 (3) 模型更新 对于测试集 中对象p，按照前面聚类的方式，对新增对象进行增量式聚类更新 用建立模型同样的方法对所有簇重新标记其类别。 6.6 离群点挖掘方法的评估 可以通过下表所示混淆矩阵来描述离群点挖掘方法的检测性能。在离群点检测问题中，并不关注预测正确的normal类对象，重点关注的是正确预测的outlier类对象。 预测类别 outlier normal 实际类别 outlier 预测正确的outlier 预测错误的outlier normal 预测错误的normal 预测正确的normal 离群点检测方法准确性的两个指标 检测率(Detection rate)表示被正确检测的离群点记录数占整个离群点记录数的比例； 误报率(False positive rate)表示正常记录被检测为离群点记录数占整个正常记录数的比例。 期望离群点挖掘方法对离群数据有高的检测率，对正常数据有低的误报率，但两个指标之间会有一些冲突，高的检测率常常会导