The Study Of A Formal Concept Calculation Parallel Algorithm Based On Attribute Topology

Formal Concept Analysis(FCA) is a field of applied mathematics, which explains the concept of philosophical in mathematics and hierarchies. Concept, as the basic cell of ideas and knowledge, has become an important research object in the Artificaial Intelligence, and has promote the development of FCA in knowledge discovery, data mining, cognitive computing, classification decisions, and other fields. Attribute Topology(AT) is a novel representation of formal context, combined with information science theory and describes the correlation between attribute-pairs visually. AT is widespread concerned recently. In this parper, based on the theories of FCA and AT, the followings were studied.Firstly, the attribute-sorting methods are discussed. By analyzing the specificity and level limitation of existing attribute-sorting algorithm and referencing the graph and degree of information science, a noval way to measure attribute-pairs' relevancy was introduced. On this ground, an attribute-sorting method based on attribute degree, which can be used to optimize the complexity of concepts computing, was proposed. It makes the sorting result more flexible, in the limitation of holding a clear advantage on searching of attribute's parents.Then, the relationship between AT and concepts computing was deeply discussed. A parallel concept computing algorithm base on AT, named bottom-up decomposition of Attribute Topology(BDAT) was proposed. We have proved that each sub-AT's generation, reduction and concepts computation can be compeleted independently without information transfer. All the concepts obtained by this algorithm are non of pseudo-concepts, non-suplicaiton and non of losing any concepts in the formal context. Under the assumption of infinite number of threads, the efficiency of the algorithm will be greatly enhanced. Under normal circumstances, the load balancing problem was also discussed in the paralle concepts computing.Finally, in the same software and hardware environment, by comparing the elaspsed time for different formal contexts and algrothims, the BDAT can be used to compute concpets accurately, visually and rapidly. When a large-scale formal context which has less objects than attribute, the BDAT is 30% faster than the PCb O. The transpose of formal context could makes the scope of BDAT doubled correspondingly. The parallel algrothim proposed in this paper enrichs the AT theory, and provides the basis for the development in cognitive computing and large-scale formal concept analysis.