·596 智能系统学报 第12卷 互信息是一种衡量两个随机变量之间相互依 H(X)=-px(x)logpx(x)dx (4) 赖强弱程度的准则，其来源于信息论中嫡的概 念劉。采用互信息进行特征选择主要有以下两个 H(Y)=-p(y)logp(y)dy (5) 难点：1)特征评价策略；2)互信息的准确估计。针 对评价策略，Battiti等[]提出了MFS(mutual H(X.Y)=-px.x(x.y)logpx.x(x.y)dxdy(6) information feature selection)方法，通过平衡相关特 根据式(4)、(5)和(6)，式(3)还可以表示为 征和冗余特征的选择，取得了较好的效果，此后， I(X;Y)=H(X)+H(Y)-H(X,Y) (7) Peng等o、Fleuret、Yang等Ia、Brown[)和韩 等都分别提出了各自的评价策略。上述方法主 2 高维k-近邻互信息理论 要是采用一维互信息来衡量特征好坏，当存在冗余 2.1 高维k-近邻互信息的估计 特征时，并不能保证得到最优特征子集。互信息的 Kraskov等7-8]提出的k-近邻法通过数据直接 估计一般通过非参数方式[6)求解概率密度函数 近似估计特征的互信息，避免了对概率密度分布的 来实现，主要有直方图法和核函数法。近几年发展 近似估计。其基本思想是，在由随机变量X和Y构 的k-近邻法(k-nearest neighbors,kNN)I-I8]构建的 成的空间中对于给定的N个样本首先找出它的k 数据驱动型特征选择框架，无需假设概率密度函数 个近邻，再找出其他样本分别在X和Y方向到当前 形式，避免了对概率密度函数的估计，其基础理论 样本的距离小于当前样本到k个近邻距离的最大值 完备，非常适合具有非线性不规则分布特点的实际 的数目，通过统计数目从而进行互信息的估计。 数据，但是高维k-近邻互信息的估计存在一定困难。 现将其扩展到高维互信息的估计，高维互信息 因此，本文在k-近邻互信息基础上将其扩展用 计算的具体思路如下8]： 于高维互信息的估计，然后采用前向累加后向交叉 给定N个样本z=[(x)r(y)T]T(i=1, (forward accumulation and backward cross,FABC) 2,…,N),其中x0∈Rd且y0∈RP。如果z和z 最优特征子集选择策略，构建kNN-FABC的特征选 为数据集中两个不同的向量，则 择方法，最后以Friedman数据、Housing数据和实际 ‖z-z'‖=max(‖x-x'I,Iy-y'I)(8) 污水处理出水总磷预测数据为例进行仿真实验，并 式中·【表示取最大范数。 结合多层感知器(multilayer perceptron,MLP)预测 若z⊙的k-近邻为z》=[(x)T(y)T]T, 模型来验证所提特征选择方法的有效性。 则z)与z)之间的Euclidean距离为 e0=‖z0-z)1三 1互信息理论 max((() (9) 互信息是一种衡量两个随机变量之间相互依 对于z)中的分量x0和y0有 赖强弱程度的准则，其来源于信息论中嫡的概念。 e0=-Ir0-xo》‖=maxx0-xo)l 三12， 两个随机变量之间的互信息越大，则两者之间的相 (10) 关性就越强)。 9=0-yo》1=,盟，y9-yo1 对随机变量X和Y来说，设其联合概率密度函 (11) 数为Px.y(x,y),则其边缘概率密度函数为 将与x和y之间距离小于o的样本点个数 ex(x)=exx(x,y)dy (1) 分别记为N和N。因此，变量X和Y之间互信息的 py(y)=Jpx.x(x.y)dx 估计量为 (2) 根据信息论的有关理论[)，随机变量X和Y之 i(x:)=k)-d+P-1+(d+p-1)n- k 间的互信息定义为 三(2心)·三) (12) (x:)()og) ()p(ddy (3) 式中：亚(·)为digama函数，(+1)=亚()+， 式中S为X和Y的定义域。 根据Shannon嫡的定义[)，X、Y的熵和联合熵 (1)≈-0.5772156：k一般取2~6。通过式(12)可以 分别为 发现，(X:Y)不仅与k和N有关，而且与变量X和Y互信息是一种衡量两个随机变量之间相互依 赖强弱 程 度 的 准 则， 其 来 源 于 信 息 论 中 熵 的 概 念［８］ 。 采用互信息进行特征选择主要有以下两个 难点：１）特征评价策略；２） 互信息的准确估计。 针 对评 价 策 略， Ｂａｔｔｉｔｉ 等［９］ 提 出 了 ＭＩＦＳ （ ｍｕｔｕａｌ ｉｎｆｏｒｍａｔｉｏｎ ｆｅａｔｕｒｅ ｓｅｌｅｃｔｉｏｎ） 方法，通过平衡相关特 征和冗余特征的选择，取得了较好的效果，此后， Ｐｅｎｇ 等［１０］ 、 Ｆｌｅｕｒｅｔ ［１１］ 、 Ｙａｎｇ 等［１２］ 、 Ｂｒｏｗｎ ［１３］ 和 韩 等［１４］都分别提出了各自的评价策略。 上述方法主 要是采用一维互信息来衡量特征好坏，当存在冗余 特征时，并不能保证得到最优特征子集。 互信息的 估计一般通过非参数方式［１５－１６］ 求解概率密度函数 来实现，主要有直方图法和核函数法。 近几年发展 的 ｋ⁃近邻法（ｋ⁃ｎｅａｒｅｓｔ ｎｅｉｇｈｂｏｒｓ， ｋＮＮ） ［１７－１８］ 构建的 数据驱动型特征选择框架，无需假设概率密度函数 形式，避免了对概率密度函数的估计，其基础理论 完备，非常适合具有非线性不规则分布特点的实际 数据，但是高维 ｋ⁃近邻互信息的估计存在一定困难。 因此，本文在 ｋ⁃近邻互信息基础上将其扩展用 于高维互信息的估计，然后采用前向累加后向交叉 （ｆｏｒｗａｒｄ ａｃｃｕｍｕｌａｔｉｏｎ ａｎｄ ｂａｃｋｗａｒｄ ｃｒｏｓｓ， ＦＡＢＣ）的 最优特征子集选择策略，构建 ｋＮＮ⁃ＦＡＢＣ 的特征选 择方法，最后以 Ｆｒｉｅｄｍａｎ 数据、Ｈｏｕｓｉｎｇ 数据和实际 污水处理出水总磷预测数据为例进行仿真实验，并 结合多层感知器（ｍｕｌｔｉｌａｙｅｒ ｐｅｒｃｅｐｔｒｏｎ， ＭＬＰ） 预测 模型来验证所提特征选择方法的有效性。 １ 互信息理论 互信息是一种衡量两个随机变量之间相互依 赖强弱程度的准则，其来源于信息论中熵的概念。 两个随机变量之间的互信息越大，则两者之间的相 关性就越强［１７］ 。 对随机变量 Ｘ 和 Ｙ 来说，设其联合概率密度函 数为 ρＸ，Ｙ（ｘ，ｙ） ，则其边缘概率密度函数为 ρＸ（ｘ） ＝ ∫ρＸ，Ｙ（ｘ，ｙ）ｄｙ （１） ρＹ（ｙ） ＝ ∫ρＸ，Ｙ（ｘ，ｙ）ｄｘ （２） 根据信息论的有关理论［１７］ ，随机变量 Ｘ 和 Ｙ 之 间的互信息定义为 Ｉ（Ｘ；Ｙ） ＝ ∬ Ｓ ρＸ，Ｙ（ｘ，ｙ）ｌｏｇ ρＸ，Ｙ（ｘ，ｙ） ρＸ（ｘ）ρＹ（ｙ） ｄｘｄｙ （３） 式中 Ｓ 为 Ｘ 和 Ｙ 的定义域。 根据 Ｓｈａｎｎｏｎ 熵的定义［１７］ ，Ｘ、Ｙ 的熵和联合熵 分别为 Ｈ（Ｘ） ＝ － ∫ρＸ（ｘ）ｌｏｇ ρＸ（ｘ）ｄｘ （４） Ｈ（Ｙ） ＝ － ∫ρＹ（ｙ）ｌｏｇ ρＹ（ｙ）ｄｙ （５） Ｈ（Ｘ，Ｙ） ＝ － ∬ Ｓ ρＸ，Ｙ（ｘ，ｙ）ｌｏｇ ρＸ，Ｙ（ｘ，ｙ）ｄｘｄｙ （６） 根据式（４）、（５）和（６），式（３）还可以表示为 Ｉ（Ｘ；Ｙ） ＝ Ｈ（Ｘ） ＋ Ｈ（Ｙ） － Ｈ（Ｘ，Ｙ） （７） ２ 高维 ｋ⁃近邻互信息理论 ２．１ 高维 ｋ⁃近邻互信息的估计 Ｋｒａｓｋｏｖ 等［１７－１８］提出的 ｋ⁃近邻法通过数据直接 近似估计特征的互信息，避免了对概率密度分布的 近似估计。 其基本思想是，在由随机变量 Ｘ 和 Ｙ 构 成的空间中对于给定的 Ｎ 个样本首先找出它的 ｋ 个近邻，再找出其他样本分别在 Ｘ 和 Ｙ 方向到当前 样本的距离小于当前样本到 ｋ 个近邻距离的最大值 的数目，通过统计数目从而进行互信息的估计。 现将其扩展到高维互信息的估计，高维互信息 计算的具体思路如下［１８］ ： 给定 Ｎ 个样本ｚ （ｉ） ＝ ［（ｘ （ｉ） ） Ｔ （ｙ （ｉ） ） Ｔ ］ Ｔ （ ｉ ＝ １， ２，…，Ｎ） ，其中 ｘ （ｉ） ∈ℝ ｄ 且 ｙ （ｉ） ∈ℝ ｐ 。 如果 ｚ 和 ｚ′ 为数据集中两个不同的向量，则 ‖ｚ － ｚ′‖ ＝ ｍａｘ（‖ｘ － ｘ′‖，‖ｙ － ｙ′‖） （８） 式中‖·‖表示取最大范数。 若ｚ （ｉ） 的ｋ⁃近邻为 ｚ （ｋ（ｉ）） ＝ ［（ｘ （ｋ（ｉ）） ） Ｔ （ｙ （ｋ（ｉ）） ） Ｔ ］ Ｔ ， 则 ｚ （ｉ） 与 ｚ （ｋ（ｉ）） 之间的 Ｅｕｃｌｉｄｅａｎ 距离为 ε （ｉ） ＝ ‖ ｚ （ｉ） － ｚ （ｋ（ｉ））‖ ＝ ｍａｘ（‖ｘ （ｉ） － ｘ （ｋ（ｉ））‖，‖ｙ （ｉ） － ｙ （ｋ（ｉ））‖） （９） 对于 ｚ （ｉ） 中的分量 ｘ （ｉ） 和 ｙ （ｉ） 有 ε （ｉ） ｘ ＝ ‖ｘ （ｉ） － ｘ （ｋ（ｉ））‖ ＝ ｍａｘ ｓ ＝ １，２，…，ｄ ｘ （ｉ） ｓ － ｘ （ｋ（ｉ）） ｓ （１０） ε （ｉ） ｙ ＝ ‖ｙ （ｉ） － ｙ （ｋ（ｉ））‖ ＝ ｍａｘ ｔ ＝ １，２，…，ｐ ｙ （ｉ） ｔ － ｙ （ｋ（ｉ）） ｔ （１１） 将与 ｘ （ｉ） ｓ 和 ｙ （ｉ） ｔ 之间距离小于 ε （ｉ）的样本点个数 分别记为Ｎ （ｉ） ｘｓ 和Ｎ （ｉ） ｙｔ 。 因此，变量Ｘ 和Ｙ 之间互信息的 估计量为 Ｉ ＾ （Ｘ；Ｙ） ＝ Ψ（ｋ） － ｄ ＋ ｐ － １ ｋ ＋ （ｄ ＋ ｐ － １）Ψ（Ｎ） － １ Ｎ∑ Ｎ ｐ ＝ １ ∑ ｄ ｓ ＝ １ Ψ（Ｎ （ｉ） ｘｓ ） ＋ ∑ ｐ ｔ ＝ １ Ψ（Ｎ （ｉ） ｙｔ ( ）) （１２） 式中：Ψ（·）为 ｄｉｇａｍｍａ 函数，Ψ（ｔ ＋１） ＝ Ψ（ｔ） ＋ １ ｔ ， Ψ（１）≈－０．５７７ ２１５ ６； ｋ 一般取 ２～６。 通过式（１２）可以 发现， Ｉ ＾ （Ｘ；Ｙ） 不仅与 ｋ 和 Ｎ 有关，而且与变量 Ｘ 和 Ｙ ·５９６· 智 能 系 统 学 报 第 １２ 卷