Research on Parallel Attribute Exploration Algorithm Based on Unrelated Attribute and Intent Sets

The attribute exploration algorithm is an important knowledge discovery tool for obtaining the stem basis and intent of a given formal context in formal concept analysis. However, when the scale of the formal context is large, the traditional attribute exploration algorithm and the improved attribute exploration algorithm still traverse the attribute sets in the lexicographical order, which leads to the calculation process of the algorithm is too time-consuming. It seriously hinders the promotion and application of the current big data era. The time-consuming bottleneck mainly exists in the link of “traversing attribute sets in the lexicographic order”. To solve this problem, first, we construct a prefix dictionary tree in the inverse linear order of the attribute sets in the inter-layer cardinality order and use the irrelevant definition. Second, we propose and prove three theorems by the above definition and formal concept analysis. Third, according to these theorems, we put forward a new parallel attribute exploration algorithm based on attribute and intent sets. In the process of calculating intent and pseudo-intent sets, the algorithm skips the computing process of attribute sets which are intent sets and neither intent nor pseudo-intent sets with the help of these proposed theorems and reduces search space of the algorithm and the scale of implication calculation, so as to reduce the time complexity. Experimental results show that the worst time complexity of the algorithm is(O(M^{2}\times \max (P, G))). Compared with the improved algorithm, this algorithm has obvious time performance advantages.