一种多粒度空间的快速构建方法  

An Efficient Approach for Constructing the Multi-Granularition Spaces

作　　者：赵凡[1,3] 张清华[1,2,3,4] 吴成英 谢秦 王国胤 ZHAO Fan;ZHANG Qing-Hua;WU Cheng-Ying;XIE Qin;WANG Guo-Yin(Chongqing Key Laboratory of Computational Intelligence,Chongqing University of Posts and Telecommunications,Chongqing 400065;Key Laboratory of Tourism Multisource Data Perception and Decision,Ministry of Culture and Tourism,Chongqing 400065;Key Laboratory of Big Data Intelligent Computing,Chongqing University of Posts and Telecommunications,Chongqing 400065;Key Laboratory of Cyberspace Big Data Intelligent Security,Ministry of Education,Chongqing University of Posts and Telecommunications,Chongqing 400065)

机构地区：[1]重庆邮电大学计算智能重庆市重点实验室,重庆400065 [2]旅游多源数据感知与决策技术文化和旅游部重点实验室,重庆400065 [3]重庆邮电大学大数据智能计算重点实验室,重庆400065 [4]重庆邮电大学网络空间大数据智能安全教育部重点实验室,重庆400065

出　　处：《计算机学报》2024年第9期2141-2162,共22页Chinese Journal of Computers

基　　金：国家自然科学基金(No.62276038,No.62221005);重庆市自然科学基金(No.cstc2019jcyj-cxttX0002).

摘　　要：粒计算是模拟人脑多粒度认知模式处理复杂问题的一种方法.模糊商空间理论作为粒计算的一种典型模型,将复杂问题渐进式粒化成为分层递阶的多粒度空间,从而实现层次化的求解.然而,面对海量高维数据,现有模糊商空间模型通过模糊相似关系构建多粒度空间的效率将大幅降低.一方面,模糊相似关系需要计算数据空间中任意两个对象之间的相似性,不利于处理体量大的数据集;另一方面,模糊相似关系包含大量冗余信息,导致后续步骤中存在大量的冗余计算.因此,本文基于2近邻模糊关系,提出了多粒度空间的快速构建方法,在保证面向下游分类任务时性能不下降的前提下,极大地提升了多粒度空间构建效率.首先,基于k近邻算法提出k近邻模糊关系,并分析证明其关键性质;然后,面向多粒度空间构建任务,对k近邻模糊关系进行参数分析,从理论上证明k取2时即可包含数据空间中全部有效信息;随后,定义了最近邻和次近邻两阶段的有效位置数,提出了模糊相似关系有效值和有效位置提取算法,多粒度空间构建效率提升了75%左右.最后,通过在9个UCI数据集、3个UKB数据集、3个图像数据集和3个文本数据集上的相关实验,验证了该算法构建多粒度空间的高效性、正确性以及面向下游分类任务的有效性、稳定性和显著性.Granular computing is a state-of-the-art methodology that simulates the multi-granularition cognitive pattern of the human brain to deal with complex problems.As a typical description of granular computing,fuzzy quotient space theory focuses on gradually granulating complex problems into the hierarchical multi-granularition spaces,thereby implementing hierarchical solution of the complex problems.However,when dealing with massive high-dimensional data,the efficiency of constructing multi-granularition spaces through the fuzzy similarity relations in the existing fuzzy quotient space methods reduces significantly.On one hand,the fuzzy similarity relation is obtained through calculating the similarity among all objects,which is not conducive to processing large datasets;On the other hand,the fuzzy similarity relation contains a large amount of redundant information,which leads to a large number of redundant computation in the subsequent steps.Therefore,based on the 2-nearest neighbor fuzzy relation,an efficient construction approach for constructing multi-granularition spaces is proposed,which greatly improves the efficiency on the premise of ensuring the performance when facing downstream classification tasks.First,based on the k-nearest neighbor algorithm,a k-nearest neighbor fuzzy relation is proposed,and its key properties are discussed and proven.Second,for the multi-granularition spaces construction task,parameter analysis is performed on the k-nearest neighbor fuzzy relation,theoretically proving that when k is taken as k,all effective information in the data space could be included.Then,the number of effective positions in the nearest neighbor and second nearest neighbor phases are defined.And the algorithm for extracting effective values and effective positions of the fuzzy similarity relation is proposed,the efficiency of constructing multigranularition spaces is improved by about 75%.Finally,relevant experiments are conducted on 9 UCI datasets,3 UKB datasets,3 image datasets and 3 text datasets to valida

关 键 词：粒计算 多粒度空间 K近邻 模糊关系 模糊商空间 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]