[1]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]
Copy

Efficient attribute reduction algorithm for an incomplete decision table based on knowledge granulation

CAAI Transactions on Intelligent Systems[ISSN 1673-4785/CN 23-1538/TP] Volume: 11 Number of periods: 2016 1 Page number: 129-135 Column: 学术论文—知识工程 Public date: 2016-02-25
Title:
Efficient attribute reduction algorithm for an incomplete decision table based on knowledge granulation
Author(s):
QIAO Lijuan1; 2;  XU Zhangyan1; 2;  XIE Xiaojun1; 2;  ZHU Jinhu1; 2;  CHEN Xiaofei2;  LI Juan2
1. Guangxi Key Laboratory of Multi-source Information Mining & Security, Guangxi Normal University, Guilin 541004, China;
2. College of Computer Science and Information Technology, Guangxi Normal University, Guilin 541004, China
Keywords:
attribute reduction; knowledge granularity; incomplete decision table; condition attribute frequency; discernibility matrix; heuristic information
CLC:
TP18
DOI:
10.11992/tis.201506029
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.
Similar References:

Memo

-

Last Update: 1900-01-01

Copyright © CAAI Transactions on Intelligent Systems