基于改进的差别矩阵的快速属性约简算法

doi:10.3778/j.issn.1002-8331.2008.21.028

计算机工程与应用 ›› 2008, Vol. 44 ›› Issue (21): 102-105.DOI: 10.3778/j.issn.1002-8331.2008.21.028

基于改进的差别矩阵的快速属性约简算法

钱进,叶飞跃,徐亚平

江苏技术师范学院计算机科学与工程学院，江苏常州 213001

收稿日期:2008-04-30 修回日期:2008-05-30 出版日期:2008-07-21 发布日期:2008-07-21
通讯作者: 钱进

Fast attribute reduction algorithm based on improved discernibilty matrices

QIAN Jin,YE Fei-yue,XU Ya-ping

Institute of Computer Science and Engineering，Jiangsu Teachers University of Technology，Changzhou，Jiangsu 213001，China

Received:2008-04-30 Revised:2008-05-30 Online:2008-07-21 Published:2008-07-21
Contact: QIAN Jin

摘要/Abstract

摘要： 为了解决基于差别矩阵属性约简的计算效率问题，首先以计数排序的思想设计了一个新的计算U/C的高效算法，其时间复杂度降为O（|C||U|）。其次分析了基于差别矩阵的属性约简算法的不足，提出了改进的差别矩阵的定义，利用快速计算核属性算法生成的核属性和出现频率最多的属性来降低差别矩阵的大小，并设计了基于改进的差别矩阵的快速属性约简算法，证明了该新算法的时间复杂度和空间复杂度分别被降为max（O（|C|²∑_0≤i<j≤k |D_i||D_j|），O（|C||U|））和max（O（|C|∑_0≤i<j≤k |D_i||D_j|），O（|U|））。最后，实例分析与实验结果表明了新算法具有高效性。

关键词: 粗糙集, 属性约简, 差别矩阵, 核属性

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|²∑_0≤i<j≤k|D_i||D_j|），O（|C||U|））and max（O（|C|∑_0≤i<j≤k |D_i||D_j|），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.

Key words: rough set, attribute reduction, discernibility matrices, core attribute

钱进,叶飞跃,徐亚平. 基于改进的差别矩阵的快速属性约简算法[J]. 计算机工程与应用, 2008, 44(21): 102-105.

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.

[1]	代琪，李敏，刘洋，李丽红. 模糊层次商空间的快速属性约简算法[J]. 计算机工程与应用, 2021, 57(4): 55-60.
[2]	高天宇，王庆荣，杨磊. 粗糙集属性依赖度强化的应急数据挖掘模型[J]. 计算机工程与应用, 2021, 57(3): 87-93.
[3]	王庆荣，马辰坤. 面向案例消耗推理的应急物资预测[J]. 计算机工程与应用, 2021, 57(22): 281-287.
[4]	张呈玲，李进金，林艺东. 基于OE-概念格的形式背景属性约简[J]. 计算机工程与应用, 2021, 57(15): 82-89.
[5]	刘玉锋，孙文鑫. 一般多粒度量化软粗糙集模型[J]. 计算机工程与应用, 2021, 57(12): 137-143.
[6]	刘桂枝. 维度变化的不完备混合型数据增量式属性约简[J]. 计算机工程与应用, 2021, 57(12): 161-169.
[7]	张博，贾华宇，马珺. RS-GA神经网络无人机受风情况估计[J]. 计算机工程与应用, 2020, 56(4): 209-213.
[8]	牟恩，张贤勇，姚岳松，邓切. 邻域近似条件熵的特定类属性约简及启发算法[J]. 计算机工程与应用, 2020, 56(24): 175-180.
[9]	张建华，李方方，杨岚. 融合PFS与RS的案例知识供需匹配研究[J]. 计算机工程与应用, 2020, 56(23): 139-145.
[10]	骆公志，梅焘. 监督机制多粒度决策粗糙集模型及应用[J]. 计算机工程与应用, 2020, 56(18): 214-220.
[11]	谢旭明，段隆振，邱桃荣，杨幼凤. 改进量子搜索算法及其在核属性求解上的应用[J]. 计算机工程与应用, 2020, 56(14): 57-61.
[12]	李旭，荣梓景，任艳. 带权决策表的属性约简[J]. 计算机工程与应用, 2020, 56(12): 54-59.
[13]	陈盼盼，林梦雷. 基于包含度的单值中智决策信息系统属性约简[J]. 计算机工程与应用, 2020, 56(12): 175-181.
[14]	任俊1，唐绮雯1，徐怡2，胡善忠2. 大学生贫困资助评定的多粒度粗糙集研究[J]. 计算机工程与应用, 2019, 55(7): 82-86.
[15]	邬阳阳，汤建国. 大数据背景下粗糙集属性约简研究进展[J]. 计算机工程与应用, 2019, 55(6): 31-38.

基于改进的差别矩阵的快速属性约简算法

Fast attribute reduction algorithm based on improved discernibilty matrices

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics