Computer Science ›› 2015, Vol. 42 ›› Issue (1): 285-289.doi: 10.11896/j.issn.1002-137X.2015.01.063

Previous Articles     Next Articles

FCA Concept Similarity Computation Based on Bounded Transitive Similarity Graph

HUANG Hong-tao, WU Zhong-liang, WAN Qing-sheng and HUANG Shao-bin   

  • Online:2018-11-14 Published:2018-11-14

Abstract: 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 given.Experimental results show that this bounded transitive similarity graph based method improves the efficiency of FCA concept computation effectively without the loss of accuracy.

Key words: FCA concept similarity,Similarity graph,Transitive similarity relation,Bounded transitivity

[1] Wille R,Yahia S,Nguifo E,et al.Formal Concept Analysis as Applied Lattice Theory[M]∥Concept Lattices and Their Applications.Springer Berlin Heidelberg,2008,4923:42-67
[2] Ning L,Guanyu L,Li S.Using formal concept analysis for maritime ontology building[C]∥2010 International Forum on Information Technology and Applications (IFITA).2010,2:159-162
[3] Sánchez D,Batet M,Isern D,et al.Ontology-based semanticsimilarity:A new feature-based approach[J].Expert Systems with Applications,2012,39(9):7718-7728
[4] Li D,Du J,Yao S.Research on Computer Science Domain Onto-logy Construction and Information Retrieval[J].Knowledge Engineering and Management,2011,123:603-608
[5] Kang X,Li D,Wang S.Research on domain ontology in different granulations based on concept lattice[J].Knowledge-Based Systems,2012,27:152-161
[6] Maarek Y S,Berry D M,Kaiser G E.An information retrieval approach for automatically constructing software libraries[J].IEEE Transactions on Software Engineering,1991,17(8):800-813
[7] Kumar C A.Knowledge discovery in data using formal concept analysis and random projections[J].International Journal of Applied Mathematics and Computer Science,2011,21(4):745-756
[8] Formica A.Semantic web search based on rough sets and fuzzy formal concept analysis[J].Knowledge-Based Systems,2012,26:40-47
[9] Formica A,Missikoff M.Concept similarity in SymOntos:an enterprise ontology management tool[J].The Computer Journal,2002,45(6):583-594
[10] Formica A.Ontology-based concept similarity in formal concept analysis[J].Information Sciences,2006,176(18):2624-2641
[11] Biere A,Cimatti A,Clarke E M,et al.Bounded model checking[J].Advances in computers,2003,58:117-148
[12] Bayati M,Shah D,Sharma M.Maximum weight matching via max-product belief propagation[C]∥Proceedings of the 2005 IEEE International Symposium of Information Theory.2008,54:1763-1767
[13] Yellin D M.Speeding up dynamic transitive closure for bounded degree graphs[J].Acta Informatica,1993,30(4):369-384
[14] Sankowski P,Mucha M.Fast dynamic transitive closure lookahead[J].Algorithmica,2010,56(2):180-197
[15] 舒虎,崇志宏,倪巍伟,等.X-Hop:传递闭包的多跳数压缩存储和快速可达性查询[J].计算机科学,2012(3):144-148

No related articles found!
Full text



[1] LEI Li-hui and WANG Jing. Parallelization of LTL Model Checking Based on Possibility Measure[J]. Computer Science, 2018, 45(4): 71 -75, 88 .
[2] XIA Qing-xun and ZHUANG Yi. Remote Attestation Mechanism Based on Locality Principle[J]. Computer Science, 2018, 45(4): 148 -151, 162 .
[3] LI Bai-shen, LI Ling-zhi, SUN Yong and ZHU Yan-qin. Intranet Defense Algorithm Based on Pseudo Boosting Decision Tree[J]. Computer Science, 2018, 45(4): 157 -162 .
[4] WANG Huan, ZHANG Yun-feng and ZHANG Yan. Rapid Decision Method for Repairing Sequence Based on CFDs[J]. Computer Science, 2018, 45(3): 311 -316 .
[5] SUN Qi, JIN Yan, HE Kun and XU Ling-xuan. Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem[J]. Computer Science, 2018, 45(4): 76 -82 .
[6] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[7] WU Jian-hui, HUANG Zhong-xiang, LI Wu, WU Jian-hui, PENG Xin and ZHANG Sheng. Robustness Optimization of Sequence Decision in Urban Road Construction[J]. Computer Science, 2018, 45(4): 89 -93 .
[8] LIU Qin. Study on Data Quality Based on Constraint in Computer Forensics[J]. Computer Science, 2018, 45(4): 169 -172 .
[9] ZHONG Fei and YANG Bin. License Plate Detection Based on Principal Component Analysis Network[J]. Computer Science, 2018, 45(3): 268 -273 .
[10] SHI Wen-jun, WU Ji-gang and LUO Yu-chun. Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading[J]. Computer Science, 2018, 45(4): 94 -99, 116 .