Novel attribution reduction algorithm of information entropy

doi:10.3778/j.issn.1002-8331.2009.32.034

Computer Engineering and Applications ›› 2009, Vol. 45 ›› Issue (32): 108-110.DOI: 10.3778/j.issn.1002-8331.2009.32.034

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

Novel attribution reduction algorithm of information entropy

SHU Wen-hao¹，XU Zhang-yan^1，2，YANG Bing-ru²，QIAN Wen-bin¹

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:2009-06-12 Revised:2009-07-24 Online:2009-11-11 Published:2009-11-11
Contact: SHU Wen-hao

一种新的信息熵属性约简算法

舒文豪¹，徐章艳^1，2，杨炳儒²，钱文彬¹

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

通讯作者: 舒文豪

Abstract

Abstract: Firstly，the definition of attribution reduction of discernibility object pair set is provided.At the same time，it is proved that the above definition of attribution reduction is equal to the definition of attribution reduction based on information entropy.In order to compute discernibility object pair set，a quick algorithm for simplified decision table is provided，whose time complexity is O（|C||U|）.On this condition，an efficient attribution reduction algorithm based on information entropy of discernibility object pair set is designed，whose time complexity and space complexity of the new algorithm are O（|C||U|）+O（|C||U/C|²） and O（|U/C|²）+O（|U|）respectively.Finally，an example is used to illustrate the efficiency of the new algorithm.

Key words: rough set, information entropy, discernibility object pair set, attribution reduction, algorithm complexity

摘要： 给出一个区分对象对的属性约简定义，同时证明该属性约简的定义与基于信息熵的属性约简的定义是等价的。为求出区分对象对集，首先给出了一个快速求简化决策表的算法，其时间复杂度为O（|C||U|）。然后在简化决策表的基础上，设计了基于区分对象对集的信息熵属性约简算法，其时间复杂度和空间复杂度分别为O（|C||U|）+O（|C||U/C|²）和O（|U/C|²）+O（|U|），最后用一个实例说明了新算法的高效性。

关键词: 粗糙集, 信息熵, 区分对象对集, 属性约简, 算法复杂度

CLC Number:

TP311

SHU Wen-hao¹，XU Zhang-yan^1，2，YANG Bing-ru²，QIAN Wen-bin¹. Novel attribution reduction algorithm of information entropy[J]. Computer Engineering and Applications, 2009, 45(32): 108-110.

舒文豪¹，徐章艳^1，2，杨炳儒²，钱文彬¹. 一种新的信息熵属性约简算法[J]. 计算机工程与应用, 2009, 45(32): 108-110.

[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.

Novel attribution reduction algorithm of information entropy

一种新的信息熵属性约简算法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics