计算机科学 ›› 2018, Vol. 45 ›› Issue (7): 197-201.doi: 10.11896/j.issn.1002-137X.2018.07.034

• 人工智能 • 上一篇    下一篇

基于投票式属性重要度的快速属性约简算法

王蓉1,刘遵仁2,纪俊2   

  1. 青岛大学数据科学与软件工程学院 山东 青岛2660711;
    青岛大学计算机科学技术学院 山东 青岛2660712
  • 收稿日期:2017-05-18 出版日期:2018-07-30 发布日期:2018-07-30
  • 作者简介:王 蓉(1989-),女,硕士生,主要研究方向为粗糙集理论、数据挖掘,E-mail:475985222@qq.com;刘遵仁(1963-),男,博士,硕士生导师,主要研究方向为粗糙集理论、智能计算、数据挖掘等,E-mail:liuzunren@126.com(通信作者);纪 俊(1982-),男,博士,主要研究方向为数据挖掘、大数据应用、转化医学等,E-mail:1120108823@qq.com。
  • 基金资助:
    本文受国家自然科学基金项目(61503208)资助。

Fast Attribute Reduction Algorithm Based on Importance of Voting Attribute

WANG Rong1,LIU Zun-ren2,JI Jun2   

  1. School of Data Science and Software Engineering,Qingdao University,Qingdao,Shandong 266071,China1;
    College of Computer Science and Technology,Qingdao University,Qingdao,Shandong 266071,China2
  • Received:2017-05-18 Online:2018-07-30 Published:2018-07-30

摘要: 作为经典Pawlak粗糙集的扩展,邻域粗糙集能有效处理数值型的数据。但是,因为引入了邻域粒化的概念,所以邻域实数空间下的计算量要比经典离散空间下的计算量大得多。对于邻域粗糙集算法而言,能够有效且快速地找到数据集的属性约简是十分有意义的。为此,针对现有算法中属性重要度定义的不足,首先提出了一种改进的投票式属性重要度,然后进一步提出了一种基于投票式属性重要度的快速属性约简算法。实验证明,与现有算法相比,在保证分类精度的前提下,该算法能更快速地得到属性约简。

关键词: 投票, 域粗糙集, 属性约简, 属性重要度

Abstract: As an extension of the classical Pawlak rough set,neighborhood rough sets can efficiently manipulate numerical data.However,because the concept of neighborhood granulation is introduced,computational complexity in the neighborhood real space is much larger than that in the classical discrete space.For the neighborhood rough set algorithm,it is very meaningful to find the attribute reduction of the data set efficiently and quickly.To this end,an improved definition of voting attribute importance was proposed for the shortcomings of the definition of attribute importance in existing algorithms,then a fast attribute reduction algorithm based onimportance of voting attribute was proposed.Compared with the existing algorithms,the experiment proves that the algorithm can get the attribute reduction more quickly under the premise of ensuring the classification accuracy.

Key words: Attribute reduction, Attribute significance, Neighborhood rough set, Vote

中图分类号: 

  • TP182
