基于相似和差异双视角的高维数据属性约简_李元江.pdf

2023-05-10计算机应用,Journal of Computer Applications2023,43(5):1467-1472ISSN 1001-9081CODEN JYIIDUhttp：/基于相似和差异双视角的高维数据属性约简李元江，权金升，谭阳奕，杨田*（智能计算与语言信息处理湖南省重点实验室（湖南师范大学），长沙 410081）（通信作者电子邮箱math_）摘要：针对数据维度过高、冗余信息过多导致维度灾难的问题，提出一种基于异同矩阵的高维属性约简算法（ARSDM）。该算法在区分矩阵的基础上加入对同类样本的相似度衡量，形成对所有样本的综合评估。首先，计算样本在每个属性下的距离，并基于这些距离得到同类相似度和异类差异度；其次，建立异同矩阵，形成对整个数据集的评价；最后，进行属性约简，即将异同矩阵的每一列求和，依次选择值最大的特征进行约简，并将相应样本对的行向量置为零向量。实验结果表明，与经典属性约简算法 DMG（Discernibility Matrix based on Graph theory）、FFRS（Fitting Fuzzy Rough Sets）以及GBNRS（Granular Ball Neighborhood Rough Sets）相比，在分类回归树（CART）分类器下，ARSDM的平均分类准确率分别提高了1.07、6.48、8.92个百分点；在支持向量机（SVM）分类器下，ARSDM的平均分类准确率分别提高了1.96、11.96、12.39个百分点；运行效率上ARSDM优于GBNRS和FFRS。可见，ARSDM能够有效去除冗余信息，提高分类准确率。关键词：异同矩阵；区分矩阵；属性约简；粗糙集；粒计算；数据挖掘中图分类号：TP181；TP311.13 文献标志码：AAttribute reduction for high-dimensional data based on bi-view of similarity and differenceLI Yuanjiang，QUAN Jinsheng，TAN Yangyi，YANG Tian*（Hunan Provincial Key Laboratory of Intelligent Computing and Language Information Processing（Hunan Normal University），Changsha Hunan 410081，China）Abstract:Concerning of the curse of dimensionality caused by too high data dimension and redundant information，a high-dimensional Attribute Reduction algorithm based on Similarity and Difference Matrix（ARSDM）was proposed.In this algorithm，on the basis of discernibility matrix，the similarity measure for samples in the same class was added to form a comprehensive evaluation of all samples.Firstly，the distances of samples under each attribute were calculated，and the similarity of same class and the difference of different classes were obtained based on these distances.Secondly，a similarity and difference matrix was established to form an evaluation of the entire dataset.Finally，attribute reduction was performed，i.e.，each column of the similarity and difference matrix was summed，the feature with the largest value was selected into the reduction in proper order，and the row vector of the corresponding sample pair was set to the zero vector.Experimental results show that compared with the classical attribute reduction algorithms DMG（Discernibility Matrix based on Graph theory），FFRS（Fitting Fuzzy Rough Sets）and GBNRS（Granular Ball Neighborhood Rough Sets），the average classification accuracy of ARSDM is increased by 1.07，6.48，and 8.92 percentage points respectively under the Classification And Regression Tree（CART）classifier，and increased by 1.96，11.96，and 12.39 percentage points under the Support Vector Machine（SVM）classifier.At the same time，ARSDM outperforms GBNRS and FFRS in running efficiency.It can be seen that ARSDM can effectively remove redundant information and improve the classification accuracy.Key words:similarity and difference matrix;discernibility matrix;attribute reduction;rough set;granular computing;data mining0 引言 随着数据规模的不断扩大，尤其是特征数量的急剧增长，维度灾难成为数据挖掘和人工智能的共性问题1。作为主要的数据压缩方法，属性约简能够根据某种评估规则筛选有效的特征，去除冗余特征，从而达到降维数据、简化计算、提高数据质量和模型泛化能力的目的2。粗糙集3为属性约简提供了理论框架，在没有先验知识的情况下4-6，通过知识粒和近似算子计算上下逼近，筛选重文章编号：1001-9081（2023）05-1467-06DOI：10.11772/j.issn.1001-9081.2022081154收稿日期：2022-07-19；修回日期：2022-09-06；录用日期：2022-10-12。基金项目：湖南省自然科学优秀青年基金资助项目（2021JJ20037）；长沙市杰出创新青年培养计划项目（kq1905031）。作者简介：李元江（1999），男，湖北宜昌人，硕士研究生，主要研究方向：数据挖掘、粗糙集理论、机器学习；权金升（2003），男，江苏徐州人，主要研究方向：机器学习；谭阳奕（2002），女，湖南株洲人，主要研究方向：粗糙集；杨田（1984），女，湖南长沙人，副教授，博士，主要研究方向：粒计算与智能信息处理、粗糙集、模糊集理论、拓扑学。第 43 卷计算机应用要特征，进而制定推理规则。基于粗糙集理论，学者们设计了一系列属性约简算法7-11。其中，区分矩阵12是粗糙集理论中的一种属性约简方法，它关于特征的复杂度为线性级别，能够对高维数据进行快速降维13。经典的区分矩阵模型聚焦于异类的样本，将能否区分异类的样本作为评估属性的标准，好的属性往往能够区分更多的异类样本对。但是在以往区分矩阵的研究中，没有基于同类样本对属性形成评价，导致同类样本的信息没有得到充分利用。针对这一问题，本文提出了异同矩阵，通过样本对相似性和差异性的两方面对属性形成综合评估，以充分利用原始数据表的信息，使属性约简结果更加合理可靠。1 相关工作 维度灾难会降低机器学习模型的性能，导致学习算法失效，降维能将高维的原始数据转换为低维数据，同时尽可能保留数据的原始含义，从而使机器学习模型能够有效使用这些数据。属性约简是降维中的重要方法，在粒计算领域，当前研究主要集中于粗糙集理论及其推广理论。由 Pawlak3提出的粗糙集理论是重要的知识粒化模型。粗糙集以等价关系形成知识粒，通过上下逼近划分正域和边界，正域为能准确分类的样本的集合，基于正域的大小制定规则就能挑选出有效特征，这些规则包括依赖度14-15、信息熵16-17、相关族18、区分矩阵12，19等。这些方法在知识推理，机器学习，数据挖掘等邻域发挥着重要的作用20-23。另外，有一些较新颖的属性约简思想被提出，包括：Armanfard 等24提出了一种局部特征选择的方法，区别于经典属性约简方法为所有样本生成一个约简子集，该方法为每个样本区域生成一个约简，从而对后续的学习更有针对性；Wang等25提出了邻域自信息的概念，将粗糙集模型中的上近似纳入特征的衡量标准，能更加全面地考量特征子集；Zhu等26提出了一种多粒度的邻域粗糙集模型，在此基础上得到一种自适应特征选择方法；Yamada等27针对高维生物数据提出了一种非线性特征选择方法；Hu等28将属性的重叠度引入到k-最近邻粗糙集中，提高了约简数据的计算效率和分类性能。以上方法都是基于不同的考量，形成新的属性约简的标准，但它们都面临共同的问题，即对于属性维度的时间复杂度或空间复杂度较高，算法效率较低。而区分矩阵算法对于属性维度的复杂度是线性级别的，因此能够处理更高维度的数据。当前基于经典区分矩阵模型，结合其他模型，衍生出了一系列新的算法：Hu等14用邻域关系替换等价关系，以样本为中心，固定半径形成邻域，进而形成上下逼近；Wang等29在邻域关系的基础上进行改进，提出了邻域区分指数来衡量特征子集的区分能力。另一个方面研究则是对经典集合进行改变：Dubois等30引入模糊集，形成了模糊粗糙集；Jensen等31首次把依赖度应用于模糊粗糙集，提出了新的属性约简算法；Chen等32将区分矩阵的概念应用于模糊粗糙集中。相较于原始模型，这些新的区分矩阵模型作出了基于邻域形成覆盖关系替代划分关系以及用模糊关系替代经典集合关系等改进，旨在更加充分地利用数据信息，其中覆盖关系能够处理连续数据，模糊关系生成的信息粒能包含更多信息。但经典区分矩阵及其衍生模型都没有完全充分利用样本信息，均只使用不同类别的样本信息对属性进行评价，并没有使用到大量的同类样本信息。因此，为了更加充分地挖掘数据信息，异同矩阵的概念被提出。异同矩阵将同类样本相似度纳入对属性的衡量，形成同类相似度和异类差异度两个方面的评价。基于样本对在每个属性下的距离以及类别标签计算同类相似度和异类差异度，进而将所有样本对的信息形成异同矩阵，并提出相应的属性重要度对属性进行评价，通过启发式属性约简算法挑选出重要属性，去除冗余属性，完成属性约简。2 基本概念 2.1粗糙集定义 13 不可区分关系。设R是U上的一个等价关系，U/R表示R的所有等价类构成的集合，xR表示包含元素x U的R等价类。一个知识库就是一个关系系统K=(U，R)，其中U为非空有限集，称为论域，R是U上的一族等价关系。若P R，且P也是一个等价关系，称为P上的不可区分（indi