Research On Formal Concept Analysis Based Dependence Cluster Detection

A dependence cluster is a maximal set of program components that all depend upon each other. The current view is that large dependence cluster is extremely universal, which widely exists in all kinds of program source code. The existence of large dependence cluster may lead to the significant ripple effect, which might affect the whole system. A change to a certain point of the cluster will cause potential adverse effects on the rest of the cluster. It has a negative impact on many different software engineering activities, including comprehension, testing and maintenance. Dependence cluster detection is a prerequisite for solving adverse effects caused by dependence cluster. Previous work has proposed a Monotonic Slice-size Graph (MSG) based method to detect the same slice size of dependence cluster. They believe that the program components which has same size slice belong to a same cluster. However, the proposed method is conservative approximatation. Even though the scheme performs with good efficiency, the accuracy of the detection is not satisfied, which will cause false positives and false negatives.To improve the accuracy of the same slice size detection, this paper presents a dependence cluster detection method with the aid of Formal Concept Analysis (FCA) which is known as an effective mathematical tool and designs the process in detail. The paper discusses the selection of the research object and how to obtain the research object dependence relations. Next, this work abstracts and organizes the dependence relations to a formal context. Additionally, the paper presents the definition of large concept in the concept lattice based on object inclusion degree, the selection strategy of large concepts, and the dependence cluster detection method utilizing the large concepts. In order to improve the efficiency of detection method and the accuracy of large concepts, a dependence cluster detection method based on Lightweight Formal Concept Analysis is proposed. With evaluating and selecting the best one out of the concept lattice construction algorithms, the pruned transformation strategy of FCBO algorithm based on the object inclusion degree is proposed and its correctness is proved theoretically.To evaluate the effectiveness of the proposed FCA based dependence cluster detection method, the experiments are conducted on 12 programs which are in different sizes and areas. Experiment analyzes the proposed method in terms of the results. The dependence cluster generated by same slice size detection method is analyzed to verify the effectiveness of the proposed method. In addition, through false negatives and false positives experimental analysis of the accuracy of the two methods, the results show that the proposed method can effectively avoid false negatives and false positives, increase dependence cluster detection accuracy. Furthermore, the effectiveness of lightweight strategy is evaluated. The results show that the method can not only choose the same large concept as the unabridged concept lattices, but can also significantly reduce the number of concepts generated, narrow the large concepts search domain, and reduce the time cost in concept lattice construction.