The Research Of Context Isomorphism Detection Algorithms And Their Application

Concept lattice constructing is a crucial problem in the theory of FCA (Formal Concept Analysis). The traditional algorithms usually build a lattice directly in terms of a context while they cannot use existing lattice to generate a new one. Pursuing this problem, the work team around our supervisor proposes a method of isomorphic generating, of which an elementary problem is how to determine whether two contexts are isomorphic or not. And this is also the central mission of this paper.Context isomorphism detection is quite similar to the well-known problem of graph isomorphism. The difference between them is that, for context isomorphism detecting, the results include not only the answer Yes or No, but also the pair of maps if a context is isomorphic to another. Owing to using matrix to express a context, we are only concerned with the isomorphism detecting arithmetics of graph which expressed by matrix. These arithmetics are mainly divided into two kinds: one is detecting by rank exchange, the other by invariants and some other traits of the graph. The"direct arithmetic"in this paper is using the rank exchange. Yet, it's a high time-complexity, low efficiency method. According to the latter idea, we use some invariants of context to make a primary detection and combine with the rank exchange, which we named"equivalent class arithmetic".The idea of the equivalent class algorithms, is to divide contexts K1 and K2 according to equivalent weight, which includes two parts: objects partition and attributes partition. Objects partition is to divide the objects set into equivalent classes then to order by weight on basis of accounting the weight of each object (row). To ensure the modal uniqueness of the context, we should always preserve the order of the equivalent classes. The same to attributes partition. So, the context is divided into multi sub-contexts by object equivalent class and attribute equivalent class. The only subsequence step is to apply direct arithmetic to the corresponding sub-contexts of K1 and K2.The tests proved that equivalent class arithmetic outgo direct arithmetic in both time-complexity and space-complexity and enhance the efficiency of isomorphism detecting, especially when the context has large attributes and objects the advantage becomes more obvious. Combined with decomposition and reduction of context, it is a...