基于层次类别邻域粗糙集的在线流特征选择算法

doi:10.13232/j.cnki.jnju.2022.03.014

南京大学学报(自然科学版) ›› 2022, Vol. 58 ›› Issue (3): 506–518.doi: 10.13232/j.cnki.jnju.2022.03.014

• • 上一篇

基于层次类别邻域粗糙集的在线流特征选择算法

曾艺祥¹^,², 林耀进¹^,²(), 范凯钧¹^,², 曾伯儒¹^,²

^1.闽南师范大学计算机学院，漳州，363000
^2.数据科学与智能应用福建省高校重点实验室，漳州，363000

收稿日期:2022-03-02 出版日期:2022-05-30 发布日期:2022-06-07
通讯作者: 林耀进 E-mail:zzlinyaojin@163.com
基金资助:
国家自然科学基金(62076116);福建省自然科学基金(2021J02049)

Online streaming feature selection method based on hierarchical class neighborhood rough set

Yixiang Zeng¹^,², Yaojin Lin¹^,²(), Kaijun Fan¹^,², Boru Zeng¹^,²

^1.School of Computer Science and Engineering, Minnan Normal University, Zhangzhou, 363000, China
^2.Key Laboratory of Data Science and Intelligence Application, Minnan Normal University, Zhangzhou, 363000, China

Received:2022-03-02 Online:2022-05-30 Published:2022-06-07
Contact: Yaojin Lin E-mail:zzlinyaojin@163.com

摘要/Abstract

摘要：

在开放动态环境中，在线流特征选择是降低特征空间维度的有效方法.现有的在线流特征选择算法能够有效地选择一个较优的特征子集，然而，这些算法忽略了类别中可能存在的层次结构.基于此，提出基于层次类别邻域粗糙集的在线流特征选择算法：首先，在邻域粗糙集中引入层次最近异类的邻域关系，避免邻域粒度的选择，借助层次结构计算特征对标记的层次依赖度，推广邻域粗糙集模型以适应层次类别数据；其次，基于层次依赖度提出三个在线特征评价函数，设计了在线相关选择、在线重要度计算和在线冗余更新的层次特征选择框架；最后，在六个层次类别数据集和八个扁平单标记数据集上的实验表明，提出的算法优于现有最先进的在线流特征选择算法.

关键词: 在线流特征选择, 邻域粗糙集, 层次分类, 层次依赖度

Abstract:

Online streaming feature selection is an effective approach to reduce feature space dimension in open and dynamic environment. Existing streaming feature selection methods can effectively get an optimal feature subset. However，these methods generally ignore a real?world scenario，i.e.，the hierarchical structure of the class. To address this problem，we propose an online streaming feature selection method based on hierarchical class neighborhood rough set. Firstly，we introduce a new neighborhood relation to avoid granularity selection. Then，the hierarchical structure is leveraged to calculate hierarchical dependence，which generalize neighborhood rough set to fit hierarchical classification learning. Three online feature subset evaluation functions based on hierarchical dependence are defined. We design an online hierarchical label streaming feature selection framework including online relevance selection，online importance calculation，and online redundant updation. Finally，empirical experiments are carried out on six hierarchical class and eight single label datasets，showing that the proposed algorithm outperforms other state?of?the?art online streaming feature selection methods.

Key words: online streaming feature selection, neighborhood rough set, hierarchical classification, hierarchical dependence

中图分类号:

TP181

曾艺祥, 林耀进, 范凯钧, 曾伯儒. 基于层次类别邻域粗糙集的在线流特征选择算法[J]. 南京大学学报(自然科学版), 2022, 58(3): 506–518.

Yixiang Zeng, Yaojin Lin, Kaijun Fan, Boru Zeng. Online streaming feature selection method based on hierarchical class neighborhood rough set[J]. Journal of Nanjing University(Natural Sciences), 2022, 58(3): 506–518.

图/表 22

图1

表1

层次结构数据符号说明"

