基数比较法—高效的信息表求核方法

doi:10.3778/j.issn.1002-8331.2009.22.012

计算机工程与应用 ›› 2009, Vol. 45 ›› Issue (22): 34-37.DOI: 10.3778/j.issn.1002-8331.2009.22.012

基数比较法—高效的信息表求核方法

农修德^1，3，徐章艳^1，2

1.广西师范大学计算机科学与信息工程学院，广西桂林 541004
2.北京科技大学信息工程学院，北京 100083
3.南宁师范高等专科学校数学与计算机科学系，广西崇左 532200

收稿日期:2009-02-19 修回日期:2009-03-31 出版日期:2009-08-01 发布日期:2009-08-01
通讯作者: 农修德

Comparing radix method—efficient approach to compute core of information table

NONG Xiu-de ^1，3，XU Zhang-yan^1，2

1.College of Computer Science and Information Technology，Guangxi Normal University，Guilin，Guangxi 541004，China
2.College of Information Engineering，Science and Technology University of Beijing，Beijing 100083，China
3.Department of Mathematics and Computer Science，Nanning Teachers College，Chongzuo，Guangxi 532200，China

Received:2009-02-19 Revised:2009-03-31 Online:2009-08-01 Published:2009-08-01
Contact: NONG Xiu-de

摘要/Abstract

摘要： 目前的求核方法大多基于决策表，基于信息表的报道不多。为此，先寻找理论依据，说明了U/C与U/（C-{a}）的内在关系，证明了U/（C-{a}）≠U/C与真细分的等价性，证明了可以通过比较等价类和它子类的基数来判断是否真细分。然后基于最高位优先基数排序思想，应用正整数有序分拆特性定义了一个用于记录和比较等价类基数的数组，接着设计了一个信息表求核算法，时间复杂度为O（|C|2|U|），空间复杂度为O（|U|）。算法的主要贡献是将求核问题转化为等价类生成过程中的集合基数比较问题。通过实例验证了算法的正确性。

关键词: 粗糙集, 信息表, 等价类, 真细分, 基数比较

Abstract: At present，approaches to compute the core based on decision table are in the overwhelming majority，and based on information table are in the tiny minority.For this reason，beginning with seeking theoretical basis，the inherent correlation between U/C and U/（C-{a}） is explained，and the equivalence relation between U/（C-{a}）≠U/C and real subdivision is discovered，and so is that real subdivision can be judged whether it is true or not by comparing an equivalence class radix with its subclass’s.Then basing on principle of most significant ditital radix sorting，and applying property of positive integer ordered partition，an array used for recording and comparing the radix of equivalence classes is defined，and then an algorithm for computing the core of information table is designed.Its time complexity is O（|C|2|U|），and the space complexity is O（|U|）.The important contribution that it made is the way to get the core is transformed into comparing set radix during the course of generating equivalence classes.Its correctness is verified by the example.

Key words: rough set, information table, equivalence class, real subdivision, comparing radix

农修德^1，3，徐章艳^1，2. 基数比较法—高效的信息表求核方法[J]. 计算机工程与应用, 2009, 45(22): 34-37.

NONG Xiu-de ^1，3，XU Zhang-yan^1，2. Comparing radix method—efficient approach to compute core of information table[J]. Computer Engineering and Applications, 2009, 45(22): 34-37.

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

基数比较法—高效的信息表求核方法

Comparing radix method—efficient approach to compute core of information table

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics