《基于不完全数据的异常挖掘算法研究》由会员分享，可在线阅读，更多相关《基于不完全数据的异常挖掘算法研究（8页珍藏版）》请在金锄头文库上搜索。
1、第 41 卷 第 9 期2004 年 9 月计 算 机 研 究 与 发 展J OURNAL OF COMPU TER RESEARCH AND DEV ELOPMEN TVol141 ,No19Sep1 2004收稿日期 :2003 - 07 - 14 ;修回日期 :2004 - 02 - 26基于不完全数据的异常挖掘算法研究杨虎 1 ,2 钟震 1 程代杰 21 (重庆大学数理学院 重庆 400044)2 (重庆大学计算机学院 重庆 400044)(yh cqu1edu1cn)摘 要 异常挖掘是数据挖掘的重要研究内容之一 ,对于不完全数据会面对双重的困难 1 首先将用于缺失数据填充的EM 算
2、法和 MI 算法推广到混合缺失情形 ,并根据 Weisberg 的不完全数据填充理论 ,提出了 RE算法 ,然后通过将聚类分析与向前搜索算法结合起来 ,获得了比单纯的向前搜索法更优越的算法 1 最后 ,在上述填充算法的基础上探讨了不完全数据的异常挖掘 1 理论和实例分析均表明 ,基于不完全数据的异常挖掘算法是有效可行的 1关键词 缺失数据 ; EM 算法 ;聚类分析 ;异常挖掘中图法分类号 TP311An Outlier Mining Algorithm Based on the Imcomplete DataYAN G Hu1 ,2 , ZHON G Zhen1 , and CHEN G D
3、ai2Jie2( College of Sciences , Chongqing U niversity , Chongqing 400044)( College of Com puter Science , Chongqing U niversity , Chongqing 400044)Abstract Lots of deferent ways can be used to mine outliers , among which , the forward search algorithmis one of the most important ways1 Since data are
4、incomplete , data mining for outliers will encounter somedifficulties , and thus one needs to make an attempt on this field1 First of all , one should think of the fill ofthose lost data1 Thinking of the mixed loss , one can simplify the application of algorithm , such as EM algo2rithm and M I algor
5、ithm1 Furthermore , the more simple and facile RE algorithm is proposed1 The actual fillof data indicates the effect of the method1 When one uses the forward search algorithm to mine outliers , an2alyzing the formation of EM algorithm , he can use the same method to estimate the unknown parameter1Ev
6、en when making usual statistical outliers testing , the test statistics that relies on residuals can also be alsogenerated by EM algorithm1 That means the result of data mining is more credible when one first completesand then mines the data1 Finally , if one clusters the data beforehe selects initi
7、al subset , the result of re2search can be better and faster1 What s more , false conclusion can be avoided1Key words missing data ; EM algorithm ; clustering analysis ; outlier mining1 引 言异常挖掘 1 ,2 是数据挖掘的重要内容之一 ,尤其是针对不完全数据的异常挖掘更具有现实意义 1因为在金融证券、医学研究、调查统计、 Web 挖掘、信号传输和图像压缩等数据处理方面 ,得到的数据通常是不完全的 ,针对这些数
8、据进行异常挖掘时首先就必须考虑缺失数据可能造成的影响 ,途径之一就是寻求有效的数据填充方法 3 1本文区别于文献中通常的做法 ,综合考虑矩阵X 和响应变量 Y混合缺失即 Z = ( Y, X) 的情形 ,主要基于以下考虑 :(1) 现有文献往往仅对矩阵 X 或响应变量 Y 1995-2005 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved.的缺失进行分析 1 例如 ,Atkinson 和 Cheng3 对于矩阵 X 的缺失情况进行了分析 ; Glynn4 对于响应变量 Y的缺失情况进行了分析 1(2) 在现实的数据处理过
9、程中 ,混合缺失情况更为普遍 ,即所得到数据中的矩阵 X 和响应变量 Y往往都是不完全的 ,又比如对金融数据序列 , X 和 Y是一脉相承的 ,多数情况下我们实际考虑的是自回归问题 ,这时考虑矩阵 Z = ( Y, X) 的混合缺失是很自然的事 1(3) 有关矩阵 Z = ( Y, X) 的算法具有通用性 ,可以分别解决矩阵 X 的缺失和响应变量 Y 的缺失问题 1本文首先将用于缺失数据填充的 EM 算法和M I 算法 3 推广到混合缺失即 Z = ( Y, X) 的情形 ,针对 EM 算法和 M I 算法的不足 ,根据 Weisberg 的缺失数据填充理论 5 ,提出了 RE 算法 ,然后通
10、过将向前搜索算法的搜索初始子集先进行聚类分析 ,简化了 EM 算法的条件均值和协方差的计算 ,进而达到更快地搜索出初始子集的目的 ,获得了效果不错的改进的向前搜索算法并用于异常挖掘 1 研究表明 ,本文基于不完全数据的异常挖掘算法是有效可行的 12 混合缺失下的 EM 算法和 MI算法设 Y = + = 0 + X + ,其中 , Y 为 n 1响应变量 , 为 n ( p + 1) 阶矩阵 ,其中第 1 列的元素全为 1 , X 为 去掉第 1 列后的矩阵 , = ( 0 , 1 , , p) 为参数向量 , 为 n 1 随机误差向量 ,其分布为 N ( 0 , 2 I) 1 设矩阵 Z =
11、 ( Y, X) 存在数据缺失 ,即矩阵的某些元素缺失 1 1977 年由 Dempster ,Larid 和 Rubin6 提出的 EM 算法是一种迭代法 ,主要用来求后验分布的众数 (或极大似然估计 ) ,可用于处理缺失数据问题 3 1 EM 算法的每次迭代包含两步 :求期望值 ( E 步 ) 和极大值化 ( M 步 ) 1 对于混合缺失即矩阵 Z = ( Y, X) 的缺失模式可以建立类似于文献 3 的 EM 算法 1设 Z = ( Y, X) 服从多元正态分布 ,即zi = ( yi , xi) N p , ,其中 , = yx , = 2yi yx xy x x 1并设矩阵 Z =
12、( Y, X) 中 , Zmis为未 知值 , Zobs为已知值 , = ( , ) , f ( 3 ) 为概率分布函数 1 则 E 步将 log f ( / Zmis , Zobs ) 关于 Zmis 的条件分布f ( Zmis/ ( t - 1) , Zobs) 求期望 ,从而将 Zmis积掉 ,即Q ( / ( t - 1) , Zobs) EZmislog f ( / Zobs , Zmis) / Zobs , ( t - 1) =Zmislog f ( / Zobs , Zmis) f ( Zmis/ Zobs , ( t - 1) ) d Zmis =Zmislog f ( / Z
13、) f ( Zmis/ Zobs , ( t - 1) ) d Zmis ,(1)其中 , ( t - 1)是第 t - 1 步迭代得到的参数 的估计 1M 步 ,将 Q ( / ( t - 1) , Zobs) 极大化 ,即找到一个参数 ( t) ,使 :Q ( ( t) / ( t - 1) , Zobs) = max Q ( / ( t - 1) , Zobs) 1(2)如此完成一次迭代 ,用 ( t) 替代 ( t - 1) ,重复上述步骤直至收敛从而得到参数 的估计值 1 关于EM 算法的收敛性有很多文献给出论述 7 ,8 ,在此不加赘述 1 具体算法步骤如下 :设 (0)为 = (
14、 , ) 的初始值 ,设 ui , t为第 t 步得到的 的第 i 个元素的估计值 , jk , t为第 t 步得到的 的第 j 行第 k 列元素的估计值 ,根据 Atkin2son 和 Cheng 的公式 ,得到 ( t)与 ( t - 1)之间的关系公式 (3) (6) ,其中式 (3) 和式 ( 4) 各为第 t 步时 ( t)中 和 的估计式 :uj , t = 1n ni = 1zij , t - 1 , j = 1 , , p , (3) jk , t = 1n ni = 1 ( zij , t - 1 - uj , t - 1) ( zik , t - 1 - uk , t -
15、1) +cjk , t - 1 , j , k = 1 , , p , (4)其中 ,zij , t - 1 =E ( z ij/ zobs, i , ( t - 1) , z ij 未知 ,z ij , z ij 已知 ,i = 1 , , n , j = 1 , , p1 (5)cik , t - 1 =cov ( z ij , z ik/ zobs , i , ( t - 1) ) , z ij , z ik 未知 ,0 , 至少 z ij , z ik 中的一个已知 ,i = 1 , , n , j = 1 , , p , (6)zobs , i为第 i 组数据的已知分量 ; zij , t是第 t 步迭代得到的矩阵 Z 的第 i 行第 j 列元素的值 ; z ij为矩阵 Z的第 i 行第 j 列元素的值 ;式 (6) 中的 cjk , t - 1为第 t- 1 步迭代时第 i 组数据的条件协方差矩阵 Ct - 1的第 j 行第 k 列元素 13351 9 期 杨 虎等 :基于不完全数据的异常挖掘算法研究 1995-2005 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved.从式 (3) (6) 看出 ,
