基于流形学习的离群点检测方法

基于流形学习的离群点检测方法 基于流形学习的离群点检测方法 1 1 1 2 1 徐雪松, 宋东明, 张,许满武, 刘凤玉 () 1 . 南京理工大学计算机科学与技术学院 , 南京 210094 ; 2 . 南京大学计算机科学与技术系 , 南京 210093 [ 摘要 ] 为了提高高维数据集合离群数据挖掘效率 ,提出了一种基于流形学习的离群点检测算法 。局部线 () 性嵌入 locally linear embedding ,LL E算法是流形学习中有效的非线性降维方法 ,它的优势在于只定义唯一的 参数 ,即邻域数 。根据 LL E 算法的思想寻找样本数据的内在嵌入分布 ,并通过邻域数选取和降维后数据点之 间的距离调整 ,提高了数据集中离群点发现效率 ,同时利用离群点权值判别式进行权值数据判定 ,根据权值 的大小标识出数据集中的离群点 ,仿真实验的结果表明了该方法能够有效地发现高维数据集中的离群点 。 与此同时 ,该算法具有参数估计简单 、参数影响不大等优点 ,该算法为离群点检测问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 的机器学习提供了一 条新的途径 。 [ 关键词 ] 流形学习 ;离群点检测 ;高维数据 ;维数约减 ;离群数据 () [ 中图分类号 ]TP391 [ 文献标识码 ]A [ 文章编号 ] 1009 - 1742 200902 - 0082 - 06 使数据集不满足任何特定分布模型 ,它仍能有效地 1 前言发现离群点 。此算法的一个主要缺陷是要计算所有 () 离群数据 outlier是在数据集中与众不同的数 点之间的距离 ,每计算一个点的距离就要扫描一次 据 ,使人怀疑这些数据并非随机偏差 ,而是产生于完 数据集 ,对于大数据集 ,其 I/ O 次数常常使得算法的 1 全不同的机制。目前已经出现了一些高效的离群 计算效率非常低 。由此 ,基于 LL E 算法和基于距离 点检测挖掘算法 :基于聚类的 、统计的 、距离的 、深度 2 ,6 方法的融合 ,提出了一种思路 ———基于流形学习的的以及基于密度的方法等 5 种类型。但大多数 离群点检测方法 , 其基本思想是 : 该算法利用 LL E离群点检测算法对高维数据的异常检测效果都不是 算法对高维非线性数据进行维数约减 ,对从高维采 很理想 。高维空间离群点检测与其他数据集的离群 样数据中恢复得到低维数据集 ,通过邻域数的选取 , 点检测差别甚大的原因主要有两个 :a . 对高维数据 结合降维后数据点之间距离调整 ,并根据文章提出 的估计需要的样本个数与维数构成指数增长的关 的离群点权值判别式进行权值数据的判别 ,同时 ,在 ( 系 , 即 机 器 学 习 中 的“维 数 灾 难 ”curse of 7 判别基础上 ,设定分段线性处理 ,再利用局部邻近点 ) dimensionality; b. 大量的数据 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 问题本质上是 加权 ,最终确定离群点 。实验表明此算法能够快速 非线性的 ,甚至是高度的非线性 。一种常用的做法 处理带有离群点的非线性高维数据集 ,结果与对象 是在保持数据所含感兴趣信息的前提下 ,尽可能降 空间分布顺序无关 ,并且效率优于已有的同类基于 低数据的维数 , 即降维 。LL E 是 Roweis 和 Saul 于 距离的离群点检测算法 。 2000 年提出的一种解决非线性问题及克服维数灾 8 难问题的方法;由文献9 和10 中可知基于距离 的 离群点最早是由 Knorr 和 Ng 提出的 ,他们把数据 2 LL E 算法简介 看作高维空间中的点 ,离群点被定义为数据集中与 LL E 算法是映射数据 X = { x, x, , x} , x 1 2 n i大多数点之间的距离都大于某个阈值的点 。基于距 D d ( ? R到数据集 Y = { y , y, , y } , y ? RD >1 2 n i 离的离群点定义包含并拓展了基于统计的思想 ,即 ) d。该算法主要包括 3 步 : ( 第一步 ,对高维空间中的每个样本点 xi = 1 ,i [ 收稿日期 ] 2007 - 09 - 18 ; 修回日期 2008 - 02 - 12() [ 作者简介 ] 刘凤玉1943 - ,女 ,江苏江阴市人 ,南京理工大学教授 ,主要研究方向为人工智能与信息安全 ; E2mail :liu. fengyu @263 . net ) 2 , , n, 计算它和其他 n - 1 个样本点之间的距样本集 , 近邻点个数 k 的选取对实验结果影响较 ( 大 。在样本点分布稀疏的区域 , k 个近邻点所组成 , 离 ,根据距离的大小 ,选择前 K 个与 xi = 1 ,2 ,i 的局部邻域显然要比在样本点分布比较密集的区域 ) n最近的点作为其邻近点 ,采用欧氏距离来度量两 大 ,可以通过以下对数据点之间距离的调整来降低 x- x| ; 个点之间的距离 ,即 d= |i j ij 它受样本点分布的影响 。 ) ( n,找到它的 K, 第二步 ,对每个 xi = 1 ,2 ,i 对于 LL E 算法降维后分布中含有离群点的样 个近邻点之后 ,计算该点和它的每个近邻点之间的( ) i本集 ,由于 LL E 算法能够实现高维输入数据点映射 权值 w ,即最小化 :j 到低维坐标系 ,同时保留邻接点之间的关系 ,即固有 n K 2 ( )i ) ()( min w= x- w x1 i j j的几何结构得到保留 。因此 ,对降维后所得数据集 , 6 6 i = 1 j = 1 k 可以调整数据点之间的距离 , 以有利于离群点的 ( )i ( ) ( 其中 , w = 1 ,如果 xj = 1 ,2 ,, n不是 xij j i 6 发现 。 j = 1 ( ) i我们知道在样本点分布稀疏的区域 ,近邻点所 ) n的近邻 ,则 w = 0 ;, = 1 ,2 , j 组成的局部邻域应该要比在样本点分布比较稠密的 ( 第三步 ,根据高维空间中的样本点 xi = 1 ,2 ,i 区域大 ,所以需要对原有的欧氏距离公式改进 ,改进 ) ) ( K之间的权值, , n和它的近邻 xj = 1 ,2 ,j ( )距离如下 :i w 来计算低维嵌入空间中的值 y和 y。由于在低j i j | y- y| i j 维空间中尽量保持高维空间中的局部线性结构 , 而 ()( ) 4 dy, y= ij i j ( ) ( ) M i M j( ) ( )ii 权值 w 代表着局部信息 ,所以固定权值 w ,使下j j ( ) ( ) ( ) 其中 , M i , M jyi = 1 ,2 , , n, 分别表示i 面的损失函数最小化 :( ) yj = 1 ,2 , , n, 采用改 和其他点之间的平均值 j n K 2 ( )i T ( ) ) ( y- w y min ?Y== t r Y M Yi j i进的距离寻找离群点 。6 6 i = 1 j = 1 ( ) dy, y的分子是普通的欧氏距离 ,分母是数 ij i j ()2 值 ,所以容易证明给出的新距离满足距离定义的要 T ) ( ) ( W I - W 。 其中 , M = I -求 ,即 n n 1 T ( ) ) 1dy, y?0 ,当且仅当 y= y时成立 ,满ij i j i j y= 0 且 要求yy = 1 , 以使 min ? i i i6 6 ni = 1 i = 1 足距离的非负性 ; ( ) Y对平移、旋转和伸缩变化都具有不变性 ,使 min ) 2满足距离对称性要求 :( ) ?Y最小化的解为矩阵 M 的最小几个特征值所 ( ) ( ) dy, y= dy, y; ij i j ij j i 对应的特征向量构成的矩阵 Y。取 M 最小的 m + 1 个 ) 3满足三角不等式要求 ,即 特征值对应的特征向量 , 去掉其中最小的特征值对 ( ) ( ) ( ) dy, y+ dy, y? dy, y。 新的ij i j it i t it j t 应的特征向量 ,剩余的 m 个特征向量组成的矩阵就 是低维空间中所得特征向量 。 距离使处于样本点分布较密集区域的样本 点之间的距离增大 ,而使处于样本点分布较稀疏的 区域的样本点之间的距离缩小 ,这样会使降维后的 3 基于流形学习的离群点检测方法 样本数据集整体分布趋于均匀化 ,有利于近邻点计 3. 1 邻域数的选取和改进距离定义 算 ,从而使数据集中的离群点更加突出 。同时距离 最近邻域最佳选取的原因在于大量的最近邻域 公式可设定所需的距离尺度用于下面的判别定理 。可以促成流形小规模结构的消除及整个流形的平 3. 2 离群点的权值判别定理 滑。相反 ,太少邻域可能误将连续的流形划分成脱经过 LL E 算法降维 ,包括离群点的低维数据集 节的子流形 。可参照文献 11 原则按下式进 行 是通过权值 W 计算而得 ,离群点权值的变化情况可 选取 : 由以下定理判别 。 2 ρ)()(( ) k = argmin 1 - D D 3 令 y代表 y, y所代表相应的真实值 , U yx y 0 i i 0 D是输入空间 X 的欧氏距离矩阵 , D是得到x y ρ嵌入的低维流形 Y 的欧氏距离矩阵 ,是他们之间 ( ) 代表 y的邻域 ,设 y, y,, y? U y,则0 1 2 k 0 离群点 ,以及相应的A 为 正 交 矩 阵 , ? =。 由 于 , k k λ 0 k i′ i′ = , W = 1 y′W y′ 0iT 6 6 0 0 0 i = 1 i = 1 ( ) ( ) ran k YY= ran k Y,所以 若再令T T 0 0 T T δ(δ) δ)(δ 0 E W Y Y W = E W A ? AW) ( Y= y , y , , y , 1 2 k k 0′ 2 ( )Y = y′, y′, (), y′ λ8 (δ) 1 2 k ?E W mini 6 λ i = 1 ,= 0 i 以及( ) 通过对 A 进行行初等变换 改变两行的位置,1 2 k T ) ( W = W, W, W, , () 然后计算相应的式 2,将所得结果相加可得1′ 2′ k′T ) ( W′= W, W, , WT T 0 0 T T (δδ)(δδ) E W Y Y W = E W A ? AW 于是有0 0′ 1 2 y= Y W , y′= Y W′ ()λδ 9 ?E ‖W ‖0 0 min k 0 其中 , Y代表 y 点的邻域矩阵。0 λλ 其中 , = min {> 0} min i 1 ?i ?k , 各离群点之间 , 不同真定理在上述记号下 () 结合式 1可知k 实值之间 ,以及 W与离群点之′间是相互独立的 ,各 ( ) k k + 1 2 2 2 ()δ 10 E ‖W ‖ ?δEW i() δ6 = W-′ 离群点是同均值 0,同方差的 ,并且记Wλ l min i = 1 W ,有如下判别式 : λl2 2min δ 即 , E ‖W‖′? E ‖W ‖。2 λl( σ)k k + 1 min 2 2δ() 5 E ‖W‖′? E ‖W ‖2( σ)k k + 1 由上述定理可知 , 在邻域大小 k 已知情况下 ,0 ( ) λ , ‖?‖取为欧几里德范数 , l = ran k Y,其中 min 离群点权值 W主要由′ 3 个因素决定 :a . 数据点之间 T 00 λ距离 d 的大小 ; b. 邻域的影响 , 即 和秩 l 的大 min Y为 Y的最小非零特征值 , d 代表 d 的第 i 个分 i 小 ;c . 真实值权值的 ‖W ‖的大小 。对于 a 要素可 量 : k λ通过距离公式确定 ,b 要素可通过调整和 l 两个 min 2 2 2σ) σ σ( ) ( = = ,V ar d i = 1 ,2 , , k。i i i 6 值确定 ,c 要素直接由 LL E 算法可知 。 i = 1 3. 3 算法描述( ) di = 0 ,1 , + 证明 :由 y′=y, k可见 i i i k 输入 :输入样本数据集 X = { x, x,, x} , x 1 2 n i0′ D W′d] y y′= Y W′+ i i 0i ? R,邻域参数 k ; 6 i = 1 输出 :低维数据集中的离群点 y′;k i 0 ( 步骤 1 对高维空间中的每个样本点 xi = 1 , Wd′ i = YW′+ - d i i 0 6 i = 1 ) 2 , , n, 计算它和其他 n - 1 个样本点之间的距 k k 0 )( ) ( W′d d , W′ 进一步有 YW′-= - Wi 0 i i 6 6 ( , i = 1 i = 1 离 ,根据距离的大小 ,选择前 K 个与 x i = 1 ,2 ,i k ) n最近的点作为其邻近点 ,常采用欧氏距离来度量= W= 1 i 6 i = 1 两个点之间的距离 ;k 0( ) 步骤2 对每个 xi = 1 ,2 ,, n,找到它的 Ki ()δ( ) 6 即 YW = W′d - d i 0 i 6 i = 1 个近邻点之后 ,计算该点和它的每个近邻点之间的 由于离群点是独立的 ,则有( ) i() 权值 w ,即最小化式 1;j T T 0 0(δδ)E WYYW 步骤 3对最小化所得的每一点的权值 min ?k k T ( ) w组成一个权值矩阵 ,并对 W 进行约束限制 ;)( ) ( d = E - - W′ddW′d i i 0i i 06 6 i = 1 i = 1 ( 步骤 4根据高维空间中的样本点 xi = 1 ,2 ,i k k 2 2 2 ( ) , n ) K , xj = 1 ,2 , 和它的近邻之间的权值j = σ+ ( )σEWE W′W′ ii j 6 6 ( )ii = 1 i = 1 w来计算低维嵌入空间中的值 y和 y, 即 y- j i j i 2 2K ( σ )()?k + 1E ‖W‖′7 ( )i T T T w y; j j 0 0 0 0 6 A?A ,其中 YYj = 1 记 Y的正交分解为 Y= () 步骤 5根据式 3重新选取邻域数 k ,并重复由于对降维后的数据点之间距离重新调整 , 使得降 维后的样本数据集整体分布趋于均匀化 , 有利于近 1 至步骤 4 ;步骤 邻点计算 ,从而使数据集中的离群点更加突出 。采用 步骤 6根据距离公式改进降维后样本数据集 文章提出的算法 , 将三维的曲线形柱面降维至二维 中各点之间的距离 , 以利于发现样本数据集中的离 群点 ;平面 ,并分离出离群点的效果如图 2 所示 。 步骤 7经过 LL E 算法降维 ,包括离群点的低 维数据集是通过权值 W 计算而得 ,离群点权值的变 () 化情况可依据判别定理 ,由式 4得出 ; 对从判别式中得到的离群点权值 W,′ 步骤 8 利用离群点的局部重建权值矩阵及近邻点的线性组 合来表示出该离群点 。 4 算法的实现及其实验结果的评估 采用文章提出的算法对两个样本集进行实验 , 其中一个样本集是采用算法生成的曲线形柱面 ,另 ( 一个样本集来自于 UCI 标准数据库 http :ΠΠwww. ics. ) uci . edu/ mlearn/ MLRepository. htm1。 图 2 降维后分离出离群点的数据集 Fig. 2 Outliers separated from data set after 整个实验运行在主频为 P42 . 4 GHz 、内存为 512 dimensionality reduction MB 、80 GB 硬盘 、操作系统为 Windows XP sp2 的主机 上面 。基于此环境 ,对整个算法进行相关性能测试 。 第 二 个 数 据 集 为 MUSHROOM 数 据 集 ,( 第一个实验数据集为曲线形柱面 如图 1 所 MUSHROOM 数据集为 UCI 标准数据库之一 。该数 ) 示,柱面上半部分由 30 个离群点组成 ,下半部分由 据集中训练样本为 210 个 ,测试样本为 8 124 个 ,样 20 ×20 = 400 个采样点组成 ,数据点维数为三维 ,内 本的维数为 22 。表 1 给出了分别使用不同的基于 在维数为两维 。目的是将三维数据降为两维数据 , 距离 的 离 群 点 检 测 算 法 和 笔 者 提 出 的 算 法 对 并发现离群点 。 MUSHROOM 数据集进行学习和离群点分离的结果 , 其中提出算法在运行时需要指定不同参数的值 ,算 () 法中的 k 值根据式 3选取 ,其取值范围在 7,12 时 效果较好 , k 值的选取与测试错误率如图 3 所示 。 () 除此之外 ,还需根据式 4调整降维后数据集中点之 间的距离 。笔者提出算法的测试分离离群点的错误 率明显低于其他基于距离的离群点检测算法的测试 错误率 ,而且该算法具有良好的特性 , 即 k 值的估 计非常简单 ,且在一定范围内结果比较稳定 。 表 1 不同算法对离群点的检测结果 Ta ble 1 Experimental result of Outliers Detection Based on 图 1 曲线形柱面数据集different algorithms Fig. 1 Data set f ormed by curve sha pe cylinder % 测试错误率Π 算法类别 ( ) ( ) 基于索引的算法基于距离?0 . 6122. 32 ( ) 嵌套循环算法基于距离 实验中近邻点的个数 k 选择很重要 , k 的取值 ( )26. 73 ?0 . 63( ) 基于单元算法基于距离太大 ,算法不能体现局部特性 ,而且降维效果显著变 ( )18. 24 ?0 . 61( )文章提出的算法k = 9 ( )3 . 67 ?0 . 66差 ,这是因为测试数据是比较弯曲的流形 ,容易发生 短路现象 。反之 ,算法不能保持样本点在低维空间中 实验表明该方法是正确的 ,为了更好地应用 ,应 群点检测效果 。 参考文献 1 ] 夏火松. 数据仓库与数据挖掘技术 M . 北京 : 科学出版社 2004 Barnett V , Lewis T. Outliers in Statistical Data M . New York : 2 ] John Wiley and Sons , Inc , 1994 3 ] Preparata F , Shamos M I. Computational Geometry : an Introduction M. New York : Springer 2Verlag , 1988 4 ] Knorr E M , Ng R T. Algorithms for mining distance2based outliers in 图 3 算法中 k 值对数据集中离群点检测错误率的影响large datasetsA . Proceedings of the 24th International Conference Fig. 3 The effect of k value from algorithm on mista ke on Very Large Data Bases C . New York : Morgan Kaufmann , rate detected in outliers from data set 1998 . 392 - 403 5 ] Breunig Markus M B , Kriegel Hans Peter , Ng Raymond T , et al . 如离群点个数较少 , 运算时间明显加快 ;LOF : identifying density2based local outliers A . Chen W , ) 2可以使用增量技术 ,用户选择某个阈值 ,计算 Naughton J F , Bernstein P A , eds. Proceedings of the ACM SIGMOD International Conference on Management of Data C . 了一个结果后 ,不用全部从头开始计算两点距离 ,可 Dallas , Texas : ACM Press , 2000 :93 - 104 以大大减少运行时间 ; 6 ] Papadimitriou Spiros , Kitagawa Hiroyuki , Gibbons Phillip B. LOCI : ) 3距离的选取非常重要 ,实验中采用改进的距fast outlier detection using the local correlation integral A . 离公式 ,可以根据挖掘数据的目标 ,将所感兴趣的离 Proceedings of the 19th International Conference on Data Engineering 群数据值加权 。 C. 2003 . 315 - 326 7 ] Agrawal R , Gehrke J , Gunopulos D , et al . Automatic subspace 实验说明了笔者提出的算法既保证了得到的结 clustering of high dimensional data for data mining applicationsA . 果相当接近于全局最优解 ,又保证了能非常快速地 Haas L M , Tiwary A. Proc of the ACM SIGMOD International 得到结果 。即使对于样本的个数为8 124 、维数为 22 Conference on Management of Data C. Seattle :ACM Press ,1998 :94 这样的高维大样本 ,也能快速得到比较满意的结果 。- 105 8 ] Roweis S T , Saul L K. Nonlmensionality reduction by locally linear 5 结语() embedding J . Science , 2000 ,290 22:2323 - 2325 在分析了传统的离群数据挖掘算法优点和缺点 Knorr E M ,Ng R T. Finding intensional knowledge of distance2based 9 ] 的基础上 ,针对非线性高维数据集中的离群点检测 outliersA . Scotland : Pruc of the 25th VLDB Conference Edinburgh 问题 ,提出一种基于流形学习的离群点检测算法 。 C. 1999 . 21l - 222 该算法利用 LL E 算法的思想寻找样本数据的内在 Knorr E M ,Ng R T. Algorithms for mining distance2based oufliers in 10 large datasetsA . New York : Proc of Int Conf Very Large Data 2bases 嵌入分布 ,并通过邻域数选取和降维后数据点之间 () VLDB’98C. 1998 . 392 - 403 的距离调整 ,提高了数据集中离群点发现效率 ,根据 Olga Kouropteva , Oleg Okun , Matti Pietik,inen. Selection of the 11 离群点权值判别式进行权值数据判定 ,依据权值的 optimal parameter value for the locally linear embedding 大小标识出数据集中的离群点 。特别是对于一些线 algorithmA . FSDK″02 , Proc of the 1 st Int Conf on Fuzzy Systems 性不可分的数据集 ,在运用传统离群点检测算法失 and Knowledge DiscoveryC. 2002 . 359 - 363 The research of detection of outliers based on manif old learning 1 1 1 2 1 Xu Xuesong, Song Dongming, Zhang Xu,Xu Manwu, Liu Fengyu ( 1 . Department of Computer Science and Technology , N anjing University of Science and Technology , N anjing 210094 , China ; )2 . Department of Computer Science and Technology , N anjing University , N anjing 210093 , China [ Abstract ] The data dimensionality reduction is the main method that can enhance the outliers mining efficiency based on higher2dimension data set . The research of detection of outliers based on manifold learning is proposed after analyzing the advantages and disadvantages of the classical outlier mining algorithm in the paper . Local Linear Embedding () algorithm LL Eis an effective technique for nonlinear dimensionality reduction in manifold learning. Compared with other dimensionality reduction algorithms , the advantage of the local Linear Embedding algorithm is that it only defines unique parameter , i . e . number of nearest neighbours. With the idea of Local Linear Embedding ,the algorithm can select optimal parameter and regulate the distance among data set after data dimensionality reduction , so as to improve efficiency of detection of outliers. The algorithm determines weighted values by discretion formula of weighted outliers. Through these weighted values , the experts can identify the outliers easily. Simulation results illustrate that this algorithm is very efficient. Moreover , our method has the advantage of simple parameter estimation and low parameter sensitivity. Our method gives a new way for the solution of detection of outliers. [ Key words ] manifold learning ; detection of outliers ; high dimensional data ; dimensionality reduction ;outliers