摘要
原属性约简算法在计算相容关系时,存在大量重复计算,从而导致时间复杂度为O(|C|3|U|2)。针对该问题,基于不完备决策表,提出时间复杂度为O(|U|2)的高效相容矩阵计算算法,在此基础上,设计改进的基于相容矩阵的属性约简算法。通过实例证明,当空间复杂度相同时,改进算法的时间复杂度从原有O(|C|3|U|2)降为O(|C|2|U|2)。
When original attribute reduction algorithm calculates tolerance relation,there is much repeatedly calculating consumption.And this leads to O（｜C｜3｜U｜2） time complexity.Aiming at this problem,based on incomplete decision table,this paper presents a high efficient tolerance matrix computational algorithm whose time complexity is O（｜U｜2）.On that basis,it designs an improved attribute reduction algorithm based on tolerance matrix.Test proves that the time complexity of improved algorithm is reduced from O（｜C｜3｜U｜2） to O（｜C｜2｜U｜2） with the same space complexity.
出处
《计算机工程》
CAS
CSCD
北大核心
2010年第20期25-27,31,共4页
Computer Engineering
基金
国家自然科学基金资助项目(60573059)
北京市重点学科建设基金资助项目(XK100080537)
广西教育厅基金资助项目(200807MS015)
关键词
粗糙集
属性约简
相容关系矩阵
不完备决策表
Rough Set（RS）
attribute reduction
tolerance relation matrix
incomplete decision table
