（信号与信息处理专业论文）基于贝叶斯方法的分类问题研究.pdf

摘要 数据挖掘是信息技术自然演化的结果，是从大量数据中提取或“挖 掘 未知的、有价值的模式或规律等知识的复杂过程。其中，对数据 进行分类是数据挖掘领域研究的重要课题。贝叶斯方法由于具有坚实 的数学理论基础以及综合先验信息和数据样本信息的能力，而被广泛 研究与应用。本文重点研究了基于贝叶斯方法的数据分类算法，主要 工作和成果表现在以下两个方面： ( 1 ) 针对无线传感器网络事件区域检测问题，提出分布式加权分 类容错检测的思想：考虑“邻域的邻域”的容错范围，首先通过邻域 节点与其周围节点的信息交换，对邻域节点的状态值进行估计，然后 采用加权方法对邻域节点的估计状态值进行加权综合，通过贝叶斯方 法对加权的阈值进行推导，完成对中心节点的错误检测和分类处理。 针对传感器节点规则排列和非规则排列两种情况，分别建立相应的无 线传感器网络事件区域容错检测模型，对规则排列的模型提出基于固 定权重的加权分类容错检测算法，而对非规则排列的模型，则提出基 于距离加权的分类容错检测算法。实验结果表明，这两种算法均具有 较高的错误检测精度，且算法运行时整个网络所消耗的能量适中。 ( 2 ) 多类标数据中的样本可能属于一个或多个类标，因此其分类 问题较单类标分类更为复杂。本文提出一种新的多类标学习算法，首 先针对多类标数据的特征属性维数高的特点，采用l l e 算法对多类 标数据的特征属性进行降维，提取能较完整描述数据的一组低维特征 属性集；然后将多类标样本集按所属的类标进行划分，并采用贝叶斯 分类模型来学习各组样本集的分类特性；根据各个分类模型的判定类 标，综合得到多类标样本的最终类标集。将该算法分别应用到自然场 景图像和基因数据的多类标分类学习中，实验结果表明，该算法针对 不同的多类标数据集均能取得很好的分类效果，且相比于其他多类标 算法有更高的性能。 关键词数据挖掘，贝叶斯方法，无线传感器网络，容错检测，多类 标分类 a b s t r a c t d a t am i n i n gi st h e p r o d u c to ft h ed e v e l o p m e n to fi n f o r m a t i o n t e c h n o l o g y , w h i c hi sac o m p l e xp r o c e s se x t r a c t i n gt h ei m p l i c a t e da n d v a l u a b l ep a t t e r n s ，k n o w l e d g ea n dr u l e sf r o mal a r g es c a l ed a t a s e t d a t a c l a s s i f i c a t i o ni so n eo ft h ei m p o r t a n tt o p i c si nt h ef i e l do fd a t am i n i n g b a y e sm e t h o d ，w h i c h b a s e so ns o l i dm a t h e m a t i c st h e o r i e sa n d c o m p r e h e n s i v e l y c o n s i d e r st h e p r i o ri n f o r m a t i o n a n dd a t as a m p l e i n f o r m a t i o n ，i sb e i n gw i d e l ys t u d i e da n du s e di nr e c e n ty e a r s i nt h i s p a p e r , d a t ac 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 nb a y e sm e t h o di sm a i n l y s t u d i e d ，a n dt h er e s e a r c hw o r kc o n s i s t so ft w op a r t sa sf o l l o w s ： ( 1 ) a i m i n ga tt h ep r o b l e mo f f 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 n w i r e l e s ss e n s o rn e t w o r k s ( w s n ) ，t h i s p a p e rp r o p o s e t h ei d e ao f d i s t r i b u t e dw e i g h t e dc l a s s i f i c a t i o nf a u l t t o l e r a n td e t e c t i o n ：c o n s i d e r i n g t h er a n g eo 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 i r s tu s ei n f o r m a t i o n e 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 e s 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 t a l g o r i t h mt op r e d i c tt 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 e c e n t r a ln o d e ；b yu s i n gb a y e sm e t h o d ，t h ew e i g h tt h r e s h o l df o rf a u l t d e t e c t o ni sc a l c u l a t e d w eb u i l dt w ok i n d so ff a u l t t o l e r a n td e t e c t i o n m o d e l o n ei st os i m u l a t et h ew i r e l e s ss e n s e rn e t w o r kw i t ha 1 1s e n s e r s a r r a n g e dr e g u l a r l y , a n dt h eo t h e ri st os i m u l a t et h en e t w o r kw i t hs e n s e r s a r r a n g e di r r e g u l a r l y t w ow e i g h t e dc l a s s i f i c a t i o na l g o r i t h ma r ep r o p o s e d r e s p e c t i v e l yt od e t e c tt h ee v e n tr e g i o no f t h e s et w om o d e l s ：t h ea l g o r i t h m w i t hf i xw e i g h ti sf o rr e g u l a r - a r r a n g e ds e n s o rn e t w o r k ，t h eo t h e r a l g o r i t h mb a s e d o nd i s t a n c e - - w e i g h tm e t h o di sf o ri r r e g u l a r a r a n g e d s e n s o rn e t w o r k t h ee x p e r i m e n tr e s u l t ss h o wt h a tt h e s et w ow e i g h t e d c l a s s i f i c a t i o na l g o r i t h m sg a i nh i g ha c c u r a c yf o rf a u l t t o l e r a n td e t e c t i o no f t h ew s ne v e n tr e g i o n ，a n dc o s tl o we n e r g yo ft h ew h o l en e t w o r k ( 2 ) s a m p l e so fm u l t i l a b e ld a t am a yb e l o n gt om o r et h a no n ec l a s s ， s oi t sc l a s s i f i c a t i o np r o b l e mi sm u c hm o r ec o m p l i c a t e dt h a ns i n g l e l a b e l d a t a t h i sp a p e rp r o p o s e dan o v e lm u l t i l a b e ll e a r n i n ga l g o r i t h m f e a t u r e a t t r i b u t e so fm u l t i l a b e ld a t ao f t e nh a sh i g hd i m e n s i o n s ，a n dw eu s el l e a l g o r i t h mt od e c r e a s et h ed i m e n s i o ni no r d e rt oe x t r a c tag r o u po fl o w d i m e n s i o n a lf e a t u r ea t t r i b u t e ss e tw h i c hc o u l dc o m p l e t e l yd e s c r i b ed a t a i i t h e nm u l t i l a b e l s a m p l e sa r ep a r t i t i o n e di nt e r m so ft h e i rb e l o n g i n g c l a s s e s ，a n dl e a r nc l a s s i f i c a t i o nc h a r a c t e r i s t i c s o f e a c hg r o u pu s i n g b a y e s i a nc l a s s i f i c a t i o nm o d e l a f t e rt h a t ，w ec a ng e tt h ef i n a lc l a s s l a b e l s e to fm u l t i - l a b e ls a m p l e sa c c o r d i n gt ot h ed e c i s i o nc l a s s - l a b e lo fe a c h c l a s s i f i c a t i o nm o d e l i nt h i sp a p e r , t h ea l g o r i t h mi sa p p l i e dt om u l t i l a b e l c l a s s i f i c a t i o nl e a r n i n go fn a t u r es c e n ei m a g ea n dg e n ed a t ai n d i v i d u a l l y e x p e r i m e n t a l r e s u l t ss h o wt h a to u r a l g o r i t h m c a n a c q u i r eg o o d c l a s s i f i c a t i o ne f f e c t so nd i f f e r e n tm u l t i l a b e ld a t a s e t ，a n de n a b l eb e t t e r p e r f o r m a n c ec o m p a r e dt oo t h e rs i m i l a ra l g o r i t h m s k e yw o r d sd a t am i n i n g ，b a y e sm e t h o d ，w i r e l e s ss e n s o rn e t w o r k ， f a u l t - t o l e r a n td e t e c t i o n ，m u l t i l a b e lc l a s s i f i c a t i o n 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研 究工作及取得的研究成果。尽我所知，除了论文中特别加以标注 和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究 成果，也不包含为获得中南大学或其他单位的学位或证书而使用 过的材料。与我共同工作的同志对本研究所作的贡献均己在论文 中作了明确的说明。 作者签名：谢绝日期：五喀年上月丝日 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学 校有权保留学位论文并根据国家或湖南省有关部门规定送交学 位论文，允许学位论文被查阅和借阅；学校可以公布学位论文的 全部或部分内容，可以采用复印、缩印或其它手段保存学位论文。 同时授权中国科学技术信息研究所将本学位论文收录到中国学 位论文全文数据库，并通过网络向社会公众提供信息服务。 作者签名：蒯量复一导师签名拯日期：盟年l 月丛日 硕士学位论文 第一章绪论 1 1 研究的背景和意义 第一章绪论 伴随着信息高速公路的建设，数字技术、数据库技术迅猛发展，人类的数据 库里积累了越来越多的历史数据，而这些大量的历史数据除了实时的利用价值 外，还蕴涵了丰富的引导信息，这些信息是不能被表象发现的，是隐含在海量数 字符号背后的能够为人类社会发展提供指导意义的信息。那么如何将数字符号背 后的有用信息提取出来引起了学术界的广泛关注，也成为近几年学术研究的热 点，应运而生的就是“数据挖掘”学科，又被称为数据库中的“知识发现”，简单的 解释就是通过数据库、机器学习、人工智能、统计学等领域的技术，从数据库或 数据仓库中提取出隐含的、未知的且有潜在应用价值的知识，能够为人类提供有 决策意义的信息，为决策和科学发展提供有利的基础和支持。 通过数据挖掘技术可以从大量的数据中发现模式或知识，按作用不同可以将 模式分为两类：描述型模式和预测型模式。描述型模式是对数据中隐含的规律通 过模式形式描述出来，包括泛化模式、聚类模式、关联模式及时间序列模式；预 测型模式是利用从历史数据中提取出的知识对未知数据的某些性质进行预测，包 括分类模式和回归模式l 卜4 j 。 其中，分类模式是一种重要的预测型模式，且有重要的实用价值。例如在无 线通信行业，通过对客户流信息数据库中的样本数据进行分析，对客户群体进行 分类，概括出每个类的特征并且采用科学的建模型方法对每个类进行建模描述， 挖掘出作为分类的一般规则，再用这个分类规则可以对其它预测数据进行分类预 测。部门可以针对不同类的客户采取不同的业务方案，提供针对性的服务，近年 来开始出现的个性化服务以及对应的集团客户服务正在受到个人以及各行业的 青睐。利用数据挖掘的分类技术建立一套科学的数据表达模型和客户评价指标体 系，对客户消费行为特征进行挖掘，已成为无线通信运行商提高市场竞争力扩大 业务范围的有力武器。 分类模式的过程可抽象地描述为：首先对数据库中的数据集进行预处理，将 记录不全的、无关的属性清除，并确定一个用于标定数据类别的属性；然后从该 数据集中抽取出一定数量的记录形成训练样本集；再运用分类方法对训练样本集 进行挖掘，最终输出某种形式的分类模式。 综上所述，分类技术作为数据挖掘的重要分支将对通信、金融、商业、医疗、 保险等诸多行业提供决策支持，对人类生活及社会发展也将产生深远的影响。贝 硕士学位论文第一章绪论 叶斯分类方法以其突出的优势及广泛的应用成为分类建模中尤为重要的方法，本 文选择数据挖掘中的分类方法作为研究课题，并着重研究了基于贝叶斯的分类方 法。 1 2 研究现状 分类是数据挖掘中的一种重要的分析方法，是预测分类标号。利用分类可以 从数据集中提取数据类的模型，并且把数据集中的每个对象归入到某个已知的对 象类中。描述数据类的模型可以是显式的，如决策树或者一组分类规则，也可以 是隐式的，比如一个数学公式。分类在许多领域都有应用，如客户流的损失，传 感器区域检错，多类标数据的归类等。 1 2 1 分类的一般过程 分类一般包括两个步骤实现：建立数学模型和使用数学模型对未知类别的数 据进行分类。 第一步：对类别已经确定的数据集建立模型。用于建立模型的数据集称为训 练集，训练集中的单个元组称为训练样本。训练集中的每一个元组都属于一个确 定的类别，类别用类标号标示。学习模型用分类规则，判定树、数学公式或者图 的形式提供。例如：给定一个信用卡顾客的信用信息数据库，可以学习分类规则， 根据他们的信誉度好坏来识别顾客。这些规则可以用来分类，就是一种分类模型， 利用它可以对以后的顾客进行分类。 第二步，使用创建的模型将类别未知的元组归入到某个或者某几个类中。使 用模型进行分类需要评估分类模型的预测准确率。评估的方法很多，通常使用创 建的模型在一个测试集进行预测，并将结果和实际值进行比较得到预测准确率。 测试集是随机选取的样本集并独立于训练集。 评估模型可以根据下列标准来进行：( 1 ) 预测准确率；( 2 ) 模型的创建速度 和使用速度；( 3 ) 强壮性；( 4 ) 模型对具有噪声或空缺值的数据的适应能力；( 5 ) 伸缩性；( 6 ) 数据大量增加时模型的适应能力；( 7 ) 可解释性，即对模型的可理 解程度。 1 2 2几种主要分类方法 分类可以采用决策树、基于关联规则、支持向量机和贝叶斯等方法，其国内 外研究现状如下： ( 1 ) 决策树分类法 2 硕+ 学位论文 第一章绪论 决策树是较早应用于数据挖掘分类问题的一种方法。它是一种树型结构，其 每一个内部节点表示在一个属性上的测试，并且该节点的每一个后继分支对应于 该属性的一个可能值，每个树叶节点表示类或类分布，树的最顶层节点为根节点。 分类实例的方法采用自顶向下的递归式，在决策树叶子节点得到该实例的类别。 绝大多数决策树分类方法【5 4 1 分两步构造分类器：树的生成与树的剪枝。在树 的生成阶段，决策树是通过反复地拆分训练集而成。在每一次分拆时，都是利用 某种分拆准则选择一个属性。由所选属性值不同将训练集分成多个子集。然后在 每个子集上重复同样的分拆过程，直到每个分拆后的训练集的子集样本均属于同 一个类别为止。 ( 2 ) 支持向量机的分类方法 支持向量机( s u p p o r tv e c t o rm a c h i n e ，s v m ) 是一种基于统计学习理论的 机器学习方法，s v m 可以自动寻找出那些对分类有较好区分能力的支持向量，由 此构造出的分类器可以最大化类与类的间隔，因而有较好的适应能力和较高的分 准率。该方法只需要由各类域的边界样本的类别来决定最后的分类结果。 支持向量卡几【7 。8 】算法基本思想是通过用非线性映射将输入空间变换到一个高 维空间，在这个高维空间中寻找输入变量和输出变量之间的一种非线性关系。算 法仅使用高维空间中的内积，通过引入核函数，高维空间的内积运算就可用原空 间中的函数来实现，通过采用适当的核函数就可实现某一非线性变换后的线性分 类，而计算复杂度没有增加，从而在一定程度上避免了维数灾难问题。它以最大 化分类间隔构造最优分类超平面来提高分类器的泛化能力，较好地解决了非线 性、高维数、局部极小点等问题。 ( 3 ) 基于关联规则的分类 关联规则挖掘发现大量数据中项集之问的有趣的关联或相关联系。随着大量 数据不停地收集和存储，关联分类在数据挖掘领域内引起越来越广泛的关注，取 得了一批研究成果，代表算法有c b a 9 1 ，c m a r 【10 1 ，c p a r 11 】等。 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 n r u l e s ，c a r ) ；第二步：从已发现的c a r 中选择高优先度的规则来覆盖训练集。 基于多维关联规则的分类算法c m a r ( c l a s s i f i c a t i o nb a s e do nm u l t i p l e c 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 ) 结构有效地存储关联规则。 基于置信度、相关性和数据库覆盖来剪枝。分类算法c p a r ( c l a s s i f i c a t i o nb a s e d o 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 算法相当。 ( 4 ) 贝叶斯分类 贝叶斯分类【1 2 。16 】是建立在经典的贝叶斯概率理论的基础上的给予统计的分 类方法，是一种有指导的学习方法。以其独特的不确定性知识表达形式、丰富的 概率表达能力、综合先验知识的增量学习特性等成为当前数据挖掘中最为引人注 目的分类方法之一。 密度估计 贝叶斯密度估计研究如何根据样本的数据信息和人类专家的先验知识获得 对未知变量的分布及其参数的估计。它有两个过程：一是确定未知变量的先验分 布；一是获得相应分布的参数估计。如果对以前的所有信息一无所知，称这种分 布为无信息先验分布；如果知道其分布求它的分布参数，称之为有信息先验分布。 由于在数据挖掘中，从数据中学习是它的基本特性，所以无信息先验分布是贝叶 斯学习理论的主要研究对象。研究无信息分布的奠基性工作是贝叶斯假设参数的 无信息先验分布在参数的取值范围内应是均匀的。对参数有界的情况，贝叶斯假 设在实际运用中获得了很大的成功，与经典的参数估计方法是一致的，而当参数 无界时，贝叶斯假设却遇到了困难。为此，人们提出了一些选取先验分布的原则： 共轭分布：共轭分布假定先验分布与后验分布属于同一种类型。这一假定 为后验分布的计算带来很大的方便，同时在认知上，它要求经验的知识与现在的 样本信息有某种同一性，它们能转化为同一类型的经验知识。 最大熵原则：利用信息论中熵的理论，在确定无信息先验分布时应取参数 变化范围内熵最大的分布作为先验分布。最大熵原则比贝叶斯假设前进了不少， 但在无限区间上产生了各种各样的新问题。 朴素贝叶斯学习模型 朴素贝叶斯学习模型假定特征向量的各分量相对于决策变量是相对独立的， 也就是说各分量独立地作用于决策变量。尽管这一假定一定程度上限制了朴素贝 叶斯模型的适用范围，然而在实际应用中，不仅指数级的降低了贝叶斯网络构建 的复杂性，而且在违背这种假定的条件下，朴素贝叶斯也表现出相当的健壮性和 高效性，它已经成功地应用到分类、聚类及模型选择等数据挖掘的任务中。目前， 许多研究人员正致力于放松特征变量间条件独立性的限制，以使它适用于更大的 范围。主要集中在两个方面： 增广贝叶斯学习模型( a u g m e n t s i m p l eb a y e s i a n ) 。g e o f f r e yl w e b b 0 2 1 在朴 素贝叶斯模型中为每个类别赋一权值，这个权值乘以原来的概率值作为新的调整 值，在应用中有效地提高了预测精度。e a m o n nj k e o g h l l 3 j 通过在特征属性之间增 4 硕士学位论文第一章绪论 加相应的弧来降低朴素贝叶斯模型属性之间独立性的限制，并且给出了建立属性 之间关联的两种方法：贪婪的爬山搜索法和超父节点搜索法。 基于b o o s t i n g 卡 素贝叶斯模型。c h a r l e se l k a n 1 4 】利用b o o s t i n g 技术对朴素贝 叶斯模型进行了改进。他通过调整训练样本的权重，产生几个朴素贝叶斯模型， 然后再将这些模型以一定的方式组合起来，并且证明，组合后的模型在表达能力 上相当于具有几个隐含层的感知机模型。然而b o o s t i n g 技术并非对所有朴素贝叶 斯模型都适用，有时甚至会降低它的预测精度。 贝叶斯神经网络模型 朴素贝叶斯模型在表达形式上等价于感知机模型，对应于分类器中线性可分 的情况。当线性不可分时，也就是说当考虑属性间的相关性时，需要引入具有隐 含层的神经网络模型。目前对贝叶斯神经网络的研究主要集中在以下几个方面： 基于b o o s t i n g 、投票等方法产生几个朴素贝叶斯模型，然后将这些模型以 一定方式组合。组合后的模型相当于含有隐含层的神经网络模型，用贝叶斯方法 来训练神经网络的权重【l4 1 。 利用贝叶斯证据框架理论学习神经网络的结构【l5 1 。这一方法已成功地应 用到模型选择、自相关性侦探等方面。 贝叶斯网络是表示变量间概率分布及关系的有向无环图。结点表示随机变 量，弧表示变量问的依赖关系，定量的概率分布在条件概率表中指定。贝叶斯网 络的一个关键特征是它提供了把整个概率分布分解成几个局部分布的方法，网络 的拓扑结构表明如何从局部的概率分布获得完全的联合概率分布。贝叶斯网络适 合于对领域知识具有一定了解的情况，至少对变量间的依赖关系较清楚的情况。 否则完全从数据中学习贝叶斯网的结构不但复杂性较高，网络维护代价昂贵，而 且它的估计参数较多，为系统带来了高方差，影响了它的预测精度。 1 3 本文的工作 分类问题在数据挖掘、模式识别、机器学习中一直是一个活跃的研究领域。 正确有效地识别未知模式的类别是分类研究的中心。目前国内外对于传感器网络 事件区域检测问题以及多类标问题分类的研究还处在初级阶段，在作者能够检索 到的知名学术会议论文集和公开发表的刊物上，发现针对这两方向的研究成果较 少。本文针对这两方面问题采用贝叶斯方法进行了研究和探讨，研究的主要内容 如下： ( 1 ) 研究传感器网络事件区域检测问题 传感器网络由部署在检测区域中的大量节点组成，每个节点都具有一定的计 算、感知能力以及有限的能量，其目的是协作地感知、采集和处理网络覆盖区域 硕士学位论文 第一章绪论 中感知对象的信息。传感器网络的一个重要应用是监控环境中异常事件的发生， 并找到事件发生区域【1 。7 。1 8 】。无线传感器网络的特点意味着传统的集中式处理方法 并不适用，采用局部和分布式的算法可以有效地减少因网络内部计算而消耗的能 量。而传感器网络由大量的节点设备自组织形成，每个传感器节点都是低端的不 可靠的设备，节点出错的可能性非常大。节点出错带来的虚假信息，会导致加大 对事件区域检测的难度。因此，在传感器事件区域检测过程中，进行容错处理是 非常有必要的。 针对传感器网络事件区域检测问题，提出了分布式加权分类容错检测的思 想。对于节点分布规则的传感器网络提出分布式加权容错算法，考虑到网络中观 测到有异常事件发生的传感器节点，应当比观测正常的节点更应该引起重视，引 入了加权容错检测模型，为不同状态的节点赋予不同的权重，该想法能较好地检 测出事件发生区域及其边界。其次，考虑到邻域节点信息的不可靠问题，提出“邻 域的邻域”方法，利用邻域节点与其周围最近邻节点的两两之间信息交换，先对 邻域节点的状态进行估计，综合邻域节点的加权信息对中心节点进行错误检测， 达到提高检测分类准确度的目的。对于节点分布不规则的传感器网络提出基于加 权距离的分布式容错算法，考虑到节点间的距离不同，利用节点空间相关性的思 想，按照节点间的距离来加权，融合双邻域节点的加权信息总和对中心节点状态 进行判断。通过实验结果比较表明，这两种算法均具有较高的错误检测精度，且 算法运行时整个网络所消耗的能量适中。 ( 2 ) 研究多类标数据的分类问题 多类标问题在各个不同的领域中都普遍存在。在基因数据中，每个基因可能 对应多个功能类别的集合，如“变异基因”，“复制基因”等；而图像场景分类中， 每幅场景图像可能属于多个语义类别，按照图像中包含对象的不同，同一幅图像 既可能属于“沙滩 类别，也属于“建筑 类别。在文本分类中，每个文件可能 同时属于多个题材类别，如“环保 和“健康”；在这些多类标问题中，训练集 中的每个样本都对应由一个或多个类标组成的集合，而多类标学习的任务就是在 类标集中类标数目未知的情况下，为每个未知的样本预测类标集。 目前，国内外针对多类标问题的研究还非常少【1 9 】。本文针对基因数据、图 像数据产生的多类标问题，提出一种基于l l e 降维和贝叶斯分类的多类标学习 算法。首先，考虑到贝叶斯网络在对高维数据进行处理时，构网耗时长、分类结 果差的特点，我们先采用l l e 算法对多类标样本数据的特征属性进行降维处理。 然后将处理后的降维数据进行离散化，按照其类别建立单类标的贝叶斯网络的分 类器，最后将所判定的类标的并集归一化后得到最终的类标集。将该算法与已有 的多类标分类算法进行了性能比较，实验结果表明，面对复杂的多类标分类问题， 6 硕士学位论文 第一章绪论 采用l l e 降维和贝叶斯分类模型来处理多类标分类问题，具有简单直观、性能 稳定、分类精度高的特点。 1 4 本文的组织 本文共分五章，各章的内容安排如下： 第一章：绪论。主要概述了数据挖掘的相关概念，以及不同分类算法的介绍。 解释了数据挖掘及其研究对象的发展现状和未来趋势，详细阐述了数据挖掘中分 类问题的定义、方法以及分类模型评价的标准等。说明了本文的研究内容和意义， 最后给出文章的组织结构。 第二章：贝叶斯理论与贝叶斯分类模型。主要对基于贝叶斯方法的分类问题 的基本原理进行介绍，包括贝叶斯理论的基本知识和基本的贝叶斯分类模型。贝 叶斯定理是贝叶斯分类模型的理论基础，所有的工作都是围绕这一定理展开研 究，目前最常用的两种贝叶斯分类模型是朴素贝叶斯分类器和贝叶斯网络分类 器，分别对这两种模型的特点进行了分析。 第三章：无线传感器网络事件区域容错检测贝叶斯分类算法研究。提出了一 种基于贝叶斯方法的无线传感器网络事件区域容错检测算法：构建无线传感器网 络中事件发生区域的容错模型，结合传感器网络的特点，提出了一种分布式加权 的容错检测算法来确定传感器网络中的事件区域。采用贝叶斯方法进行推导，得 到事件区域检测的最优阈值，并与其它算法进行性能比较，以及进行能耗分析。 第四章：基于l l e 降维和贝叶斯分类的多类标学习算法。为了具有多类标的 高维数据的分类问题，首先采用l l e 降维方法先对高维的数据样本进行降维，然 后通过构造贝叶斯网络的方法对降维后的多类标样本进行分类。由于l l e 降维算 法能够很好地保证数据样本原有的拓扑结构，所以采用贝叶斯方法对其降维后的 数据进行分类的方法，相比于其它算法，有更好的准确性。该方法是贝叶斯方法 对高维、多类标样本进行分类的一个有效应用。 第五章：总结与展望。对本文的研究成果进行总结，并探讨了进一步研究的 方向。 7 硕士学位论文 第二章贝叶斯理论与贝叶斯分类模型 第二章贝叶斯理论与贝叶斯分类模型 贝叶斯分类器是建立在经典的贝叶斯概率理论的基础上的给予统计的分类 模型，本章主要讨论贝叶斯分类的基本原理和几种常见的贝叶斯分类模型。 2 1 贝叶斯相关理论 条件概率：设彳，b 为两随机事件且p ( a ) 0 ，事件b 在给定事件彳发生时 的条件概率定义为 郴伽= 等 公式( 2 1 ) 乘法定律：直观上，p ( ba ) 是在已知a 发生时，对b 发生的信度；而p ( b ) 贝j j 是在不知道a 是否发生时，对b 发生的信度。由式( 2 1 ) 可得 p ( a b 1 = p ( a ) p ( b i a ) 公式( 2 2 ) 这称为概率的乘法定律，其含意非常直观：对a 和召同时发生的信度，等于对于 彳发生的信度乘以已知a 发生时对b 发生的信度。当然乘法定律也可以写为 p ( a b 、= p ( 8 ) p ( a i s ) 公式( 2 3 ) 全概率公式：设试验e 的样本空问为s ，a 为e 的事件，蜀，岛，或为s 的 一个划分，且p ( e ) _ o ( i = 1 ，2 ，z ) ，则： 尸( 么) = 尸( 蜀) p ( 彳f 蜀) + p ( 垦) p ( 彳l 垦) + + 尸( 色) 尸( 彳i 或) ：n 尸( e ) 尸( 么i e ) 公式( 2 4 ) 上式称为全概率公式。 贝叶斯定理：设试验e 的样本空间为s ，a 为e 的事件，蜀，色，e 为s 的 一个划分，且尸( 彳) - o ，尸( e ) - o ( i = 1 ，2 ， ) ，则由条件概率的定义和全概率公式： 。，。hp ( a i e ) p ( e ) 尸( ef 彳) = i l _ _ 二 尸( 彳i e ) p ( 哆) 公式( 2 5 ) 上式称作贝叶斯定理【2 1 1 。 极大后验假设：在许多学习场景中，学习器考虑候选假设集合h 并在其中寻 找给定的数据d 时的可能最大的假设h h 。这样具有最大的可能性的假设被称 8 硕士学位论文第二章贝叶斯理论与贝叶斯分类模型 为极大后验假设( m a x i m u map o s t e r i r i ，m a p ) ，记作：御。 h m a p = a r g 。m a xp ( hi 。) = a r 写舅a x 警= a r g 。m a x p ( di 厅) p ( h ) 公式( 2 - 6 ) 由于p ( d ) 是不依赖于h 的常量，所以可以把它去掉。公式( 2 6 ) 是一个原始的分 类模型，贝叶斯分类就是根据上述m a p 假设找出的新实例最有可能的分类。 极大似然假设：所有对贝叶斯的分类模型的研究都是以此假设为前提条件。 在某些情况下，可假定日中的每个假设都有相同的先验概率( 即对h 中的任意的 曩和办，有p ( 魄) = p ( h j ) ) 。这时可以把上式进一步简化，只考虑p ( hd ) 来寻 找极大可能假设。p ( d i 办) 常被称为给定h 时数据d 的似然度，而使得p ( d l 矗) 最 大的假设称为极大似然假设( m a x i m u nl i k e l i h o o d ，m l ) ，记作： = a r g m ，a xp ( dl h ) 公式( 2 7 ) h e h 、 与机器学习问题相联系，我们把数据d 称作某目标函数的训练样本，而把h 称 为候选目标函数空间。 事件的独立性：设彳，b 是试验e 的两个事件两个事件，一般彳的发生对b 发 生的概率是有影响的，这时p ( ba ) p ( b ) ，只有在这种影响存在时才会有 p ( ba ) = p ( b 1 ，这时有： p ( a b ) = p ( bi 彳) 尸( 彳) = p ( 彳) p ( b )公式( 2 8 ) 则称彳，b 为相互独立事件。 同样，对于n 个事件4 ，4 ，4 ，如果有 p ( a l ，4 ，以) = p ( a i ) p ( 4 ) p ( a 。)公式( 2 9 ) 则称4 ，4 ，以为相互独立事件。 2 2 贝叶斯分类模型 分类有规则分类和非规则分类这两种。贝叶斯分类属于非规则分类，它通过 训练集训练得到分类器，然后利用已有的分类器对没有分类的数据( 测试集) 进 行分类。贝叶斯分类具有如下特点： ( 1 ) 贝叶斯分类并不把一个数据对象唯一的指派给某个类别，而是通过计算 得到属于不同类的概率，在单类标数据的情况下具有最大概率的类便是该对象所 属的类，在多类标数据的情况下概率较大的类为该对象所属的类，具体划分按设 计者要求来确定。 ( 2 ) 一般情况下在贝叶斯分类中所有的属性都潜在的起作用，即并不是依据 一个或者几个属性来决定分类，而是所有的属性都参与分类，其中可能存在某些 9 硕士学位论文 第二章贝叶斯理论与贝n l 斯分类模型 属性对分类的影响较大。 ( 3 ) 贝叶斯分类对数据的格式没有什么要求，既可以是离散的、连续的，也 可以是混合的，这很好的保证了贝叶斯分类的通用性。 贝叶斯分类器中有代表性的分类器有朴素贝叶斯分类器、贝叶斯网络分类器 和数扩展的朴素贝叶斯分类器模型t a n 分类器等。根据给定的训练集归纳出分 类器是数据挖掘的一项重要而基本的任务，在众多的分类器中，朴素贝叶斯分类 器以简单的结构和良好的性能受到人们的关注。 2 2 1 朴素贝叶斯分类模型 朴素贝叶斯分类器( n a i v eb a y e s i a nc l a s s i f i e r ，n b c ) 是贝叶斯分类模型中一种 最简单、有效的而且在实际使用中很成功的分类器【2 引。其性能可以与神经网络， 决策树( 女1 c 4 5 ) 相比，甚至在某些场合优于其它分类器。 朴素贝叶斯分类模型描述如图2 1 所示。设有变量集u = 4 ，4 ，4 ，c ，其 中4 ，以以是实例的属性变量，c 是取m 个值的类变量。假设所有的属性都条 件独立于类变量c ，即每一个属性变量都以类变量作为唯一的父节点，就得到朴 素贝叶斯分类器。 图2 1 朴素贝叶斯分类模型示意图 朴素贝叶斯模型假设特征向量的各个分量之间相对于决策变量是相对独立 的，也就是各个分量独立地作用于决策变量，尽管这一假设在一定程度上限制了 朴素贝叶斯模型的适用范围，但是在实际的应用中，大大降低了贝叶斯网的构建 复杂性。朴素贝叶斯分类模型已经成功地应用到聚类，分类等数据挖掘任务中。 目前，许多研究致力于改进特征变量问独立性的限制条件，以使它能适用于更广 的范围。 ( 1 ) 朴素贝叶斯分类的工作过程 第一步：每个数据样本用一个刀维特征向量x = x l ，乇，矗 表示，分别描 述对n 个属性4 ，4 ，以样本的刀个度量。 第二步：假定有m 个类c l ，c ，c 。给定一个未知的数据样本x ( 即没有 类标属性值) ，分类法将预测x 属于具有最高后验概率( 条件x 下) 的类。朴 l o 硕士学位论文第二章贝叶斯理论与贝叶斯分类模型 素贝叶斯分类将未知的样本分配给类c j ，当且仅当： p ( gl x ) 尸( qi x ) ，1 ，聊，j i公式( 2 1 0 ) 这样，最大化尸( c ，i x ) 。其中p ( gl x ) 最大的类g 称为最大后验假定。根据贝 叶斯定理得： 粥= 警 公式( 2 11 ) 第三步：由于尸( x ) 对于所有类为常数，只需要p ( x l g ) p ( c , ) 最大即可。如 果类的先验概率未知，则通常假定这些类是等概率的， 即 尸( c 1 ) = p ( c 2 ) = = p ( q ) 。并根据这个对尸( ei x ) 最大化，否则，最大化 e ( x l c , ) e ( c , ) 。同时可以注意到，先验概率可以用公式尸( c ，) = 最s 来进行计算， 其中s ，是类e 中的训练样本数，而s 是训练样本总数。 第四步：给定具有许多属性的数据集，计算p ( x l c , ) 的开销可能非常大。为 了降低计算p ( x l c , ) 的开销，可以做类条件独立的朴素假设。给定样本的类标号， 假设属性值相互条件独立，即在属性问，不存在依赖关系。这样， g ( x l c ，) = 兀p ( 坼i c ，) k = i 公式( 2 - 1 2 ) 概率p ( x ic ，) ，p ( x 2 l e ) ，尸( 矗l g ) 可以由训练样本估值，其中 如果4 是分类属性，则尸( 稚ic ) = s i k s i ，其中是在属性4 上具有值吒 的类g 的训练样本数，而墨是e 中的训练样本数。 如果4 是连续值属性，则通过假设该属性服从高斯分布。 第五步：为对未知样本x 分类，对每个类c f ，计算p ( xg ) p ( g ) 。样本x 被 指派到类e ，当且仅当 e ( x l c ? ) p ( c ? ) p ( x c ，) p ( c ，) ，l j m ，j f 公式( 2 - 1 3 ) 换而言之，被指派到其p ( x i e ) 尸( c f ) 最大的类c j 贝叶斯分类模型优点是：算法逻辑简单，易于实现；分类过程中时空开 销小；算法稳定，对于不同的数据特点其分类性能差别不大，也就是说健壮性 比较好。 ( 2 ) 朴素贝叶斯分类模型的改进 朴素贝叶斯分类器是基于一个简单的假定：在给定分类特征条件下属性值之 间是相互条件独立的。在现实生活中，它的属性独立性假设使其无法表示实际应 用中各属性之间的依赖关系，影响了它的分类性能。因此需要针对实际应用对朴 素贝叶斯分类模型进行改进，使之在属性独立性假设不满足的情况下依然有较高 的分类精确度。因此，研究朴素贝叶斯分类器的改进模型，需从以下角度进行分 硕士学位论文第二章贝叶斯理论与贝叶斯分类模型 析： 属性删除技术：适用于存在冗余属性的情况。目前研究者们提了一些基 于属性删除的选择性贝叶斯分类器，当存在时，属性删除方法确实能够改善朴素 贝叶斯分类器的预测精度。 构造新属性或概率调整技术：适用于某些属性依赖于其他属性时。