（概率论与数理统计专业论文）因子分析模型多异常点识别的贝叶斯分析.pdf

b a y e s i a nm e t h o d sf o rd e t e c t i n gm u l t i p l e o u t l i e r so ff a c t o ra n a l y s i sm o d e l b y c u im i a o q i n g s u p e r v i s o r ：a s s o c i a t e dp r o f j i a n gq i b a o s o u t h e a s tu n i v e r s i t y n a n j i n g ，2 1 1 1 8 9 ，c h i n a d e c e m b e r , 2 0 0 9 独创性声明及使用授权的说明 学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成 果尽我所知，除了文中特别加以标明和致谢的地方外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得东南大学或其它教育机构的学位或证书而使用过 的材料与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并 表示了谢意 二、关于学位论文使用授权的说明 签名；崔益日期：盈山) 东南大学、中国科学技术信息研究所，国家图书馆有权保留本人所送交学位论文的 复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文本人电子文档的内 容和纸质论文的内容相一致除在保密期内的保密论文外，允许论文被查阅和借阅，可 以公布( 包括刊登) 论文的全部或部分内容论文的公布( 包括刊登) 授权东南大学研究生 院办理 签名：槛导师签名；日期：墼) d 摘要 本文主要研究因子分析模型多异常点的识别问题在我们的问题中，异常点的个数 和因子个数都是未知的换言之，我们必须同时解决因子分析模型的多异常点识别问题 和模型选择问题针对这个复杂而又困难的问题，本文采用b a y e s 的方法解决这当中最 棘手的是如何设氍异常点的分布在以前的b a y e s 统计诊断文献中，一般假定正常点和异 常点来自同一个分布族，只是参数值有所不同而已：或者均值发生了漂移，或者方差扩 大了这种做法要求我们对于异常点的产生机制预先有充分的了解这在实际应用中并 不总是可能的，因为异常点的来源一般是不清楚的本文采取最保守的做法，假定异常 点来自整个空间上的均匀分布这相当于假定没有任何有关异常点的先验知识对于多 异常点的识别问题，本文提出了两套解决方案，即数据扫描法和随机搜索法 所谓数据扫描法就是为每个数据点设毁一个指示变量，用于说明该数据点是否为异 常点与此相对应，在后验分布的抽样算法中，每次迭代都必须更新这些指示变量，换 言之，我们要对整个数据集进行扫描这一方案的最大好处在于容易实现但是，当数 据集比较大时，其计算量之大使人难以忍受因此，我们提出了另一种方法，随机搜索 法在这一方案中，只有正常点的个数和每个正常点的标号( 它们合在一起决定了正常点 集) 是随机变量，相应的抽样算法每次迭代只更新正常点集，所需的操作无非是增加一个 数据点或剔除一个数据点正常点集的更新是所谓的变维抽样闻题，即在迭代过程中变 量个数是可变的为了实现变维抽样，本文采用了生死m a r k o v 链m o n t ec a r l o ( b d m c m c ) 方法与其它方法相比，b d m c m c 方法更容易实现另外，因子个数的确定也是变维抽 样问题，文中同样采用生死m a r k o v 链m o n t ec a r l o 方法确定因子个数 为了检验算法的精确性和有效性，本文进行了一系列模拟实验实验结果令人满意： 两种方法都能准确地确定因子个数和异常点，而且实验结果对参数的依赖性很小由于 迭代中需要更新的变量大大减少，随机搜索方法对于较大的数据集有明显的优势，在我 们的一个实验中，随机搜索方法的计算时间缩减了3 0 以上 关键词：因子分析模型；多异常点；模型选择；贝叶斯分析；m a r k o v 链m o n t ec a r l o a b s t r a c t i nt h i st h e s i s ，w ec o n s i d e rt h ep r o b l e mo fd e t e c t i n gm u l t i p l eo u t l i e r sf o rt h ef a c t o ra n a l y s i sm o d e l s i n c ew ea s s u m et h en u m b e ro ff a c t o r sa n dt h en u m b e ro fo u t l i e r sa r eb o t hu n k n o w n ，w em u s ts o l v et h e o u t l i e rd e t e c t i o np r o b l e ma n dt h em o d e ls e l e c t i o np r o b l e ms i m u l t a n e o u s l y t ot r e a ts u c hac o m p l i c a t e d a n dd i f f i c u l tp r o b l e m ，w ea d o p tt h eb a y e s i a np a r a d i g m t ot h i sa i m ，w es h o u l ds o l v es e v e r a lt e c h n i c a l p r o b l e m s t h em o s tc r i t i c a lo n ei st h ec h o i c eo ft h er i g h td i s t r i b u t i o nf o ro u t l i e r s i nt h eb a y e s i a n s t a t i s t i c a ld i a g n o s e sl i t e r a t u r e ，u s u a l l yas i n g l ef a m i l yo fd i s t r i b u t i o n si su s e df o ra l ld a t a ，t h eo u t l i e r s a r es i g n i f i e db yd i f f e r e n tp a r a m e t r i cv a l u e s s u c hac h o i c ei sr e a s o n a b l eo n l yi fw eh a v es u f f i c i e n tp r i o r i n f o r m a t i o nf o rt h eg e n e r a t i o no fo u t l i e r s i np r a c t i c e ，t h em e c h a n i s mf o rt h eg e n e r a t i o no fo u t l i e r si s r a r e l yc l e a r t h u sw es u p p o s et h eo u t l i e r sa r eg e n e r a t e df r o mt h eu n i f o r md i s t r i b u t i o no nt h ew h o l e s p a c e t h i si se q u i v a l e n tt oa s s u m en op a r t i c u l a rk n o w l e d g er e l a t e dt oo u t l i e r s t w os c h e m e sa r ep r o p o s e di nt h i st h e s i s ，e a c hc o r r e s p o n d i n gt oap a r t i c u l a ro u t l i e r - s e a r c h i n ga l g o - r i t h m i no u rf i r s ts c h e m e a ni n d i c a t o ri si n t r o d u c e df o re a c hd a t ap o i n tt ob o o k k e e pw h e t h e ri ti sa n o u t l i e r c o r r e s p o n d i n g l y , t h es e a r c h i n ga l g o r i t h mm u s ts c a nt h ew h o l ed a t as e ti ne a c hi t e r a t i o n t h i s d a t a - s c a na l g o r i t h mi se a s yt oi m p l e m e n t ，b u tt h ec o m p u t a t i o n a lb u r d e nb e c o m e ss e v e r ef o rl a r g ed a t a s e t o u rs e c o n ds c h e m es o l v e dt h ep r o b l e m ，w h e r e ，t os i g n i f yt h es e to f n o r m a lp o i n t s ，o n l yt h e i rn u m b e r a n dl a b e l sa r eu s e d a sar e s u l t ，t h es a m p l i n ga l g o r i t h mn e e d so n l yu p d a t et h es e to fn o r m a lp o i n t sb y a d d i n go rd e l e t i n gad a t ap o i n t t h ei m p l e m e n ti sn o te a s y , s i n c ev a r y d i m e n s i o n a ls a m p l i n ga l g o r i t h m i sn e e d e d w ea d o p tt h eb i r t h d e a t hm a r k o vc h a i nm o n t ec a r l of o rt h i st a s k n o t et h a tt h ed e t e r m i n a t i o n o ft h en u m b e ro ff a c t o r si sa l s oav a r y d i m e n s i o n a ls a m p l i n gp r o b l e m ，w ea l s op r o p o s eab i r t h d e a t h m a r k o vc h a i nm o n t ec a r l o ( b d m c m c ) a l g o r i t h mt oa s c e r t a i nt h en u m b e ro ff a c t o r s as y s t e m a t i cs i m u l a t i o ns t u d yi sd o n et oa s s e s st h ee f f i c i e n c yo f o u rm e t h o d s t h ee x p e r i m e n t a lr e s u i t sa r eq u i t es a t i s f a c t o r y t h eo u t l i e r sa n dt h em o d e la r ea l w a y sc o r r e c t l ys e l e c t e db yt h et w om e t h o d s ， t h eh y p e r p a r a r n e t e rv a l u e sh a v el i t t l ei m p a c to nt h eo u t p u t s a se x p e c t e d ，t h es e c o n dm e t h o du s e sf e w e r t i m ef o rl a r g ed a t as e t i no n ee x p e r i m e n t ，m o r et h a n3 0 o fc o m p u t a t i o nt i m ei sc u to f f , a sc o m p a r e d w i t ht h ef i r s tm e t h o d k e y w o r d s ：f a c t o ra n a l y s i sm o d e l ；m u l t i p l eo u t l i e r s ；m o d e ls e l e c t i o n ；b a y e s i a na n a l y s i s ；m a r k o vc h a i n m o n t ec a r l o v 目录 摘要 i v 第一章引言 1 1 1 因子分析模型简介 1 1 2 问题的背景及研究状况 1 1 3 本文的主要工作 3 第二章多异常点识别的数据扫描方法 5 2 1 贝叶斯框架 5 2 2 参数的先验选取与后验计算 6 2 3 抽样算法 9 2 3 1 因子个数的生死过程 9 2 3 2 多异常点的识别1 0 第三章多异常点识别的随机搜索方法 1 2 3 1 贝叶斯框架1 2 3 2 参数的先验选取与后验计算1 3 3 3 抽样算法1 5 3 3 1 正常点列的生死过程1 5 3 3 2 多异常点的识别。1 7 第四章模拟实验 1 8 4 1 实验一1 8 4 2 实验二。2 2 第五章结论及进一步的问题 2 4 致谢 2 5 参考文献 2 6 第一章引言 1 1 因子分析模型简介 因子分析模型假设p 维显示( 可观测) 变量x 6 卵由一些相关的因素组成，可以被降 维成低维的潜在( 不可观测) 变量z 卵，q p ，并且这些因素之间是互不相关的，g 称为 因子个数因子分析模型的形式如下： x = a z + p + 岛( 1 1 ) 其中a = ( a u ) 为实值p xq 维矩阵，叫做因子负荷阵，t l r p 为x 的均值，g r p 为 独立的扰动向量因子分析模型假设z 一心( o ，) ，一坼( o ，) ，其中= d i a g ( o l ，露) ， s 和z 为独立的从这里我们可以得知c o v z ) = a 并且当z 未知时x 的边际密度为 p ( 功= n p ( x ；a ，人人7 + ) 当z 已知时p ( 工l z ) = 名( j ；+ a z , e ) 1 2 问题的背景及研究状况 统计诊断足统计学的一个重要分支，而异常点检验又是统计诊断中重要内容统计 诊断就是对从实际问题中收集起来的数据提炼出来的模型以及由此出发所作的推断方法 合理性进行深入细致的分析，并通过一些诊断统汁量来检查数据，模型及推断方法中可 能存在的”毛病”，进而提出”治疗”方案异常点的定义多种多样，目前对异常点有以下 两种比较流行的看法；第一，把异常点看成那些与数据集的主体明显不协调、使得研究 者大感惊讶的数据点这时，异常点可解释为所假定的分布中的极端点，即落在分布的 单侧或双侧仃分位点以外的点，而通常口取很小的值第二，把异常点看成杂质点他与 数据集的主体不是来自同一分布，是在绝大多数来自某一共同分布的数据点中掺入的来 自另一分布的少量”杂质” 目前，对线性模型来说，其单个异常点识别的理论和方法都已经比较完善，可以用 数据删除模型或均值漂移模型和方差扩大模型对于多个异常点，问题变得很复杂我 们首先是确定异常点的个数，如果所设的个数与实际个数不符，则会出现所谓的掩盖或 l 第一章引言 j 2 问题的背景及研究状况 淹没其次即使是异常点个数k 确定下来了，但是究竟取胛个中哪k 个数据点进行检验也 不易确定如果考虑所有磷组合，则计算量非常大以往的做法，通常都结合其他的方 法( 如残差分析法) 作预选( 韦博成等， 1 9 9 1 ) ，大体确定异常点的个数，然后再进一步进 行检验这种方法比较粗糙，不精确随着b a y e s 统计的发展，在统计诊断中出现了异常 点识别在内的各种b a y e s 方法b o x 和t i a o 在1 9 6 8 年利用b a y e s 方法研究了异常点的识别 问题，这种方法的基本出发点就是求出每个( 或几个) 数据点服从的后验概率，若上述后 验概率很大，则可认为对应的点服从备择分布，这些点即为异常点但他方法的缺点是 必须给出备择分布在实际应用中备择分布往往足不知道的，所以这种方法有一定限制 性c h a l o n e r - b r a n t 方法( 韦博成，1 9 9 1 ) 不需要事先给出备择分布，有明确的直观意义 该方法主要任务就是对于给定的先验分布计算残差的后验分布。但是这种方法的缺点是 对于多个异常点的诊断需要较大的计算量此后，g u t t m a n 等人进一步讨论了均值漂移模 型进行异常点识别的b a y e s 方法( 韦博成等，1 9 9 1 ) 但是他们解决的一般都是单个异常点 识别问题，对多个异常点仍无法克服计算的复杂性和结果的粗糙性对于因子分析模型 来说，情况更加复杂由于因子分析模型本身的特点，因子的个数是未知的，首先要先 确定因子的个数，也就是先要进行模型选择，然后再进行异常点的识别 过去的十几年中，m a r k o v 链m o n t ec a r l o ( m c m c ) 方法已经成为统计推断，特别是贝 叶斯统计推断中的标准方法c a p p ea n dr o b e r t ( 2 0 0 3 ) 在利用m c m c 方法处理模型选择问 题时，参数维数的变化给一般的抽样策略带来了难以克服的困难，为此，g r e e n ( 1 9 9 5 ) 提 出了可逆跳跃m a r k o v 链m o n t ec a r l o ( r e v e r s i b l ej u m pm a r k o vc h a i nm o n t ec a r l o ，r j m c m c ) 方 法，并成功地应用在变点问题和聚类问题上；s t e p h e n s ( 2 0 0 0 ) 以混合模型为例提出了生死 m a r k o v 链m o n t ec a r l o ( b d m c m c ) 方法，这种方法通过模拟一个连续时间的随机点过程实 现了一种特殊情况的变维移动，也叫生死( b d ) 移动b d 移动只适用于一种特殊情况的变 维问题，即要求模型参数中与维数有关的部分可以看成空闻中的有限点集，其所含点的 个数随维数的变化而变化因子分析模型就是这种问题的典型例子，稍后文献f o k o u ea n d t i t t e r i n g t o n ( 2 0 0 0 ) 将生死m a r k o v 链m o n t ec a r l o 用于因子分析模型中来确定因子个数，也 就是用贝叶斯的方法解决了因子分析模型的模型选择问题，这种方法简单且容易理解， 在真实和人造数据上效果不错 2 第一章引言3 本文的主要工作 1 3 本文的主要工作 本文主要研究因子分析模型多异常点的识别问题，在我们的问题中因子个数和异常 点的个数都是未知的从而问题涉及到两个方面，一是因子分析模型中多异常点的识别 问题二是因子分析模型的模型选择问题，也就是要确定模型中的因子个数 我们采用贝叶斯框架，为了解决因子分析模型多异常点的识别问题，在对数据的处 理上，我们为每个数据点设置一个指示变量，用于说明该数据点是否为异常点在以前 的b a y e s 统计诊断文献中，一般是先通过其他途径确定哪几个点为异常点并假定正常点 和异常点来自同一个分布族，只是参数值有所不同而已；或者均值发生了漂移，或者方 差扩大了这种做法要求我们对于异常点的产生机制预先有充分的了解这在实际应用 中并不总是可能的，因为异常点的来源一般是不清楚的本文采取最保守的做法，假定 异常点来自整个空间上的均匀分布这相当于假定没有任何有关异常点的先验知识，这 样就更符合实际情况在异常点的个数未知的情况下，得出模型中因子个数并进行多异 常点识别，该方法简化了计算量并克服了结果的不精确性对于因子分析模型的模型选 择问题来说，它是一个变维抽样的问题，我们采用文献f o k o u ea n dt i t t e r i n g t o n ( 2 0 0 0 ) 中所 使用的方法，也就是使用生死m a r k o v 链m o n t ec a r l o ( b d m c m c ) 的方法确定因子个数 文中提出了两种多异常点的识别方法，在数据集不是很大的情况下，我们提出了多 异常点识别的数据扫描方法，我们为每个参数设置了共轭先验并设指示变量的先验分布 为伯努利分布，通过这些先验可以得到相应的后验分布，对得到的后验分布进行m o n t e c a r l o 抽样，就可以估计每个数据点是否为异常点的概率这样在不需要事先给定异常点 个数的情况下就能判断哪些点为异常点但是这种方法需要对每个数据点进行扫描，在 数据集比较大的情况下，数据扫描方法计算量非常大为了解决这个问题，在数据集比 较大时，我们提出了多异常点识别的随机搜索方法，这种方法的主要思路是模拟一个随 机点过程，只有正常点的个数和每个正常点的标号( 它们合在一起决定了正常点集) 是随 机变量，相应的抽样算法每次迭代只更新正常点集，所需的操作无非是增加一个数据点 或剔除一个数据点正常点集的更新是所谓的变维抽样问题，即在迭代过程中变量个数 3 第一章引言1 3 本文的主要工作 是可变的随机点过程的实现采用生死m a r k o v 链进行模拟这样就避免了对每个数据点 都进行扫描，可以加快程的运行速度 本文余下内容安排如下；第二章介绍了利用数据扫描方法进行多异常点的识别，我 们为每个数据点设置一个指示变量，用于说明该数据点是否为异常点我们采用整个空 间的均匀分布作为异常点的先验分布，通过给出的先验分布，我们得到了所有参数包括 指示变量的后验分布，采用生死m a r k o v 链m o n t ec a r l o 方法确定因子个数，数据点为异常 点的概率由后验分布的抽样中得到第三章介绍了利用随机搜索方法对多异常点进行识 别，这种方法在数据集比较大的情况下，可以提高程序的运行速度第四章足我们的实 验结果，我们进行了两组实验，实验一主要考查两种方法的有效性和两种方法对参数的 依赖性，实验二主要考查两种方法的收敛速度和在数据点比较多时第二种方法在时闻上 的优势最后，我们在第五章对本文的方法进行了总结，并提出了有待于进一步研究的 问题 4 第二章多异常点识别的数据扫描方法 2 1 贝叶斯框架 我们考虑因子分析模型的多异常点识别，因子分析模型的形式如下： x = a z + p + 岛 ( 2 1 ) 其中a = q 玎) 为实值p q 维矩阵，叫做因子负荷阵，r p 为x 的均值，g r p 为 独立的扰动向量因子分析模型假设z m ( o ，t q ) ，s n a o ，) ，其中= d i a g ( o 彳l ，嵋) ， s 和z 为独立的从这里我们可以得知c o v ( x z ) = 人并且当z 未知时x 的边际密度为 烈d = n p ( x ；n ，a 人7 + ) 当z 已知时p ( x l z ) = n a x ；v + 肥，) 假设原始数据点有疗个，分别为石妇，我们设隐藏变量6 = ( 6 ”，以) ，6 i 对应于x i ， 西= l 耋篓荛主喜熹： 由于异常点的分布是未知的，我们这里令异常点的分布为全空间上的均匀分布对 于隐藏变量5 i ，设其服从伯努利分布，即毋b ( 1 ，w i ) ，w i = p ( s i = 1 ) ，i = l ，疗，这里设每个 w i = ，即每个数据点为正常点和异常点的先验概率相同容易得出 模型的全参数似然函数为： 这里0 = 似，a z 1 p ( x i i z i ，西) 【 名( 而；+ 句。) 】函 ( 2 2 ) 以口；x 正z ) 几【帏( 而；+ a 勿，锄) 】西， j - l 5 ( 2 3 ) 其中 2 2 参数的先验选取与后验计算 对于x 的均值p 的先验取为正态分布p 一心( f ，d 参数t l 的后验概率密度为 p 0 i ) 颤p ；x 玩z ) p ( i z ) 几 n p ( x i ；l z + a z i ，) 】西础) 甑p 【_ 圭主双x i - t - a z i ) - 1 “一p 一蝴】e x p 【_ 兰。一咱】 。i = l 一 e x p 一j i 加7 坳一劫m 】j ， h 咏= 啦。+ r 1 ， 扛l 从而 】m ( 蛑1 m ，蚱1 ) 为了使方差不落到一个很小的范围内，对人使用超参数，定义列向量a ；为人的第厂 行的转置，令人；一n q ( o ，锄，= 1 ，p ，其中q 为对角矩阵q = d i a g ( t o l 2 ，嵋) 参数人；的 后验概率密度为 烈人：1 ) 芘z ( p ；x 反z ) p ( 人：) 丌n p ( x f ；g + a z d p ( h r ) e x p - 三喜甜( a z i ) z - i ( 心) 一2 ( 她髓_ 1 慵一删l c x p - j 1 ( k ) ，q - c x p - 三【( a ：) ，慨，k 一2 ( 人；) ， r 】 ， 6 弩 + 岫 一 聊西 。越 一 1 1 第二章多异常点识别的数据扫描方法2 2 参数的先验选取与后验计算 其中 m a r = q 一1 + 酊26 i z i z ，i 。 n a r = 0 7 2 6 f z i ( x i - - 2 ) r ， ，= l 俯一p ) ，为x i 一的第，个元素，从而【人 】一m ( 栋：a ，栋：) ，厂= 1 ，p 对于超参数q 一1 = d i a g ( t o i - 2 ，听2 ) ，对每个蛎2 ，d = 1 ，口使用g a m m a 先验呀2 o a ( g ，l i ) ，d = 1 ，q 参数蛎2 的后验概率密度为 其中 p p ( a j d 2 i ) 。ct i - ip ( 人：) p ( u 二2 ) ，= i 1 p o c t o d pe x p 一百1 蛎2 t z * r ( a ；) 】耐 蛎研2e x p l 一蛎2 厅l o c 嵋2 ( g + 籼e x p 一蛎2 ( 矗+ b d d ) ， b = 人：( 人；) ， 砌为矩阵b 的d 行躬硐的元素，从而【蟠2 i 】一g a ( g + 呈，h + 譬) 对于方差艺来说，一1 = d i a g ( t r 2 ，啄2 ) ，对每个町2 ，= 1 ，p ，使用独立的g a m m a 先验o - ；2 一g a ( a ，f ) ，= 1 ，p ，即p ( o - r 2 ) o r 2 仃- 1 ) e x p ( 一听2 ) 参数町2 的后验概率密度为 p ( o r 2 i ) o cz ( p ；置反z ) p ( 町2 ) o c 丌 坼( 而；p + 她) p p ( ( r 7 2 ) 庙i 酽唧i 艺：。( x i p 一心一p a z i ) o r 2 1 嘲一一) 万2 1 等+ a - i ) e x p 一2 ( 丁+ j 1 s ，) 】， 7 斟 州 其中 s = e 6 i b i 一恤一入z 濑x i p 一把汀， f = i 从而 0 7 2 1 】g a ( o t + 警，丁+ 争) ，r = 1 ，p 其中 由于z i n q ( o ，岛) ，i = 1 ，刀，潜在变量z 的条件后验概率密度为 p ( z i l ) 【 名( j ，；+ a z i ，) p ( 勿) 】西 优e x p 一扣西坳，一2 弼嘲i ， 必= i + a 7 a ， 心= 人( x i 一) ， 易知当6 i = 1 时，【z ，i 】一n q ( m ；1 心，蜂1 ) ，i = 1 ，刀 其中 前面我们设烈西) = 砖( 1 一w i ) 6 i ，下面计算6 i = 1 ，i = 1 ，刀的后验概率 p ( 6 i i ) z ( 9 ；五最z ) 从巧，) 丌【 名阮；+ a z i ，咖亿) 】6 7 烈6 ，) = w i , v p ( x , ；u + a z i ，咖锄) ， 匆的= 1 一w i ，i = 1 ，1 易知烈西= l | ) = b i l ，p ( 西= o l - - ) = 第f 个点为正常点的概率记为a i , 从而口f = 杀坛， j = l ，疗 8 占h m 6 斟磅 第二章多异常点识别的数据扫描方法 2 3 抽样算法 2 3 1 因子个数的生死过程 2 3 抽样算法 由于因子分析模型中因子个数是未知的，就要先确定因子个数，这里采用的是生死 m a r k o v 链m o n t ec a r l o 方法( b d m c m c ) 因子的个数实际上就是因子负荷阵人的列数，模 型中与维数q 有关的参数可以看成空间中的有限点集，并且人人7 + 关于a 的任意氍换 是不变的，模型的似然函数翰，a ，劲l - l n ( x f ；，人人7 + ) 】6 ，关于人的列的置换也是不 毋l 变的，因此人的列可以当做一个点过程令c = a 1 ，人2 i ，我们的目标是建立一个以 p ( q ，人，芑，为平稳分布的m a r k o v 链，平衡方程为： 白+ o d ( c ；v ) p ( cu 力= f l ( c ) b ( c ； ，搬c ) ， 其中p ( c u i y j ) 表示出生了一个点，即q + 1 个点时的概率密度，6 ( c ；y ) 和破g ；y ) 分别代表 出生和死亡密度函数，这里出生率卢( c ) = 卢为一个常数，可以根据实验进行选择对参数 q 使用参数为u 的截断p o s s i o n 分布 计算死亡率 此式等同于 删咖署c 醑训g 卸 舱y 南意 吠c ；y ) = 6 ( c ；y ) 等而p ( c v d 可以看出，成分a j ，j = 1 ，q 的死亡率为 删= 售而b ( c ；v j ) 掣锗 选择耶；y ) = p ( v y ) ，从而人的第列的死亡率白= g 掣，这里巧代表a 的第，列人一， z ( c ) 为当前点集的似然函数 9 第二章多异常点识别的数据扫描方洼 2 3 抽样算法 算法一：因子个数的生死过程 步骤一：选择出生率卢，令砂= 0 ，q = 9 ( 川； 步骤二；计算白= 譬掣，= 1 ，g ； 步骤三：计算“c ) = 宝白( c ) ； 口 j = - 步骤四：抽取s e 硝顶丽1 ) ，并令f ，= 0 + s ； 步骤五：若b 州碌筹) = 1 ， 令吁= 叮+ l ， 抽取a g n ( o ，d ， 令c = c u a g l ； 步骤六：若b p “砾祭b ) 1 ， 抽取= m n ( 瓣，鬻) ， 令c = c i a ，l ， 令q = g l ； 步骤七：返回步骤二，直到t l p 2 3 2 多异常点的识别 算法二：数据扩大算法假设当前m a r k o v 链上的值为伊n ，z f n ， 步骤一；抽取潜在变量的值： 抽取z ( 件1 ) 一烈z i 砂，x 尔o ) ； 步骤二：抽取参数的值； 抽取分件1 ) 一p ( o l z ( + n ，x ) ； 1 0 第二章多异常点识别的数据扫描方法2 3 抽样算法 步骤三：抽取伊7 + 1 ) p ( 6 1 x , z + ，o t 川) 主算法：假设当前的参数值为g ( f ) ，i a t o ，( n ，人( n ，弘) 步骤一：利用算法一更新q 的值，得到q ( h 1 ) 的值； 步骤二：在口( 川给定的情况下，利用算法二抽取p ( 川) ，曩川) ，a t 件n ，m ) 的值 这里的算法就是使用了生死过程对因子个数进行选择，而异常点则是直接由后验分 布中抽出的 第三章多异常点识别的随机搜索方法 3 1 贝叶斯框架 当数据集比较大的情况下，我们将正常点的样本看作一个随机点过程，这个点过程 的实现采用生死m a r k o v 链进行模拟这样就避免了在抽样过程中对每个数据点都进行扫 描，这会加快程序运行的速度现在考虑的模型为 j 0 = u 2 ：i + + 8 j r ， ( 3 1 ) 尹= j i ， ，k 疗，其中厅为原始数据点的个数，户为所选择的正常点的下标集，与 原模型相同一帏( o ，z ) ，= d i a g ( 一i ，吒) ，z n q ( o ，厶) 在这里设k 的先验为截断p o s s i o n 分布 丌( do c 砉，( 露功 定义s k = f ( ，l - 一，a ) l j l ， 互不相等l ，在此模型下，当钰已知时的分布为 烈劬) = n a x j , ；u + t 乜, j r ，劲， 易知模型的似然函数为 k z ( o ；x , z l k , f i b 丌 ( ；p + 魄，) 嘞；o ，岛) 】 记下标为 的数据点被选进的概率为办从而k 已知时的先验为 k 丌沪i 露) = 1 户s 女l 兀办， r = l 其中q = 岛t ，舀。n 笔i 以为规范化常数由于没有先验信息，我们取p r = ；，厂= 1 ，聆从 而，) 的先验可以简化为丌盼= 攀产 1 2 3 2 参数的先验选取与后验计算 上节已经给出了k 的先验，其余参数的先验与上一种方法先验的选取是一样的，下 面利用变维情况的模型计算参数的后验 参数p = o l 一，p p ) 的先验为p 皓，d ，础) e x p - l o - 考：) 7 k - 1 - 0 ，参数的后验 概率密度为 础i ) z ( o ；x , z l k ，归0 ) 其中 虻 h n ( x j , ；p + a z j r ，x ) n ( z j r ( o ，岛) ) 】l 础) r = l e x p 一互1 阻7 ( 心扣一劫7 m 】 毛= 后一+ x 一1 ， 从而 】一m 蜂1 雌，蛑1 ) 与前面相同对a 使用超参数，定义列向量八：，它为人的第c 行的转置，令 ：一( o ，q ) ， c = i ，p ，其中q 为对角矩阵q = d i a g ( t o ，嵋) 参数k 的后验概率密度为 烈a 。ii ) 芘以日；x z f 疋硒) 仄八：) o c 【兀n a x j , ；u + a z j , ) m a 。f ) e x p 【一三砉( 吼一吲1 一心) e x p - 2 ( 订1 k 】 e x 卅三喜t t 心髓1 c 嘞，叫心肛一c - p ) e x p - 2 c k m t - i k ， e x p l 一三 ( a 砾。人：- 2 ( 人j ， - 1 3 f 5 + 胁 一 壤 。一 一 l i 坛 其中 七 眠= q 一+ 虻2 勺，毛， 厂= l 七 帆= 虻2 z j , ( x j , 一p k r = i 从而【k 1 卜m ( 唆帆，吣- 1 ) ，c = 1 ，p 对于超参数q 一1 = d i a g ( w 2 ，嵋2 ) ，对每个蛎2 ，d = 1 ，q 使用g a m m a 先验蛎2 一 g a ( g , h ) ，d = 1 ，q 蛎2 的后验分布跟前面类似【二2 1 】一c , a ( g + 譬，h + 争) ，其中b = p ；( a ，i ) ， r - - l 一1 = d i a g ( 盯t 2 ，0 7 ) ，对于每个町2 ，c = 1 ，p 使用独立的g a m m a 先验町2 一 g 口( 仃，下) ，c = 1 ，p ，即烈2 ) o c 2 1 ) e x p ( 一晖2 ) 町2 的后验慨率密度为 其中 从町2 | ) z ( 0 ；x , z l k ，f * b p ( o - ：2 ) k 【兀坼( 啊；p + 崦) 】p ( 町2 ) r - - i 刚! e x p - 三e ，l 。( “一一吩( 一一心版2 ( 口- 1 ) e x p ( - 穰) 2 ( 口+ l - 1 ) e x p 一虻2 下+ 抄1 】l s = 七 q j r 一 l a z j r x x j r p a z r ) 1 ， 从而k 2 i 卜g a ( a ：+ ，丁+ 争) ，c = 1 ，p 1 4 一 第三章多异常点识别的随机搜索方法 3 3 抽样算法 为 计算潜在变量z 的条件后验，锄一m ( o ，t q ) ，= 1 ，k 潜在变量z 的后验概率密度 其中 p ( z y r l ) z ( o ；x , z i l ) 七 l - 1 w p ( x j a + a z j ，z ) n q ( z j ，；0 ，厶) 】 r - - l 铙n p b l 3 p 七把j r ，z ) n q ( z j , ；0 ，l e x p f - 三略一】j 必= ，+ 人一1 人， j v 矗= 人一1 ( 一) 从而i 】一( 屹1 见，吲) ，= 1 ，k 3 3 1 正常点列的生死过程 3 3 抽样算法 在随机搜索方法中，因子个数还是要由生死过程来确定，正常数据点集也由生死过 程来确定，而不同于前面的由抽样确定因子个数的选择前面已经讨论过，下面讨论一 下正常数据点集选择的生死过程首先计算一下k 与尹的联合后验 烈t i ) o cz x z i 屯产) 7 彤i 七如( d 【丌坼( 纠+ 慨】警和驯 o c e x p 【一吾主一p 一心) 譬1 一一心) 冈一l 一幼七乩 1 5 第三章多异常点识别的随机搜索方法3 3 抽样算法 假设当前正常点的f 标集，叼= u i ，一，a j ，k n ，我们的目的是要建立一个以烈t ， i ) 为平稳分布的m a r k o v 链p r e s t o n ( 1 9 7 6 ) 证明要使得这样构造的生死过程以q 上的概率测 度为平稳分布，只需对任何的k l ，f 辄，ggm + l x ) v ( 纠= 厶+ 。舻”；脚“t ( 劬， ( 3 2 ) 上6 加“咖) = 厶雕蟛b ；g m ， ( 3 3 ) 这里的平稳分布触即为此处的p ( k ，| ) ，i z k + i 即为p ( k + l ，严1 1 ) 选择正常点的下标 是一个离散的情形，在第一个式子中我们令f 为m 中的一点，设y m + i 中每个成分的 死亡率是相同的为鬲1 ，从而6 = 1 ，带入第一个式子，得到 m = 高岛驴吒1 c 一吲c 一删， 带入第二个式中，得到 卢( 衅k m ，) = 编e x p 卜三( 。一一i ) ，_ l ( ，一一魄+ i ) 】， 由以上两式可以求得 如加卜繁鬻鲁舞舞筹， 矽o ； + i ) 即为第七+ 1 个正常点下标的出生分布，这里五+ i 隹工 算法四；正常点列的生死过程 步骤一：选择烈c ) = 1 ，令0 = 0 ，g = g ( 卜1 ； 步骤二：计算邸)