基于互信息的特征选择 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是属性值

的集合，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. 6 Li Y F, Xie M, Goh T N. A study of mutual information based feature selection for case based reasoning in software cost estimation [J]. Expert Systems with Applications, 2009, 36(3, Part 2): 5921-5931. 7唐亮,段建国,许洪波,梁玲.基于互信息最大化的特征选择算法及应用[J]. 计算机工程与应用,2008,44(13):130-133 8苗夺谦,胡桂容.知识约简的一种启发式算法[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估算值的精确度呈递减趋势. 第二种，using the continuous kernel based density estimator to approximate I(x；y)， as proposed by Kwak and Choi (2002b). 利用基于密度评价者的连续核心近似互信息I(x；y)，该方法由Kwak and Choi (2002b)提出. 给出一个变量x的N个样本，近似密度函数为：（基于互信息特征选择标准： 最大的依赖，最大关联， 最小冗余）12

其中，是Parzen窗口函数（Parzen window function (Parzen， 1962)）；是第i个样本；h是窗口宽度.Parzen已证明了，选择适当的和h，当N趋近于无穷时，近似函数趋近于真实的p(x). 通常，可用高斯窗口（Gaussian window）：

其中，，d是样本x的维度，是z的协方差， 以上计算可以利用peng制作的matlab的互信息计算工具包.

11 SteuerR, Kurths J, DaubC O, eta.l Themutual information: detecting and evaluating dependencies between variables [J]. Bioinformatics, 2002,18( sup2):231-240. 12 Feature Selection Based on Mutual Information Criteria of Max-Dependency, Max-Relevance, and Min-Redundancy http://www.mathworks.com/matlabcentral/fileexchange/14888-mutual-information-computation 1.3.2 基于互信息的特征选择的算法模型 建立一个特征选择的模型，可以描述为：设原始特征空间为FR，包含有n个特征，c为分类类别，现要从FR中选择k个最有效的特征，形成一个新的特征空间R ，要求k< n． 利用互信息的特征选择的算法模型，包括二阶段 1）内部阶段为：经典的 MIFS (Battiti， 1994)用来选择特征的m个序数，——找到更高级的该种算法1314。经典的MIFS算法的步骤如下1516：

改进的算法： MIFS和 MIFS-u算法都是近似算法，随着输入特征的增加，特征选择性能逐渐下降．希望考虑待选输入特征和已选输入特征之间互信息在特征选择过程中的权重是一致的，我们可以用 待选输入特征 和各个已选输入特征 之间互信息J(F F ；C)的均值作为待选输入特征和已选输入特征互信息J(F S；C) 的近似，这样，权重系数可以取常数，在整个特征选择过程中，考虑与已选输入特征互信息权重的系数是一致的17．

2）外部阶段为：最小化训练数据集的基于案例推理的错误，以确定序数m 外层阶段解决内层阶段没能解决的问题：确定特征m的最佳序数.假定数据集中有n个特征，MIFS首先用来选择1到n的特征，并形成一连串的特征集：

1.3.3 比较这n个连续的特征集 ，找出子集，使得CBR的训练误差（用MMRE衡量）

最小.因此，m是特征的最佳序数，是最佳数据集.

13 Using Mutual Information for Selecting Features in Supervised Neural Net Learning 14 Novovičová J, Malík A, Pudil P. Feature Selection Using Improved Mutual Information for Text Classification [M]. 2004: 1010-1017. 15 杨打生.特征选择的信息论算法研究[D].东南大学硕士学位论文, 2005.

16 Improved Mutual Information Feature Selector for Neural Networks in Supervised Learning 17杨打生, 李泰. 信息论特征选择算法的改进[J].商丘职业技术学院学报,2005(4):2.