基于有序差别集的高效属性约简算法

doi:10.3778/j.issn.1002-8331.2008.29.041

计算机工程与应用 ›› 2008, Vol. 44 ›› Issue (29): 146-149.DOI: 10.3778/j.issn.1002-8331.2008.29.041

• 数据库、信号与信息处理 • 上一篇下一篇

基于有序差别集的高效属性约简算法

杨传健¹,葛浩²

1.滁州学院计算机系，安徽滁州 239012
2.滁州学院电子信息工程系，安徽滁州 239012

收稿日期:2008-04-23 修回日期:2008-07-21 出版日期:2008-10-11 发布日期:2008-10-11
通讯作者: 杨传健

Efficient attribute reduction algorithm based on ordered discernibility set

YANG Chuan-jian¹,GE Hao²

1.Department of Computer Science，Chuzhou University，Chuzhou，Anhui 239012，China
2.Department of Electronic and Information Engineering，Chuzhou University，Chuzhou，Anhui 239012，China

Received:2008-04-23 Revised:2008-07-21 Online:2008-10-11 Published:2008-10-11
Contact: YANG Chuan-jian

摘要/Abstract

摘要： 基于可分辨矩阵的属性约简算法需要占用大量的存储空间，可分辨矩阵中许多元素项对约简是多余的；并且随着问题规模的增大，该类算法的效率并不理想。针对上述不足，提出一种基于有序差别集的属性约简算法，该算法不需要创建可分辨矩阵和生成多余的元素项，大大降低了存储量和计算量，从而提高了属性约简效率，使算法的时间复杂度和空间复杂度分别降为max{O（|C|²
|U/C|²），O（|C|²|MsCount|）}和O（|MsCount|）。实验表明该算法是有效的、高效的。

关键词: 粗糙集, 属性约简, 有序差别集, 可分辨矩阵

Abstract: The algorithm for attribute reduction based on discernibility matrix needs a lot of memory space，and many elements of discernibility matrix are not unnecessary for reduction.The efficiency of the algorithm is not good when the scale of problem is very large.For the above deficiency，an attribute reduction algorithm based on ordered discernibility set is put forward.The algorithm is not need to create the discernibility matrix and generate redundant elements，so it can cut down the storing and the computing capacity greatly，and the efficiency of the algorithm is improved.The time complexity and space complexity of the algorithm are cut down to max{O（|C|²|U/C|²），O（|C|²|MsCount|）} and O（|MsCount|）.The experimental results show that the algorithm is effective and efficient.

Key words: rough set, attribute reduction, ordered discernibility set, discernibility matrix

杨传健¹,葛浩². 基于有序差别集的高效属性约简算法[J]. 计算机工程与应用, 2008, 44(29): 146-149.

YANG Chuan-jian¹,GE Hao². Efficient attribute reduction algorithm based on ordered discernibility set[J]. Computer Engineering and Applications, 2008, 44(29): 146-149.

[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.

基于有序差别集的高效属性约简算法

Efficient attribute reduction algorithm based on ordered discernibility set

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics