Abstract Rough set theory is widely used in attribute reduction. Computational complexity is one of the factors to limit applicability in reduction techniques, especially in the neighborhood rough set based reduction. In this paper, some mathematical properties of neighborhood rough set model are analyzed. An efficient method is proposed for forward attribute selection strategy based on dependency by using the property that positive region monotonously increases with the amount of attributes. By this algorithm, the comparison times of the samples in computing positive region and neighborhood are reduced, and thus the computational efficiency is improved. The experimental results show that the proposed method is effective.
[1] Chang Liyun, Wang Guoyin, Wu Yu. An Approach for Attribute Reduction and Rule Generation Based on Rough Set Theory. Journal of Software, 1999, 10(11): 1207-1211 (in Chinese) (常犁云,王国胤,吴 渝.一种基于Rough Set理论的属性约简及规则提取方法.软件学报, 1999, 10(11): 1207-1211) [2] Shi Yun, Sun Yufang, Zuo Chun. Spatial Data Classification Based on Rough Set. Journal of Software, 2000, 11(5): 673-678 (in Chinese) (石 云,孙玉芳,左 春.基于Rough Set的空间数据分类方法.软件学报, 2000, 11(5): 673-678) [3] Wilson D R, Martinez T R. Improved Heterogeneous Distance Functions. Journal of Artificial Intelligence Research, 1997, 6(1): 1-34 [4] Hu Qinghua, Yu Daren, Xie Zongxia. Numerical Attribute Reduction Based on Neighborhood Granulation and Rough Approximation. Journal of Software, 2008,19(3): 640-649 (in Chinese) (胡清华,于达仁,谢宗霞.基于邻域粒化和粗糙逼近的数值属性约简.软件学报, 2008, 19(3): 640-649) [5] Hu Qinghua, Yu Daren, Xie Zongxia. Neighborhood Classifiers. Expert Systems with Applications: An International Journal, 2008, 34(2): 866-876 [6] Wang Jue, Wang Ren, Miao Duoqian, et al. Data Enriching Based on Rough Set Theory. Chinese Journal of Computers, 1998, 21(5): 393-400 (in Chinese) (王 珏,王 任,苗夺谦,等.基于Rough Sets理论的“数据浓缩”.计算机学报, 1998, 21(5): 393-400) [7] Miao Duoqian, Hu Guirong. A Heuristic Algorithm for Reduction of Knowledge. Journal of Computer Research and Development, 1999, 36(6): 681-684 (in Chinese) (苗夺谦,胡桂荣.知识约简的一种启发式算法.计算机研究与发展, 1999, 36(6): 681-684) [8] Ye Dongyi. An Improvement to Jelonek's Attribute Reduction Algorithm. Acta Electronica Sinica, 2000, 28(12): 81-82 (in Chinese) (叶东毅.Jelonek属性约简算法的一个改进.电子学报, 2000, 28(12): 81-82) [9] Liu Shaohui, Sheng Qiujian, Wu Bin, et al. Research on Efficient Algorithms for Rough Set Methods. Chinese Journal of Computers, 2003, 26(5): 1-6 (in Chinese) (刘少辉,盛秋戬,吴 斌,等.Rough集的高效算法的研究.计算机学报, 2003, 26(5): 1-6) [10] Xu Zhangyan, Liu Zuopeng, Yang Bingru, et al. A Quick Attribute Reduction Algorithm with Complexity of Max(O(｜C｜｜U｜), O(｜C｜2｜U/C｜)). Chinese Journal of Computers, 2006, 29(3): 391-399 (in Chinese) (徐章艳,刘作鹏,杨炳儒,等.一个复杂度为max(O(｜C｜｜U｜),O(｜C｜2｜U/C｜))的快速属性约简算法.计算机学报, 2006, 29(3): 391-399)
2008, Vol. 21 
