Attribution reduction algorithm based on binary discernibility matrix of information entropy

doi:10.3778/j.issn.1002-8331.2010.06.034

Computer Engineering and Applications ›› 2010, Vol. 46 ›› Issue (6): 120-123.DOI: 10.3778/j.issn.1002-8331.2010.06.034

• 数据库、信号与信息处理 • Previous Articles Next Articles

Attribution reduction algorithm based on binary discernibility matrix of information entropy

QIAN Wen-bin¹，XU Zhang-yan¹，HUANG Li-yu¹，YANG Bing-ru²

1.School of Computer Science and Information Engineering，Guangxi Normal University，Guilin，Guangxi 541004，China
2.School of Information Engineering，University of Science and Technology Beijing，Beijing 100083，China

Received:2008-09-02 Revised:2008-11-18 Online:2010-02-21 Published:2010-02-21
Contact: QIAN Wen-bin

基于信息熵的二进制差别矩阵属性约简算法

钱文彬¹，徐章艳¹，黄丽宇¹，杨炳儒²

1.广西师范大学计算机科学与信息工程学院，广西桂林 541004
2.北京科技大学信息工程学院，北京 100083

通讯作者: 钱文彬

Abstract

Abstract: The definition of attribution reduction of simplified binary discernibility matrix is provided.At the same time，it is proved that the above definition of attribution reduction is the same as the definition of attribution reduction based on information entropy.In order to compute simplified binary discernibility matrix，a quick algorithm for simplified decision table is designed，its time complexity is O（|C||U|）.In this condition，a quick attribution reduction algorithm based on simplified binary discernibility matrix of information entropy is designed，the time complexity and space complexity of the new algorithm are max{O（|C||U|），O（|C|²|U/C|²）} and max{O（|C||U/C|²），O（|U|）} respectively.At last，an example is used to illustrate the efficiency of the new algorithm.

Key words: rough set, information entropy, simplified binary discernibility matrix, attribution reduction, algorithm complexity

摘要： 给出一个简化的二进制差别矩阵的属性约简定义，并证明该属性约简的定义与基于信息熵的属性约简的定义是等价的。为求出简化的二进制差别矩阵，设计了一个快速求简化决策表的算法，其时间复杂度为O（|C||U|）。在此基础上，设计了基于信息熵的简化二进制差别矩阵的快速属性约简算法，其时间复杂度和空间复杂度分别为max{O（|C||U|），O（|C|²|U/C|²）}和max{O（|C||U/C|²），O（|U|）}，最后用一个实例说明了新算法的高效性。

关键词: 粗糙集, 信息熵, 简化的二进制差别矩阵, 属性约简, 算法复杂度

CLC Number:

TP301.6

QIAN Wen-bin¹，XU Zhang-yan¹，HUANG Li-yu¹，YANG Bing-ru². Attribution reduction algorithm based on binary discernibility matrix of information entropy[J]. Computer Engineering and Applications, 2010, 46(6): 120-123.

钱文彬¹，徐章艳¹，黄丽宇¹，杨炳儒². 基于信息熵的二进制差别矩阵属性约简算法[J]. 计算机工程与应用, 2010, 46(6): 120-123.

[1]	WANG Peng, YE Xueyi, WANG Tao, QIAN Dingwei. Face Recognition Based on Double Variation and Double Space Local Directional Pattern [J]. Computer Engineering and Applications, 2021, 57(4): 91-99.
[2]	GAO Tianyu, WANG Qingrong, YANG Lei. Data Mining Model Based on Attribute Dependability Enhancement of Rough Set [J]. Computer Engineering and Applications, 2021, 57(3): 87-93.
[3]	WANG Qingrong, MA Chenkun. Forecast of Emergency Supplies for Case Consumption Reasoning [J]. Computer Engineering and Applications, 2021, 57(22): 281-287.
[4]	JIANG Kui, QIU Yuandong, ZHENG Haocheng. ICMPv6 DDoS Attack Detection Method Based on Information Entropy and LSTM [J]. Computer Engineering and Applications, 2021, 57(21): 148-154.
[5]	SONG Shijie, CHEN Kaiyan, ZHANG Yang. Security Evaluation Framework of Deep Learning Side Channel Analysis from Information Entropy [J]. Computer Engineering and Applications, 2021, 57(17): 138-146.
[6]	ZHANG Nianpeng, WU Xu, ZHU Qiang. Entropy-Based Oversampling Framework [J]. Computer Engineering and Applications, 2021, 57(13): 96-101.
[7]	LIU Yufeng, SUN Wenxin. Generalized Multi-granulation Quantization Soft Rough Set Model [J]. Computer Engineering and Applications, 2021, 57(12): 137-143.
[8]	LIU Guizhi. Incremental Attribute Reduction of Incomplete Hybrid Data Based on Dimension Change [J]. Computer Engineering and Applications, 2021, 57(12): 161-169.
[9]	CHEN Jiancu, WANG Yue, ZHU Xiaofei, LI Zhangyu, LIN Zhihang. Wild Animal Video Object Detection Method Combining Multi-feature Map [J]. Computer Engineering and Applications, 2020, 56(7): 221-227.
[10]	LIN Kezheng, ZHANG Yuanming, LI Haotian. Research on HOG Feature Extraction Algorithm Weighted by Information Entropy [J]. Computer Engineering and Applications, 2020, 56(6): 147-152.
[11]	ZHANG Bo, JIA Huayu, MA Jun. Estimation of Air Condition for Unmanned Aerial Vehicle Based on RS-GA Neural Network [J]. Computer Engineering and Applications, 2020, 56(4): 209-213.
[12]	MOU En, ZHANG Xianyong, YAO Yuesong, DENG Qie. Class-Specific Attribute Reduct and Its Heuristic Algorithm of Neighborhood Approximation Condition-Entropy [J]. Computer Engineering and Applications, 2020, 56(24): 175-180.
[13]	ZHANG Jianhua, LI Fangfang, YANG Lan. Research on Matching Supply and Demand of Case Knowledge Based on PFS and RS [J]. Computer Engineering and Applications, 2020, 56(23): 139-145.
[14]	BAI Fengbo, CHANG Lin, WANG Shifan, LI Bin, WANG Yingjie, ZHOU Hong, LIU Yao. Improved Method Study on Extracting Keywords in Chinese Judgment Documents [J]. Computer Engineering and Applications, 2020, 56(23): 153-160.
[15]	LUO Gongzhi, MEI Tao. Multi-granulation Decision-Theoretic Rough Set Method Based on Supervisory Mechanism and Its Application [J]. Computer Engineering and Applications, 2020, 56(18): 214-220.

Attribution reduction algorithm based on binary discernibility matrix of information entropy

基于信息熵的二进制差别矩阵属性约简算法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics