Calculation and optimization of thresholds for sets of software metrics

The methods described in this article are general and may be used independent of a specific metric set. However, as part of this article, metric sets for the evaluation of the maintainability are studied exemplary. This is done with two different metric sets on different levels of abstraction: methods and classes. The maintainability describes non-functional aspects such as testability, understandability, or changeability of software. Because no single metric is able to cover all these aspects, we employ a set of metrics that covers internal attributes like the structure, size, and complexity instead. We selected the metrics based on our experience and with the aim to cover the maintenance related aspects of the source code that can be measured automatically with internal product metrics.

For the analysis of methods and functions, we use four metrics listed in Table 1a. With the control-flow structuredness measured by the Cyclomatic Number (VG) and Nested Block Depth (NBD), coupling measured by Number of Function Calls (NFC), and size measured by Number of Statements (NST), these metrics cover most of the maintainability-related attributes of methods, except the algorithmic complexity. Since algorithmic complexity is not really an attribute of the source code and cannot be measured automatically, it has been omitted. While both VG and NBD measure the control-flow structuredness, they measure different aspects of this attribute: NBD measures the maximum nesting of structural blocks, while (VG) measures the overall branching between blocks.

For the analysis of classes, the seven metrics listed in Table 1b are used. With these metrics, five internal attributes of classes are evaluated. The metric Weighted Methods per Class (WMC) measures the method complexity as the sum of the metric VG measured for all methods in a class. The metrics Coupling Between Objects (CBO) and Response For a Class (RFC) measure the coupling. For the measurement of the size of a class, the metrics Number of Methods (NOM) and Lines of Code (LOC) are utilized. The use of inheritance is measured by Number of Overridden Methods (NORM), the staticness of a class is measured by the metric Number of Static Methods (NSM). We included the attributes inheritance and staticness, as they greatly influence the maintainability of classes (Daly et al. 1996). Inheritance is often difficult to test and also decreases the understandability of the source code. Static methods and attributes can pose problems, as they are global for all instances of a class and can therefore introduce unwanted side effects.

One might have noted that with WMC, CBO, and RFC, three of the six popular metrics defined by Chidamber and Kemerer (1994) are used. Initially, all of the six metrics were part of the set, but the metrics Depth of Inheritance Tree (DIT), Number of Children (NOC) and Lack of Cohesion in Methods (LCOM) were excluded due to their poor distributions. LCOM was found to be poorly distributed by Basili et al. (1996). Furthermore, DIT and NOC are poorly distributed in the projects measured for the case studies in this work. We discuss their exclusion in Section 5.3.

In general, thresholds discriminate values. In case a threshold defines an upper bound, the values that are greater than a threshold value are considered to be problematic, the values lower are considered to be acceptable. Thus, by defining thresholds a simple analysis of measured values is possible. For the interpretation of software metrics thresholds are required. For example, consider a metric m that measures the size of an entity x. Then a threshold t can be used to determine if x is to large:

While the above is an example of a threshold used as an upper bound, it might as well be a lower bound. For simplicity, we assume that thresholds are always upper bounds. However, this is no restriction as lower bounds can be transformed into upper bounds. Let m a metric with threshold t that defines a lower bound, i.e., entities x are considered to be problematic if m(x) < t, which is equivalent to 1/m(x) > 1/t if m(x) and t are non-negative, as metrics and thresholds usually are. By defining a new metric m′(x) = 1/m(x) and a new threshold t′ = 1/t a new metric with the opposite order is defined and with t′ a threshold is obtained that defines an upper bound. However, by inverting the metric, its scale is changed. Another way to transform a lower bound into an upper bound while keeping it to scale is to subtract the metric from a maximum value. Let m _max the maximum value of metric m. Then and a new metric m′′(x) = m _max  − m(x) and a new threshold t′′ = m _max  − t are obtained, where t′′ is an upper bound for m′′. However, this method has the disadvantage that a maximum value m _max has to be known.

Thresholds are not without problems. The first is the generality of threshold values. In general, a threshold value is good in one setting must not necessarily be good every setting. Depending on the organization, the programming language, the tools used, the qualification of the developers, among other factors that are project dependent, good threshold values may vary. This is a problem, as each organization, and maybe even each project, has to define thresholds that are chosen depending on its environment. This issue directly relates to a second issue, as good thresholds depend on so many factors, the definition of thresholds itself is a problem. Therefore, a methodology to determine environment specific thresholds is required.

To allow a more differentiated analysis more than one threshold value for one metric can be defined. In this article, we assume source code to be either problematic or un-problematic. However, further shades of gray exist in between. For example, there may be two thresholds, a low one for weak infractions and a higher one for critical infractions. In this study, we only consider defining a single threshold for a given metric.

As baseline for our analysis, we use the thresholds listed in Table 2 for the metric sets introduced in the previous section to analyze the maintainability of methods and classes. Most of them were determined as good thresholds for these metrics in previous work (Lorenz and Kidd 1994; French 1999; Benlarbi et al. 2000). The languages and the environments for which these threshold values were determined are sufficiently similar to the setting of this work, which is why we argue that these thresholds are transferable to our application. The thresholds for the metrics LOC and NOM are based on thresholds used by the source code analysis tool PMD (Copeland 2005). PMD defines a threshold value of 1000 for lines of code including empty and comment-only lines for Java classes. In this work, we use different definition for the lines of code metric that excludes both empty and comment-only lines, thus we adapted the value to 500. Furthermore, PMD defines a threshold value of 10 for the number of methods excluding methods that start with “get” or “set”. As the metric NOM counts all methods, the threshold value is adapted to 20 to account for the additional methods. For the remaining two metrics, NFC and NST, no reference values are available in the literature. Therefore, based on our experience, reasonable threshold values for both metrics have been defined, 5 for NFC and 50 for NST.

In this work, we use concept learning. A concept defines how to divide vectors from the ℝ ^d into positive and negative examples. The task of a learning algorithm is to infer a target concept g out of a concept class \(\mathcal{C}\). The target concept can also be interpreted as the bayesian classifier (Duda and Hart 1973) of the concept. A concept can also be understood as a map \(g: \mathfrak{X}^d \to \{0,1\}\), where \(\mathfrak{X}^d \subset \mathbb{R}^d\) denotes the input space. A learning sample is of the form \(U=(X,Y) \in \mathfrak{X}^d \times \{0,1\}\), where the input element X is randomly distributed according to the sample distribution \(\mathcal{D}\) defined over the input space \(\mathfrak{X}\), Y is the random label or output element associated with X. In a noise free setting, the value of Y depends only on the random vector X and the target concept g and Y = g(X). To obtain samples U, the concept of an oracle is used. On request, an oracle \(EX(\mathcal{D},g)\) randomly draws an input element X according to the distribution \(\mathcal{D}\), classifies X using g and returns a sample U = (X,g(X)). In practical applications, the oracle can be seen as a training sample that contains classified entities to be used for the learning.

Real-life applications are usually not noise-free, i.e., the property Y = g(X) is not always fulfilled. Most algorithms designed to work on noise-free data often perform poorly or do not work at all in the presence of noise. Therefore, noise modelling and algorithms that use these models for learning in the presence of noise are important. One way to introduce noise into a learning model is the classification noise model, which was first formalized by Angluin and Laird (1988). Further details on noise models can be found in Mammen and Tsybakov (1999), Tsybakov (2004). In the classification noise model, the label of the output variable Y is changed with a fixed probability and Y = g(X) ⊕ S, where ⊕ denotes the symmetric difference. The random noise S ∈ {0,1} is 1 with probability η, i.e., ℙ(S = 1) = η, where η denotes the noise rate. In the classification noise model, S is independent of the input element X. It follows directly that ℙ(Y ≠ g(X)) = η. In combination with oracles, noise can be seen as an attacker that corrupts the output element of a sample generated by an oracle. Figure 1a visualizes this concept.

In the SQM proposed by Kearns (1998) query functions of the form \(\chi: \mathfrak{X}^d \times \{0,1\} \to [a,b]\) are used to infer information about the data. For this purpose, a statistical oracle is introduced that returns the expected result of the queries within a specified degree of precision. The estimation is based on noise models.

We use a generalization of the classification noise model, where the random noise rate is orthogonal to the target concept (Brodag et al. 2010). The restriction that S is independent of the input element X is dropped. Instead, we introduce a random noise rate η(X) that depends on the input element, as shown in Fig . 1b. Hence, η(x) = ℙ(S = 1|X = x) and thus the random noise depends on the input. For a given \(x \in \mathfrak{X}^d\), the noise rate is η(x) = ℙ(Y ≠ g(X)|X = x) and for y ₀ ∈ {0,1} the conditional expected noise rate given g(X) = y ₀ is Using the conditional expected noise rates η ₀, η ₁, the expected noise rate can be calculated as \(\eta := \mathbb{E}\eta(X) = \eta_0\mathbb{P}(g(X)=0)+\eta_1\mathbb{P}(g(X)=1)\).

Furthermore, we assume that query functions are admissible. A query function χ is admissible, if it is not correlated to the noise rate η(X) conditioned on the concept g(X). The geometrical uncorrelation is orthogonality, hence it is said that the noise is orthogonal to the target concept. For the learning, this means that it is not possible to infer the value of χ by simply considering the noise rate η(X). This is a reasonable assumption, as usually no information about the result of a query is obtained by simply considering the noise rate.

Based on the introduced concepts and definitions, we can state the central theorem of the learning framework. This theorem describes how the expected value of an admissible query can be calculated if the conditional expected noise rates η ₀ and η ₁ are known.

The proof of Theorem 1, as well as further details concerning learning with orthogonal noise, can be found in Brodag et al. (2010). The function \( \mathbb{1} \) is defined as On a learning sample, the expected values \(e_{y_0} := \mathbb{P}(Y = y_0)\), \(e_{\chi,y_0} := \mathbb{E}[\mathbb{1}_{\{Y=y_0\}} \chi(X,\) y ₀)], and \(e_{\bar{\chi},y_0} := \mathbb{E}[\mathbb{1}_{\{Y=\bar{y}_0\}} \chi(X,y_0)]\) can be estimated using standard maximum-likelihood estimators. With the estimated values, the conditional expected value of a query \(\mathbb{E}(\chi(X,\!y_0)|g(X)\!=\!y_0)\) can be calculated for y ₀ ∈ {0, 1} according to Theorem 1 as and where \(\bar{\chi}\) is an abbreviation for \(\bar{\chi}(x,y) = \chi(x,\bar{y})\). The conditional noise rates η ₀ and η ₁ are usually unknown and estimated by guessing. In practical applications, the noise rates are guessed by sampling. For example, if we estimate that the noise rate is between 0.1 and 0.2, hypotheses for all pairs of noise rates η ₀,η ₁ = 0.1,0.11,...,0.19,0.2 could be calculated. Afterwards, we select the best of these hypotheses. This is not an estimation of the noise rate itself, i.e., the noise rate used to calculate the optimal solution is not necessarily the true noise rate. Such noise handling strategies guarantee that if a noise rate close to the true noise rate is part of the sampled noise rates, the result is at least as good as it would be with the true noise rate.

In this work, we adapted the algorithm for learning axis-aligned d-dimensional rectangles proposed by Kearns (1998) to the noise model described above. The main adaptations are that the conditional expected noise rates η ₀ and η ₁ have both to be sampled, instead of only the expected noise rate η. Furthermore, the statistical oracle used by the algorithm is changed from the SQM to the random noise model by calculating the expected results of statistical queries based on Theorem 1. The algorithm has two phases. In the first phase, the training data is partitioned according to its distribution. In the second phase, the rectangle is computed based on this partition. Both phases are described in the following.

The aim of the first phase of the algorithm is to find a partition of the d-dimensional real-space, such that for each dimension i = 1,...,d and p,q = 1,...,⌈1/ε⌉ for X ∈ ℝ ^d randomly distributed according to \(\mathcal{D}\), where X _i donates the i-th component of X and ε an error bound that the calculate hypothesis should abide. This means that it is equally likely that the i-th component of the randomly drawn vector X falls into any of the intervals I _i,·. In the implementation of the algorithm, a sorting algorithm is utilized to obtain these intervals according to the empirical distribution of a discrete training sample. After sorting the values for the i-th dimension, the intervals I _i,p can be defined by assigning the first \(\frac{p}{\lceil 1/\varepsilon \rceil}\) vectors to I _i,1, the next \(\frac{p}{\lceil 1/\varepsilon \rceil}\) to I _i,2 and so on. These intervals fulfill the property defined by (3.6). If there are n samples in a training set, the complexity of the first phase is O(d n logn), as for each dimension the samples have to be sorted and efficient sorting algorithms are O(n logn).

