您的位置：山东大学 -> 科技期刊社 -> 《山东大学学报（理学版）》

山东大学学报（理学版） ›› 2018, Vol. 53 ›› Issue (8): 25-33.doi: 10.6040/j.issn.1671-9352.4.2018.121

• • 上一篇    下一篇

基于决策分类的分块差别矩阵及其求核算法

左芝翠1,2,张贤勇1,2*,莫智文1,2,冯林3   

  1. 1. 四川师范大学 数学与软件科学学院, 四川 成都 610066;2. 四川师范大学 智能信息与量子信息研究所, 四川 成都 610066;3. 四川师范大学 计算机科学学院, 四川 成都 610066
  • 收稿日期:2018-04-15 出版日期:2018-08-20 发布日期:2018-07-11
  • 作者简介:左芝翠(1993— ), 女, 硕士研究生, 研究方向为粗糙集与数据挖掘. E-mail:zhicuizuo@163.com*通信作者简介: 张贤勇(1978— ), 男, 博士后, 教授, 硕导, 研究方向为粗糙集、粒计算、数据挖掘. E-mail:xianyongzh@sina.com
  • 基金资助:
    国家自然科学基金资助项目(61673285,61203285,11671284);四川省科技支撑计划资助项目(2017JY0197,2017JQ0046,2015GZ0079)

Block discernibility matrix based on decision classification and its algorithm finding the core

ZUO Zhi-cui1,2, ZHANG Xian-yong1,2*, MO Zhi-wen1,2, FENG Lin3   

  1. 1. College of Mathematics and Software Science, Sichuan Normal University, Chengdu 610066, Sichuan, China;
    2. Institute of Intelligent Information and Quantum Information, Sichuan Normal University, Chengdu 610066, Sichuan, China;
    3. College of Computer Science, Sichuan Normal University, Chengdu 610066, Sichuan, China
  • Received:2018-04-15 Online:2018-08-20 Published:2018-07-11

PDF (PC)

1031

摘要： 属性约简是粗糙集理论进行数据挖掘的基本途径, 相关算法主要基于核。 核的差别矩阵表示及相关求核计算具有重要意义, 但已有的差别矩阵及其求核算法还具有时空局限性。对此, 依据差别矩阵的稀疏性与大规模性, 提出基于决策分类的分块差别矩阵及其求核算法, 直接地将决策分类信息融入形式结构与问题求解。 首先, 基于决策分类来定义分块差别矩阵, 设计其计算算法; 其次, 基于分块差别矩阵, 确定核的内涵与算法; 最后, 进行实例分析与实验验证, 说明所建方法的有效性。基于决策分类的分块差别矩阵有效地实施了信息提取与维度降低, 相关的求核算法较好地减少了差别矩阵求核算法的时空复杂性。

关键词: 粗糙集, 核, 差别矩阵, 属性约简, 决策分类, 分块差别矩阵

Abstract: Attribute reduction is the fundamental approach of rough set theory to implement data mining, and its relevant algorithms are mainly based on the core. For the core, both its representation of the discernibility matrix and its calculation for finding the core exhibit important significance, but the existing discernibility matrix and its core algorithm have time and space limitations. According to the sparsity and large scale of the discernibility matrix, the block discernibility matrix based on the decision classification and its algorithm finding the core are proposed, and thus the decision classification information is directly applied to the form structure and problem solving. At first, the block discernibility matrix is defined by the decision classification, and its calculation algorithm is achieved. Then, based on the block discernibility matrix, the essence and algorithm of the core are provided. Finally, the proposed methods effectiveness is verified by the example and experiment. The block discernibility matrix based on the decision classification effectively implements the information extraction and dimensionality reduction, so its relevant algorithm finding the core well decreases the time and space complexities of the corresponding algorithm based on the discernibility matrix.

Key words: attribute reduction, core, block discernibility matrix, decision classification, discernibility matrix, rough set

中图分类号: 

  • TP18
