基于标记模糊化的层次特征选择

Hierarchical feature selection based on label fuzzification

摘要

分层分类任务通常面临高维特征空间、复杂的类别层次结构以及标记稀疏等多重挑战，其中，标记稀疏性导致监督信息不足，进而削弱特征选择的效果.针对该问题，提出一种新的层次特征选择方法——基于标记模糊化的层次特征选择方法（Hierarchical Feature Selection Based on Label Fuzzification，HFSLF），其核心思想是通过增强稀疏标记的语义表达能力来改善监督信息.具体地，HFSLF首先利用兄弟关系构建类别间的模糊相似性，并利用该相似性将样本的原始标记转化为标记分布，这一转化过程有效扩展了监督信息的覆盖范围，增强了稀疏场景下的语义监督表达.进一步，所提算法以特征与标记分布之间的互信息为监督信号，引导特征权重逼近其对应的互信息值，从而增强模型对高相关性特征的选择偏好.在六个层次数据集上的实验证明了所提算法的有效性.

Abstract

Hierarchical classification tasks typically face multiple challenges，such as high⁃dimensional feature space，a complex label hierarchy，and label sparsity. Among these，label sparsity can lead to insufficient supervision，thereby degrading the effectiveness of feature selection.To address this issue，this paper proposes a novel hierarchical feature selection method：Hierarchical Feature Selection Based on Label Fuzzification (HFSLF). The core idea of this method is to improve supervision by enhancing the semantic expressiveness of sparse labels. Specifically，HFSLF first uses sibling relationships to construct fuzzy similarities among categories and transforms the original sample labels into label distributions. This transformation effectively expands the coverage of supervisory information and strengthens semantic supervision in sparse scenarios. Then，the proposed algorithm employs the mutual information between features and label distributions as a supervisory signal，guiding the feature weights to approximate their corresponding mutual information values，thereby enhancing the model's preference for highly relevant features. Experiments on six hierarchical datasets demonstrate the effectiveness of the proposed algorithm.

Graphical abstract

关键词

特征选择 / 分层分类学习 / 标记模糊化 / 互信息

Key words

feature selection / hierarchical classification learning / label fuzzification / mutual information

在大数据时代，面对日益增长的数据，传统的扁平化建模方式正面临严峻挑战：一方面，样本的特征空间通常具有高维性，并可能伴随显著稀疏性，这对模型的表达能力和泛化能力提出了更高的要求；另一方面，样本的标记空间往往蕴含丰富的语义结构，类别之间通过父子、兄弟等关系形成层次化体系.这种结构化的先验知识不仅反映了人类对知识的自然组织方式，也为处理大规模、细粒度分类任务提供了关键线索.从18世纪卡尔·冯·林奈建立的生物分类体系^［1］到当代ImageNet的语义层级结构^［2］和层次化文本分类^［3］，层次化建模的思想一脉相承，广泛应用于各类复杂分类场景.研究表明，当样本规模庞大且类别间存在较强语义关联时，分层分类建模已成为提升模型泛化能力和预测一致性的主流范式之一.因此，有效利用标记空间的层次结构进行建模已成为当前研究的热点.

在分层分类任务建模过程中，随着任务涉及的类别规模从最初的二类分类到网页数据的万类级别^［4］，学习模型正面临日益严峻的多重挑战.高维特征导致存储压力与计算开销显著增加，类别数量的急剧增长进一步加剧了模型的泛化难度.为了缓解高维性问题，特征选择作为一种关键的数据降维技术受到广泛关注.然而，传统特征选择方法大多基于扁平化分类框架设计，忽略标记空间存在的层次关系，导致特征选择过程难以充分利用标记空间中的先验知识，限制了对样本信息的充分挖掘.因此，面对超多类别且类别间存在层次化语义关联时，选出最具判别力的特征子集已成为当前亟待解决的关键问题.

粒计算^［5-6］是模拟人类多层次认知机制的计算范式，其理论框架强调通过构建多层次的信息结构，实现对复杂数据的结构化分析与建模.模糊粗糙集^［7］作为粒计算的重要理论工具，能够基于模糊相似关系对数据进行粒化，形成不同粒度层次的信息表示，有效处理数据中的模糊性与不确定性.Wang et al^［8］利用模糊邻域的概念定义了样本的模糊决策，将原始标记转化为模糊标记，通过引入参数化模糊关系对模糊信息粒进行刻画，在重构模糊决策下近似和上近似的基础上提出一种模糊粗糙模型.Wang et al^［9］提出一种有向模糊粗糙集模型，将类别子空间的分布信息融合到有向模糊二元关系中，由此开发了一种启发式特征选择算法.Deng et al^［10］通过标记分布的相关性定义样本间的模糊等价关系并评估被划分为同一类别的概率，构建了一种新的邻域模糊粗糙集.然而，上述算法主要面向扁平标记空间，没有充分考虑标记空间存在层次关系.

在分层分类任务中，利用模糊粗糙集模型构建与类别层次相协调的信息粒，有助于挖掘数据中潜在的信息^［11］，目前已有一些基于模糊粗糙集理论构建的层次特征选择算法被提出.Zhao et al^［12］将层次结构嵌入模糊粗糙集，采用包含策略和兄弟策略为层次分类重新定义了下近似和上近似，由此设计了一种基于模糊粗糙集的层次分类特征选择算法.Qiu and Zhao^［13］根据标记语义的层次结构，将特征选择任务分解为粗粒度和细粒度任务，采用Hausdorff距离的模糊粗糙集方法，给出一种基于粒计算的层次特征选择方法.Bai et al^［14］通过在线重要性选择和在线冗余分析，构建了一种基于核模糊粗糙集的层次流特征选择框架.已有方法提升了特征选择的性能，但仍然存在对类别语义层次利用不充分等问题.具体地，样本与邻近类别（如兄弟类）的潜在语义关联常被忽略，导致信息粒划分过于刚性，造成样本类别的监督信息不够充分，因此，更细腻地刻画样本与层次化标记之间的语义关联，成为提升模型泛化能力的关键.

