基于多粒度一致性邻域的多标记特征选择

doi:10.13232/j.cnki.jnju.2022.01.007

基于多粒度一致性邻域的多标记特征选择

卢舜¹^,², 林耀进^,¹^,², 吴镒潾¹^,², 包丰浩¹^,², 王晨曦¹^,²

1.闽南师范大学计算机学院, 漳州, 363000

2.福建省数据科学与智能应用高校重点实验室, 闽南师范大学, 漳州, 363000

Multi⁃label feature selection based on multi⁃granularity consistent neighborhood

Lu Shun¹^,², Lin Yaojin^,¹^,², Wu Yilin¹^,², Bao Fenghao¹^,², Wang Chenxi¹^,²

1.School of Computer Science，Minnan Normal University，Zhangzhou，363000，China

2.Key Laboratory of Data Science and Intelligence Application，Minnan Normal University，Zhangzhou，363000，China

通讯作者: E⁃mail：zzlinyaojin@163.com

收稿日期: 2021-06-16

基金资助:

国家自然科学基金. 62076116
福建省自然科学基金. 2021J02049. 2020J01811

Received: 2021-06-16

摘要

多标记学习广泛应用于图像分类、疾病诊断等领域，然而特征的高维性给多标记分类算法带来时间负担、过拟合和性能低等问题.基于多粒度邻域一致性设计相应的多标记特征选择算法：首先利用标记空间和特征空间邻域一致性来粒化所有样本，并基于多粒度邻域一致性观点定义新的多标记邻域信息熵和多标记邻域互信息；其次，基于邻域互信息构建一个评价候选特征质量的目标函数用于评价每个特征的重要性；最后通过多个指标验证了所提算法的有效性.

关键词： 多标记学习 ; 特征选择 ; 多粒度 ; 邻域一致性

Abstract

Multi⁃label learning is widely used in image classification，disease diagnosis and other fields. However，the high dimension of features brings time burden，over fitting and low performance to multi⁃label classification algorithms. In this paper，a multi⁃label feature selection algorithm is designed based on multi⁃granularity neighborhood consistency. Firstly，all samples are granulated by using the neighborhood consistency of label space and feature space. Moreover，new multi⁃label neighborhood information entropy and multi⁃label neighborhood mutual information are defined based on the view of multi⁃granularity neighborhood consistency. Secondly，an objective function is constructed to evaluate the quality of candidate features based on multi⁃label new neighborhood mutual information，which is used to evaluate the importance of each feature. The effectiveness of the proposed algorithm is verified by several measure criteria.

Keywords： multi⁃label learning ; feature selection ; multi⁃granularity ; neighborhood consistency

PDF (1622KB) 元数据多维度评价相关文章导出 EndNote| Ris| Bibtex 收藏本文

本文引用格式

卢舜, 林耀进, 吴镒潾, 包丰浩, 王晨曦. 基于多粒度一致性邻域的多标记特征选择. 南京大学学报（自然科学）[J], 2022, 58(1): 60-70 doi:10.13232/j.cnki.jnju.2022.01.007

Lu Shun, Lin Yaojin, Wu Yilin, Bao Fenghao, Wang Chenxi. Multi⁃label feature selection based on multi⁃granularity consistent neighborhood. Journal of nanjing University[J], 2022, 58(1): 60-70 doi:10.13232/j.cnki.jnju.2022.01.007

经典的监督学习中每个样本相对于多个候选标签只属于一个标签，然而在现实生活中，一个样本通常同时与多个标记相关联^［1］.如图1可能有“房子”“白云”“蓝天”“草地”等不同语义信息的标记；一份关于电影的介绍文档可能与“电影”“娱乐”“艺术”等多个主题相关；在疾病的诊断记录中，某位病人可能同时患有“糖尿病”“心脏病”“风湿性关节炎”等多种疾病.由于单标记不能很好地描述这些概念，因此多标记分类任务引起了研究学者的广泛关注.

图1

新窗口打开| 下载原图ZIP| 生成PPT

图1 多标记图片示例

Fig.1 A picture with multi⁃labels

多标记数据往往有数以千计的特征，且许多特征是冗余或无关的.特征的高维性给多标记分类算法带来时间负担、过拟合和性能低等问题^［2］.为了解决上述问题，许多多标记特征降维方法被提出，现有的研究工作主要可分为特征提取和特征选择两类.

多标记特征提取是将原有特征空间映射到一个新的特征空间.常见的多标记特征提取的方法有偏最小二乘法（Partial Least Squares，PLS）^［3］、线性判别分析（Linear Discriminant Analysis，LDA）^［4］、典型关联分析法（Canonical Correlation Analysis，CCA）^［5］.虽然特征提取的方法能够在很大程度上提高整个算法的分类性能，但会使新特征空间丧失原空间的物理意义，某种程度上破坏了原特征空间的结构.