[1] PAWLAK Z. Rough sets: theoretical aspects of reasoning about data[M]. Netherlands: Kluwer Academic Publishers, 1991.
[2] 叶东毅, 黄翠微, 赵斌. 粗糙集属性约简的一个贪心算法[J]. 系统工程与电子技术, 2000, 22(09): 63-65. YE Dongyi, HUANG Cuiwei, ZHAO Bin. A greedy algorithm for attribute reduction in rough sets[J]. Systems Engineering and Electronics, 2000, 22(9):63-65.
[3] ZHANG Xianyong, MIAO Duoqian. Three-way attribute reducts[J]. International Journal of Approximate Reasoning, 2017, 88: 401-434.
[4] 程美英, 倪志伟, 朱旭辉. 融合粗糙集和扩散二元萤火虫算法的属性约简方法[J]. 系统工程与电子技术, 2016, 38(10): 2449-2456. CHENG Meiying, NI Zhiwei, ZHU Xuhui. The properties of combining rough sets and diffused dual firefly algorithms[J]. Systems Engineering and Electronics Technology, 2016, 38(10):2449-2456.
[5] 徐怡, 程燕. 基于属性值变化的动态覆盖系统中近似集增量算法[J]. 系统工程与电子技术, 2017, 39(7):1660-1668. XU Yi, CHENG Yan. The approximate set increment algorithm in dynamic coverage system based on property value change[J]. Systems Engineering and Electronics Technology, 2017, 39(7):1660-1668.
[6] 丁棉卫, 张腾飞, 马福民. 基于二进制区分矩阵的增量式属性约简算法[J]. 计算机工程, 2017, 43(1): 201-206. DING Mianwei, ZHANG Tengfei, MA Fumin. The incremental attribute reduction algorithm based on binary discrimination matrix[J]. Computer Engineering, 2017, 43(1): 201-206.
[7] 胡帅鹏, 张清华, 姚龙洋. 一种基于二进制表示的快速求核算法[J]. 计算机科学, 2016, 43(12): 79-83. HU Shuaipeng, ZHANG Qinghua, YAO Longyang. A quick calculation method based on binary representation[J]. Journal of Computer Science, 2016, 43(12): 79-83.
[8] HU Xiaohua, CERCONE N. Learning in relational databases: a rough set approach[J]. Computational Intelligence, 1995, 11(02): 323-337.
[9] 徐章艳, 杨炳儒, 宋威. 一个基于差别矩阵的快速求核算法[J]. 计算机工程与应用, 2006, 42(6): 4-6. XU Zhangyan, YANG Bingru, SONG Wei. A quick accounting method based on differential matrix[J]. Computer Engineering and Application, 2006, 42(6): 4-6.
[10] 徐章艳, 杨炳儒, 蔡卫东, 等. 一个基于正区域的快速求核算法[J]. 系统工程与电子技术, 2006, 28(12): 1902-1905. XU Zhangyan, YANG Bingru, CAI Weidong, et al. A quick accounting method based on positive region[J]. Systems Engineering and Electronics Technology, 2006, 28(12): 1902-1905.
[11] 杨传健, 马丽生, 葛浩. 基于水平划分决策表的核属性求解算法[J]. 计算机工程与应用, 2016, 52(2): 61-64. YANG Chuanjian, MA Lisheng, GE Hao. Algorithm for solving kernel properties of decision table based on horizontal division[J]. Computer Engineering and Application, 2016, 52(2): 61-64.
[12] 陆光, 李想. 一种改进的基于差别矩阵的求核属性算法[J]. 森林工程, 2014, 30(2): 120-124. LU Guang, LI Xiang. An improved attribute the core algorithm based on discernibility matrix[J]. Forest Engineering, 2014, 30(02): 120-124.
[13] 叶东毅, 陈昭炯. 一个新的差别矩阵及其求核方法[J]. 电子学报, 2002, 30(7): 1086-1088. YE Dongyi, CHEN Zhaojiong. A new method of discernibility matrix and its core[J]. Journal of Electronics, 2002, 30(7): 1086-1088.
[14] 高学东, 丁军. 基于简化差别矩阵的属性约简算法[J]. 系统工程理论与实践, 2006, 26(6): 101-107. GAO Xuedong, DING Jun. Attribute reduction algorithm based on simplified discernibility matrix [J]. Journal of Systems Engineering Theory and Practice, 2006, 26(6): 101-107.
[15] 葛浩,李龙澍,杨传健.基于相对分辨能力的属性约简算法[J].系统工程理论与实践,2015, 35(6): 1595-1603. GE Hao, LI Longshu, YANG Chuanjian. Based on the relative resolution ability of attribute reduction algorithm [J]. System Engineering Theory and Practice, 2015, 35(6): 1595-1603.
[16] 朱金虎, 徐章艳, 乔丽娟, 等. 改进的布尔冲突矩阵的高效属性约简算法[J]. 计算机工程与应用, 2017, 53(6):145-149. ZHU Jinhu, XU Zhangyan, QIAO Lijuan, et al. Improved efficient attribute reduction algorithm for Boolean conflict matrix [J]. computer Engineering and Applications, 2017, 53(6):145-149.
[17] 杨涛, 张贤勇, 冯山. 基于差别矩阵的属性集求核算法[J]. 郑州大学学报(理学版), 2018, 50(1): 27-32. YANG Tao, ZHANG Xianyong, FENG Shan. A core algorithm of attribute sets based on the discernibility matrix[J]. Journal of Zhengzhou University(Natural Science Edition), 2018, 50(1): 27-32.
[1] 陈佳,燕慧超,刘有军. 平均框架下多元逼近问题的(s,t)-弱可处理性[J]. 《山东大学学报(理学版)》, 2026, 61(2): 50-57.
[2] 李文焱,李丽红,王洪欣. 基于知识度量的模糊粗糙c-均值算法[J]. 《山东大学学报(理学版)》, 2026, 61(1): 49-64.
[3] 张光旭,姚卫. 基于二型模糊预序的模糊粗糙集模型[J]. 《山东大学学报(理学版)》, 2026, 61(1): 85-93.
[4] 周缪娟,黄韩亮,张纪平,李进金. 基于FT-粗糙集构建知识结构与寻找学习路径方法[J]. 《山东大学学报(理学版)》, 2025, 60(7): 116-130.
[5] 李心如,李令强,贾成昭. 新型多粒度变精度(*,·)-模糊粗糙集[J]. 《山东大学学报(理学版)》, 2025, 60(7): 131-142.
[6] 杨志强,冯山,尹伊,吴慧佳. 一种多因素融合的高效离群点检测方法[J]. 《山东大学学报(理学版)》, 2024, 59(8): 118-126.
[7] 王玲,赵彬. 子Z-Quantale及其性质[J]. 《山东大学学报(理学版)》, 2024, 59(6): 76-83.
[8] 宋苏洋,叶军,曾广财,孙清. 基于优化可辨识矩阵的多粒度粗糙集属性约简算法[J]. 《山东大学学报(理学版)》, 2024, 59(5): 52-62.
[9] 高贺飞,李艳,王硕. 基于邻域粗糙集的偏标记特征选择[J]. 《山东大学学报(理学版)》, 2024, 59(5): 100-113.
[10] 孙嘉睿,杜明晶. 模糊边界剥离聚类[J]. 《山东大学学报(理学版)》, 2024, 59(3): 27-36, 50.
[11] 温欣,李德玉. 基于属性加权的ML-KNN方法[J]. 《山东大学学报(理学版)》, 2024, 59(3): 107-117.
[12] 汪廷华,胡振威,占宏祥. 一种新颖的无监督特征选择方法[J]. 《山东大学学报(理学版)》, 2024, 59(12): 130-140.
[13] 龚何余,舒琴,赵平. 半群$\mathscr{C} \mathscr{F}_{(n, r)}$的幂等元秩[J]. 《山东大学学报(理学版)》, 2024, 59(10): 122-126.
[14] 王茜,张贤勇. 不完备邻域加权多粒度决策理论粗糙集及三支决策[J]. 《山东大学学报(理学版)》, 2023, 58(9): 94-104.
[15] 胡成祥,张莉,黄晓玲,王汇彬. 面向属性变化的动态邻域粗糙集知识更新方法[J]. 《山东大学学报(理学版)》, 2023, 58(7): 37-51.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
版权所有 © 2018 《山东大学学报(理学版)》编辑部　
地址: 山东省济南市山大南路27号山东大学中心校区（250100）　电话: +86-0531-88366917　E-mail: xblxb@sdu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发