-The understandability, maintainability, and reusability of object-oriented programs could be improved by automatically detecting well-known design patterns in programs. Many existing detection techniques are based on static analysis and use strict conditions composed of class structure data. Hence, it is difficult for them to detect design patterns in which the class structures are similar. Moreover, it is difficult for them to deal with diversity in design pattern applications. We propose a design pattern detection technique using metrics and machine learning. Our technique judges candidates for the roles that compose the design patterns by using machine learning and measurements of metrics, and it detects design patterns by analyzing the relations between candidates. It suppresses false negatives and distinguishes patterns in which the class structures are similar. We conducted experiments that showed that our technique was more accurate than two previous techniques.
INTRODUCTION
Design patterns (hereafter, patterns) are defined as
descriptions of communicating classes that form a common
solution to a common design problem. Gang of Four (GoF)
patterns [
Programs implemented by a third party and open source software may take a lot of time to understand, and patterns may be applied without explicit class names, comments, or attached documents in existing programs. Thus, pattern detection improves the understandability of programs. However, manually detecting patterns in existing programs is inefficient, and patterns may be overlooked.
Many studies on using automatic pattern detection to solve the above problems have used static analysis. However, static analysis has difficulty identifying patterns in which class structures are similar and patterns with few features. In addition, there is still a possibility that software developers might overlook patterns if they use strict conditions like the class structure analysis, and if the applied patterns vary from the intended conditions even a little.
We propose a pattern detection technique that uses
software metrics (hereafter, metrics) and machine learning.
Although our technique can be classified as a type of static
analysis, unlike previous detection techniques it detects
patterns by using identifying elements derived by machine
learning based on measurement of metrics without using
strict condition descriptions (class structural data, etc.). A
metric is a quantitative measure of a software property that
can be used to evaluate software development. For example,
one such metric, number of methods (NOM), refers to the
number of methods in a class [
II.
PREVIOUS DESIGN PATTERN DETECTION TECHNIQUES
AND THEIR PROBLEMS
Most of the existing detection techniques use static
analysis [
There is a technique that detects patterns based on the
degrees of similarity between graphs of pattern structure and
graphs of programs to be detected [
There is a technique that outputs pattern candidates based
on features derived from metric measurements [
Another existing technique improves precision by
filtering detection results using machine learning. This
technique inputs measurements of the classes and methods of
each pattern [
One current technique analyzes programs both before and
after patterns are applied [
Yet another approach detects patterns from the class
structure and behavior of a system after classifying its
patterns [
Other detection techniques use dynamic analysis. These
methods identify patterns by referring to the execution route
information of programs [
Some detection techniques use a multilayered
(multiphase) approach [
Finally, one existing technique detects patterns using
formal OWL (Web Ontology Language) definitions [
We suppress false negatives by using metrics and
machine learning to accommodate diverse pattern
applications and to distinguish patterns in which the class
structures are similar. It should be noted that only techniques
[
III.
Our technique is composed of a learning phase and a detection phase. The learning phase is composed of three processes, and the detection phase is composed of two processes, as shown in Figure 3. Each process is described below, with pattern specialists and developers included as the parties concerned. Pattern specialists mean persons that have the knowledge about the patterns. Developers mean persons that maintain the object-oriented software. Our technique currently uses Java as the program language. [Learning Phase]
Pattern specialists determine the detectable patterns and define the structures and roles composing these patterns.
Pattern specialists determine useful metrics to judge the roles defined in P1 by using the Goal Question Metric decision technique.
Pattern specialists input programs applied patterns into the metrics measurement system, and obtain measurements for each role. And specialists input these measurements into the machine learning simulator to learn. After machine learning they verify the judgment for each role, and if the verification results are not good, they return to P2 and revise the metrics. [Detection Phase]
Developers input programs to be detected into the metrics measurement system, and obtain measurements for each class. And developers input these measurements into the machine learning simulator. Machine learning simulator identifies role candidates.
Developers input role candidates judged in P4 to the pattern detection system by using the pattern structure definitions defined in P1. This system detects patterns automatically. The structure definitions correspond to the letters P, R, and E of section III-B.
A.
Currently, our technique considers five GoF patterns (Singleton, TemplateMethod, Adapter, State, and Strategy) and 12 roles. The GoF patterns are grouped into creational patterns, structural patterns, and behavioral patterns. Our technique uses these patterns to cover all these groups.
Pattern specialists decide on useful metrics to judge roles
by using the Goal Question Metric decision technique [
We experimented with judging roles by using general metrics without GQM. However, the machine learning results were unsatisfactory because the measurements of some metrics were irregular. Consequently, we chose GQM so that the machine learning could function appropriately by stable metrics in each role. With our technique, the pattern specialists set as a goal the accurate judgment of each role. To achieve this goal they defined a set of questions to be evaluated. Next, they decided on useful metrics to help answer the questions they had established. The pattern specialists decide metrics to identify roles by the quantity and the ratio of measurements. Therefore, they decide questions by paying attention to the attributes and operations of the roles by reading the description of the pattern definition. They decide simple metrics concerning the static aspect like structure first to improve the recall. However, the lack of questions might occur because GQM is qualitative. Therefore, if the machine learning results were unsatisfactory by irregular measurements of metrics, the procedure loops back to P2 to reconsider metrics also concerning behavior. Moreover, it will be possible to apply GQM to roles with new patterns in the future.
For example, Figure 4 illustrates the goal of making a judgment about the AbstractClass role in the TemplateMethod pattern. AbstractClass roles have abstract methods or methods using written logic that use abstract methods as shown in Figure 5. The AbstractClass role can be distinguished by the ratio of ConcreteClass
Target the number of methods to the number of abstract methods because with this role the former exceeds the latter. Therefore, the number of abstract methods (NOAM) and number of methods (NOM) are useful metrics for judging this role. Table I shows the results of applying GQM to all roles. The details of metrics are described in Table II of paragraph IV-A.
The previous technique [
P3.
Machine learning is a technique that analyzes sample data by computer and acquires useful rules with which to make forecasts about unknown data. We used the machine learning so as to be able to evaluate patterns with a variety of application forms. Machine learning suppresses false negatives and achieves extensive detection.
Our technique uses a neural network [
A neural network is composed of an input layer, hidden layers, and an output layer, as shown in Figure 6, and each layer is composed of elements called units. Values are given a weight when they move from unit to unit, and a judgment rule is acquired by changing the weights. A typical algorithm for adjusting weights is back propagation. Back propagation calculates an error margin between output result y and the correct answer T, and it sequentially adjusts weights from the layer nearest the output to the input layer, as shown in Figure 7. These weights are adjusted until the output error margin of the network reaches a certain value.
Our technique uses a hierarchical neural network
simulator [
Developers input programs to be detected into the metrics measurement system, and obtain measurements for each class. And developers input these measurements to the machine learning simulator. This simulator outputs values between 0–1 to all roles to be judged. The output values are normalized such that the sum of all values becomes 1. These output values are called role agreement values. A larger role agreement value means that the role candidate is more likely correct. The reciprocal of the number of roles to be detected is set as a threshold, and the role agreement values that are higher than the threshold are taken to be role candidates. The threshold is 1/12 (i.e., 0.0834) because we treat 12 roles at present. The sum of the output values is different at each input in the neural net work. Therefore, to use a common threshold for all the output, our technique normalizes the output value.
For example, Figure 8 shows the role candidate judgment results with NOM of 3 and NOAM of 2 and other metrics of 0; the output value of AbstractClass is the highest value. By regularizing the values of Figure 8, the roles are judged to be AbstractClass and Target.
Developers input role candidates judged in P4 into the pattern detection system by using the pattern structure definitions defined in P1. And, this system detects patterns by matching the direction of the relations between role candidates and the roles of pattern in programs. The matching moves sequentially from the role candidate with the highest agreement value to that with the lowest value. The pattern detection system searches all combinations of role candidates that accord with the pattern structures. The pattern detection system detects patterns when the directions of relations between role candidates accord with the pattern structure and when the role candidates accord with roles at both ends of the relations. Moreover, the relation agreement values reflect the kind of relation.
Currently, our method deals with inheritance, interface implementation, and aggregation relations. The kind of relations will increase as more patterns get added in the future. The relation agreement value is 1.0 when the kind agrees with the relation of the pattern, and it is 0.5 when the kind does not agree. If the relation agreement value is 0 then the kind of relation does not agree, the pattern agreement value might become 0, and these classes will not be detected as patterns. In such cases, a problem similar to those of the previous detection techniques will occur because the difference in the kind of relation is not recognized.
The pattern agreement value is calculated from the role agreement values and the relation agreement values. The pattern to be detected is denoted as P, the role set that composes the pattern is denoted as R, and the relation set is denoted as E. Moreover, the program that is the target of detection is defined as P’, the set of classes comprising the role candidates is R’, and the set of relations between elements of R' is denoted as E’. The role agreement value is denoted as Role, and the relation agreement is denoted as Rel. Role means the function which is input the element of R and the one of R' , and . Rel means the function which is input the element of E and the one of E'. The product of the average of two roles at both ends of the relation and Rel is denoted as Com, and the average of Com is denoted as Pat. Moreover, the average of two Roles is calculated when Com is calculated, and the average value of Com is calculated to adjust Pat and Role to values from 0 to 1 when Pat is calculated. If the directions of the relations do not agree, Rel is assumed to be 0.
rm R, rn R e p E, eq E Com(ep , eq ) Role(ra , rb) Role(rc , rd ) R el(ep , eq )
2 ra , rc R, rb, rd R, ep (ra , rc ), ep (rb, rd ) 1 Pat(P, P) (e p , eq ) E E R el(e p , eq ) 0
Figure 9 shows an example of detecting the TemplateMethod pattern. In this example, it is assumed that class SampleA has the highest role agreement value for an AbstractClass. The pattern agreement value between the program Samples and the TemplateMethod pattern is calculated with the following algorithm. epE,eqE Com(e p , eq ) P TemplateMethod (R, E) R {AbstractClass, ConcreteClass} E {AbstractClass ConcreteClass} Samples (R, E) R {SampleA, SampleB, SampleC} E {SampleA SampleB, SampleA ◇SampleC} ( : inheritance, ◇ : aggregation) Role( AbstractClass, SampleA) 0.82 Role(ConcreteClass, SampleB) 0.45 Role(ConcreteClass, SampleC) 0.57 R el( AbstractClass ConcreteClass, SampleA SampleB) 1.0 R el( AbstractClass ConcreteClass, SampleA ◇SampleC) 0.5
2
2 Pat(TemplateMethod , Samples) 1 0.635 0.348 0.492
2
In the program shown in Figure 9, the pattern agreement value of the TemplateMethod pattern was calculated to be 0.492. Pattern agreement values are normalized from 0 to 1, just like role agreement values. Our technique uses the same threshold among of pattern agreement value as role agreement value because a lot of classes are detected as the pattern that composed of the only class like the singleton pattern. Classes with a pattern agreement value that exceeds the threshold are output as the detection result. The reciprocal of the number of roles for detection is taken to be the threshold, similar to the case of role candidate judgment, and pattern agreement values that are higher than the threshold are output as the detection result.
In Figure 9, SampleA, SampleB, and SampleC were detected as TemplateMethod patterns. Moreover, SampleA and SampleB, SampleA and SampleC can also be considered to match the TemplateMethod pattern. In this case, the relation of “SampleA SampleB” is more similar to a TemplateMethod pattern than the relation of “SampleA ◇ SampleC” because its agreement value of the former pair is 0.635 while that of the latter pair is only 0.348.
IV.
We determined whether the machine learning simulator derived identifying elements of the roles after learning. Moreover, we compared our technique with two previous techniques to verify the precision and recall of our approach and to confirm whether it could match its detected patterns with similar structures and diverse patterns.
A.
We used cross-validation to verify the role candidate
judgment. In cross-validation, data are divided into n groups,
and a test to verify a role candidate judgment is executed
such that the testing data are one data group and the learning
data are n-1 data groups. We executed the test five times by
dividing the data into five groups. In this paper, programs
such as programs in the reference [
Table II shows the metrics that were chosen for the small-scale and large-scale programs. We used different metrics depending on the magnitude of the programs. For instance, we chose the metric called number of methods generating instance (NMGI) for small-scale programs because the method for transit states in the ConcreteState role in the State pattern generates other ConcreteState roles in small-scale programs. We guessed that the difference appeared in ratios of metrics about State and Strategy, so we used the same metrics for the large-scale programs without NMGI. Because State pattern treats the states in State role and treats the actions of the states in the Context role. On the other hand Strategy pattern encapsulates the processing of each algorithm into a Strategy role, and Context processing becomes simpler compared with that of State pattern.
http://www.washi.cs.waseda.ac.jp/ja/paper/uchiyama/dp.html
We focused our attention on recall because the purpose of our technique was detection covering diverse pattern applications. Recall indicates the degree to which detection results are free of leakage, whereas precision shows how free of disagreement these result are. The data in Table III was used to calculate recall. wr, xr, yr, and zr are numbers of roles, and wp, xp, yp, and zp are numbers of patterns. Recall was calculated from the data in Table III by the following expressions.
Recall of role candidate judgment: Rer wr wr xr
Table IV shows the average recall for each role. Role candidates must be judged accurately because the State pattern and Strategy pattern have the same class structure. Therefore, our technique regards the roles of the patterns other than State and Strategy patterns as role candidates when the role agreement value was above the threshold, whereas our technique regards the roles of State and Strategy patterns as role candidates when the role agreement value was above the threshold and the roles of both patterns were distinguished State pattern from Strategy pattern.
As shown in Table IV, the recalls for the large-scale programs were lower than those for the small-scale programs. Accurate judgment of large-scale programs was more difficult because these programs possessed attributes and operations that were unnecessary for pattern composition. Therefore, it will be necessary to collect a significant amount of learning data to adequately cover a variety of large-scale programs.
The results in Table IV pertain to instances where the State and Strategy patterns could be distinguished. The Context role had high recall, but State and ConcreteState roles had especially low recalls for largescale programs. However, the candidates for the State role were output with high recall when the threshold was exceeded. Therefore, the State pattern can be distinguished by initiating searching from the Context role in P5, and this improves recall.
Our technique detects patterns using test data in both the small-scale and large-scale programs, and this result is evaluated. We used 40 sets of programs where patterns are applied in small-scale programs and 126 sets of programs where patterns are applied in large-scale programs as learning data. We judged manually and qualitatively whether the patterns were appropriately applied in the detection results. Table V shows precision and recall of the detected patterns. Precision and recall were calculated from the data in Table III by the following expressions:
Recall of pattern detection : Re p wp wp x p Precision of pattern detection : Prp wp wp y p
Small-scale and large-scale programs shared a common point in that they both had recalls that were higher than precisions. However, there were many non-agreements about the State patterns and Strategy patterns in the largescale programs. Recall was 90% or more with the smallscale programs, but it dropped as low as 60% with the largescale programs.
The large-scale programs resulted in especially low recall for the Adapter pattern. Table IV shows the cause: The recall of the role candidate judgment for the Adapter pattern was not high enough. It is necessary to show that all roles that compose patterns have agreement values that are above the threshold so that patterns will be detected. There were many cases in which neither of the roles that composed patterns was judged as a role candidate for the Adapter pattern. It will be necessary to return to P2 and choose new metrics. The State pattern was identified by searching from the Context role, for instance, in the State pattern detection in the large-scale programs, and the recall of the pattern detection was higher than the recall of role candidate judgment. Table V shows holistically that our technique suppresses false negatives because the recall is high.
We experimentally compared our technique with
previous detection techniques [
Figure 10 shows the recall and precision graphs for our technique and TSAN, and Figure 11 shows the corresponding graphs for our technique and DIET. We ranked the detection results of our technique with the pattern agreement values. Next, we calculated recall and precision according to the ranking and plotted them. Recall and precision were calculated from the data in Table III by using the expressions of paragraph IV -B. In the results of TSAN and DIET, we alternately plotted results because these previous detection techniques output no value to rank. In the recall and precision graphs higher values are better.
Figure 10 and 11 show particularly good results for all techniques when small-scale programs was examined. This is because small-scale programs do not include unnecessary attributes and operations in the composition of patterns.
Table VI and VII show the average F measure for each plot of Figure 10 and 11. The F measure is calculated with recall and precision calculated by the above-mentioned expression as follows.
F measure 2 Prp Re p
Prp Re p
A large F measure means higher accuracy, and these tables show that our technique had a larger F measure than the previous techniques had.
Our technique distinguished State pattern Strategy pattern. Table VIII is an excerpt of the metrics measurements for the Context role in State pattern and Strategy pattern that were distinguished by the experiment on the large-scale programs. State pattern treats the states in State role and treats the actions of the states in the Context role. Strategy pattern encapsulates the processing of each algorithm into a Strategy role, and Context processing becomes simpler compared with that of State pattern. Table VIII shows 45 fields and 204 methods as the largest in Context role in State pattern (18 and 31 respectively in Context role of Strategy pattern). Therefore, the complexity of Context role of both patterns appears in the number of fields and the number of methods, and these are distinguishing elements. Figure 10 shows that our technique is especially good because State pattern and Strategy pattern could not be distinguished with TSAN.
Figure 11 shows that the recall of DIET is low in the case of large-scale programs because this technique doesn't accommodate the diversity in pattern applications. Additionally, large-scale programs not only contain many attributes and operations in the composition of patterns but also subspecies of patterns.
Our technique detected subspecies of patterns. For example, our technique detected the source code of the Singleton pattern that used the boolean variable as shown in Figure 12. This Singleton pattern was not detected in TSAN or DIET. However, unlike the previous techniques, our technique is affected by false positives because it is a gradual detection using metrics and machine learning instead of strict conditions. False positives of the Singleton pattern especially stood out because Singleton pattern is composed of only one role. It will be necessary to use metrics that are specialized to one or a few roles to make judgments about patterns composed of one role like the Singleton pattern (P4).
Therefore, our technique is superior to previous one because the curve of our technique is above the previous in Figures 10 and 11.
We devised a pattern detection technique using metrics and machine learning. Role candidates are judged using machine learning that relies on measured metrics, and patterns are detected from the relations between classes. We worked on the problems associated with overlooking patterns and distinguishing patterns in which the class structures are similar.
We demonstrated that our technique was superior to two previous detection techniques by experimentally distinguishing patterns in which the class structures are similar. Moreover, subspecies of patterns were detected, so we could deal with a very diverse set of pattern applications. However, our technique was more susceptible to false positives because it does not use strict conditions such as those used by the previous techniques.
We have several goals for our future work. First, we plan to add more patterns to be detected. Our technique can currently cope with five patterns. However, we predict it will be possible to detect other patterns if we can decide upon metrics to identify them. It is also necessary to collect more learning data to cover the diversity in pattern applications. Moreover, we plan to more narrowly adapt the metrics to each role by returning to step P2 because results might depend on the data. This process would lead to the enhancement of recall and precision.
Second, we currently qualitatively and manually judge whether to return to step P2 and to apply GQM again; hence, in the future, we should find an appropriate automatic judgment method.
Third, we plan to prove the validity of the expressions and the parameters of agreement values and thresholds. We consider that it is possible to reduce the false positive rate by deciding on the optimum thresholds for role agreement values and pattern agreement values.
Finally, we plan to determine the learning number of times automatically and examine the correlation of the learning number of times and precision. [21] JUnit.org. Resources for Test Driven Development.
http://www.junit.org/