（计算机应用技术专业论文）几类复杂体系的分类及属性选择问题研究.pdf

大连理丁大学硕士学位论文 摘要 生命科学技术的快速发展产生了大量的生物数据，形成了多种多样的复杂体系，如 何从这些数据中发现有价值的知识及规律，成为目前理论与实践研究的热点与难点。为 了快速且全面的处理如此多的生物数据，数据挖掘技术成了大部分研究者的首选，旨在 利用数据挖掘的方法，在已有数据的基础之上发现相应的规律和知识进而指导与解释生 物实验与生命现象，加速对生命本质特征的认识。 分类是数据挖掘中重要的内容，也成为各学科研究的重点。朴素贝叶斯分类器是一 种简单且高效的分类器，它是在贝叶斯定理的基础上，通过条件独立性假设，将计算消 耗降低，预测未知数据样本，并且对高维数据分类有良好的表现。但朴素贝叶斯限制条 件较强，影响其在现实应用中的分类性能。通常对朴素贝叶斯的改进一般从两方面进行， 即属性间的依赖关系和分类器的整体技术。本文着眼于分类器整体技术和属性选择，提 出了二次建模的加权朴素贝叶斯，结果表明该算法在相对较大的样本集中取得了较好的 效果。 属性选择作为一种数据预处理的技术，有着重要的意义。研究表明大部分数据集中 存在的冗余和噪音数据严重影响了分类的效果，一般采取的方法是属性选择或属性提 取。本文提出了基于r e l i e f f 的打包算法，结合了过滤( f i l t e r ) 属性选择与打包( w r a p p e r ) 属性选择的方法，其效果比单独使用其中的一种更好。经测试，通过与三个f i l t e r 方法 和两个w r a p p e r 方法比较，该算法体现了其优越性。 关键词：数据挖掘；复杂体系；朴素贝叶斯；f i1 t e r ；w r a p p e r 大连理下大学硕士学位论文 r e s e a r c ho nc l a s s i f i c a t i o na n df e a t u r es e l e c t i o na n di t sa p p l i c a t i o ni n c o m p l e xs y s t e m s a b s tr a c t 1 1 l eb i o l o g i c a ld a t ah a sa l s 0i n c r e a s e de x p o n e n t l a l l yw i t ht h ed e v e l o p m e n t0 f t h el i f c s c i e n c ea n df b m e dm a n yc o m p l e x i t ys y s t e m s h o wt od i s c 0 v e rt h ev a l u a b l el 【i l o w l e d g e 觚d m l e sb e h i n dt h e s ed a t ab e c o m eac r i t i c a lp r o b l e m ni sb o t hi n e f f i c i e n c ya n dt i m ec 0 n s u m i n g f o rd e a l i n gw i t hs u c hl a r g es i z e0 fb i o l o g i c a ld a t ao n l yb a s e do nt h ec o n v e n t i o n a lb i o l o g i c a l c x p e r i e n c c u n d e rs u c hc i r c u m s t 锄c e ，a p p l yt h ed a t am i n i n gt e c h n o l o g yt 0c o m p l e x i t y s y s t e mr e s e a r c hb e c 0 m et h ef i r s tc h o i c eo fm 锄yr e s e a r c h e 璐o nt h ep u 叩o s eo fd i s c o v e r i n g m i e s 锄dl 【i l o w i e d g eb e h i n dt h ed a t af o rf u n h e rc o n d u c t i n ga i l de x p l a i n i n gt h eb i o l o 酉c a l e x p e r i e n c e 锄dl i f es c i e n c e ，弱w e ua ss p e e d i n gu pt h eu n d e r s t a n d i n go ft h ee s s e n t i a l t 0l i f e c l a s s i f i c a t i o ni si m p o n a n tc o m p o n e n to fd a t am i n i n 岛a sw e l l 豁t h ec r i t i c a lp r o b l e m0 f m 锄yd i s c i p l i n e s n 柳eb a y e s i 锄c l a s s i f i e r ( n b c ) i sc o n s i d e r e d 嬲o n eo ft h ee 疏c t i v e c i a s s i f i e rd e s p i t e0 fi t ss i m p l i c i t y ，w h i c hi ss u p p o n e db yb a y e s i 锄t l l e o r y b a s e do nt h e 弱s u m p t i o n0 fc o n d i t i o n a l i n d e p e n d e n c e ，i t 伊e a t l yr e d u c e st h ec o m p u t a t i o n a lc o m p l e x i t y 锄d h 弱ag o o dp e d o 锄a n c eo nh i 曲d i m e n s i o nd a t as e t h o w c v e r ，i ta l s oi nl a r g es c a l ei n n u e n c e s t h ea p p l i c a t i o ni nr e a l i t yb e c a u s et h i s 髂s u m p t i o nc o n n i c t sw i t ht h ef a c tt h a tm o s tr e a l l i f c d a t a s e t sa r er e l e v a n t t h e r ea r eu s u a l l yt w ow a y sf o re n h a n c i n gt h ep e r f b n n a n c e0 fn a v e b a y e s i 锄c l a s s i f i e rt h a ti st h ed e p e n d e n c eo fa t t 曲u t e s 锄dt h ew h o l eq u a l i t yo ft h ec l 硒s i f i e r h e 佗w ep r o p o s e dt h er e - b u i l d 柚dw e i g l l t e dn a v eb a y e s i 锄c l a s s i f i e r ( r w n b c ) w h i c h 五d c l 珞0 nt h ew h o l eq u a l i t y0 ft h ec l a s s i f i e ra i l df e a t u r cs e l e c t i o n t h er e s u l ts h o wt h a to u r m e t h o do u tp e r f b n n e dn b c0 nt h et o b a c c od a t as e t f e 柏l r es e l e c t i o ni sa i ii n d i s p e n s a b l es t e pi nm o s td a t ap r e - p r o c e s s i n g m a n yr e s e a r c h e s i l l d i c a t et h a tt h ee x i s t e n c eo fr e d u n d a n ta n dn o i s yd a t ag r e a t l yc o n s t r a i l lt h ee f f i c i e n c ya i l d e f 佗c t i v eo fc l a s s i f i c a t i o n t 1 l en o m a ls o l u t i o nt ot h i sp m b l e mi sf e a t u r es e l e c t i o no rf e a t u r c e x t r a c t i o n h lt h i sp a p e r ，an e wr e l i e f f - b a s e dw r a p p e re v a l u a t i o na p p r o a c hi sp r o p o s e df o r t h eg r e e d ys e a r c ho ff e a t u r es u b s e t 1 tc o m b i n e st h ea d v a n t a g e so ff i l t e ra n dw r a p p e r ，w l l i c h a c l l i e v e sb e t t e rp e r f o 姗a n c et h 锄b o t ho ft h e m t h r o u g l le x p e r i m e n t s ，t h er e s u l t ss h o wt h e a l g o r i t l l ma c h i e v e db e t t e rr e s u l tt h a nt l l r e e c o m m o nf i l t e rm e t h o d s锄d觚0岍a p p e r a p p r o a c h e s i ti n d i c a t e st h en e wr e l i e f f - b a s e dw r 印p e ra l g o r i t h mi se 饿c t i v ei nf i n d i n g s i g n i f i c a n ta t t r i b u t e st h a ta r es i g n i f i c a n ti nd i s c r i m i n a t i n gd i f f e r e n t 粤o u p s k e yw o r d s ： d a t am j n i n g ；c o m p i e x i t ys y s t e m ；n a i v eb a y e s i a n ；f j 【t e r ；w r a p p e r i i i 大连理工大学硕士研究生学位论文 大连理工大学学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定，在校攻读学位期间 论文工作的知识产权属于大连理工大学，允许论文被查阅和借阅。学校有 权保留论文并向国家有关部门或机构送交论文的复印件和电子版，可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印、或扫描等复制手段保存和汇编本学位论文。 学位论文题目：! 魈盔红尘金趣碰塾蛐遛磁 作者签名： 盘! i 堕! 鱼 日期： 冱竺年月王日 导师签名： 弛窆莲 日期： 边f 里年l 月三一日 大连理工大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外， 本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已申请 学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的贡献 均已在论文中做了明确的说明并表示了谢意。 若有不实之处，本人愿意承担相关法律责任。 学位论文题目：! 送鱼垒丛生塑鱼丝塑毽! 垒坠囹丝盈遂 作者签名：爿壹l 魄业年月立日 大连理工大学硕十学位论文 1绪论 1 1 研究背景及意义 随着现代分析技术的发展，样品中越来越多的化学成分被分离出来，样品的组分日 益多样化，不仅如此，多种分析方法的分析结果组合在一起，构成样品成分数据的多样 性和多元化。对这样的复杂体系样品的分析是现代分析科学面临的最困难课题之一。如 无机成分与有机化成分共存一体；高分子、大分子与小分子化合物共存一体；生命与非 生命物质共存一体等。完成把物质中的各个组分逐一分离成单一成分的过程就是复杂体 系解析。复杂体系中研究的问题是高维体系，大的数据集中的每一个样品并不是单一的 或少数几个指标可以描述的。但是如此多的属性中存在噪音以及与问题无关的信息，因 而不利于理解问题的本质。 复杂体系分离分析一直是分析化学的热点和难点问题。色谱作为一种分离技术与方 法，1 9 0 3 年，俄国植物学家茨维特( t s w e t t ) 首先用于植物色素的分离分析【，经过一个 多世纪的发展，现在已经发展成为分析化学的一个重要分支，在各个领域得到了广泛的 应用，如环境，食品，化工，生命科学等。物质的化学成分可以用色谱指纹谱图来表示， 它通过特定的分析方法和色谱仪器得到。这一命名借用了人们所熟悉的法医学中指纹鉴 定的概念。它将样品中的化学组分通过相应的色谱仪器进行分离并以色谱峰谱图的形式 描述出来。由于不同样品所含成分及每一成分含量的不同，所产生的样品色谱峰谱图如 同人的指纹一样各不相同。色谱技术在现代科学中有着广泛的影响力，著名分析化学家 周同惠教授曾说：“可以毫不夸张地说，如果没有色谱技术的应用，自然科学和生命科 学能发展到今天的这个样子是很难想象的，【2 1 。现代色谱分析主要分为液相色谱和气相 色谱，随着分析技术的发展，各种与之相关的色谱与其他检测相关的连用技术也发展起 来，例如气相色谱质谱，气相色谱红外光谱，气相色谱核磁共振谱，气相色谱原子 发射( 或者吸收) 光谱；液相色谱质谱，液相色谱红外光谱，液相色谱原子发射( 或 者吸收) 光谱，液相色谱核磁共振谱。一个完整的色谱分析通常包括三个步骤：样品 的采集与预处理，得到样品的色谱，色谱分析结果。其中样品处理消耗了大部分的时间， 约占整个分析时间的6 0 一7 0 【3 j ，是影响分析测定结果的准确性和可靠性的决定性因 素，因而常常成为色谱分析的瓶颈。随着化学分析技术的发展，更多的样品成分被分离 出来，推动了色谱指纹的应用。色谱指纹在产品质量控制、疾病诊断与治疗等领域的应 用日益广泛。 几类复杂体系的分类及屙i 生选择问题研究 例如，在复杂体系中，代谢指纹的研究通常对疾病诊断起至关重要的作用。代谢产 物是代谢组学研究的重要对象。代谢组学( m e t a b o n o m i c s ) 是继基因组学( g e n o m i c s ) 、转录 组学( t r a n s c r i p t o m i c s ) 和蛋白质组学( p r o t e o m i c s ) 后新兴的一种组学方法，是系统生物学的 重要组成部分，由n i c h o l s o n 【4 】于1 9 8 5 年首次提出。不同生物体其代谢产物所包含的成 分以及成分的含量不完全相同，代谢物的成分及其含量构成代谢指纹。每个生物体都有 其独特的代谢指纹，正如人的手指指纹不会完全相同一样。代谢组学研究的核心思想在 于利用现代分析技术定量测定生物体液( 如尿液、血浆、组织提取液等) 中的内源性代 谢产物，考察生物体在不同状态下( 生理病理状态、给药前后等) 其代谢产物的变化， 通过代谢物图的整体分析直接认识生理病理及生化状态，结合化学信息学分析方法确定 内源性小分子代谢物成分的变化模式，获得相应的生物标记物群( b i o m a r k e r s ) ，表征或揭 示生物体在特定时间、环境下整体的功能状态。疾病的发生引发病人机体的病理变化， 使得机体的代谢产物也随之发生某种相应的变化，对这些由疾病诱导产生的代谢产物的 变化进行分析，能够帮助人们了解病变过程及机体体内代谢途径，寻找疾病新的生物标 志物，同时辅助临床诊断和治疗。通常采用色谱分离技术，采集色谱数据，最终对数据 进行分析，以期待能找到对病因起决定作用的生物标识物，在众多的数据分析方法中， 本文主要利用数据挖掘技术对色谱指纹及基因数据进行分析。 1 2 数据挖掘 随着化学分析技术的发展，样品的色谱指纹、基因分析等复杂体系通常包含数十、 数百乃至数千个变量信息，如此信息量丰富的高维数据也带动了复杂体系数据分析处理 技术的研究和发展。许多数据挖掘的技术，如s v m r f e ，b a v e s ，d e c i s i o nt r e e 等，被 应用于分析和处理复杂体系，提取与问题相关的有用信息，建立高效的学习方法。 1 2 1 数据挖掘概念 科学技术的飞速发展，使经济和社会都取得了极大的进步，与此同时，在各个领域 产生了大量的数据，如何从这些数据中发现有价值的知识及规律，成为目前理论与实践 研究的热点与难点。在这些海量数据中往往隐含着多种多样的信息，这些信息往往凭直 觉与经验是难以发现的。而这些信息往往对各个行业( 如商业、企业、政府部门) 做出 有意义的决策起重大的作用，因而如何从大量的数据中获得有价值的信息与规律成为这 些行业发展的至关重要的因素。虽然传统的数据库有成熟的经验，但是随着数据的快速 增长，采用传统的数据库技术已经显得力不从心了，与此同时，数据的快速增长与数据 分析处理方法之间的鸿沟也日趋增大。人们希望能够在已有的大量数据的基础上预测未 来的商业走势或企业动态，从而达到为决策服务的目的。数据挖掘就是为了满足这种需 大连理t 大学硕士学位论文 求而迅速发展起来的一种新的数据处理技术。它的实质是一种发现知识和规律的应用技 术，是一个提取有用信息的过程。自2 0 世纪末提出以来，数据挖掘技术逐渐应用于金 融、电力、零售业、工业过程、医疗保健和政府决策等各个领域，取得了良好的社会效 益和经济效益，引起了许多专家学者的广泛关注，具有广阔的开发和应用前景。 数据挖掘的概念包含丰富的内涵，是一个多科交叉研究领域，其定义从不同的角度 看有不同的含义。数据挖掘从本质上说是一种新的辅助商业信息处理的技术，通过抽取 商业数据库中的大量数据，然后进行转换、分析和其他模型化处理，最终对商业决策有 关键性影响的数据被提取出来。虽然说数据挖掘从本质上是一种数据分析方法，但是并 不仅仅限于数据分析，随着社会的发展，人们所收集的数据不再是仅仅为了分析而收集。 为了帮助实现利润最大化，人们需要从大量由于纯机会的商业运作而产生的数据中获得 有利于商业决策的真正有价值的信息，因而分析这些数据不再单纯的为了研究需要了。 但是所有企业面临的一个共同问题是：企业数据量非常大，而其中真正有价值的信息却 很少。因此从大量的数据中经过深层分析，获得有利于商业运作、提高竞争力的信息， 就像从矿石中淘金一样，数据挖掘也因此而得名。 目前数据挖掘通用的定义是指从大量的、不完全的、有噪声的、模糊的、随机的实 际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识 的过程【5 1 。数据挖掘要解决的问题就是在庞大的数据中寻找有价值的隐藏信息和规律， 加以分析，并将这些有意义的信息总结成学习模型，提供给有关人员在将来决策时参考。 1 2 2 数据挖掘方法及应用 数据挖掘的方法很多，每种方法都有其特定适用的领域。一种方法不可能胜任所有 的数据挖掘任务，通常在一个复杂的数据挖掘系统中，多种数据挖掘方法被同时采用， 通过整合多种数据挖掘方法来弥补不同数据挖掘方法所存在的缺陷并结合其优点。数据 挖掘的方法主要有以下几种： ( 1 ) 决策树方法：决策树方法就是利用训练集生成一个测试函数，根据不同取值建 立树的分支；在每个分支子集中重复建立下层结点和分支。这样便生成一棵决策树，然 后对决策树进行剪枝处理，最后把决策树转化为规则，决策树方法主要用于分类挖掘。 ( 2 ) 统计分析方法【6 l ：统计分析方法是利用概率论、统计学的原理对关系中各属性 进行统计分析，从而找出它们之间的关系和规律。 ( 3 ) 遗传算法i _ 他遗传算法是对自然环境中的遗传和进化过程的一种模拟，从而形 成的一种自适应全局优化概率搜索算法。它最早由美国密执安大学的h o l l a n d 教授提出， 几类复杂体系的分类及属性选择问题研究 具有计算简单、优化效果好的特点，它在处理组合优化问题方面也有一定的优势，可用 于聚类分析等。 ( 4 ) 粗糙集方法【8 j ：粗糙集理论是波兰p a w l a kz 教授在1 9 8 2 年提出的一种智能决策 分析工具，它是一种刻划不完整性和不确定性的数学工具，它对不完备信息，如不精确、 不一致、不完整能进行有效地分析。粗糙集方法被广泛应用于不精确、不确定、不完全 的信息的分类和知识获取。 ( 5 ) 模糊逻辑【9 】：模糊数学研究的是“亦此亦彼”的模糊性。模糊数学是继经典数 学、统计数学之后，在数学上的又一新的发展。模糊逻辑在数据挖掘领域可以进行模糊 综合判别、模糊聚类分析等。 ( 6 ) 聚类分析：聚类分析是根据事物的特征对其进行聚类或分类，即所谓物以类聚。 以期从中发现规律和典型模式。通过聚类以后，数据集就转化为类集，同一类的数据具 有相似的变量值，不同类的数据的变量值不具有相似性。这类技术是数据挖掘的最重要 技术之一。除传统的基于多元统计分析的聚类方法外，近年来模糊聚类和神经网络聚类 方法也有了长足的发展。 最近邻技术：通过寻找后个与之最相近的训练样本来辨别新样本。这种技术可 用作聚类、偏差分析等数据挖掘任务。 ( 8 ) 可视化技术：这是一类辅助方法。它将挖掘出来的模式采用比较直观的图形图 表的方式表现出来。这种技术扩大了数据的表达能力，更直观，从而更易于为人们所理 解。这在数据挖掘中非常重要，可视化技术正受到日益广泛的重视。 数据挖掘技术的潜在应用是十分广泛的，从政府管理决策、商业经营、科学研究、 工业企业决策支持和h l t e m e t 服务等各个领域都可以找到数据挖掘技术的用武之地。下 面举出目前开展的比较活跃的数据挖掘的应用方向。 ( 1 ) 在商业企业中的应用：数据挖掘在商业银行、保险、交通、零售等商业机构有 广泛的应用。数据挖掘在商业方面的应用主要基于如下假设，即“消费者过去的行为是 其今后消费倾向的最好说明”。数据挖掘可用于对企业数据库中的大量业务数据进行研 究和其他模型化处理，从中提取出有用的关键性数据，从而辅助商业决策，可以挖掘出 影响生产能力的关键因素，如预测机器故障、预测生产销售额、决定库存量、批发点分 布的规划、调度等，甚至在企业危机管理中也得到了普遍的应用。 ( 2 ) 在科学探索中的应用：近年来，在尖端科学的探索中广泛用到数据挖掘技术。 如数据挖掘在生物学上的应用主要集中于分子生物学特别是基因工程的应用上，通过用 计算生物分子系列分析方法，尤其是基因数据库搜索技术已在基因研究上作出了重大的 贡献。例如，d n a 序列分析被认为是人类征服顽疾的最有前途的公关课题。已有大量 大连理t 大学硕士学位论文 的文献对其做出研究，同时，数据挖掘也进入到近些年发展起来的代谢组学领域中。本 文正是利用数据挖掘的方法对基因及代谢数据进行分析。 ( 3 ) 在i n t e m e t 上的应用：i l l t e m e t 上有海量的数据信息，怎样对这些数据进行复杂 的应用成了现今数据库技术的研究热点。数据挖掘就是从大量的数据中发现隐含的信息 和规律性的内容，解决数据的应用质量问题。充分利用有用的数据，废弃虚伪无用或冗 余的数据，是数据挖掘技术的最重要的应用。除了w e b 内容，其服务效率也很重要， 通过对w e b 日志数据挖掘，可以提供网站服务效率全方位的信息，从而有助于找到平 衡服务器负荷，优化传输减少拥塞的方法，缩短用户等待时间，提高系统效率和服务质 量。 1 3 本文的主要工作 复杂体系的数据处理通常包含降维或特征提取，分类，聚类处理。本文以色谱指纹 和基因数据为应用背景，对复杂体系的分类和特征选择这两种数据处理技术进行研究， 主要工作如下： ( 1 ) 研究分类方法，对朴素贝叶斯的分类理论进行研究，提出了二次建模的加权朴 素贝叶斯分类器( r w n b c ) 算法。r w n b c 着眼于分类器整体技术和属性选择，在训练阶 段仅仅产生所需要的频率表，在修正和测试阶段进行属性选择和加权，修正分类器模型， 生成了二次建模的加权朴素贝叶斯分类器( r w n b c ) ，并成功地将其应用于卷烟烟丝的 分类问题上。实验结果表明，与朴素贝叶斯相比，r w n b c 具有较高的分类正确性。 ( 2 ) 研究属性选择技术，对三种经典的属性选择策略( f i l t e r 、w r a p p e r 和e m b e d d e d ) 进行分析，根据f i l t e r 和w r a p p e r 这两种策略的优缺点，提出了一种新的基于r e l i e f f 的 w r a p p e r 属性选择方法。该方法结合了f i l t e r 和w r a p p e r 属性选择算法的优点，从大量 的变量中挑选与问题相关的预测能力较强的特征，在提高分类准确率的同时，克服了 w r a p p e r 固有的时间复杂度较高的缺点。 最后，基于色谱指纹和基因数据通过分类准确率等指标验证了算法的有效性。 文章的组织结构如下： 第一章绪论，主要介绍课题的研究背景及意义。 第二章复杂体系的相关技术。分类和属性选择是复杂体系数据处理的两个主要内 容。第二章介绍了现有的主要分类算法和属性选择算法。 第三章基于二次建模的加权的朴素贝叶斯分类器( r w n b c ) 。首先叙述了朴素贝叶 斯的基本理论，提出了一个基于二次建模的加权的朴素贝叶斯分类器，设计并实现了该 算法，并将其应用于烟草色谱指纹的数据处理。 几类复杂体系的分类及属性选择问题研究 第四章基于r e l i e f f 的w r 印p e r 属性选择方法。本章对两种流行的属性选择技术： f i l t e r 和w r 印p e r 进行分析，结合二者的特点，提出了一种新的属性选择算法：基于r e l i e f f 的w r a p p e r 技术，给出了该算法的实现。 第五章结论，对所做的工作进行总结。 大连理工大学硕士学位论文 2 复杂体系处理的相关技术 复杂体系中一般包含大量的数据，随着对复杂体系的研究日益广泛，如何有效地处 理这些海量的数据一直是大家关注的问题，相应的数据分析和处理技术也日益成为人们 研究的重点。数据挖掘正是应对海量的数据并从中找出有用的信息的一门技术，它处理 复杂体系数据，能从数十、数百乃至数千的变量中找到与问题有关的部分变量，一方面 将数据降维，有助于提高学习方法的性能，一方面确定关键特征，使得可以帮助人们正 确了解复杂体系问题的本质，确定问题的关键，更高效地进行诊断、治疗或做出决策。 复杂体系的数据处理通常包含分类，聚类和属性选择等，以下从分类和属性选择两方面 进行重点介绍。 2 1 分类方法概述 2 1 1 分类的定义及流程 分类问题可以表述成如下的数学形式【1 0 】( 假设对两类问题来说) ：已知训练集包含 m 个样本点丁= 妣，) ，。) ，( ，y 。) y ) ”，其中t x ( x = 尺“) 是输入，其分量称为 特征或属性；c ；c = 一1 1 是输出。目标是对一个新的输入z ，推断它所对应的输出c 是 1 还是1 。问题的实质是找到一个把上的点分成两部分的规则。该规则可以等价为寻 找x ；尺“上的一个实值函数g o ) ，用决策函数，0 ) = s 萨( g ) ) 来判断任一输入石对应 的c 值。可见分类学习机即是构造决策函数的方法或算法，由两类分类器可以推广到多 类问题。 拥有一个完整的分类系统和一整套的数据处理流程对实现复杂系统的自动分类是 必不可少的。通常来说，一个完整的分类系统主要包括如下几个部分：数据采集、数据 预处理、数据的特征向量空间表示、训练分类器、分类器分类和性能评价。图2 1 示例 了代谢数据分类处理的流程，首先通过采集代谢物( 如血浆、尿液、组织提取液等) ， 然后通过化学实验，利用色谱分析仪器得到代表代谢物中各个成分以及各成分含量的指 纹谱图数据，形成样品峰表，其中数据预处理可能包括属性降维、离散化等处理，最后 将预处理之后的样品分成训练样品集和测试样品集，用训练样品集对学习算法进行训练 得到学习模型用于预测，对测试样品集的分类结果进行性能评估。用于结果的评估的准 则根据实际需要的不同而有所不同，一般的分类评价标准有准确率、召回率、特异性、 灵敏度等。 几类复杂体系的分类及属性选择问题研究 图2 1 代谢数据分类处理的基本流程 f i g 2 1 t h ed a s s i f i c a t i o np r o c e d u r eo fm e t a b o l i cd a t a 2 1 2 分类算法 分类是数据挖掘中一项非常重要的任务。其目的是通过学习训练出一个分类函数或 构造一个分类模型( 也称分类器) ，该函数或模型能将数据集中的样本映射到给定类别 中的某一个类别。分类可用于预测，预测的目的是从利用历史数据记录中自动推导出对 给定数据的推广描述，从而能对未来数据进行预测。分类方法大致可以归结为四种类型： 基于距离的分类方法、决策树分类方法、贝叶斯分类方法和规则归纳方法。以下对这几 类算法中包含的算法做具体的介绍。 ( 1 ) k 最近邻算法 k 最近邻算法僻n e a r e s tn e i 曲b o r ) 【1 1 l ：该算法是一种基于样本间距离进行分类的算 法，它需要对样本间的相似性进行度量，在实际应用中通常采用样本间的距离来表示它 们之间的相似性。k 最近邻算法将原始数据集分为训练集和测试集，假定每个类包含多 个训练数据，且每个训练数据都有一个唯一的类别标记。k 最近邻分类的基本原理就是 对待分类的样本计算其和训练集中每个样本的距离，取与其距离最近的k 个训练数据， 统计k 个数据中每类样本的个数，个数最多的那一类则为待分类样本的类别。 ( 2 ) 决策树 决策树( d e c i s i o nt r e e ) 是一个类似于流程图的树结构，其中每个内部节点表示在一 个属性上的测试，每个分支代表一个测试输出，而每个树叶结点代表类或类分布。树的 最顶层是根结点，一棵典型的决策树如图2 2 所示。这是一个关于是否去打球的决策， 大连理工大学硕士学位论文 包含3 个属性( o u t l o o k ，h u m i d i t y 和w i n d y ) ，属性在决策树中属于内部节点，而叶子节 点是决策( 在本例中是去打球或不去) ，每一条从根节点到叶子节点的路径都代表一个 根据天气状况是否去打球的决策过程。决策树分类方法采用自顶向下的递归方式，在决 策树的内部结点进行属性值的比较并根据不同的属性值判断从该结点向下的分支，在决 策树的叶节点得到结论。所以从决策树的根到叶结点的一条路径就对应着一条合取规 则，整棵决策树就对应着一组析取表达式规则。 图2 2 一棵简单的决策树 f i 昏2 2 as a m p l ed e c i s i o nt 嗽 如何构造一棵较好的决策树昵? 研究结果表明，一般情况下，树越小则树的预测能 力越强。由于构造最小的树是n p 困难问题，因此只能采取用启发式策略来挑选逻辑判 断或属性。要构造尽可能小的决策树，关键在于选择恰当的逻辑判断或属性，属性选择 依赖于各种对子集的不纯度( i i i l p u r i t y ) 度量方法。不纯度度量方法包括信息增益 ( i n f o 加a t i o ng a i n ) 、基尼指数( g i n i i n d e x ) 、信息增益比( g a i nr a t i o ) 、j m e a s u r c 、距离度 量( d i s t a n c em e a s u r e ) 、矿统计、g 统计、证据权重( w e i g l l to fe v i d e n c e ) 、最小描述长度 ( m u p ) 、正交法( o n 0 9 0 n a l i t ym e a s u r e ) 、相关度( r e l e v 柚c e ) 和r e l i e f 等。不同的度量有不 同的效果，特别是对于多值属性，选择合适的度量方法将产生大大不同的结果 决策树是一种基于规则的分类器，由于规则具有明确的含义，因此它非常适合于采 用二值形式描述的样本。但随着样本集的增大，规则库也会随之增大，使得对数据的敏 感性增强，从而容易产生过拟和问题，这也就限制了决策树应用于大规模的生物数据分 类。 ( 3 ) 支持向量机 几类复杂体系的分类及屙| 生选择问题研究 支持向量机算法( s u p p o r tv e c t o rm a c h i n e ) 【1 3 】是基于结构风险最小化原理，其基本原 理是通过将低维空间不可分的向量映射到高维空间，寻找到高维空间的一个超平面，使 得它能够尽可能多的将两类数据点正确的分开，如图2 3 所示，同时使分开的两类数据 点距离分类面最远。 特征 _ 映射 在低维空问比较复杂的数据 在高维空问较简单 图2 3s v m 空间映射 f i g 2 3s p a c em a p p i n go fs v m 甲面 图2 4 线性可分情况下的支持向量机 f i g 2 4 s v m0 nt h ec i r c u m s t a n c co fl i n e a f p a r a b l e 在线性可分的情况下，支持向量机的计算可用图2 4 的两维情况来加以说明。其中， 实心原点和空心原点分别代表两类不同的样本，其中有多个平面( s 印a r a t eh y p e 叩l a n e ) 大连理工大学硕十_ 学位论文 可以将两类样本分开，但是存在一个最优平面( o p t i m a lh y p e 印l a n e ) 。两、凰分别为过两 类中离最优分类线最近的样本且平行于最优分类线的直线，它们之间的距离叫作分类间 隔，其上的样本工1 z 2 即为支持向量。所谓最优平面就是要求平面不但能将两类正确分 开，即训练错误率为o ，而且使分类间隔( m a r 西n ) 最大化。 支持向量机算法主要具有以下几个优点： 它是专门针对有限样本情况的，其目标是得到现有信息下的最优解而不仅仅是 样本数趋于无穷大时的最优值： 算法最终将转换成一个二次型寻优问题，从理论上说，得到的将是全局最优点， 克服了在神经网络方法中无法避免的局部极值问题： 算法将实际问题通过非线性变换转换到高维的特征空间( f e a t u r es p a c e ) ，通过在 高维空间中构造线性判别函数来实现原空间中的非线性判别函数，特殊性质能保证机器 有较好的推广能力，同时它巧妙地解决了维数问题，其算法复杂度与样本维数无关，而 取决于最终计算得到的支持向量的数目。 s v m 是一种有坚实理论基础的新颖的小样本学习方法。它基本上不涉及概率测度 及大数定律等，因此不同于现有的统计方法。从本质上看，它避开了从归纳到演绎的传 统过程，实现了高效的从训练样本到预报样本的“转导推理”( t r 锄s d u c t i v ei n f e r e n c e ) ， 大大简化了通常的分类和回归等问题。支持向量机算法在解决小样本、非线性及高维模 式识别问题中表现出了许多特有的优势，并成功的应用到许多领域，如：人脸识别、手 写体识别、文本分类等。 ( 4 ) 贝叶斯网络 贝叶斯网络能够完成决策、诊断、预测、分类等任务，目前已在经济预测、企业管 理、语音文字识别、文本分类、医疗系统等诸多领域获得了成功的应用。贝叶斯网络分 类器是一种基于概率的分类器，它能够预测出一个数据对象属于某个类别的概率，具有 较强的理论基础。它最终构建一个有向无环图的模型，表示随机变量之间复杂的不确定 性关系，并提供了一种自然的表示因果关联的方法，可以用于发现数据间的潜在关系。 贝叶斯网络用于分类主要分成网络学习、参数学习和推理( 属于类别向量中的哪一 类) 。其中网络学习一般根据专家经验或在属性空间执行搜索算法、如爬山算法、l ( 2 算法等；参数学习是为了建立条件概率表( c p d ，进而根据其结构与条件概率表进行推 理。推理一般分为精确推理和近似推理两个部分，主要研究高效、适用于不同网络的推 理算法。精确推理算法有基于直接计算的和基于连接树的，如桶消元算法和联合树算法。 但是当精确推理无法承受大规模的数据集运算，必须通过近似推理来解决，近似推理算 法包括基于搜索的和基于随机模拟的算法，如m c m c 算法、随机抽样算法。人们也使 几类复杂体系的分类及属性选择问题研究 用混合的推理算法，如结合连接树和随机模拟的算法。图2 5 表示一个贝叶斯网络精确 推理的例子。该网络描述了某个家庭进入盗贼或发生地震，随后报警玲响，并且j o l l l l 和m a r y 听到报警铃后打电话房子主人的概率情况。其中有五个属性节点，分别是 b u r 舀a r y 、e a n h q u a k e 、魁a 咖、j o h n c a l l s 和m a r y c a l l s ，在每一个属性旁边的表格即为 该属性的条件概率表。人们根据该网络的各个属性的关联情况以及条件概率表做出推理 决策。 制塞哕 m 1 l爻叩7 be p ( a ) tt0 9 5 tf0 9 4 弋 ft0 2 9 ff 0 0 0 1 、? ap ( j ) 延岁 t 0 9 0 f0 0 5 图2 5 一个简单的贝叶斯网络 f i g 2 5 as a m p l eb a y e s i a nn e t 、7 l r o r k 匦口 同 i 一 圈 贝叶斯网络分类器的主要优点如下： ( 1 ) 贝叶斯网络的推理是经过了先验信息与后验信息进行评定，从信息论的角度看， 它充分利用了所有可以利用的信息，因而结论是合理的、完备的； ( 2 ) 贝叶斯网络善于从不完全的、不精确的或不确定的知识和信息中做出推理； ( 3 ) 随着贝叶斯网络训练经验的积累，预测结果会越来越准确； ( 4 ) 贝叶斯网络的结果是通过概率来表示的。 随着贝叶斯网络得到越来越广泛的应用，逐步形成了贝叶斯网络的更多新方向，如 动态贝叶斯网络、离散时间的贝叶斯网络等。动态贝叶斯网络将静态b n 与时间信息结 合，形成具有处理时序数据的新的随机模型。主要应用在语音识别、说话人识别、视频 跟踪、大信息量处理等方面。离散时间的贝叶斯网络采用时间拓展技术，适合表示带有 时间序列特征的事件多状态、不确定性信息逻辑关系。使贝叶斯网络能够应用于更多领 域，起到了更重要的作用。 大连理工大学硕士学位论文 2 2 属性选择概述 2 2 1 属性选择的重要性及定义 在过去的十多年，属性选择已经在机器学习，模式识别中关于数据的预处理部分变 得非常重要，特别是对于一些高维的数据，如基因数据，代谢数据，质谱数据等。从理 论上讲，属性数目越多，越有利于目标的分类，但实际情况并非如此。在样本数目有限 的情况下，利用很多属性进行分类器设计，无论是从计算的复杂程度考虑，还是分类器 性能都是不适宜的。同时样本的属性通常可分为4 种类型，即有效属性，噪音属性，问 题无关属性和冗余属性。其中有效属性是指对学习算法有积极效果的属性，噪音属性会 对学习算法造成不良影响，问题无关属性指与学习算法无关的属性，而冗余属性指包含 分类有关的信息，但在已有的属性集中添加或删除该属性并不会影响学习算法性能的属 性。 对于特定的任务来说，噪音属性的存在容易使分类算法得出错误的结果，导致错误 分类；冗余和问题无关属性的存在会降低算法的性能。人们通常通过属性选择或提取来 去掉冗余和噪音属性，这是降低复杂度和提高分类精度的有效途径。 属性选择是模式识别、统计学以及数据挖掘等领域一个十分活跃的研究方向，其主 要目的是从原始属性集中删除不具有预测能力或预测能力及其微弱的属性，建立高效的 学习模型。它也是对高维数据进行降维的一种有效手段。当然，不同的应用问题，属性 选择定义的角度会有所不同。以下是从不同角度对属性选择所作的各种定义。 理想化：寻找最小属性子集，该子集是目标概念的充分必要属性子集。 典型：在属性个数为珂的属性集合中选择属性个数为朋的属性子集，所 。+ 。1 。一 训练数据集 二：一二 训练数据集 特征集1 特征降维 、 f机器学习算法1 丁- 交 7 ( 最终评估 ) l 赢度 j 图2 8 打包属性选择的过程 f i g 2 8t 1 l ep r o c e d u r e0 ff e a t u r es e l e c t i o nw i t hw m p p e r 属性选择的一般准则是选择尽可能少，有影响力的属性，从而可以构造简单而快速 的分类器。以下对三种模型的属性选择算法分别进行举例。 ( 1 ) f o c u s 舢m u a l l i m l 9 9 1 年提出的f 0 c u s 算法是机器学习领域最早的一种f i l t e r 特征选择算法 之一。f 0 c u s 以空集状态为搜索起点，采用宽度优先的搜索算法进行搜索，例如当前搜 索的特征子集为( o ，0 ，0 ) ，则下一个搜索的子集为( 1