多标记特征选择方法通过某些人为制定的准则从原始特征数据集中选择一组最优特征子集，这组特征子集没有改变原始的特征空间.多标记特征选择方法可分为三类：封装式、嵌入式和过滤式.封装式方法利用预测学习算法的精度来判断所选特征的好坏^［6］；嵌入式方法将特征选择过程与分类器的学习过程融合在一起^［7］；过滤式方法的特征选择过程独立于分类器^［8］，其优点是对分类结果的可解释性强.过滤方法的关键步骤是设计有效的指标来评价候选特征的质量，如依赖性分析^［9］、F统计量法^［10］和互信息^［11］.依赖性指计算特征与标记分布对样本划分的一致性；F统计量法是基于统计信息而被应用于分类数判决的有效性函数；互信息考虑变量之间的相关性，从而获得最优的特征子集，降低维数对分类精度的影响.

目前，利用邻域粗糙集进行多标记特征选择得到广泛关注^［12］，然而已有算法仅从标记空间或特征空间出发来定义样本的邻域，很少有研究将二者结合起来考虑.本文首先分别利用标记空间一致性和特征空间一致性对所有样本进行粒化，然后融合特征空间和标记空间中样本的粒度提出一致性邻域，并在此基础上定义新的多标记邻域信息熵和多标记邻域互信息.其次，构建一个目标函数来评价候选特征的重要性，并设计了相关算法.最后，使用多个评价指标在公开可用的数据集上，用多组实验验证了所提算法的有效性.

1 邻域熵和邻域互信息

本节主要介绍邻域熵与邻域互信息的有关基础知识.

给定样本集 $B = \{x_{1}, x_{2}, \dots, x_{n}\}, x \in R^{d}$ . $Δ$ 是 $B$ 上的距离函数，满足 $Δ (x_{i}, x_{j}) \geq 0$ . $p^{-}$ 范数距离定义为：

Δ_{p} (x_{i}, x_{j}) = {(\sum_{k = 1}^{N} {|x_{i k} - x_{j k}|}^{p})}^{\frac{1}{p}}

(1)

当 $δ \geq 0$ ，称点集 $δ (x) = \{x_{i}| Δ (x, x_{i}) \leq δ\}$ 是 $x$ 的邻域.直观地说，具有相似的特征值的不同样本应该被分作同一类.此外， $δ (x)$ 的大小取决于邻域 $δ$ 的大小.

定义1^［13］

给定样本集 $B = \{x_{1}, x_{2}, \dots, x_{n}\}$ ，属性集合 $f \subseteq F$ ，样本 $x_{i}$ 在属性 $f$ 下计算得到的邻域为 $δ_{f} (x_{i})$ .那么样本的不确定性定义为：

N H_{x_{i}}^{δ} (f) = - l g \frac{‖δ_{f} (x_{i})‖}{n}

(2)

于是，样本的平均不确定性定义为：

N H^{δ} (f) = - \frac{1}{n} \sum_{i = 1}^{n} l g \frac{‖δ_{f} (x_{i})‖}{n}

(3)

定义2^［13］

$\forall r$ ， $f \subseteq F$ 是刻画属性对象的两组特征，样本 $x_{i}$ 在 $f ⋃ r$ 的特征空间下的邻域被定义为 $δ_{f ⋃ r} (x_{i})$ ，则联合邻域熵被定义为：

N H^{δ} (r, f) = - \frac{1}{n} \sum_{i = 1}^{n} l g \frac{‖δ_{f ⋃ r} (x_{i})‖}{n}

(4)

当 $r$ 是输入变量， $c$ 是决策属性时，有 $δ_{r ⋃ c} (x_{i}) = δ_{r} (x_{i}) ⋂ δ_{c} (x_{i})$ ，此时有：

N H^{δ} (r, c) = - \frac{1}{n} \sum_{i = 1}^{n} l g \frac{‖δ_{r} (x_{i}) ⋂ δ_{c} (x_{i})‖}{n}

(5)

定义3^［13］

$\forall r$ ， $f \subseteq F$ 是刻画属性对象的两组特征，已知属性 $f$ 后属性 $r$ 的邻域条件熵定义为：

N H^{δ} (r| f) = - \frac{1}{n} \sum_{i = 1}^{n} l g \frac{‖δ_{r ⋃ f} (x_{i})‖}{‖δ_{f} (x_{i})‖}

(6)

定义4^［13］

$\forall r$ ， $f \subseteq F$ 是刻画属性对象的两组特征，则 $r$ 和 $f$ 的邻域互信息被定义为：

