计算机工程 ›› 2012, Vol. 38 ›› Issue (19): 163-166.doi: 10.3969/j.issn.1000-3428.2012.19.042

• 人工智能及识别技术 • 上一篇    下一篇

一种属性约简的探测性贪婪算法

李 旻a,b, 陈卫东a   

  1. (华南师范大学 a. 计算机学院;b. 招生办,广州 510631)
  • 收稿日期:2011-12-02 出版日期:2012-10-05 发布日期:2012-09-29
  • 作者简介:李 旻(1980-),女,工程师、硕士研究生,主研方向:智能算法,数据分析;陈卫东,副教授、博士
  • 基金项目:
    国家自然科学基金资助项目(60973150, 11071089);广东省自然科学基金资助项目(10451063101006313)

Exploration Greedy Algorithm with Attribute Reduction

LI Min   a,b, CHEN Wei-dong  a   

  1. (a. Computer School; b. Admission Department, South China Normal University, Guangzhou 510631, China)
  • Received:2011-12-02 Online:2012-10-05 Published:2012-09-29

摘要: 贪婪算法一旦做出贪婪选择就不能反悔,因此设计简单、执行速度快,但其搜索空间过于狭小,从而降低了贪婪解的精度。针对该问题,提出一种属性约简的探索性贪婪算法,采用前景探测策略提高贪婪解的精度。实验结果表明,该算法在时间略有增加的情况下能提高解的精度。

关键词: 粗糙集, 属性约简, 贪婪算法, 探测策略, 正区域

Abstract: Greedy algorithms make local optimal choices step by step without regretting later, which makes them easy to design and have a high running speed, but the quality of greedy solutions is generally undesirable due to their very small searching space. In this paper, a greedy algorithm with exploration is presented and an exploration strategy is introduced to improve the quality of greedy solution. Experimental results show that the algorithm obviously outperforms the original greedy algorithm in the solution quality with slightly increased running time.

Key words: rough set, attribute reduction, greedy algorithm, exploration strategy, positive region

中图分类号: