基于双空间模糊邻域相似关系的多标记特征选择

引用本文

徐久成, 申凯丽. 基于双空间模糊邻域相似关系的多标记特征选择. 模式识别与人工智能, ,35(9): 805-815
XU Jiucheng, SHEN Kaili. Multi-label Feature Selection Based on Fuzzy Neighborhood Similarity Relations in Double Spaces. PATTERN RECOGNITION AND ARTIFICIAL INTELLIGENCE, ,35(9): 805-815. 复制到剪切板

Doi: 10.16451/j.cnki.issn1003-6059.202209004
Permissions

《模式识别与人工智能》编辑部所有

基于双空间模糊邻域相似关系的多标记特征选择

徐久成^1,², 申凯丽^1,²

1.河南师范大学计算机与信息工程学院新乡 453007

2.河南师范大学智慧商务与物联网技术河南工程实验室新乡 453007;

通信作者：

徐久成,博士,教授,主要研究方向为数据挖掘、粒计算、生物信息学.E-mail:xjc@htu.edu.cn.

作者简介: 申凯丽,硕士研究生,主要研究方向为粗糙集、生物信息学.E-mail:shenkaili@stu.htu.edu.cn.

收稿日期: 2022-07-18 接受日期: 2022-09-15

资助项目: 国家自然科学基金项目(No.61976082,62076089,62002103)资助

摘要

针对基于粗糙集的大部分多标记特征选择方法存在的忽略样本的模糊性和邻域关系、手动设置邻域半径、从单一的样本空间度量属性重要度等问题,文中利用模糊邻域粗糙集弥补经典粗糙集的不足,并在此基础上从特征空间和标记空间出发,提出基于双空间模糊邻域相似关系的多标记特征选择算法.首先,设计自适应邻域半径的计算方法,构建特征空间下样本的模糊邻域相似矩阵.再根据模糊邻域相似关系,得出特征空间下的样本相似度及标记空间下的样本相似度.然后,通过权重将特征空间和标记空间上的样本相似度进行融合,基于融合后的度量计算属性重要度.最后,运用前向贪心算法构建多标记特征选择算法.在12个多标记数据集上的对比实验验证文中算法的有效性.

关键词: 多标记特征选择; 模糊邻域相似关系; 模糊邻域粗糙集; 自适应邻域半径; 不确定性度量

中图分类号:TP 18

Multi-label Feature Selection Based on Fuzzy Neighborhood Similarity Relations in Double Spaces

XU Jiucheng^1,², SHEN Kaili^1,²

1.College of Computer and Information Engineering, Henan Nor-mal University, Xinxiang, 453007

2.Engineering Lab of Intelligence Business and Internet of Things of Henan Province, Henan Normal University, Xinxiang, 453007

Corresponding author：XU Jiucheng, Ph.D., professor. His research interests include data mining, granular computing and bioinformatics.

Author：SHEN Kaili, master student. Her research interests include data mining and bioinforma-tics.

Fund:Supported by National Natural Science Foundation of China(No.61976082,62076089,62002103)

Abstract

In most of the current rough set based multi-label feature selection algorithms, sample fuzziness and neighborhood relationship are ignored, the neighborhood radius needs setting manually, and attribute importance is measured in a single space. To overcome the defects of classical rough set algorithms, an algorithm of multi-label feature selection based on fuzzy neighborhood similarity in double spaces is proposed from the perspectives of feature space and label space. Firstly, an adaptive neighborhood radius calculation method is proposed and fuzzy neighborhood similarity matrix of samples in feature space is constructed. Secondly, similarities of sample in feature space and label space are obtained according to fuzzy neighborhood similarity relations. Then, the sample similarities in feature space and label space are fused by introducing weights and the attribute importance is calculated based on the fused measures. Finally, a multi-label feature selection algorithm is constructed via the forward greedy algorithm. The effectiveness of the proposed algorithm is confirmed on twelve multi-label datasets.

Key words: Key Words Multi-label Feature Selection; Fuzzy Neighborhood Similarity Relation; Fuzzy Neighborhood Rough Set; Adaptive Neighborhood Radius; Uncertainty Measurement

文章图片

在传统的分类学习中, 每个样本只包含一个类别标签, 即单标记学习.然而, 在实际应用中, 大部分样本同时包含多个类别标签, 即多标记学习^{[1, 2, 3]}.多标记学习与单标记学习一样遇到维数灾难的问题, 多标记数据中存在一些可能与分类任务不相关或冗余的特征, 导致诸如计算成本过高、过拟合、多标记分类学习算法的性能较低和分类学习过程较长等问题.特征选择作为一种常用的解决维数灾难问题的有效方法, 在多标记分类任务中占有重要位置^[4].

经典粗糙集^[5]是一种处理不确定数据的数学工具, 广泛应用于特征选择.为了扩展经典粗糙集的适用性, 学者们提出邻域粗糙集模型(Neighborhood Rough Sets, NRS)^[6]、模糊粗糙集模型(Fuzzy Rough Sets, FRS)^[7]和模糊邻域粗糙集模型(Fuzzy Neigh-borhood Rough Sets, FNRS)^{[8, 9]}.NRS可处理连续数值数据, 已成为多标记学习研究热点和处理特征选择的新方向.然而, NRS使用邻域相似类近似描述决策等价类, 无法表示模糊背景下实例的模糊性^{[10, 11]}.Lin等^[12]利用不同的模糊关系度量不同标签下样本之间的相似度, 提出基于FRS的多标记特征选择算法.赵晋欢等^[13]基于FRS, 构造模糊辨识矩阵, 对连续型数据进行属性约简.姚二亮等^[14]同样在FRS中基于模糊辨识关系, 分别从样本和标记角度计算多标记特征重要度.然而, FRS只使用模糊相似度划分决策类, 并未划分样本之间的相似度阈值.FNRS可构造一个鲁棒的距离函数, 使用模糊信息粒度描述实例决策, 降低数据分类的错误率^[15].FNRS在特征选择中具有一定的优势, 初步处理多标记数据集的同时具有邻域粗糙集和模糊粗糙集的优势, 既从邻域关系角度将多标记数据集上的特征进行分类, 又从模糊相似关系的角度计算每个样本之间特征值的相似度.虽然基于FNRS的特征选择方法已在单标记数据集上广泛应用, 然而少有针对多标记数据集的研究.因此, 开发基于FNRS的多标记特征选择方法是有必要的.

现有的基于模糊邻域粗糙集的多标记特征选择算法多从特征或标记的单一角度刻画特征对标记的重要程度, 未综合考虑特征空间和标记空间对样本相似度的影响, 并且大部分基于邻域关系的特征选择方法是借鉴专家的经验选取邻域参数值, 具有一定的主观性.因此, 本文基于模糊邻域粗糙集模型, 引入自适应邻域计算公式, 并在特征和标记空间上利用样本间特征值的相似性对标记值相似性的关联程度度量特征的重要度, 设计基于双空间模糊邻域相似关系的多标记特征选择算法(Multi-label Fea-ture Selection Based on Fuzzy Neighborhood Similarity Relations in Double Spaces, DSFNS).首先, 设计自适应邻域半径的计算方法, 构建特征空间下样本的模糊邻域相似矩阵.再根据模糊邻域相似关系, 得出特征空间下的样本相似度及标记空间下的样本相似度.然后, 通过权重将特征空间和标记空间上的样本相似度进行融合, 基于融合后的度量计算属性重要度.最后, 运用前向贪心算法构建多标记特征选择算法.在12个多标记数据集上的对比实验验证本文算法的有效性.

1 相关知识

1.1 模糊邻域粗糙集

定义1^[16] 设MFNDS=< U, A∪ D, δ > 为一个多标记模糊邻域决策系统, U={x₁, x₂, …, x_n}, B为论域U中的属性子集, B⊆A, 由B引出一个模糊二元关系R_B, 对于∀ x∈ U, y∈ U, R_B(x, y)称为模糊相似关系.R_B满足

1)自反性:R_B(x, x)=1, ∀ x∈ U;

2)对称性:R_B(x, y)=R_B(y, x), ∀ x∈ U, y∈ U.

定义2^[16] 给定一个多标记模糊邻域决策系统

MFNDS=< U, A∪ D, δ > ,

B⊆A, ∀ a∈ B, R_a为由特征a引出的模糊相似关系, 定义

R_B= $\cap_{a}^{\in}$ R_a,

对于∀ x∈ U, y∈ U, 模糊相似矩阵

[x]_a(y)=R_a(x, y),

则x在U上关于B的模糊相似矩阵定义为

[x]_B(y)= $\min_{a \in B}$ ([x]_a(y)).

定义3^[16] 设MFNDS=< U, A∪ D, δ > 为一个多标记模糊邻域决策系统, 对于∀ B⊆A, x∈ U, y∈ U, 参数化的模糊邻域信息粒构造如下:

δ _B(x)= ${[x]}_{B}^{δ}$ (y)= $\{\begin{array}{l} R_{B} (x, y), & R_{B} (x, y) \geq 1 - δ \\ 0, & R_{B} (x, y) < 1 - δ \end{array}$

其中, δ 表示模糊邻域半径, 0≤ δ ≤ 1.通过模糊相似关系R_B和邻域半径δ 可确定∀ x∈ U的模糊邻域粒.

1.2 自适应邻域半径

模糊邻域粗糙集上的邻域半径是根据样本之间的距离决定的.当选取邻域半径δ 过大时, 样本的邻域粒子变大、正域变小, 分类准确率下降; 当选取的邻域半径δ 过小时, 分类准确率虽得到提高, 但样本的邻域可能变成样本本身, 达不到特征选择的目的.目前, 为不同的数据集选取合适的邻域半径是提高特征选择性能的重要因素.在大多数模糊邻域粗糙集上, 邻域值是根据以往专家的经验人为给出, 主观性较强^[17], 在不同的数据集上选取的邻域半径值相同, 未结合每个数据集自身的分布特征进行选取.此外, 部分方法将邻域半径值按一定的步长进行全选, 计算每个邻域值求出的分类结果, 再从中选取最优邻域值, 这不仅浪费时间, 而且会增加很多不必要的工作量, 增加特征选择的复杂性.因此, 本文提出自适应邻域半径公式, 自适应调整每个数据集的不同分布结构.

定义4^[17] 设MFNDS=< U, A∪ D, δ > 为一个多标记模糊邻域决策系统, 对于∀ d_k∈ D,

B⊆A, B={a₁, a₂, …, a_m},

∀ a_j∈ B, 设标记D对论域U划分为

U/D={D₀, D₁},

决策类

D_r={x₁, x₂, …, x_p}, r=0, 1,

则决策类D_r中样本相对于标记d_k的特征集B的标准差为:

$s_{B}^{k}$ = $\frac{1}{m} \overset{m}{\sum_{j}} \sqrt[]{\frac{1}{p} \overset{p}{\sum_{i}} (a_{j} (x_{i}) - {\bar{a}}_{j} (D_{r}))^{2}}$ ,

其中 ${\bar{a}}_{j}$ (D_r)表示标记为r的样本在特征a_j下的平均值.

定义5^[17] 给定多标记模糊邻域决策系统

MFNDS=< U, A∪ D, δ > , B⊆A, B={a1_,a2_,…, am}

为特征集, D={d₁, d₂, …, d_t}为决策集, 对于∀ d_k∈ D, 样本相对于标记d_k的特征集标准差为 $s_{B}^{k}$ , 则多标记模糊邻域自适应半径为:

δ = $\frac{1}{t} \overset{t}{\sum_{k}} s_{B}^{k}$ .

2 多标记模糊邻域决策系统中的模糊邻域相似关系

多标记数据集上每列标记是二分值, 每列特征为数值型数据, 在计算某列特征下样本的相似度时, 应在一定范围内从样本间的特征差值上定义, 这个范围即为邻域半径, 模糊邻域相似关系即为样本的相似性.特征之间的相似性与标记之间的相似性具有一定的关联性, 从这一角度将模糊邻域相似关系应用在特征空间和标记空间下的样本相似度的度量中.

定义6 设MFNDS=< U, A∪ D, δ > 为一个多标记模糊邻域决策系统, ∀ a_j⊆A, x∈ U, y∈ U, 其参数化的模糊邻域信息粒构造如下:

$δ_{a_{j}}$ (x)= ${[x]}_{a_{j}}^{δ}$ (y)= $\{\begin{array}{l} R_{a_{j}} (x, y), & R_{a_{j}} (x, y) \geq 1 - δ \\ 0, & R_{a_{j}} (x, y) < 1 - δ \end{array}$

其中, δ 表示由定义5得出的模糊邻域自适应半径, 0≤ δ ≤ 1.通过模糊相似关系 $R_{a_{j}}$ 和邻域半径δ 可确定∀ x∈ U的模糊邻域粒.

定义7 设MFNDS=< U, A∪ D, δ > 为一个多标记模糊邻域决策系统, U为论域, ∀ x∈ U, y∈ U,

A={a₁, a₂, …, a_m}

为特征集, ∀ a_j∈ A决定的模糊邻域相似关系定义为

FN $S_{a_{j}}$ D(U)={(x, y) ${[x]}_{a_{j}}^{δ}$ y)≠ 0, (x, y)∈ U× U},

其中, FN $S_{a_{j}}$ D(U)表示特征a_j的相似样本对的集合, $|FN S_{a_{j}} D (U)|$ 表示特征a_j的相似样本对的个数.

例1 给定多标记决策表MLDT=< U, A∪ D> , 如表1所示,

U={x₁, x₂, x₃, x₄, x₅, x₆}, A={a_1,a_2,a₃}, D={d_1,d_2,d₃},

设模糊邻域半径δ =1.

表1 多标记决策表 Table 1 Multi-label decision table

根据

f(x_i)= $\frac{x_{i} - x_{\min}}{x_{\max} - x_{\min}}$

对表1中的数据进行归一化, 如表2所示.

表2 归一化数据 Table 2 Normalized data

特征a_k在样本x_i、x_j之间的模糊相似关系为^[16]:

$R_{a_{k}}$ (x_i, x_j)=1-|_ik-x_jk|

由定义6可得

${[x]}_{a_{1}}^{δ}$ (y)= $[\begin{array}{l} 1 & 0.52 & 0.82 & 0.97 & 0 & 0.68 \\ 0.52 & 1 & 0 & 0 & 0 & 0 \\ 0.82 & 0 & 1 & 0.85 & 0.66 & 0.86 \\ 0.97 & 0 & 0.85 & 1 & 0.51 & 0.72 \\ 0 & 0 & 0.66 & 0.51 & 1 & 0.80 \\ 0.68 & 0 & 0.86 & 0.72 & 0.80 & 1 \end{array}]$ ,

${[x]}_{a_{2}}^{δ}$ (y)= $[\begin{array}{l} 1 & 0 & 0.7 & 0.7 & 0 & 0.8 \\ 0 & 1 & 0 & 0 & 1 & 0 \\ 0.7 & 0 & 1 & 1 & 0 & 0.9 \\ 0.7 & 0 & 1 & 1 & 0 & 0.9 \\ 0 & 1 & 0 & 0 & 1 & 0 \\ 0.8 & 0 & 0.9 & 0.9 & 0 & 1 \end{array}]$ ,

${[x]}_{a_{3}}^{δ}$ (y)= $[\begin{array}{l} 1 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0.71 & 0 & 1 & 1 \\ 0 & 0.71 & 1 & 0 & 0.71 & 0.71 \\ 1 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0.71 & 0 & 1 & 1 \\ 0 & 1 & 0.71 & 0 & 1 & 1 \end{array}]$ .

由定义7可得

FN $S_{a_{1}}$ D(U)={(x₁, x₁), (x₁, x₂), (x₁, x₃), (x₁, x₄),

(x₁, x₆), (x₂, x₁), (x₂, x₂), (x₃, x₁),

(x₃, x₃), (x₃, x₄), (x₃, x₅), (x₃, x₆),

(x₄, x₁), (x₄, x₃), (x₄, x₄), (x₄, x₅),

(x₄, x₆), (x₅, x₃), (x₅, x₄), (x₅, x₅),

(x₅, x₆), (x₆, x₁), (x₆, x₃), (x₆, x₄),

(x₆, x₅), (x₆, x₆)},

FN $S_{a_{2}}$ D(U)={(x₁, x₁), (x₁, x₃), (x₁, x₄), (x₁, x₆),

(x₂, x₂), (x₂, x₅), (x₃, x₁), (x₃, x₃),

(x₃, x₄), (x₃, x₆), (x₄, x₁), (x₄, x₃),

(x₄, x₄), (x₄, x₆), (x₅, x₂), (x₅, x₅),

(x₆, x₁), (x₆, x₃), (x₆, x₄), (x₆, x₆)},

FN $S_{a_{3}}$ D(U)={(x₁, x₁), (x₁, x₄), (x₂, x₂), (x₂, x₃),

(x₂, x₅), (x₂, x₆), (x₃, x₂), (x₃, x₃),

(x₃, x₅), (x₃, x₆), (x₄, x₁), (x₄, x₄),

(x₅, x₂), (x₅, x₃), (x₅, x₅), (x₅, x₆),

(x₆, x₂), (x₆, x₃), (x₆, x₅), (x₆, x₆)}.

因此

$|FN S_{a_{1}} D (U)|$ =26, $|FN S_{a_{2}} D (U)|$ =20, $|FN S_{a_{3}} D (U)|$ 20.

定义8 给定多标记模糊邻域决策系统

MFNDS=< U, A∪ D, δ > ,

∀ a∈ B, B⊆A, 特征子集B的多标记模糊邻域相似关系定义为

FNS_BD(U)= $\cup_{a}^{\in}$ FNS_aD(U),

其中FNS_BD(U)表示特征子集B的相似样本对的集合.

性质1 设MFNDS=< U, A∪ D, δ > 为一个多标记模糊邻域决策系统, ∀ B₁⊆B₂⊆A, 则

FN $S_{B_{1}}$ D(U)⊆FN $S_{B_{2}}$ D(U).

证明根据定义8,

FN $S_{B_{1}}$ D(U)= $\cup_{a}^{\in}$ FNS_aD(U),
FN $S_{B_{2}}$ (U)= $\cup_{a}^{\in}$ NSa_D(U),

由B₁⊆B₂, 可得

$\cup_{a}^{\in}$ FNS_aD(U)⊆ $\cup_{a}^{\in}$ FNS_aD(U),

进而可证

FN $S_{B_{1}}$ D(U)⊆FN $S_{B_{2}}$ D(U).

由性质1可知,

$|FN S_{B_{1}} D (U)|$ ≤ $|FN S_{B_{2}} D (U)|$ .

上述内容从特征空间角度计算样本间的相似度.例如:例2中样本x₁、x₃相似, 样本x₁、x₄也相似, 但样本x₁、x₃间只有一个相同标记, 样本x₁、x₄间有两个相同的标记.由于FNS_aD(U)只关心样本之间是否相似, 并不关心相似的程度, 因此, 不能准确反映特征对标记的关联程度.

接下来, 在标记空间上计算样本的相似度, 进而刻画特征的重要度.

定义9 给定多标记模糊邻域决策系统

MFNDS=< U, A∪ D, δ > ,

∀ a∈ A, 特征a下相似样本的一致标记对个数为:

${|FN S_{a} D (U)|}^{D}$ = $\sum_{(} |SD (x, y)|$ ,

其中,

SD(x, y)={d_k|d_k(x)=d_k(y), ∀ d_k∈ D}

表示样本x、y之间一致的标记集合, $|SD (x, y)|$ 表示样本x和样本y之间一致标记的个数.

性质2 设MFNDS=< U, A∪ D, δ > 为一个多标记模糊邻域决策系统, ∀ B₁⊆B₂⊆A, 则

${|FN S_{B_{1}} D (U)|}^{D}$ ≤ ${|FN S_{B_{2}} D (U)|}^{D}$ .

证明已知∀ B₁⊆B₂⊆A, 由定义9可知

${|FN S_{B_{1}} D (U)|}^{D}$ = $\sum_{(} |SD (x, y)|$ ,

${|FN S_{B_{2}} D (U)|}^{D}$ = $\sum_{(} |SD (x, y)|$

由性质1可知

FN $S_{B_{1}}$ D(U)⊆FN $S_{B_{2}}$ D(U),

则

$\sum_{(} |SD (x, y)|$ ≤ $\sum_{(} |SD (x, y)|$ ,

因此, 可得

${|FN S_{B_{1}} D (U)|}^{D}$ ≤ ${|FN S_{B_{2}} D (U)|}^{D}$ .

例2 在例1中, ∀ a∈ A的相似对样本对应的相同标记对个数为:

$\left| SD({{x}_{1}}, {{x}_{1}}) \right|=3$, $\left| SD({{x}_{1}}, {{x}_{2}}) \right|=1$,

$\left| SD({{x}_{1}}, {{x}_{3}}) \right|=1$, $\left| SD({{x}_{1}}, {{x}_{4}}) \right|=2$,

$\left| SD({{x}_{1}}, {{x}_{5}}) \right|=2$, $\left| SD({{x}_{1}}, {{x}_{6}}) \right|=2$,

$\left| SD({{x}_{2}}, {{x}_{1}}) \right|=1$, $\left| SD({{x}_{2}}, {{x}_{2}}) \right|=3$,

$\left| SD({{x}_{2}}, {{x}_{3}}) \right|=1$, $\left| SD({{x}_{2}}, {{x}_{4}}) \right|=2$,

$\left| SD({{x}_{2}}, {{x}_{5}}) \right|=2$, $\left| SD({{x}_{2}}, {{x}_{6}}) \right|=0$,

$\left| SD({{x}_{3}}, {{x}_{1}}) \right|=1$, $\left| SD({{x}_{3}}, {{x}_{2}}) \right|=1$,

$\left| SD({{x}_{3}}, {{x}_{3}}) \right|=3$, $\left| SD({{x}_{3}}, {{x}_{4}}) \right|=0$,

$\left| SD({{x}_{3}}, {{x}_{5}}) \right|=0$, $\left| SD({{x}_{3}}, {{x}_{6}}) \right|=2$,

$\left| SD({{x}_{4}}, {{x}_{1}}) \right|=2$, $\left| SD({{x}_{4}}, {{x}_{2}}) \right|=2$,

$\left| SD({{x}_{4}}, {{x}_{3}}) \right|=0$, $\left| SD({{x}_{4}}, {{x}_{4}}) \right|=3$,

$\left| SD({{x}_{4}}, {{x}_{5}}) \right|=3$, $\left| SD({{x}_{4}}, {{x}_{6}}) \right|=1$,

$\left| SD({{x}_{5}}, {{x}_{1}}) \right|=2$, $\left| SD({{x}_{5}}, {{x}_{2}}) \right|=2$,

$\left| SD({{x}_{5}}, {{x}_{3}}) \right|=0$, $\left| SD({{x}_{5}}, {{x}_{4}}) \right|=3$,

$\left| SD({{x}_{5}}, {{x}_{5}}) \right|=3$, $\left| SD({{x}_{5}}, {{x}_{6}}) \right|=1$,

$\left| SD({{x}_{6}}, {{x}_{1}}) \right|=2$, $\left| SD({{x}_{6}}, {{x}_{2}}) \right|=0$,

$\left| SD({{x}_{6}}, {{x}_{3}}) \right|=2$, $\left| SD({{x}_{6}}, {{x}_{4}}) \right|=1$,

$\left| SD({{x}_{6}}, {{x}_{5}}) \right|=1$, $\left| SD({{x}_{6}}, {{x}_{6}}) \right|=3$．

由定义9可得,

${|FN S_{a_{1}} D (U)|}^{D}$ =44, ${|FN S_{a_{2}} D (U)|}^{D}$ =38, ${|FN S_{a_{3}} D (U)|}^{D}$ =34.

例1中特征a₂、a₃的相似样本对数都为20.因此, 从特征的模糊邻域相似关系角度上看, 特征a₂、a₃具有相同的重要性.然而, 由例2可知, 特征a₂、a₃对应的一致标记数分别为38和34.从标记的模糊邻域相似关系角度上看, 特征a₂比特征a₃重要.

综上所述, 对于多标记特征选择问题, 从特征和标记两个空间刻画特征的重要度优于单纯从特征空间刻画.

定义10 给定多标记模糊邻域决策系统

MFNDS=< U, A∪ D, δ > ,

对于B⊆A, 标记集D关于特征子集B的依赖度为:

γ _B(D)=ω $\frac{|FN S_{B} D (U)|}{|FN S_{A} D (U)|}$ +(1-ω ) $\frac{{|FN S_{B} D (U)|}^{D}}{{|FN S_{A} D (U)|}^{D}}$ ,

其中, ω 表示权重参数, 0≤ ω ≤ 1.

性质3 设MFNDS=< U, A∪ D, δ > 为一个多标记模糊邻域决策系统, 若∀ B₁⊆B₂⊆A, 则

$γ_{B_{1}}$ (D)≤ $γ_{B_{2}}$ (D).

证明由定义10可知:

$γ_{B_{1}}$ (D)=ω $\frac{|FN S_{B_{1}} D (U)|}{|FN S_{A} D (U)|}$ +(1-ω ) $\frac{{|FN S_{B_{1}} D (U)|}^{D}}{{|FN S_{A} D (U)|}^{D}}$

$γ_{B_{2}}$ (D)=ω $\frac{|FN S_{B_{2}} D (U)|}{|FN S_{A} D (U)|}$ +(1-ω ) $\frac{{|FN S_{B_{2}} D (U)|}^{D}}{{|FN S_{A} D (U)|}^{D}}$ .

由性质1与性质2可知,

$|FN S_{B_{1}} D (U)|$ ≤ $|FN S_{B_{2}} D (U)|$ , ${|FN S_{B_{1}} D (U)|}^{D} {|FN S_{B_{2}} D (U)|}^{D}$

所以 $γ_{B_{1}}$ (D)≤ $γ_{B_{2}}$ (D).

性质3表明, γ _B(D)关于特征集具有单调性, 即增加任何新的候选特征a∈ A-B到已选的特征子集B上时, 对应的依赖度

γ _B(D)≤ γ _B_∪_a(D).

因此, 可基于 $γ_{B}^{}$ (D)设计前向启发式多标记特征选择算法.

定义11 设MFNDS=< U, A∪ D, δ > 为一个多标记模糊邻域决策系统, ∀ B⊆A,

D={d₁, d₂, …, d_t},

∀ a∈ B, 特征a在B中相对于D的特征重要度为:

SIG(a, B, D)=γ _B_∪_a(D)-γ _B(D).

3 多标记特征选择算法

基于定义11给出的特征重要度, 运用前向贪心策略, 设计基于双空间模糊邻域相似关系的多标记特征选择算法(DSFNS), 具体步骤如下.

算法 DSFNS

输入 MFNDS=< U, A∪ D, δ >

输出最优特征子集R

1.初始化R=Ø ;

2.计算邻域半径δ ;

3.for ∀ a_j∈ A do

4. 计算FN $S_{a_{j}}$ D(U);

5.End for

6.for ∀ d_t∈ D, ∀ x∈ U, y∈ U do

7. 计算 $|SD (x, y)|$ ;

8.End for

9.for ∀ a_s∈ A-R do

10. 计算 $|FN S_{R ⋃ a_{s}} D (U)|$ , ${|FN S_{R ⋃ a_{s}} D (U)|}^{D}$ ,

$γ_{B ⋃ a_{s}}$ (D)和SIG(a_s, B, D);

11.End for

12.计算SIG(a_t, B, D)= $\max_{a_{s} \in A - R}$ (SIG(a_s, B, D));

13.if SIG(a_t, B, D)> 0 then

14. R=R∪ a_t, 执行step 9;

15.Else

16. 执行step 18;

17.End if

18.返回最优特征子集R;

19.End.

在算法中, 假设多标记模糊邻域决策系统包含n个样本、m维特征和t个标记, step 2的时间复杂度为O(nmt).step 3~step 5计算特征的相似样本个数的时间复杂度为O(n²m).step 6~step 8判断相似的样本在t个标记上是否一致的时间复杂度为O(n²t).step 9~step 18的时间复杂度为O(n²m).因此, 算法提出的依赖度选择最优特征子集的时间复杂度为O(n²max(m, t)).

4 实验及结果分析

4.1 实验环境

为了评估DSFNS的有效性, 本文在来自不同领域的12个多标记数据集(http://mulan.sourceforge.net/datasets.html和http://www.uco.es/kdis/mllresources)上进行实验.这些数据集的基本信息如表3所示,

LC(D)= $\frac{1}{n} \overset{n}{\sum_{i}} \overset{t}{\sum_{j}}$ [d_j(x_i)=+1],

表示标记的基数,

LD(D)= $\frac{1}{nt} \overset{n}{\sum_{i}} \overset{t}{\sum_{j}}$ [d_j(x_i)=+1],

表示标记的密度, [d_j(x_i)=+1]表示样本x_i中存在标签d_j.当[d_j(x_i)=+1]满足时, [· ]等价于1; 否则为0^[18].

表3 多标记数据集信息 Table 3 Information of multi-label datasets

本文实验均在Inter(R)Core(TM) i5-8500 CPU @3.00 GHz的处理器, 16.00 GB的内存, Windows10系统及MatlabR2019a的实验平台上进行.采用ML-KNN(Multi-label K-Nearest Neighbor)^[18]和MLFE(Multi-label Learning with Feature-Induced Labeling Information Enrichment)^[19]分类器验证DSFNS的分类性能, ML-KNN与MLFE中的平滑参数均设为1, 最近邻K值均设为10^[20].

此外, DSFNS的权重值ω 设为固定值0.5, 其它算法中权重的取值范围为[0, 1], 设定步长为0.1.通过实验选取各数据集上可使性能指标均为最优时的最佳权重值, 并与其它算法进行对比^[14], 而本文通过选取固定值0.5作为后续实验的权重值, 更能展现算法在随机选取权重值时的优越性.

实验中选取多标签分类中常用的7个评价指标, 包括:平均精度(Average Precision, AP)、覆盖率(Coverage, CV)、汉明损失(Hamming Loss, HL)、1-错误率(One Error, OE)、排序损失(Rank Loss, RL)、宏平均F1(Macro-Averaging F1, MacF1)和微平均F1(Micro-Averaging F1, MicF1)^[21].AP、MacF1、MicF1值越高, 分类性能越优; CV、OE、RL、HL值越低, 分类性能越优.

4.2 在ML-KNN分类器下的实验结果

实验选取如下6种相关的多标记特征选择算法:MDDM_p(Multilabel Dimensionality Reduction via Dependence Maximization with Uncorrelated Projection Constraint)^[21]、MDDM_f(Multilabel Dimensionality Re-duction via Dependence Maximization with Uncorrela-ted Feature Constraint)^[21]、PMU^[22]、RF-ML(ReliefF for Multi-label Feature Selection)^[23]、MLDFC(Multi-label Feature Selection Based on Label Distribution and Feature Complementarity)^[24]、MFSFN(Multi-label Feature Selection Algorithm Based on Fuzzy Neighbor-hood Rough Sets)^[25].在ML-KNN分类器上, 各算法

在12个数据集上的指标值对比如表4~表8所示, 表中黑体数字表示最优值, “ -” 表示数据缺失, 无相应的对比数据.

各算法的AP值对比如表4所示.在Plant、Virus、Gnegative、BBC、Guardian、Gpositive、Yeast、Medical数据集上, DSFNS的AP值均最高.在Birds、Scene、Business数据集上, DSFNS的AP值居第二, 分别仅次于MLDFC、MDDM_f和PMU.在Flags数据集上, DSF-NS的AP值比最优值0.835 7下降0.005 7.

表4 各算法在12个数据集上的AP值对比 Table 4 AP value comparison of different algorithms on 12 datasets

各算法的CV值对比如表5所示.除了Scene、Flags数据集以外, DSFNS在其它10个数据集上均最优.在Birds、Gnegative、BBC、Medical数据集上, DSFNS的CV值均显著低于其它算法, 超过0.1, 在Flags数据集上, DSFNS的CV值优于PMU和RF_ML, 在Scene数据集上, DSFNS的CV值仅次于MDDM_f.

表5 各算法在12个数据集上的CV值对比 Table 5 CV value comparison of different algorithms on 12 datasets

各算法的OE值对比如表6所示.DSFNS在超一半数据集上均具有显著的优势, 在Birds、Virus、BBC、Guardian、Medical数据集上低于部分对比算法, 超过0.1.在Scene、Business数据集上分别仅次于MDDM_f和PMU.

各算法的RL值对比如表7所示.DSFNS在Plant、Virus、Gnegative、BBC、Guardian、Gpositive数据集上表现较优; 在Business数据集上的RL值仅次于PMU, 与RF_ML相当.

表6 各算法在12个数据集上的OE值对比 Table 6 OE value comparison of different algorithms on 12 datasets

表7 各算法在12个数据集上的RL值对比 Table 7 RL value comparison of different algorithms on 12 datasets

各算法的HL值对比如表8所示.在Plant、Flags、Yeast、Scene、Business数据集上, DSFNS表现最优, 在BBC数据集上仅次于RF_ML, 在Birds数据集上比MLDFC仅高0.002 5, 在Guardian数据集上比RF_ML和MDDM_p仅高出0.002 8.

表8 各算法在12个数据集上的HL值对比 Table 8 HL value comparison of different algorithms on 12 datasets

综上所述, 在不同的评价指标中, DSFNS都能获得较高的指标值和排名, 在各评价指标中最优结果出现的频率最高, 在所有数据集上的扩展能力明显优于其它算法.因此, DSFNS具有显著的有效性.

4.3 在MLFE分类器下的实验结果

本节选取如下对比算法:PCT-CHI2(Pair-wise Comparison Transformation Method Combined with Chi-square Statistics)^[26]、CSFS(Convex Semi-super-vised Multi-label Feature Selection)^[27]、SFUS(Sub-Feature Uncovering with Sparsity)^[28]、文献[29]算法.在分类器MLFE下对比算法性能, 在Yeast、Flags、Scene数据集上进行实验.

各算法的指标值对比如表9~表14所示.DSFNS的AP、macroF1、microF1值均最高, CV、OE、RL值均最低, 总之, 在3个数据集上, DSFNS均取得较理想的分类结果.

表9 各算法在3个数据集上的AP值对比 Table 9 AP value comparison of different algorithms on 3 datasets

表10 各算法在3个数据集上的CV值对比 Table 10 CV value comparison of different algorithms on 3 datasets

表11 各算法在3个数据集上的OE值对比 Table 11 OE value comparison of different algorithms on 3 datasets

表12 各算法在3个数据集上的RL值对比 Table 12 RL value comparison of different algorithms on 3 datasets

表13 各算法在3个数据集上的MacF1值对比 Table 13 MacF1 value comparison of different algorithms on 3 datasets

表14 各算法在3个数据集上的MicF1值对比 Table 14 MicF1 value comparison of different algorithms on 3 datasets

5 结束语

为了提高多标记模糊邻域决策系统的分类性能, 本文提出基于双空间模糊邻域相似关系的多标记特征选择算法.在模糊邻域粗糙集框架下, 提出自适应邻域半径, 并通过模糊邻域相似矩阵计算样本间的模糊邻域相似关系, 将特征和标记两个空间上所得样本相似度融合成新的度量方法, 用于计算特征的重要度.本文还设计多标记特征选择算法.与以往的基于模糊邻域粗糙集的多标记特征选择算法不同, 本文运用特征和标记两个空间上样本相似度之间的影响程度度量特征的重要性, 全面刻画特征对标记的重要性.在12个多标记数据集上的实验结果表明本文算法的有效性.本文算法是在完备信息系统中进行特征选择, 在今后的工作中, 将设计针对不完备信息系统的多标记特征选择算法, 并将标记分布和标记增强的因素加入到今后的特征选择方法研究中.

参考文献

文献选项

[1]	HUANG S J, GAO W, ZHOU Z H. Fast Multi-instance Multi-label Learning. IEEE Transactions on Pattern Analysis and Machine Inte-lligence, 2019, 41(11): 2614-2627. [本文引用:1]
[2]	LIU B S, LIU X L, REN H, et al. Text Multi-label Learning Method Based on Label-Aware Attention and Semantic Dependency. Multimedia Tools and Applications, 2022, 81(5): 7219-7237. [本文引用:1]
[3]	张平照. 多标记学习特征空间和标记空间降维方法研究. 硕士学位论文. 马鞍山: 安徽工业大学, 2020. (ZHANG P Z. Research on Multi-label Learning via Feature Space and Label Space Dimension Reduction Method. Master Dissertation. Maanshan, China: Anhui University of Technology, 2020. ) [本文引用:1]
[4]	JIANG Z H, LIU K Y, YANG X B, et al. Accelerator for Supervised Neighborhood Based Attribute Reduction. International Journal of Approximate Reasoning, 2020, 119: 122-150. [本文引用:1]
[5]	PAWLAK Z. Rough Sets. International Journal of Computer and Information Sciences, 1982, 11(5): 341-356. [本文引用:1]
[6]	段洁, 胡清华, 张灵均, 等. 基于邻域粗糙集的多标记分类特征选择算法. 计算机研究与发展, 2015, 52(1): 56-65. (DUAN J, HU Q H, ZHANG L J, et al. Feature Selection for Multi-label Classification Based on Neighborhood Rough Sets. Journal Computer Research and Development, 2015, 52(1): 56-65. ) [本文引用:1]
[7]	李钰雯. 基于模糊粗糙集模型的特征选择方法研究. 博士学位论文. 厦门: 厦门大学, 2019. (LI Y W. Research on Feature Selection with Fuzzy Rough Sets. Ph. D. Dissertation. Xiamen, China: Xiamen University, 2019. ) [本文引用:1]
[8]	WANG C Z, SHAO M W, HE Q, et al. Feature Subset Selection Based on Fuzzy Neighborhood Rough Sets. Knowledge-Based Systems, 2016, 111: 173-179. [本文引用:1]
[9]	陈盼盼. 基于粗糙集扩展模型的属性约简算法研究. 硕士学位论文. 漳州: 闽南师范大学, 2020. (CHEN P P. Research on Attribute Reduction Algorithms Based on Extended Rough Set Model. Master Dissertation. Zhangzhou, China: Minnan Normal University, 2020. ) [本文引用:1]
[10]	SUN L, WANG L Y, DING W P, et al. Feature Selection Using Fuzzy Neighborhood Entropy-Based Uncertainty Measures for Fuzzy Neighborhood Multigranulation Rough Sets. IEEE Transactions on Fuzzy Systems, 2021, 29(1): 19-33. [本文引用:1]
[11]	SUN L, WANG L Y, QIAN Y H, et al. Feature Selection Using Lebesgue and Entropy Measures for Incomplete Neighborhood Decision Systems. Knowledge-Based Systems, 2019, 186. DOI: DOI:10.1016/j.knosys.2019.104942. [本文引用:1]
[12]	LIN Y J, LI Y W, WANG C X, et al. Attribute Reduction for Multi-label Learning with Fuzzy Rough Set. Knowledge-Based Systems, 2018, 152: 51-61. [本文引用:1]
[13]	赵晋欢, 王长忠. 基于模糊粗糙集的辨识矩阵属性约简方法. 渤海大学学报(自然科学版), 2019, 40(2): 146-151. (ZHAO J H, WANG C Z. Fuzzy Rough Attribute Reduction Method Based on Discernibility Matrix. Journal of Bohai University (Natural Science Edition), 2019, 40(2): 146-151. ) [本文引用:1]
[14]	姚二亮, 李德玉, 李艳红, 等. 基于双空间模糊辨识关系的多标记特征选择. 模式识别与人工智能, 2019, 32(8): 709-717. (YAO E L, LI D Y, LI Y H, et al. Multi-label Feature Selection Based on Fuzzy Discernibility Relations in Double Spaces. Pattern Recognition and Artificial Intelligence, 2019, 32(8): 709-717. ) [本文引用:2]
[15]	MA J, ATEF M, KHALIL A M, et al. Novel Models of Fuzzy Rough Coverings Based on Fuzzy α-Neighborhood and Its Application to Decision-Making. IEEE Access, 2020, 8: 224354-224364. [本文引用:1]
[16]	XU J C, WANG Y, MU H Y, et al. Feature Genes Selection Based on Fuzzy Neighborhood Conditional Entropy. Journal of Intelligent and Fuzzy Systems, 2019, 36(1): 117-126. [本文引用:4]
[17]	吕月姣. 面向多标记数据的邻域自适应粗糙集模型. 硕士学位论文. 太原: 山西大学, 2021. (LÜ Y J. Neighborhood Adaptive Rough Set Model for Multi-label Data. Master Dissertation. Taiyuan, China: Shanxi University, 2021. ) [本文引用:3]
[18]	ZHANG M L, ZHOU Z H. ML-KNN: A Lazy Learning Approach to Multi-label Learning. Pattern Recognition, 2007, 40(7): 2038-2048. [本文引用:2]
[19]	ZHANG Q W, ZHONG Y, ZHANG M L. Feature-Induced Labeling Information Enrichment for Multi-label Learning // Proc of the 32nd AAAI Conference on Artificial Intelligence. Palo Alto, USA: AAAI, 2018: 4446-4453. [本文引用:1]
[20]	HUANG R, JIANG W D, SUN G L. Manifold-Based Constraint Laplacian Score for Multi-label Feature Selection. Pattern Recognition Letters, 2018, 112: 346-352. [本文引用:1]
[21]	ZHANG Y, ZHOU Z H. Multilabel Dimensionality Reduction via Dependence Maximization. ACM Transactions on Knowledge Discovery from Data, 2010, 4(3). DOI: DOI:10.1145/1839490.1839495. [本文引用:3]
[22]	LEE J, KIM D W. Feature Selection for Multi-label Classification Using Multivariate Mutual Information. Pattern Recognition Le-tters, 2013, 34(3): 349-357. [本文引用:1]
[23]	SPOLAÔR N, CHERMAN E A, MONARD M C, et al. ReliefF for Multi-label Feature Selection // Proc of the Brazilian Conference on Intelligent Systems. Washington, USA: IEEE, 2013: 6-11. [本文引用:1]
[24]	QIAN W B, LONG X D, WANG Y L, et al. Multi-label Feature Selection Based on Label Distribution and Feature Complementarity. Applied Soft Computing, 2020. DOI: DOI:10.1016/j.asoc.2020.106167. [本文引用:1]
[25]	XU J C, SHEN K L, SUN L. Multi-label Feature Selection Based on Fuzzy Neighborhood Rough Sets. Complex and Intelligent Systems, 2022, 8: 2105-2129. [本文引用:1]
[26]	XU H T, XU L Y. Multi-label Feature Selection Algorithm based on Label Pairwise Ranking Comparison Transformation // Proc of the International Joint Conference on Neural Networks. Washington, USA: IEEE, 2017: 1210-1217. [本文引用:1]
[27]	CHANG X J, NIE F P, YANG Y, et al. A Convex Formulation for Semi-supervised Multi-label Feature Selection. Proceedings of the AAAI Conference on Artificial Intelligence, 2014, 28(1): 1171-1177. [本文引用:1]
[28]	MA Z G, NIE F P, YANG Y, et al. Web Image Annotation via Subspace-Sparsity Collaborated Feature Selection. IEEE Transactions on Multimedia, 2012, 14(4): 1021-1030. [本文引用:1]
[29]	LIM H, LEE J, KIM D W. Optimization Approach for Feature Selection in Multi-label Classification. Pattern Recognition Letters, 2017, 89: 25-30. [本文引用:1]

2019

0.0

... 然而,在实际应用中,大部分样本同时包含多个类别标签,即多标记学习^[1,2,3] ...

2022

0.0

... 然而,在实际应用中,大部分样本同时包含多个类别标签,即多标记学习^[1,2,3] ...

2020

0.0

... 然而,在实际应用中,大部分样本同时包含多个类别标签,即多标记学习^[1,2,3] ...

2020

0.0

... 特征选择作为一种常用的解决维数灾难问题的有效方法,在多标记分类任务中占有重要位置^[4] ...

1982

0.0

... 经典粗糙集^[5]是一种处理不确定数据的数学工具,广泛应用于特征选择 ...

2015

0.0

... 为了扩展经典粗糙集的适用性,学者们提出邻域粗糙集模型(Neighborhood Rough Sets, NRS)^[6]、模糊粗糙集模型(Fuzzy Rough Sets, FRS)^[7]和模糊邻域粗糙集模型(Fuzzy Neigh-borhood Rough Sets, FNRS)^[8,9] ...

2019

0.0

2016

0.0

2020

0.0

2021

0.0

... 然而,NRS使用邻域相似类近似描述决策等价类,无法表示模糊背景下实例的模糊性^[10,11] ...

2019

0.0

... 然而,NRS使用邻域相似类近似描述决策等价类,无法表示模糊背景下实例的模糊性^[10,11] ...

2018

0.0

... Lin等^[12]利用不同的模糊关系度量不同标签下样本之间的相似度,提出基于FRS的多标记特征选择算法 ...

2019

0.0

... 赵晋欢等^[13]基于FRS,构造模糊辨识矩阵,对连续型数据进行属性约简 ...

2019

0.0

... 姚二亮等^[14]同样在FRS中基于模糊辨识关系,分别从样本和标记角度计算多标记特征重要度 ...

... 通过实验选取各数据集上可使性能指标均为最优时的最佳权重值,并与其它算法进行对比^[14],而本文通过选取固定值0 ...

2020

0.0

... FNRS可构造一个鲁棒的距离函数,使用模糊信息粒度描述实例决策,降低数据分类的错误率^[15] ...

2019

0.0

... 1 模糊邻域粗糙集定义1^[16] 设MFNDS=#cod#x0003C ...

... 定义2^[16] 给定一个多标记模糊邻域决策系统 ...

... 定义3^[16] 设MFNDS=#cod#x0003C ...

... 特征a_k在样本x_i、x_j之间的模糊相似关系为^[16]: ...

2021

0.0

... 在大多数模糊邻域粗糙集上,邻域值是根据以往专家的经验人为给出,主观性较强^[17],在不同的数据集上选取的邻域半径值相同,未结合每个数据集自身的分布特征进行选取 ...

... 定义4^[17] 设MFNDS=#cod#x0003C ...

... 定义5^[17] 给定多标记模糊邻域决策系统 ...

2007

0.0

... 否则为0^[18] ...

... 采用ML-KNN(Multi-label K-Nearest Neighbor)^[18]和MLFE(Multi-label Learning with Feature-Induced Labeling Information Enrichment)^[19]分类器验证DSFNS的分类性能,ML-KNN与MLFE中的平滑参数均设为1,最近邻K值均设为10^[20] ...

2018

0.0

2018

0.0

2010

0.0

... 实验中选取多标签分类中常用的7个评价指标,包括:平均精度(Average Precision, AP)、覆盖率(Coverage, CV)、汉明损失(Hamming Loss, HL)、1-错误率(One Error, OE)、排序损失(Rank Loss, RL)、宏平均F1(Macro-Averaging F1, MacF1)和微平均F1(Micro-Averaging F1, MicF1)^[21] ...

... 2 在ML-KNN分类器下的实验结果实验选取如下6种相关的多标记特征选择算法:MDDM_p(Multilabel Dimensionality Reduction via Dependence Maximization with Uncorrelated Projection Constraint)^[21]、MDDM_f(Multilabel Dimensionality Re-duction via Dependence Maximization with Uncorrela-ted Feature Constraint)^[21]、PMU^[22]、RF-ML(ReliefF for Multi-label Feature Selection)^[23]、MLDFC(Multi-label Feature Selection Based on Label Distribution and Feature Complementarity)^[24]、MFSFN(Multi-label Feature Selection Algorithm Based on Fuzzy Neighbor-hood Rough Sets)^[25] ...

2013

0.0

2013

0.0

2020

0.0

2022

0.0

2017

0.0

... 3 在MLFE分类器下的实验结果本节选取如下对比算法:PCT-CHI2(Pair-wise Comparison Transformation Method Combined with Chi-square Statistics)^[26]、CSFS(Convex Semi-super-vised Multi-label Feature Selection)^[27]、SFUS(Sub-Feature Uncovering with Sparsity)^[28]、文献[29]算法 ...

2014

0.0

2012

0.0

2017

0.0