N M I^{δ} (r; f) = - \frac{1}{n} \sum_{i = 1}^{n} l g \frac{‖δ_{r} (x_{i})‖ \cdot ‖δ_{f} (x_{i})‖}{n ‖δ_{r ⋃ f} (x_{i})‖}

(7)

邻域信息熵和邻域互信息能够有效度量变量之间的相关性，因此广泛应用于特征选择.

2 基于多粒度一致性邻域的多标记特征选择

2.1　大间隔

从近邻分类学习算法的一致性角度出发，属于同一邻域内的样本 $x$ 具有相同的类标记.为了获取样本的邻域，可使用样本之间相应的间隔^［13］，其中样本的分类间隔为：

m (x) = Δ (x, N S (x)) - Δ (x, N T (x))

(8)

其中， $N T (x)$ 表示在样本空间中与样本最近的同类样本， $N S (x)$ 表示在样本空间中与样本最近的异类样本. $Δ (x, N T (x))$ 和 $Δ (x, N S (x))$ 分别表示样本点 $x$ 到 $N T (x)$ 和 $N S (x)$ 的距离.根据式（8）可知，所有的样本在邻域内具有相同的标记，若 $m (x) < 0$ ，则令 $m (x) = 0$ ，如图2所示.

图2

新窗口打开| 下载原图ZIP| 生成PPT

图2 x的间隔

Fig.2 The margin of x

2.2　基于多粒度一致性邻域的邻域互信息

在多标记学习中每个样本都与一组标记同时关联，样本对于标记有正相关或者负相关.因此，在特征空间和标记空间可分别获得目标样本的间隔.

定义5

给定多标记决策信息系统 $M D S = 〈B, F ⋃ L〉$ ， $B = \{x_{1}, x_{2}, \dots, x_{n}\}$ 表示样本集合， $F = \{f_{1}, f_{2}, \dots, f_{t}\}$ 表示样本特征集， $L = \{l_{1}, l_{2}, \dots, l_{m}\}$ 表示样本标记集合，则样本 $x$ 在标记 $l_{i}$ 下的分类间隔为：

m_{l_{i}} (x) = Δ_{l_{i}} (x, N S_{l_{i}} (x)) - Δ_{l_{i}} (x, N T_{l_{i}} (x)), \forall l_{i} \in L

(9)

根据式（9），样本在不同标记下的分类间隔大小不一致，因此需定义样本在不同标记的分类间隔.

定义6

给定多标记决策信息系统 $M D S = 〈B, F ⋃ L〉$ ， $B = \{x_{1}, x_{2}, \dots, x_{n}\}$ 表示样本集合， $F = \{f_{1}, f_{2}, \dots, f_{t}\}$ 表示样本特征集， $L = \{l_{1}, l_{2}, \dots, l_{m}\}$ 表示样本标记集合，由于样本 $x$ 在标记空间中属于不同的标记，样本 $x$ 在每个标记下有独自的分类间隔，则样本 $x$ 在标记空间 $L$ 下的邻域一致性分类间隔为：

m_{1} (x) = \frac{1}{|L|} \sum_{i = 1}^{L} m_{l_{i}} (x)

(10)

在式（10）的基础上可以获得每个样本在多标记下的邻域.

定义7

给定多标记决策信息系统 $M D S = 〈B, F ⋃ L〉$ ， $B = \{x_{1}, x_{2}, \dots, x_{n}\}$ 表示样本集合， $F = \{f_{1}, f_{2}, \dots, f_{t}\}$ 表示样本特征集， $L = \{l_{1}, l_{2}, \dots, l_{m}\}$ 表示样本标记集合，样本 $x$ 在标记空间 $L$ 下的一致性邻域为：

δ_{1} (x) = \{y| Δ (x, y) \leq m_{1} (x)\}

(11)

从分类一致性角度出发，在多标记学习中，样本的分类间隔不仅受到标记空间中不同标记的影响，在特征空间中也会受到其近邻的影响.

定义8

给定多标记决策信息系统 $M D S = 〈B, F ⋃ L〉$ ， $B = \{x_{1}, x_{2}, \dots, x_{n}\}$ 表示样本集合， $F = \{f_{1}, f_{2}, \dots, f_{t}\}$ 表示样本特征集， $L = \{l_{1}, l_{2}, \dots, l_{m}\}$ 表示样本标记集合，样本 $x$ 在特征空间 $F$ 中的邻域一致性分类间隔为：

m_{2} (x) = \frac{1}{|δ_{1} (x)|} \sum_{x' \in δ_{1} (x)} m_{1} (x')

(12)

上式表示在邻域 $δ_{1} (x)$ 中的所有样本分类间隔的均值.根据近邻分类原则，目标样本与其近邻的类标记应该一致.于是，通过分类间隔 $m_{2} (x)$ 可以在一定程度上剔除目标样本中邻域集合中的异常点，有效降低异常点带来的干扰.

定义9

δ_{2} (x) = \{y| Δ (x, y) \leq m_{2} (x)\}

(13)

根据定义7和定义9，可以给出样本 $x$ 在特征空间和标记空间下多粒度一致性邻域.

定义10

给定多标记决策信息系统 $M D S = 〈B, F ⋃ L〉$ ， $B = \{x_{1}, x_{2}, \dots, x_{n}\}$ 表示样本集合， $F = \{f_{1}, f_{2}, \dots, f_{t}\}$ 表示样本特征集， $L = \{l_{1}, l_{2}, \dots, l_{m}\}$ 表示样本标记集合，则样本 $x$ 在特征空间和标记空间下的多粒度一致性邻域 $δ' (x)$ 为：

\begin{array}{l} δ' (x) = \{y| Δ (x, y) \leq m' (x)\} \\ m' (x) = w_{1} m_{1} (x) + w_{2} m_{2} (x) \end{array}

(14)

其中， $w_{1}$ 和 $w_{2}$ 表示权重系数，本文均设置为0.5，即取 $m_{1} (x)$ 与 $m_{2} (x)$ 之和的均值.

通过定义10，可重构多粒度一致性邻域中的多标记邻域信息熵和多标记邻域互信息的概念.

定义11

给定多标记决策信息系统 $M D S = 〈B, F ⋃ L〉$ ， $B = \{x_{1}, x_{2}, \dots, x_{n}\}$ 表示样本集合， $F = \{f_{1}, f_{2}, \dots, f_{t}\}$ 表示样本特征集， $L = \{l_{1}, l_{2}, \dots, l_{m}\}$ 表示样本标记集合，在多粒度一致性邻域 $δ' (x)$ 下的不确定性定义为：

N H^{δ'} (f) = - \frac{1}{n} \sum_{i = 1}^{n} l g \frac{‖δ' (x_{i})‖}{n}

(15)

定义12

给定多标记决策信息系统 $M D S = 〈B, F ⋃ L〉$ ， $B = \{x_{1}, x_{2}, \dots, x_{n}\}$ 表示样本集合， $F = \{f_{1}, f_{2}, \dots, f_{t}\}$ 表示样本特征集， $L = \{l_{1}, l_{2}, \dots, l_{m}\}$ 表示样本标记集合， $\forall r$ ， $f \subseteq F$ 用来刻画论域的两组特征集合，样本 $x_{i}$ 在特征子集 $f ⋃ r$ 下的邻域记作 $δ_{f ⋃ r}^{'} (x_{i})$ .则相应的多标记邻域联合熵被定义为：

N H^{δ'} (r, f) = - \frac{1}{n} \sum_{i = 1}^{n} l g \frac{‖δ_{f ⋃ r}^{'} (x_{i})‖}{n}

(16)

定义13

N H^{δ'} (r| f) = - \frac{1}{n} \sum_{i = 1}^{n} l g \frac{‖δ_{f ⋃ r}^{'} (x_{i})‖}{‖δ_{f}^{'} (x_{i})‖}

(17)

定义14

N M I^{δ'} (r; f) = - \frac{1}{n} \sum_{i = 1}^{n} l g \frac{‖δ_{r}^{'} (x_{i})‖ \cdot ‖δ_{f}^{'} (x_{i})‖}{n ‖δ_{r ⋃ f}^{'} (x_{i})‖}

(18)

2.3　基于近似一致性邻域互信息的多标记特征选择

本节讨论如何利用一致性邻域互信息进行多标记特征选择.假设 $S$ 是已选特征子集， $L$ 是标记集合，则 $S$ 和 $L$ 之间的依赖关系可定义为：

N M I^{δ'} (S; L) = N H^{δ'} (S) + N H^{δ'} (L) - N H^{δ'} (S, L)

(19)

若加入候选特征 $f^{+}$ ，则式（19）转化为：

\begin{array}{l} N M I^{δ'} (f^{+}, S; L) = \\ N H^{δ'} (f^{+}, S) + N H^{δ'} (L) - N H^{δ'} (f^{+}, S, L) \end{array}

(20)

由式（19）和式（20）得到度量候选特征 $f^{+}$ 的优化目标函数如下：

\begin{array}{l} \underset{f^{+}}{a r g m a x} J (f^{+}, S, L) = N M I^{δ'} (f^{+}, S; L) - N M I^{δ'} (S; L) \\ 其 中, S \subset F (21) \end{array}

为了求解式（21），可先利用希勒不等式

\begin{array}{l} N H^{δ'} (f^{+}, S, L) \leq \\ \frac{1}{2} (N H^{δ'} (f^{+}, S) + N H^{δ'} (f^{+}, L)) + N H^{δ'} (S, L) \end{array}

对式（21）进行近似目标函数处理：

J (f^{+}, S, L) = N M I^{δ'} (f^{+}, S; L) - N M I^{δ'} (S; L)

(22)

对于式（22），借用文献［13］进行近似求解：

\begin{array}{l} \tilde{J} (f^{+}, S, L) \propto \frac{1}{2} (N H^{δ'} (f^{+}, S) - N H^{δ'} (f^{+}, L) + N H^{δ'} (S, L)) - N H^{δ'} (S) \propto N H^{δ'} (f^{+}, S) - N H^{δ'} (f^{+}, L) = \\ N M I^{δ'} (f^{+}; L) - N M I^{δ'} (f^{+}; S) + N H^{δ'} (H) - N H^{δ'} (L) \propto N M I^{δ'} (f^{+}; L) - N M I^{δ'} (f^{+}; S) \end{array}

(23)

式（23）在较大程度上衡量了每个特征的重要度，并且按照重要度进行降序排序.根据式（23）可设计如下的多标记特征选择算法.

本文算法包含三个主要步骤：首先进行多标记数据的转换，时间复杂度为 $O (|B| \cdot |L|)$ ；其次寻找每个样本的最近同类和最近异类，时间复杂度为 $O (|B| \cdot |B|)$ ；最后利用启发式搜索对特征进行排序，时间复杂度为 $O (|S| \cdot |F|)$ .因此本算法总的时间复杂度为 $O (|B| \cdot |L| + |B| \cdot |B| + |S| \cdot |F|)$ ，具体步骤如算法1所示.

算法1

基于多粒度一致性邻域的多标记特征选择算法

输入：候选特征集F；标记集合L

输出：最终的特征排序S

1.对于 $\forall x \in B$ ，计算 $δ' (x)$ ；

2.初始化 $S = \emptyset$ 且 $F = \{f_{1}, f_{2}, \dots, f_{N}\}$ ；

3.While $|S| < N$

4.寻找 $f \in F$ 使式（21）最大化；

5. $S \leftarrow S ⋃ \{f\}$ ；

6. $F = F \ S$ ；

7.endwhile

8.返回 $S$ .

3 实验设计与结果比较

为了有效评估提出的MFSNC（Multi⁃label Feature Selection Based on Multi⁃Granularity Neighborhood Consistency）算法，选择五个不同的算法进行对比：MLNB（Feature Selection for Multi⁃label Naive Bayes Classification）^［14］；MDDM（Multi⁃Label Dimensionality Reduction via Dependence Maximization）.根据投影方式的不同分为MDDMspc^［15］和MDDMproj^［15］；PMU（Feature Selection for Multi⁃label Classification Using Multivariate Mutual Information）^［16］和RF⁃ML（ReliefF for Multi⁃label Feature Selection）^［17］.在本文算法MFSNC中， $w_{1}$ ， $w_{2}$ 均设置为0.5.在MDDMspc中 $μ$ 设置为0.5.在PMU中，将连续的特征离散化，采用等宽策略分成2折.同时，用一种代表性的多标记分类算法ML⁃KNN评价特征选择的结果，并将最近邻域 $K$ 的值设置为10.最后，用标记集合预测和标记排序两类标准评价所选特征的好坏.在标记集合预测中选择Hamming Loss（HL）；在标记排序中选择Average Precision（AP），Ranking Loss（RL）和Coverage（CV）.这四个评价指标分别从不同的方面评价特征选择算法的性能，通常很少有算法在这些评价准则上均优于其他算法.

3.1　实验数据集

实验使用的数据集有Arts，Computer，Health，Recreation，Reference和Scene，这些数据集来自Mulan Library.前五个数据集在文本分类领域使用较多，Scene被应用于场景图像的分类和识别.表1列出了所用数据集的信息，六个数据集的所有特征都被标准化为 $[0,1]$ .

表1 实验使用的数据集的描述

Table 1 Descriptions of datasets used in experiments

数据集	样本数	特征数	类别数	训练样本数	测试样本数
Arts	5000	462	26	2000	3000
Computer	5000	681	33	2000	3000
Health	5000	612	32	2000	3000
Recreation	5000	606	22	2000	3000
Reference	5000	793	33	2000	3000
Scene	2407	294	6	1211	1196

新窗口打开| 下载CSV

3.2　评价指标

在多标记学习中，假设 $X \subset R^{d}$ 表示一个多标记数据集，且 $x \in X$ 表示 $d$ 维向量 $x = [x_{1}, x_{2}, \dots, x_{d}]$ ， $L = \{l_{1}, l_{2}, \dots, l_{m}\}$ 是一组标签.每个数据点与 $L$ 的子集相关联，并且该子集可被描述为 $m$ 维向量 $y = [y^{1}, y^{2}, \dots, y^{m}]$ .其中，当且仅当 $x$ 具有特定标签 $l_{j}$ 时， $y^{j} = 1$ ，否则为0.

实验评估中给定测试集 $T = \{(x_{i}, y_{i})| 1 \leq i \leq N\}$ ，其中 $y_{i} \subseteq L$ 是正确的标记子集， $Y_{i}^{'} \subseteq L$ 是由多标记分类器预测的标记向量.

Average Precision （AP）：

A P = \frac{1}{n} \sum_{i = 1}^{N} \frac{1}{|y_{i}|} \sum_{γ \in y_{i}} \frac{|\{γ' \in y_{i} : r_{i} (γ') \leq r_{i} (γ)\}|}{r_{i} (γ)}

(24)

其中， $r_{i} (γ)$ 表示由算法针对给定实例 $x_{i}$ 预测的标签 $l \in L$ 的排名.AP统计了在样本的类标记排序序列中，排在相关标记之前的标记依然是相关标记的情况.该指标越大则系统性能越好.

Ranking Loss（RL）：

\begin{array}{l} R L = \\ \frac{1}{N} \sum_{i = 1}^{N} \frac{1}{|y_{i}| |\bar{y_{i}}|} |\{(λ_{1}, λ_{2})| λ_{1} \leq λ_{2}, (λ_{1}, λ_{2}) \in y_{i} \times \bar{y_{i}}\}| \end{array}

(25)

其中， $\bar{y_{i}}$ 表示集合 $y_{i}$ 的补集.该评价指标用于考察在样本的类别标记排序序列中出现排序错误的情况，即无关标记在排序序列中位于相关标记之前.该指标取值越小则系统性能越优.

Hamming Loss（HL）：

H L = \frac{1}{N} \sum_{i = 1}^{N} \frac{|Y_{i}^{'} \oplus y_{i}|}{M}

(26)

其中， $\oplus$ 是异或运算，此指标评估实例⁃标记对被错误分类的次数.该指标取值越小则系统性能越优.

Coverage（CV）：

C V = \frac{1}{N} \sum_{i = 1}^{N} \underset{λ \in y_{i}}{m a x} r a n k (λ) - 1

(27)

其中， $r a n k (λ)$ 表示依照 $λ$ 可能性的排序.该评价指标用于考察在样本的类别标记排序序列中，覆盖所有相关标记所需的搜索深度情况.该指标取值越小则系统性能越优.

3.3　实验结果与分析

从三个方面分析所提算法的有效性.第一组实验：将MFSNC与MDDM⁃spc，MDDMproj，RF⁃ML和PMU算法进行比较，MFSNC是以特征排序作为特征选择的结果.此外，MDDMspc，MDDMproj和RF⁃ML也可以直接处理混合型数据.第二组实验：为了分析选择特征子集的分类精度，选择MDDMspc，MDDM⁃proj，PMU，MLNB，RF⁃ML与MFSNC进行比较.其中特征数量由MLNB确定，、因为MLNB直接得到特征子集.第三组实验：使用统计验证分析系统地比较算法之间的性能.所有实验使用的各个数据集的训练集与测试集均采用Mulan Library的设置.

为了验证MFSNC方法的有效性，通过一系列实验展示不同特征选择数量与分类性能的对应关系.图3到图8分别显示MFSNC算法在数据集Arts，Computer，Health，Recreation，Reference和Scene中不同评价指标下的分类情况，图中红色曲线代表本文所提算法，横坐标表示已选定特征的子集数量，纵坐标表示评价指标相对应的结果.可以明显看出，在所有数据集上，随着选择特征数量的增长，算法的评价结果也会发生相应的变化，并且其分类性能并不随已选特征的数量单调增加或减少.

图3

新窗口打开| 下载原图ZIP| 生成PPT

图3 Arts数据集上MFSNC与对比算法在四个评价指标上的实验结果

Fig.3 Four evaluation indexes of MFSNC and other algorithms on Arts dataset

图4

新窗口打开| 下载原图ZIP| 生成PPT

图4 Computer数据集上MFSNC与对比算法在四个评价指标上的实验结果

Fig.4 Four evaluation indexes of MFSNC and other algorithms on Computer dataset

图5

新窗口打开| 下载原图ZIP| 生成PPT

图5 Health数据集上MFSNC与对比算法在四个评价指标上的实验结果

Fig.5 Four evaluation indexes of MFSNC and other algorithms on Health dataset

图6

新窗口打开| 下载原图ZIP| 生成PPT

图6 Recreation数据集上MFSNC与对比算法在四个评价指标上的实验结果

Fig.6 Four evaluation indexes of MFSNC and other algorithms on Recreation dataset

图7

新窗口打开| 下载原图ZIP| 生成PPT

图7 Reference数据集上MFSNC与对比算法在四个评价指标上的实验结果

Fig.7 Four evaluation indexes of MFSNC and other algorithms on Reference dataset

图8

新窗口打开| 下载原图ZIP| 生成PPT

图8 Scene数据集上MFSNC与对比算法在四个评价指标上的实验结果

Fig.8 Four evaluation indexes of MFSNC and other algorithms on Scene dataset

为了更加详细凸显所提算法与其他算法的差异，以MLNB确定的特征数量作为最终特征子集个数进行比较.例如，Arts数据集中算法MLNB选定特征的数量是224，所以将224作为其他特征选择算法最终特征选择的数量.表2至表7分别显示在数据集Arts，Computer，Health，Recreation，Reference，Scene中，MLNB，MDDMspc，MDDMproj，PMU，RF⁃ML和MFSNC算法在四种评价指标下的分类性能，表中粗体字表示每个评价标准的最佳性能，“↓”表示越小越好，“↑”表示越大越好.

表2 Arts数据集上六种特征选择算法的比较评估

Table 2 Comparative evaluation of six feature selection methods on Arts dataset

算法	AP (↑)	HL (↓)	CV (↓)	RL (↓)
MLNB	0.4991	0.0612	5.5040	0.1542
MDDMspc	0.5072	0.0607	5.4740	0.1521
MDDMproj	0.4943	0.0612	5.5553	0.1555
PMU	0.4944	0.0615	5.4917	0.1527
RF⁃ML	0.4823	0.0627	5.4853	0.1540
MFSNC	0.5275	0.0597	5.2873	0.1452

新窗口打开| 下载CSV

表3 Computer数据集上六种特征选择算法的比较评估

Table 3 Comparative evaluation of six feature selection methods on Computer dataset

算法	AP (↑)	HL (↓)	CV (↓)	RL (↓)
MLNB	0.6391	0.0401	4.3740	0.0910
MDDMspc	0.6345	0.0406	4.3987	0.0916
MDDMproj	0.6284	0.0406	4.4437	0.0934
PMU	0.6276	0.0413	4.5013	0.0941
RF⁃ML	0.6285	0.0421	5.4853	0.0931
MFSNC	0.6332	0.0392	4.3313	0.0896

新窗口打开| 下载CSV

表4 Health数据集上六种特征选择算法的比较评估

Table 4 Comparative evaluation of six feature selection methods on Health dataset

算法	AP (↑)	HL (↓)	CV (↓)	RL (↓)
MLNB	0.6670	0.0442	3.5553	0.0681
MDDMspc	0.6585	0.0445	3.4973	0.0665
MDDMproj	0.6482	0.0458	3.6250	0.0699
PMU	0.6276	0.0443	3.4000	0.0636
RF⁃ML	0.6285	0.0465	3.4257	0.0643
MFSNC	0.7202	0.0398	3.1183	0.0567

新窗口打开| 下载CSV

表5 Recreation数据集上六种特征选择算法的比较评估

Table 5 Comparative evaluation of six feature selection methods on Recreation dataset

算法	AP (↑)	HL (↓)	CV (↓)	RL (↓)
MLNB	0.4613	0.0604	5.1547	0.1936
MDDMspc	0.4738	0.0620	4.8987	0.1826
MDDMproj	0.4665	0.0616	4.9763	0.1872
PMU	0.4357	0.0634	5.1480	0.1957
RF⁃ML	0.4465	0.0630	5.0860	0.1917
MFSNC	0.5252	0.0584	4.8267	0.1775

新窗口打开| 下载CSV

表6 Reference数据集上六种特征选择算法的比较评估

Table 6 Comparative evaluation of six feature selection methods on Reference dataset

算法	AP (↑)	HL (↓)	CV (↓)	RL (↓)
MLNB	0.6234	0.0296	3.4313	0.0889
MDDMspc	0.6126	0.0322	3.4390	0.0888
MDDMproj	0.6106	0.0311	3.4460	0.0889
PMU	0.6169	0.0306	3.3660	0.0868
RF⁃ML	0.6151	0.0345	3.3270	0.0856
MFSNC	0.6414	0.0286	3.2760	0.0839

新窗口打开| 下载CSV

表7 Scene数据集上六种特征选择算法的比较评估

Table 7 Comparative evaluation of six feature selection methods on Scene dataset

算法	AP (↑)	HL (↓)	CV (↓)	RL (↓)
MLNB	0.8351	0.0984	0.5936	0.0976
MDDMspc	0.8313	0.1028	0.6212	0.1036
MDDMproj	0.8383	0.1040	0.6003	0.0990
PMU	0.8277	0.1052	0.6355	0.1006
RF⁃ML	0.7933	0.1200	0.7575	0.1307
MFSNC	0.8431	0.0962	0.6028	0.0996

新窗口打开| 下载CSV

由表可见，MFSNC优于MDDMspc，MDDMproj，PMU和RF⁃ML.此外，绝大多数情况下MFSNC的性能优于MLNB.例如，Arts数据集下MLNB，MDDMspc，MDDMproj，PMU，RF⁃ML，MFSNC这些对比算法的特征子集的精度分别为0.4991，0.5072，0.4943，0.4944，0.4823，0.5275.

进一步探讨六种特征选择算法的性能是否有显著差异，采用Friedman^［18］检验和Bonferroni⁃Dunn^［19］检验.其中，Friedman统计被定义为：

\begin{array}{l} F_{F} = \frac{(N - 1) χ_{F}^{2}}{N (k - 1) - χ_{F}^{2}} \\ χ_{F}^{2} = \frac{12 N}{k (k + 1)} (\sum_{i = 1}^{k} R_{i}^{2} - \frac{k {(k + 1)}^{2}}{4}) \end{array}

(28)

其中， $k$ 表示算法的数目， $N$ 表示数据集的个数， $R_{i}$ 表示算法i在所有数据集下的平均排序.排在 $F_{F}$ 后的 $(k - 1)$ 和 $(k - 1) (N - 1)$ 是Fisher分布的自由度，如果在Friedman检验统计中否定了假设，则使用Bonferroni⁃Dunn检验进一步分析比较算法之间的相对性能.两种算法之间的差异性可通过Critical Difference（CD）进行比较：

C D_{α} = q_{α} \sqrt[]{\frac{k (k + 1)}{6 N}}

(29)

为了直观地展示MFSNC和其他比较算法性能的差异性，表8显示了在四个评价准则下不同算法的平均排序值.由表可见，本文所提算法在四个评价准则下的平均排序值均为第一.不同评价指标的 $F_{F}$ 的值如表9所示.此时，在显著性水平 $α = 0.10$ 下， $F (5,25)$ 的值为2.0922.从表9可以看出 $F_{F}$ 大于 $F (5,25)$ 的值，因此拒绝“所有算法的性能相同”这个假设.对于Bonferroni⁃Dunn测试，当 $α = 0.10$ 时，有 $q_{α} = 2.326$ ， $C D_{α} = 2.5124$ ，其中， $k$ 和 $N$ 均为6.

表8 在四个评价准则下不同算法的平均排序值

Tabel 8 Average ranks of different algorithms with four criteriaes

算法	AP	HL	CV	RL
MLNB	2.500	2.250	3.833	3.917
MDDMspc	3.000	3.583	3.333	3.333
MDDMproj	4.167	3.830	4.500	4.583
PMU	5.000	4.500	4.000	4.000
RF⁃ML	5.000	5.833	4.000	3.833
MFSNC	1.333	1.000	1.333	1.333

新窗口打开| 下载CSV

表9 不同指标下的Friedman统计(k=6, N=6)

Tabel 9 Friedman statistics (k=6,N=6) on different evaluation measures

评价指标	$F_{F}$	临界值 $α = 0.10$
AP	8.2353	2.0922
HL	2.6911
CV	2.8358
RL	2.9046

新窗口打开| 下载CSV

根据算法的平均排序值绘制图9，图中的坐标轴上画出了各对比算法的平均排序，最左边的平均排序最高.若两种算法在所有数据集上的平均排序的差高于临界值CD，则认为它们有显著性差异.用一根加粗的线段将性能没有显著差异的算法组连接起来.根据图9可以得出以下结论：

图9

新窗口打开| 下载原图ZIP| 生成PPT

图9 通过Bonferroni⁃Dunn测试比较MFSNC与其他算法的性能差异

Fig.9 Performance of MFSNC and other algorithms tested by Bonferroni⁃Dunn

（1）MFSNC在四个指标上与PMU，MDDMproj这两个算法都有显著性差异.

（2）MFSNC与RF⁃ML在AP，HL，CV这三个指标上有显著性差异.

4 结论

本文提出一种基于多粒度一致性邻域的多标记特征选择算法.首先，利用标记空间和特征空间的邻域一致性来粒化所有样本，并基于多粒度邻域一致性角度定义新的多标记邻域信息熵和多标记互信息.其次，在新定义的邻域信息熵及邻域互信息的基础上，构建一个评价候选特征质量的优化目标函数，该目标函数可以通过逼近多标签邻域互信息来解决.最后，在六个数据集上进行了大量的实验，通过四种不同的多标记评价指标表明，MFSNC优于其他对比算法.

参考文献

原文顺序

文献年度倒序

文中引用次数倒序

被引期刊影响因子

[1]

Boutell

M R

，Luo

J B

，Shen

X P

，et al.

Learning multi⁃label scene classification

Pattern Recognition，2004，37(9)：1757-1771.