基于互信息的特征选择
1. 模型
定义D1 病集S由有关心脏病病种（i=1，2，…，n）组成，令患者的疾病信息熵 - 为：
(1)
显然疾病信息熵具有Shannon信息熵的性质，反映了临床中具体病人的客观信息及实际医疗干预过程中所表现的信息在总体特征上的平均不确定性.
定义D2：一个诊断病例库可以表示为关于病例特征的矩阵形式
(2)
其中，—病例库中第个病例的第个属性值；
m—病例特征数量；
n—病例库规模；
定义D3：一个信息系统（IS）可以表达为
(3)
其中，U 是对象的非空有限集合， R是属性的非空有限集合，是属性值的集合，Vr 表示了属性任意时的属性值范围， 是一个信息函数，它指定U中每一个对象 x 的属性值.
当R中的属性集可进一步分解为条件属性集合C和决策属性集合D，且满足时，信息系统(IS)称为决策系统(DS) . ai为某一条件属性，则决策属性D对某一条件属性ai的依赖程度可以利用下式计算 - ：
（4）
式中，RC、RD 分别表示条件属性集合C和策属性集合D在论域上的等价关系.表示RD 相对于RC 的条件熵.的值越大，则条件属性ai对决策属性D的重要性越大.如果，则说明ai对于D不起作用，可以删除.在基于属性信息增益的约简方法中，计算案例库属性集的每个属性的信息增益，并约定属性的信息增益大于某个阈值时就将该属性归入最优属性子集，否则弃用属性.
基于互信息的特征选择 ：
三种经典的基于互信息的特征选择算法，分别为信息增益、互信息和交叉熵，以及于互信息最大化的特征选择算法 。
结合互信息的计算公式可知,信息增益方法计算出的结果也是一种互信息。若将互信息看成两个随机变量之间的关系,则信息增益表示随机变量C={c1,c2,…,ck}与随机变量T*={t,t}之间的关系,而互信息最大化研究的是随机变量C={c1,c2,…,ck}与随机变量T={t1,t2,…,tm}之间的关系。每个特征的信息增益的计算是独立的,与其它特征的分布无关。而互信息最大化将所有的特征看成一个整体,计算随机变量T所能提供的关于随机变量C的互信息,并计算出每个特征对该互信息的贡献。
苗夺谦 等人提出的基于互信息的知识约简算法,是建立在条件属性对决策属性的互信息基础上的;文 提出了一种基于互信息增益率的属性约简算法; 颜艳等 提出了一种改进的互信息的属性约简算法，基于改进的互信息的启发式算法，并比对互信息、互信息增益率和文中提出的改进的互信息为属性重要性度量方法的启发式知识约简算法。
熵的公式：
联合熵：
条件熵：
联合熵和条件熵的关系：
互信息（MI）
互信息是衡量不考虑特征分布的两个特征之间的一般依赖性.
互信息越大，这两个随机变量之间的联系月越紧密.当互信息趋近于零时，这两者之间相互独立.
特征和类之间的互信息：P（wi）是特征wi的概率， 表示wi没有发生.P（ci）是类cj的概率，P(cj，wi)是类cj与特征wi的联合概率.
是特征之间的互信息.
互信息和信息熵之间的联系：
互信息和信息熵的关系见图1.
图1 互信息和信息熵的关系图
连续型时，(p(x)， p(y) 和p(x，y)都是连续的)
计算连续的基因表达变量的熵或互信息，首先要将其离散化，一般采用直方图方法 ，并根据表达向量的值域范围选择合适的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个样本，近似密度函数为：（基于互信息特征选择标准： 最大的依赖，最大关联， 最小冗余）
其中，是Parzen窗口函数（Parzen window function (Parzen， 1962)）；是第i个样本；h是窗口宽度.Parzen已证明了，选择适当的和h，当N趋近于无穷时，近似函数趋近于真实的p(x).
通常，可用高斯窗口（Gaussian window）：
其中，，d是样本x的维度，是z的协方差，
以上计算可以利用peng制作的matlab的互信息计算工具包.
基于互信息的特征选择的算法模型
建立一个特征选择的模型，可以描述为：设原始特征空间为FR，包含有n个特征，c为分类类别，现要从FR中选择k个最有效的特征，形成一个新的特征空间R ，要求k< n．
利用互信息的特征选择的算法模型，包括二阶段
1）内部阶段为：经典的 MIFS (Battiti， 1994)用来选择特征的m个序数，——找到更高级的该种算法 。经典的MIFS算法的步骤如下 ：
改进的算法：
MIFS和 MIFS-u算法都是近似算法，随着输入特征的增加，特征选择性能逐渐下降．希望考虑待选输入特征和已选输入特征之间互信息在特征选择过程中的权重是一致的，我们可以用 待选输入特征 和各个已选输入特征 之间互信息J(F F ；C)的均值作为待选输入特征和已选输入特征互信息J(F S；C) 的近似，这样，权重系数可以取常数，在整个特征选择过程中，考虑与已选输入特征互信息权重的系数是一致的 ．
2）外部阶段为：最小化训练数据集的基于案例推理的错误，以确定序数m
外层阶段解决内层阶段没能解决的问题：确定特征m的最佳序数.假定数据集中有n个特征，MIFS首先用来选择1到n的特征，并形成一连串的特征集：
比较这n个连续的特征集
，找出子集，使得CBR的训练误差（用MMRE衡量）最小.因此，m是特征的最佳序数，是最佳数据集.
MMRE，mean magnitude of relative error ，平均相对误差幅度
其中，n代表了对象的序数，指第i个对象的真实影响，指第i个对象的期望影响，小的MMRE指期望误差处在低水平；
图1 基于互信息的特征选取（MICBR方法）的框架图
最大依赖性、最大相关性和最小冗余性的准则
彭汉川，
赵军阳等 基于模糊粗糙集的信息熵模型提出最大互信息最大相关熵标准,并根据该标准设计了一种新的特征选择方法,能同时处理离散数据、连续数据和模糊数据等混合信息。属性子集中单个属性与决策类之间互信息均值的最大值. 相关熵来度量条件属性集的独立性. 基于最大互信息最大相关熵标准MmMi ce,提出一种新的特征选择算法FS-mMC。该算法采用启发式前向搜索,初始为空集,每次选择具有最大互信息的属性添加到特征子集中,如果该属性使子集的相关熵增大,即冗余性减少,则保留该属性,否则去除该属性.
基于互信息梯度优化计算的信息判别特征提取
将互信息梯度优化引入特征提取矩阵求解，提出一种信息判别分析的特征提取方法，建立了类条件分布参数模型下互信息最大化的信息判别模型，证明了互信息判别的线性变换不变性和贝叶斯一致优化，构造了一个互信息梯度优化计算的特征提取算法 。
论述了高斯分布假设下的该互信息判据的类可分特性,并证明了现有典型算法都是本算法的特例;然后,在给出该互信息判据严格的数学意义基础上,提出了基于矩阵特征向量分解计算最优化特征规模算法 。
作为高维数据分离度度量的有效工具，互信息建立了特征提取向量和数据分类信息的内在关系，产生了特征提取的信息判据分析方法 。
分析特征向量和分类判别关系的基础上，在判据目标函数中引入互信息的罚函数机制 。
通过启发式迭代优化进行混合模型的极大似然拟合，一定程度上克服了罚函数的过度拟合 。
Adaboost-互信息的 CBR
CBR智能体的集成学习，典型的继承算法包括 boosting、bagging和stacking ：
A new problem is solved as the weighted vote of all the Agents' solutions. 每个CBR智能体都有其案例库，用来整合智能体的经验.
Bagging包括使用权重投票方案，但是在这种案例中中经验并没有针对每个智能体，以致互补性（complementarity）学习者的the construction is left to chance and the variability 学习方法.
Stacking技术中每个智能体使用不同的推理方法.
Adaboost算法
Boosting CBR的核心问题是每个智能体的权重设置.Adaboost是该领域的最著名的学习算法，（AdaBoost 算法是1995 年提出的一种快速人脸检测算法，Adaboost是一种迭代算法，其核心思想是针对同一个训练集训练不同的分类器 (弱分类器)，然后把这些弱分类器集合起来，构成一个更强的最终分类器(强分类器).其算法本身是通过改变数据分布来实现的，它根据每次训练集之中每个样 本的分类是否正确，以及上次的总体分类的准确率，来确定每个样本的权值.将修改过权值的新数据集 送给下层分类器进行训练，最后将每次训练得到的分类器最后融合起来，作为最后的决策分类器.使用adaboost分类器可以排除一些不必要的训练数据特 徵，并将关键放在关键的训练数据上面.）
将弱学习机按其相应的权重加权组合形成强学习机，准确率越高的弱学习机权重越高
Boosting训练器内部结构：训练集特征向量输入（1） --> 直方图计算（2） --> 选择准确率最高的一 维作为弱学习机（3） --> 根据公式计算相应的权重，调整样本分布（4） --> 转向（3）直到到达规定的循环次数 --> 输出加权组合后的分类器。
Boosting的思想源泉： 将一系列粗略的规则加权组合起来得到高度精确的规则。
Boosting的数学实质： 对目标函数（损失函数）的最优化问题；损失函数形式不同，优化方法不同；
Boosting的理论联系：熵映射；对数回归；
改进方向：用遗传算法学习boosting权重，提出遗传算法优于AdaBoost 算法（存在贪婪行为）
为了Boosting目的，将在CBR智能体合作解决问题的多智能体的环境中，应用遗传算法，
基于熵的AdaBoost分类器
Adaboost方法能够“聚焦于”那些较困难(更富信息)的样本上。令每个样本的权重相等，对于第k次迭代操作,我们就根据这些权重来选择样本点,进而训练分类器Ck，根据这个分类器,来提高被它错分的那些样本点的权重,并减低可以被正确分类的样本权.然后,权重更新过的样本集被用来训练下一个分类器Ck+1 .
基于Boosting 的条件互信息Conditional Mutual Information based Boosting(CMIB)
，
最大熵特征选取
特征选择方法MEFS(maximum entropy feature selection).MEFS在基于最大熵原理的基础上,运用互信息和Z-测试技术,采用两步方法进行空间特征选择。对MEFS方法和RELIEF方法以及基于MEFS的分类方法与决策树算法ID3分别进行了实验比较。
互信息增益率
为了获得决策系统中更好的相对属性约简%提出了一种基于互信息增益率的属性约简算法<该算法考虑了 所选择条件属性与决策属性的互信息%还考虑了所选择属性的值的分布情况%从信息论角度定义了基于互信息增 益率的属性重要性度量方法%并以此度量为启发式信息%算法从空集开始逐步将最重要的条件属性加入到选择属 性集%直到所选择的条件属性集与决策属性集的互信息等于整个条件属性集与决策属性集的互信息时%算法停止< 结果表明%算法能更有效地对决策系统进行约简%同时约简后的对象数目较少.
中对以互信息增益和本文的互信息增益率为度量的方法进行了数据集对照<
2. 仿真数据
用UCI 机器学习数据库中的心脏病诊断数据集cleveland 作为例子, 该数据集由医学博士Robert Detrano 收集, 包括303 个病例, 13 个条件属性(age, sex, cp, trestbps, chol, fbs,restecy, thalach, exang,oldpeak, slope, ca, thal), 1 个决策属性(num) 。
将数据集分为两部分, 其中223 个对象作为训练数据, 其余80个作为测试数据。
任一样本的特征的数据结构
ID
特征(Features)
Full name
属性说明Description
1
Age
年龄
age: age in years
2
Sex
性别
sex: sex (1 = male； 0 = female)
3
Cp
胸痛类型
cp: chest pain type -- Value 1: typical angina -- Value 2: atypical angina -- Value 3: non-anginal pain -- Value 4: asymptomatic
4
Trestbps
静脉压
trestbps: resting blood pressure (in mm Hg on admission to the hospital)
5
Chol
每毫升血液中的血清重量mg
chol: serum cholestoral in mg/dl
6
Fbs
每毫升的血糖浓度是否超过120mg
fbs: (fasting blood sugar > 120 mg/dl)
(1 = true； 0 = false)
7
Restecg
安静时的心电图结果
restecg: resting electrocardiographic results -- Value 0: normal -- Value 1: having ST-T wave abnormality (T wave inversions and/or ST elevation or depression of > mV) -- Value 2: showing probable or definite left ventricular hypertrophy by Estes' criteria
8
Thalach
最高心率
thalach: maximum heart rate achieved
9
Exang
是否运动导致心绞痛
exang: exercise induced angina (1 = yes； 0 = no)
10
Oldpeak
运动所导致的ST下降
oldpeak = ST depression induced by exercise relative to rest
11
Slope
峰值ST倾斜角度
slope: the slope of the peak exercise ST segment -- Value 1: upsloping -- Value 2: flat -- Value 3: downsloping
12
Ca
主血管数量
ca: number of major vessels (0-3) colored by flourosopy
13
Thal
心跳情况
thal: 3 = normal； 6 = fixed defect； 7 = reversable defect
14
num
num: diagnosis of heart disease (angiographic disease status) -- Value 0: < 50% diameter narrowing -- Value 1: > 50% diameter narrowing (in any major vessel: attributes 59 through 68 are vessels)
样本数据
样本数据（大于15）
特征
样本编号
Age
Sex
Disese（是否患有心脏病）
1
2
3
4
验证方法
利用朴素Bayes(NB)和TFIDF算法进行分类
结合新西兰Waikato大学开发的WEKA软件,将选择结果与CFS、Re-lief和InfoGain算法进行了比较,并分别在C4. 5、Bagging和NaiveBayes条件下对每种算法选择的各个数据集的特征子集进行分类精度评价25。
3. 预期结果
特征筛选与数据处理
影响心脏病种类的动脉氧含量的信息熵计算
动脉氧含量
A1类心脏病
A2类心脏病
例数
概率
H1（X）
例数
概率
H2（X）
<50
50—65
65—80
80>
RELIEF、SSGA、MIFS和FMIFS的特征选取的比较 ：
(1) Feature selection with RELIEF.
(2) Feature selection with SSGA.
(3) Feature selection with MIFS.
(4) Feature selection with FMIFS.
4. 结果分析
特征选取是基于案例推理的重要环节.当前基于案例推理的特征选取是是“‘wrappers’ (Kohavi & John， 1997).”，wrappers可以产生高拟合精度，但是计算复杂和所选特征对于其他条件具有较低的普适性.
另一特征选取的方式是“‘filters’(Almuallim & Dietterich， 1994； Kohavi & John， 1997)”，相对于wrappers来讲计算更为简单，所选的特征对其他条件具有更高的普适性.
本方案提出基于互信息的混合包装（wrappers）和过滤（‘filters’）的特征选择方法——MICBR.为了验证该方法，使用了真实的数据集：
第一步，过滤（‘filters’）特征选择，通过调整CBR的参数设置；
第二步，所提出MICBR的与其他基于案例推理的特征选取的“包装”（wrappers）方法（(exhaustive search， hill climbing， and forward sequential selection)）相比较，预测结果表明MICBR方法比其他方法所取得的训练数据集的预测结果（普适性）更好，但其调整训练数据集反而不及它们.
5. 结论
马笑潇, 黄席樾, 等. 基于信息熵的诊断过程认知信息流分析[J]. 重庆大学学报：自然科学版, 2002,25(5):25-28.
王园, 吉国力, 魏磊. 信息熵在临床定量诊断分析中的研究及应用[J]. 厦门大学学报：自然科学版, 2004,43(B08):353-356.
张文宇. 数据挖掘与粗糙集方法[M]. 西安电子科技大学出版社, 2007: 49.
屈利, 苑津莎, 李丽. 基于事例推理的电力系统短期负荷预测[J]. 电力科学与工程, 2008,24(2):59-63.
程其云, 孙才新, 周湶, 等. 粗糙集信息熵与自适应神经网络模糊系统相结合的电力短期负荷预测模型及方法[J]. 电网技术, 2004,28 (17): 72-75.
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.
唐亮,段建国,许洪波,梁玲.基于互信息最大化的特征选择算法及应用[J]. 计算机工程与应用,2008,44(13):130-133
苗夺谦,胡桂容.知识约简的一种启发式算法[J].计算机研究与发展, 1999,36(6): 681 - 684.
贾平,代建华,潘云鹤,等.一种基于互信息增益率的新属性约简算法[J].浙江大学学报(工学版), 2006,40(6):1041 - 1044.
颜艳,杨慧中.一种基于互信息的粗糙集知识约简算法[J]. 清华大学学报(自然科学版),2007,47(S2):1903-1906.
SteuerR, Kurths J, DaubC O, Themutual information: detecting and evaluating dependencies between variables [J]. Bioinformatics, 2002,18( sup2):231-240.
Feature Selection Based on Mutual Information Criteria of Max-Dependency, Max-Relevance, and Min-Redundancy
Using Mutual Information for Selecting Features in Supervised Neural Net Learning
Novovičová J, Malík A, Pudil P. Feature Selection Using Improved Mutual Information for Text Classification [M]. 2004: 1010-1017.
杨打生.特征选择的信息论算法研究[D].东南大学硕士学位论文, 2005.
Improved Mutual Information Feature Selector for Neural Networks in Supervised Learning
杨打生, 李泰. 信息论特征选择算法的改进[J].商丘职业技术学院学报,2005(4):2.
(Huang & Chiu, 2006).
Peng H. Feature Selection Based on Mutual Information: Criteria of Max-Dependency, Max-Relevance [J]. IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, 2005, 27(8): 1126-1138.
赵军阳, 张志利. 基于最大互信息最大相关熵的特征选择方法[J]. 计算机应用研究,2009,26(1):233-235
谢文彪,樊绍胜,费洪晓,樊晓平. 基于互信息梯度优化计算的信息判别特征提取[J]. 电子与信息学报,2009,31(12):2975-2979.
谢文彪,樊绍胜,樊晓平.一种可最优化计算特征规模的互信息特征提取[J]. 控制与决策,2009,24(12):1810-1815
Hild II K E, Erdogmus D, and Torkkola K. Feature extraction using information-theoretic learning [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2006, 28(9): 1385-1392.
Padmanabhan M and Dharanipragada S. Maximizing information content in feature extraction [J]. IEEE Transactions on Speech Audio Processing, 2005, 13(4): 512-519.
Leiva-Murillo J M and Artés-Rodríguez A. Maximization of mutual information for supervised linear feature extraction [J]. IEEE Transactions on Neural Networks, 2007, 18(5): 1433-1440.
López B, Pous C, Pla A, et al. Boosting CBR Agents with Genetic Algorithms [M]. 2009: 195-209.
Boosting原理及在分类上的应用
刘天键.基于熵的特征选择的AdaBoost改进算法[J]. 闽江学院学报,2009,30(2):60-64. 烂文献
Caifeng Shan S G, Peter W. Mcowan Conditional Mutual Infomation Based Boosting for Facial Expression Recognition [J]. 2005
宋国杰, 唐世渭, 杨冬青,王腾蛟. 基于最大熵原理的空间特征选择方法[J]. 软件学报.2003(14):9
贾平,代建华,潘云鹤,朱淼良. 一种基于互信息增益率的新属性约简算法[J]. 浙江大学学报(工学版).2006(40):6
UCI 机器学习数据库网址.UCI Repository of machine learning atabases [DB/OL]. mlearn/.
Sánchez L, Rosario Suárez M, Villar J R, et al. Mutual information-based feature selection and partition design in fuzzy rule-based classifiers from vague data [J]. International Journal of Approximate Reasoning, 2008, 49(3): 607-622.
PAGE
PAGE 2
基于案例推理
已选择的
特征子集
特征选择
基于案例推理
WEKA软件
特征集
预测
最小化MMRE
训练的数据集
最大化I(C;fi|s)
最小的MMRE?
最优的特征集
第一阶段
“filters”
第二阶段“wrappers”
