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

doi:10.3778/j.issn.1002-8331.2009.22.012

Computer Engineering and Applications ›› 2009, Vol. 45 ›› Issue (22): 34-37.DOI: 10.3778/j.issn.1002-8331.2009.22.012

• 研究、探讨 • Previous Articles Next Articles

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

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

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

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

通讯作者: 农修德

Abstract

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

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

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

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

[1]	GAO Tianyu, WANG Qingrong, YANG Lei. Data Mining Model Based on Attribute Dependability Enhancement of Rough Set [J]. Computer Engineering and Applications, 2021, 57(3): 87-93.
[2]	WANG Qingrong, MA Chenkun. Forecast of Emergency Supplies for Case Consumption Reasoning [J]. Computer Engineering and Applications, 2021, 57(22): 281-287.
[3]	LIU Yufeng, SUN Wenxin. Generalized Multi-granulation Quantization Soft Rough Set Model [J]. Computer Engineering and Applications, 2021, 57(12): 137-143.
[4]	LIU Guizhi. Incremental Attribute Reduction of Incomplete Hybrid Data Based on Dimension Change [J]. Computer Engineering and Applications, 2021, 57(12): 161-169.
[5]	ZHANG Bo, JIA Huayu, MA Jun. Estimation of Air Condition for Unmanned Aerial Vehicle Based on RS-GA Neural Network [J]. Computer Engineering and Applications, 2020, 56(4): 209-213.
[6]	MOU En, ZHANG Xianyong, YAO Yuesong, DENG Qie. Class-Specific Attribute Reduct and Its Heuristic Algorithm of Neighborhood Approximation Condition-Entropy [J]. Computer Engineering and Applications, 2020, 56(24): 175-180.
[7]	ZHANG Jianhua, LI Fangfang, YANG Lan. Research on Matching Supply and Demand of Case Knowledge Based on PFS and RS [J]. Computer Engineering and Applications, 2020, 56(23): 139-145.
[8]	LUO Gongzhi, MEI Tao. Multi-granulation Decision-Theoretic Rough Set Method Based on Supervisory Mechanism and Its Application [J]. Computer Engineering and Applications, 2020, 56(18): 214-220.
[9]	XIE Xuming, DUAN Longzhen, QIU Taorong, YANG Youfeng. Improved Quantum Search Algorithm and Its Application on Computation of Core [J]. Computer Engineering and Applications, 2020, 56(14): 57-61.
[10]	LI Xu, RONG Zijing, REN Yan. Attribute Reduction on Weighted Decision Table [J]. Computer Engineering and Applications, 2020, 56(12): 54-59.
[11]	CHEN Panpan, LIN Menglei. Attributes Reduction of Single Valued Neutrosophic Decision Information System Based on Inclusion Degree [J]. Computer Engineering and Applications, 2020, 56(12): 175-181.
[12]	REN Jun1, TANG Qiwen1, XU Yi2, HU Shanzhong2. Research on Multi Granularity Rough Set for University Students’ Poverty Support Evaluation [J]. Computer Engineering and Applications, 2019, 55(7): 82-86.
[13]	WU Yangyang, TANG Jianguo. Research Progress of Attribute Reduction Based on Rough Set in Context of Big Data [J]. Computer Engineering and Applications, 2019, 55(6): 31-38.
[14]	QI Meilan, LI Xiaonan. Matroidal Structure Based on Set-Valued Mapping and Its Relationship with Covering Rough Sets [J]. Computer Engineering and Applications, 2019, 55(6): 50-56.
[15]	YANG Zhen, GENG Xiuli. Research on Mining Association Rules Based on Multi-Granularity Attribute Reduction [J]. Computer Engineering and Applications, 2019, 55(6): 133-139.

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

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics