新的基于区分对象集的邻域粗糙集属性约简算法
|
摘要
基于正域的属性约简算法是利用"下近似"思想,仅考虑被正确区分样本数的约简算法。借鉴"上近似"的思想,利用"邻域信息粒"的概念定义了区分对象集,探讨了其基本性质,并提出了基于区分对象集的属性重要度度量及启发式属性约简算法。该约简算法既考虑信息决策表的相对正域,也考虑以核属性为启发信息逐个增加条件属性时对边界域样本的影响。通过实例分析,说明了所提算法的可行性,并且以6个UCI标准数据集为实验对象,与基于正域的属性约简算法进行对比实验。实验结果说明,采用提出的约简算法得到的约简属性集,与基于正域的属性约简算法相比,在进行分类任务时的分类精度能够保持不变或有所提高。
Since the algorithm of attribute reduction based on positive region is based on the thought of lower approximation, it just considers the right distinguished samples. Using the thought of upper approximation and the concept of neighborhood information granule, the distinguished object set with its basic characteristics was designed and analyzed, then the new attribute importance measurement based on distinguished object set and heuristic attribute reduction algorithm was proposed. The proposed algorithm considered both the relative positive region of information decision table and the influence on boundary samples when growing condition attributes. The feasibility of the algorithm was discussed by instance analysis, and the comparative experiments on UCI data set with attribute reduction algorithm based on positive region were carried out. The experimental results show that the proposed attribute reduction algorithm can get better reduction, and the classification precision of sample set can remain the same or has certain improvement.
Since the algorithm of attribute reduction based on positive region is based on the thought of lower approximation, it just considers the right distinguished samples. Using the thought of upper approximation and the concept of neighborhood information granule, the distinguished object set with its basic characteristics was designed and analyzed, then the new attribute importance measurement based on distinguished object set and heuristic attribute reduction algorithm was proposed. The proposed algorithm considered both the relative positive region of information decision table and the influence on boundary samples when growing condition attributes. The feasibility of the algorithm was discussed by instance analysis, and the comparative experiments on UCI data set with attribute reduction algorithm based on positive region were carried out. The experimental results show that the proposed attribute reduction algorithm can get better reduction, and the classification precision of sample set can remain the same or has certain improvement.
引文
[1]PAWLAK Z,SKOWRON A.Rudiments of rough sets[J].Information Sciences,2007,177(1):3-27.
[2]MA X,ZHANG J,YANG H.Heuristic algorithm of attribute reduction based on discernibility matrix[J].Journal of Computer Applications,2010,30(8):1999-2003.(马翔,张继福,杨海峰.基于区分矩阵的启发式属性约简算法[J].计算机应用,2010,30(8):1999-2003.)
[3]YANG C,GE H,LI L.Attribute reduction based on logical operation of boolean discernibility matrix[J].Journal of Sichuan University:Engineering Science Edition,2012,44(2):76-82.(杨传健,葛浩,李龙澍.基于布尔差别矩阵逻辑运算的属性约简[J].四川大学学报:工程科学版,2012,44(2):76-82.)
[4]WANG G,YU H,YANG D.Decision table reduction based on conditional information entropy[J].Chinese Journal of Computers,2002,25(7):759-766.(王国胤,于洪,杨大春.基于条件信息熵的决策表约简[J].计算机学报,2002,25(7):759-766.)
[5]LIANG J,WEI W,QIAN Y.An incremental approach to computation of a core based on conditional entropy[J].Systems Engineering—Theory and Practice,2008,28(4):81-89.(梁吉业,魏巍,钱宇华.一种基于条件熵的增量核求解方法[J].系统工程理论与实践,2008,28(4):81-89.)
[6]QIAN Y,LIANG J,PEDRYCZ W,et al.Positive approximation:an accelerator for attribute reduction in rough set theory[J].Artificial Intelligence,2010,174(9/10):597-618.
[7]LI Y,JIANG Y,WANG X.An improved algorithm for attribute reduction based on rough sets[J].Journal of Computer Applications,2008,28(8):2000-2002.(李永华,蒋芸,王小菊.一种基于Rough集的属性约简的改进算法[J].计算机应用,2008,28(8):2000-2002.)
[8]DENG C,LYU Y,LI J.Efficient attribute reduction algorithm on decision table[J].Computer Engineering and Applications,2009,45(4):152-155.(邓春燕,吕跃进,李金海.决策表的高效属性约简算法[J].计算机工程与应用,2009,45(4):152-155.)
[9]LI J,FAN X,WANG X.An improved attribute reduction algorithm based on importance of atttribute vaule[J].Procedia Engineering,2010,7:356-359.
[10]LIN T,LIU Q,HUANG K.Rough sets,neighborhood systems and approximation[C]//Proceeding of the Fifth International Symposium on Methodologies of Intelligent Systems.New York:North-Holland Publishing Company,1990:130-141.
[11]HU Q.Rough computation models and algorithms for knowledge discovery from heterogenous data[D].Harbin:Harbin Institute of Technology,2008:34.(胡清华.混合数据知识发现的粗糙计算模型和算法[D].哈尔滨:哈尔滨工业大学,2008:34.)
[12]HU Q,ZHAO H,YU D.Efficient symbolic and numerical attribute reduction with neighborhood rough sets[J].Pattern Recognition and Artificial Intelligence,2008,21(6):732-738.(胡清华,赵辉,于达仁.基于邻域粗糙集的符号与数值属性快速约简算法[J].模式识别与人工智能,2008,21(6):732-738.)
[13]HU Q,YU D,XIE Z.Numerical attribute reduction based on neighborhood granulation and rough approximation[J].Journal of Software,2008,19(3):640-649.(胡清华,于达仁,谢宗霞.基于邻域粒化和粗糙逼近的数值属性约简[J].软件学报,2008,19(3):640-649.)
[14]HU Q,YU D,XIE Z.Neighborhood classifiers[J].Expert Systems with Applications:An International Journal,2008,34(2):866-876.
[2]MA X,ZHANG J,YANG H.Heuristic algorithm of attribute reduction based on discernibility matrix[J].Journal of Computer Applications,2010,30(8):1999-2003.(马翔,张继福,杨海峰.基于区分矩阵的启发式属性约简算法[J].计算机应用,2010,30(8):1999-2003.)
[3]YANG C,GE H,LI L.Attribute reduction based on logical operation of boolean discernibility matrix[J].Journal of Sichuan University:Engineering Science Edition,2012,44(2):76-82.(杨传健,葛浩,李龙澍.基于布尔差别矩阵逻辑运算的属性约简[J].四川大学学报:工程科学版,2012,44(2):76-82.)
[4]WANG G,YU H,YANG D.Decision table reduction based on conditional information entropy[J].Chinese Journal of Computers,2002,25(7):759-766.(王国胤,于洪,杨大春.基于条件信息熵的决策表约简[J].计算机学报,2002,25(7):759-766.)
[5]LIANG J,WEI W,QIAN Y.An incremental approach to computation of a core based on conditional entropy[J].Systems Engineering—Theory and Practice,2008,28(4):81-89.(梁吉业,魏巍,钱宇华.一种基于条件熵的增量核求解方法[J].系统工程理论与实践,2008,28(4):81-89.)
[6]QIAN Y,LIANG J,PEDRYCZ W,et al.Positive approximation:an accelerator for attribute reduction in rough set theory[J].Artificial Intelligence,2010,174(9/10):597-618.
[7]LI Y,JIANG Y,WANG X.An improved algorithm for attribute reduction based on rough sets[J].Journal of Computer Applications,2008,28(8):2000-2002.(李永华,蒋芸,王小菊.一种基于Rough集的属性约简的改进算法[J].计算机应用,2008,28(8):2000-2002.)
[8]DENG C,LYU Y,LI J.Efficient attribute reduction algorithm on decision table[J].Computer Engineering and Applications,2009,45(4):152-155.(邓春燕,吕跃进,李金海.决策表的高效属性约简算法[J].计算机工程与应用,2009,45(4):152-155.)
[9]LI J,FAN X,WANG X.An improved attribute reduction algorithm based on importance of atttribute vaule[J].Procedia Engineering,2010,7:356-359.
[10]LIN T,LIU Q,HUANG K.Rough sets,neighborhood systems and approximation[C]//Proceeding of the Fifth International Symposium on Methodologies of Intelligent Systems.New York:North-Holland Publishing Company,1990:130-141.
[11]HU Q.Rough computation models and algorithms for knowledge discovery from heterogenous data[D].Harbin:Harbin Institute of Technology,2008:34.(胡清华.混合数据知识发现的粗糙计算模型和算法[D].哈尔滨:哈尔滨工业大学,2008:34.)
[12]HU Q,ZHAO H,YU D.Efficient symbolic and numerical attribute reduction with neighborhood rough sets[J].Pattern Recognition and Artificial Intelligence,2008,21(6):732-738.(胡清华,赵辉,于达仁.基于邻域粗糙集的符号与数值属性快速约简算法[J].模式识别与人工智能,2008,21(6):732-738.)
[13]HU Q,YU D,XIE Z.Numerical attribute reduction based on neighborhood granulation and rough approximation[J].Journal of Software,2008,19(3):640-649.(胡清华,于达仁,谢宗霞.基于邻域粒化和粗糙逼近的数值属性约简[J].软件学报,2008,19(3):640-649.)
[14]HU Q,YU D,XIE Z.Neighborhood classifiers[J].Expert Systems with Applications:An International Journal,2008,34(2):866-876.