| 基于改进的差别矩阵的快速属性约简算法 |
| |
| 引用本文： | 钱进,叶飞跃,徐亚平. 基于改进的差别矩阵的快速属性约简算法[J]. 计算机工程与应用, 2008, 44(21): 102-105. DOI: 10.3778/j.issn.1002-8331.2008.21.028 |
| |
| 作者姓名： | 钱进 叶飞跃 徐亚平 |
| |
| 作者单位： | 江苏技术师范学院,计算机科学与工程学院,江苏,常州,213001 |
| |
| 基金项目： | 江苏技术师范学院青年项目 |
| |
| 摘 要： | 为了解决基于差别矩阵属性约简的计算效率问题,首先以计数排序的思想设计了一个新的计算U/C的高效算法,其时间复杂度降为O(|C||U|)。其次分析了基于差别矩阵的属性约简算法的不足,提出了改进的差别矩阵的定义,利用快速计算核属性算法生成的核属性和出现频率最多的属性来降低差别矩阵的大小,并设计了基于改进的差别矩阵的快速属性约简算法,证明了该新算法的时间复杂度和空间复杂度分别被降为max(O|C|2Σ0≤i
|
| 关 键 词： | 粗糙集 属性约简 差别矩阵 核属性 |
| 收稿时间： | 2008-04-30 |
| 修稿时间： | 2008-5-30 |
Fast attribute reduction algorithm based on improved discernibilty matrices |
| |
| QIAN Jin,YE Fei-yue,XU Ya-ping. Fast attribute reduction algorithm based on improved discernibilty matrices[J]. Computer Engineering and Applications, 2008, 44(21): 102-105. DOI: 10.3778/j.issn.1002-8331.2008.21.028 |
| |
| Authors: | QIAN Jin YE Fei-yue XU Ya-ping |
| |
| Affiliation: | Institute of Computer Science and Engineering，Jiangsu Teachers University of Technology，Changzhou，Jiangsu 213001，China |
| |
| Abstract: | In order to solve the efficiency problem of calculating the attribute reduction based on discernibility matrices，a new algorithm based on counting sorting for computing U/C is provided，and its complexity is cut down to O（|C||U|）.Then，the shortcomings of attribution reduction algorithm are analyzed based on discernibility matrices，and the definition of the improved discernibility matrices is presented.Furthermore，core attribute computed by a fast computing core algorithm and an attribute with more frequencies can be used to generate smaller class feature matrices.So a new algorithm based on the improved class feature matrices is proposed，whose worst time complexity and space complexity are cut down to max（O（|C|2∑0≤i<j≤k|Di||Dj|），O（|C||U|））and max（O（|C|∑0≤i<j≤k |Di||Dj|），O（|U|）） respectively.An example is used to illustrate the efficiency of the new algorithm.Experiments show that the new algorithm is efficient for various kinds of data sets. |
| |
| Keywords: | rough set attribute reduction discernibility matrices core attribute |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
| 点击此处可从《计算机工程与应用》浏览原始摘要信息 |
|
点击此处可从《计算机工程与应用》下载免费的PDF全文 |
