（计算机软件与理论专业论文）基于置信度预测的半监督特征选择算法.pdf

摘要 基于置信度预测的半监督特征选择算法 高幅度。 关键字：半监督学习，特征选择，无类别标签样本，样本偏差，置信度，自我训练 a b s t r a c t 基于置信度预测的半监督特征选择算法 k e yw b r d s ：s e m i - s u p e i 8 e d ，f b a t u r es e l e c t i o n ，u n l a b e l e dd a t a ，8 a m p l es e l e c t i o n b i a s ，c o n 丘d e n c e ，s e l f - t r a i n i n g 基于置信度预测的半监督特征选择算法摘要 基于置信度预测的半监督特征选择算法 计算机软件与理论 硕士生：丘正元 指导教师：印鉴教授 摘要 传统的特征选择算法直接在有类别标签数据集上进行特征选择，以选取对 这些已知类别标签样本的类别具有最大区分能力的特征子集。但是在一些实际 应用中，如在医学诊断、欺诈检测等领域，样本的类别标签通常不能很容易地获 基于置信度预测的半监督特征选择算法学位论文使用授权声明 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学校有权保留 学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版，有权将 学位论文用于非赢利日的的少量复制并允许论文进入学校图书馆、院系资料室 被查阅，有权将学位论文的内容编入有关数据库进行检索，可以采用复印、缩印 或其他方法保存学位论文。 学位论文作者签名：一一丑 日期：工口口彦年乡月乡 疋死j 导师签名： 日 日期：磁年厂月弓日 u 1 基于置信度预测的半监督特征选择算法第2 章特征选择概述 的独立性和正交性的假设条件下，特征排序方法也能够为某个给定的学习模型 选择出最好的特征子集。例如，在使用f i s h e r 评价标准1 为分类问题进行特征排 序特征选择时，如果得到的协方差矩阵是对角矩阵，则得到的目标特征为f i s h e r 线性判别分类将是最优的【l7 】。即使是当特征排序方法并不能得到一个最优结果 时，它也可能比其它的特征子集选择方法好，因为其在计算复杂性与统计特性上 具有较强的优势【6 】o 就计算复杂性而言，特征排序方法具有较高的效率，因为其 只需计算n 个评估值并对这n 个评估值进行排序；就统计特性而言，它具有较强 的鲁棒性( r o b l l s t ) ，并能在一定程序上消除过适应的问题。 特征评价标准的定义是特征排序方法的一个核心内容。根据不同的标准，特 征排序会得到不同的序列。另外，不同的评价标准可能会适用于某些应用领域， 因此各种标准都有其适用之地。下面我们简要介绍各种评价标准的定义。 2 3 1 相关性标准 从特征排序这方面讲，相关性度量可以找出特征与类别之间存在的相互 关系。但同时这一度量方法也可以根据特征之间的依赖关系来发现特征的冗余 性。p e a r 8 0 n 系数是一种最常用的相关性度量方法。 如果输入向量x 可以解释为在一个未知分布的空间中随机抽取的向量的一 个实例，则x 的第i 个分量记为x 。类似地，y 是剪的一个随机变量空间。下面 我们将用毪标记m 维向量空间中所有训练样本的第t 个分量的变量值；用l ! ，标 记m 维向量的所有目标值。对于可是连续输出值的预测问题，p e 盯s o n 相关性系 数定义为； 聊) = 焉器， ( 2 _ 1 ) 、u 0 7 i ) u n r 【yj 其中，口表示协方差，移n r 表示方差。其近似估计计算方法为： 耻去蒜蓦赫， c 2 之， 其中，带上划线的部分表示对应下标后上的一个均值。当向量猕和可进行中心 化( 减去其平均值) 后，该系数同时也是毪和可的余弦值。另外，虽然r ( i ) 是由 冗( i ) 导出的，但其并不需要这个前提假设：输入的变量是一个随机变量【6 】。 相关性标准( 如，r ( ) ) 只能够检测出特征与目标概念( t a r g e t ) 之间的线性 依赖关系。一种改变该种限制的途径是计算特征与目标概念之间的非线性适应 性，然后通过该适应性来对特征进行排序。因为存在过适应的风险，我们可以选 择性地使用非线性的预处理方法( 如取平方、平方根、对数、倒数等) ，然后使用 1 f i 8 h e r 评价标准，指类间方差和类内方差的比值。 7 第2 章特征选择概述基于置信度预测的半监督特征选择算法 简单的相关性系数进行特征排序【6 ，1 8 】。相关性标准经常被用于基因芯片数据分 析等领域【1 9 】。 2 3 2 单特征分类器 前面已经提到，r ( i ) 可以作为一种排序标准评价单个特征的线性可分性。同 样的道理，我们也可以根据单个特征的分类预测能力来选择特征，即是以分类预 测能力来作为特征排序的标准。例如，特征的取值本身可以作为判别函数。通过 在特征的取值上设置一个阈值口( 口的取值可以是两类别的重心的中点) 来进行 分类。特征的分类预测能力可以通过错误率来度量。但也可以采用其它包含正类 错分率如r ( f a l s ep o s i t i v ec l a s s i 矗c a t i o nr a t e ) 和负类错分率，n r ( f a l s en e g a t i v e c l a s s i f i c a t i o nr a t e ) 等的度量方法f 6 1 。 当有很多个特征能取得好的分类效果时，分类正确率的排序标准很难在这 些好的特征之间进行特征好坏的判别。此时，我们更倾向于使用相关性系数或其 它的统计方法，如类别边界距离2 等等。 2 3 3 信息论排序标准 很多特征选择方法f 1 3 ，2 0 ，1 5 ，2 1 】都使用了信息论的评价标准。其中，基于 特征值与目标类别之间的互信息( m u t u a li n f o r m a t i o n ) 的是一项重要的实验评 估方法。其定义为： z ( 移2 ；z p ( 甄彬) l o g 责翳如咖， ( 2 _ 3 ) 其中，p ( 兢) 和p ( 可) 是瓤和y 的概率密度，p ，可) 是两者的联合密度。互信息 z ( z ) 量度了变量耽的密度和目标类别可的密度之问的关联性。 根据公式( 2 - 3 ) ，我们必须取得三个概率密度p ( 玩) 、p ( ) 和p ( 甄，) 才能计 算出z ( z ) 。但这三个概率密度都是未知的并且很难在训练数据集上评估得到。当 变量是离散的或标称型的时候问题将变得简单，因为其中的积分将变成一个累 加： 坤) = 莓莩职锄卜刚。g 篇端 戤毫， 、。、”7 此时，这三个概率可以通过在数据集上计算出现的频率来估计【6 】。 特征取值是连续的( 也有可能目标值也是连续的) 将是最难处理的情形。 我们可以考虑将特征取值离散化或采用一个无参数的( n o n - p a r 锄e t r i c ) 方 法( 如，p a r z e nw i n d o w s 【2 1 】) 对概率密度进行估计【6 】。采用正态分布对概率密 8 2 类别边界距离是指两类别最相近点之间的距离。 基于置信度预测的半监督特征选择算法第2 章特征选择概述 度进行估计将使我们回到对五和y 的协方差的估计中，因此也使其跟相对性系 数的方法相似。 2 4 特征排序方法局限性的讨论 在特征排序方法中，我们通常只考虑了单个特征的重要性，并未考虑特征的 冗余性及互补性。冈此，该科t 方法选择到的特征集合可能存在较多的冗余特征， 另有一些重要性相对低的特征有可能被忽略掉，但其如果跟其它特征联合起来 可能是一个很有价值的。这就是特征排序方法的局限性问题。g u y o n 等1 6 】通过 对几个实例的研究得出如下几个结论： 1 增加看起来是多余的特征，可达到减小噪声和增加类别区分能力的效果； 2 完全相关的特征是多余的，增加这样的特征并不能增加新的信息； 3 很高的特征相关性( 或反相关性) 并不意味着不存在特征间的互补性； 4 两个本身无用的特征在一起有可能达到好的分类效果。 2 5 特征子集选择方法 在前面的部分中，我们介绍了特征排序的特征选择方法，并讨论了特征排序 方法存在的局限性。为了克服特征排序方法存在大量特征冗余、不能发现互补特 征的缺陷，我们可以采用子集式的特征选择方法。子集式选择方法通过把特征子 集作为一个整体来度量其有效性，这与特征排序方法根据单个特征的评价为标 准来选择特征不同。子集式特征选择在本质上可以分为封装式( w r a p p e r ) 、过滤 式( f i l t e r ) 、和嵌入式( e i n b e d d e d ) 的三种方法6 1 。封装式的特征选择算法跟某 一学习方法相关，其使用该学习方法来评价特征子集的好坏；过滤式的特征选择 算法独立于选定的学= i 方法，其特征选择过程通常是作为一个数据预处理的过 程；嵌入式的特征选择算法通常是在模型训练的过程中实现特征选择的功能，其 通常也是跟选定的机器学习算法相关的。 子集搜索方式的特征选择算法是从原始特征集合中选择一个最优特征子集 的过程。这个子集的最优性是通过一个评价标准米度量的。随着所处理数据的维 度不断扩展，特征个数不断增加，这使得直接去搜索一个最优特征子集通常 是行不通的【1 6 1 ，并且很多与特征选择相关的问题都被证明是n p 难题【2 2 l 。一 个子集式特征选择算法一般都包括四个基本的处理步骤( 见图2 1 ) 【5 】：特征子 集生成、特征子集评价、中止条件和结果特征子集的验证。特征子集生成步骤是 9 第2 章特征选择概述基于置信度预测的半监督特征选择算法 图2 - 1 子集式特征选择的四个关键步骤 一个基于某种搜索策略的候选子集生成过程。每一个候选子集都通过某一种标 准进行评估来跟先前搜索到的最优子集进行比较。如果该新的特征子集比先前 搜索到的最优子集要好，则替换掉先前最优子集。子集生成和估价的过程将不断 重复直到满足给定的中止条件。最后得到的结果特征子集通常要通过一些数据 集来验证其好坏。 2 5 1 子集生成 子集生成过程在本质上是一个启发式搜索过程，它在搜索空间的每一步产 生一个候选子集给评估程序进行评估。该搜索过程一般包括两个问题。第一，必 须决定搜索的起点。该起点决定了搜索的方向。搜索过程可以从一个空集开始再 不断地增加特征( 如前向搜索) ，也可以从一个全集开始在每一步不断地移除特 征( 如后向搜索) ，或者从两头开始不断地交替增减特征( 如双向搜索) 。搜索起 点也可以是一个随机的特征子集，以此预防陷入局部最优【2 3 1 。第二，我们必须 确定搜索的策略。因为一个数据集如果有个特征，其候选特征子集将有2 个 之多。其完全搜索空间将是指数级的。即使对中等程序的，无遗漏的搜索也难 以胜任。因此，在现有的特征选择算法中采用了多种不同的搜索策略：完全搜索、 顺序搜索和随机搜索f 5 】。 ( 一) 完全搜索 安全搜索算法能保证所搜索到的特征子集对选定的评价标准是最优的。无 遗漏的全空间扫描是一种完全搜索( 没有遗漏任何一个最优子集) ，但搜索的完 全性并不一定表示必须对全搜索空间都扫描一遍。不同的启发式函数可以用来 降低搜索空间，而不影响对最优子集的搜索。因此，尽管搜索空间的数量级是 d ( 2 ) ，但需评估的子集数可以小很多。该类型的搜索策略有：分枝界定( b r a n c h a n db o u n d ) f 2 4 1 和束扫描( b e a ms e a r c h ) f 2 3 1 等等。 ( 二) 顺序搜索 1 0 基于置信度预测的半监督特征选择算法第2 章特征选择概述 顺序搜索策略放弃了搜索的完全性，因此也可能搜索不到一个最优子集。该 类型算法中有多个贪心爬山方法的变种，如顺序前向选择、顺序后向剔除和双向 搜索方法【4 】。这些方法在搜索的每一步都增加或减少一个特征。另一种变形是 可以交替地进行增加( 或移除) p 个特征和移除( 或增加) g ( p g ) 个特征f 2 3 1 。 顺序搜索方法是一种简单容易实现的方法。因为其搜索空间通常是d ( 2 ) 或更 小，所以计算效率也比较高。 ( 三) 随机搜索 随机搜索方法从一个随机生成的子集开始搜索，其处理过程可以用两种方式 进行。一种是根据顺序搜索方法，将随机过程插入到经典的顺序搜索方法中去。 这类型的方法有随机开始爬山算法( r a n d o m - s t a r th i l l c l i m b i n g ) 和模拟退火算 法( s i m u l a t e da n n e a l i n g ) 2 3 】。另一种方法是以一种完全随机的方式产生下一个 候选子集，如l o s y e 夕o s 算法【2 5 】。在这些方法中，随机过程有助于避免搜索方 法在搜索空间中陷入局部最优，但其能否搜索到最优结果取决于可用的资源( 包 括硬件资源及时间) 。 2 5 2 子集评估方法 正如我们前面所说，每一个生成的候选子集都必须使用一个评估标准来进 行评估。子集的好坏通常是跟选定的评估标准相关的。使用一种评估标准进行评 估是最优的子集对于另一种评估标准来说可能并不是最优的。根据评估标准是 否和学习算法相关，可以将评估标准分为两类：与学习算法独立的标准和与学习 算法相关的标准【5 】。 ( 一) 独立的评估标准 独立的评估标准一般地都应用于过滤式的特征选择算法中。它通过评估训 特征子集在练数据集上的内在特征来评估特征子集的好坏，而不是通过引入目标 学习算法来评价。一些常用的独立评估标准有：距离度量( d i s t a n c em e 嬲u r e s ) 、 信息度量( i n f o r m a t i o nm e a s u r e s ) 、相关性度量( d e p e n d e n c ym e a u s u r e s ) 、和一致 性度量( c o n s i 8 t e n c ym e a s u r e s ) 4 1 。 距离度量也即是可分性度量。对于两类别的问题，如果在特征x 上两个类 别的距离比在特征y 上产生的距离大，则我们选取特征x ，因为我们希望 把两个类别分得远越好。 信息度量方法通常采用信息增益的标准。如果特征x 的信息增益比特征y 的信息增益要大，则选取特征x 。信息度量方法中的互信息标准已在前面 的特征排序度量标准中作了介绍。 】 第2 章特征选择概述基于置信度预测的半监督特征选择算法 相关性度量有时候也称为相似性度量。它度量通常一个特征的值预测另一 个特征取值的能力。在为分类问题进行的特征选择中，我们选择与类别相 关性高的特征。如果特征x 与类别c 之间的相关性比特征y 与类别c 之 间的相关性高，则选取特征x 。相关性度量也已在特征排序方法部分作了 介绍。 一致性度量试图找出一个具有最小特征个数的特征子集，使得在这个特征 子集上跟在整个特征空间上对类别具有相同的区分能力。如果两个样本有 相同的特征取值，但类别标签不同，则称其为不一致。看下面的一个包含三 个特征和一个类别的数据集： f f l易 乃 c 12 5a 18 6a 15 1 6b l 32 5b 在该数据集中，第一维r 上的数据分布与类别分布c 完全不一致，而第三 维毋上的数据分布与类别c 的分布是一致的。与类别一致的特征能用于 区分类别，而不一致的特征则无法用于区分类别。所以根据一致性的度量 方法将选取玛而不选取f 1 。但是在实际的应用中，用一致性度量方法进行 特征选择时需要考虑各种特征的不同组合，应用于高维数据时其计算代价 很高。 ( 二) 与学习算法相关的评价标准 与学习算法相关的评价标准通常是用在封装式特征选择算法中。使用这种 评价标准时须预先确定特征选择结果的应用领域，因为它是与学习算法相关的。 使用一种学习算法构造模型作评价标准选择出的特征子集并不一定适合与其它 学习算法。但正因为其与学习算法相关，使得其特征选择的结果具有一定的针对 性，最后选择出的特征子集应用于选定的学习算法时通常能取得较好的效果【5 】。 然而，使用该种方法进行评估时其计算量很大。例如，当使用分类器的精度作为 评估值时，对于每一个特征子集都必须构造分类器并用验证集米验证该分类器 的精度，使得特征子集评估的计算量很大。 2 5 3 搜索中止条件 中止条件的判定是搜索过程的一个重要步骤。在特征选择算法中，终止条件 决定了何时该中止特征选择过程。常用的终止条件有【5 】- 1 2 基于置信度预测的半监督特征选择算法第2 章特征选择概述 1 搜索完成，即根据特征子集生成策略完成了在整个特征空间上的搜索； 2 达到了某种给定的边界条件，该边界条件可以是预先给定的特征个数或搜 索的最大迭代次数等等； 3 不管是增加还是删除任何特征，都不能搜索到比原来更好的特征子集； 4 找到了一个足够好的特征子集，例如在所找到的特征子集上的分类错误率 满足用户的要求。 2 5 4结果评价 一个最直接的方法是使用先验的知识对特征选择的结果进行评价f 5 1 。但是 先验知识通常只是在使用人工合成的数据时才拥有，在处理现实世界的数据时 我们通常并没有先验知识，因此必须借助于非直接的方法。非直接的评价方法就 是比较两个特征子集上完成挖掘任务所取得的性能好坏。例如对于分类问题进 行的特征选择，在搜索过程中可以比较两个特征子集上所构造的分类器所取得 的精度，从面判断两个特征子集哪个更优。 2 6特征子集选择方法的三种模型 2 6 1 封装式和嵌入式特征选择算法 不管选择何种学习方法，封装式1 6 1 算法都提供了一种简单而有效的特征选 择方法。其算法流程如图2 2 所示。在这种方法中，学习算法的程序供特征选择 方法调用来评价特征子集的好坏。在实际应用中，我们必须定义【6 】：( 1 ) 怎样搜索 所有可能的特征子集组成的空间；( 2 ) 怎样评估学习方法的预测能力从而引导特 征子集空间的搜索和中止搜索过程；( 3 ) 使用哪种学习方法。如果特征的个数不 会很多，则可以使用完全搜索方法。但这种搜索方法是n p 一难的【2 6 1 ，其搜索的时 间复杂度很高。为了提高搜索效率，我们可以使用如最优优先( b e s t f i r s t ) 、分支 界定( b r a n c h a n d - b o u n d ) 、模块退火( s i m u l a t e da n n e a l i n g ) 、遗传算法( g e n e t i c a l g o r i t h m s ) 等搜索策略 1 6 】。特征子集上所构造出的学习模型的评估通常使用 一个验证集( v a h d a t i o ns e t ) 进行评估，或使用交叉评估方法( c r o s s _ v a l i d a t i o n ) 。 学习方法的选择是由用户的应用领域决定的。 封装式的特征选择算法通常受到很大的批评，因为其需要很大的计算量。但 如果我们能采用效率高的搜索策略的话，其效率也是能大大地提高的6 1 。也许 我们会认为使用这些非完全的搜索策略牺牲了对预测能力的评估，但事实上使 1 3 第2 章特征选择概述 基于置信度预测的半监督特征选择算法 目标学习算法相关，可以将子集式特征选择算法分为封装式特征选择算法和过 滤式特征选择算法：封装式特征选择算法使用目标学习算法来评价特征子集；而 过滤式特征选择算法则使用独立于目标学习算法的其它标准来评价特征子集。 从计算效率上来说，特征排序方法是效率最高的一类算法；子集式搜索的过 滤式算法次之；封装式算法执行效率最低。这是因为它们的目标子集的形成方 式、搜索方式和子集评价方式不同所致。在现实应用中我们除了考虑算法的效率 之外还应考虑算法与实际问题的适应性问题：特征排序方法因无法检测特征间 的冗余性和互补性而不能应用于特征冗余性高和互补性强的领域；子集式特征 选择的过滤式算法冈非针对某个学习算法进行特征选择而在目标特征子集的好 坏上略逊于封装式特征选择算法。然而庞大的特征数量对子集式搜索算法特别 是封装式算法是难以承受的，因此我们通常也会先采用特征排序方法去除不相 关特征，然后苒用子集式搜索算法进行特征选择。 本意介绍的特征选择算法一般都是指传统的特征选择算法，也即其特征选 择过程是在有类别标签数据集上完成的有监督特征选择。这些都是我们进行创 新特征选择算法的理论基础。然而我们面临的是有类别标签数据不足、无类别标 签数据丰富的问题，这一问题必须采用半监督学习的方法来解决。因此我们在下 一章具体地介绍半监督学习的理论。 1 6 基于置信度预测的半监督特征选择算法第3 章半监督学习方法 第3 章半监督学习方法 半监督分类是分类问题的一种特殊形式。在传统的有监督学习模式中，分类 器需要在有类别标签的数据集( 1 a b e l e dd a t a ) 上进行训练。该有类别标签数据集 的每一个样本都包含特征向量和类别标签。然而很多情况下获取类别标签是费 时费力代价很高的，并且可能必须是具有实践经验的人才能完成为数据赋予类 别标签的工作。相反地，无类别标签数据相对地容易收集，但能够直接使用这些 无类别标签的方法很少。半监督学习方法提供了一种使用大量无类别标签数据 和少量有类别标签数据进行模型构造的有效方法f 2 9 ，3 0 1 。半监督学习方法需要 更少的人力进行数据处理并且能获得更高的分类精度，因此从理论上和实践上 来说它都是一种可行的方法。 3 1半监督学习方法的应用背景 有类别标签数据缺乏和训练集数集与真实数据存在偏差是促使我们使用半 监督学习方法的两大原因。我们先来讨论有类别标签数据缺乏的问题。正如前面 所说，在实际应用中我们通常是很难获取到有类别标签数据的，为了取得一个数 据的类别常常要付出很的代价。比如在基冈芯片检测巾一个基因芯片的类别通 常必须通过医学检验才能获得；在矿产资源检测中必须实地挖掘才能判定该地 理位置是否有资源；而在文本图像等的分类问题中必须通过人工阅读才能判定 其真实的类别。在有类别标签数据不能大量地获取时，如果我们能够有效地利用 无类别标签数据就能够缓解训练数据不足的压力。此时利用无类别标签数据就 是要把它们加入到训练集中增加训练集的信息。对于这个问题后而将有一系列 相关的方法进行解决。 数据偏差是半监督学习方法所要解决的第二大问题。所谓数据偏差是指训 练集上的有类别标签数据所反映的数据分布跟真实的数据分布不一致。这种不 一致性使得在训练集上训练出的模型不能有效地应用于将来的待预测数据的预 测过程。产生这种偏差也有其三大原因： 1 数据概念随时间变动。当产生训练集数据跟产生后续数据的概念不一致时 会使得训练集数据与真实数据存在分布上的偏差。这种概念的变动常常是 数据流上面l 隘的问题，但在半监督学习问题中我们不是用新获取的有类别 1 7 第3 章半监督学习方法基于置信度预测的半监督特征选择算法 标签数据来更新训练集，而是用无类别标签数据来更新训练集。 2 抽样机制产生的偏差。训练集数据通常是从大规模的数据集中抽样产生， 如果这个抽样机制没有做到完全的随机也有可能会产生数据分布不一致的 偏差问题。 3 有类别标签数据少产生的偏差。产生这种偏差是因为有类别标签数据太少 以致其不能反映一定的数据分布。通常在有类别标签数据量极端少的情况 下都会存在这个问题。 在数据偏差问题中引入无类别标签数据就不只是扩充训练集的问题，而是 要通过引入无类别标签数据来改变训练集的数据分布。但彳 管是应对有类别标 签数据缺乏的问题还是对数据存在偏差的问题，半监督学习方法都是通过引入 无类别标签数据来解决。 然而，引入无类别标签数据总是有效的吗? 我们的答案是：无类别标签数 据不可能总对学习问题带来帮助。如果问题领域的结构与所选用的模型的假设 不想匹配，则引入无类别标签数据可能会危害学习模型的构建 2 9 】o 例如，有一 些半监督学习方法假设分类的决策边界应该避免较高的p ( z ) 的区域。这些方法 包括：传递性支持向量机( t r a n s d u c t i v es u p p o r tv e c t o rm a c h i n e s ，t s v m s ) 、信息 正则化( i n f o r m a t i o nr e g u l 甜i z a t i o n ) 、带有空类别噪音模型的高斯处理、当图的 权重使用距离对度量时基于图的处理方法等等。此时，如果数据集是由两个高 度重合的高斯分布产生的，则其决策边界会通过样本分布的密集区，用这些半 监督学习方法可能会取得不好的效果。对于这种类别的数据集，如果使用其它 的半监督学习方法如生成混合模型的e m 方法则可能可以获得较好的效果。在 机器学习领域中，每一种算法模型都会适用于某一个问题领域，要使一个模型 适应所有的问题是几乎不可能的，因此，我们要针对不同的问题选用不同的模 型。下面我们介绍几种常用的半监督学习模型，包括：带生成混合模型的e m 方 法( e mw i t hg e n e r a t i v e 血x t u r em o d e l 8 ) 、自我训练方法( s e 堆t r a i n i n g ) 、协作训 练方法( c 伊t r a i n i n g ) 、传递性支持向量机( t r a 璐d u c t i v es u p p o r tv e c t o rm a c h i n e s ， t s v m s ) 和基于图的方法( g r a p h - b a s e dm e t h o 凼) 等等。 3 2 生成混合模型和e m 这或许是最老的半监督学习模型。它混合有类别标签数据和无类别标签数 据一起生成聚簇1 ，在一个聚簇中根据有类别标签数据来判断无类别标签数据的 1 聚簇，是指以空间分布而聚集在一起的样本集合，不一定是指以聚类算法生成的聚类，有可 能是根据某种概率模型而确定的样本关联。 1 8 第3 章半监督学习方法基于置信度预测的半监督特征选择算法 的类别赋予其余的无类别标签样本【3 7 ，3 8 】。这种算法的有效性取决于所选用的 聚类算法是否能够适应数据分布。因为一个数据集用不同的聚类算法得到的聚 类结果是有可能不同的，因此对无类别标签样本赋予的类别标签也有可能不同。 3 3 s e l f _ t r a i n i n g s e l f - t r a i n i n g 2 9 1 是一种广泛使用的半监督学习技术。在s e l f - t r a i n i n g 方法 中，首先在较小的有类别标签数据集上训练一个分类器，然后使用该分类器对无 类别标签样本进行预测。其中的预测置信度较高的无类别标签样本连同其预测 标签起再加入到原始的有类别标签数据集中形成新的训练集。接着再在这个 新的训练集上重新训练分类器。这个“训练一预测一采样一训练”的过程可以经 过多次迭代直到满足一定的中止条件为止。我们可以发现这里的分类器用自己 的预测结果来重新训练自己，则在迭代过程中正确的预测结果有可能加强其正 确性，但错误的预测结果则会误导其下一步的学习过程。所以很多算法采用的策 略是：当预测置信度小于某一个阈值时，采样时就不再选择这些无类别标签样本 点。 s e l f - t r a i n i n g 方法已被广泛用于自然语言处理任务中。o w s k y 使用s e l f t r 2 l i n i n g 方法进行语义消歧f 3 9 】r i l o f f 等使用s e l f - t r a i n i n g 方法进行主语名词的 识别 4 0 】os e l f - t r a i n i n g 还被使用在语言分析和机器翻译上面。 本文的研究引入了s e l f - t r a i n i n g 的半监督学习方法，提出了一种基于置信度 预测的半监督特征选择算法。它采用s e l f t r a i l l i n g 的算法框架，引入置信度的评 判标准，以迭代的模式进行子集式的特征选择。详细的分析请看第4 章的内容。 3 4 c 沪t r a j n i n g c 伊t r a i n i n gf 4 1 ，4 2 】假设特征子集能够很自然地划分为两个子集；每一个子 集上都有足够的能力训练一个好的分类器；且两个子集都能够独立地判断分类 信息。最开始两个分类器都在各自的特征子集上用有类别标签样本进行训练，然 后用这两个分类器对无类别标签样本进行预测，接着用一个分类器预测后的样 本点( 通常选择置信度高的一部分) 加入到原始训练集去训练另一个分类器。该 训练过程可以进行迭代。 我们可以采用二部图来分析为什么把无类别标签数据引入到训练过程 中能提高其预测精度。c 伊t r a i n i n g 的训练过程可以用如图3 2 所示的二部图 g d ( x 7 ，x ) 表示( 或简记为g d ) 【4 1 1 。在二部图中，左边的每一顶点代表x 7 视角 下的一个样本点，右边的每一顶点代表x 视角下的一个样本点。如果任意两个 基于置信度预测的半监督特征选择算法第3 章半监督学习方法 黑 二s 一 图3 2 二部图分析c m t r a i l l i n g 学习过程( 其中实线边相连部分组成g s ，所有顶点组成的 二部图为g d ) 顶点所代表的样本点属于同一类别的概率不为零，则这两个顶点有一条边相连 接。因为任意相同序号的两个顶点代表的是同一个样本，所示它们之间必定有边 相连。有类别标签数据集的任意两个样本如果是属于同一个类别，则它们之间有 一条实线相连。如果用s 表示由有类别标签数据组成的有限数据集，g s 表示由 s 构造的二部图，则s 上的各个连接子图表示了s 上的类别分布，如图3 2 ( a ) 所示。因为二部图上的子图是由连通的顶点组成的，所以在相同子图中的顶点都 属于同一个分类类别。对于无类别标签数据，左边的每一个顶点都将根据其在 x 7 视角上的预测结果而连接到右边的顶点上。因此，它将被连接到其最有可能 的类别上。我们再记d 为所有的真实数据集，g d 是表示真实数据集的二部图。 因为g d 上的子图反映了真实数据集d 上的类别分布，所以如果我们能够正确 地取得g d 上的子图则能完全正确地对d 上的数据进行预测分类。但当d 是一 个无限集时是不可能达到此目的的。c 伊t r a i n i n g 模型构造的工作就是通过无类 别标签数据的使用找到接近于g d 的子图分布。给定s ，当不断增加对无类别标 签数据的预测时，将有边不断地增加到二部图中，则二部图的子图会不断地聚 合，其子图的个数会不断地降低。因此，g s 中的子图将跟g d 中的子图更接近， 由此使得对无类别标签数据的预测将更加准确。例如，在图3 - 2 中顶点1 和2 代 表有类别标签数据中具有相同分类的样本，顶点5 ，6 和7 代表有类别标签数据 中具有相同的分类但与顶点1 和2 具有不同分类的样本，顶点3 和4 代表无类别 标签数据。在知道预测类别标签3 和4 之前二部图有四个子图，如图3 2 ( a ) 所 示。引入顶点3 和4 的预测类别标签后( 假设顶点3 预测为与顶点2 有相同的类 别标签，顶点4 预测为与顶点5 有相同的类别标签) 。则无类别标签样本3 可以 连接到顶点l 和2 形成一个新的子图，无类别标签样本4 可以连接到顶点5 ，6 和7 从而形成另一个新的子图。所以子图的个数降为2 ，如图3 - 2 ( b ) 所示。文 献【4 1 】已经证明当无类别标签数据有足够多时，g s 中的子图数将和g d 中的子 2 1 基于置信度预测的半监督特征选择算法第3 章半监督学习方法 正则化处理方法是对这种图结构进行处理的有效方法。 采用正则化处理方法的一系列算法都可以看作是在图上定义了一个评估函 数，必须同时满足两个方面的要求：( 1 ) 必须与有类别标签样本的类别分布 舰相同或相似；( 2 ) 在整个图上的类别分布必须是平滑的。因此，我们可以用 损失函数( 1 0 s sf u n c t i o n ) 和正则化因子( r e g u l a r i z e r ) 两方面来组成正则化框架 【2 9 1 。损失函数表示对第一个要求的满足程度，即半监督处理结果对有类别标签 样本类别的拟合程度；正则化因子则用丁实现上面的第二个目标，它是正则化处 理的主要度量标准。不同算法因采取的策略或处理方法的不同，在损失函数和正 则化因子的选取上也会有所不同，但他们从这两方面来考虑问题的理念却是相 同的( 尽管在很多文献中并没有明确提出损失函数与正则化因子的概念) 。 最小分割方法与高斯随机域和谐函数方法是基于图的半监督学习方法中具 有代表性的方法。下面我们将详细地分析这两种方法。 3 5 1最小分割 图的最小分割是b l u m 和c h a w l a 【4 4 1 提出的一种半监督学习方法。给定一 个有类别标签样本集l 和无类别标签样本集u 。假定我们面对的是一个二分类 问题( 类别分别为正类和负类) 。用l 一表示l 中的所有正类样本，用l 一表示l 中的所有负类样本。则可以用如下流程进行最小分割处理。 1 构造一个带权图g = ( ke ) ，其中y = luuu q ，2 ，一) ，e y y 。每 一条边e e 的权值是叫( e ) 。顶点q 和口一叫作分类顶点，其余的顶点叫 做样本顶点。 2 分类顶点通过具有无限大权值的边跟相同类别的其它有类别样本点相连。 也即对所有移4 ，有彬( 秒，弭) = o 。；对所有秽l 一，有钮( 秽，钞) = o 。 3 样本顶点间的权值通过样本间的关系来确定，如使用相似性、距离度量等 方法计算获得。 4 确定所构造的图上( 口+ ， ) 的最小划分，也即确定一个边的集合，使该集 合的边的权值总和最小，并且移除这些边后能使u + 和 一不相连。则在移 除这些边后整个图被分割成h 和忙两部分，其中外吩，砂一亿。 5 将正类类别标签赋给h 中的所有无类别标签样本，将负类类别标签赋给 亿中的所有无类别标签样本。 在上述最小分割方法中，如果相似的样本之间的边给予一个较高的权值，则 两个相似的样本有较大的可能被划分在同一个集合里面。这与其它一此学习方 2 3 第3 章半监督学习方法基于置信度预测的半监督特征选择算法 法的“相似样本应该有相同的类别”的假设一致。我们可以通过一个物理模型来 看待这个最小分割方法：分类顶点移+ 是一个水源，钞一是一个目标池，连接各项 点的边是一系列的管道，边上的权值是这些管道的容量( 即单条管道的最大流 量) ；则分割( 外，钉一) 的最小划分问题是一个寻找从水源秒+ 到目标池秽一的最大 流量的问题。该最大流量即是所求得的最小分割的边集的权值总和。求解这个问 题可以采用最大流( m 躲n o w ) 算法。 最小分割的方法其实是一个二类别的马尔可夫随机域( m a r k o vr a n d o m f i e l d ) 模型。我们可以从损失函数和正则化因子两方面来分析该算法。因为分类 样本秽+ 和u 一与其同类的有类别标签样本相连的边具有无限大的权值，则分割 时不可能把这些有类别标签样本划分到对方的类别中去。因此这种方法对有类 别标签样本的误分率是零，其损失函数可以用经过无限大加权的平方误差表示： 五螂= o 。( 纺一玑i l ) 2 i l ( 3 _ 1 ) 正则化因子是整个数据集上被分为不同类的样本的加权和，表示为： 砉蛳i 玑一协i = 吉( 玑一班) 2 ( 3 _ 2 ) 。t 。j。t 。j 上式中等式成立是因为我们假设取二元的0 或1 的类别标签。把损失函数和正 则化因子两部分加起来得到一个目标函数： ( 鼽一蚍) 2 + 吉蚴( 玑一协) 2 ， 诞l。谢 其中狮 o ，l ，忱。最小分割方法的规划就是要使该目标函数值最小。 ( 3 _ 3 ) 3 5 2 高斯随机域及谐函数 马尔可夫随机域应用于离散的类别标签集合，而高斯随机域及谐函数方 法( g a u s s i a nr a n d o m 矗e l d sa n dh a r m o n i cf l m c t i o nm e t h o d s ) f 4 5 】放松了这个条 件限制，可以将其推广到连续空间的过程中。将离散样本空间推广到连续空间的 处理方法给我们带来了一些好处：其可能的域结构是唯一的；可以通过谐函数来 表示；并且可以用矩阵计算等方法来解决。相反地，在离散随机域中计算分布结 构的最小能量将是n p 一难的，这使得必须采用近似计算的方法或其它的启发式算 法来计算。高斯随机域方法的分类结果可以看作是最近邻方法的一种形式，其最 近的一个有类别标签样本通过在所构造的图上按一定的随机方法进行“走动”得 到。 第3 章半监督学习方法基于置信度预测的半监督特征选择算法 3 5 3 基于图的其他方法 除了上而提到的最小分割方法与高斯随机域及谐函数方法之外，还有多种 采用正则化的图学习方法，如：离散马尔可夫域的b o l t z m a n nm a u c h i n e s 4 6 ，4 7 】、 局部与全局一致性方法【4 8 】、t i l 【h o n o v 正则化方法【4 9 】、m a n i f o l d 正则化方法 ：5 0 ，5 1 】和拉普拉斯频谱的图核方法【5 2 ，5 3 ，5 4 】等等。 3 6半监督学习方法的选择问题 前面几个部分已详细介绍了多种半监督学习模型，然而我们应该选用哪种半 监督学习方法? 这应该根据问题领域而定。因为有类别标签样本点很稀少，半监 督学习方法在应用时需要有强的模型假设。在理想的情况下，我们应该选用模型 假设适合于问题结构的方法【2 9 】。但在现实中这或许会很困难。尽管如此，我们 可以通过以下方法来进行模型的选择：各类别是否能够产生较好的聚集，如果是 的话则可以选用带产生式混合模型的e m 方法；是否特征能够自然地分成两个 集合，如果是的话则可以选用c 0 _ t r a i n i n g 方法：是否有相似特征的两个点很可能 是同一类别的样本点，如果是的话则可以选用基于图的方法；是否原有方法中已 经使用s v m 方法，如果是的话则可考虑把其扩展成t s v m s 方法；是否已有的 有监督分类器已经比较复杂并难以改动，如果是的话则可考虑选用s e l f - t r a i n i n g 的方法。 3 7 半监督特征选择 特征选择和半监督学习方法都已经得到广泛且深入的研究，但将两者结合 起来还是一个新的研究问题。在z h a o 和l i u 于2 0 0 7 年提出基于频谱分析的半监 督特征选择方法【9 】时首先将有类别标签数据和无类别标签数据同时引入到特征 选择过程。 很多有监督和无监督的特征选择算法都要求度量特征的相关性，只是方法 不同而已。因此设计一个有效的半监督特征选择算法就要求设计一个框架，该框 架能够在有类别标签数据和无类别标签数据上以一个自然的方式对特征的相关 性进行评价。聚类的假设通常被其它的半监督学习方法的假设所采用。其假设 是：如果样本点被聚到同一个类中，则它们较可能是同类别的样本点。基于这种 思想，z h a o 和l i u 提出一种半监督特征选择算法s s e l e c tf 9 1 0 该方法首先将一个 特征向量f i ( 所有样本点的第i 个特征的取值组成的向量) 转换成一个聚类指示 器。聚类指示器的适应度通过两方面来进行评价：( 1 ) 分离性一一是否聚类的结 基于置信度预测的半监督特征选择算法第3 章半监督学习方法 构具有好的分离性；( 2 ) 一致性一一是否聚类的结构与有类别标签样本的分类信 息一致。理想的结果是聚类中所有的有类别标签样本都具有相同的类别。 假设g 是由特征向量f 生成的聚类指示器，宫= 就夕礼( g ) 。则正则化框架可 定义为： ( 1 叫( 1 一删鲫) ) + 入每喾黑窖 ( 汕) 。厶仇yy “” 其中，m ，( 童，y ) 是官和y 之间的规格化互信息( n o r m a l i z e dm u t u a li n f o r m a t i o n ) ，用于度量离散化后的聚类指示器与有类别标签数据的一致性。公式( 弘1 0 ) 的第二项计算了使用舍作为对数据x 的聚类指示器的分割值；第一项则评估了 使用窘对有类别标签样本进行分类判断的损失函数。在该框架中，不管是对有类 别标签数据的评估还是对无类别标签数据的评估都是通过使用聚类指示器g 进 行的。 z h a o 和l i u 提出的半监督特征选择算法s s e l e c t 是一种基于频谱分析的 正则化处理方法，但在半监督学习环境中，迭代方法也是一种有效的处理过 程。我们在另一篇论文中提出的前向半监督特征选择算法【5 5 】扩展了顺序前向 特征选择算法以利片j 无类别标签数据。传统的完全有监督的顺序前向特征选 择( s e q u e n t i a lf o r w a r df e a t u r es e l e c t i o n ，s f f s ) 是一种被广泛使用的特征选择 算法。它是一种从空的特征子集开始的一种迭代方法。在每次迭代过程中都从剩 余的特征中选择一个特征加入到所选择的特征子集中来。要决定哪一个特征被 加入，必须将每一个剩余特征都加进去测试该特征子集所对应的精度，以选取加 进来后能够取得最高分类精度的那个特征。通常这个迭代过程在增加特征而不 能提高其精度或当特征子集达到预先规定的大小时结束。因为该方法能够很容 易地实现并且有比较高的效率，所以它是一种广泛地应用的特征选择算法。将 s f f s 扩展为顺序前向特征选择算法则可以利片j 无类别标签数据。算法的基本过 程为：首先，我们在有类别标签的数据卜运行s f f s 算法得到一个初始的特征子 集；然后，和前向特征选择类似地在所得到的初始特征子集上利用有类别标签数 据集构造一个分类器，用该分类器去预测所有无类别标签的数据以得到其最可 能的类别标签( 称为“预测标签 ) ，然后随机选择已经有“预测标签”的无类别 标签数据和原始的有类别标签数据一起构成一个“扩展了的训练集”；接着用此 扩展了的训练集，用基于封装式的特征选择方法进行特征选择；多次随机选择便 能形成多个“扩展了的训练集”并得到多个特征子集：最后将出现频率最大的特 征加入到结果特征子集中；该过程将重复进行直到选出的特征个数达到预先确 定的特征个数为止。 本文提出的基于置信度预测的半监督特征选择算法在基本思想上与我们以