In the second phase, the boundaries of the target rectangle are calculated. For each dimension separately, the probability \(p_{I_{i,p}} = \mathbb{P}(X_i \in I_{i,p} | g(X) = 1)\), i.e., the probability that the target rectangle intersects an interval I _i,p is calculated. This probability is calculated using admissible queries and (3.5). If the target rectangle intersects an interval, the probability \(p_{I_{i,p}}\) should be significantly larger than 0. Thus, for each dimension i, the probabilities \(p_{I_{i,p}}\) are calculated from the left, i.e., p = 1,2,.... The first interval, for which \(p_{I_{i,p}}\) is significant defines the left, i.e., lower boundary l _i of the rectangle in the i-th dimension. The same is done from the right, i.e., p = ⌈1/ε⌉,⌈1/ε⌉ − 1, ... to determine the right, i.e., upper boundary u _i . Using this procedure for each dimension, boundaries (l _i ,u _i ) are calculated.

In the second phase, for each dimension, the probability \(p_{I_{i,o}}\) is calculated for at most ⌈1/ε⌉ intervals from the left and analogously from the right. The estimation of this probability is O(n). Thus the complexity of the second phase is \(O(d n \frac{1}{\varepsilon})\) and the overall complexity of the algorithm is \(O(d n \log n + d n \frac{1}{\varepsilon})\).

The analysis approach is based on a given metric set M = {m ₁, ..., m _d } and a set of software entities X with known classifications Y. The aim is to obtain thresholds T = {t ₁, ..., t _d } for the metrics in M such that the metric set can be used to discriminate software entities in the same way, as it is done by the pair (X,Y). By measuring the software entities X with M, we transform the set of software entities X into a set of vectors in the d-dimensional real space, such that \(M(\mathbf{X}) := \{(m_1(x),\ldots,m_d(x)): x \in \mathbf{X}\} \subset \mathbb{R}^d\). The pair (M(X),Y) is the input for the axis-aligned rectangle learning algorithm, introduced in Section 3.2. As result, the algorithm yields pairs of upper and lower bounds (l _i ,u _i ) for each dimension i = 1,...,d. As the i-th dimension represents the values the software entities calculated using the metric m _i and under the assumption that high metric values are bad, we interpret the upper bound of the rectangle in the i-th dimension as the threshold for the metric m _i . Therefore, with t _i  = u _i a set of thresholds T = {t ₁, ..., t _d } for the metric set M is obtained. For an entity x, the classification of the metric set M and the thresholds T is defined as i.e., f ₀(x,M,T) is zero when at least one metric m _i exceeds its threshold t _i , and is one when none of the metrics exceeds its threshold.

Under the assumption that metric values are positive, this classification describes a rectangle with upper bounds t _i and 0 as the lower bound. Figure 2a visualizes this in a 2-dimensional setting to clarify the relationship between rectangle learning and the usage of metric thresholds for the classification of software entities. Algorithm 1 describes this methodology in a step-wise fashion. The algorithm can be used to determine thresholds for a metric set given any training sample (X,Y) and any metric set, regardless of how the training sample or the metric set were determined.

The classification error is defined as the probability that a randomly drawn sample (X,Y) is classified wrongly Consequently, the empirical classification error on a given training sample (X,Y) is defined as

Next, we define a threshold optimization algorithm that computes an optimized metric set based on the calculation of thresholds for a metric set. This means a metric set that is not only effective with respect to the classification it yields, but also efficient in terms of its size. To achieve this, we reduce the dimension of the metric set and recalculate the threshold values for the reduced sets. Recalculating the thresholds allows the algorithm to, e.g., enforce a stronger classification using one metric while dropping another from the set.

The algorithm uses an existing method f for the classification of software entities X. By applying f to the entities x ∈ X, the classification Y can be calculated as Y = {f(x): x ∈ X}. The resulting pair (X,Y) is the basis for the calculation of thresholds.

Let M be a metric set to be used as basis for the determination of an optimized, i.e., effective and efficient metric set with thresholds. A metric set is called effective if its classification error is close to 0, i.e., less than or equal to a threshold for the error δ ∈ ℝ. A metric set is called efficient if it is the smallest set to do so. Therefore, we need to calculate a subset \(M' = \{m'_1, \ldots, m'_{d'}\} \subseteq M\) with thresholds T′ = {t′₁, ..., t′_d′} that yields classification error smaller than δ. To this aim, we determine thresholds based on the training set (X,Y) for all subsets of M. In other words, all sets that are element of the power set of M: \(M' \in \mathcal{P}(M) \setminus \emptyset\). Then, for each subset M′ the empirical classification error ε _X,Y is calculated. The smallest set M′ that has a classification error ε _X,Y ≤ δ is an effective and efficient subset of M. Algorithm 2 describes the whole threshold optimization algorithm in a step-wise fashion. We discuss the run time and scalability of the algorithm in Section 6.1 (research question R5).

The value δ can be used as a steering parameter, depending on the accuracy expected of the optimized set and the available data. The higher the accuracy shall be and the more data is available, the smaller δ should be. It is possible that no M′, T′ satisfies the condition that its error is below δ. In this case, there are three options to proceed: 1) choose a larger value for δ; 2) use a different metric set M; 3) abort the optimization efforts and conclude that a metric set M′ with threshold T′ is insufficient to describe the classification. As a practical matter, δ can be sampled, e.g., by starting with δ = 0.01 and increasing it in 0.01 steps till a metric set found.

Given an existing effective metric set, the threshold optimization algorithm can determine an effective and efficient subset. Let M be a metric set with thresholds T and X a set of software entities. The function f ₀(x,M,T) defines a classification method for X. Then, f ₀, X, M, and an appropriate value for δ are the input for the threshold optimization algorithm which will compute an optimized subset M ^* with thresholds T ^*.¹ As an example, Fig. 2 shows how the classification obtained by two metrics is approximated by only one of the two metrics. The dashed lines visualize the thresholds of the two metrics, used to classify the samples for the training. In Fig, 2a, both metrics are used for the classification; in Fig. 2b, only metric one is used. The squares mark the entities that are misclassified by the approximation.

Another way to utilize the threshold optimization algorithm is to reduce the complexity of the classification scheme. With thresholds, a simple kind of classification is described: if a threshold is violated, an entity is problematic. This makes it clear why an entity is problematic and also provides an indicator what the problem might be. A slightly more complex approach is to allow a number of infractions λ, i.e., λ thresholds may be violated. The function describes the classification defined by a metric set M with thresholds T. With λ = 0, this f _λ is equal to f ₀ 4.1, hence f _λ is a generalization of f ₀.

One reason to use such a rule is to grant the developers more freedom, e.g., allowing short methods with a high structural complexity or long methods with a low structural complexity. But methods that are both long and structurally complex are forbidden. The classification with λ allowed infractions introduces an additional complexity to understand why a problematic entity was classified as such and which counter measures can be taken. Complex approaches that may yield a very good classification may be difficult to impossible to interpret, e.g., SVM based techniques (Schölkopf and Smola 2002). Other techniques, e.g., classification trees (Quinlan 1986) show directly why an entity was classified as problematic, but it not clear how to fix as the tree may hide other reasons why the entity is problematic. In general, the classification could be performed by an arbitrary complex function f. A metric set that yields the same classification, with no infractions whatsoever allowed is preferable, because as Occams Razor suggests, the simplest solution is preferable (MacKay 2003).

The threshold optimization algorithm calculates a simple threshold-based effective and efficient classification for a metric set M, with f, M and a set of software entities X as input for Algorithm 2. Figure 3 shows an example of how a classification obtained with two metrics and one allowed infraction is approximated by only one of them.

An important aspect of thresholds for metrics is that they are often dependent on the properties of the project environment such as the requirements, the developer qualification or the programming language. Therefore, the best results are achieved with thresholds tailored to the specific environment. In the previous two sections, we have only shown how the threshold optimization algorithm can optimize already existing classification methods. However, the algorithm is also able to determine thresholds where currently no method of classification exists. For this, an expert has to select a set of software entities X that are typical for the project environment. Afterwards, the expert manually classifies them into good and bad based on his or her expertise. As basis for this, the expert may use intricate knowledge, but also information about the software, e.g., the fault history to identify which sections are probably problematic (e.g. Rosqvist et al. 2003). This is the traditional approach to determine the quality of a software, without metric sets and thresholds. Using the thus obtained knowledge, we can determine a metric set with environment specific thresholds that mimics the experts knowledge. To conform to our nomenclature, the expert can be seen as a function f that classifies software. Then, given a metric set M, the threshold optimization algorithm is able to determine an effective, efficient, and environment specific metric set M ^* with thresholds T ^* that emulates the expert’s knowledge.