试析基于信息论的特征选择和分类算法研究

《试析基于信息论的特征选择和分类算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、西南农业大学硕士学位论文基于信息论的特征选择和分类算法研究姓名：张隆申请学位级别：硕士专业：农业机械化工程指导教师：余建桥20050501硅南农业大学硕士学位论文捅墨摘要随着计算机科学与技术的发展，人们越来越认识到信息的价值。在信息爆炸的今天，人们迫切需要一种方法从大量的数据信息中提取并找到有用的信息，数据挖掘就是在这种情况下诞生的。近十年，数据挖掘的研究工作取得了很大的进展．各种数据挖掘软件的应用极大地推动了人们掌握、处理信息的能力，并为人们带来了很好的经济效益。数据挖掘就是从大量的、不完全的、有噪声的、模糊的、随机的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的

2、信息和知识的过程。特征选择和数据分类是数据挖掘的两个重要的课题。特征选择就是从一个原始的特征集合中选择一个最优特征子集的过程，这个特征子集应当保留原始特征集合的全部或大部分类别信息。数据分类的任务是找出一个类别的概念描述(通常称之为分类器)，它代表了这类数据的整体信息，即该类的内涵描述，一般用规则或决策树模式表示，该模式能够把数据库中的元组映射到给定类别集中的某一个。本文在特征选择算法和数据分类算法两个方面做出了一些比较深入的研究。在特征选择算法方面，研究了信息度量中的互信息在衡量特征与类别之间和各个特征之间的关系时所起到的作用；主要针对特征选择过程中的冗余特征消除问题作出了具体而深入的

3、研究。在数据分类算法方面，研究了在分类过程中条件互信息在评价特征重要性方面的作用；利用条件互信息建立互信息网络{井通过互信息网络简化分类规则。并通过实验对这两方蔼的研究成果作出了较为科学的评价。本文在第4章通过讨论特征选择的过程，分析和论证了在特征选择过程中消除冗余特征的重要性，提出了在特征选择过程中消除冗余特征的一种算法_i丘似的马尔可夫毯过滤法。共在此基础上提出了一个基于信息论的特征选择算法——-EcBF算法。该算法以信息论量度为基本工具．结合了在特征子集评估中的特征冗余分析，利用单个特征评估在计算上的优势，将特征冗余性分析引入到单个特征评估方法中，实现对高维度数据集的高效的特征选择

4、。在文中我们选取了基于信息论的关联量度RMI，该量度通过互信息和信息熵构造而成，从总体上反映了各个特征之间以及特征与类别之间的关联程度。通过运用关联度量ltMI计算各个特征与类别之间的关联度，可以将特征集中的与类别不相关的特征全部过滤出去，产生与类别相关的相关特征集。但在相关特征集中通常存在着冗余的特征．消除冗余特征将使得后续的数据分类模型的建立更加有效。特征冗余通常以特征关联来确定。普遍认为如果两个特征的数值完全地相互关联，则它们彼此是冗余的。事实上，当一个特征与一组特征部分地相互关联的时候，不可能直接决定该特征是冗余的。马尔可夫毯是进行特征冗余性分析的一种强有力的工具，它描述了一个冗

5、余特征在特征集中的主要表现，通过冗余特征与特征集的统计关系可以判定特征的冗余性，并由此产生了判定冗余特征的马尔可夫毯过滤法。由于马尔可夫毯过滤法在计算上的要求过高，在高维度的数据集中，应用马尔可夫毯过滤法分析和判定冗余特征必然会使特征选择算法的效率降低，因而这种方法是不适合商维度的特征选择的-在马尔可夫毯过滤法中，我们通过抽取该方法的基本特性，分析该方法的主要组成部分并结合关联量度RMI，推论并构造了一个近似的马尔可夫毯过滤法，并以此方法在相关特征集中进行冗余特征分析。在近似的马尔可夫毯过滤法中，特征与类别之闻的关联称为c．关联，两个特征之问的关联称为F关联，没有任何的近似的马尔可夫毯的

6、特征称为优越的特征。近似的马尔可夫毯的基本工作原理是：如果特征x的c-关联大于特征Y的c一关联．且特征之间的F．关联大于特征Y的c．关联，则特征Y是冗余的。由近似的马尔可夫毯的基本工作原理可知其基本性质：具有晟大c-关联值的特征不存在近似的马尔可夫毯，该特征是优越的特征。利用该性质，在对相关特征的C。关联值进行排序后，可以从具有最大C．关联值的特征开始，逐步消除所有的冗余特征，而保留优越的特征，最后形成的特征集由所有优越的特征组成。利用近似的马尔可夫毯过滤法进行相关性和冗余性分析，就是通过选择所有的优越特征并且除去剩余特征的方法。它使用c．关联和F-关联来确定特征冗余，而且结合前向序列选

7、择和除去冗余特征．因此，它不但围绕所有的特征对进行F-关联分析。而且比纯粹的前向序列选择或后向消除法取得更高的效率。本文第5章提出了一个建立在相关特征集上的数据分类方法——MⅡN算法。该算法以信息论量度为基本工具．通过条件互信息评估各个相关特征在分类过程中的等级次序，产生简洁的分类规则，并评估分类规则在分类过程中的重要程度。互信息网络(～lutual—InformationNetwork(MIN))是一种信息论方法，在拓朴结构上类似