CAJ | 학술논문

概念格的同构判定问题是机器学习、知识工程等领域的一个研究重点，广泛应用。针对现有同构判定算法时间复杂度较高的问题，提出一种基于节点分类的概念格同构判定算法，以期利用同构判定算法中只需要处理一种类型节点的特性，缩减搜索空间，提高算法效率。首先，算法引入节点分层方法，结合节点的入度和出度，将其分为4种类型，并创建等价类；然后，以对应等价类为基本处理单元，调用EquivalenceClass算法找出节点的映射。仿真实验结果表明，该算法具有较低时间复杂度，在确保算法有效性的基础上提高了处理效率。
개념격적동구판정문제시궤기학습、지식공정등영역적일개연구중점，엄범응용。침대현유동구판정산법시간복잡도교고적문제，제출일충기우절점분류적개념격동구판정산법，이기이용동구판정산법중지수요처리일충류형절점적특성，축감수색공간，제고산법효솔。수선，산법인입절점분층방법，결합절점적입도화출도，장기분위4충류형，병창건등개류；연후，이대응등개류위기본처리단원，조용EquivalenceClass산법조출절점적영사。방진실험결과표명，해산법구유교저시간복잡도，재학보산법유효성적기출상제고료처리효솔。
Concept lattice isomorphism judgment algorithm,as a studying focus in the fields of machine learning and knowledge engineer-ing,has been widely used.With the purpose of solving the problem of excessive time complexity of the current algorithms,in this paper we propose a nodes classification-based algorithm for complete lattice isomorphic judgment.This algorithm aims at reducing the search space and improving the efficiency by taking the advantages of the characteristic of isomorphic judging process,which deals only with one type of the nodes.Firstly,a node stratification method is introduced to the algorithm,which divides the nodes into four types according to their indegree and outdegree,and the equivalence classes are created.Then,the mapping relation is established by taking the corresponding equivalence classes for the basic processing unit and calling the EquivalenceClass algorithm.Result of the simulation experiments shows that the proposed algorithm has a lower time complexity and improves the processing efficiency without weaken its utility.