什么是邻域互信息?如何基于互信息进行特征选择?

对于什么是互信息,我们之前已经知道:它是衡量不同变量之间相关性的有效标准,它描述了两个随机变量之间的共享信息。可以参考文章:什么是互信息

由互信息的定义可以知道,当随机变量 X 和 Y 没有共享信息时,互信息为最小值0,当随机变量 X 和Y 间的共享信息越多或者说两变量以来成都越强,他们之间互信息的值越大。

基于互信息的特征选择

由上面介绍可知,我们进行特征选择的目的,就是让互信息作为度量,让最终筛选得到的特征子集包含更多的有价值的信息,且有更少的冗余信息。

这时候,我们利用特征标签之间的依赖性来作为筛选标准,依赖性越弱,说明其携带的信息越多,冗余性越少。

那么特征选择算法基于三个概念:最大特征相关性、最小化特征冗余性、最大化特征互补性。相关计算方法

邻域互信息

在属性取值为连续型的数据中,互信息便不再适用,此时我们所选方法为邻域互信息。

相关定义如下:

定义一:

设 U 是非空集合,若 \forall x_i , x_j ,x_k \isin U ,都存在唯一确定的实函数 \varDelta 与之对应,并且 \varDelta 满足:

  1. \varDelta (x_i,x_j) \geqslant 当且仅当 x_i= x_j,\varDelta (x_i,x_j) = 0
  2. \varDelta (x_i,x_j) = \varDelta (x_j,x_i)
  3. \varDelta (x_i,x_k) \leqslant \varDelta (x_i,x_j)+ \varDelta (x_j,x_k)

则称, \varDelta 是 U 上的距离函数, <U, \varDelta> 是度量空间。一般将距离函数定义为闵可夫斯基距离:

\varDelta_p(x_i,,x_j) = [\sum_{l=1}^N(x_{li},x_{lj})^P]^{\frac {1}{ p}}

当 P = 1时, \varDelta 表示为曼哈顿距离,当 P = 2时, \varDelta 则表示为欧式距离。

定义二:

<U, \varDelta> 是非空度量空间,则 x \isin U , \delta \geqslant 0 称作点集

\delta(x) = \{ y| \varDelta(x , y) \leqslant \delta , y \isin U \}

为 x 在度量空间的邻域,概率与可以表示为球心在 x 点处,半径为 \delta 的闭球。若度量函数 \varDelta 采用欧氏距离时,则样本 x 的邻域是球心在 x 点,半径为 \varDelta 的超球体。

定义三:

给定论域 U ,C 是指描述 U 的条件属性,D 是决策属性。 根据 C 可生成一组论域上的邻域关系 R ,则称 NDT =<U, R, D >为邻域近似空间。

定义四:

给定论域空间 \{ x_1,x_2,......,x_n \} ,条件属性 C , A \subseteq C ,N_A 表示为特征子集 A 诱导的邻域关系。则记 x_i 根据属性 A 计算得到的邻域为 \delta _A{(x_i)}那么邻域粒子的不确定性为:

NH_{\delta}^{x_i}(A) = - lb \dfrac{|\delta_A{(x_i)}|}{n}

此处是以 2 为底。相应地,邻域近似空间<U, N_A > 的不确定性为:

NH_{\delta}(A) = - {1 \over n }lb \dfrac{|\delta_A{(x_i)}|}{n}

由于 \forall x_i , \delta _A \isin U , |\delta _A (x_i)| / n \leqslant 1 因此 lb n \geqslant NH_{\delta}(A) \geqslant 0 。当且仅当 \forall x_i , \delta _A (x_i) = 1 ,有 NH_{\delta} = lb n 。当且仅当 \forall x_i , \delta _A (x_i) =n ,有 NH_{\delta} = 0

定义五:

当且仅当 A,B \isin C 是刻画论域的两组特征子集,x_i 在 A \cup B 上的邻域记为 \delta _{A \cup B}(x_i) 那么 A 和B 的联合熵可以定义为:

NH_{\delta}(A,B) = - {1 \over n } \sum _{i=1} ^n lb \dfrac{|\delta_{A \cup B}{(x_i)}|}{n}

当 C 是决策属性时,有 \delta _{A \cup B }(x_i ) = \delta_A (x_i) \cap c_{x_i} 此时有:

NH_{\delta}(A,C) = - {1 \over n } \sum _{i=1} ^n lb \dfrac{|\delta_{A}{(x_i)} \cap c_{x_i}|}{n}

定义六:

A,B \isin C 是刻画论域的两组特征子集,给定特征子集 A ,则B相对于A的邻域条件熵为:

NH_{\delta}(B|A) = - {1 \over n } \sum _{i=1} ^n lb \dfrac{|\delta_{A \cup B}{(x_i)}|}{|\delta_A(x_i )|}

定义七:

A,B \isin C 是刻画论域的两组特征子集,A 和B 的邻域互信息可定义为:

NMI_{\delta}(B;A) = - {1 \over n } \sum _{i=1} ^n lb \dfrac{|\delta_{A}{(x_i)}|*|\delta_B(x_i)|}{n|\delta_{A \cup B }(x_i )|}
赞 (1)