18.1.1 Getting rid of similar features: synonym pruning

Throughout the rest of the chapter we will use the term synonyms, which is nothing but features that are similar to one another according to a certain measure (e.g., Euclidean distance in this chapter). QUICK discovers such features and removes them from the data set as follows:

(1) Take an unlabeled data set (i.e., no effort value) and transpose it, so that the independent features become the instances (rows) in a space whose dimensions (columns) are defined by the original instances.

(2) Let E_NN be a matrix ranking the neighbors of a feature: closest feature is #1, the next is #2, and so on.

(3) E(k) marks k-closest features (e.g., E(1) marks #1s).

(4) Calculate the popularity of a feature by summing up how many times it was marked as #1.

(5) Leave only the unmarked features, i.e., the ones with a popularity of zero.

The features with a popularity of zero are the unique features, which are not similar to any other feature. In our data set, we want to have features that are different from one another so that they convey different information. That is why we are picking only the features that have a popularity of zero.

18.1.2 Getting rid of dissimilar instances: outlier pruning

The concept of outlier pruning is very similar to the concept of synonym pruning, they both remove cells in a multidimensional space. A good explanation is given by Lipowezky [262], who says that the two tasks (feature and outlier pruning) are quite similar: They both remove cells in the hypercube of all instances times all features. According to the viewpoint of Lipowezky, it should be possible to convert a case selection mechanism into a feature selector and vice versa. Here we will see that the feature selector mechanism we used above is used almost in an as-is manner as an instance selector, with some minor, yet important, differences:

• With synonym pruning, we transpose the data set, so that the features are defined as rows, which are what we want to work on. Then we find the distances between “rows” (which, in the transposed data are the features). We count the popularity of each feature and delete the popular ones (note that these are the synonyms, the features that needlessly repeat the information found in other features).

• With outlier pruning, we do not transpose the data before finding the distances between rows (as rows are already what we want to work on, i.e., instances). Then we count the popularity of each instance and delete the unpopular ones (these are the instances that are most distant, hence most dissimilar to the other instances).

A quick note of caution here is that the data set on which we prune outliers contains only the selected features of the previous phase. Also note that the terms feature and variable will be used interchangeably from now on. To summarize, the outlier pruning phase works as follows:

(1) Let E_NN be a matrix ranking the neighbors of a project, i.e., closest project is #1, the next is #2, etc.

(2) E(k) marks only the k-closest projects, e.g., E(1) marks only #1s.

(3) Calculate the popularity of a project by summing up how many times it was marked as #1.

(4) Collect the costing data, one project at a time in decreasing popularity, then place it in the “active pool.”

(5) Before a project's, say project A, costing data is placed into the active pool, generate an estimate for A. The estimate is the costing data of A's closest neighbor in the active pool. Note the difference between the estimate and the actual cost of A.

(6) Stop collecting costing data if the active pool's error rate does not decrease in three consecutive project additions.

(7) Once the stopping point is found, a future project—say project B—can be estimated. QUICK's estimate is the costing data of B's closest neighbor in the active pool.

18.3.1 Phase 1: synonym pruning

The first phase (synonym pruning) is composed of four steps:

1. Transpose data set matrix.

2. Generate distance-matrices.

3. Generate E(k) matrices using E_NN.

4. Calculate the popularity index based on E(1) and select nonpopular features.

1. Transpose data set matrix. It is assumed that the instances of your data set are stored as the rows prior to transposition. Hence, this step is not necessary if the rows of your data set in fact represent the dependent variables. However, rows of SEE as well as software defect data sets almost always represent the past project instances, whereas the columns represent the features defining these projects. When such a matrix is transposed the project instances are represented by columns and project features are represented by rows. Note that columns are normalized to 0-1 interval before transposing to remove the superfluous effect of large numbers in the next step. To make things clear for readers, who are not familiar with distance calculation: The main reason of dealing with the transposition of a data set is to prepare it for step #2, where we generate the distance matrices. At the end of step #1 we aim the rows to represent whatever objects (in synonym pruning they are the features) between which we want to calculate the distances.

2. Generate distance-matrices. For the transposed dataset D^T of size F, the associated distance-matrix (DM) is an F × F matrix keeping the distances between every feature-pair according to Euclidean distance function. For example, a cell located at ith row and jth column (DM(i, j)) keeps the distance between ith and jth features (diagonal cells (DM(i, i)) are ignored as we are not interested in the distance of a feature to itself, which is 0).

3. Generate E_NN and E(1) matrices. E_NN[i, j] shows the neighbor rank of “j” with regard to “i,” e.g., if “j” is “i's” third nearest neighbor, then E_NN[i, j] = 3. The trivial case where i = j is ignored, because an instance cannot be its own neighbor. The E(k) matrix is defined as follows: if i ≠ j and E_NN[i, j] ≤ k, then E(k)[i, j] = 1; otherwise E(k)[i, j] = 0. In synonym pruning, we want to select the unique features without any nearest neighbors, as these are dimensions of our space that are most unique and different from other dimensions. For that purpose we start with k = 1; hence, E(1) identifies the features that have at least another nearest neighbor and the ones without any nearest neighbor. The features that appear as one of the k-closest neighbors of another feature are said to be popular. The “popularity index” (or simply “popularity”) of feature “j,” Pop(Feat_j), is defined to be $\mathit{Pop}\left(\mathit{Fea}{t}_j\right)={\sum }_{i=1}^{n}E\left(1\right)\left[i,j\right]$, i.e., how often “jth” feature is some other feature's nearest neighbor.

4. Calculate the popularity index based on E(1) and select nonpopular features. Nonpopular features are the ones that have a popularity of zero, i.e., Pop(Feat_i) = 0.

18.3.2 Phase 2: outlier removal and estimation

Outlier removal is almost identical to synonym pruning in terms of implementation, with a few important distinctions. However, most of your code implemented for synonym pruning can be reused in the outlier removal. Below are the four steps of forming the outlier removal:

1. Generate distance-matrices.

2. Generate E(k) matrices using E_NN.

3. Calculate a “popularity” index.

4. After sorting by popularity, find the stopping point.

1. Generate distance-matrices. Similar to the case of synonym pruning, a data set D of size N would have an associated distance-matrix (DM), which is an N × N matrix whose cell located at row i and column j (DM(i, j)) keeps the distance between the ith and jth instances of D. The cells on the diagonal (DM(i, i)) are ignored. Note that D in this phase comes from the prior phase of synonym pruning; hence, it only has the selected features. Remember to retranspose (or revert the previous transpose) your matrix, so that in this phase the rows correspond to the instances of your data set (e.g., the projects for SEE data sets or the software modules for software defect data sets would correspond to rows).

2. Generate E_NN and E(1) matrices. This step is identical to that of synonym pruning in terms of how we calculate the E_NN and E(1) matrices. To reiterate the process: E_NN[i, j] shows the neighbor rank of “j” with regard to “i.” Similar to the step of synonym pruning, if “j” is “i's” third nearest neighbor, then E_NN[i, j] = 3. Again, the trivial case of i = j is ignored (nearest neighbor does not include itself). The E(k) matrix has exactly the same definition as the one in the synonym pruning phase: if i ≠ j and E_NN[i, j] ≤ k, then E(k)[i, j] = 1; otherwise E(k)[i, j] = 0. In this study the nearest-neighbor-based Analogy-based estimation (ABE) is considered, i.e., we use k = 1; hence, E(1) describes just the single nearest neighbor. All instances that appear as one of the k-closest neighbors of another instance are defined to be popular. The “popularity index” (or simply “popularity”) of instance “j”, Pop(j), is defined to be $\mathit{Pop}\left(j\right)={\sum }_{i=1}^{n}E\left(1\right)\left[i,j\right]$, i.e., how often “j” is someone else's nearest neighbor.

3. Calculate the popularity index based onE(1) and determine the sort order for labeling. Table 18.3 shows the popular instances (instances that are the closest neighbor of another instance) among the SEE projects experimented with in this chapter. As shown in Table 18.3, the popular instances j with Pop(j) ≥ 1 (equivalently, E(1)[i, j] is 1 for some i) have a median percentage of 63% among all data sets; i.e., more than one-third of the data is unpopular with Pop(j) = 0. The meaning of this observation is that if we were to use a k-NN algorithm with k =1, then one-third of the labels that we have would never be used for the estimation of a test instance.

4. Find the stopping point and halt. Remember that, ideally, active learning should finish asking for labels before all the unlabeled instances are labeled, so that there would be some sense in going into all the trouble of forming an active learner. This step finds that stopping point before asking for all the labels. QUICK labels instances from the most popular to the least popular and adds each instance to the so-called active pool. QUICK stops asking for labels if one of the following rules fire:

1. All instances with Pop(j) ≥ 1 are exhausted (i.e., QUICK never labels unpopular instances).

2. Or if there is no estimation accuracy improvement in the active pool for n consecutive times.

3. Or if the Δ between the best and the worst error of the last n instances in the active pool is very small.

For the error measure in point #3, we used MRE; in other words, the magnitude of relative error (abs(actual − predicted)/actual). MRE is only one of many possible error measures. As shown below, even though we guide the search using only MRE, the resulting estimations score very well across a wide range of error measures. During the implementation of the algorithm, a practitioner should feel free to opt for the most appropriate learner for his domain. In the experiments that we will report in this chapter, we used n = 3 and Δ < 0.1. The selection of (n, Δ) values is based on our engineering judgment, so refrain from seeing these values as absolute. The sensitivity analysis of trying different values of (n, Δ) can reveal the best values for a different domain.

18.3.3 Seeing quick in action with a toy example

The above pseudocode and formulation probably makes things clearer for the reader; however, personally we find it very helpful to view an algorithm in action with a small example. This subsection provides such an example. Assume that the training set of the example consists of three instances/projects: P₁, P₂, and P₃. Also assume that these projects have one dependent and three independent features. Our data set would look like Figure 18.1.

18.3.3.1 Phase 1: Synonym pruning

Step 1: Transpose data set matrix. After normalization to 0-1 interval, then transposing our data set, the resulting matrix would look like Figure 18.2.

Step 2: Generate distance-matrices. The distance matrix DM keeps the Euclidean distance between features. The matrix of Figure 18.2 is used to calculate the DM of Figure 18.3.

Step 3: Generate E_NN and E(1) matrices. According to the distance matrix of Figure 18.3, the resulting E_NN[i, j] of Figure 18.4 shows the neighbor ranks of features. Using E_NN we calculate the E(1) matrix that identifies the features that have at least another nearest neighbor. E(1) matrix is given in Figure 18.5.

Step 4: Calculate the popularity index based on E(1) and select nonpopular features. Popularity of a feature is the total of E(1)'s columns (see the summation in Figure 18.5). Nonpopular features are the ones with zero popularity. In this toy example, we only select Feat₃, as it is the only column with zero popularity.

18.3.3.2 Phase 2: Outlier removal and estimation

In this phase, QUICK continues execution with only the selected features. After the first phase, our data set now looks like Figure 18.6.

Since our data now has only one independent variable, we can visualize it on a linear scale as in Figure 18.7.

Step 1: The first step of QUICK in this phase is to build the distance matrix. Because projects are described by a single attribute Feat₃ (say KLOC), the Euclidean distance between two projects will be the difference between the normalized KLOC values. The resulting distance-matrix is given in Figure 18.8.

Step 2: Creating the E_NN matrix based on the distance matrix is the second step. As we are creating the E_NN matrix we traverse the distance matrix row-by-row and label the instances depending on their distance order: closest neighbor is labeled 1, the second closest neighbor is labeled 2, and so on. Note that diagonal entries with the distance values of 0 are ignored, as they represent the distance of the instance to itself, not to a neighbor. After this traversal, the resulting E_NN is given in Figure 18.9.

Step 3: Calculating the popularity index based on E_NN and determining the labeling order is the final step of the algorithm. Remember from the previous section that E(1) is generated from E_NN: E(1)[i, j] = 1 if E_NN[i, j] = 1; otherwise, E(1)[i, j] = 0. The popularity index associated with each instance is then calculated by summing the values in every column (i.e., the sum of the first column is the popularity index of the first instance, the sum of the second column is the popularity index of the second instance, and so forth). The E(1) matrix and the popularity indices of our example is given in Figure 18.10. Note that E(k) matrices are not necessarily symmetric; see that E(1) of Figure 18.10 is not symmetric.

In our data set example, Figure 18.10 produces the labeling order of the instances {P₁, P₂, P₃}. In other words, in the first round we will ask our expert to label P₁ and place that label in the active pool. In that round, because the active pool contains only 1 labeled instance it will be the closest labeled neighbor of every test instance and the estimates for all the test instances will be the same (the label of P₁).

In the second round, P₂ will be labeled by the expert and placed into a pool of “active” (i.e., labeled) examples. This time the test instances will have two alternatives to choose their closest-neighbor from; hence, the estimates will be either the label of P₁ or the label of P₂. Finally, the expert will label P₃ and place it into the active pool. The change of the active pool is shown in Figure 18.11. Note that we only move from Round_i to Round_i+1 if the stopping rules (described above) do not fire.

18.5.1 Performance

Before we start looking at the plots of performance vs. number of labeled training instances, we will walk through a sample plot step-by-step to explain how to interpret these plots. Figure 18.12 is a sample plot that is derived from an actual representative data set (shown is the desharnais data set). Figure 18.12 is the result of QUICK's synonym pruning (four features are selected for the sample desharnais data set) followed by labeling N′ instances in decreasing popularity. Here is how we can read Figure 18.12:

• Y-axis is the logged MdMRE error measures: The smaller the value the better the performance. In case MdMRE is not the ideal error measure for a practitioner's problem domain, he/she should feel free to switch it with an appropriate error measure.

• The line with star-dots shows the error seen when i^th instance was estimated using the labels 1,…, (i − 1), i.e., each instance can only use the i − 1 labeled instances in the active pool.

• The horizontal lines show the errors seen when estimates were generated using all the data (either from CART or passiveNN).

• The vertical line shows the point where QUICK advised that labeling can stop (i.e., N′). Recall that QUICK stops asking for labels if one of the predefined rules fire.

• The square-dotted line shows randNN, which is the result of picking any random instance from the training set and using its effort value as the estimate.

Figure 18.12 shows that QUICK uses a considerably smaller number of labeled instances with fewer features. But of course the reduction in the labels and features would not have much meaning unless QUICK can also show a high performance. However, to observe the possible scenarios we cannot make use of Figure 18.12 any more for two reasons: Repeating Figure 18.12 for 7 error measures × 17 data sets would consume too much space without conveying any new information and more importantly, Figure 18.12 does not tell whether or not differences are significant; e.g., see Tables 18.5, 18.6 showing that performance differences among QUICK, passiveNN, and CART are not significant for the desharnais data set. Therefore, we will continue our performance analysis with summary tables in the following subsections.

18.5.2 Reduction via synonym and outlier pruning

Table 18.4 shows reduction results from all 18 data sets used in this study. The N column shows the size of the data and the N′ column shows how much of that data was labeled by QUICK. The $\frac{N^{\prime }}{N}$ column expresses the percentage ratio of these two numbers. In a similar fashion, F shows the number of independent features for each data set, whereas F′ shows the number of selected features by QUICK. The $\frac{F^{\prime }}{F}$ ratio expresses the percentage of selected features to the total number of the features. The important observation of Table 18.4 is that, given N projects and F features, it is neither necessary to collect detailed costing details on 100% of N nor is it necessary to use all the features. For nearly half the data sets studied here, labeling around one-third of N would suffice (median of $\frac{N^{\prime }}{N}$ for 18 data sets is 32.5%). There is a similar scenario for the amount of features required. QUICK selects around one-third of F for half the data sets. The median value of $\frac{F^{\prime }}{F}$ for 18 data sets is 38%.

Table 18.4

The Essential Content of the SEE Data Sets Used in Our Experimentation (From Ref. [231].)

Data Set	N	N′	$\frac{N^{\prime }}{N}$	F	F′	$\frac{F^{\prime }}{F}$	$\frac{N^{\prime }*F^{\prime }}{N*F}$
nasa93	93	21	23%	16	3	19%	4%
cocomo81	63	11	17%	16	6	38%	7%
cocomo81o	24	13	54%	16	2	13%	7%
maxwell	62	10	16%	26	13	50%	8%
kemerer	15	4	27%	6	2	33%	9%
desharnais	81	19	23%	10	4	40%	9%
miyazaki94	48	17	35%	7	2	29%	10%
desharnaisL1	46	12	26%	10	4	40%	10%
nasa93_center_5	39	11	28%	16	6	38%	11%
nasa93_center_2	37	16	43%	16	4	25%	11%
cocomo81e	28	9	32%	16	7	44%	14%
desharnaisL2	25	6	24%	10	6	60%	14%
sdr	24	10	42%	21	8	38%	16%
desharnaisL3	10	6	60%	10	3	30%	18%
nasa93_center_1	12	4	33%	16	9	56%	19%
cocomo81s	11	7	64%	16	5	31%	20%
finnish	38	17	45%	7	4	57%	26%
albrecht	24	9	38%	6	5	83%	31%

The essential content of a data set D with N instances and F independent features would be the ratio of its actual features and instances to the selected features (F′) and selected instances (N′), i.e., $\frac{N^{\prime }*F^{\prime }}{N*F}$.

The combined effect of synonym and outlier pruning becomes clearer when we look at the last column of Table 18.4. Assuming that a data set D of N instances and F independent features is defined as an N-by-F matrix, the reduced data set D′ is a matrix of size N′-by-F′. The last column shows the total reduction provided by QUICK in the form of a ratio: $\frac{N^{\prime }*F^{\prime }}{N*F}$. The rows of Table 18.4 are sorted according to this ratio. Note that the maximum size requirement (albrecht data set) is only 32% of the original data set and with QUICK we can go as low as only 4% of the actual data set size (nasa93).

18.5.3 Comparison of QUICK vs. CART

Figure 18.15 shows the PRED(25) difference between CART (using all the data) and QUICK (using just a subset of the data). The difference is calculated as PRED(25) of CART minus PRED(25) of QUICK. Hence, a negative value indicates that QUICK offers better PRED(25) estimates than CART. The left-hand side (starting from the value of −35) shows QUICK is better than CART, whereas in other cases CART outperformed QUICK (see the right-hand side until the value of +35).

From Figure 18.15 we see that 50th percentile corresponds around the PRED(25) value of 2, which means that at the median point the performance of CART and QUICK are very close. Also note that 75th percentile corresponds to less than 15, meaning that for the cases when CART is better than QUICK the difference is not dramatic.

18.5.4 Detailed look at the statistical analysis

Tables 18.5, 18.6 compare QUICK to passiveNN and CART using 7 error measures. Smaller values are better in these tables, as they show the number of losses: A method loses against another method if its performance is worse than the other method and if the two methods are statistically significantly different from one another. When calculating “loss” for six of the measures, “loss” means higher error values. On the other hand, for PRED(25), “loss” means lower values. The last column of each table sums the losses associated with the method in the related row.

Table 18.5

QUICK (on the Reduced Data Set) vs. passiveNN (on the Whole Data Set) with Regard to the Number of Losses, i.e., Lower Values are Better

The right-hand column sums the number of losses. Rows highlighted in gray show data sets where QUICK performs worse than passiveNN in the majority case (4 times out of 7, or more). Note that only 1 row is highlighted.

Table 18.6

QUICK (on the Reduced Data Set) vs. CART (on the Whole Data Set) with Regard to the Number of Losses, i.e., Lower Values are Better

The right-hand column sums the number of losses. Gray rows are the data sets where QUICK performs worse than CART in the majority case (4 times out of 7, or more).

By sorting the values in the last column of Table 18.5, we can show that the number of losses is very similar to the nearest neighbor results:

The gray rows of Table 18.5 show the datasets where QUICK loses over most of the error measures (4 times out of 7 error measures, or more). The key observation here is that, when using nearest-neighbor methods, a QUICK analysis loses infrequently (only 1 gray row) compared to a full analysis of all projects.

As noted in Figure 18.15, QUICK has a close performance to CART. This can also be seen in the number of losses summed in the last column of Table 18.6. The 4 gray rows of Table 18.6 show the data sets where QUICK loses most of the time (4 or more out of 7) to CART. In just 4/18 = 22% of the data sets is a full CART analysis better than a QUICK partial analysis of a small subset of the data. The sorted last column of Table 18.6:

18.5.5 Early results on defect data sets

To question the robustness of QUICK, we also adapted it to defect prediction (which is a classification problem unlike SEE). The data set and the statistical comparison of QUICK to other methods is provided in Table 18.8. We compared QUICK to successful learners in defect prediction domain such as CART, k-NN (i.e., passiveNN), as well as Naive Bayes. Because defect prediction is a classification problem, we used different evaluation criteria: Let A, B, C, D denote the true negatives, false negatives, false positives, and true positives, respectively. Then p_d = (D/(B + D)) and p_f = (C/(A + C)), where p_d stands for probability of detection and p_f stands for probability of false alarm rate. We combined the p_d and p_f into a single measure called the G-value, which is the harmonic mean of the p_d and (1 − p_f) values (Table 18.7).

Table 18.7

QUICK's Sanity Check on 8 Company Data Sets (Company Codes are C1, C2,…, C8) from Tukutuku

Cases where QUICK loses for the majority of the error measures (4 or more) are highlighted. QUICK is statistically significantly the same as CART for 5 out of 8 company data sets for the majority of the error measures (4 or more). Similarly, QUICK is significantly the same as passiveNN for 5 out of 8 company data sets.

Table 18.8 shows whether QUICK is statistically significantly better than the compared method (according to the Cohen significance test). As can be seen, in 18 out of 32 comparisons, QUICK (that uses only a small fraction of the labels) is comparable or better than the supervised methods (that use all the labeled data). This is a good indicator that the performance of QUICK-like active learning solutions are transferable. The results of Table 18.8 is part of an ongoing study; hence, we will not go deep into other aspects of the results of QUICK's performance on defect data sets.