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

随着计算机科学与技术的发展,人们越来越认识到信息的价值。在信息爆炸的今天,人们迫切需要一种方法从大量的数据信息中提取并找到有用的信息,数据挖掘就是在这种情况下诞生的。近十年,数据挖掘的研究工作取得了很大的进展,各种数据挖掘软件的应用极大地推动了人们掌握、处理信息的能力,并为人们带来了很好的经济效益。数据挖掘就是从大量的、不完全的、有噪声的、模糊的、随机的实际应用数据中,提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程。 特征选择和数据分类是数据挖掘的两个重要的课题。特征选择就是从一个原始的特征集合中选择一个最优特征子集的过程,这个特征子集应当保留原始特征集合的全部或大部分类别信息。数据分类的任务是找出一个类别的概念描述(通常称之为分类器),它代表了这类数据的整体信息,即该类的内涵描述,一般用规则或决策树模式表示,该模式能够把数据库中的元组映射到给定类别集中的某一个。 本文在特征选择算法和数据分类算法两个方面做出了一些比较深入的研究。在特征选择算法方面,研究了信息度量中的互信息在衡量特征与类别之间和各个特征之间的关系时所起到的作用;主要针对特征选择过程中的冗余特征消除问题作出了具体而深入的研究。在数据分类算法方面,研究了在分类过程中条件互信息在评价特征重要性方面的作用;利用条件互信息建立互信息网络;并通过互信息网络简化分类规则。并通过实验对这两方面的研究成果作出了较为科学的评价。 本文在第4章通过讨论特征选择的过程,分析和论证了在特征选择过程中消除冗余特征的重要性,提出了在特征选择过程中消除冗余特征的一种算法——近似的马尔可夫毯过滤法。并在此基础上提出了一个基于信息论的特征选择算法——ECBF算法。该算法以信息论量度为基本工具,结合了在特征子集评估中的特征冗余分析,利用单个特征评估在计算上的优势,将特征冗余性分析引入到单个特征评估方法中,实现对高维度数据集的高效的特征选择。 在文中我们选取了基于信息论的关联量度RMI,该量度通过互信息和信息熵构造而成,从总体上反映了各个特征之间以及特征与类别之间的关联程度。通过运用关联度量RMI计算各个特征与类别之间的关联度,可以将特征集中的与类别不相关的特征全部过滤出去,产生与类别相关的相关特征集。但在相关特征集中通常存在着冗余的特征,消除冗余特征将使得后续的数据分类模型的建立更加有效。 特征冗余通常以特征关联来确定。普遍认为如果两个特征的数值完全地相互关联,则它们彼此是冗余的。事实上,当一个特征与一组特征部分地相互关联的时候,不可能直接决定该特征是冗余的。马尔可夫毯是进行特征冗余性分析的一种强有力的工具,它描述了一个冗余特征在特征集中的主要表现,通过冗余特征与特征集的统计关系可以判定特征的冗余性,并由此产生了判定冗余特征的马尔可夫毯过滤法。 由于马尔可夫毯过滤法在计算上的要求过高,在高维度的数据集中,应用马尔可夫毯过滤法分