符号	意义
$H$	表示一个树形层次结构
$D$	表示类别集合
$U$	表示样本集合
$H i$	表示第i层的所有类别
$U i$	表示第i层上样本的集合
$U i j$	表示第i层上利用层次信息划分 $U i$ 的第j类样本集合
$H$	表示层次结构中的层数
$C$	表示所有特征的数目

表1

表2

层次结构样本数据示例"

U	C	D
$x 1$	0.1	Class 1
$x 2$	0.2	Class 1
$x 3$	0.4	Class 2
$x 4$	0.6	Class 3
$x 5$	0.8	Class 4
$x 6$	0.75	Class 3
$x 7$	0.81	Class 4
$x 8$	0.6	Class 2
$x 9$	0.82	Class 4

表2

图2

表3

表4

图3

图4

图5

图6

图7

图8

图9

图10

表5

表6

表7

表8

表9

表10

不同层次评价指标下的FF和相应的临界值"

层次评价指标	$F F$	临界值
AP	3.8889	1.98
LCA⁃F1	5.1103
H⁃F1	4.4590
TIE	4.2562

表10

表11

扁平单标记评价指标下的FF和相应的临界值"

扁平单标记评价指标	$F F$	临界值
AP	6.26	1.87

表11

图11

参考文献 24

1	胡清华，王煜，周玉灿，等.大规模分类任务的分层学习方法综述.中国科学：信息科学，2018，48(5)：487-500.
	Hu Q H， Wang Y， Zhou Y C，et al. Review on hierarchical learning methods for large?scale classification task. Scientia Sinica：Informationis，2018，48(5)：487-500.
2	An L， Adeli E， Liu M X，et al. A hierarchical feature and sample selection framework and its application for Alzheimer's disease diagnosis. Scientific Reports，2017(7)：45269.
3	Friedman N. Inferring cellular networks using probabilistic graphical models. Science，2004，303(5659)：799-805.
4	Zhai Y T， Ong Y S， Tsang I W. The emerging "Big Dimensionality". IEEE Computational Intelligence Magazine，2014，9(3)：14-26.
5	Grimaudo L， Mellia M， Baralis E. Hierarchical learning for fine grained internet traffic classification∥2012 8^th International Wireless Communications and Mobile Computing Conference. Limassol，Cyprus：IEEE，2012：463-468.
6	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.
7	Liu X X， Zhao H. Hierarchical feature extraction based on discriminant analysis. Applied Intelligence，2019，49(7)：2780-2792.
8	郝世杰，郭艳蓉，陈涛,等.基于自适应稀疏结构学习的神经精神疾病特征选择方法.模式识别与人工智能，2021，34(4)：311-321.
	Hao S J， Guo Y R， Chen T，et al. Feature selection method for neuropsychiatric disorder based on adaptive sparse structure learning. Pattern Recognition and Artificial Intelligence，2021，34(4)：311-321.
9	Javidi M M， Eskandari S. Online streaming feature selection：A minimum redundancy，maximum significance approach. Pattern Analysis and Applications，2019，22(3)：949-963.
10	Perkins S， Lacker K， Theiler J. Grafting：Fast，incremental feature selection by gradient descent in function space. The Journal of Machine Learning Research，2003(3)：1333-1356.
11	Wu X D， Yu K， Ding W，et al. Online feature selection with streaming features. IEEE Transactions on Pattern Analysis and Machine Intelligence，2013，35(5)：1178-1192.
12	Zhou P， Hu X G， Li P P，et al. Online feature selection for high?dimensional class?imbalanced data. Knowledge?Based Systems，2017(136)：187-199.
13	Lin Y J， Hu Q H， Liu J H，et al. Streaming feature selection for multilabel learning based on fuzzy mutual information. IEEE Transactions on Fuzzy Systems，2017，25(6)：1491-1507.
14	Liu J H， Lin Y J， Li Y W，et al. Online multi?label streaming feature selection based on neighborhood rough set. Pattern Recognition，2018(84)：273-287.
15	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.
16	?lezak D， Synak P， Wróblewski J，et al. Infobright analytic database engine using rough sets and granular computing∥2010 IEEE International Conference on Granular Computing. San Jose，CA，USA：IEEE，2010：432-437.
17	Silla C N， Freitas A A. A survey of hierarchical classification across different application domains. Data Mining and Knowledge Discovery，2011，22(1-2)：31-72.
18	胡清华，于达仁，谢宗霞. 基于邻域粒化和粗糙逼近的数值属性约简. 软件学报，2008，19(3)：640-649.
	Hu Q H， Yu D R， Xie Z X. Numerical attribute reduction based on neighborhood granulation and rough approximation. Journal of Software，2008，19(3)：640-649.
