一种最小最大局部结构信息的特征选择方法

摘要

本发明公开了一种最小最大局部结构信息的特征选择方法，包括以下步骤：构建一个全局图G和对应的权矩阵W；根据A）步骤中的全局图G和权矩阵W，构建一个近邻图G

说明书

【技术领域】

本发明涉及特征选择的方法，特别涉及最小最大局部结构信息的特征选择 方法。

【背景技术】

在许多机器学习任务中，常常会碰到许多高维数据，如计算视觉和模式识 别中的人脸图像、数据挖掘中的文本数据等，在处理高维数据时，需要很长的 处理时间和可观的存储空间，所以在进行分类、聚类等机器学习任务前，需要 对高维数据进行降维预处理，如特征选择和特征提取，目的是获得一个低维的 特征子集。

一般地，特征选择分为捆绑式和滤波式，捆绑式是利用现有的分类器来评 价各个特征子集，从而找出最优的特征子集。对于某一个特定的分类器而言， 捆绑法可以获得较好效果，但它需要分类器在各个特征子集进行训练，导致计 算复杂度非常高；滤波式则直接利用一个准则函数，如Fisher Score、Laplacian Score等，来评价每个特征的优劣，滤波式特征选择方法又分为无监督和有监督 两种，实际应用中，由于获取标签数据非常难且成本高，而获得无标签数据很 容易，所以无监督滤波式特征选择方法一直得到很大的关注。

在机器学习中，流行学习一直是关注的焦点，为了反映潜在的数据流行结 构，提出了诸如ISOMAP、拉普拉斯特征映射、局部线性嵌入、局部保持投影和 近邻保持投影等特征提取方法和无监督的特征选择方法Laplacian Score， Laplacian Score利用局部不变性保证特征子集保持数据流行结构，但局部结构 信息之间的关系并未考虑，而这种局部结构信息间的关系在机器学习任务扮演 重要作用，因此所获得的特征子集所具备的表示能力有所欠缺。

【发明内容】

本发明的目的就是解决现有技术中的问题，提出一种最小最大局部结构信 息的特征选择方法，提供一种无监督的特征选择准则，使所获得的特征子集具 有更好的表示能力。

为实现上述目的，本发明提出了一种最小最大局部结构信息的特征选择方 法，包括如下步骤：

A)构建一个全局图G和对应的权矩阵W，

$W_{\mathrm{ij}}=\exp (-\frac{{\left|\right|x_i-x_j\left|\right|}^2}{{2t}^2})---\left(1\right)$

其中，x_i和x_j为样本点，t为常量；

B)根据A)步骤中的全局图G和权矩阵W，构建一个近邻图G_w和对应的权矩阵 W_w，

其中，N(x_i)和N(x_j)分别表示样本点x_i和x_j的k个近邻子集；

C)根据B)步骤中计算得到的权矩阵W_w，计算权矩阵A＝W_w-αW，对角矩阵D 和拉普拉斯矩阵L＝D-A，其中0≤α≤1；

D)计算各个特征的最小最大局部结构信息的拉普拉斯指标MMLS_r

${\mathrm{MMLS}}_r=\frac{{{\tilde{f}}_r}^{T}L{\tilde{f}}_r}{{{\tilde{f}}_r}^{T}D{\tilde{f}}_r}---\left(3\right);$

E)根据D)步骤中获得的拉普拉斯指标MMLS_r大小，依次选出d个最小拉普拉斯 指标MMLS_r对应的特征，构成特征子集。

作为优选，所述D)步骤中，f_r＝[X_r1，Λ,X_rm]^T是由数据集矩阵 的第r个特征构成的向量，是第r个特征的数 学期望。。

作为优选，所述D)步骤中提出的最小最大信息准则MMLS_r，

为${\mathrm{MMLS}}_r=\frac{(1-\alpha )\underset{i,j=1}{\overset{m}{\Sigma }}{(f_{\mathrm{ri}}-f_{\mathrm{rj}})}^2{W}_{w,\mathrm{ij}}-\alpha \underset{i,j=1}{\overset{m}{\Sigma }}{(f_{\mathrm{ri}}-f_{\mathrm{rj}})}^2{W}_{b,\mathrm{ij}}}{\mathrm{Var}\left(f_r\right)}---\left(4\right).$

作为优选，所述D)步骤中Var(f_r)是第r个特征的方差，W_w和W_b是权矩阵， 所述0≤α≤1，

且

作为优选，所述D)步骤中提出的最小最大信息准则MMLS_r，包括如下过程： 因为W_w+W_h＝W，故

$(1-\alpha )\underset{i,j=1}{\overset{m}{\Sigma }}{(f_{\mathrm{ri}}-f_{\mathrm{rj}})}^2{W}_{w,\mathrm{ij}}-\alpha \underset{i,j=1}{\overset{m}{\Sigma }}{(f_{\mathrm{ri}}-f_{\mathrm{rj}})}^2{W}_{b,\mathrm{ij}}$

$=\underset{i,j=1}{\overset{m}{\Sigma }}{(f_{\mathrm{ri}}-f_{\mathrm{rj}})}^2{W}_{w,\mathrm{ij}}-\alpha \underset{i,j=1}{\overset{m}{\Sigma }}{(f_{\mathrm{ri}}-f_{\mathrm{rj}})}^2(W_{b,\mathrm{ij}}+W_{w,\mathrm{ij}})$

$=\underset{i,j=1}{\overset{m}{\Sigma }}{(f_{\mathrm{ri}}-f_{\mathrm{rj}})}^2{W}_{w,\mathrm{ij}}-\alpha \underset{i,j=1}{\overset{m}{\Sigma }}{(f_{\mathrm{ri}}-f_{\mathrm{rj}})}^2{W}_{\mathrm{ij}}$

$=\underset{i,j=1}{\overset{m}{\Sigma }}{(f_{\mathrm{ri}}-f_{\mathrm{rj}})}^2(W_{\mathrm{wij}}-\alpha W_{\mathrm{ij}})$

$=\underset{i,j=1}{\overset{m}{\Sigma }}{(f_{\mathrm{ri}}-f_{\mathrm{rj}})}^2{A}_{\mathrm{ij}}---\left(6\right)$

$=\underset{i,j=1}{\overset{m}{\Sigma }}(2f_{\mathrm{ri}}^2{A}_{\mathrm{ij}}-2f_{\mathrm{ri}}{f}_{\mathrm{rj}}{A}_{\mathrm{ij}})$

$=2f_r^{T}D{f}_r-2f_r^T{\mathrm{Af}}_r$

$=2f_r^{T}L{f}_r$

$=2{{\tilde{f}}_r}^{T}L\tilde{f}$

其中，A＝W_w-αW，D为对角矩阵且L为拉普拉斯矩阵且L＝D-A， ${\tilde{f}}_{\mathrm{ri}}=f_{\mathrm{ri}}-{\mu }_r,$

因为$\mathrm{Var}\left(f_r\right)=\underset{i=1}{\overset{m}{\Sigma }}{(f_{\mathrm{ri}}-{\mu }_r)}^2{D}_{\mathrm{ii}}$和${\mu }_r=\frac{\underset{i=1}{\overset{m}{\Sigma }}{f}_{\mathrm{ri}}{D}_{\mathrm{ii}}}{\underset{i=1}{\overset{m}{\Sigma }}{D}_{\mathrm{ii}}}=\frac{f_r^{T}D1}{1^{T}D1},$

故$\mathrm{Var}\left(f_r\right)=\underset{i=1}{\overset{m}{\Sigma }}{\tilde{f}}_{\mathrm{ri}}^2{D}_{\mathrm{ii}}={{\tilde{f}}_r}^{T}D{\tilde{f}}_r$

因计算各特征性能时，式（4）分子项，即式（6）都有常数2，故可省去， 即得到步骤三中的式（3）。

本发明的优点是：本发明提供一种无监督的特征选择准则，通过引入局部 内结构信息和局部间结构信息，通过最小局部内结构信息来保持各类数据潜在 的流行结构，通过最大局部间结构信息来释放类之间的信息，从而选择出更具 表示能力的特征子集。

【附图说明】

图1是本发明一种最小最大局部结构信息的特征选择方法的应用示意图；

图2是本发明一种最小最大局部结构信息的特征选择方法得到的分类性能 于COIL20数据集的示意图；

图3-a到图3-g是本发明一种最小最大局部结构信息的特征选择方法聚类 性能于PIE数据集的示意图；其中：图3-a是本发明于PIE数据集10类的示意 图；图3-b是本发明于PIE数据集20类的示意图；图3-c是本发明于PIE数据 集30类的示意图；图3-d是本发明于PIE数据集40类的示意图；图3-e是本 发明于PIE数据集50类的示意图；图3-f是本发明于PIE数据集60类的示意 图；图3-g是本发明于PIE数据集68类的示意图。

【具体实施方式】

实施例一

参阅图1和图2，在真实的COIL20数据集上，利用本发明一种最小最大局 部结构信息的特征选择方法进行特征选择获得相应的特征子集，然后再进行分 类任务；本发明依次包括以下步骤：

A)构建一个全局图G和对应的权矩阵W，

$W_{\mathrm{ij}}=\exp (-\frac{{\left|\right|x_i-x_j\left|\right|}^2}{{2t}^2})---\left(1\right)$

其中，x_i和x_j为样本点，t为常量；

B)根据A)步骤中的全局图G和权矩阵W，构建一个近邻图G_w和对应的权矩阵 W_w，

其中，N(x_i)和N(x_j)分别表示样本点x_i和x_j的k个近邻子集；

C)根据B)步骤中计算得到的权矩阵W_w，计算权矩阵A＝W_w-αW，对角矩阵D 和拉普拉斯矩阵L＝D-A，其中0≤α≤1；

D)计算各个特征的最小最大局部结构信息的拉普拉斯指标MMLS_r

${\mathrm{MMLS}}_r=\frac{{{\tilde{f}}_r}^{T}L{\tilde{f}}_r}{{{\tilde{f}}_r}^{T}D{\tilde{f}}_r}---\left(3\right);$

E)根据D)步骤中获得的拉普拉斯指标MMLS_r大小，依次选出d个最小拉普拉斯 指标MMLS_r对应的特征，构成特征子集。

所述D)步骤中，f_r＝[X_r1，Λ,X_rm]^T是由数据集矩阵 的第r个特征构成的向量，是第r个特征的数 学期望，所述D)步骤中提出的最小最大信息准则MMLS_r，

为${\mathrm{MMLS}}_r=\frac{(1-\alpha )\underset{i,j=1}{\overset{m}{\Sigma }}{(f_{\mathrm{ri}}-f_{\mathrm{rj}})}^2{W}_{w,\mathrm{ij}}-\alpha \underset{i,j=1}{\overset{m}{\Sigma }}{(f_{\mathrm{ri}}-f_{\mathrm{rj}})}^2{W}_{b,\mathrm{ij}}}{\mathrm{Var}\left(f_r\right)}---\left(4\right),$

所述D)步骤中Var(f_r)是第r个特征的方差，W_w和W_b是权矩阵，所述0≤α≤1，

且

所述D)步骤中提出的最小最大信息准则MMLS_r，包括如下过程：因为 W_w+W_b＝W，故

$(1-\alpha )\underset{i,j=1}{\overset{m}{\Sigma }}{(f_{\mathrm{ri}}-f_{\mathrm{rj}})}^2{W}_{w,\mathrm{ij}}-\alpha \underset{i,j=1}{\overset{m}{\Sigma }}{(f_{\mathrm{ri}}-f_{\mathrm{rj}})}^2{W}_{b,\mathrm{ij}}$

$=\underset{i,j=1}{\overset{m}{\Sigma }}{(f_{\mathrm{ri}}-f_{\mathrm{rj}})}^2{W}_{w,\mathrm{ij}}-\alpha \underset{i,j=1}{\overset{m}{\Sigma }}{(f_{\mathrm{ri}}-f_{\mathrm{rj}})}^2(W_{b,\mathrm{ij}}+W_{w,\mathrm{ij}})$

$=\underset{i,j=1}{\overset{m}{\Sigma }}{(f_{\mathrm{ri}}-f_{\mathrm{rj}})}^2{W}_{w,\mathrm{ij}}-\alpha \underset{i,j=1}{\overset{m}{\Sigma }}{(f_{\mathrm{ri}}-f_{\mathrm{rj}})}^2{W}_{\mathrm{ij}}$

$=\underset{i,j=1}{\overset{m}{\Sigma }}{(f_{\mathrm{ri}}-f_{\mathrm{rj}})}^2(W_{\mathrm{wij}}-\alpha W_{\mathrm{ij}})$

$=\underset{i,j=1}{\overset{m}{\Sigma }}{(f_{\mathrm{ri}}-f_{\mathrm{rj}})}^2{A}_{\mathrm{ij}}---\left(6\right)$

$=\underset{i,j=1}{\overset{m}{\Sigma }}(2f_{\mathrm{ri}}^2{A}_{\mathrm{ij}}-2f_{\mathrm{ri}}{f}_{\mathrm{rj}}{A}_{\mathrm{ij}})$

$=2f_r^{T}D{f}_r-2f_r^T{\mathrm{Af}}_r$

$=2f_r^{T}L{f}_r$

$=2{{\tilde{f}}_r}^{T}L\tilde{f}$

其中，A＝W_w-αW，D为对角矩阵且L为拉普拉斯矩阵且 L＝D-A，${\tilde{f}}_{\mathrm{ri}}=f_{\mathrm{ri}}-{\mu }_r,$

因为$\mathrm{Var}\left(f_r\right)=\underset{i=1}{\overset{m}{\Sigma }}{(f_{\mathrm{ri}}-{\mu }_r)}^2{D}_{\mathrm{ii}}$和${\mu }_r=\frac{\underset{i=1}{\overset{m}{\Sigma }}{f}_{\mathrm{ri}}{D}_{\mathrm{ii}}}{\underset{i=1}{\overset{m}{\Sigma }}{D}_{\mathrm{ii}}}=\frac{f_r^{T}D1}{1^{T}D1},$故

$\mathrm{Var}\left(f_r\right)=\underset{i=1}{\overset{m}{\Sigma }}{\tilde{f}}_{\mathrm{ri}}^2{D}_{\mathrm{ii}}={{\tilde{f}}_r}^{T}D{\tilde{f}}_r---\left(7\right)$

因计算各特征性能时，式（4）分子项，即式（6）都有常数2，故可省去， 即得到步骤三中的式（3）。

如图2所示（MMLS对应本发明方法），由于本发明同时引入了局部内结构信 息和局部间结构信息，通过最小局部内结构信息来保持各类数据潜在的流行结 构，通过最大局部间结构信息来释放类之间的信息，使得最近邻分类器1-NN在 特征子集上获得好的分类性能。

实施例二

参阅图1和图3-a～3-g，在真实的PIE数据集上，利用本发明进行特征选 择获得相应的特征子集，然后再进行聚类任务，本发明依次包括如下步骤：

A)构建一个全局图G和对应的权矩阵W，

$W_{\mathrm{ij}}=\exp (-\frac{{\left|\right|x_i-x_j\left|\right|}^2}{{2t}^2})---\left(1\right)$

其中，x_i和x_j为样本点，t为常量；

B)根据A)步骤中的全局图G和权矩阵W，构建一个近邻图G_w和对应的权矩阵 W_w，

其中，N(x_i)和N(x_j)分别表示样本点x_i和x_j的k个近邻子集；

C)根据B)步骤中计算得到的权矩阵W_w，计算权矩阵A＝W_w-αW，对角矩阵D 和拉普拉斯矩阵L＝D-A，其中0≤α≤1；

D)计算各个特征的最小最大局部结构信息的拉普拉斯指标MMLS_r

${\mathrm{MMLS}}_r=\frac{{{\tilde{f}}_r}^{T}L{\tilde{f}}_r}{{{\tilde{f}}_r}^{T}D{\tilde{f}}_r}---\left(3\right);$

E)根据D)步骤中获得的拉普拉斯指标MMLS_r大小，依次选出d个最小拉普拉斯 指标MMLS_r对应的特征，构成特征子集。

所述D)步骤中，f_r＝[X_r1，Λ,X_rm]^T是由数据集矩阵的 第r个特征构成的向量，是第r个特征的数学期望，所述D)步 骤中提出的最小最大信息准则MMLS_r，

为${\mathrm{MMLS}}_r=\frac{(1-\alpha )\underset{i,j=1}{\overset{m}{\Sigma }}{(f_{\mathrm{ri}}-f_{\mathrm{rj}})}^2{W}_{w,\mathrm{ij}}-\alpha \underset{i,j=1}{\overset{m}{\Sigma }}{(f_{\mathrm{ri}}-f_{\mathrm{rj}})}^2{W}_{b,\mathrm{ij}}}{\mathrm{Var}\left(f_r\right)}---\left(4\right),$

所述D)步骤中Var(f_r)是第r个特征的方差，W_w和w_b是权矩阵，所述0≤α≤1，

且

所述D)步骤中提出的最小最大信息准则MMLS_r，包括如下过程：

$(1-\alpha )\underset{i,j=1}{\overset{m}{\Sigma }}{(f_{\mathrm{ri}}-f_{\mathrm{rj}})}^2{W}_{w,\mathrm{ij}}-\alpha \underset{i,j=1}{\overset{m}{\Sigma }}{(f_{\mathrm{ri}}-f_{\mathrm{rj}})}^2{W}_{b,\mathrm{ij}}$

$=\underset{i,j=1}{\overset{m}{\Sigma }}{(f_{\mathrm{ri}}-f_{\mathrm{rj}})}^2{W}_{w,\mathrm{ij}}-\alpha \underset{i,j=1}{\overset{m}{\Sigma }}{(f_{\mathrm{ri}}-f_{\mathrm{rj}})}^2(W_{b,\mathrm{ij}}+W_{w,\mathrm{ij}})$

$=\underset{i,j=1}{\overset{m}{\Sigma }}{(f_{\mathrm{ri}}-f_{\mathrm{rj}})}^2{W}_{w,\mathrm{ij}}-\alpha \underset{i,j=1}{\overset{m}{\Sigma }}{(f_{\mathrm{ri}}-f_{\mathrm{rj}})}^2{W}_{\mathrm{ij}}$

$=\underset{i,j=1}{\overset{m}{\Sigma }}{(f_{\mathrm{ri}}-f_{\mathrm{rj}})}^2(W_{\mathrm{wij}}-\alpha W_{\mathrm{ij}})$

因为W_w+W_b＝W，故$=\underset{i,j=1}{\overset{m}{\Sigma }}{(f_{\mathrm{ri}}-f_{\mathrm{rj}})}^2{A}_{\mathrm{ij}}---\left(6\right)$

$=\underset{i,j=1}{\overset{m}{\Sigma }}(2f_{\mathrm{ri}}^2{A}_{\mathrm{ij}}-2f_{\mathrm{ri}}{f}_{\mathrm{rj}}{A}_{\mathrm{ij}})$

$=2f_r^{T}D{f}_r-2f_r^T{\mathrm{Af}}_r$

$=2f_r^{T}L{f}_r$

$=2{{\tilde{f}}_r}^{T}L\tilde{f}$

其中，A＝W_w-αW，D为对角矩阵且L为拉普拉斯矩阵且L＝D-A， ${\tilde{f}}_{\mathrm{ri}}=f_{\mathrm{ri}}-{\mu }_r,$因为$\mathrm{Var}\left(f_r\right)=\underset{i=1}{\overset{m}{\Sigma }}{(f_{\mathrm{ri}}-{\mu }_r)}^2{D}_{\mathrm{ii}}$和${\mu }_r=\frac{\underset{i=1}{\overset{m}{\Sigma }}{f}_{\mathrm{ri}}{D}_{\mathrm{ii}}}{\underset{i=1}{\overset{m}{\Sigma }}{D}_{\mathrm{ii}}}=\frac{f_r^{T}D1}{1^{T}D1},$故

$\mathrm{Var}\left(f_r\right)=\underset{i=1}{\overset{m}{\Sigma }}{\tilde{f}}_{\mathrm{ri}}^2\mathrm{Dii}={\tilde{f}}_r^{T}D{\tilde{f}}_r---\left(7\right)$

因计算各特征性能时，式（4）分子项，即式（6）都有常数2，故可省去， 即得到步骤三中的式（3）。

如图3所示（MMLS对应本发明方法），同时引入了局部内结构信息和局部间 结构信息，通过最小局部内结构信息来保持各类数据潜在的流行结构，通过最 大局部间结构信息来释放类之间的信息，使得K-Means聚类方法在特征子集上 获得好的聚类性能。

上述实施例是对本发明的说明，不是对本发明的限定，任何对本发明简单 变换后的方案均属于本发明的保护范围。