计算机科学 ›› 2021, Vol. 48 ›› Issue (11A): 102-105.doi: 10.11896/jsjkx.210300065

• 智能计算 • 上一篇    下一篇

基于三支决策的增量标签传播算法

辛现伟1, 史春雷1, 韩雨琦1, 薛占熬2, 宋继华1   

  1. 1 北京师范大学人工智能学院 北京100875
    2 河南师范大学计算机与信息工程学院 河南 新乡453007
  • 出版日期:2021-11-10 发布日期:2021-11-12
  • 通讯作者: 宋继华(songjh@bnu.edu.cn)
  • 作者简介:xinxianwei@mail.bnu.edu.cn
  • 基金资助:
    国家自然科学基金项目(61877004,62007004);国家社会科学基金重大项目(18ZDA295);北京师范大学博士学科交叉基金项目(BNUXKJC1925,BNUXKJC2020)

Incremental Tag Propagation Algorithm Based on Three-way Decision

XIN Xian-wei1, SHI Chun-lei1, HAN Yu-qi1, XUE Zhan-ao2, SONG Ji-hua1   

  1. 1 School of Artificial Intelligence,Beijing Normal University,Beijing 100875,China
    2 School of Computer and Information Engineering,Henan Normal University,Xinxiang,Henan 453007,China
  • Online:2021-11-10 Published:2021-11-12
  • About author:XIN Xian-wei,born in 1991,doctoral student.His main research interests include three-way decisions,granular computing and intuitionistic fuzzy set.
    SONG Ji-hua,born in 1963,Ph.D,professor,Ph.D supervisor,is a senior member of China Computer Federation.His main research interests include Chinese information processing and application of computer education.
  • Supported by:
    National Natural Science Foundation of China(61877004,62007004),Major Program of National Social Science Foundation of China(18ZDA295) and Doctoral Interdisciplinary Foundation Project of Beijing Normal University(BNUXKJC1925,BNUXKJC2020).

摘要: 三支决策(Three-Way Decision,3WD)作为一种新的粒计算方法,在处理不确定和不精确问题上具有独特的优势。针对标签传播算法(Label Propagation Algorithm,LPA)在节点更新过程中存在的较高随机不确定性和冗余性问题,提出了基于三支决策的增量标签传播算法(3WD_ILPA)。首先,给出了邻接模糊信息测度的概念和计算方法,并用于生成任意两节点间的概率转移矩阵。然后,将三支决策融入节点的动态更新过程,并把迭代更新后准确率最高的节点逐步增量添加到下一循环过程,直至收敛。此外,给出了3WD_ILPA算法的详细流程。最后,在ABIDE数据集上进行孤独症(Autistic Spectrum Disorder,ASD)识别实验,与传统机器学习、深度学习和迁移学习等方法的对比结果表明,所提方法具有更高的准确率。

关键词: ASD识别, 标签传播, 邻接模糊信息测度, 三支决策, 增量

Abstract: As a new method of granular computing,the three-way decision(3WD) has unique advantages in dealing with uncertain and imprecise problems.Aiming at the high random uncertainty and redundancy of the label propagation algorithm (LPA) in the node update process,an incremental label propagation algorithm based on the three-way decision (3WD_ILPA) is proposed.First,the concept and calculation method of adjacency fuzzy information measure are given and used to generate the probability transfer matrix between any two nodes.Then,the three-way decision is integrated into the dynamic update process,and the node with the highest precision is added to the next periodic iteration until convergence.Furthermore,the algorithm flow of 3WD_ILPA is given in detail.Finally,the autism (ASD) recognition experiment is carried out on the ABIDE data set.By comparing with traditional machine learning,deep learning and transfer learning methods,the results show that the proposed method has higher accuracy.

Key words: Adjacency fuzzy information measure, ASD recognition, Incremental, Tag propagation, Three-way decisions

中图分类号: 

  • TP181
