全部 标题 作者
关键词 摘要

OALib Journal期刊
ISSN: 2333-9721
费用:99美元

查看量下载量

相关文章

更多...

图支配集问题的粗糙集属性约简方法*

DOI: 10.16451/j.cnki.issn1003-6059.201506004, PP. 507-512

Keywords: 粗糙集,信息系统,属性约简,,支配集,信息熵

Full-Text   Cite this paper   Add to My Lib

Abstract:

探讨粗糙集的属性约简和图的支配集问题之间的联系.通过构造信息系统,将粗糙集的属性约简问题与图的支配集问题相联系,从而把图的支配集问题转化为粗糙集的属性约简问题.首先证明图的极小支配集恰是其构造的信息系统的属性约简,然后提出一种基于信息熵的最小支配集算法,最后通过实例验证该算法的可行性和有效性.

References

[1]  Pawlak Z. Rough Sets. International Journal of Computer and Information Sciences, 1982, 11(5): 341-356
[2]  Haynes T W, Hedetniemi S T, Slater P J. Fundamentals of Domina-tion in Graphs. New York, USA: Marcel Dekker, 1998
[3]  Li J J. Topological Methods on the Theory of Covering Generalized Rough Sets. Pattern Recognition and Artificial Intelligence, 2004, 17(1): 7-10 (in Chinese)(李进金.覆盖广义粗集理论中的拓扑学方法.模式识别与人工智能, 2004, 17(1): 7-10)
[4]  Liu J N K, Hua Y X, He Y L. A Set Covering Based Approach to Find the Reduct of Variable Precision Rough Set. Information Scie-nces, 2014, 275: 83-100
[5]  Chen C Y, Li Z G. A Study of Reduction of Attributes and Set Covering Problem. Computer Engineering and Applications, 2004, (2): 44-46, 84 (in Chinese)(陈彩云,李治国.关于属性约简和集合覆盖问题的探讨.计算机工程与应用, 2004, (2): 44-46, 84)
[6]  Chen J K, Li J J. An Application of Rough Sets to Graph Theory. Information Sciences, 2012, 201: 114-127
[7]  Lu G, Zhou M T, Tang Y, et al. A Survey on Exact Algorithms for Dominating Set Related Problems in Arbitrary Graphs. Chinese Journal of Computers, 2010, 33(6): 1073-1087 (in Chinese)(路 纲,周明天,唐 勇,等.任意图支配集精确算法回顾.计算机学报, 2010, 33(6): 1073-1087)
[8]  Yu H, Yang D C. Approach to Solving Attribute Reductions with Ant Colony Optimization. Pattern Recognition and Artificial Intelligence, 2011, 24(2): 176-184 (in Chinese) (于 洪,杨大春.基于蚁群优化的多个属性约简的求解方法.模式识别与人工智能, 2011, 24(2): 176-184)
[9]  Liang J Y, Shi Z Z. The Information Entropy, Rough Entropy and Knowledge Granulation in Rough Set Theory. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 2004, 12(1): 37-46
[10]  Qian Y H, Liang J Y, Pedrycz W, et al. Positive Approximation: An Accelerator for Attribute Reduction in Rough Set Theory. Artificial Intelligence, 2010, 174(9/10): 597-618
[11]  Miao D Q, Hu G R. A Heuristic Algorithm for Reduction of Knowledge. Journal of Computer Research & Development, 1999, 36(6): 681-684 (in Chinese)(苗夺谦,胡桂荣.知识约简的一种启发式算法.计算机研究与发展, 1999, 36(6): 681-684)
[12]  Skowron A, Rauszer C. The Discernibility Matrices and Functions in Information Systems // Sowiński R, ed. Intelligent Decision Support. Dordrecht, The Netherlands: Springer, 1992: 331-362
[13]  S′lezak D. Approximate Entropy Reducts. Fundamenta Informaticae, 2002, 53(3/4): 365-390
[14]  Yao Y Y, Zhao Y. Discernibility Matrix Simplification for Constructing Attribute Reducts. Information Sciences, 2009, 179(7): 867-882
[15]  Wang G Y, Yu H, Yang D C. Decision Table Reduction Based on Conditional Information Entropy. Chinese Journal of Computers, 2002, 25(7): 759-766 (in Chinese)(王国胤,于 洪,杨大春.基于条件信息熵的决策表约简.计算机学报, 2002, 25(7): 759-766)

Full-Text

Contact Us

service@oalib.com

QQ:3279437679

WhatsApp +8615387084133