基于NextClosure改进的概念生成算法  

Improved Concepts Generation Algorithm Based on NextClosure

作　　者：林志鸿[1,3] 吴清寿 LIN Zhi-hong;WU Qing-shou(Department of Informational Engineering,Meizhouwan College of Vocational Technology,Putian 351111,China;College of Mathematics and Computer Science,Wuyi University,Wuyishan 354300,China;Key Laboratory of Smart Agriculture and Forestry(Fujian Agriculture and Forestry University),Fujian Province University,Fuzhou 350002,China)

机构地区：[1]湄洲湾职业技术学院信息工程系,福建莆田351111 [2]武夷学院数学与计算机学院,福建武夷山354300 [3]智慧农林福建省高校重点实验室(福建农林大学),福建福州350002

出　　处：《长春师范大学学报》2022年第4期43-50,66,共9页Journal of Changchun Normal University

基　　金：国家社会科学基金项目“基于旅游大数据的国家公园游憩空间适宜性研究”(19XGL010);福建省自然科学基金项目“基于网络表征学习的动态重叠社区的实时发现”(2019J01835);智慧农林福建省高校重点实验室开放课题基金资助项目“武夷岩茶种植环境数据自动采集技术及平台构建研究”(2019LSAF03)。

摘　　要：针对NextClosure算法中交集运算较多导致的时间性能下降问题,提出了一种改进的概念生成算法INCA。引入一个哈希表(元素为字典形式),每个由内涵与外延构成的键值对在表中只能出现1次,以此避免相同内涵重复计算外延的问题。利用集合元素过滤和缩减闭包正规性判断条件的方法,以此降低交集运算的时间复杂度。仿真结果显示,在不同对象数量、不同属性数量和不同属性填充率的三种背景上,INCA算法的平均运行时间分别比NextClosure算法减少了15.4%、50%和20.3%。该结果表明,INCA算法可有效减少集合运算次数并降低交集操作的时间复杂度,且比NextClosure算法能更好地适应大背景下的概念生成。INCA算法在复杂网络分析和推荐系统等领域具有很好的应用前景。Multiple intersection operations in Nextclosure reduce the time performance of the algorithm,in order to settle the problem,this paper proposes an Improved NextClosure Algorithm(INCA)for concept generation.Firstly,a hash table(elements are in dictionary form)is introduced.Each key value pair composed of intension and extension appears only once in the table,so as to avoid the problem of repeated calculation of extension for the same intension.Secondly,the time complexity of intersection operation is reduced by using set element filtering and reducing closure normality judgment conditions.The simulation results show that the average running time of INCA is 15.4%,50%and 20.3%less than that of NextClosure algorithm under different object number,attribute number and attribute filling rate.The results show INCA algorithm can effectively reduce the number of set operations and the time complexity of intersection operations,and it can better adapt to concept generation in large formal context than nextclosure algorithm.Therefore,INCA algorithm has a good application prospect in complex network analysis and recommendation system.

关 键 词：概念格 形式概念分析 NextClosure算法 概念生成 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]