[1]ZADEH L A.Fuzzy sets[J].Information & Control,1965,8(65):338-353.
[2]SHAFER G.A mathematical theory of evidence[M].Princeton University Press,1976.
[3]WILE R.Restructuring lattice theory:An approach based on hierarchies of concepts[M].Dordrecht Boston,1982:445-470.
[4]PAWLAK Z.Rough sets[J].International Journal of Computer &Information Sciences,1982,11(5):341-356.
[5]ATANASSOV K T.Intuitionistic fuzzy sets[J].Fuzzy sets and Systems,1986,20(1):87-96.
[6]CHEN D Y,ZHAO H,ZHANG X.Aided Diagnosis Method for Diseases Based on the Domain Semantic Knowledge Base[J].Journal of Software,2020,31(10):3167-3183.
[7]KHAN M A,JALAL A S.A fuzzy rule based multimodalframework for face sketch-to-photo retrieval[J].Expert Systems with Applications,2019,134:138-152.
[8]YOLCU O C,BAS E,EGRIOGLU E,et al.A new intuitionistic fuzzy functions approach based on hesitation margin for time-series prediction[J].Soft Computing,2020,24(11):8211-8222.
[9]ZHANG W Y,ZHANG L,MAO J L,et al.An AutomatedMethod of Unknown Protocol Fuzzing Test[J].Chinese Journal of Computers,2020,43(4):653-667.
[10]ZHU J,GHAHRAMANI Z B.Learning from labeled and unlabeled data with label propagation:Technical Report CMU-CALD-02-107[R].Carnegie Mellon University,2002.
[11]AHAMDIANFAR I,BOZORG H O,CHU X F.Gradient-based optimizer:A new Metaheuristic optimization algorithm[J].Information Sciences,2020,540:131-159.
[12]PAN Z B,WANG Y K,PAN Y W.A new locally adaptive k-nearest neighbor algorithm based on discrimination class[J].Knowledge-Based Systems,2020,204:106185.
[13]DEY A,PAL A,LONG H V.Fuzzy minimum spanning tree with interval type 2 fuzzy arc length:formulation and a new genetic algorithm[J].Soft computing,2020,24(6):3963-3974.
[14]ZHAI X H,OLIVER A,KOLESNIKOV A,et al.S4l:Self-supervised semi-supervised learning[C]//Proceedings of the IEEE International Conference on Computer Vision.2019:1476-1485.
[15]CHEN C,LIU Y,KUMAR M,et al.Energy consumption mo-delling using deep learning embedded semi-supervised learning[J].Computers & Industrial Engineering,2019,135:757-765.
[16]ZHAO H M,ZHENG J J,DENG W,et al.Semi-supervisedbroad learning system based on manifold regularization and broad network[J].IEEE Transactions on Circuits and Systems I:Regular Papers,2020,67(3):983-994.
[17]ISCEN A,TOLIAS G,AVRITHIS Y,et al.Label propagation for deep semi-supervised learning[C]//Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition.2019:5070-5079.
[18]SEYEDI S A,LOTFI A,MORADI P,et al.Dynamic graph-based label propagation for density peaks clustering[J].Expert Systems with Applications,2019,115:314-328.
[19]ZHANG Y,LIU Y G,LI Q Q,et al.LILPA:a label importance based label propagation algorithm for community detection with application to core drug discovery[J].Neurocomputing,2020,413:107-133.
[20]YAO Y Y.Three-way decisions with probabilistic rough sets.Information Sciences[J].Information Sciences,2010,180(3):341-353.
[21]YAO Y Y.The superiority of three-way decisions in probabilistic rough set models[J].Information Sciences,2011,180(6):1080-1096.
[22]CAMOAGNER A,CABITZA F,CIUCCI D.Three-way classification:ambiguity and abstention in machine learning[C]//International Joint Conference on Rough Sets.Cham:Springer,2019:280-294.
[23]LIANG W,DUAN X D,XU J F.Three-way Filtering Algorithm of Basic Clustering Based on Differential Measurement[J].Chinese Journal of Computer Science,2021,48(1):136-144.
[24]CHENG Y L,ZHANG Q H,WANG G Y,et al.Optimal scale selection and attribute reduction in multi-scale decision tables based on three-way decision[J].Information Sciences,2020,541:36-59.
[25]YE X Q,LIU D,LIANG D C.Three-way Granular Recommendation Algorithm Based on Collaborative Filtering[J].Chinese Journal of Computer Science,2018,45(1):90-96.
[26]KARTEN A,HIRSCH J.Brief report:anomalous neural deactivations and functional connectivity during receptive language in autism spectrum disorder:a functional MRI study[J].Journal of Autism and Developmental Disorders,2015,45(6):1905-1914.
[27]HEINAFELS A S,FRANCO A R,CRADDOCK R C,et al.Identification of autism spectrum disorder using deep learning and the ABIDE dataset[J].NeuroImage-Clinical,2018,17:16-23.
[28]YANG X,ISLAM M S,KHALED A A.Functional connectivity magnetic resonance imaging classification of autism spectrum disorder using the multisite ABIDE dataset[C]//2019 IEEE EMBS International Conference on Biomedical & Health Informatics.2019:1-4.
[29]KUNDA M,ZHOU S,GONG G,et al.Improving multi-site autism classification based on site-dependence minimisation and second-order functional connectivity[J].bioRxiv,2020.
[30]KAZEMINDEJAD A,SOTERO R C.Topological properties of resting-state fMRI functional networks improve machine lear-ning-based autism classification[J].Frontiers in Neuroscience,2019,12:1018.
[1] 刘冬梅, 徐洋, 吴泽彬, 刘倩, 宋斌, 韦志辉.
基于边框距离度量的增量目标检测方法
Incremental Object Detection Method Based on Border Distance Measurement
计算机科学, 2022, 49(8): 136-142. https://doi.org/10.11896/jsjkx.220100132
[2] 何茜, 贺可太, 王金山, 林绅文, 杨菁林, 冯玉超.
比特币实体交易模式分析
Analysis of Bitcoin Entity Transaction Patterns
计算机科学, 2022, 49(6A): 502-507. https://doi.org/10.11896/jsjkx.210600178
[3] 邢云冰, 龙广玉, 胡春雨, 忽丽莎.
基于SVM的类别增量人体活动识别方法
Human Activity Recognition Method Based on Class Increment SVM
计算机科学, 2022, 49(5): 78-83. https://doi.org/10.11896/jsjkx.210400024
[4] 沈少朋, 马洪江, 张智恒, 周相兵, 朱春满, 温佐承.
多元时序上状态转移模式的三支漂移检测
Three-way Drift Detection for State Transition Pattern on Multivariate Time Series
计算机科学, 2022, 49(4): 144-151. https://doi.org/10.11896/jsjkx.210600045
[5] 王志成, 高灿, 邢金明.
一种基于正域的三支近似约简
Three-way Approximate Reduction Based on Positive Region
计算机科学, 2022, 49(4): 168-173. https://doi.org/10.11896/jsjkx.210500067
[6] 张师鹏, 李永忠.
基于降噪自编码器和三支决策的入侵检测方法
Intrusion Detection Method Based on Denoising Autoencoder and Three-way Decisions
计算机科学, 2021, 48(9): 345-351. https://doi.org/10.11896/jsjkx.200500059
[7] 王政, 姜春茂.
一种基于三支决策的云任务调度优化算法
Cloud Task Scheduling Algorithm Based on Three-way Decisions
计算机科学, 2021, 48(6A): 420-426. https://doi.org/10.11896/jsjkx.201000023
[8] 赵志强, 易秀双, 李婕, 王兴伟.
基于GR-AD-KNN算法的IPv6网络DoS入侵检测技术研究
Research on DoS Intrusion Detection Technology of IPv6 Network Based on GR-AD-KNN Algorithm
计算机科学, 2021, 48(6A): 524-528. https://doi.org/10.11896/jsjkx.200500001
[9] 鄂海红, 张田宇, 宋美娜.
基于Web的数据可视化图表渲染优化方法
Web-based Data Visualization Chart Rendering Optimization Method
计算机科学, 2021, 48(3): 119-123. https://doi.org/10.11896/jsjkx.200600038
[10] 梁伟, 段晓东, 徐健锋.
基于差异性度量的基础聚类三支过滤算法
Three-way Filtering Algorithm of Basic Clustering Based on Differential Measurement
计算机科学, 2021, 48(1): 136-144. https://doi.org/10.11896/jsjkx.200700213
[11] 薛占熬, 张敏, 赵丽平, 李永祥.
集对优势关系下多粒度决策粗糙集的可变三支决策模型
Variable Three-way Decision Model of Multi-granulation Decision Rough Sets Under Set-pair Dominance Relation
计算机科学, 2021, 48(1): 157-166. https://doi.org/10.11896/jsjkx.191200175
[12] 刘凌云, 钱辉, 邢红杰, 董春茹, 张峰.
一种基于Q-学习算法的增量分类模型
Incremental Classification Model Based on Q-learning Algorithm
计算机科学, 2020, 47(8): 171-177. https://doi.org/10.11896/jsjkx.190600150
[13] 桑彬彬, 杨留中, 陈红梅, 王生武.
优势关系粗糙集增量属性约简算法
Incremental Attribute Reduction Algorithm in Dominance-based Rough Set
计算机科学, 2020, 47(8): 137-143. https://doi.org/10.11896/jsjkx.190700188
[14] 陈玉金, 徐吉辉, 史佳辉, 刘宇.
基于直觉犹豫模糊集的三支决策模型及其应用
Three-way Decision Models Based on Intuitionistic Hesitant Fuzzy Sets and Its Applications
计算机科学, 2020, 47(8): 144-150. https://doi.org/10.11896/jsjkx.190800041
[15] 张志扬, 张凤荔, 谭琪, 王瑞锦.
基于深度学习的信息级联预测方法综述
Review of Information Cascade Prediction Methods Based on Deep Learning
计算机科学, 2020, 47(7): 141-153. https://doi.org/10.11896/jsjkx.200300130
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!