[1]PAWLAK Z,SO-WINSKI R.Rough set approach to multi-attribute decision analysis[J].European Journal of Operational Research,1994,72(3):443-459.
[2]ZADEH L A.Towards a theory of fuzzy information granulation and its centrality in human reasoning and fuzzy logic[J].Fuzzy Sets & Systems,1997,90(90):111-127.
[3]LIN T Y.Granular Computing on binary relations I:Data -mining and neighborhood systems[J].Rough Sets in Knowledge Discovery,1998(2):165-166.
[4]HU Q,YU D,LIU J,et al.Neighborhood rough set based hetero-geneous feature subset selection[J].Information Sciences,2008,178(18):3577-3594.
[5]CHEN H,YANG J A,ZHUANG Z Q.The Core of Attributes and Minimal Attributes Reduction in Variable Precision Rough Set[J].Chinese Journal of Computers,2012,35(5):1011-1017.(in Chinese)
陈昊,杨俊安,庄镇泉.变精度粗糙集的属性核和最小属性约简算法[J].计算机学报,2012,35(5):1011-1017.
[6]LOU C,LIU Z R,GUO G Z.Quick Attribute Reduct Algorithm on Neighborhood Rough Set Based on Block Set[J].Computer Science,2014,41(S2):337-339.(in Chinese)
娄畅,刘遵仁,郭功振.基于块集的邻域粗糙集的快速约简算法[J].计算机科学,2014,41(S2):337-339.
[7]XU J C,XU T H,SUN L,et al.Feature Selection for CancerClassification Based on Neighborhood Rough Set and Particle Swarm Optimization[J].Journal of Chinese Computer Systems,2014,35(11):2528-2532.(in Chinese)
徐久成,徐天贺,孙林,等.基于邻域粗糙集和粒子群优化的肿瘤分类特征基因选取[J].小型微型计算机系统,2014,35(11):2528-2532.
[8]MENG Z Q,SHI Z Z.On quick attribute reduction in decision-theoretic rough set models[J].Information Sciences,2016,330 (C):226-244.
[9]LIU F,LI T R.Accelerated Attribute Reduction AlgorithmBased on Probabilistic Rough Sets[J].Computer Science,2016,43(12):63-70.(in Chinese)
刘芳,李天瑞.一种基于概率粗糙集的属性约简加速算法[J].计算机科学,2016,43(12):63-70.
[10]YAN H C,ZHANG F,LIU B X.Rough decision rules extraction and reduction based on granular computing[J].Journal on Communications,2016,37(Z1):30-35.(in Chinese)
阎红灿,张奉,刘保相.基于粒计算的粗决策规则抽取与约简[J].通信学报,2016,37(Z1):30-35.
[11]LIU Y,HUANG W,JIANG Y,et al.Quick attribute reduct algorithm for neighborhood rough set model[J].Information Scien-ces,2014,271(7):65-81.
[12]LIU Z R,WU G F.An Algorithm for Sub-optimal Attribute Reduction in Decision Table Based on Neighborhood Rough Set Model[J].Computer Science,2012,39(10):268-271.(in Chinese)
刘遵仁,吴耿峰.基于邻域粗糙集模型的高维数据集快速约简算法[J].计算机科学,2012,39(10):268-271.
[13]HU Q H,YU D R,XIE Z X.Numerical Attribute Reduction Based on Neighborhood Granulation and Rough Approximation[J].Journal of Software,2008,19(3):640-649.(in Chinese)
胡清华,于达仁,谢宗霞.基于邻域粒化和粗糙逼近的数值属性约简[J].软件学报,2008,19(3):640-649.
[1] 冯雁, 王蕊聪.
基于量子傅里叶变换求和的量子投票协议
Quantum Voting Protocol Based on Quantum Fourier Transform Summation
计算机科学, 2022, 49(5): 311-317. https://doi.org/10.11896/jsjkx.210300058
[2] 陈于思, 艾志华, 张清华.
基于三角不等式判定和局部策略的高效邻域覆盖模型
Efficient Neighborhood Covering Model Based on Triangle Inequality Checkand Local Strategy
计算机科学, 2022, 49(5): 152-158. https://doi.org/10.11896/jsjkx.210300302
[3] 孙林, 黄苗苗, 徐久成.
基于邻域粗糙集和Relief的弱标记特征选择方法
Weak Label Feature Selection Method Based on Neighborhood Rough Sets and Relief
计算机科学, 2022, 49(4): 152-160. https://doi.org/10.11896/jsjkx.210300094
[4] 王子茵, 李磊军, 米据生, 李美争, 解滨.
基于误分代价的变精度模糊粗糙集属性约简
Attribute Reduction of Variable Precision Fuzzy Rough Set Based on Misclassification Cost
计算机科学, 2022, 49(4): 161-167. https://doi.org/10.11896/jsjkx.210500211
[5] 王志成, 高灿, 邢金明.
一种基于正域的三支近似约简
Three-way Approximate Reduction Based on Positive Region
计算机科学, 2022, 49(4): 168-173. https://doi.org/10.11896/jsjkx.210500067
[6] 袁晓磊, 岳晓峰, 方博, 马国元.
基于点对特征及分层全连接聚类的三维目标识别方法
Three-dimensional Target Recognition Method Based on Pair Point Feature and HierarchicalComplete-linkage Clustering
计算机科学, 2021, 48(6A): 127-131. https://doi.org/10.11896/jsjkx.200800035
[7] 李艳, 范斌, 郭劼, 林梓源, 赵曌.
基于k-原型聚类和粗糙集的属性约简方法
Attribute Reduction Method Based on k-prototypes Clustering and Rough Sets
计算机科学, 2021, 48(6A): 342-348. https://doi.org/10.11896/jsjkx.201000053
[8] 季钰翔, 黄建华, 王喆, 郑红, 唐瑞琮.
基于信任度匹配的改进PBFT共识算法
Improved PBFT Consensus Algorithm Based on Trust Matching
计算机科学, 2021, 48(2): 303-310. https://doi.org/10.11896/jsjkx.200500112
[9] 闫凯伦, 张继连.
一种可用于数据和模型分享的模型链
Model Chain for Data and Model Sharing
计算机科学, 2021, 48(2): 311-316. https://doi.org/10.11896/jsjkx.191000126
[10] 曾惠坤, 米据生, 李仲玲.
形式背景中概念及约简的动态更新方法
Dynamic Updating Method of Concepts and Reduction in Formal Context
计算机科学, 2021, 48(1): 131-135. https://doi.org/10.11896/jsjkx.200800018
[11] 李莉.
多赢家投票理论的研究进展
Survey on Multi-winner Voting Theory
计算机科学, 2021, 48(1): 217-225. https://doi.org/10.11896/jsjkx.200600013
[12] 蒲泓全, 崔喆, 刘霆, 饶金涛.
安全性电子投票方案研究综述
Comprehensive Review of Secure Electronic Voting Schemes
计算机科学, 2020, 47(9): 275-282. https://doi.org/10.11896/jsjkx.190900125
[13] 桑彬彬, 杨留中, 陈红梅, 王生武.
优势关系粗糙集增量属性约简算法
Incremental Attribute Reduction Algorithm in Dominance-based Rough Set
计算机科学, 2020, 47(8): 137-143. https://doi.org/10.11896/jsjkx.190700188
[14] 岳晓威, 彭莎, 秦克云.
基于面向对象(属性)概念格的形式背景属性约简方法
Attribute Reduction Methods of Formal Context Based on ObJect (Attribute) Oriented Concept Lattice
计算机科学, 2020, 47(6A): 436-439. https://doi.org/10.11896/JsJkx.191100011
[15] 徐旭东, 张志祥, 张献.
私有二进制协议中变长域的格式挖掘方法
Format Mining Method of Variable-length Domain in Private Binary Protocol
计算机科学, 2020, 47(6A): 556-560. https://doi.org/10.11896/JsJkx.190900035
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!