属性约简作为粗糙集理论研究的核心内容之一，主旨思想是在保持信息系统分类能力不变的条件下，删除知识库中不必要或者不重要的属性。现有的大多数约简算法是针对静态决策表设计的，对动态决策表约简的算法研究较少。当系统的样本、属性同时动态变化时，需要得到更新后系统的属性约简，已有的静态约简算法在处理动态变化时效率较低、时间消耗巨大，因此，需要进行增量式属性约简算法的研究。

本文主要工作如下：

1.在对常用的四种基于静态数据库的决策表属性约简算法讨论基础上，从约简结果、是否为有效约简以及时间复杂度三个方面对该四种算法进行了对比分析，并指出了其优势和不足。

2.针对样本、属性同时动态变化决策系统，本文在对已有二进制可辨识矩阵的方法优化基础上提出了一种改进的二进制可分辨矩阵的决策表在样本变化时的属性约简算法。该算法利用指针存储对象的方式对决策表进行简化并得到简化后的等价类，根据对应的二进制差别矩阵对新增样本进行了分类，通过属性频率函数计算得到属性约简。并将改进算法与已有约简算法在约简结果、时间和空间复杂度等方面进行比较。实例表明，改进算法简便高效、准确性高，且具有一定的实用性和完备性。

3.针对样本、属性可能同时动态变化交通事故系统原始数据存在大量冗余信息的问题，将改进的二进制矩阵增量式约简算法应用到交通事故分析的属性约简问题上，确定了影响交通事故的关键因素，为交通部门提供了决策支持。

Attribute reduction is one of the core contents of rough set theory. The main idea is to delete unnecessary or unimportant attributes in knowledge while keeping the classification ability of information system unchanged. Most of the existing reduction algorithms are designed for the static decision table, but the algorithm research on the dynamic decision table reduction is less. When the samples and attributes of the system change dynamically at the same time, the attribute reduction of the updated system needs to be obtained. The existing static reduction algorithms are inefficient and time consuming in dealing with the dynamic changes, the research of incremental attribute reduction algorithm is needed.

The main work of this paper is as follows:

1.Based on the discussion of four commonly used decision table attribute reduction algorithms based on static database, this paper makes a comparative analysis of these four algorithms from three aspects of reduction results, whether they are effective or not, and time complexity, and points out their advantages and disadvantages.

2.Aiming at the simultaneous dynamic change of sample and attribute decision system, this paper proposes an improved attribute reduction algorithm for the binary discernible matrix decision table when the sample changes on the basis of optimizing the existing binary discernible matrix method. The algorithm simplifies the decision table by using pointer to store objects and obtains the simplified equivalence class. The new samples are classified according to the corresponding binary differential matrix, and the attribute reduction is obtained by calculating the attribute frequency function. The improved algorithm is compared with the existing reductive algorithm in terms of reduction results, time and space complexity. The example shows that the improved algorithm is simple, efficient and accurate, and has certain practicability and completeness.

  3.In view of the problem that there is a lot of redundant information in the original data of the traffic accident system that the samples and attributes may change dynamically at the same time, the improved binary matrix incremental reduction algorithm is applied to the attribute reduction problem of traffic accident analysis, and the key factors affecting the traffic accident are determined, which provides decision support for the traffic department.

[1]U.M.Fayyad,G. Piatetsky-Shapiro, P Smyth. Knowledge discovery and data mining: towards a unifying framework in: E. Simoudis, J. w. Han, U.M. Fayyads. Proceedings of AAAI Workshop on KDD-96. Portland, USA. 1996.,MenloiPark, California: AAAI Press,1996,82-88.

[2]U.M. Fayyad, G. Piatetsky-Shapiro, P Smyth. The KDD process for extracting useful knowledge form volumes of data. Comunications of the ACM, 1996, 39 (11):27-34.

[3]H. Jiawei, M. K amber. Data Mining: Concepts and Techniques. New York: Morgan Kaufmann Publisher,2000,1-14.

[4]Z. Pawlak. Rough sets. International Journal of Computer and Information Science,1982,11(05):341-356.

[5]侯运炳,潘启新.基于粗糙集决策方法的矿山不确定多属性问题的研究[J].煤炭工程,2005,(04):52-55.

[6]汪江桦,冷伏海.基于粗糙集的新兴技术未来产业影响力评估模型研究[J].情报科学,2013,31(05):123-127.

[7]王磊,李天瑞.一种基于矩阵的知识粒度计算方法[J].模式识别与人工智能,2013,26(05):447-453.

[8]项海飞.基于互信息粒度的相对约简的矩阵计算方法[J].西南师范大学学报(自然科学版),2014,39(03):60-64.

[9]I. Jagielska, C. Matthews, T. Whitfort. An investigation into the application of neural net works, fuzzy logic, genetic algorithms and rough sets to automated knowledge acquisition for classification problems. Neurocomputing 1999,24

(01):37-54.

[10]J. Richard, S. Qiang. Semantics-Preserving Dimensionality Reduction: Rough and Fuzzy-Rough-Based Approaches. IEEE Transactions on knowledge and dataengineering,2004,16(12):1457-1471.     

[11]赛煜,姚红,李林.从数据库中发现知识的研究[J].山东科技,2004,4:57-59. 

[12]仇计清,李晓华,苏连青.机器学习与知识发现在高校公共突发事件智能系统中的应用[J].河北科技大学学报,2012,(02):171-174.

[13]曾志.一种用于知识发现的非精确学习算法[J].东莞理工学院学报,2013,(01):24-29.

[14]Shen J B , Lv Y J . A Rapid Algorithm for Reduction Based on Positive Region Attribute Significance. IEEE, 2010.

[15]S. Li, Y. Feng, X. Guo. An Efficient Algorithm for Rough Sets Positive Region[C]. 2011 International Conference on Transportation, Mechanical, and Electrical Engineering (TMEE), 2011:141l-1414.

[16]黄国顺,曾凡智,陈广义等.基于严凸函数的知识粒度与相对粒度[J].模式识别与人工智能,2013,(10):897-908.

[17]Qi J J . Attribute reduction in formal contexts based on a new discernibility matrix[J]. Journal of Applied Mathematics & Computing, 2009, 30(1):305-314.

[18]李京政,杨习贝,窦慧莉等.重要度集成的属性约简方法研究[J].智能系统学报,2018,(03):414-421.

[19]Y. Lv, H. Liu, J. Jiang. The Method of Attribute Reduction Based on Discernibility Matrix[C]. 2010 International Conference on Computer Application and System Modeling (ICCASM),2010: V1-370-V1-373.

[20]闫鑫,景运革.矩阵增量属性约简算法[J].小型微型计算机系统,2018,(06):1245-1249.

[21]C. Wang. An Attribute Reduction Algorithm in Rough Set Theory Based on Information Entropy[C].2008. International Symposium on Computational Intelligence and Design (SCID), 2008: 3-6.

[22]Z. Xu, W. Qian, L. Huang, B. Yang. Comparative Research of Attribute Reduction based on the New Information Entropy and on Skowron's Discernibility Matrix[C]. 2008 International Symposium on. Computational Intelligence and Design (ISCID), 2008: 129-132.

[23]郑文彬,李进金,余佩秋,等.变精度多粒度粗糙集近似更新的矩阵算法[J].模糊系统与数学,2019,39(11):3140-3145.

[24]蔡娜,张雪峰.基于贝叶斯粗糙集模型的属性约简[J].计算机程,2007,(24):

46-48.

[25]李中然,舒兰.概率粗糙集上下近似集的矩阵运算[J].模糊系统与数学,2015,

29(06):185-190.

[26]Zeng tai, Xiao xia Zhang. The further investigation of variable precision intuitionistic fuzzy rough set model[J]. Internatioan Journal of Machine Learing and Cybernetics,2017,8(05)1565-1584.

[27]Zhang Kai, Zhan Jianming, Wu Wei-Zhi. Novel fuzzy rough set models and corresponding applications to multi-criteria decision-making[J]. Fuzzy Sets and Systems,2020,383:92-126.

[28]Yi tian Xu, Lai sheng Wang, Rui yan Zhang. A dynamic attribute reduction algorithm based on 0-1 integer programming[J]. Knowledge-Based Systems,2011,24(08)1341-1347.

[29]王永生,郑雪峰,锁延锋.一种基于信息粒度的动态属性约简求解算法[J].计算机科学,2015,42(02):213-216.

[30]李成,赵海琳.基于粗糙集的不完备信息系统增量式属性约简[J].测控技术,2018,37(11):50-54.

[31]Pawlak Z. Rough Sets Theory and It’s Applications to Data Analysis[J]. Cybemetnetics&Systems,1998,29(04):661-688.

[26]Pawlak Z. Rough sets [J]. International Journal of Computer and Information Science,1982,11(05):341-356.

[32]苗夺谦,王珏.粗糙集理论中知识粗糙集与信息熵关系的讨论[J].模式识别与人工智能,1998,11(01):34-40.

[33]徐宁,章云,周如旗.基于区分矩阵与区分函数的同元转换约简算法[J].

计算机工程,2013,39(04):39-43.

[34]苗夺谦,李道国.粗糙集理论算法与应用[M].北京:清华大学出版社,2008,4.

[35]徐章艳,钱文彬.基于粗糙集的属性约简和核的快速更新算法研究[D].广西:广西师范大学,2007,29-33.

[36]葛浩,杨传健,李龙澍.一种改进的基于二进制可分辨矩阵属性约简算法[J].计算机技术与发展,2008,18(8):12-16.

[37]支天云,苗夺谦.二进制可分辨矩阵的变换及高效属性约简算法的构造[J].计算机科学,2002,29(2):140-142.

[38]刘高峰,牟廉明.基于改进区分矩阵的决策表增量式属性约简算法[J].计算机工程,2010,36(20):46-48.

[39]申雪芬,谢珺.一种基于相对正域的增量式属性约简算法.[J].广西师范大学学报(自然科学版),2013,31(3):45-50.

[40]革运景.一种基于关系矩阵决策表增量式属性约简算法[J].小型微型计算机系统,2015,5(5):1069-1072.

[41]程妮.一种基于属性变化的增量式简算法[J].山西大同大学学报(自然科学版),2016,32(1):3-7.

[42]Yanyan Yang, Dedang Chen, Hui Wang. Fuzzy rough set based incremental attribute reduction from dynamic data with sample arriving[J]. Applied Soft Computing, 2016,45:129-149.

[43]高晓红,李兴奇.一种基于粗糙集理论的增量式属性约简算法[J].长春大学学报,2018,28(12):16-20.

[45]陈曦,刘晶.基于邻域关系的知识粒度增量式属性约简算法[J].微电子学与计算机,2020,37(10):1-6.

[46]高晓红,李兴奇.基于差别矩阵和重要度的增量式属性约简算法[J].长春大学学报,2020,30(6):15-23.

[47]王珂,朱启兵.一种基于差别矩阵的启发式属性约简算法[J].计算机工程与科学,2008,30(6):73-75.

[48]金华.道路交通事故起因分析与防范对策[J].公路交通科技术,2008(2):

157-159.

[49]易正俊,张业亭,黄华.基于粗糙集的道路交通事故预警算法研究[J].西华大学学报(自然科学版),2007,26(5):26-28.

[50]肖厚国,桑琳,丁守珍,等.基于遗传算法的粗糙集属性约简及其应用[J].计算机工程与应用,2008,44(15):228-230.

[51]Lianjie Dong, Degang Chen. Incremental attribute reduction with rough set for dynamic datasets with simultaneously increasing samples and attributes[J]. International Journal of Machine Learning and Cybernetics,2020,11:1339–1355.