520· 智能系统学报 第12卷 根据数据是否带有标记，基于谱图理论的特征 阵用到类标记信息，那么对于给定的图G,其相似性 选择可分为有监督特征选择和无监督特征选 矩阵S为 择8-2)。无监督特征选择算法在构造相似性矩阵时 1 不考虑类信息，通常对给出的样本值采用核函数构 S,= :=y=k 造相似性矩阵。有监督特征选择算法将类信息引 0,其他 入相似性矩阵中，常根据类别个数来构造对应的相 式中n为类别为k的样本个数。 似性矩阵。利用谱图理论进行特征选择的主要思 令G为一无向有权图，则邻接矩阵W,=S(1≤ 想是对邻接图Laplacian矩阵进行谱分解，其特征向 i,j≤m),且W为对称矩阵。令度矩阵D为 量反映了样本的类属关系[。基于该思想，Zhao 等]设计了一个谱特征选择框架，框架根据相似性 Wi,j=i D= (1) 矩阵是否考虑类标记信息分别应用于有监督和无 0, j≠i 监督算法，而选择特征子集过程与具体学习器无 由式(1)可以看出度矩阵D是一个对角矩阵， 关，利用特征对样本分布的影响对特征进行排序。 对角线上的每个元素是邻接矩阵W每一行或每一 He等[uo]结合谱图理论和特征的局部保持能力提出 列的和。度矩阵可以解释为每个样本周围围绕的 了基于Laplacian得分的特征选择算法。Zhao[]和 其他样本的密集度，度矩阵中的元素越大，意味着 He[o]等基于谱图理论的特征选择均仅考虑每个单 有更多的样本靠近这个元素代表的样本。 独的特征按一定的可分性或统计判据进行排队以 由邻接矩阵和度矩阵得到相应的Laplacian矩 形成特征序列，并取靠前的特征子集进行学习。该 阵L和正则化的Laplacian矩阵 策略仅在各个特征间统计独立且类别正态分布时 较优，但特征间具有这种关系仅仅是极少数)，实 罗=D-S,3=D立LD 根据Laplacian矩阵的性质[)，给出下面定义： 际上特征空间中特征之间存在较为紧密的关联性。 定义1 Laplacian矩阵的最小特征值为0，对应 针对已有的基于谱图理论有监督特征选择算 特征向量为单位向量 法存在的上述问题，我们提出融合特征相关的谱特 let1=[11…1]I,L*1=0 征选择算法，在原始的整个特征空间中不仅考虑每 定义2对于任意一个n维向量x(数据集中的 一个特征的区分力，还考虑特征组的区分性能，迭 特征列)，都满足下式成立： 代地寻找对保持数据的局部结构比上一组特征更 强的特征组合。由此，提出了基于特征相关的谱特 eR=∑g,x-)产 征选择算法(spectral feature selection based on 定义3对于任意一个n维向量x(数据集中的 feature correlation,SPFC)。实验结果表明，该算法不 特征列)，任意一个实数，都有（特征列中的每个元 仅提高了特征选择的分类性能，而且获得了较高的 素减去一个相同的值得到的新特征列仍然保持结 分类精度下所需特征子集的数量较少。 果不变)： 1 谱特征选择算法 Vx ER",VtE R,(x-t*e)L(x-t*e)=xLx 谱图理论说明，Laplacian矩阵的特征值与特征 谱特征选择算法的主要理论是谱图理论，本文 向量包含着数据集的样本分布结构。谱特征选择 研究的算法是以Laplacian Score特征选择算法为基 在选取有强识别度的特征时，以特征取值的分布是 础，因此本节只介绍图Laplacian矩阵谱分析。 否与样本分布的结构保持一致作为特征选择的评 假设训练样本集X=[x1x2…x]T,类标 价标准。例如在图1中，每个图形（三角和星）表示 记y=[y:y2…yn]T。用标量F(1≤i≤n)记 一个样本，形状不同意味样本在同一特征上的取值 为第i个特征，向量表示有样本在第i个特征上 不同，各圆形分别为类1和类2的区域，即同一区域 的取值，第j个样本可以表示成x=(ff行，…)。 内的样本属于同一类别。在图1左侧中属于同一类 样本分布的结构由邻接图G(V,E)表示，其中V为 的样本在特征F上取值近似相同，而不属于同一类 图的点集，图的第j个结点，∈V对应于训练样本中 的样本在特征F上取值不同，因此特征F对类1 的第j个样本x,E为图的边集，边e∈E的权重W 和类2就有很好的识别能力，此时称特征F的取值 对应第j个样本和第i个样本的相似度S(1≤i,j≤ 分布与样本分布一致。在图1右侧中特征2的取 m)。本文研究有监督谱特征选择，即构建相似性矩 值分布则与样本分布不一致，F2对类1和类2不具根据数据是否带有标记，基于谱图理论的特征 选择 可 分 为 有 监 督 特 征 选 择 和 无 监 督 特 征 选 择［８－１２］ 。 无监督特征选择算法在构造相似性矩阵时 不考虑类信息，通常对给出的样本值采用核函数构 造相似性矩阵。 有监督特征选择算法将类信息引 入相似性矩阵中，常根据类别个数来构造对应的相 似性矩阵。 利用谱图理论进行特征选择的主要思 想是对邻接图 Ｌａｐｌａｃｉａｎ 矩阵进行谱分解，其特征向 量反映了样本的类属关系［１１］ 。 基于该思想，Ｚｈａｏ 等［８］设计了一个谱特征选择框架，框架根据相似性 矩阵是否考虑类标记信息分别应用于有监督和无 监督算法，而选择特征子集过程与具体学习器无 关，利用特征对样本分布的影响对特征进行排序。 Ｈｅ 等［１０］结合谱图理论和特征的局部保持能力提出 了基于 Ｌａｐｌａｃｉａｎ 得分的特征选择算法。 Ｚｈａｏ ［８］ 和 Ｈｅ ［１０］等基于谱图理论的特征选择均仅考虑每个单 独的特征按一定的可分性或统计判据进行排队以 形成特征序列，并取靠前的特征子集进行学习。 该 策略仅在各个特征间统计独立且类别正态分布时 较优，但特征间具有这种关系仅仅是极少数［１３］ ，实 际上特征空间中特征之间存在较为紧密的关联性。 针对已有的基于谱图理论有监督特征选择算 法存在的上述问题，我们提出融合特征相关的谱特 征选择算法，在原始的整个特征空间中不仅考虑每 一个特征的区分力，还考虑特征组的区分性能，迭 代地寻找对保持数据的局部结构比上一组特征更 强的特征组合。 由此，提出了基于特征相关的谱特 征 选 择 算 法 （ ｓｐｅｃｔｒａｌ ｆｅａｔｕｒｅ ｓｅｌｅｃｔｉｏｎ ｂａｓｅｄ ｏｎ ｆｅａｔｕｒｅ ｃｏｒｒｅｌａｔｉｏｎ，ＳＰＦＣ）。 实验结果表明，该算法不 仅提高了特征选择的分类性能，而且获得了较高的 分类精度下所需特征子集的数量较少。 １ 谱特征选择算法 谱特征选择算法的主要理论是谱图理论，本文 研究的算法是以 Ｌａｐｌａｃｉａｎ Ｓｃｏｒｅ 特征选择算法为基 础，因此本节只介绍图 Ｌａｐｌａｃｉａｎ 矩阵谱分析。 假设训练样本集 Ｘ ＝ ［ｘ１ ｘ２ … ｘｍ ］ Ｔ ，类标 记ｙ ＝ ［ｙ１ ｙ２ … ｙｍ ］ Ｔ 。 用标量 Ｆ ｉ （１≤ｉ≤ｎ） 记 为第 ｉ 个特征，向量 ｆ ｉ表示所有样本在第 ｉ 个特征上 的取值，第 ｊ 个样本可以表示成 ｘｊ ＝ （ｆ １ ｊ ，ｆ ２ ｊ ，…，ｆ ｎ ｊ ）。 样本分布的结构由邻接图 Ｇ（Ｖ，Ｅ）表示，其中 Ｖ 为 图的点集，图的第 ｊ 个结点 ｖｊ∈Ｖ 对应于训练样本中 的第 ｊ 个样本 ｘｊ，Ｅ 为图的边集，边 ｅｊｉ∈Ｅ 的权重 Ｗｉｊ 对应第 ｊ 个样本和第 ｉ 个样本的相似度 Ｓｉｊ（１≤ｉ，ｊ≤ ｍ）。 本文研究有监督谱特征选择，即构建相似性矩 阵用到类标记信息，那么对于给定的图 Ｇ，其相似性 矩阵 Ｓ 为 Ｓｉｊ ＝ １ ｎｋ ， ｙｉ ＝ ｙｊ ＝ ｋ ０， 其他 ì î í ï ï ïï 式中 ｎｋ 为类别为 ｋ 的样本个数。 令 Ｇ 为一无向有权图，则邻接矩阵 Ｗｉｊ ＝ Ｓｉｊ（１≤ ｉ，ｊ≤ｍ），且 Ｗ 为对称矩阵。 令度矩阵 Ｄ 为 Ｄ ＝ ∑ ｍ ｊ ＝ １ Ｗｊｉ， ｊ ＝ ｉ ０， ｊ ≠ ｉ ì î í ï ï ïï （１） 由式（１）可以看出度矩阵 Ｄ 是一个对角矩阵， 对角线上的每个元素是邻接矩阵 Ｗ 每一行或每一 列的和。 度矩阵可以解释为每个样本周围围绕的 其他样本的密集度，度矩阵中的元素越大，意味着 有更多的样本靠近这个元素代表的样本。 由邻接矩阵和度矩阵得到相应的 Ｌａｐｌａｃｉａｎ 矩 阵 Ｌ 和正则化的 Ｌａｐｌａｃｉａｎ 矩阵 Ｌ Ｌ ＝ Ｄ － Ｓ，Ｌ ＝ Ｄ － １ ２ ＬＤ － １ ２ 根据 Ｌａｐｌａｃｉａｎ 矩阵的性质［５］ ，给出下面定义： 定义 １ Ｌａｐｌａｃｉａｎ 矩阵的最小特征值为 ０，对应 特征向量为单位向量 ｌｅｔ Ｉ ＝ ［１ １ … １］ Ｔ ，Ｌ∗Ｉ ＝ ０ 定义 ２ 对于任意一个 ｎ 维向量 ｘ（数据集中的 特征列），都满足下式成立： ∀ｘ ∈ Ｒ ｎ ，ｘ ＴＬｘ ＝ １ ２ ∑ ｗｉｊ ｘｉ － ｘｊ ( ) ２ 定义 ３ 对于任意一个 ｎ 维向量 ｘ（数据集中的 特征列），任意一个实数，都有（特征列中的每个元 素减去一个相同的值得到的新特征列仍然保持结 果不变）： ∀ｘ ∈ Ｒ ｎ ，∀ｔ ∈ Ｒ，(ｘ － ｔ∗ｅ) Ｔ Ｌ（ｘ － ｔ∗ｅ） ＝ ｘ ＴＬｘ 谱图理论说明，Ｌａｐｌａｃｉａｎ 矩阵的特征值与特征 向量包含着数据集的样本分布结构。 谱特征选择 在选取有强识别度的特征时，以特征取值的分布是 否与样本分布的结构保持一致作为特征选择的评 价标准。 例如在图 １ 中，每个图形（三角和星）表示 一个样本，形状不同意味样本在同一特征上的取值 不同，各圆形分别为类 １ 和类 ２ 的区域，即同一区域 内的样本属于同一类别。 在图 １ 左侧中属于同一类 的样本在特征 Ｆ １ 上取值近似相同，而不属于同一类 的样本在特征 Ｆ １ 上取值不同，因此特征 Ｆ １ 对类 １ 和类 ２ 就有很好的识别能力，此时称特征 Ｆ １ 的取值 分布与样本分布一致。 在图 １ 右侧中特征 Ｆ ２ 的取 值分布则与样本分布不一致，Ｆ ２ 对类 １ 和类 ２ 不具 ·５２０· 智 能 系 统 学 报 第 １２ 卷