基于限界传递相似度图的FCA概念相似度计算方法  

FCA Concept Similarity Computation Based on Bounded Transitive Similarity Graph

作　　者：黄宏涛[1] 吴忠良[1] 万庆生 黄少滨[2] 

机构地区：[1]河南师范大学河南省高校教育信息工程技术研究中心,新乡453007 [2]哈尔滨工程大学计算机科学与技术学院,哈尔滨150001

出　　处：《计算机科学》2015年第1期285-289,共5页Computer Science

基　　金：国家科技支撑计划项目(2012BAH08B02);河南省科技攻关项目(082400420250;112300410008);河南省教育厅科学技术研究重点项目(13A520508);河南师范大学博士科研启动基金项目(qd12107);青年科学基金项目(2013qk33)资助

摘　　要：使用相似度图计算FCA概念相似度需要构造相似关系的传递闭包,对于复杂问题会导致相似度图规模过大,从而影响相似度评价的效率。为了降低相似度图规模,提出一种基于限界传递相似度图的FCA概念相似度计算方法。该方法首先通过限定传递相似关系的长度来避免构造相似关系的传递闭包,得到的限界传递相似度图中忽略了长度超过界限且对区分FCA概念无用的传递相似关系,能够有效压缩相似度图的规模;然后给出了动态传递相似度计算方法和由限界传递相似度图构建二部图的方法。实验结果表明,使用限界传递相似度图能够在不损失计算结果准确度的情况下有效提高FCA概念相似度计算的效率。It is necessary to construct the transitive closure of similarity relation in the case of computing similarity between FCA concepts by means of similarity graph. This method will lead to large scale similarity graph for complex problem, which may affect the efficiency of similarity evaluation. A bounded transitive similarity graph based FCA concept similarity computing method was proposed in order to reduce the size of similarity graph. This method can avoid constructing the transitive closure of similarity relation by adding a bound on transitive similarity relation, and the bounded transitive similarity graph obtained does not contain the transitive relation whose length beyonds the bound, and this omitted transitive relation is useless to distinguish different FCA concepts, which makes it possible to compress the scale of similarity graph. Then a dynamic transitive similarity computation method and a bipartite graph construction method using bounded transitive similarity graph were giverx Experimental results show that this bounded transitive similarity graph based method improves the efficiency of FCA concept computation effectively without the loss of accuracy.

关 键 词：FCA概念相似度 相似度图 传递相似关系 限界传递 

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