（计算机应用技术专业论文）面向应用领域特点的分类方法研究.pdf

摘要随着计算机技术的飞速发展，很多领域对分类方法提出了新的要求。如在生物信息学方面，人们通过d n a 微阵列芯片实验可以得到基因表达谱数据，由于其数据高维的特点，如何从基因表达谱数据中选取包含样本分类信息的特征基因，建立合适分类器，是当前生物信息学研究的重要领域；在图象颜色迁移方面，如何进行多值多类标分类并进行多源图像颜色迁移是新的研究课题；在无线传感器领域中，针对事件检测和传感器的特点，如何建立分布式分类检测算法，对分类器提出了新要求。针对这些问题，本文重点研究了若干分类算法，主要工作和成果表现在以下方面：1 针对基因表达谱的特征基因选取问题进行了研究，提出了综合性分类信息指标一g b 指标，将g i n i 指数与类加权b h a t t a c h a r y y a 距离相结合进行无关基因及噪声数据的剔除；采用欧氏距离丢弃高相关性的冗余基因；运用搜索算法得到最终的特征子集。针对两类急性白血病数据集最终提取了2 组包含4 个特征基因的子集；针对四类小圆蓝细胞数据集最终提取了l 组包含7 个特征基因的子集。使用支持向量机和神经网络作为分类器对这些特征基因子集进行分类测试，留一交叉检验和独立测试正确识别率都达到1 0 0 ，本文提取的特征基因子集更精简，优于目前已发表的同类结果。2 将分类与关联规则挖掘相结合建立基于闭合模式的分类器。基因的表达值代表的是基因的三种表达状态：上升、下降和不变。由于基于关联规则的经典算法c b a 等是挖掘所有频繁项目集，对高维基因表达谱进行频繁项集挖掘时，有相当多的模式是冗余的或价值不大的，采用基于闭合模式的分类算法是解决基因表达谱分类途径之一。本文提出了一种基于闭合模式的多类别分类算法d m a c 。针对基因表达数据集的特点采用行枚举思想，通过对行集建立行f p - t r e e ，构造路径枚举树的路径枚举p e a 算法来挖掘闭合模式。提出了权重算法q z ，通过构造权重函数，对分类器无法识别的样本用权重进行判断，改进了二类分类器的性能。在对四类数据集的测试中取得了好的实验结果。算法有效地解决了基于关联规则的多类分类问题。3 本文对处理多属性多类标数据决策树算法m m c 和m m d t 机制进行了研究分析，提出了新的相似度公式s i m 3 。由于s i m 3 综合考虑了类标集的相似度和行为一致性，在此基础上构建的决策树算法s c c _ s p与m m c 及m m d t 相比有更好的性能。针对图像颜色迁移问题，研究了二种单源图像颜色迁移算法，在此基础上提出了一种基于多类标决策树的多源图像颜色迁移算法。以多幅源图像中的图像块作为训练样本，提取其颜色、纹理特征以及类标集，建立基于多源图像的多类标决策树；利用多类标决策树对目标图像各图像块进行分类决策，从而实现对目标图像的颜色迁移，其方法弥补了单源图像迁移参考信息不足的缺点，为多源颜色迁移提供了新的借鉴和参考。4 针对无线传感器网络事件区域检测问题，本文提出一种分布式加权容错分类检测算法。针对无线传感器网络的特点，考虑“邻域的邻域”的容错范围，首先通过邻域节点与其周围节点的信息交换，对邻域节点的状态值进行估计，然后采用加权方法对邻域节点的估计状态值进行加权综合，完成对中心节点的错误检测和分类处理。仿真结果表明，该算法在传感器网络初始错误率达到2 0 的情况下，仍能够检测和纠正9 0 以上的错误。相比其他算法，该算法具有较高的错误检测精度，改善了事件发生区域边界节点的纠错性能，且算法运行时整个网络所消耗的能量适中。关键词特征基因选取，闭合模式分类器，多值多类标决策树，颜色迁移，事件区域检测w i t ht h er a p i dd e v e l o p m e n to fc o m p u t e rt e c h n o l o g y , w ef a c em a n yn e wc h a l l e n g e si nt h ec l a s s i f i c a t i o nf i e l d f o re x a m p l e ，i nt h ef i e l do fb i o i n f o r m a t i c s ，w ec o u l dg e tt h eg e n ee x p r e s s i o np r o f i l eu s i n gd n am i c r o a r r a y s ，a n dt h r o u g ha n a l y s i so f t h ed a t aw eh a v eg o t , w ec o u l dm i n em e a n i n g f u lb i o l o g i c a lk n o w l e d g ea n di n f o r m a t i o no u to ft h ed a t a b e c a u s eb i o l o g i c a ld a t a s e t sa r et y p i c a l l yl o n g , r e c e n tr e s e a r c hh a sc o n c e n t r a t e do ns a m p l ec l a s s i f i c a t i o na n df e a t u r es e ts e l e c t i o n ；i nt h ef i e l do fc o l o rt r a n s f e r , r e c e n tr e s e a r c hc o n c e n t r a t e do na p p l y i n gm u l t i - v a l u e da n dm u l t i - l a b e l e dt om u l t i - i m a g e sc o l o rt r a n s l , i nt h ef i e l do fw i r e l e s ss e n s o rn e t w o r k s ，a c c o r d i n gt ot h ef e a t u r e so fe v e n td e t e c t i o na n ds e n s o rn e t w o r k s ，h o wt oc o n s t r u c td i s n i b u t e da n dw e i g h t e da l g o r i t h mf o rf a u l t - t o l e r a n te v e n tr e g i o nd e t e c t i o na l s op r o p o s e dn e wd e m a n d st oc l a s s i f i e r a i m i n ga tt h e s ep r o b l e m s ，t h i sp a p e rc o n c e n t r a t e so nt h ea l g o r i t h m so fc l a s s i f i c a t i o n t h ew o r kh a sb e e nd o n ea n dt h em a i na c h i e v e m e n t so b t a i n e da r ep r e s e n t e db e l o w ：。，1 a i m i n ga tt h ec l a s s i f i c a t i o no f g e n ee x p r e s s i o nd a t ao f t h et u n l o u rs u b t y p ea n dt h ef e a t u r eg e n es e l e c t i o n , a l la l l - r o u n di n d e xc a l l e dg bi n d e xi sp r o p o s e dt oe l i m i n a t et h ei r r e l e v a n tg e n e sa n dn o i s e ，b yc o m b i n i n gt h eg i n ii n d e xa n dt h eb h a t t a c h a t y y ad i s t a n c e ；t h ei n f o r m a t i v eg e n e s ，a c c o r d i n gt ot h ee u c l i d i a nd i s t a n c e ，a r es a v e db yf u r t h e rd e l e t i n gs o m er e d u n d a n tg e n e sw i t hs t r o n gr e l e v a n c y ；t h ef e a t u r eg e n e sa r es e l e c t e df r o mt h ei n f o r m a t i v eg e n e sw i t hs e a r c h i n ga p p r o a c h e s w eo b t a i n e d2f e a t u r es e t st h a tc o n t a i n e d4f e a t u r eg e n e sf r o mt h ea c u t el e u k a e m i ad a t as e ta n d1f e a t u r es e tt h a tc o n t a i n e d7f e a t u r eg e n e sf r o mt h es r b c td a t as e t u s i n gs v ma n da n na st h ec l a s s i f i e r , t h ea c c u r a c yo fc l a s s i f i c a t i o ni s1 0 0 t h ef e a t u r es e t si nt h i sw o r ka r em o r ec o m p a c ta n ds u p e r i o rt h a np r e v i o u sw o r k 2 c o m b i n i n gc l a s s i f i c a t i o na n dm i n i n go fa s s o c i a t i o nr u l e s ，w ec o n s t r u c t e dt h ec l a s s i f i e rb a s e do nc l o s e dp a t t e r n s g e n ee x p r e s s i o nd a t ar e p r e s e n tt h r e es t a t u so fg e n e s ：r i s i n g ，d e s c e n d i n ga n du n c h a n g i n g t h ec l a s s i ca l g o r i t h m sb a s e do na s s o c i a t i o nr u l e s ，e g c b a ，a r em i n i n ga l lt h ef r e q u e n ti t e m s e t s i nt h ef r e q u e n ti t e m s e t sm i n i n go fg e n ee x p r e s s i o nh ip r o f i l e ，w em a yo b t a i nm a n yr e d u n d a n ta n dv a l u e l e s sr u l e s ，1 1 1 ec l a s s i f i c a t i o na l g o r i t h mb a s e do nc l o s e dp a t t e r ni so n eo ft h ea p p r o a c h e st os o l v et h i sp r o b l e m t i l i sw o r kp r o p o s e dac l a s s i f i c a t i o na l g o r i t h m ,d m a c ，b a s e do nc l o s e dp a r e m a c c o r d i n gt ot h ef e a t u r eo fg e n ee x p r e s s i o n p r o f i l e , w eb u i l dr o wf p - t r e eb a s e do nr o we n u m e r a t i o n , t h e nu s ep e at om i n ec l a s s e dp a r e m s w ea l s op r o p o s e dw e i g h ta l g o r i t h mq zt oi m p r o v et h ep e r f o r m a n c eo fc l a s s i f i e r , r e c l a s s i l y i n gt h eu n r e c o g n i z e dg e n e sb yc o n s t r u c t i n gw e i g h tf u n c t i o n t l l i sa l g o r i t h mi sa l s op r o v e dt ob ec o r r e c ta n de f f i c i e n tb ye x p e r i m e n t si nf o u r - c l a s sd a t as e t s t i l i sa l g o r i t h mi sp r o v e dt ob ee 伍c i e n ti nm u l t i c l a s sc l a s s i f i c a t i o n 3 t h i sp a p e ra n a l y z e dt h ea l g o r i t h mo fm m ca n dm m d t , a n dp r o p o s e dan e wf o r m u l as i m 3w h i c hc o n s i d e r e db o t hs i m i l a r i t ya n db e h a v i o rc o h e r e n c e 1 1 l ed e c i s i o nt r e ea l g o r i t h ms c cs pb a s e d0 1 1t h i sf o r m u l at h e r e f o r eh a sb e t t e rp e r f o r m a n c e st h a n n 伧a n dm m d t a i m i n ga tt h ec o l o rt r a n s f e r , t h i sw o r ka n a l y z e dt h ec o l o rt r a n s f e ra l g o r i t h mo fs i n 西ei m a g e ，a n dp r o p o s e dm u l t i - l a b e l e dd e c i s i o nt r e ea l g o r i t h mo fm u l t i - i m a g e sc o l o rt r a n s f e r s e l e c t i n gm u l t i - - i m a g e sa st h et r a i n i n gs a m p l e sa n dc o n s t r u c t i n gm u l t i - l a b e l e dd e c i s i o nt r e ea c c o r d i n gt ot h ec o l o ra n dt e x t u r ei n f o r m a t i o no fs o u r c ei m a g e s 。c o n s t r u c t i n gm u l t i l a b e l e dd e c i s i o nt r e ea n dm a k i n gu s eo ft h em u l t i - l a b e l e dd e c i s i o nt r e ef o rc l a s s i f i c a t i o n , t h i sw o r kr e a l i z e dt h ec o l o rt r a n s f e ro fo b j e c ti m a g e n l i sa l g o r i t h mt r i e da n dr e a l i z e dc o l o rt r a n s f e ro fm u l t i - i m a g e sw h i c hw a ss u p e r i o rt oc o l o rt r a n s f e ro fs i n g i e - i m a g eb yp r o v i d i n gm o r er e f e r e n c ei n f o r m a t i o n 4 a i m i n ga tt h ep r o b l e mo ff a u l t - t o l e r a n te v e n tr e g i o nd e t e c t i o ni nw i r e l e s ss e n s o rn e t w o r k s ，t h i sp a p e rp r o p o s e sad i s t r i b u t e da n dw e i g h t e da l g o r i t h mf o rf a u l t - t o l e r a n te v e n tr e g i o nd e t e c t i o n c o n s i d e r i n gt h ef a u l t - t o l e r a n te v e n tr e g i o no fn e i g h b o r h o o d sn e i g h b o r h o o d , w ef n s tu s ei n f o r m a t i o ne x c h a n g eb e t w e e nn e i g h b o rn o d e sa n dt h e i rn e a r b yn o d e st oe s t i m a t et h es t a t u so ft h en e i g h b o rn o d e s t h e nw eu s et h ew e i g h t e df a u l t - t o l e r a n ta l g o r i t h mt of u s et h es t a t u so fn e i g h b o rn o d e sf o rf a u l td e t e c t i o no ft h ec e n t r a ln o d e 1 1 1 es i m u l a t i o nr e s u l t ss h o wt h a t9 0 o ff a u l t sc a nb ed e t e c t e da n dc o r r e c t e du s i n gt h i sa l g o r i t h m e v e nw h e n2 0 n o d e sa r ef a u l t y , c o m p a r e dw i t l lo t h e rd e t e c t i o na l g o r i t h m , t h ep r o p o s e da l g o r i t h mi m p r o v e st h ea c c u r a c yo fd e t e c t i n gf a u l t - t o l e r a n te v e n tr e g i o na sw e l la st h ef a u l td e t e c t i o no f b o u n d a r yn o d e so f t h ee v e n tr e g i o n , a n di ta c h i e v e sab e t - t e l b a l a n c eb e t w e e nd e t e c t i o na c c u r a c ya n de n e r g yu s a g e k e yw o r d sf e a t u r eg e n es e l e c t i o n ，c l o s e dp a t t e r n s ，m u l t i - v a l u e da n dm u l t i l a b e l e dd e c i s i o nt r e e ，c o l o rt r a n s f e r , e v e n tr e g i o nd e t e c t i o nv插图索引1 1 论文组织结构图1 42 1 真核生物基因表达过程1 52 2 基于g b 指标和s v m 分类器的特征基因提取结构图2 l2 3 基因的g i n i 指数值升序排列分布曲线图2 32 - 4 基因的b h a t i a c h a r ，y 胡i 离值降序排列分布曲线图2 42 - 5s r b c t 数据集基因的g b 指数分布直方图2 52 6 冗余基因去除算法蹦2 72 7 蹦算法2 82 - 8 后向搜索算法b s s m 2 92 9s m 算法中各信息基因独立测试正确预测样本数3 02 1 0s r b c t 数据集中备特征子集的测试结果3 03 ic b a - r g 算法3 83 2 未采取任何优化的部分行枚举树4 23 3p e a 算法4 33 4 表和行f p - t r e e ( 最小支持数为3 ) 4 43 5 行6 的路径枚举树( 最小支持数为3 ) 4 63 5v i t a e 算法4 63 5q z 权重算法4 74 - 1 处理多值属性多类标数据的决策树算法5 54 2 灰度图像上色h i s t 算法6 54 3h is t 算法与r e i n h a r d 算法、w e ls h 算法的结果图比较6 64 4 基于高斯混合模型区域颜色迁移算法结构图6 74 5 颜色图像样本集分类结果比较6 94 6 变色彩绘图像的迁移效果比较7 l4 7 褪色彩绘图像( 灰度图像) 的迁移效果比较7 24 8 灰度共生矩阵提取纹理特征7 34 - 9 基于标准质心k 均值算法7 44 1 0 对源图像的预处理结果7 44 1 l 部分源图像7 74 1 2 多源图像颜色迁移示例一7 74 - 1 3 多源图像颜色迁移示例二7 85 1容错事件区域检测模型8 l5 - 2。邻域的邻域”双重检测机制8 25 3 分布式加权容镨分类算法8 3图图图图图图图围困图图图图图图图图图图图图图图图图图图图圈图图图图图5 - 4 阁值o ( 横坐标) 与修正后仍存在错误率关系图8 65 5 采用加权检测算法对节点错误模型的检测结果8 75 - 6 采用最优门限算法对节点错误模型的检测结果8 75 - 7 加权容错分类算法与最优门限算法性能比较曲线图8 75 8 事件发生区域处于传感器网络中两类错误模型模型仿真9 05 - 9 事件发生区域在边界的节点错误模型图9 05 1 0 阈值中与修正后仍存在错误率关系图( 边界模型) 9 05 1 l 采用加权容错分类算法对节点错误模型的检测结果( 边界模型) 9 05 1 2 采用最优门限算法算法对节点错误模型的检测结果( 边界模型) 9 05 1 3 加权分类算法与最优门限算法性能比较曲线图( 边界模型) 9 l5 - 1 4 事件发生区域在边界的两类错误模型图9 2i x图图图图图图图图图图图表1 1表2 - 1表2 2表2 - 3袁2 4表2 - 5表2 - 6表2 7表2 - 8表2 - 9表2 1 0表3 - 1表3 - 2表3 - 3表3 - 4袁3 - 5表3 - 6表3 7表4 - l表4 2表4 3表“表4 5表4 6表4 7表5 1表5 - 2表格索引基因表达谱数据格式2急性白血病的基因表达谱数据集1 7急性白血病的训练样本集1 8小圆蓝细胞样本划分情况表1 8s r b c t 数据集不同基因个数独立测试情况2 4不同阀值f 得出的基因及独立测试结果2 8急性白血病数据集特征基因子集1 及其描述3 l急性白血病数据集特征基因子集2 及其描述3 l急性白血病数据集不同方法提取的特征基因数量及性能3 ls r b c t 数据集最优子集的基因及其描述3 2s r b c t 数据集的实验结果比较情况3 2水平格式的数据集4 2垂直格式的数据集4 4s u p 变化情况下的实验结果4 9c o n t 变化情况下的实验结果4 9s u p 、c o n f 最优情况下的实验结果4 9不同算法在训练集的预测准确率5 0不同算法在测试集的预测准确率5 0有关报刊征订的具有多值属性的多类标训练数据5 3实验数据属性的描述6 0根据属性值判断客户类型的规则6 0参变量n 6 0参变量d 谚6 l参变量s u p n 6 l参变量埘h 。6 l加权容错分类算法相关定义8 3算法性能参数列表8 8x原创性声明本人声明，所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得中南大学或其它单位的学位或证书而使用过的材料。与我共同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明。作者签名：旌日期：2 珥年为冱日关于学位论文使用授权说明本人了解中南大学有关保留、使用学位论文的规定，即：学校有权保留学位论文，允许论文被查阅和借阅；学校可以公布学位论文的全部或部分内容，可以采用复印、缩印或其他手段保存学位论文；学校可根据国家或湖南省有关部门规定送交学位论文作者签名：趁导师签名作者签名：兰l 盈导师签名博士学位论文第一章绪论第一章绪论本章首先介绍了论文的研究背景，阐述了研究意义，分析了当前相关领域的研究现状，然后叙述了本文的研究目的和内容，给出了全文的组织结构。1 1研究背景与意义随着数据库技术和网络的迅速发展，数据库中存储的数据爆炸性的增长，数据挖掘是从数据集中识别出有效的、新颖的、潜在的、有用的以及最终可理解模式的高级处理过程，一般包括数据选择、数据清理、数据集成、数据变换、开采挖掘、模式评估、知识表示等阶段“1 脚数据挖掘是一门交叉学科，它汇聚了不同领域的技术，其中包括数据库、人工智能，数理统计、可视化、并行计算和机器学习等。通过数据挖掘，可以从数据库中提取有趣的知识、规则和高层信息发现的知识可以用于决策、过程控制、信息处理和查询处理等。因此，数据挖掘被信息产业界认为是计算机学科重要的前沿领域之一，对信息产业有重要应用前途1 3 】分类技术是一种根据输入数据集建立分类模型的系统方法，它是数据挖掘中应用领域极其广泛的重要技术之一。至今已提出了多种分类算法，主要有决策树、关联规则、神经网络、支持向量机和贝叶斯、k - 临近法、遗传算法、粗糙集以及模糊逻辑技术等嘲嘲。大部分技术都是使用学习算法确定分类模型，拟合输入数据中样本类别和属性集之间的联系，预测未知样本的类别。训练算法的主要目标是建立具有好的泛化能力的模型，该模型能够准确地预测未知样本的类别各种分类算法有其自身的优劣，适合于不同的领域嘲。目前随着新技术和新领域的不断出现，对分类方法提出了新的要求下面对若干应用领域的分类新问题进行简要分析，阐述本文的研究背景：( 1 ) 基因表达谱中特征提取与分类2 0 世纪8 0 年代末，人类基因组计划( h u m a ng e n o m ep r o j e c t ， l g p ) 的启动推动了生物信息学的产生和蓬勃发展。人类基因组计划的直接结果是获得了大量不连续的数据。这些数据的收集、存储，并进行分析、解释，从中获取有用的生物学信息，成为生物信息学迫切要解决的问题咖。作为一种重要的数据处理分析技术，数据挖掘技术因其在大规模数据处理方面的卓越能力而在生物信息学领域具有良好的研究与应用前景n 町。生物信息学中的数据挖掘研究仍然处于起步阶段，有很多问题需要解决。基因表达谱数据分析是目前生物信息学研究的热点和重点“”。基因芯片技术博士学位论文第一章绪论已经成为大规模提取和探索基因表达数据的强有力手段。基因芯片( g e n ec h i p ) ，又称d n a 微阵列( m i c r o a r r a y ) ，是由大量d n a 或寡核苷酸探针密集排列所形成的探针阵列，其基本原理是通过杂交检测信息。通过基因芯片可以得到包含多个基因在不同生理过程中( 如代谢，应激，癌变和发育等) 的一组表达数据，称为大规模基因表达谱。对基因表达谱数据，在大规模数据集上进行分析、归纳，可以了解基因表达的时空规律，探索基因表达的代谢控制，了解基因的功能，理解遗传网络，提供疾病发病机理的信息。研究基因表达谱数据的处理和分析方法已成为生物信息学发展的一个重要方向n 叭“。通常有p 个基因探针的m r n a 或d n a 芯片检测n 个m r n a 或d n a 样品的基因表达谱数据可由二维实数矩阵x = o 【i i ) 表示。其中，矩阵第i 行对应于第i个基因，第j 列对应于第j 个样品，而矩阵的每个元素粕纪录了第i 个基因在第j 个样品中的m r n a 或d n a 表达水平急性白血病基因表达谱数据格式如表i 1 所示：第一行是样本标号，第一列是基因编号。表中的数值为基因在样本中的表达水平值。表i - 1 基因表达谱数据格式a f f x - b i o & 5 越a f f ) ( b i o b - m 越a f f x - b i o & 3 址”救8 5 f 缸利用基因表达谱数据，建立起有效的分类模型，为临床诊断提供一种客观、准确的方法，具有极大的实际应用价值”。由于基因表达谱数据包含了大量的特征基因数目，一般均是几千个，而样本训练数目只有几十左右，高维数据带来了“维数发难”的问题，因此提取出特征基因子集是非常重要的，它不仅是基因表达谱数据识别的核心内容，也是最终构建分类器的关键所在。如何将数据挖掘的方法有效地运用到基因表达谱的分析研究过程，提高分析效率，是目前人们致力研究的热点问题n m 。( 2 ) 多值多类标决策树与多源图像颜色迁移决策树是分类模式中有效的、能够处理大量数据集、计算量小、生成规则易于理解的方法，因此被广泛地应用。目前众多的决策树算法都是针对记录的属性( 包括分类属性) 只取单一值的数据进行分类的，而现实中我们经常会遇到多值也憎do啪弗狮埘埘md一小“心鹊一讲博士学位论文第一章绪论属性多类标号数据的分类处理问题。州嘲，多类标学习任务在现实世界中的应用是很广泛的例如，在文本分类中，每个文件可能属于多个已定义的主题。力町n ”嘲：在视图分类中，每个图像可能属于多个类，比如沙滩和市区等吼1 ；在性能基因系统中，每个基因可能关联多个性能类集，比如新陈代谢，转基因和蛋白质合成等功能嘲嘲在这些例子中，每个在训练集中的实例被关联于一组类标记的集合，传统的决策树算法不能直接应用于多值属性多类标数据的分类处理问题，其研究还很不成熟洲嘲。而多值属性多类标数据分类在图象检索，颜色迁移，文本分类有十分重要的作用，值得深入研究颜色迁移是数字图像处理的一个新兴领域，现阶段的研究主要是针对单源图像的颜色迁移，即将颜色从一幅源图像迁移到另一幅目标图像中嘲嘲。单源图像的颜色迁移实际上要解决以下问题：基于给定的图像a 和图像b ，合成一幅新的图像b ，使其同时具有a 的颜色和b 的形状等遗传信息，即图像b 在不改变它所表达的形状信息的情况下，学习了图像a 的颜色基调，我们把这个过程称为图像的颜色迁移，并称图像a 为颜色图像，图像b 为形状图像目前的颜色迁移算法大多局限于单源图像的色彩迁移，要求形状图像和颜色图像的内容非常近似，而实际色彩迁移中形状图像内容涉及到多幅颜色图像的内容，单源图像的色彩迁移难以满足内容丰富的目标图像的参考色彩需求。研究多源图像的色彩迁移有现实意义，可以利用多值多类标决策树对目标图像各图像块进行分类决策，从而实现对目标图像的颜色迁移，弥补单源图像迁移参考信息不足的缺点，为多源颜色迁移提供新的借鉴和参考。( 3 ) 无线传感器网络事件区域检测与分布式容错分类无线传感器网络是目前新兴技术之一，用途非常广泛洲咖其中一个重要应用是监控环境中异常事件的发生，并找到事件发生区域咖嘲例如，利用传感器网络监控工厂有毒化学物质的泄漏，当泄漏事件发生时，必须充分利用传感器节点返回的状态信息，判断事件发生节点密集的区域及其位置，从而有效阻止泄漏事故的扩散。无线传感器网络由部署在检测区域中的大量节点组成，每个节点都具有一定的计算、感知能力以及有限的能量，其目的是协作地感知、采集和处理网络覆盖区域中感知对象的信息，并发送给观察者。无线传感器网络通常具有自组织无监督、能量有限的特点嘲。考虑到经济可行性，每个传感器节点都是低端的不可靠的设备，存在节点出错的可能性，节点出错会产生虚假的信息，从而影响对事件区域检测的准确度。事件区域检测可以归结为分类问题，即根据观察值进行决策分类，以纠正错误的节点，提高检测的准确度。由于无线传感器网络的特点，采用传统的集中式博士学位论文第一章绪论处理方法是不适宜的，因为频繁的通信使得节点能量消耗很大，采用分布式的算法可以有效地减少因网络内部计算而消耗的能量。针对其特点研究分布式的检测分类算法有重要的意义。综上所述，由于应用领域的多样性和复杂性，很难有通用的分类算法能解决各个领域的分类问题。针对不同领域的特点，设计和实现相关算法是本文的主要研究工作，本文主要致力于针对高维、多值多类标和分布式容错分类问题进行研究，设计并实现相关的分类算法，并对其性能进行分析1 2 研究现状1 2 1 相关技术的研究现状分类可以采用决策树、基于关联规则、支持向量机和贝叶斯等方法，其国内外研究现状如下：( i ) 决策树决策树是一个树结构的分类模型，其中每个内部节点表示在一个属性上的测试，每个分枝代表一个测试输出，而每个叶子节点代表类或类分布。树的最顶层节点是根节点。i d 3 算法是较早的决策树归纳算法，它是1 9 8 6 年由q u i n l a n 提出的嘲。该算法利用信息论中的互信息( 信息增益) 寻找数据库中具有最大信息增益的属性字段，建立决策树的一个节点，再根据该属性字段的不同取值建立树的分支。在每个分支子集中重复建立树的下层节点和分支过程。这种方法的优点是描述简单、分类速度快。但i d 3 算法是借用信息论中的互信息作为单一属性能力的度量，其启发式函数并不是最优的，同时互信息的计算依赖于属性取值的较多特征，而这一属性不一定最优；对i d 3 算法的早期改进算法主要是c 4 5 嘲、后期的改进算法主要有p u b l i c 等嘲。i d 3 等算法对于小的数据集是很有效的，但当用于现实世界中非常大的数据挖掘时，有效性和可伸缩性就成了需要关注的问题。大部分决策树算法都限制训练样本驻留主存，这一限制制约了这些算法的可伸缩性，为解决这一问题，一些可伸缩性的决策树算法相继推出，如s l i q b 耵、s p r i n t 口力、r a i n f o r e s t 嘲算法等。s p r i n t 和s l i q 对非常大而不能放入主存的驻留磁盘的数据集进行预排序。s p r i n t 使用与s l i q 不同的属性表数据结构，易于并行化，增强了算法的可伸缩性。s p r i n t 算法的优点是在寻找每个结点的最优分裂标准时变得更简单。其缺点是对非分裂属性的属性列表进行分裂变得困难。解决的办法是对分裂属性进行分裂时用哈希表记录下每个记录属于哪个孩子结点，若内存能够容纳下整个哈希表，其4博士学位论文第一章绪论他属性列表的分裂只需参照该哈希表即可。由于哈希表的大小与训练集的大小成正比，当训练集很大时，哈希表可能无法在内存容纳，此时分裂只能分批执行，这使得s p r i n t 算法的可伸缩性仍然不是很好( 2 ) 基于关联规则的分类1 9 9 8 年在纽约举行的数据库知识发现国际会议上新加坡国立大学的l i u 等人提出了基于分类关联规则( c l a s s a s s o c i a t i o nr u l e ) 的关联分类算法c s a = j( c l a s s i f i c a t i o nb a s e do na s s o c i a t i o n ) ，关联分类在数据挖掘领域内引起广泛关注。目前中国、美国和加拿大等国家都设立了国家自然科学基金进行这方面的研究许多学者目前正在进行这方面的工作，并且在分类算法上先后相继取得了一批研究成果，代表算法有c b a 嘲，c 姒r h 帕，c p a r m l 和c a a r “妇等。c b a 算法分两个步骤构造分类器第一步：采用经典a p r i o r i 算法发现所有关联规则，即右部为类别属性值的类别关联规则( c l a s s i f i c a t i o na s s o c i a t i o nr u l e s ，c a r ) ；第二步：从已发现的c a r 中选择高优先度的规则来覆盖训练集。c b a算法的优点是其分类准确度较高，在许多数据集上比c 4 5 更精确存在的主要问题是采用a p r i o r i 算法产生大量分类关联规则，消耗的系统资源多。当遇到高维数据库时，分类模型的准确度将显著地下降。基于多维关联规则的分类算法c m a r ( c 1 a s s i f i c a t i o nb a s e do nm u l t i p l ec l a s sa s s o c i a t i o nr u l e s ) 是利用f p - g r o w t h 算法挖掘关联规则，建立类关联分布树f p _ 树。采用c r _ 树( c l a s s i f i c a t i o nr u l et r e e ) 结构有效地存储关联规则。基于置信度、相关性和数据库覆盖来剪枝。分类的具体执行采用加权x 2 来分析与c b a 和c 4 5 相比，c m a r 性能优异且伸缩性较好。但c m a r 优先生成的是长规则，对数据库的覆盖效果较差；利用加权工2 统计量进行分类，会造成x 2 统计量的失真，致使分类值的准确程度降低。2 0 0 3 年，】【y i n 提出了一个称为预测型关联规则的分类算法c p a r ( c l a s s i f i c a t i o nb a s e do np r e d i c t i v ea s s o c i a t i o nr u l e s )避开了使用资源消耗大的关联规则发现算法采用贪婪算法直接从训练数据集中挖掘关联规则，采用基于信息熵的方法选择最优的5 个规则用来分类一个实例，其缺点在于如何选择最优的规则，c p a r 方法产生的规则数小于c m a r 算法，在分类准确度上与c m a r 算法相当。邹晓峰等人研究了模糊分类关联规则的挖掘嘲，赵传申等对c i l a r 进行了改进咖( 3 ) 支持向量机支持向量机( s u p p o r tv e c t o rm a c h i n e ，s v m ) 是数据挖掘中的一项新技术，是借助最优化方法解决机器学习问题的新工具。它最初于2 0 世纪9 0 年代由v a p n i k提出“”，近年来在其理论研究和算法实现方面都取得了突破性进展，开始成为克服“维数灾难”和“过学习”等传统困难的有力手段。博士学位论文第一章绪论支持向量机是一种基于统计学习理论的机器学习方法，s 可以自动寻找出那些对分类有较好区分能力的支持向量，由此构造出的分类器可以最大化类与类的间隔，因而有较好的适应能力和较高的分准率该方法只需要由各类域的边界样本的类别来决定最后的分类结果嘲支持向量机算法基本思想是通过用非线性映射将输入空间变换到一个高维空间，在这个高维空问中寻找输入变量和输出变量之间的一种非线性关系。算法仅使用高维空间中的内积，通过引入核函数，高维空间的内积运算就可用原空间中的函数来实现，通过采用适当的核函数就可实现某一非线性变换后的线性分类，而计算复杂度没有增加，从而在一定程度上避免了维数灾难问题。它以最大化分类间隔构造最优分类超平面来提高分类器的泛化能力，较好地解决了非线性、高维数、局部极小点等问题。s v m 最初是针对解决两类分类问题提出的，要将其推广到多类分类问题，需要构造多类s v m 分类器，其构造方法主要有两种：一种是以w e s t o n 在1 9 9 9 年提出的多类算法为代表咖。只需将原始的两类改为k 类，就很自然地将两类分类s v m 转化为k 类分类s 。这种算法选择的目标函数十分复杂，变量数目过多，计算复杂度也非常高，实现困难，所以只在小型问题的求解中用到。另一种构造方法的基本思想是通过组合多个两类分类器，这类方法目前主要有一对多算法、一对一算法、决策导向无环图和基于二叉树的多类分类方法等嘲侧。一对多算法对于k 类问题构造k 个两类分类器，第i 个s 、i l 用的i 类中训练样本作为正的分类样本，而将其它的样本作为负的样本，最后的输出是两类分类器输出的最大的那一类。一对一算法在k 类训练样本中构造可能的两类分类器，每类仅在k 类中的两类训练样本上训练，结果共构造珏( k 1 ) 2 个分类器，组合这些两类分类器并使用投票法，得票最多的类为样本点所属的类基于二叉树的支持向量机的多类分类方法继承了一对多方法的训练支持向量数少及一对一方法训练速度快的优点，通过在分类阶段结合二叉树，大大提高了支持向量机的分类速度；同时也克服了一对一、一对多、决策导向无环图方法可能出现的无法分类区域的存在，提高了支持向量机多类分类的性能。郑春红等提出了一种基于模糊方法的f s 吼1 李昆仑等提出了一种模糊多类支持向量机模型，即f m s 嘲。该方法是在w e s t o n 等人提出的多类s v m 模型中引入模糊成员函数，针对每个输入数据对分类结果的不同影响，该模糊成员函数为其赋予不同的值，由此得到不同的惩罚值由于s v m 的特性，其在各个领域得到广泛应用嘲，如基于支持向量机的蛋白质