信息熵-特征选择方案

基于互信息的特征选择1.模型定义D1病集S由有关心脏病病种iX（i=1，2，…，n）组成，令患者的疾病信息熵1-2为：)(1log)()(1iniiXPXPXH(1)显然疾病信息熵具有Shannon信息熵的性质，反映了临床中具体病人的客观信息及实际医疗干预过程中所表现的信息在总体特征上的平均不确定性.定义D2：一个诊断病例库可以表示为关于病例特征的矩阵形式nmijxCasebase][(2)其中，ijx—病例库中第j个病例的第i个属性值；m—病例特征数量；n—病例库规模；定义D3：一个信息系统（IS）可以表达为,,,rrfRIURVf(3)其中，U是对象的非空有限集合，R是属性的非空有限集合，rrRVVU是属性值的集合，Vr表示了属性任意rR时的属性值范围，:rfURV是一个信息函数，它指定U中每一个对象x的属性值.当R中的属性集可进一步分解为条件属性集合C和决策属性集合D，且满足,RCDCD时，信息系统(IS)称为决策系统(DS)3.ai为某一条件属性，则决策属性D对某一条件属性ai的依赖程度可以利用下式计算4-5：1马笑潇,黄席樾,等.基于信息熵的诊断过程认知信息流分析[J].重庆大学学报：自然科学版,2002,25(5):25-28.2王园,吉国力,魏磊.信息熵在临床定量诊断分析中的研究及应用[J].厦门大学学报：自然科学版,2004,43(B08):353-356.3张文宇.数据挖掘与粗糙集方法[M].西安电子科技大学出版社,2007:49.4屈利,苑津莎,李丽.基于事例推理的电力系统短期负荷预测[J].电力科学与工程,2008,24(2):59-63.（4）式中，RC、RD分别表示条件属性集合C和策属性集合D在论域上的等价关系.()DCRHR表示RD相对于RC的条件熵.(,)iIaD的值越大，则条件属性ai对决策属性D的重要性越大.如果(,)0iIaD，则说明ai对于D不起作用，可以删除.在基于属性信息增益的约简方法中，计算案例库属性集的每个属性的信息增益，并约定属性的信息增益大于某个阈值时就将该属性归入最优属性子集，否则弃用属性.1.3基于互信息的特征选择6：三种经典的基于互信息的特征选择算法，分别为信息增益、互信息和交叉熵，以及于互信息最大化的特征选择算法7。结合互信息的计算公式可知,信息增益方法计算出的结果也是一种互信息。若将互信息看成两个随机变量之间的关系,则信息增益表示随机变量C={c1,c2,…,ck}与随机变量T*={t,t}之间的关系,而互信息最大化研究的是随机变量C={c1,c2,…,ck}与随机变量T={t1,t2,…,tm}之间的关系。每个特征的信息增益的计算是独立的,与其它特征的分布无关。而互信息最大化将所有的特征看成一个整体,计算随机变量T所能提供的关于随机变量C的互信息,并计算出每个特征对该互信息的贡献。苗夺谦8等人提出的基于互信息的知识约简算法,是建立在条件属性对决策属性的互信息基础上的;文9提出了一种基于互信息增益率的属性约简算法;颜艳等10提出了一种改进的互信息的属性约简算法，基于改进的互信息的启发式算法，并比对互信息、互信息增益率和文中提出的改进的互信息为属性重要性度量方法的启发式知识约简算法。熵的公式：联合熵：5程其云,孙才新,周湶,等.粗糙集信息熵与自适应神经网络模糊系统相结合的电力短期负荷预测模型及方法[J].电网技术,2004,28(17):72-75.6LiYF,XieM,GohTN.Astudyofmutualinformationbasedfeatureselectionforcasebasedreasoninginsoftwarecostestimation[J].ExpertSystemswithApplications,2009,36(3,Part2):5921-5931.7唐亮,段建国,许洪波,梁玲.基于互信息最大化的特征选择算法及应用[J].计算机工程与应用,2008,44(13):130-1338苗夺谦,胡桂容.知识约简的一种启发式算法[J].计算机研究与发展,1999,36(6):681-684.9贾平,代建华,潘云鹤,等.一种基于互信息增益率的新属性约简算法[J].浙江大学学报(工学版),2006,40(6):1041-1044.10颜艳,杨慧中.一种基于互信息的粗糙集知识约简算法[J].清华大学学报(自然科学版),2007,47(S2):1903-1906.条件熵：联合熵和条件熵的关系：1.3.1互信息（MI）互信息是衡量不考虑特征分布的两个特征之间的一般依赖性.互信息越大，这两个随机变量之间的联系月越紧密.当互信息趋近于零时，这两者之间相互独立.特征和类之间的互信息：P（wi）是特征wi的概率，表示wi没有发生.P（ci）是类cj的概率，P(cj，wi)是类cj与特征wi的联合概率.是特征之间的互信息.互信息和信息熵之间的联系：互信息和信息熵的关系见图1.图1互信息和信息熵的关系图连续型时，(p(x)，p(y)和p(x，y)都是连续的)计算连续的基因表达变量的熵或互信息，首先要将其离散化，一般采用直方图方法11，并根据表达向量的值域范围选择合适的bin值，联合熵计算可采用二维直方图法.连续变量的互信息计算：第一种，histogram方法(Moddemeijer，1989)，将数据划分成等尺度（直方图）的间隔.该方法在低维度条件下，可以获得满意解；随着数据维度的增多，histogram估算值的精确度呈递减趋势.第二种，usingthecontinuouskernelbaseddensityestimatortoapproximateI(x；y)，asproposedbyKwakandChoi(2002b).利用基于密度评价者的连续核心近似互信息I(x；y)，该方法由KwakandChoi(2002b)提出.给出一个变量x的N个样本，近似密度函数为：（基于互信息特征选择标准：最大的依赖，最大关联，最小冗余）12其中，是Parzen窗口函数（Parzenwindowfunction(Parzen，1962)）；是第i个样本；h是窗口宽度.Parzen已证明了，选择适当的和h，当N趋近于无穷时，近似函数趋近于真实的p(x).通常，可用高斯窗口（Gaussianwindow）：其中，，d是样本x的维度，是z的协方差，以上计算可以利用peng制作的matlab的互信息计算工具包.11SteuerR,KurthsJ,DaubCO,eta.lThemutualinformation:detectingandevaluatingdependenciesbetweenvariables[J].Bioinformatics,2002,18(sup2):231-240.12FeatureSelectionBasedonMutualInformationCriteriaofMax-Dependency,Max-Relevance,andMin-Redundancy基于互信息的特征选择的算法模型建立一个特征选择的模型，可以描述为：设原始特征空间为FR，包含有n个特征，c为分类类别，现要从FR中选择k个最有效的特征，形成一个新的特征空间R，要求kn．利用互信息的特征选择的算法模型，包括二阶段1）内部阶段为：经典的MIFS(Battiti，1994)用来选择特征的m个序数，——找到更高级的该种算法1314。经典的MIFS算法的步骤如下1516：改进的算法：MIFS和MIFS-u算法都是近似算法，随着输入特征的增加，特征选择性能逐渐下降．希望考虑待选输入特征和已选输入特征之间互信息在特征选择过程中的权重是一致的，我们可以用待选输入特征和各个已选输入特征之间互信息J(FF；C)的均值作为待选输入特征和已选输入特征互信息J(FS；C)的近似，这样，权重系数可以取常数，在整个特征选择过程中，考虑与已选输入特征互信息权重的系数是一致的17．2）外部阶段为：最小化训练数据集的基于案例推理的错误，以确定序数m外层阶段解决内层阶段没能解决的问题：确定特征m的最佳序数.假定数据集中有n个特征，MIFS首先用来选择1到n的特征，并形成一连串的特征集：1.3.3比较这n个连续的特征集，找出子集，使得CBR的训练误差（用MMRE衡量）最小.因此，m是特征的最佳序数，是最佳数据集.13UsingMutualInformationforSelectingFeaturesinSupervisedNeuralNetLearning14NovovičováJ,MalíkA,PudilP.FeatureSelectionUsingImprovedMutualInformationforTextClassification[M].2004:1010-1017.15杨打生.特征选择的信息论算法研究[D].东南大学硕士学位论文,2005.16ImprovedMutualInformationFeatureSelectorforNeuralNetworksinSupervisedLearning17杨打生,李泰.信息论特征选择算法的改进[J].商丘职业技术学院学报,2005(4):2.MMRE，meanmagnitudeofrelativeerror，平均相对误差幅度18其中，n代表了对象的序数，指第i个对象的真实影响，指第i个对象的期望影响，小的MMRE指期望误差处在低水平；基于案例推理已选择的特征子集特征选择基于案例推理WEKA软件特征集预测最小化MMRE训练的数据集最大化I(C;fi|s)最小的MMRE?最优的特征集第一阶段“filters”第二阶段“wrappers”图1基于互信息的特征选取（MICBR方法）的框架图1.3.7最大依赖性、最大相关性和最小冗余性的准则19彭汉川，赵军阳等20基于模糊粗糙集的信息熵模型提出最大互信息最大相关熵标准,并根据该标准设计了一种新的特征选择方法,能同时处理离散数据、连续数据和模糊数据等混合信息。属性子集中单个属性与决策类之间互信息均值的最大值.相关熵来度量条件属性集的独立性.基于最大互信息最大相关熵标准MmMice,提出一种新的特征选择算法FS-mMC。该算法采用启发式前向搜索,初始为空集,每次选择具有最大互信息的属性添加到特征子集中,如果该属性使子集的相关熵增大,即冗余性减少,则保留该属性,否则去除该属性.1.3.8基于互信息梯度优化计算的信息判别特征提取将互信息梯度优化引入特征提取矩阵求解，提出一种信息判别分析的特征提取方法，建立了类条件分布参数模型下互信息最大化的信息判别模型，证明了互信息判别的线性变换不变性和贝叶斯一致优化，构造了一个互信息梯度优化计算的特征提取算法(Huang&Chiu,2006).19PengH.FeatureSelectionBasedonMutualInformation:CriteriaofMax-Dependency,Max-Relevance[J].IEEETRANSACTIONSONPATTERNANALYSISANDMACHINEINTELLIGENCE,2005,27(8):1126-1138.20赵军阳,张志利.基于最大互信息最大相关熵的特征选择方法[J].计算机应用研究,2009,26(1):233-23521。论述了高斯分布假设下的该互信息判据的类可分特性,并证明了现有典型算法都是本算法的特例;然后,在给出该互信息判据严格的数学意义基础上,提出了基于矩阵特征向量分解计算最优化特征规模算法22。作为高维数据分离度度量的有效工具，互信息建立了特征提取向量和数据分类信息的内在关系，产生了特征提取的信息判据分析方法23。分析特征向量和分类判别关系的基础上，在判据目标函数中引入互信息的罚函数