[1]乔丽娟,徐章艳,谢小军,等.基于知识粒度的不完备决策表的属性约简算法[J].智能系统学报编辑部,2016,11(1):129-135.[doi:10.11992/tis.201506029]
QIAO Lijuan,XU Zhangyan,XIE Xiaojun,et al.Efficient attribute reduction algorithm for an incomplete decision table based on knowledge granulation[J].CAAI Transactions on Intelligent Systems,2016,11(1):129-135.[doi:10.11992/tis.201506029]
点击复制
QIAO Lijuan,XU Zhangyan,XIE Xiaojun,et al.Efficient attribute reduction algorithm for an incomplete decision table based on knowledge granulation[J].CAAI Transactions on Intelligent Systems,2016,11(1):129-135.[doi:10.11992/tis.201506029]
基于知识粒度的不完备决策表的属性约简算法
《智能系统学报》编辑部[ISSN 1673-4785/CN 23-1538/TP] 卷:
11
期数:
2016年第1期
页码:
129-135
栏目:
学术论文—知识工程
出版日期:
2016-02-25
- Title:
- Efficient attribute reduction algorithm for an incomplete decision table based on knowledge granulation
- Keywords:
- attribute reduction; knowledge granularity; incomplete decision table; condition attribute frequency; discernibility matrix; heuristic information
- 分类号:
- TP18
- 摘要:
- 知识粒度是属性约简的有效方法,但对于大型的决策表,计算知识粒度过于费时,算法效率不高。在引入粒度差别矩阵后,设计了一个计算粒度差别矩阵中条件属性出现频率的函数,有效地降低粒度差别矩阵的存储空间,根据此函数设计了一个高效属性约简算法。新算法使得时间复杂度与空间复杂度都降为O(K|C||U|)(其中K=max{|Tc(xi)|, xi∈U}和O(|U|)。最后通过实例仿真说明了此算法的高效性和可行性。
- Abstract:
- The use of knowledge granularity is an effective attribute reduction approach. But for a large decision table, computing knowledge granularity is so time-consuming that the algorithm is not efficient for practical use.After the introduction of the discernibility matrix of granularity, a function was designed for calculating the occurrence frequency of condition attributes in the matrix. In this paper, we design an efficient attribute reduction algorithm based on the granularity discernibility matrix. The new algorithm reduces the time and space complexities to O(K|C||U|) (K=max{|Tc(xi)|, xi∈U}) and O(|U|), respectively. The results from our simulation example verify that the proposed algorithm is feasible and highly efficient.
- 参考文献/References:
-
[1] PAWLAK Z, GRZYMALA-BUSSE J, SLOWINSKI R. Rough sets[J]. Communications of the ACM, 1995, 8(1):89-95.
[2] PAWLAK Z. Rough set theory and its applications to data analysis[J]. Cybernetics and systems:an international, 1998, 29(7):661-668.
[3] KRYSZKIEWICZ M. Rough set approach to incomplete information systems[J]. Information sciences, 1998, 112(1-4):39-49.
[4] 钱文彬, 杨炳儒, 徐章艳, 等. 基于不完备决策表的容差类高效求解算法[J]. 小型微型计算机系统, 2013, 34(2):345-350. QIAN Wenbin, YANG Bingru, XU Zhangyan, et al. Efficient algorithm for computing tolerance classes of incomplete decision table[J]. Journal of Chinese computer systems, 2013, 34(2):345-350.
[5] 李秀红, 史开泉. 一种基于知识粒度的不完备信息系统的属性约简算法[J]. 计算机科学, 2006, 33(11):169-170, 199. LI Xiuhong, SHI Kaiquan. A knowledge granulation-based algorithm for attribute reduction under incomplete information systems[J]. Computer science, 2006, 33(11):169-170, 199.
[6] 史先红, 史进玲. 一种基于相对粒度的不完备决策表约简算法[J]. 河南师范大学学报:自然科学版, 2010, 38(4):51-53, 84. SHI Xianhong, SHI Jinling. A reduction algorithm based on relative granularity in incomplete decision tables[J]. Journal of Henan normal university:natural science, 2010, 38(4):51-53, 84.
[7] 张清国, 郑雪峰. 基于知识粒度的不完备决策表的属性约简的矩阵算法[J]. 计算机科学, 2012, 39(2):209-211, 243. ZHANG Qingguo, ZHENG Xuefeng. Discernibility matrix algorithm of attribute reduction based on knowledge granulaion in incomplete decision table[J]. Computer science, 2012, 39(2):209-211, 243.
[8] 张伟, 徐章艳, 王晓宇. 一种结合概率启发信息和知识粒度的属性约简算法[J]. 计算机应用与软件, 2013, 30(7):43-45, 50.ZHANG Wei, XU Zhangyan, WANG Xiaoyu. An attribute reduction algorithm combining probability heuristic information and knowledge granularity[J]. Computer applications and software, 2013, 30(7):43-45, 50.
[9] PAWLAK Z. Rough sets and intelligent data analysis[J]. Information sciences, 2002, 147(1-4):1-12.
[10] 王炜, 徐章艳, 李晓瑜. 不完备决策表中基于对象矩阵属性约简算法[J]. 计算机科学, 2012, 39(4):201-204. WANG Wei, XU Zhangyan, LI Xiaoyu. Attribute reduction algorithm based on object matrix in incomplete decision table[J]. Computer science, 2012, 39(4):201-204.
[11] 舒文豪, 徐章艳, 钱文彬, 等. 一种快速的不完备决策表属性约简算法[J]. 小型微型计算机系统, 2011, 32(9):1867-1871. SHU Wenhao, XU Zhangyan, QIAN Wenbin, et al. Quick attribution reduction algorithm based on incomplete decision table[J]. Journal of Chinese computer systems, 2011, 32(9):1867-1871.
[12] 韩智东, 王志良, 高静. 用差别矩阵思想设计的基于正区域的高效属性约简算法[J]. 小型微型计算机系统, 2011, 32(2):299-304.HAN Zhidong, WANG Zhiliang, GAO Jing. Efficient attribute reduction algorithm based on the idea of discernibility object pair set[J]. Journal of Chinese computer systems, 2011, 32(2):299-304.
[13] 钟珞, 梅磊, 郭翠翠, 等. 粒矩阵属性约简的启发式算法[J]. 小型微型计算机系统, 2011, 32(3):516-520. ZHONG Luo, MEI Lei, GUO Cuicui, et al. Heuristic algorithm for attribute reduction on granular matrix[J]. Journal of Chinese computer systems, 2011, 32(3):516-520.
[14] 唐孝, 舒兰. 基于粒计算的属性约简改进算法[J]. 计算机科学, 2014, 41(11A):313-315, 346. TANG Xiao, SHU Lan. Improved algorithm of attribute reduction based on granular computing[J]. Computer science, 2014, 41(11A):313-315, 346.
[15] 张清国, 郑雪峰. 相容矩阵的高效属性约简算法[J]. 小型微型计算机系统, 2012, 33(9):1944-1947. ZHANG Qingguo, ZHENG Xuefeng. An efficiency attribute reduction algorithm of tolerance matrix[J]. Journal of Chiese computer systems, 2012, 33(9):1944-1947.
[16] 梁吉业, 李德玉. 信息系统中的不确定性与知识获取[M]. 北京:科学出版社, 2005:1-70.
[17] 王炜, 徐章艳, 李晓瑜.不完备决策表中基于对象矩阵属性约简算法[J]. 计算机科学, 2012, 39(4):201-204.WANG Wei, XU Zhangyan, LI Xiaoyu. Attribute reduction algorithm based on object matrix in incomplete decision table[J]. Computer science, 2012, 39(4):201-204.
[18] 周建华, 徐章艳, 章晨光. 一种基于冲突域的不完备决策表属性约简算法[J]. 计算机应用与软件, 2014, 31(3):239-241, 255. ZHOU Jianhua, XU Zhangyan, ZHANG Chenguang. An incomplete decision table attribute reduction algorithm based on conflict region[J]. Computer applications and software, 2014, 31(3):239-241, 255.
- 相似文献/References:
-
[1]伞 冶,叶玉玲.粗糙集理论及其在智能系统中的应用[J].智能系统学报编辑部,2007,2(2):40.
SAN Ye,YE Yu-ling.Rough set theory and its application in the intelligent systems[J].CAAI Transactions on Intelligent Systems,2007,2():40.
[2]马胜蓝,叶东毅.一种带禁忌搜索的粒子并行子群最小约简算法[J].智能系统学报编辑部,2011,6(2):132.
MA Shenglan,YE Dongyi.A minimum reduction algorithm based on parallel particle subswarm optimization with tabu search capability[J].CAAI Transactions on Intelligent Systems,2011,6():132.
[3]杨成东,邓廷权.综合属性选择和删除的属性约简方法[J].智能系统学报编辑部,2013,8(2):183.[doi:10.3969/j.issn.1673-4785.201209056]
YANG Chengdong,DENG Tingquan.An approach to attribute reduction combining attribute selection and deletion[J].CAAI Transactions on Intelligent Systems,2013,8():183.[doi:10.3969/j.issn.1673-4785.201209056]
[4]鞠恒荣,马兴斌,杨习贝,等.不完备信息系统中测试代价敏感的可变精度分类粗糙集[J].智能系统学报编辑部,2014,9(2):219.[doi:10.3969/j.issn.1673-4785.201307010]
JU Hengrong,MA Xingbin,YANG Xibei,et al.Test-cost-sensitive based variable precision classification rough set in incomplete information system[J].CAAI Transactions on Intelligent Systems,2014,9():219.[doi:10.3969/j.issn.1673-4785.201307010]
[5]韦碧鹏,吕跃进,李金海.α优势关系下粗糙集模型的属性约简[J].智能系统学报编辑部,2014,9(2):251.[doi:10.3969/j.issn.1673-4785.201307012]
WEI Bipeng,Lü Yuejin,LI Jinhai.Attribute reduction based on the rough set model under α dominance relation[J].CAAI Transactions on Intelligent Systems,2014,9():251.[doi:10.3969/j.issn.1673-4785.201307012]
[6]钱进,朱亚炎.面向成组对象集的增量式属性约简算法[J].智能系统学报编辑部,2016,11(4):496.[doi:10.11992/tis.201606005]
QIAN Jin,ZHU Yayan.An incremental attribute reduction algorithm for group objects[J].CAAI Transactions on Intelligent Systems,2016,11():496.[doi:10.11992/tis.201606005]
[7]冯丹,黄洋,石云鹏,等.连续型数据的辨识矩阵属性约简方法[J].智能系统学报编辑部,2017,12(3):371.[doi:10.11992/tis.201704032]
FENG Dan,HUANG Yang,SHI Yunpeng,et al.A discernibility matrix-based attribute reduction for continuous data[J].CAAI Transactions on Intelligent Systems,2017,12():371.[doi:10.11992/tis.201704032]
[8]高学义,张楠,童向荣,等.广义分布保持属性约简研究[J].智能系统学报编辑部,2017,12(3):377.[doi:10.11992/tis.201704025]
GAO Xueyi,ZHANG Nan,TONG Xiangrong,et al.Research on attribute reduction using generalized distribution preservation[J].CAAI Transactions on Intelligent Systems,2017,12():377.[doi:10.11992/tis.201704025]
[9]李京政,杨习贝,窦慧莉,等.重要度集成的属性约简方法研究[J].智能系统学报编辑部,2018,13(3):414.[doi:10.11992/tis.201706080]
LI Jingzheng,YANG Xibei,DOU Huili,et al.Research on ensemble significance based attribute reduction approach[J].CAAI Transactions on Intelligent Systems,2018,13():414.[doi:10.11992/tis.201706080]
[10]陈曼如,张楠,童向荣,等.集值信息系统的快速正域约简[J].智能系统学报编辑部,2019,14(3):471.[doi:10.11992/tis.201804059]
CHEN Manru,ZHANG Nan,TONG Xiangrong,et al.Quick positive region reduction in set-valued information systems[J].CAAI Transactions on Intelligent Systems,2019,14():471.[doi:10.11992/tis.201804059]
备注/Memo
收稿日期:2015-06-16;改回日期:。
基金项目:国家自然科学基金资助项目(61262004,61363034,60963008);广西自然科学基金资助项目(2011GXNSFA018163);大学生创新资助项目(201410602099).
作者简介:乔丽娟,女,1988年生,硕士研究生,主要研究方向为数据挖掘及粗糙集理论;徐章艳,男,1972年生,教授,博士,主要研究方向为数据挖掘、模糊集、粗糙集理论。主持国家自然科学基金项目1项,参与国家自然科学基金项目2项,主持省部级科研项目1项;厅局级项目2项;主持校级项目2项。发表学术论文被SCI检索3篇,被EI检索5篇;谢小军,男,1990年生,硕士研究生,主要研究方向为数据挖掘及粗糙集理论。
通讯作者:乔丽娟.E-mail:347671379@qq.com.
更新日期/Last Update:
1900-01-01