19	毛振宇，窦慧莉，宋晶晶，等.共现邻域关系下的属性约简研究. 南京大学学报(自然科学)，2021，57(1)：150-159.
	Mao Z Y， Dou H L， Song J J，et al. Research on attribute reduction via co?occurrence neighborhood relation. Journal of Nanjing University (Natural Science)，2021，57(1)：150-159.
20	Yu K， Wu X D， Ding W，et al. Scalable and accurate online feature selection for big data. ACM Transactions on Knowledge Discovery from Data，2017，11(2)：16.
21	Zhou P， Hu X G， Li P P，et al. OFS?Density：A novel online streaming feature selection method. Pattern Recognition，2019(86)：48-61.
22	Zhou P， Hu X G， Li P P. A new online feature selection method using neighborhood rough set∥2017 IEEE International Conference on Big Knowledge. Hefei，China：IEEE，2017：135-142.
23	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.
24	Dunn O J. Multiple comparisons among means. Journal of the American Statistical Association，1961，56(293)：52-64.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

名称	样本数	特征数	内部节点	叶子节点	层数
AWA	6405	252	17	10	3
Bridges	108	12	8	6	2
Cifar	50000	512	121	100	2
DD	3020	473	32	27	2
F194	7015	473	202	194	2
VOC	7178	1000	30	88	4

名称	样本数	特征数	类别数
AUTOVAL_B	414	72	5
COLON	62	2000	2
CAR	174	9182	11
GENE2	174	12533	11
GLIOMA	50	4434	4
LEUKEMIA	72	7129	2
SRBCT	83	2308	4
WARPAR10P	103	2400	10

数据集	OSFS	FOSFS	SAOLA	K⁃OFSD	OFSD	OFS⁃A3M	OFS⁃HCRS
Average	0.2924	0.3026	0.2672	0.2912	0.2631	0.3763	0.4873
AWA	0.208	0.2195	0.1781	0.2234	0.1867	0.2512	0.3038
Bridges	0.63	0.63	0.63	0.5533	0.5644	0.6256	0.63
Cifar	0.0674	0.0747	0.0201	0.0925	0.1289	0.2710	0.2735
DD	0.3704	0.3707	0.2929	0.4226	0.3079	0.7054	0.7925
F194	0.2197	0.2537	0.2252	0.1748	0.101	0.0879	0.572
VOC	0.2594	0.2671	0.2568	0.2807	0.2898	0.3165	0.3521

数据集	OSFS	FOSFS	SAOLA	K⁃OFSD	OFSD	OFS⁃A3M	OFS⁃HCRS
Average	2.5305	2.4829	2.6289	2.4754	2.7065	2.2374	1.8454
AWA	3.6868	3.6434	3.7627	3.6593	3.8151	3.4626	3.2272
Bridges	1.0093	1.0093	1.0093	1.1667	1.1389	1	1.0093
Cifar	3.5803	3.539	3.8094	3.4557	3.2936	2.6907	2.6806
DD	1.8759	1.8759	2.2284	1.553	2.3399	0.7779	0.5682
F194	2.2133	2.0418	2.137	2.3074	2.9713	2.9300	1.16
VOC	2.8175	2.7877	2.8268	2.7101	2.68	2.5632	2.4269

数据集	OSFS	FOSFS	SAOLA	K⁃OFSD	OFSD	OFS⁃A3M	OFS⁃HCRS
Average	0.558	0.5652	0.5414	0.5619	0.534	0.6104	0.6795
AWA	0.4643	0.4712	0.4484	0.472	0.4482	0.4948	0.5297
Bridges	0.7852	0.7852	0.7852	0.7444	0.7528	0.7861	0.7852
Cifar	0.3908	0.3967	0.3559	0.4095	0.4352	0.5328	0.5345
DD	0.6338	0.6339	0.5786	0.6781	0.5743	0.8370	0.8834
F194	0.5553	0.5809	0.5635	0.5325	0.4526	0.4517	0.7605
VOC	0.5184	0.5236	0.5165	0.535	0.5411	0.5605	0.5841

基于层次类别邻域粗糙集的在线流特征选择算法

Online streaming feature selection method based on hierarchical class neighborhood rough set

RichHTML

PDF (PC)

摘要/Abstract

引用本文

使用本文

图/表 22

参考文献 24

相关文章 5

Metrics

本文评价

推荐阅读 0

数据集	OSFS	FOSFS	SAOLA	K⁃OFSD	OFSD	OFS⁃A3M	OFS⁃HCRS
Average	0.5985	0.6065	0.5824	0.6087	0.5718	0.6485	0.7135
AWA	0.5391	0.5446	0.5297	0.5426	0.5231	0.5672	0.5966
Bridges	0.8068	0.8068	0.8068	0.7815	0.7852	0.8031	0.8068
Cifar	0.4033	0.4102	0.3651	0.4241	0.4511	0.5515	0.5532
DD	0.6874	0.6874	0.6286	0.7412	0.61	0.8703	0.9053
F194	0.6311	0.6597	0.6438	0.6154	0.5048	0.5117	0.8067
VOC	0.523	0.53	0.5204	0.5471	0.5571	0.5870	0.6125

数据集	OSFS	FOSFS	SAOLA	K⁃OFSD	OFSD	OFS⁃A3M	OFS⁃HCRS
Average	0.6134	0.6844	0.7289	0.7594	0.7400	0.8601	0.9041
AUTOVAL_B	0.7673	0.8075	0.7742	0.4839	0.8401	0.8764	0.8723
COLON	0.7417	0.8708	0.8875	0.8083	0.8542	0.8583	0.9083
CAR	0.5794	0.6686	0.8614	0.9142	0.6878	0.9502	0.9374
GENE2	0.2225	0.1973	0.4466	0.6788	0.5373	0.7137	0.7125
GLIOMA	0.4879	0.7894	0.6462	0.4779	0.7621	0.7003	0.8768
LEUKEMIA	0.9675	0.9833	0.9708	0.9833	0.9667	0.9298	0.9833
SRBCT	0.8534	0.8732	0.9542	0.8466	0.875	0.9625	1
WARPAR10P	0.2875	0.285	0.29	0.8825	0.3975	0.89	0.9425

[1]	刘琼, 代建华, 陈姣龙. 区间值数据的代价敏感特征选择[J]. 南京大学学报(自然科学版), 2021, 57(1): 121-129.
[2]	程永林, 李德玉, 王素格. 基于极大相容块的邻域粗糙集模型[J]. 南京大学学报(自然科学版), 2019, 55(4): 529-536.
[3]	徐智康1，李　旸1，李德玉1，2*. 基于可变最小贝叶斯风险的层次多标签分类方法[J]. 南京大学学报(自然科学版), 2017, 53(6): 1023-.
[4]	贾洪杰1,2丁世飞1,2. 基于邻域粗糙集约减的谱聚类算法[J]. 南京大学学报(自然科学版), 2013, 49(5): 619-627.
[5]	谢娟英*，李楠^1,2，乔子茵¹. 基于邻域粗糙集的不完整决策系统特征选择算法[J]. 南京大学学报(自然科学版), 2011, 47(4): 383-390.