为此，本文引入标记模糊化机制，将样本原有的标记扩展为对多个相关类别的模糊隶属度表示.通过模糊相似关系和兄弟策略，计算研究样本与兄弟类别样本间的相似关系，进一步为每个样本分配其在不同层次上的局部隶属度，构建更细腻的标记空间.这种通过模糊化生成的标记分布能捕捉样本与语义相似类别之间的潜在关联，为后续特征选择模型的构建提供更丰富的语义支持.

综上，本文提出基于标记模糊化的层次特征选择算法（Hierarchical Feature Selection Based on Label Fuzzification，HFSLF）.首先，利用兄弟策略重新构建模糊相似关系将样本的原始标记转化为标记分布；随后，在目标函数中嵌入特征与标记分布之间的互信息作为正则化项，以增强所选特征与层次化语义结构之间的关联性.最后，通过实验验证了本文所提算法的有效性.

1 准备知识

1.1　类别的层次结构

层次结构主要有两种类型：树结构和有向无环图结构^［15］.本文主要关注树结构关系，树结构的“从属”关系存在三个特性，即不可逆性、反自反性和传递性^［16］.用\left(L,\prec \right)表达层次结构，其中，L为标记集合，“\prec”表示从属关系，则上述特性可形式化地表达为：

（1）不可逆性：若l_i\prec l_j,\forall l_i,l_j\in L,则l_j\nless l_i；

（2）反自反性：\forall l_i\in L,则l_i\nprec l_i；

（3）传递性：若l_i\prec l_j且l_j\prec l_k,对\forall l_i,l_j,l_k\in L,

则l_i\prec l_k.

1.2　分层分类的类别关系

在分层分类任务中，可根据不同的策略对目标样本的同类和异类进行刻画.如表1第1行所示，假定目标样本的类别为L_p，则根据排斥策略^［17］得到异类为非L_p.在分层分类中，利用类别之间的父子关系和兄弟关系可得到包含策略和兄弟策略^［17-18］下的同类样本和异类样本（见表1第2行和第3行）.

例1

图1展示了数据集VOC^［19］类别层次结构的局部信息.以Farmyard类为例，在排斥策略下，Farmyard类的同类仅包含其自身，其余所有类别均为其异类.在包含策略下，Farmyard类的同类包括其自身及其子类Cow，Horse和Sheep，其余类别为其异类.在兄弟策略下，Farmyard类的同类为其自身，而其异类仅包含其兄弟类别Domestic.

1.3　基于稀疏学习的层次特征选择框架

首先，设样本矩阵为X\in R^{n\times m}，其中，n表示样本数，m表示特征数.定义层次结构中的非叶子结点的个数（也称内部结点）为N+\mathrm{1}，则样本矩阵可划分为X_{\mathrm{0}},X_{\mathrm{1}},\cdots ,X_N，其中，X_i=[x_i^{\mathrm{1}},x_i^{\mathrm{2}},\cdots ,x_i^{n_i}]\in R^{n_i\times m}表示第i个内部结点的样本矩阵.其次，定义Y_{\mathrm{0}},Y_{\mathrm{1}},\cdots ,Y_N为内部结点的标记矩阵：

\begin{array}{l}{Y}_i=\left[y_i^{\mathrm{1}},y_i^{\mathrm{2}},\cdots ,y_i^{n_i}\right]\in R^{n_i\times d_{\mathrm{m}\mathrm{a}\mathrm{x}}}\\ y_k={\left\{\mathrm{0,1}\right\}}^{d_{\mathrm{m}\mathrm{a}\mathrm{x}}},\mathrm{1}\le k\le n_i\end{array}

其中，d_{\mathrm{m}\mathrm{a}\mathrm{x}}代表内部结点标记数量的最大值.再者，定义W_i=\left[w_i^{\mathrm{1}};w_i^{\mathrm{2}};\cdots ;w_i^m\right]\in R^{m\times d_{\mathrm{m}\mathrm{a}\mathrm{x}}}为每个内部结点的权重矩阵.根据已有经验，稀疏学习被证明是一种有效的特征选择方法^［20］，通常可表达为如下形式^［21］：

\underset{W}{\mathrm{m}\mathrm{i}\mathrm{n}}L\left(W;X,Y\right)+\lambda \Gamma \left(W\right)(1)

其中，L\left(·\right)表示损失函数，通常是最小二乘损失、铰链损失等.本文采用最小二乘损失作为损失函数，损失函数可定义为：

L\left(W;X,Y\right)={‖XW-Y‖}_F^{\mathrm{2}}(2)

对于稀疏正则化项\Gamma \left(W\right)，由于l_{\mathrm{2,1}}范数的正则化是凸的，且容易根据Argyriou et al^［22］的方法进行优化，因此本文采用该范数来构建模型.结合式（2）和l_{\mathrm{2,1}}范数得到基于稀疏学习的层次特征选择的基本框架为：

J={}_w{}^{\mathrm{m}\mathrm{i}\mathrm{n}}\left({\sum }_{i=\mathrm{0}}^N\left({‖X_i{W}_i-Y_i‖}_F^{\mathrm{2}}+\lambda {‖W_i‖}_{\mathrm{2,1}}\right)\right)(3)

2 基于标记模糊化的层次特征选择

首先介绍单标记环境下的标记模糊化模型，然后将其推广至层次化结构的数据场景，在此基础上，将该模型嵌入到所提算法框架中.

2.1　模糊标记

称FDIS=〈U,A,f,D,q〉为模糊决策信息系统，其中，U为非空论域，A为非空条件属性集，D为决策属性集.f:U\times A\to

{\bigcup }_{i=\mathrm{1}}^m{V}_i，其中，V_i表示任意属性a_i\in A的值域.

q:U\times D\to {\bigcup }_{i=\mathrm{1}}^m{V}_i^d，其中，V_i^d表示决策属性d_i\in D的值域^［23］.

给定论域U=\left\{x_{\mathrm{1}},x_{\mathrm{2}},\cdots ,x_n\right\}，设B\subseteq A是一组实值属性的子集，这些属性在U上诱导出一个模糊二元关系R_B.如果R_B满足以下条件，则称其为模糊相似关系^［8］.

（1）自反性：R_B\left(x,x\right)=\mathrm{1},\forall x\in U.

（2）对称性：R_B\left(x,y\right)=R_B\left(y,x\right),\forall x,y\in U.

对于任意x\in U，x的模糊邻域{[x]}_B定义为：

{\left[x\right]}_B=R_B\left(x,y\right),\forall y\in U

给定论域U，D是论域上的一个决策属性，并将U划分为k个清晰的等价类U/D=\left\{D_{\mathrm{1}},D_{\mathrm{2}},\cdots ,D_k\right\}，引入样本的模糊划分和模糊决策的概念.

定义1^［8］

给定论域U，\left\{{\tilde{D}}_{\mathrm{1}},{\tilde{D}}_{\mathrm{2}},\cdots ,{\tilde{D}}_k\right\}是U上的一组模糊集，如果满足：

{\sum }_{i=\mathrm{1}}^k{\tilde{D}}_i=\mathrm{1},\forall x\in U(4)

则称\left\{{\tilde{D}}_{\mathrm{1}},{\tilde{D}}_{\mathrm{2}},\cdots ,{\tilde{D}}_k\right\}为一个模糊划分.

定义2^［8］

给定一个决策属性D，且U/D=\left\{D_{\mathrm{1}},D_{\mathrm{2}},\cdots ,D_k\right\}，R_B是由属性集B在U上诱导出来的模糊相似关系.对于任意x\in U，x的模糊决策，定义为：

{\tilde{D}}_i\left(x\right)=\frac{\left|{\left[x\right]}_B\bigcap D_i\right|}{\left|{\left[x\right]}_B\right|},i=\mathrm{1,2},\cdots ,k(5)

对任意x\in U,B\subseteq A,\delta \in \left(\mathrm{0,1}\right)，样本x的模糊信息粒{\left[x\right]}_B^{\delta }定义为：

(6)

2.2　分层分类任务下的模糊标记

2.1给出了单标记场景下的模糊邻域粒和模糊决策的定义.为了适应分层分类任务下的样本粒化，利用兄弟策略重新定义样本的模糊信息粒.

称HFDIS=〈U,A,f_H,\tilde{D},H,q_H〉为层次模糊决策信息系统，其中，U为非空论域，A为非空条件属性集，\tilde{D}为模糊决策属性集，H表示标记空间的层次结构关系.f_H:U\times A\to \left[\mathrm{0,1}\right]，q_H:U\times \tilde{D}\to \left[\mathrm{0,1}\right]表示决策属性d_i\in \tilde{D}的值域在\left[\mathrm{0,1}\right].

为了适应分层分类的应用场景，在定义1的基础上，利用兄弟策略可得如下模糊划分的定义.

定义3

给定HFDIS=〈U,A,f_H,\tilde{D},H,q_H〉,

\left\{{\tilde{D}}_{\mathrm{1}},{\tilde{D}}_{\mathrm{2}},\cdots ,{\tilde{D}}_k\right\}是U上的一组模糊集，如果\left\{{\tilde{D}}_{\mathrm{1}},{\tilde{D}}_{\mathrm{2}},\cdots ,{\tilde{D}}_k\right\}之间互为兄弟关系，且满足：

{\sum }_{i=\mathrm{1}}^k{\tilde{D}}_i=\mathrm{1},\forall x\in U(7)

则称{\tilde{D}}_{\mathrm{1}},{\tilde{D}}_{\mathrm{2}},\cdots ,{\tilde{D}}_k为一个分层分类任务下的模糊划分.

陈曦等^［24］在多标记模糊信息系统中利用高斯核函数定义了特征子集的模糊关系，本节在此基础上进行扩展，利用兄弟策略重新定义层次模糊信息系统下的模糊关系.

定义4

给定HFDIS，对任意B\subseteq A,

\forall x,y\in U且L\left(y\right)\in sib\left(L\left(x\right)\right)，其中，L\left(x\right)表示样本x的类标记.利用高斯核函数定义属性集B的模糊关系{\tilde{R}}_B^H\left(x,y\right)：

{\tilde{R}}_B^H\left(x,y\right)=\mathrm{e}\mathrm{x}\mathrm{p}\left\{-\frac{\mathrm{1}}{\mathrm{2}{\sigma }^{\mathrm{2}}}{\sum }_{b\in B}\left|f\left(x,b\right)-f\left(y,b\right)\right|\right\}(8)

其中，参数\sigma表示高斯核宽度.

由此，得到任意样本x\in U关于属性子集B\subseteq A的模糊信息粒{\left[x\right]}_B^{sib}\left(y\right)为：

