（模式识别与智能系统专业论文）oneclass问题研究及应用.pdf

o n e c l a s s 问题研究及应用：摘要 摘要 o n e c l a s s 问题包括o n ec l a s s 描述问题和o r l e c l a s s 分类问题，给定组没 有标签的样本集，前者指如何描述它包含的内在信息( 与异常信息或噪音信息 相对应) ，而后者指如果把此样本集作为目标类，如何与其它所有无关类( 当然 也包括o u t l i e r s ) 分类的问题。o n e c l a s s 问题的研究无论是在模式识别还是在 信息处理领域都具有重要意义。 沦文的主要内容包括： ( 1 ) 概述分析t o n e c l a s s 问题的研究内容及研究意义，并首次把o n e c l a s s 问题分为o n e c l a s s 描述问题和o n e c l a s s 分类问题，并给m 了这两种问题的潜 在应用。 ( 2 ) 提出了一种解决o n ec l a s s 描述问题的模型：基于方差的信息分解模型 ( v a r l a n c e b a s e di n f o r m a t i o nd e c o m p o s i n gm o d e l ，v i d m ) ，并为此模型引 入了基于主成分分析的算法和基于主曲线的算法。 ( 3 ) 用股票异常收益检测和说话人识别的特征提取两个实验验证了v i d m 模 型及其算法的有效性。 ( 4 ) 用s v m 方法研究o n e c l a s s 分类和o u t l i e f 检测问题。在将o n ec l a s s 分类 问题理解为一种函数估计问题的基础卜，首次定义了”一o n e c l a s s $ u q o u t l i e r 问题的泛化错误，进而定义了线性可分性和边缘，得到了求解o h ec l a s s 问题的 最大边缘、软边缘和v 软边缘算法。 ( 5 ) 首次在o n e c l a s s 分类问题中引入半监督学习的思想，提mr 一种半监 督的o n e c 1 a s s 分类算法( s e m ivs v m ) ，此方法在易趣扪卖网站t ，的商品分 类上取得了很好的效果。 关键字：o n e c l a s s 问题、非监督学习、半监督学习、信息描述、分类、统计7 习算法、股票市场、说话人识别、w e b t e x tm i n i n g o n e c l a s sp r o b l e ms t u d ya n da p p l i c a t i o na b s t r a c t a b s t r a c t o n e c l a s sp r o b l e mi n c l u d e so n e - c l a s sd e s c r i p t i o na n do n e - d a s sc l a s s i f i c a t i o ng i v e na d a t a s e tw i t h o u tl a b e l ，t h ef o r m e rm e a n $ h o wt od e s c r i b et h ei n t r i n s i ci n f o r m a t i o n ( o p p o s i t et o a b n o r m a li n f o r m a t i o no rn o i s ei n f o r m a t i o n ) o ft h ed a t a s e t ，a n dt h el a t t e rm e a n st h a ti fw e t h o u g h tt h ed a t ai nt h ed a t a s e ta st a r g e ts a m p l e s ，t h e nh o wt od i v i d et h e mw i t ha l lt h eo u t l y i n g s a m p t e s ( i n c l u d e so u t l i e r s ) i ti ss i g n i f i c a n tt os t u d yo n e c l a s sp r o b l e mn o to n l y t op a t t e r n r e c o g n i t i o nb u ta l s ot oi n f o r m a t i o ns c i e n c e t h em a i n c o n t e n t si n v o l v e di nt h et h e s i sa r et h ef o l l o w i n g ： ( 1 ) f i r s t l y w e g i v e t h ec o n t e n t s a n ds i g n i f i c a n c ea b o u t t h er e s e a r c ho f p i l e c l a s s p r o b l e m ， a n dt h e nd i v i d et h eo n e - c l a s sp r o b l e mi n t oo n e c l a s sd e s c r i p t i o na n do n e c l a s sc l a s s i f i c a t i n n w es h o wt h ep o m n t i a la p p l i c a t i o n so f t h eo r e c l a s sp r o b l e ma tl a s t f 2 ) w ep r e s e n tam o d e lt os o l v et h ep r o b l e mo fo n e c l a s sd e s c r i p t i o n ：v a r i a n c e b a s e d i n f o r m a t i o nd e c o m p o s i n gm o d e l ( v i d m ) ，m i di n t r o d u c ea l g o r i t h m sb a s e do nt h ep r i n c i p a l c o m p o n e n ta n a l y s i sa n dt h ep r i n c i p a lc u r v e st ot h ev i d m ( 3 ) m a k i n ge x p e r i m e n t so na b n o r m a lr e t u r n sd e t e c t i o na n df e a t u r ee , t r a c t i o no fs p e a k e r r e c o g n i t i o nt os h o wt h ep r a c t i c a l i t yo f t h ev i d ma n d , i t sa l g o r i t h m s ( 4 ) o n e c l a s sc l a s s i f i c a t i o na n do u t l i e rp r o b l e m sa r ei n v e s t i g a t e db yu s i n gt h et d e ao f s v mb a s e do nr e g a r d i n gao n e c l a s sp r o b l e ma st h eo n et oe s t i m a t eaf u n c t i o n ，t h e g e n e r a i i g a t i o ne t x o ri sd e f i n e d f o rt h e f s tt i m et h el i n e a rs e p a f a b l 【l c y m a r g i na n do p t i m a l l i n e a rc l a s s i f i e ra r et h e nd e f i n e da n dt h er e g u l a rs v mi sr e f o r m u l m e di n t ot h a t f o ro n e c l a s s p r o b l e m s ( 5 ) t h r o u g hi n t e g r a t i n gt h ei d e a o fs e m i - s u p e r v i s e dl e a r n i n gi n t ot h ep r o b l e mo f e r i e c l a s sc l a s s i f i c a t i o n ，ak i n d o fs e m i - o n e c l a s sc l a s s i f i c a t i o na l g o n t b mi sp r e s e n t e d ( s e m i - v s v m ) t h i sa l g o r i t h mi sv e r i f i e db yt h ee x p e r i m e n to f m e r c h a n d i s ec l a s s i f i c a t i o ni n a u c t i o nw e b s i f eo f e a c h n e t ”( w v a v e a c h n e t c o m ) k e y w o r d s ：o n e 、c l a s sp r o b l e m ，u n s u p e r v i s e dl e a r n i n g ，s e m i s u p e r v i s e 6 l e a r n i n g ， i n f o r m a t i o nd e s c r i p t i o n ，c l a s s i f i c a t t o n ，s t a t i s t i c a ll e a r n i n ga l g o r i t h m ，s t o c km a r k e t ， s p e a k e rr e c o g n i t i o n ，w e b t e x tm i n i n g 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及 取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外 论文中不包含其他人已经发表或撰写过的研究成果。与我一同工作的同 志对本研究所做的任何贡献均已在论文中作了明确地说明并表示了谢 意。 签名 目期 一2 受旦= 一区! 丛一 关于论文使用授权的说明 本人完全了解中国科学院自动化研究所有关保留、使j i _ j 学位论文的 规定，即：中国科学院自动化研究所有权保留送交论文的复印件，允许 论文被查阅和借阅：可以公布论文的令部或部分内容，可以采用影e 、 缩印或其他复制手段保存论文。 社新虢例望灶儿 第一章概述：o n e - c l a s s 问题研究及应用 第一章概述：o n e clb s $ 问题研究及应用 本文的目标是存非监督学习的背景下讨论o r e cr a s s 问题( o n e c 【r s s p r o b l e m ) 的学习方法及算法。奉文认为o r e - c l a s s 问题是指给定一组没有标签 的样本集，如t i 描述它包含的内在信息( 与异常信息或噪音信息相对应) 或把 此样本集内的样本作为目标类与其它所有无关类样本( 当然也包括o u t li e f s ) 分类的阚题。根据这蕊项任务的盆标不斟，可把前者称为基于描述的e c l a s s 问题( 或称为o r e c 1 a s s 描述问题) ，把后者称为基于分类的o n e c l a s s 问题( 或 称为o r ec l a s s 分类问题) 。虽然这两种o n e c l a s s 问题的目标不同，但它们的 本质却是相同的即都可以理奄5 1 为种非监督下的函数估计的问题。为便于理 解，我们先从讨论非监督学习开始，尔后给出o n e - c l a s s 问题的具体形式及其 应用领域。 1 ，1 本文的背景：非监督学习 机器学习可分为监督学习和非监督学习 m i t c h e l l l 9 9 7 。监督学习就是寻 找映射f ：r 。呻j r ，把输入的维随机向量映射到随机变量l ，上，目标是 f ( x ) 和】，之间的筹异尽量小。如果r 是离散的那么此时监督学习就是个分 类问题。为衡量f ( x ) 和r 之间的差异，可以定义非负的损失方程q ( l 厂( ) ，j ，) ， 那么此时监督学习的目标就是求解一最小化期望损失的映射f k e g l l 9 9 9 a ，即 f = a r g r a i n 研q ( j ( x ) ，r ) 】 ( 1 一i ) r 实际问题下，x t ；f 1 ，的联合分布是未知的，代之的是从和r 的联合分布 下独立同分布抽得的样本集以= ( ，i ) ，( x 。，) ) c r 4 r ，其中h 为样本个 数。这种情况下，我们无法解析求得映射，代之的策略是在样本集磊的意义 f 求解使期望损大最小的f a x ) = f ( x ，z 。) ，如果我们能明确的定义一个评测函 数米评价 对丁- 独立测试集z = ( ( j ，i4 ) ，( x 。，r 二) ) c r 。x r ( m 为测试样本 个数) 的性能，那么这个学习问题就不是病态的。一般情况下，。j 定义这个评 测函数为对测试样本集z ：的测试错误率 k e g t l 9 9 9 a ，即损失函数 i q ( j ) = 考艺g ( - 厂( x ，) ，r ) ( 1 2 ) o n ec l a s s 问题研究及应用 然而，在非监督学习中，并没有一个指导学习的监督信息y m i t c h e l l l 9 9 7 。 在这种情况下，我们可以把非监督学习理解为一个对的信息估计的问题，即 求解映射f ：r “寸，使f ( x ) 麓尽可能好的估汁x 的信息，这是非监督学习 的一个目标，可称之为信息保持性。当然，如果对，( x ) 不做任何限制的话，问 题的解将是平凡的，因为对x 的最好估计就是x 本身。因此，对f ( x ) 施加合理 的限制条件是非监督学习的另一个目标，即采用尽可能短的信息描述长度，也 就是说尽可能采用简单的，( 并) 形式来估计x 。由于信息保持性和信息描述长度 之问存在矛盾，相对较长的信息描述长度，较短描述长度的信息描述是以损失 信息保持性为代价的 k 6 9 1 1 9 9 9 a ，因此在何处折衷这两个矛盾要看求解问题的 需要，而一般导致非监督学习问题病态性的原因是没有明确的定义一个判断折 衷好坏的标准。例如，我们可以得到两个解，：和厶，且 比厂2 有更好的信息保 持性能，而比，：具有更短的信息描述长度，在这种情况下，避免病态问题产 生的关键就是定义一个清晰的评测标准，此标准能评测疋和f 在信息保持性和 信息描述长度两个目标下的总体性能。 图卜l 和图卜2 可以帮助我们更清楚的理解非监督学习病态性产生的本质。 ( a )( b ) 图卜l 病态的非监督学习问题l ：哪一条光滑曲线对数据分布描述的更好，其中 ( a ) 益线形式简单但信息保持性差；( b ) 曲线形式复杂但信息保持性好。 在图卜1 中，( a ) ( b ) 两幅图的目的是判定哪一条光滑曲线对数据分布描 述的更好。根据匕述对非监督学习的讨论，图卜l 的任务就是通过，把、f 面中 的点映射到曲线上。在映射过程中，一个目标就是使通过数据集的曲线尽量的 第一章概述：o n ec l a s s 问题研究及应用 靠近各个数据点。显而易见，如果这是唯一的目标，那么问题的最终解将是平 凡的，即得到一条遍历所有点的曲线。凶此，我们需要加入限制曲线形式的规 则条件，如限制曲线的光滑程度，具体的可以是一个限制曲线长度的约束。如 果这个约束是明确的，例如曲线的k 度不超过某个给定的闽值，而且使数据集 到曲线上投影的平均距离最小化的曲线是存在的，则求解映射曲线，的问题就 不是病态的。但是如果在实际问题中我们在很难明确给定曲线长度约束的清 况下，而转向用种很模糊的方式来表达非蕊督学习的目标的话，则求解映射 曲线厂的问题很可能就是病态的，如“在使曲线长度尽量短的情况下，求解一 条能尽量靠近数据集中各个数据点的曲线”的模糊目标就将令我们无法判断那 条映射曲线 和厶更好。因此，在图卜1 的病态问题中，就明确需要一个评测 条件来评价( a ) ( b ) 中的结果，而这个评测条件显然得根据待求解问题的需要 而确定。 ( a )( b ) 图1 2 病态的 f 监督学习闯题2 ：哪一个有界覆盖区域对数据分布描述的更好，其 ( a ) 函数形式简单但描述精确性差：( b ) 函数形式复杂但描述精确性好。 在图1 2t | j ，( a ) ( b ) 两幅图的目的是判定哪一个有界覆盖区域对数据分 布描述的更好。与图1 一l ( a ) ( b ) 中的问题类似，同样需要根据领域问题的需 璺确定一个评测函数来评价哪个有界覆盖区域能更好的描述数据的分布； f 节我们将具体给出o 1 e - c 1 e t g s 问题的定义，性质及应用。但在此之前 进行卜述非监督学习讨论的日的是：，l 述讨论决定了我们要解决的o n ec l a s s 问题的哲学背景体系。既然般意义下的非监督学习问题是病态的，试蚓寻找 o n ec l a s s f u 题研究及应用 一个“包打天下”的算法是不现实的，因此，在下面讨论o n e c l a s s 问题时， 我们将始终坚持的一点是：任何一个o n e c l a s s 问题的非监督算法必须包岔一 参数集合，该集合中的参数能被用来调整算法应用到不同领域的问题中：从工 程的角度讲，集合中参数个数又需尽量少，而且参数的含义应尽量明确，即对 用户而言尽量是透明的。 1 。2 本文的工作：基于非监督学习的o n o c i a s s 问题 根据前一节对非监督学习的讨论，o n e c l a s s 问题是指给定一组没有标签的 样本集，如何描述它包含的内在信息( 如图卜1 ) 或把此样本集中的样本作为目 标类与其它所有无关类样奉分类( 如图l 一2 ) 的问题。根据这两项任务的目标不 同，可把前者称为基于描述的o n e c l a s s 问题( 或称为o n e c l a s s 描述问题) ， 把后者称为基于分类的o n e c l a s s 问题( 或称为0 1 3 e c l a s s 分类问题) 。虽然这 两种o n e - c l a s s 问题的目标不同，但它们的本质却是相同的，即都可以理解为 一种非监督下的函数估计的问题，前者估计一函数描述样本集的信息，后者估 计一函数描述样本集的分布。f 面给出o n e c l a s s 问题的规范表达形式。 1 2 10 n e - o f a s s 问题的形式化表示 令u 为o n e c l a s s 问题的样本空间，为函数集 i 厂：u 一尺”，称的值域为由f 生成的流形m ，即： m ，= ，( u ) = 厂( z ) ：x u ) 存fq j 全体函数所乍成的所有流形的集合定义为m ： 对于每个，f ( 13 ) m = m ，：f f ) ( 1 1 ) x u 通过，映射到流形m ，中的损失，可用某种距离a ( m ，x ) 表示，其中 m m 。因此流形m 的距离函数( 损失函数) 可定义为随机向量x u 和m 之间的期望距离，即： a ( m ) = 研a ( x ，m ) ( 1 5 ) 因此，o n e c l a s s 问题的基本目标就是求解一流形m ，要求是) 尽量小， 而m 的复杂度要比【，的复杂度低，其实这两项要求就是前节讨论的信息保持性 和信息描述长度两个目标的具体表达。 第一章概述：o n ec l a s s 问题研究及应用 实际问题【f 1 ，一般假设函数集f 和流形集合m 相对于x 的分布是独立的。 遵循奥克姆剃刀( o c c a mr a z o r v a p n i k l 9 9 8 ) 原则，我们假设任f 及其 它对应的流彤m ，m 都可以用简单的函数形式表达。如果再假设m 中的各个流 形具有相同的内在维数，那么o r e c l a s s 问题的目标就是在盯 最小化a ( m ) ， 即求解： = a r gr f f m e a ( x ，吖) 】- ( 卜6 ) 然而，通常x 的分布是未知的，代之的是从x 分布下独立同分布抽得的 o n e c l a s s 样本集厶= x ，z ：，以 cr 。，其中 为样本个数。这种情况下， 问题可转化为在样本集以的意义下求解使距离函数( 15 ) 最小化的 ，。( ) = f i x ，以) 。另外，在样本集磊的意义下，通常我们用如下经验距离函数 ( 经验损失函数) 代替距离函数( 卜5 ) ： 。( = ( x ) ( l i = l 受结构风险最小化 v a p n i k l 9 9 8 和正则化 d e v r o y e l 9 9 6 思想启发，在算法 实现中，一般引入一正则化项到经验距离函数( 卜7 ) 中来代替原来的最小化目 标函数，即： g 。( 坍) = 。( 卅) + a p ( 卅) ， ( 卜8 ) 其中，p ( m ) 称为惩罚或正则化项它用来惩罚流形的复杂度：j 称为正则化冈 子，它用来控制p ( m ) 的惩罚程度。 在给定了l 述o n ec l a s s 问题的形式化表达之后，下面就可以给出基于描述 o n e c l a s sn 日题和基于分类的o n e c l a s s 问题的具体形式。 存讨论之前，先给定j l 个必要的条件。 如上述，u 为o n e c l a s s 问题的样本空间。令a 是一参数集合，前面在讨 论非监督学习的背景时已提及，一般意义下的非监督学习问题是病态的，试图 寻找个“包打天下”的算法是不现实的，因此给定a 的目的是，期望通过调 整其中的参数来调整算法应用到不同领域的问题中，从另一角度上说，该集合 中的参数也即是用来调整算法在信息保持性和信息描述长度之间进行折衷：一 般意义卜，a 集合中的参数含义是抽象的，其含义是在实现具体算法的过程中 明确的。我们将在后续章1 ，中的具体问题中，表明设置a 的必要性。 o n e c l a s s 问题研究及应用 1 2 2 基于描述的o v l e - c i a s s 问题 定义1 - 1 设r u ( c a r d ( t ) = n ) 是与u 独立同分布的一组样本子集， x = ( x 1 , j ：，- ) t 如果存在t 上的一个函数，f 使 肖= f ( x ，且) + ， ( 卜9 ) 其中f ( x ，丑) = u ( x ，丑) ，( 如，五) ，f ( x j ，五) ) ，2 e a ，2 _ f ( x ，z ) 是x 的内在信 息部分，f 是x 的残余部分，则称x 是可分解的。 在定义卜1 下，基于描述的加e c l a s s 问题指的就足如何从已知数据集，中 求解厂来描述7 1 的内在信息( 如图卜1 ) 。 令八瓦五) 是对数据集f 内在信息的描述，根据损失函数( ! 一5 ) ，可以定义 基于描述的o n e c l a s s 问题意义下的损失函数为： a ( f ) = “t 一，( t , 2 ) 旷 ( 卜l o ) 因此，基于描述的o n e c l a s s 问题目标就是由a 控制，的复杂度的前提_ f ， 最小化损失函数| it f ( t ，五) 1 1 2 。 我们将在第二章详细讨论基于描述的o n ec l a s s 问题的具体内容。 1 2 3 基于分类的o v l e - c i a s s 问题 定义1 - 2 设r u ( c a r d ( t ) = ) 是与独立同分布的一组样本子集， x = ( x ，屯) t 如果存在t 上的一个函数，f 使 f ( s ， ) ”， ( 1 一1 1 ) 其中l ，( x ，五) r ，五a ，则称r 是可覆盖的。 在定义卜2 下，如果把r 称为目标类样本集合，则基于分类的o n e c l a s s 问题是指求得一个覆盖h 标类样本的区域，此区域能把h 标类样本与所有其它 类样本分开( 如图卜2 ) 。具体的o i gc l a s s 分类期望解决的是指如f 特点的问 题：目标样本集合容易给出，且容易定义，而负样本集合不易给出，经常出现 例外，如医疗数据中正常人的数据很容易获得，而患者数据却很难采样：另外 如股票交易数据中，异常交易数据相对于正常交易数据两言也是非常难以采样 的。对fo l l e c a s s 分类问题，我们一。般可作如f 理解：根据目标类样本集台r ， 第一章概述：o n e - c l a s s 问题研究及应用 构造一个能描述样本密度分布的二值模型。如果某一样本处于较大密度的区域 之内则认为它是目标类样本，否则就认为它是其它类样本。解决这一问题的一 个自然的想法就是利用目标类样本估计分布。但根据v a p n i k 在统计学习理论中 的原则 v a p n i k l 9 9 8 在解决一个给定问题时要设法避免把解决一个更一般 的问题作为其中间步骤( 本文以后把这条原则称为“v a p n i k 原则”) ，因此，在 此我们并不以真正估计分布为出发点。 根据损失函数( i 一5 ) ，可以定义基于分类的o n e c l a s s 问题意义下的损失 函数。 定义1 - 3 ( 损失函数和泛化错误) 对于厂f ，定义 w ( 矾旷钾髦净”， 1 2 ) 称三为基于分类的o n e c l a s s 问题的损失函数。定义 r ，7 ) = i l ( f ( x ，五) ，q ) p ( x ) c l v ( 卜1 3 ) 为基于分类的o n e ，c l a s s 问题的泛化错误，其中p ( x ) 为的分布密度函数。 注意：在不考虑密度加权的情况下，这里的泛化错误可以粗略地解释为位 于事先指定区域f ( x ，五) q 之外的服从分布e ( x ) 点的个数。在此情况下，基于 分类的o n ec l a s s 问题的目标就是由a 控制厂的复杂度的前提下，使尽量多的 服从分布_ p ( x ) 的点位于事先指定区域，( ，五) 叩之中。 我们将在第四章详细讨论基于分类的o h e - - c l a s s 闷题的具体内容。 随着信息量的不断激增，给基丁分类的o d e c l a s s 问题带来了一个普遍的 困难：在给定的大量样本中，南于人力、财力或其它原因，我们只能得到其中 很小一部分目标类样本，而任务是从大量剩余的给定样本巾检出目标类的样本， 如从给定的大量w e b 网页中榆山目标类文档，从大量的分子生物数据中检出功 能蛋白等。用这小部分【j 标类样本训练覆盖区域时，容易出现模型的过学习现 象 s a r l e l 9 9 5 ，这种现象对于具有高维特性的任务来说会更普遍，如t e x t m i n i n g 。针对此问题，我们计划引入半监督学习( s e m i s u p e r v is e d l e a r n i n g s e e g e r 2 0 0 0 ) 的思想到o n ec l a s s 分类问题中。半监督学习的思想 是：同时给定训练样本和测试样奉，通过 八测试样本的信息到分类器的训练 中，来提高分类器的泛化能力 b l u m l 9 9 8 j o a c h i m s l 9 9 9 g h a h r a m a n i l 9 9 4 j o n ec l a s s 问题研究及应用 h a s t t e l 9 9 6 。本文将在第五章提出一种半监督的o n e c l a s s 分类问题学爿方 法，其思想是：在保证己知日标类样本最好覆盖的基础上，使尽量少的测试样 本落在覆盖边界两侧的邻域内。 1 2 4o n e - c t a s s 问题的应用 上述讨论的两种o n e c l a s s 问题可应用在各种不同领域的问题中。 ( 【) 基于描述的o n e c t a s s6 日趣 特征提取( f e a t u r ee x t r a c t i o n ) ；特征提取是模式识别前处理工作的 重要组成部分 d e v i j v e r l 9 8 2 d e v r o y e l 9 9 6 ，其目标就是用尽量少的特征尽量 多豹僳持石的信息，以f 爱降低系统的输入维数。提高系统的训练及识别过程。 有损压缩( l o s s yd a t ac o m p r e s s i o n ) ：在信息理沦中，为提高数据传 输及存储的效率，对爿进行压缩是常用的方法 g e r s h 0 1 9 9 2 。在损失率尽量小 的前提下，如何提高对x 的压缩率是这类任务的目标。 去除嗓音( n ols er e d u cc i o a j ：在信号处理中 v a n t 9 6 8 ，通常假设 是由某个潜在模型产生的，即 其中是流形m 中的一随机向量e 是独立的多维随机嗓音， 务就是在样本集下求解矿，这和( 卜9 ) 式的任务是一致的。 ( 1 一】4 ) 去除噪音的任 异常信息检测( a b n o r m a li n f o r m a t i o nd e t e c t i o f f ) ：如果把( 卜1 4 ) 孛的著作异常售息的话，那么基尹描述的o n e e l a s s 问题可以应用到具裳信息 检测的任务 l ，如股票市场巾异常收益( 价格) 检测 h o n g w e i 2 0 0 4 ，网络中的 非法入侵行为检测，信用卡使用的欺诈行为检测，交通数据异常情况检j 贝4 等。 潜在变数模型( l a t e n tv a t i a b l em o d e ls ) ；假设高维空间中的z 足受 低雏空间中的结构控制的 m a c k a y l 9 9 5 b i s h o a t 9 9 6 e v e r i tc 1 9 8 4 。这是 ( 卜1 4 ) 式在附加噪音近似为零时的特例。特别是当流形m 为二维时，_ j 渺代 表x 的信息可作为一种非常有效的可视化手段 b i s h o p l 9 9 8 k r u s k a l l 9 7 8 s a m m o n l 9 6 9 。 ( 2 ) 基于分类的o n e c l a s s 问题 o n e c l a s s 聚类分析( e lu s t e r i n g ) ；此处的o f l e c l a s s 聚类分析不同于 第一章概述：o n e - c l a s s 问题研究及应用 传统的聚类分析，而是指样本分布严章不均衡的问题，如医疗数锯r l ，患者数据 相对于正常人数据严重短少的情况 【a u y ik k a a 2 0 0 0 ，对于解决此类问题，可 以从样本丰富的那类数据聚类入手，用此类数据对空问进行聚类划分，划分之 外的空间可认为是短缺类的样本分布的区域。 o u t l i e r 检测( o u t l i e rd e t e c t i o r r i t t e r l 9 9 7 ) 或n o v e l t y 检测 ( n o v e l t yd e t e c t i o n b i s h o p l 9 9 4 ) ：根据目标类样本集台7 1 ，构造一个能描 述样本密度分布的二值模型。如果某一样本处于较大密度的区域之内则认为它 为目标类样本，否则就认为它是o ul li e r 或n o v e lt y 。o u t li e r 检测妞股票市场中 异常个股检测 q i n 9 2 0 0 4 ，网络中的非法入侵行为检测，信用卡使用的欺诈行 为检测等。n o v e l t y 检测的应用如机器运行中的异常情况的监测 t a x l 9 9 9 b y p m a l 9 9 9 a y p m a l 9 9 9 b 等。 目标类与其它类的分类问题：这类问题指的是我们只关心目标类的内 容，而对于其它类是什么并不在我们考虑的范围之内。这种情况下，我们只需 针对目标类样本集合7 ，构造- - 一个能描述样本分布的模型，虫果某一样本处于模 型描述的区域之内，则认为它是目标类样本，否则就认为它是无关类样本。 w e b t e x t 挖掘中的许多问题都属于这一范畴，如从众多新闻文本中检出属于体 育新闻类的样木，或在拍卖网站中的众多交易商品中检出计算机类商品，甚至 从各类网页中检出天气预报类的网页等。另外如分子生物数据中功能蛋白的 检出，图像中的目标识剐等。 1 3 本文的框架及内容安排 本文主要分为两大部分：基丁 描述的o n e c l a s s 问题和基于分类的 o n e c l a s s 问题，图13 是本文研究的总体内容及章节安排。 除第。章概述了本文要研究的o n ec l a s sm 题之外，其余各章的主要内容 安排如下： 第二章：提出了一种解决o n e c l a s s 描述删题的模型：基于方差的信息分解 模型( v a r i a n c e b a s e d n f o r m a t i o nd e c o m p o s i n gm o d e l ，v i d m ) ，此模型把 数据集的信息分解为内在信息和异常( 噪音) 信息两部分，如( i 9 ) 式。最后， 为v d m 模型引入了基于主成分分析的算法( p r i t i c i p a lc o m p o n e n ta n a l y s i s b a s e da 1 9 0 r i t h m ，p c a a ) 和拱于丰粕线的c p e a 算法( c o n t e x t u a lp r i n c i p a l c u r v e sa 1 9 0 r i t h m ) 。 9 o n e c l a s s 问题研究反应用 图卜3 本文研究的总体内容及章节安排 第三章：给出了d m 模型及c p c a 算法的两个实际应用： j ) 利用v i d m 分解出 的数据异常信息部分，我们把v i d m 模型作为一种o u t l i e r 检测的方法应用在股票 市场中异常收益的检测e ；( 2 ) 利用v i i ) m 分解出的数据内在信息部分，我们把 v i d m 模型作为特征提取( 滤波) 的方法应用在说话人识别任务中的前处理上。 第四章：用s v m 方法研究o n e c l a s s 分类问题和o u t l i e r 问题。在将 o n e c l a s s 分类问题理解为一种函数估计问题的基础上，本章首次定义了 ”一o n e c l a s s 和1 1 一o u t l i e r 问题的泛化错误，进而定义了线性可分性和边缘，得 到了求解o n e c l a s s 问题的最大边缘、软边缘和v 一软边缘算法。我们把算法归 结为求解线性规划问题，并采用与b o o s t i n g d e m i r i z 2 0 0 2 类似的思路实现这个 线性规划。最后，通过股票市场中异常个股检测的实验验证了我# j 的算法。 第五章：首先概述了半监督学习的发展背景及现状，然后结合本文研究的 o n e c i a s s 分类问题，提出了一种半监督的o 1 e - c l a s s 分类学习方法：半监督的 v s v m ( s e m i v s v m ) ：接着给出了实现s e m i v s v m 的两种具体算法：整数规划 方法和二次规划方法：最后在文本分类的任务中验证了s e l n i v s v m 的有效性。 第六章：总结了本文的研究内容，并指出了进步的研究工作。 第_ 节琏于描述的o d e c l a s s 问题：v i d m 模犁 第二章基于描述的o n e - c i a s s 问题：v l d m 模型 _ | 刍三第一章中，我们指出o t l e c l a s s 问题叫以分为o n e el a s s 描述问题和 o d e c 1a s s 分类问题。本章的焦点是o n ec l a s s 描述问题。 本章首先提出了种解决o n e c l a s s 描述问题的模型：基r 方差的信息分解 模型( v a t l a n c e b a s e di n f m l l l l s t o nd e c o m p o s ir t gm o d e l ，v o m ) ，此模型把 数据集的信息分解为内在信息和异常( 噪音) 信息两部分。接着在算法层次上， 我们为v i d m 模型引入了基于主成分分析的算法( p r ir l c i p a lc o m p o n e n ta n a l y s i s b a s e da l g o r i t h i n p c a a ) 和基于主曲线的c p c a 算法( c o n t e x t u a le r i n e t p a l c u r v e sa 1 9 0 r i t h m ) ，最后指出了v i d m 模型及其算法的几个具体应用。 2 1 基于描述的o n e - cla s s 问题的任务 我们在第一章中指出，基于描述的o n e c l a s s 问题是指给定一组没有标签 的样本集，如何描述它包含的内在信息( 与异常信息或噪音信息相对应) 。为 完成此任务，一个直接思路就是把其理解为一种非监督下的函数估计的问题， 印估计函数来描述数据的内在信息。但遵循v a d n i k 原则 v a p n i k l 9 9 8 ，“在解 决一个给定的问题时，要设法避免把解决一个更为一般的问题作为其中间步 骤”，因此一般我们并不以真手估计分布为出发点。 因此，在本章中，对i 解决o n e c l a s s 掐述问题，我们给出了- - 1 十更为直 接的方法，既设法把数据集包含的信息直接分解成两部分：内在信息和异常( 噪 音) 信息。为此，我们提出了一种基于方差的信息分解模型( v a r i a n c e b a s e d i n o r m a t i o nd e c o m p o s i n gm o d e l v i d m ) 。在以方差表示数据信息的前提下， 此模型把数据集的信息分解为估计方差表示的内在信息和残查表示的异常( 噪 音) 信息。根据v i d m 模型，如果以内在信息为出发点，那么v i d m 可以应用在 特征提取、有损压缩、去除噪音、潜在变数模型等任务中反之，如果以异常 信息为山发点，则v i d m 可以应用在异常信息分析及o u t ie r 检测的任务中。 o n e c l a s s f q 题研究及应用 2 2 基于方差的信息分解模型( v i d m ) 在给出v i d m 模型之前，我们先给出一些预备知识。 首先，为叙述方便和保持本章的完整性，我们把第一章中的定义l l 作为 定义2 一l 无变化的列在本节。 令u c _ r 哟样本空间，a 是参数集合( a 的含义见第。章1 2 1 节，p 5 ) 。 定义2 - 1 设7 1 u ( c a r d ( t ) = 月) 是与u 独立同分布的一组样本子集， x = ( x ，x c l ) t 。如果存在t 上的一个函数i 厂使 x = ，( x ，五) 十 ( 2 - 1 ) 其中f ( x ，五) = ( ( z ，五) ，+ ( j ：， ) ，f ( x c l ，五) ) ，五a ，且f ( x ，且) 是x 的内在信 息部分，p 是z 的残余部分，则称x 是可分解的。 根据定义2 - l ，信息分解的具体任务就是把分解为f ( x ，五) 和占，其中x 的内在部分，( ，五) 是稳定的但其异常部分f 因受各种冈素影响是不确定的。 令f ( t ，五) 是对数据集t 内在信息的描述，因此可以把o n e c l a s s 描述问题的求 解转换为从已知数据集t 中求解f ( t ， ) ，目标是最小化i j r f ( t ，兄) 1 1 2 。 定义2 - 2 设x = ( ，t ，x c l ) t ，旯a 。设八肖， ) = 耳xj ) ，其中 c l e f f ( x ，五) = e ( r ，f 五) ，j = l ，2 ，d ， ( 2 2 ) 则f ( x ， ) 称为在条件丑下的估计值。 定义2 - 3 ( 平方距离) 设= ( x ，x 2 ，如) t ，五a 。距离 d e d s ( ， ) = ( x ，一e ( x ，f 五) ) 2 ， ( 2 3 ) ，= l 称为( ，a ) 和x 之间的平方距离。 定义2 4( 期望乎方距离) 设r u ( c a r d ( t ) = n ) ，五a ， f c ，五) = ( f ( x ，五) t 。距离 a ( r ，) 二叫t e ( ri ) | | 2 】 ( 2 - 4 ) 称为f ( r ，丑)