{\left[x\right]}_B^{sib}\left(y\right)=\left\{\begin{array}{c}\mathrm{0},L\left(y\right)\notin sib\left(L\left(x\right)\right)\\ R_B\left(x,y\right),L\left(y\right)\in sib\left(L\left(x\right)\right)\end{array}\right.(9)

基于定义4，进一步提出样本的模糊决策概念，其定义如下.

定义5

给定一个决策属性D，且U/D=\left\{D_{\mathrm{1}},D_{\mathrm{2}},\cdots ,D_k\right\}，{\tilde{R}}_B^H\left(x,y\right)是由属性集B在U上诱导出来的模糊相似关系.对于任意x\in U,x的基于兄弟关系的模糊决策定义为：

{\tilde{D}}_i^{sib}\left(x\right)=\frac{\left|{\left[x\right]}_B^{sib}\bigcap D_i\right|}{\left|{\left[x\right]}_B^{sib}\right|},i=\mathrm{1,2},\cdots ,k(10)

根据定义5，可将样本的原始标记转化为标记分布.相较于原始标记，式（10）得到的标记分布充分融合了类别间的兄弟关系，增强了稀疏标记下的监督信息表达.基于以上分析，设计了一种面向层次分类任务的标记模糊化算法，具体步骤如下.

算法1 面向分层分类任务的标记模糊化算法（Label Fuzzification for Hierarchical Classification Tasks）

输入：训练样本特征矩阵X_i\in R^{n_i\times m}，训练样本标记矩阵Y_i\in R^{n_i\times d_{\mathrm{m}\mathrm{a}\mathrm{x}}}，参数\sigma

输出：样本的标记分布

初始化：{\tilde{D}}_i\left(x\right)=Y_i

1.for i=\mathrm{0}:N do

2. for j=\mathrm{0}:n_i do

3. for q=\mathrm{0}:n_i do

4. 通过式（8）计算{\tilde{R}}_B^H

5. end

6. end

7. for k=\mathrm{0}:n_i do

8. for q=\mathrm{0}:d_i do

9. 通过式（10）计算样本的标记分布

10. end

11. end

12. 更新{\tilde{D}}_i^{sib}=\left[d_{\mathrm{0}};d_{\mathrm{1}};\cdots ;d_{n_i}\right]

13. 更新{\tilde{D}}^{sib}=\left[{\tilde{D}}_{\mathrm{1}}^{sib},{\tilde{D}}_{\mathrm{2}}^{sib},\cdots ,{\tilde{D}}_N^{sib}\right]

14.end

15.return {\tilde{D}}^{sib}

在获得标记分布矩阵{\tilde{D}}^{sib}后，将分层特征选择的基本模型重新定义为：

J=\mathrm{m}\mathrm{i}\mathrm{n}{\sum }_{i=\mathrm{0}}^N\left({‖X_i{W}_i-{\tilde{D}}_i^{sib}‖}_F^{\mathrm{2}}+\lambda {‖W_i‖}_{\mathrm{2,1}}\right)(11)

2.3　融合互信息的层次特征选择框架

互信息广泛用于度量变量之间的统计依赖关系，因此，为探索特征与标记分布之间的关系，本文引入互信息作为正则项.采用Kraskov et al^［25］的方法计算特征与标记之间的互信息如下所示：

\begin{array}{l}I\left(X_{·p},{\tilde{D}}_{·l}^{sib}\right)=\\ \psi \left(z\right)+\psi \left(n\right)-\frac{\mathrm{1}}{n}{\sum }_{i=\mathrm{1}}^n\left(\psi \left(n_{X_{ip}}\right)+\psi \left(n_{{\tilde{D}}_{il}^{sib}}\right)\right)\end{array}(12)

其中，I\left(X_{·p},{\tilde{D}}_{·l}^{sib}\right)表示特征向量X_{·p}与标记分布向量{\tilde{D}}_{·l}^{sib}之间的互信息.

将\sqrt[]{{\left(X_{ip}-X_{jp}\right)}^{\mathrm{2}}+{\left({\tilde{D}}_{il}^{sib}-{\tilde{D}}_{jl}^{sib}\right)}^{\mathrm{2}}}作为样本X_i与X_j之间的距离，设{\tau }_i表示X_i与其z近邻之间的距离.根据文献建议，取z=\mathrm{3}，则式（12）中的n_{X_{ip}}和n_{{\tilde{D}}_{il}^{sib}}分别满足和的样本数量.\psi \left(·\right)为digamma函数，满足：

\psi \left(u+\mathrm{1}\right)=\left\{\begin{array}{c}\psi \left(u\right)+\frac{\mathrm{1}}{u},u>\mathrm{0}\\ -C,u=\mathrm{0}\end{array}\right.(13)

其中，C=\mathrm{0.58}表示欧拉常数.

通过式（12）计算特征与标记分布之间的互信息，由此构造矩阵M\in R^{m\times d^{\mathrm{\text{'}}}}，其中，d^{\mathrm{\text{'}}}表示当前内部节点所对应的标记数量，其元素M_{pl}=I\left(X_{·p},{\tilde{D}}_{·l}^{sib}\right).由此构造如下正则项以约束特征权重：

{‖W-M‖}_F^{\mathrm{2}}(14)

结合式（11）和（14），可得最终的目标函数：

\begin{array}{l}J=\\ \mathrm{m}\mathrm{i}\mathrm{n}{\sum }_{i=\mathrm{1}}^N\left({‖X_i{W}_i-{\tilde{D}}_i^{sib}‖}_F^{\mathrm{2}}+\lambda {‖W_i‖}_{\mathrm{2,1}}+\gamma {‖W_i-M_i‖}_F^{\mathrm{2}}\right)\end{array}(15)

其中，\lambda和\gamma为平衡因子.

2.4　模型优化与算法伪代码

式（15）中，由于l_{\mathrm{2,1}}的非光滑性，根据Argyriou et al^［22］进行推导：

\frac{\partial {‖W‖}_{\mathrm{2,1}}}{\partial W}=\frac{\partial \mathrm{T}\mathrm{r}\left(W^{\mathrm{T}}AW\right)}{\partial W}=\mathrm{2}AW(16)

其中，A\in R^{d_{\mathrm{m}\mathrm{a}\mathrm{x}}\times d_{\mathrm{m}\mathrm{a}\mathrm{x}}}为对角矩阵，其第j个对角元素是a_{jj}^i=\frac{\mathrm{1}}{\mathrm{2}{‖W_i^j‖}_{\mathrm{2}}}，如果W_i^j=\mathrm{0}，设a_{jj}^i=ϵ.

依据式（16），将目标函数重新表达为：

\begin{array}{l}J=\\ \mathrm{m}\mathrm{i}\mathrm{n}{\sum }_{i=\mathrm{0}}^N\left({‖X_i{W}_i-{\tilde{D}}_i^{sib}‖}_F^{\mathrm{2}}+\lambda \mathrm{T}\mathrm{r}\left(W^{\mathrm{T}}AW\right)+\gamma {‖W_i-M_i‖}_F^{\mathrm{2}}\right)\end{array}(17)

对于各个内部结点，将式（17）关于W_i的导数设置为0，得到：

\begin{array}{l}\frac{\partial J}{\partial W}=\\ \mathrm{2}{X_i}^{\mathrm{T}}\left(X_i{W}_i-{\tilde{D}}_i^{sib}\right)+\mathrm{2}\lambda A_i{W}_i+\mathrm{2}\gamma \left(W_i-M_i\right)=\mathrm{0}\end{array}(18)

由此可得：

W_i={\left({X_i}^T{X}_i+\lambda A_i+\gamma I_i\right)}^{-\mathrm{1}}\left({X_i}^{\mathrm{T}}{\tilde{D}}_i^{sib}+\gamma M_i\right)(19)

根据式（18）和式（19），给出所提算法的伪代码，如算法2所示.通过算法2可到特征的权重矩阵W，对权重矩阵进行排序之后，选取权重值较大的特征即可完成特征选择任务.

算法2 基于标记模糊化的层次特征选择（Hierarchical Feature Selection Based on Label Fuzzification）

输入：训练样本特征矩阵X_i\in R^{n_i\times m}，参数\lambda ,\gamma，迭代次数T

输出：特征权重矩阵集合W\in R^{m\times d_{\mathrm{m}\mathrm{a}\mathrm{x}}}

初始化：{\tilde{D}}_i\left(x\right)=Y_i

1.初始化d_{\mathrm{m}\mathrm{a}\mathrm{x}}为内部节点的最大类别数，t=\mathrm{0}

2.随机初始化：W^{\left(\mathrm{0}\right)}=W_{\mathrm{0}},W_{\mathrm{1}},\cdots ,W_N\in R^{m\times d_{\mathrm{m}\mathrm{a}\mathrm{x}}}

3.计算训练样本的标记分布矩阵{\tilde{D}}_i^{sib}\in R^{n_i\times d_{\mathrm{m}\mathrm{a}\mathrm{x}}}

4.根据式（12）计算互信息M

5.while do

6. for i=\mathrm{0}:N do

7. 计算a_{jj}^i=\frac{\mathrm{1}}{\mathrm{2}{‖W_i^j‖}_{\mathrm{2}}}，求矩阵{A_i}^{\left(t\right)}

8. end for

9. for i=\mathrm{0}:N do

10. 通过式（19）更新W_i

11. end for

12. W^{\left(t+\mathrm{1}\right)}=\left[W_{\mathrm{0}},W_{\mathrm{1}},\cdots ,W_N\right]

13. t=t+\mathrm{1}

14.end while

15.返回W

算法2中包含算法1的标记分布生成过程和互信息的计算过程，因此在分析算法2基于标记模糊化的层次特征选择算法HFSLF的时间复杂度时，需分析算法1和互信息计算过程的时间开销.算法1的时间复杂度为O\left(N{n}^{\mathrm{2}}\left(m+d_{\mathrm{m}\mathrm{a}\mathrm{x}}\right)\right)，其中，N是节点个数，n是样本总数.互信息的时间复杂度为O\left(N{n}^{\mathrm{2}}m{d}_{\mathrm{m}\mathrm{a}\mathrm{x}}\right).对于算法2，其迭代域的时间复杂度主要取决于特征权重的计算和更新，每个内部节点迭代权重矩阵的时间复杂度为O\left(m^{\mathrm{3}}+N{m}^{\mathrm{2}}{d}_{\mathrm{m}\mathrm{a}\mathrm{x}}+m^{\mathrm{2}}{n}_i+m{n}_i{d}_{\mathrm{m}\mathrm{a}\mathrm{x}}\right)，其中，n_i为第i个内部节点的样本数.观察式（19），其中，{X_i}^{\mathrm{T}}{X}_i与{X_i}^{\mathrm{T}}{\tilde{D}}_i^{sib}\left(i=\mathrm{1,2},\cdots ,N\right)只要计算一次，时间复杂度表达为O\left(m^{\mathrm{2}}{n}_i+m{n}_i{d}_{\mathrm{m}\mathrm{a}\mathrm{x}}\right),可知所有内部节点所需的时间复杂度为O\left(m^{\mathrm{2}}n+mn{d}_{\mathrm{m}\mathrm{a}\mathrm{x}}\right).算法迭代次数为T，可知这部分时间复杂度为：

O\left(T\left(m^{\mathrm{3}}+N{m}^{\mathrm{2}}{d}_{\mathrm{m}\mathrm{a}\mathrm{x}}\right)+m^{\mathrm{2}}n+mn{d}_{\mathrm{m}\mathrm{a}\mathrm{x}}\right)

综上，所提算法的时间复杂度为：

\begin{array}{l}O\left(T\left(m^{\mathrm{3}}+N{m}^{\mathrm{2}}{d}_{\mathrm{m}\mathrm{a}\mathrm{x}}\right)+m^{\mathrm{2}}n+mn{d}_{\mathrm{m}\mathrm{a}\mathrm{x}}+\right.\\ \left.N{n}^{\mathrm{2}}\left(m+d_{\mathrm{m}\mathrm{a}\mathrm{x}}+m{d}_{\mathrm{m}\mathrm{a}\mathrm{x}}\right)\right)\end{array}

3 实验与分析

对实验结果进行系统分析，包括三个方面：数据集与评价指标、对比算法与参数设置和算法性能分析.其中，性能分析进一步涵盖性能指标、参数敏感性、消融实验与模型收敛等内容.

3.1　数据集与评价指标

为了验证算法的有效性，选取六个具有层次结构的数集进行实验，包括两个蛋白质数据集DD^［26］和F194^［27］、四个图像数据集AWA^［28］，CLEF^［29］，ILSVRC65^［30］和VOC^［19］.表2为数据集的相关描述.

评价指标包括预测精度、树诱导损失（Tree Induced Error，TIE）^［31］和基于增广集合的分层F1（Hierarchical⁃F1 measure）^［32］.其中，预测精度的计算方法与传统算法一致，而TIE和Hierarchical⁃F1 measure是为了评估层次结构中的错分程度而引入的.

令y和\widehat{y}分别代表样本真实标记和预测标记，Anc\left(y\right)和Anc\left(\widehat{y}\right)为y和\widehat{y}的祖先结点集合，则y和\widehat{y}的分层分类扩展标记分别表示为Y_{\mathrm{a}\mathrm{u}\mathrm{g}}=y\bigcup Anc\left(y\right)和{\widehat{Y}}_{\mathrm{a}\mathrm{u}\mathrm{g}}=\widehat{y}\bigcup Anc\left(\widehat{y}\right).

TIE指标通过计算预测标记\widehat{y}到真实标记y在层次结构中结点之间的总边数来反映分错程度：

TIE\left(y,\widehat{y}\right)=\left|E_H\left(y,\widehat{y}\right)\right|(20)

其中，E_H\left(y,\widehat{y}\right)表示从y到\widehat{y}结点之间边的集合.

Hierarchical⁃F1 measure的计算如式（21）所示：

F_H=\frac{\mathrm{2}\times P_H\times R_H}{P_H+R_H}(21)

其中，

P_H=\frac{\left|Y_{\mathrm{a}\mathrm{u}\mathrm{g}}\bigcap {\widehat{Y}}_{\mathrm{a}\mathrm{u}\mathrm{g}}\right|}{\left|{\widehat{Y}}_{\mathrm{a}\mathrm{u}\mathrm{g}}\right|},R_H=\frac{\left|Y_{\mathrm{a}\mathrm{u}\mathrm{g}}\bigcap {\widehat{Y}}_{\mathrm{a}\mathrm{u}\mathrm{g}}\right|}{\left|Y_{\mathrm{a}\mathrm{u}\mathrm{g}}\right|}

TIE指标取值越小越好，Hierarchical⁃F1 measure指标取值则越大越好.

3.2　对比算法和参数设置

将所提算法与五个分层特征选择算法进行比较.

（1） HRelief^［33］：由Relief扩展而来.

（2） HFSNM^［34］：根据FSNM修改而来.

（3） HIFSRR^［35］：是基于层次结构中的粒度关系，同时考虑父子关系和兄弟关系的优化特征选择算法.

（4） HSDFS^［36］：集成迹比目标和结构化稀疏子空间约束，以获取特征子集.

（5） HFSDK^［37］：基于粗粒度和细粒度类之间的相似性来约束所选的层间特征，并依赖于有上限的铰链损失来消除数据异常值.

所提算法涉及三个参数，分别是标记模糊化过程中的高斯核宽度参数\sigma、优化目标中的平衡因子\lambda和\gamma.其中，\sigma在\left[\mathrm{0.5,2}\right]以步长为0.5进行调整，\lambda固定为10，\gamma的取值在\left\{{\mathrm{10}}^{-\mathrm{3}},{\mathrm{10}}^{-\mathrm{2}},{\mathrm{10}}^{-\mathrm{1}},\right.

\left.{\mathrm{10}}^{\mathrm{0}},{\mathrm{10}}^{\mathrm{1}},{\mathrm{10}}^{\mathrm{2}}\right\}调整，并记录最优实验结果.采用自上而下的支持向量机分类器对所提算法的有效性进行评估.对于蛋白质数据集，采用排名靠前40个特征进行训练；对于图像数据集，采用前20%的特征进行训练.采用10折交叉验证.对于对比算法，根据相应文献中的建议搜索参数.

3.3　算法性能分析

从以下方面对实验进行了评估：（1）算法性能分析；（2）参数敏感性分析；（3）消融实验；（4）收敛性分析.

3.3.1　算法性能分析

表3~5分别给出六种算法在六个数据集上的Acc，F_H和TIE三个指标的实验结果，其中，符号“\downarrow”表示指标的取值越小越好，符号“\uparrow”表示指标的取值越大越好，表中黑体字表示对应指标下的最优结果.

从实验结果看，所提算法在所有评价指标上，均有半数的数据集上达到最优性能，体现出其在不同数据特性下的稳定性和适应性.以数据集DD为例，其特征空间具有高稀疏性，而本文算法在该数据集上的优异表现，验证了将原始标记转化为标记分布后，通过计算标记空间与特征空间互信息的有效性，这主要得益于标记分布能够提供更丰富的监督信息.以上结果初步说明，所提算法具有较强的鲁棒性和泛化能力.

为了进一步评估算法的统计显著性，采用Friedman检验^［38］作为算法排序的评估标准.给定P个算法和Q个数据集，第i个算法的平均排名表示为r_i，则Friedman检验使用式（22）进行统计：

F_F=\frac{\left(Q-\mathrm{1}\right){\mathit{𝒳}}_F^{\mathrm{2}}}{Q\left(P-\mathrm{1}\right)-{\mathit{𝒳}}_F^{\mathrm{2}}}(22)

其中，

{\mathit{𝒳}}_F^{\mathrm{2}}=\frac{\mathrm{12}Q}{P\left(P+\mathrm{1}\right)}\left({\sum }_{i=\mathrm{1}}^P{r_i}^{\mathrm{2}}-\frac{P{\left(P+\mathrm{1}\right)}^{\mathrm{2}}}{\mathrm{4}}\right)

Friedman检验的结果和各项指标对应的阈值见表6.结果表明，显著性水平\alpha =\mathrm{0.05}时，每个指标的F_F值大于F检验临界值，所有算法性能相同的原假设被拒绝.

进一步，使用Nemenyi测试^［39］来检验所提算法与对比算法之间的性能差异.该方法首先计算两种算法在平均排名上的差异，然后利用临界差异值（CD）来评估该差异是否具有统计显著性.临界值域CD的值由式（23）给出：

C{D}_{\alpha }=q_{\alpha }\sqrt[]{\frac{P\left(P+\mathrm{1}\right)}{\mathrm{6}Q}}(23)

在显著性水平\alpha =\mathrm{0.05}下，Nemenyi检验得到q_{\alpha }=\mathrm{2.850}，得到C{D}_{\alpha }=\mathrm{3.0784}.

图2显示了各指标下通过Nemenyi检验来比较各算法性能的检验结果.由图可见，所提算法的Acc和TIE两个指标明显优于HRelief算法；F_H指标明显优于HRelief，HSDFS和HFSNM算法.但没有一致的证据表明HFSDK，HIFSRR的评价指标和HFSLF算法之间存在统计学差异.

3.3.2　参数敏感性分析

HFSLF的三个参数，\lambda固定为10，高斯核宽度参数\sigma \in \left[\mathrm{0.5,2}\right]以步长为0.5进行调整，\gamma取值于集合\left\{{\mathrm{10}}^{-\mathrm{3}},{\mathrm{10}}^{-\mathrm{2}},{\mathrm{10}}^{-\mathrm{1}},\right.

\left.{\mathrm{10}}^{\mathrm{0}},{\mathrm{10}}^{\mathrm{1}},{\mathrm{10}}^{\mathrm{2}}\right\}.由于\lambda已固定，重点对\sigma和\gamma进行参数敏感性分析.采用控制变量法，固定其中一个参数，调节另一个参数，观察其Hierarchical⁃F1的变化，以评估算法性能对参数变化的敏感性.

图3和图4展示了数据集CLEF和F194的分析结果.由图可见，在CLEF上，模型性能在\sigma =\mathrm{1}时达到峰值；在F194上，最优性能出现在\sigma =\mathrm{0.5}.由于本文采用绝对值距离作为相似性度量，较小的\sigma意味着只有在特征差异较小的情况下才赋予高相似权重，这一结果表明，F194需要更严格的局部近邻性才能实现最佳匹配，反映出其局部结构上的高敏感性.

对于参数\gamma，其性能在{\mathrm{10}}^{-\mathrm{3}}~{\mathrm{10}}^{\mathrm{1}}波动较小，表现出良好的鲁棒性；当\gamma ={\mathrm{10}}^{\mathrm{2}}时出现较明显的下降.这可能是互信息正则项权重过大，导致模型的学习能力受限，进而可能引发欠拟合.

3.3.3　消融实验

通过消融实验来分析标记分布和互信息正则化项对HFSLF特征选择的影响.实验设置了以下模型.

（1） HFSLF⁃Base：仅基于稀疏学习正则化，不包含标记分布和互信息正则化项.

（2） HFSLF⁃FL：将原始标记转化为标记分布，但不包含互信息正则化项.

（3） HFSLF：完整模型，包含标记分布与互信息正则化项.

图5展示了HFSLF及其两个比较版本在六个层次数据集上的结果，由图可得以下结论.

（1） 与HFSLF⁃Base相比，HFSLF⁃FL在五个数据集上的性能均得到了提升，由此可知，本文提出的标记分布机制对模型性能有积极的影响.然而，在VOC数据集上，应用标记分布后，效果却略有下降，这可能是由于标记分布本身对该数据集引入了噪声或弱化了关键语义信息，干扰了模型的学习效果.

（2） 与HFSLF⁃FL相比，HFSLF在绝大多数数据集上的表现更优，这表明本文所提的基于互信息的正则化项是有效的.

综上，标记分布与互信息正则项共同构成了HFSLF的核心贡献，在多数情况下提升了模型的泛化能力.

3.3.4　收敛性分析

对所提算法HFSLF进行收敛性分析，所有数据集基于目标函数基础上的收敛曲线如图6所示.实验中，在所有数据集上设置了最大的迭代次数为10.实验表明，所有数据集目标函数单调递减并在不超过10次内收敛.

4 结论

本文提出一种结合标记分布建模与互信息度量的层次特征选择方法.通过标记分布建模，充分挖掘类别间的层次结构信息，并将特征与标记分布之间的互信息融合到特征选择框架，以增强特征排序的相关性与判别性.实验结果表明，该方法在多个层次数据集上具有良好的有效性与鲁棒性.

本研究为复杂结构标记下的特征选择提供了新思路，未来将探索更精细的标记增强方法，进一步提升分类性能.

参考文献

[1] 胡清华，王煜，周玉灿，等. 大规模分类任务的分层学习方法综述. 中国科学(信息科学)，2018，48(5)：487-500.

[2] Deng J， Dong W， Socher R，et al. ImageNet：A large⁃scale hierarchical image database∥2009 IEEE Conference on Computer Vision and Pattern Recog⁃nition. Miami，FL，USA：IEEE，2009：248-255.

[3] Sun A X， Lim E P. Hierarchical text classification and evaluation∥Proceedings 2001 IEEE International Conference on Data Mining. San Jose，CA，USA：IEEE，2001：521-528.

[4] Russakovsky O， Deng J， Su H，et al. ImageNet large scale visual recognition challenge. International Journal of Computer Vision，2015，115(3)：211-252.

[5] Zadeh L A. Toward a theory of fuzzy information granulation and its centrality in human reasoning and fuzzy logic. Fuzzy Sets and Systems，1997，90(2)：111-127.

[6] 张超，丁雨欣，李文涛，等. 新一代人工智能背景下粒计算研究现状与展望. 南京理工大学学报，2025，49(3)：265-277.

[7] Dubois D， Prade H. Rough fuzzy sets and fuzzy rough sets. International Journal of General System，1990，17(2/3)：191-209.

[8] Wang C Z， Qi Y L， Shao M W，et al. A fitting model for feature selection with fuzzy rough sets.IEEE Transactions on Fuzzy Systems，2017，25(4)：741-753.

[9] Wang C Y， Wang C Z， An S，et al. Feature selection and classification based on directed fuzzy rough sets. IEEE Transactions on Systems，Man，and Cybernetics：Systems，2025，55(1)：699-711.

[10] Deng Z X， Li T R， Zhang P F，et al. Feature selection for label distribution learning based on neighborhood fuzzy rough sets. Applied Soft Computing，2025，169：112542.

[11] 折延宏，黄婉丽，贺晓丽，等.面向层次结构数据的增量特征选择. 计算机科学与探索，2023，17(12)：2928-2941.

[12] Zhao H， Wang P， Hu Q H，et al. Fuzzy rough set based feature selection for large⁃scale hierarchical classification.IEEE Transactions on Fuzzy Systems，2019，27(10)：1891-1903.

[13] Qiu Z Y， Zhao H. A fuzzy rough set approach to hierarchical feature selection based on Hausdorff distance. Applied Intelligence，2022，52(10)：11089-11102.

[14] Bai S X， Lin Y J， Lü Y，et al. Kernelized fuzzy rough sets based online streaming feature selection for large⁃scale hierarchical classification. Applied Intelligence，2021，51(3)：1602-1615.

[15] Wu F H， Zhang J， Honavar V. Reformulation and approximation∥Zucker J D，Saitta L. Abstraction，Reformulation and Approximation. Heidelberg：Springer，2005：313-320.

[16] Silla C N， Freitas A A. A survey of hierarchical classification across different application domains. Data Mining and Knowledge Discovery，2011，22(1)：31-72.

[17] Eisner R， Poulin B， Szafron D，et al. Improving protein function prediction using the hierarchical structure of the gene ontology∥2005 IEEE Symposium on Computational Intelligence in Bioinformatics and Computational Biology. La Jolla，CA，USA：IEEE，2005：1-10.

[18] 18］ Ceci M， Malerba D. Classifying web documents in a hierarchy of categories：A comprehensive study. Journal of Intelligent Information Systems，2007，28(1)：37-78.

[19] Everingham M， Van Gool L， Williams C K I，et al. The pascal visual object classes (VOC) challenge. International Journal of Computer Vision，2010，88(2)：303-338.

[20] Li J D， Cheng K W， Wang S H，et al. Feature selection：A data perspective.ACM Computing Surveys，2017，50(6)：1-45.

[21] 林耀进，白盛兴，赵红，等. 基于标签关联性的分层分类共有与固有特征选择. 软件学报，2022，33(7)：2667-2682.

[22] Argyriou A， Evgeniou T， Pontil M. Multi⁃task feature learning∥Proceedings of the 20th International Conference on Neural Information Processing Systems. Cambridge,MA,USA：MIT Press，2006：41-48.

[23] 张文修. 信息系统与知识发现. 北京：科学出版社，2003.

[24] 陈曦，马建敏，刘权芳. 基于模糊依赖决策熵的多标签特征选择. 昆明理工大学学报(自然科学版)，2024，49(2)：62-72.

[25] Kraskov A， Stögbauer H， Grassberger P. Estimating mutual information. Physical Review.E，Statistical，Nonlinear，and Soft Matter Physics，2004，69(6 Pt 2)：066138.

[26] Ding C H， Dubchak I. Multi⁃class protein fold recognition using support vector machines and neural networks. Bioinformatics，2001，17(4)：349-358.

[27] Li D P， Ju Y， Zou Q. Protein folds prediction with hierarchical structured SVM. Current Proteomcs，2016，13(2)：79-85.

[28] Lampert C H， Nickisch H， Harmeling S. Learning to detect unseen object classes by between⁃class attribute transfer∥2009 IEEE Conference on Computer Vision and Pattern Recognition. Miami，FL，USA：IEEE，2009：951-958.

[29] Dimitrovski I， Kocev D， Loskovska S，et al. Hierarchical annotation of medical images. Pattern Recognition，2011，44(10/11)：2436-2449.

[30] Deng J， Krause J， Berg A C，et al. Hedging your bets：Optimizing accuracy⁃specificity trade⁃offs in large scale visual recognition∥2012 IEEE Conference on Computer Vision and Pattern Recognition. Providence，RI，USA：IEEE，2012：3450-3457.

[31] Dekel O， Keshet J， Singer Y. Large margin hierarchical classification∥Proceedings of the 21st Inter⁃national Conference on Machine Learning. New York，NY，USA：Association for Computing Machinery，2004：27.

[32] Kosmopoulos A， Gaussier E， Paliouras G，et al. The ECIR 2010 large scale hierarchical classification workshop. ACM SIGIR Forum，2010，44(1)：23-32.

[33] Kira K， Rendell L A. A practical approach to feature selection∥Proceedings of the 9^th International Workshop on Machine Learning. San Francisco，CA，USA：Morgan Kaufmann Publishers Inc.，1992：249-256.

[34] Nie F P， Huang H， Cai X，et al. Efficient and robust feature selection via joint ℓ2，1⁃norms minimization∥Proceedings of the 24th International Conference on Neural Information Processing Systems. Red Hook，NY，USA：Curran Associates Inc.，2010：1813-1821.

[35] Zhao H， Zhu P F， Wang P，et al. Hierarchical feature selection with recursive regularization∥Proceedings of the 26th International Joint Conference on Artificial Intelligence. Melbourne，Australia：AAAI Press，2017：3483-3489.

[36] Wang Z， Nie F P， Tian L，et al. Discriminative feature selection via a structured sparse subspace learning module∥Proceedings of the 29th Inter⁃national Conference on International Joint Conferences on Artificial Intelligence. Yokohama，Japan：IJCAI，2020：3009-3015.

[37] Liu X X， Zhou Y C， Zhao H. Robust hierarchical feature selection driven by data and knowledge. Information Sciences，2021，551：341-357.

[38] Friedman M. A comparison of alternative tests of significance for the problem of M rankings. The Annals of Mathematical Statistics，1940，11(1)：86-92.

[39] Demšar J. Statistical comparisons of classifiers over multiple data sets. Journal of Machine Learning Research，2006，7(1)：1-30.

基金资助

国家自然科学基金(62576158)

中国石油大学（北京）克拉玛依校区科研基金(RCYJ2016B⁃03⁃001)

中国石油大学（北京）克拉玛依校区科研基金(XQZX20240032)

克拉玛依科技计划(2020CGZH0009)