\section{Predicting Student Retention}

\subsection{Building the Experiment}   

    To construct the experiment, certain aspects were first determined to be pertinent in the final selection of top, actionable attributes in the data. The following represents brief explanations of each method used. Results obtained from a combination of which are then analyzed.

\subsection{Number of Attributes}

An attribute in the data could be something such as GPA, or ZIPCODE. The number of attributes to select is crucial in the analysis of the data, because it allows us to conclude how many of the attributes selected we should concentrate on. This is central in selecting actionable attributes. For example, suppose a data set consists of 1000 attributes, but the results from experimentation find that only 15 of the 1000 are actually important. The bulk of subsequent attention could then be spent on what actions to take based on the 15 found, as opposed to the rest of the 985. 

In this experiment, I chose n to be the number of attributes selected in increments of 5. Thus, with a maximum of 103 attributes in each data set used in the experiment, 20 different intervals of n were chosen by our feature subset selectors (described below).

\subsection{Classifiers} 

Classifiers are used in data mining by employing machine learning techniques in order to learn patterns in data. Once these patterns are learned, we can then begin to attempt to predict outcomes in the data by reflecting on data that has already been examined. We can also determine how well a classifier predicts for the data. This is done by learning on a certain portion of the data, and reflecting on how well predictions are made by another portion of the data that has not yet been seen in the learning process. By examining overall performance, we can make a statement about how much better one classifier predicts on a specific data set than another.

\begin{itemize}
\item{\nbc - A naive Bayes classifier is a simple and fast probabilistic classifier that uses Bayes' theorem to classify training data. Bayes' theorem, as shown in Equation~\ref{eq:bayesTheorem}, determines the probability $P$ of an event $H$ occurring given an amount of evidence $E$. The classifier also assumes feature independence; the algorithm examines features independently to contribute to probabilities, as opposed to the assumption that features depend on other features. Surprisingly, even though feature independence is an integral part of the classifier, it often outperforms many other learners ~\cite{NB-performance}.}

\begin{equation}
  Pr(H|E) = \frac{Pr(E|H) * Pr(H)}{Pr(E)}
\label{eq:bayesTheorem}
\end{equation}

\item{C4.5 - C4.5~\cite{quinlanC4.5} is a type of classifier known as a decision tree, and is an extension to the ID3~\cite{quinlanID3} algorithm. A decision tree~\cite{Mitchell97DescTree} (shown in Figure~\ref{fig:decisionTree}) is constructed by first determining the best attribute to make as the root node of the tree. ID3 decides this root attribute by using one that best classifies training examples based upon the attribute's information gain (described below). Then, for each value of the attribute representing any node in the tree, the algorithm recursively builds child nodes based on how well another attribute from the data describes that specific branch of its parent node. The stopping criteria are either when the tree perfectly classifies all training examples, or until no attribute remains unused. C4.5 extends ID3 by making several improvements, such as the ability to operate on both continuous as well as discrete attributes, training data that contains missing values for a given attribute(s), and employ pruning techniques on the resulting tree.}

\begin{figure}
\begin{center}
\includegraphics[width=6.5in]{figures/Investment_decision_tree.png}
\end{center}
\caption{A decision tree consists of a root node and descending children nodes who denote decisions to make in the tree's structure. This tree, for example, was constructed in an attempt to optimize investment portfolios by minimizing budgets and maximizing payoffs. The top-most branch represents the best selection in this example.}
\label{fig:decisionTree}
\end{figure}

\item{One-R - One-R, described in~\cite{holte93}, builds rules from the data by iteratively examining each value of an attribute and counting the frequency of each class for that attribute-value pair. An attribute-value is then assigned the most frequently occurring class. Error rates of each of the rules can then be calculated, and the best rules can be ranked based on the lowest error rates.}
\item{Zero-R - Often used to evaluate the success of other classification algorithms, Zero-R is an extremely simple algorithm that gives the majority class from the training data.}
\item{Alternating Decision Trees - ADTrees~\cite{Freund99thealternating} are decision trees that contain both decision nodes, as well as prediction nodes. Decision nodes specify a condition, while prediction nodes contain only a number. Thus, as an example in the data follows paths in the ADTree, it only traverses branches whose decision nodes are true. The example is then classified by summing all prediction nodes that are encountered in this traversal. ADTrees, however, differ from binary classification trees, such as C4.5, in that in those trees an example only traverses a single path down the tree.}

\begin{figure}
\begin{center}
\includegraphics[width=4.5in]{figures/bayesnet_diagram.png}
\end{center}
\caption{In this simple bayesian network, the variable {\em Sprinkler} is dependent upon whether or not its raining; the sprinkler is generally not turned on when it's raining. However, either event is able to cause the grass to become wet - if it's raining, or if the sprinkler is caused to turn on. Thus, Bayesian networks excel at investigating information relating to relationships between variables.}
\label{fig:bayesnetwork}
\end{figure}


\item{Bayesian Network - Bayesian networks, illustrated in Figure ~\ref{fig:bayesnetwork}, are graphical models that use a directed acyclic graph (DAG) to represent probabilistic relationships between variables. 
As stated in~\cite{Heckerman96atutorial} Bayesian networks have four important elements to offer:
\begin{enumerate}
\item{Incomplete data sets can be handled well by Bayesian networks. Because the networks encode a correlation between input variables, if an input is not observed, in will not necessarily produce inaccurate predictions, as would other methods.} 
\item{Causal relationships can be learned about via Bayesian networks. For instance, if an analyst wished to know if a certain action taken would produce a specific result, and also to what degree.}
\item{Bayesian networks promote the amalgamation of data and domain knowledge by allowing for a straightforward encoding of causal prior knowledge, as well as the ability to encode causal relationship strength.}
\item{Bayesian networks avoid over fitting of data, as "smoothing" can be used in a way such that all data that is available can be used for training.}
\end{enumerate}
\item{Radial Basis Function Network - A radial basis function network (RBFN)~\cite{rbfnIntroBors} is a type of network called an artificial neural network (ANN). However, RBFNs are specialized in that they utilize a radial basis function as an activation function. An ANN's activation function is used in order to offer non-linearity to the network. This is important for multi-layer networks containing many hidden layers, because their advantages lie in their ability to learn on non-linearly separable examples.}}
\end{itemize}

\subsection{Feature Subset Selectors} 

Feature Subset Selection (FSS) methods provide ways to determine how important the attributes (or features) are in the data set, and how we can keep the best scoring ones, and throw out the rest. However, we must experiment with varying FSS procedures, because each method can return strikingly different results. Thus, just by experimenting with attributes selected from a handful of FSS, we are not left with a sense of how well attributes were selected from a data set compared to other feature selection tools. 

A brief overview of the FSS methods used in this study were as follows:

\begin{itemize}
\item{CFS - Correlation-Based Feature Selection~\cite{Hall00correlation-basedfeature} begins by constructing a matrix of feature to feature, and feature-to-class correlations. It then uses a best first search by expanding the best subsets until no improvement is made, in which case the search falls to the unexpanded subset having the next best evaluation until a subset expansion limit is met.}  
\item{Information Gain - Information Gain works by using a concept from information theory known as entropy. Entropy measures the amount of uncertainty, or randomness, that is associated with a random variable. Thus, high entropy can be seen as a lack of purity in the data. Information gain, as described in~\cite{Mitchell97} is an expected reduction of the entropy measure that occurs when splitting examples in the data using a particular attribute. Therefore an attribute that has a high purity (high information gain) is better at describing the data than one with a low purity. The resulting attributes are then ranked by sorted their information gain scores in a descending order.}
\item{Chi-squared - Attributes can also be ranked using the chi-squared statistic. The chi-squared statistic~\cite{Moore06} is used in statistical tests to determine how distributions of variables are different from one another. Note that these variables must be categorical in nature. Thus, the chi-squared statistic can evaluate an attribute's worth by calculating the value of this statistic with respect to a class. Attributes can then be ranked based on this statistic.}
\item{One-R - One-R (as described above), can also be used to deliver top-ranking attributes. Since each rule contains one attribute and a corresponding value, we can evaluate attributes by sorting them based on the error rate of the rule associated with that attribute-value pair. Using this, top attributes are those whose rules result in the lowest error rates.}
\end{itemize}

\subsection{Cross-Validation}
In the process of experimentation, it is crucial to determine a method's performance. Using performance criteria, further analysis can be conducted on experimental results to aid in the search for an optimal solution. Cross-validation provides the ability to discover how well a classifier performs on any given data set or a treatment of that data set. This is conducted by randomly partitioning the data into two subsets, called the training set, and the testing set. Specifically for this experiment, the data prior to partitioning has been reduced given n attributes selected using an FSS method.

In the learning phase, only the training subset is used by the classifier. The testing set is then used to determine how well the concepts learned from the training phase can be applied to unseen data. However, to reduce variability, the partitioning of the data and reclassification of resulting subsets is generally conducted multiple times. In this experiment, for example, a 5 X 5 cross-validation was performed. This means that five times I partitioned the data into a testing set consisting of $\frac{1}{5}$-th of the data, and a training set of $\frac{4}{5}$-ths of the data. After the five rounds, median values of the validation results are examined, and are assigned to a particular combination of the above facets.

\subsection{Analysis of Experimental Results}

\subsection{Evaluation Metrics}
The evaluation metrics used in this experiment are standard in data mining to measuring the performance of a method. These are represented as probability of detection (PD), probability of false alarm (PF), and variance. PD denotes the probability that the classifier will predict correctly for a given class, given both its correct and incorrect predictions. Thus, PD values should be maximized. PF, on the other hand, is the probability that the classifier will predict incorrectly for a given class, also given its correct and incorrect predictions. For this reason, PF results should be minimized.

Variance was also used in the experiment based on PD and PF values independently as an extra means of determining performance. Variance in these values provides insight into how much reliability a classifier supports on the data. For example, if a method's PD values range from very low to very high, we can determine that the particular method is not consistent in its probabilities of detection. Therefore, it is desired to have a very small variance in both PD and PF values. 

\begin{figure}
\centering
\includegraphics{figures/ret1_pd.pdf}
\includegraphics{figures/ret1_pf.pdf}
\caption{Probability of Detection (PD) and Probability of False Alarm (PF) with variances for first year retention.}
\label{fig:ret1graphs}
\end{figure}

\begin{figure}
\centering
\includegraphics{figures/ret2_pd.pdf}
\includegraphics{figures/ret2_pf.pdf}
\caption{Probability of Detection (PD) and Probability of False Alarm (PF) with variances for second year retention.}
\label{fig:ret2graphs}
\end{figure}

\begin{figure}
\centering
\includegraphics{figures/ret3_pd.pdf}
\includegraphics{figures/ret3_pf.pdf}
\caption{Probability of Detection (PD) and Probability of False Alarm (PF) with variances for third year retention.}
\label{fig:ret3graphs}
\end{figure}

\subsection{Visualizing the Results}  
     Figures~\ref{fig:ret1graphs},~\ref{fig:ret2graphs}, and~\ref{fig:ret3graphs} show the PD and PF median results for first, second and third year retention against the variance of these values. Each point represents a specific combination of the number of attributes selected, the feature subset selector used to select them, and the classifier used to train on the resulting data. For example, one point on a graph could be seen as 50/Information Gain/Naive Bayes, where 50 denotes the number of attributes used. The color of each point shows the number of attributes used for that particular combination representing that point. 

    The horizontal line segmenting the PD graphs are given as a baseline reference designated by the already existing retention rates in the data. Thus, to predict for retention in a given year, it is desirable to yield results higher than the baseline. As can be seen in the figures, the median probability of detection of retention values for the first year do not meet the baseline, and therefore we can assume that first year retention cannot accurately be predicted for using our methods. Second year retention provides better results than first year retention, but these results are hardly significant. For example, most of the points lie at or below the baseline. For this reason, second year retention is also not considered in further analysis. Lastly, third year PD values successfully exceed the baseline, and so require more thorough examination.  

\subsection{Narrowing the Search}

    From the visualizations described above, we can narrow our space of possible combinations to examine for third year retention. The graphs for PD and PF medians show that the range of number of attributes that maximizes PD and minimizes PF values while maintaining minimal variance is approximately 20 to 60. This is significant, as it allows filtering of the results so that concentration can be placed on only treatments whose attribute numbers lie in this range. 

\subsubsection{Ranking with the Mann-Whitney Test}

        At the moment of pruning the results based on attribute ranges, we are left with many combinations to be analyzed. In order to rank each combination, I performed a statistical Mann-Whitney test at 95\% confidence in order to rank a treatment. A rank is determined by how many times a combination wins compared to another. The method that won the most number of times is then given the highest rank. The table in Figure~\ref{fig:ranktable} shows the top ten ranking combinations based on a PD performance measure. Note that identical ranks are given to those treatments whose win value is equal in magnitude. 

\begin{figure}
  \begin{center}
    \rowcolors{1}{gray!10}{}
    \begin{tabular}{| c | c | c | c |}
      \hline
      Rank & Number of Attributes & FSS & Classifier \\
      \hline
      61&         30&oneR&bnet \\ \hline
      61&50&cfs&adtree \\ \hline
      57&       50&oneR&adtree \\ \hline
      56&       30&oneR&adtree \\ \hline
      55&        30&cfs&adtree \\ \hline 
      52&         50&oneR&bnet \\ \hline
      51&   30&infogain&adtree \\ \hline
      51&          30&cfs&bnet \\ \hline
      48&   50&infogain&adtree \\ \hline
    \end{tabular}
  \end{center}
  \caption{The top ten ranking treatments for third year retention. Ranks represent how many times a particular treatment wins over all other treatments in the experiment.}
  \label{fig:ranktable}
\end{figure}

\subsection{Selected FSS and Classifier}

    Figure~\ref{fig:ranktable} shows the top-most ranking combination of FSS and classifier is obtained by either using 30 attributes, or 50. Since, the two numbers of attributes (along with their own FSS and classifier) result in the same Mann-Whitney rank, we can make the statement that the two are statistically similar, and thus by focusing on only 30 attributes selected, we can concentrate on approximately 1/3 of the original data.  Thus, our analysis of the results show that 30 attributes selected using One-R as the feature subset selection method are the most critical to third year retention.  

\section{Analyzing the Scalability of Clustering Text Documents}

As stated above, the purpose of this experiment conducted for this thesis is to verify if lightweight data mining
methods perform worse than more thorough and rigorous ones.

The data sets used in this experiment are:

\begin{itemize}
\item EXPRESS schemas: AP-203, AP-214
\item Text mining datasets: BBC, Reuters, The Guardian (multi-view text datasets), 20 Newsgroup subsets:
sb-3-2, sb-8-2, ss-3-2, sl-8-2%\footnotetext[1]{\url{http://mlg.ucd.ie/datasets}}.
\end{itemize}

\subsubsection{Classes of Methods }

This experiment compares different {\em row} and {\em column} reduction methods. Given a table of data where
each row is one example and each columns counts different features, then:
\bi
\item
Row reduction methods {\em cluster} related rows into the same group;
\item
Column reduction methods remove columns with little information.
\ei

Reduction methods are essential in text mining. For example:
\bi
\item
 A standard text mining corpus may store information
in tens of thousands of columns. For such data sets, column reduction is an essential first step before any other
algorithm can execute

%\begin{quote}
%  One of the problems with high-dimensional datasets is that, in many cases, 
%not all the measured variables are ``important'' for understanding the underlying 
%phenomena of interest.
%\end{quote}
\item
The process of clustering data into similar groups can be used in a wide variety of applications, such as:
\begin{itemize}
  \item Marketing: finding groups of customers with similar behaviors given a large database of customer data
  \item Biology: classification of plants and animals given their features
  \item WWW: document classification and clustering weblog data to discover groups of similar access patterns\footnotetext[2]{\url{http://home.dei.polimi.it/matteucc/Clustering/tutorial_html/}}.
\end{itemize}
\ei

%Thus the purpose of clustering is to ``determine the intrinsic grouping in a set of unlabeled data'' 
%XXXX adam. what does this do? \footnotemark[\value{footnote}]. 

%XXXX adam remove the following?
%Data can sometimes be overwhelmingly large, containing a great number of attributes, or dimensions. In order to reduce this vast multidimensional space, there exist dimensionality reduction methods. Dimensionality reduction filters the attributes, and attempts to select the most valid ones. In ``A Survey of Dimension Reduction Techniques'' \footnotetext[3]{\url{https://e-reports-ext.llnl.gov/pdf/240921.pdf}} by I.K. Fodor, Fodor writes:
%XXX make it a reference


\subsubsection{The Algorithms}

While there are many clustering algorithms used today, this experiment focused on three: a naive K-Means implementation, GenIc~\cite{genic04}, and clustering using canopies~\cite{canopies00}:
\be
\item
K-means, a special case of a class of EM algorithms, works as follows:
\begin{enumerate}
\item{Select initial {\em K} centroids at random;}
\item{Assign each incoming point to its nearest centroid;}
\item{Adjusts each cluster's centroid to the mean of each cluster;}
\item{Repeat steps 2 and 3 until the centroids in all clusters stop moving by a noteworthy amount}
\end{enumerate}
Here we use a naive implementation of K-means, requiring {\em K}*{\em N }*{\em I} comparisons, where {\em N} and {\em I} represent the total number of points and maximum iterations respectively.
\item
GenIc is a single-pass, stochastic clustering algorithm. It begins by initially selecting {\em K} centroids at random from all instances in the data. At the beginning of each generation, set the centroid weight to one. When new instances arrive, nudge the nearest centroid to that instance and increase the score for that centroid. In this process, centroids become ``fatter'' and slow down the rate at which they move toward newer examples. When a generation ends, replace the centroids with less than {\em X} percent of the max weight with {\em N} more random centroids. Genic
repeats for many generations, then returns the highest scoring centroids.
\item
Canopy clustering, developed by Google, reduces the need for comparing all items in the data using an expensive distance measure, by first partitioning the data into overlapping subsets called {\em canopies}. Canopies are first built using a cheap, approximate distance measure. Then, more expensive distance measures are used inside of each canopy to cluster the data. 
\ee
As to column reduction, I will focus on two methods:

\be
\item
PCA, or Principal Components Analysis, is a reduction method that
treats every instance in a data set as a point in N-dimensional
space. PCA looks for new dimensions that better fit these points-- by mapping data points to these new dimensions where the variance is found to be maximized. Mathematically, this is conducted by utilizing eigenvalue decompositions of a
data covariance matrix or singular value decomposition of a data
matrix.
\fig{pca} shows an example of PCA.  Before, on the left-hand-side, the data exists in a two-dimensional
space, neither of which captures the distribution of the data. Afterwards, on the right-hand-side, a new dimension
has been synthesized that is more relevant to the data distribution.
\begin{figure}
\begin{center}
\includegraphics[width=2.25in]{figures/cs-pca.pdf}
\end{center}
\caption{A PCA dimension feature.}\label{fig:pca}
\end{figure}
\item
TF-IDF, or term frequency times inverse document frequency, reduces the number of terms (dimensions) by describing how important a term is in a document (or collection of documents) by incrementing its importance according to how many times the term appears in a document. However, this importance is also offset by the frequency of the term in the entire corpus. Thus, we are concerned with only terms that occur frequently in a small set of documents, and very infrequently everywhere else. To calculate the Tf*IDF value for each term in a document, I use the following equation:
\begin{equation} 
Tf*df(t,D_j) = \frac{tf(t_i,D_j)}{|D_j|}log(\frac{|D|}{df(t_i)})
\end{equation}

where $tf(t_i,D_j)$ denotes the frequency of term $i$ in document $j$, and $df(t_i)$ represents the number of documents containing term $i$. Here, $|D|$ denotes the number of documents in the corpus. To reduce all terms (and thus, dimensions), we must find the sum of the above
\begin{equation}
Tf*Ifd_{sum}(t) = \sum_{D_j\epsilon D}Tf*Idf(t,D_j)
\end{equation}
\ee

In theory, TF*IDF and GenIc should perform worse than K-Means, canopy clustering and PCA:
\bi
\item
Any single-pass algorithm  like GenIc
can be confused by ``order effects''; i.e. if the data arrives in some confusing order then the
single-pass algorithm can perform worse than other algorithms that are allowed to examine all the data. 
\item
TF*IDF is a heuristic method while PCA is a well-founded mathematical technique
\ei
On the other hand, the more rigorous methods are slower to compute:
\bi
\item Computing the correlation matrix used by PCA requires at least a $O(N^2)$ calculation.
\item As shown below, K-means is much slower than the other methods studied here.
\ei

\subsubsection{Building the Experiment}

This experiment was conducted entirely with OURMINE using a collection of BASH scripts, as well as custom Java code. The framework was built as follows:

\begin{enumerate}
\item{A command-line API was developed in Java for parsing the data, reducing/clustering the data, and outputting the data. Java was chosen due to its preferred speed for the execution of computationally expensive instructions.}
\item{The data was then iteratively loaded into this Java code via shell scripting. This provides many freedoms, such as allowing parameters to be altered as desired, as well as outputting any experimental results in any manner seen fit.}
\end{enumerate}


\fig{clusterworker} shows the OURMINE code for clustering data using the K-means algorithm. Shell scripting provides us with much leverage in this example. For instance, by looking at Lines 2-5, we can see that by passing the function four parameters, we can cluster data in the range from {\em minK} to {\em maxK} on all data in {\em dataDir}. This was a powerful feature used in this experiment, because it provides the opportunity to run the clusterer across multiple machines simultaneously. As a small example, suppose we wish to run K-means across three different machines with a minimum {\em K} of 2 and a maximum {\em K} of 256. Since larger values of {\em K} generally yield longer runtimes, we may wish to distribute the execution as follows:

\begin{verbatim}
Machine 1: clusterKmeansWorker 256 256 0 dataDir
Machine 2: clusterKmeansWorker 64 128 2 dataDir
Machine 3: clusterKmeansWorker 2 32 2 dataDir
\end{verbatim}

Lines 9-13 of \fig{clusterworker} load the data from {\em dataDir} for every {\em k}, and formats the name of the output file. Then, lines 15-19 begin the timer, cluster the data, and output statistical information such as {\em k}, the dataset, and runtime of the clusterer on that data set. This file will then be used later in the analysis of these clusters.

\begin{figure}
{\scriptsize\begin{verbatim}
1 clusterKmeansWorker(){
2     local minK=$1
3     local maxK=$2
4     local incVal=$3
5     local dataDir=$4
6     local stats="clusterer,k,dataset,time(seconds)"
7     local statsfile=$Save/kmeans_runtimes
8     echo $stats >> $statsfile
9     for((k=$minK;k<=$maxK;k*=$incVal)); do
10         for file in $dataDir/*.arff; do
11             filename=`basename $file`
12             filename=${filename%.*}
13             out=kmeans_k="$k"_$filename.arff 
14             echo $out
15             start=$(date +%s.%N)
16             $Clusterers -k $k $file $Save/$out
17             end=$(date +%s.%N)
18             time=$(echo "$end - $start" | bc)
19             echo "kmeans,$k,$filename,$time" >> $statsfile
20         done
21     done
22 }\end{verbatim}}
\caption{An OURMINE worker function to cluster data using the K-means algorithm. Note that experiments using other clustering methods (such as GenIc and Canopy), could be conducted by calling line 16 above in much the same way, but with varying flags to represent the clusterer.}\label{fig:clusterworker}
\end{figure}

Similarly, the flags in line 16 can be changed to perform a different action, such as clustering using GenIc or Canopy, by changing {\em -k} to {\em -g} or {\em -c} respectively, as well as finding cluster similarities (as described below) and purities, by using {\em -sim} and {\em -purity} as inputs. 


Since any number of variables can be set to represent different libraries elsewhere in OURMINE, the variable \begin{verbatim} $Reducers \end{verbatim} is used for the dimensionality reduction of the raw dataset, as seen in \fig{tfidfworker}, whose overall structure is very similar to \fig{clusterworker}.

\begin{figure}
{\scriptsize\begin{verbatim}
1 reduceWorkerTfidf(){
2     local datadir=$1
3     local minN=$2
4     local maxN=$3
5     local incVal=$4
6     local outdir=$5
7     local runtimes=$outdir/tfidf_runtimes

8    for((n=$minN;n<=$maxN;n+=$incVal)); do
9        for file in $datadir/*.arff; do
10            out=`basename $file`
11            out=${out%.*}
12            dataset=$out
13            out=tfidf_n="$n"_$out.arff
14            echo $out
15            start=$(date +%s)
16            $Reducers -tfidf $file $n $outdir/$out
17            end=$(date +%s)
18            time=$((end - start))
19            echo "tfidf,$n,$dataset,$time" >> $runtimes
20        done
21    done
22 }\end{verbatim}}
\caption{An OURMINE worker function to reduce the data using TF-IDF.}\label{fig:tfidfworker}
\end{figure}

\subsection{Results}   

To determine the overall benefits of each clustering method, this experiment used both cluster similarities, as well as the runtimes of each method.

%\subsubsection{Purities}
%When we cluster data that already has classes available to us, we can determine cluster purity. A cluster is considered relatively ``pure'' if it contains a high percentage of points that share the same class. Thus, we can say that this is a measure of the ``{\em quality} of a clustering solution''\footnotetext[1]{\url{http://www.cse.iitm.ac.in/~cs672/purity.pdf}}. 
%To determine the purity of individual clusters, the equation
%\begin{equation}
%purity(C_a)=\frac{1}{|C_a|}*max(|C_a|_{cl=b})
%\end{equation}
%was used, where a cluster $C_a$  contains $|C_a|_{cl=b}$ number of points assigned to class $b$. However, a high purity using this equation always is easy to obtain. For instance, if a cluster contains only one instance from the dataset, the purity of that cluster is always 1. Therefore, this study uses a weighted sum of these purities
%\begin{equation}
%purity=\sum_{a=1}^k\frac{|C_a|}{|D|}*purity(C_a)
%\end{equation}
%where $|D|$ denotes the number of documents in the dataset.

%To determine cluster purities, the following text datasets were used in conjunction with their natural classes:
%\begin{itemize}
%\item BBC: 5 natural classes (business, entertainment, politics, sport, tech);
%\item BBCSPORT: 5 natural classes (athletics, cricket, football, rugby, tennis\footnotetext[1]{\url{http://mlg.ucd.ie/datasets/bbc.html}};
%\end{itemize}
%The results of the cluster purity experiments are shown in \fig{pur1} and \fig{pur2}. By examining these results, we can see that the more complete methods (in this case K-means) yields the highest weighted purity. However, since each data set and its class distribution can drastically alter the outcome of these values, it is sometimes beneficial to use fast heuristic methods, as seen in the results for the BBC data set.    

%XXX more discussion

%\begin{figure}
%\begin{center}
%\includegraphics[width=5.50in]{bbc_purities}
%\end{center}
%\caption{Normalized weighted purity sums of clusters on the BBC data set.}\label{fig:pur1}

%\end{figure}

%\begin{figure}
%\begin{center}
%\includegraphics[width=5.50in]{bbcsport_purities}
%\end{center}
%\caption{Normalized weighted purity sums of clusters on the BBCSport data set.}
%\label{fig:pur2}
%\end{figure}

\subsubsection{Similarities}

Cluster similarities tell us how similar points are, either within a cluster ({\em Intra}-similarity), or with members of other clusters ({\em Inter}-similarity). The idea here is simple: gauge how well a clustering algorithm groups similar documents, and how well it separates different documents. Therefore, intra-cluster similarity values should be maximized, while minimizing inter-cluster similarities. 

Similarities are obtained by using the cosine similarity between two documents. The cosine similarity measure defines the cosine of the angle between two documents, each containing vectors of terms. The similarity measure is represented as

\begin{equation}
sim(D_i,D_j) = \frac{D_i \cdot D_j}{||D_i|| ||D_j||} = cos(\theta)
\end{equation}

where $D_i$ and $D_j$ denote two term frequency vectors for documents $i$ and $j$, and where the denominator contains magnitudes of these vectors. 

 Cluster similarities are determined as follows:

\begin{itemize}
\item{Cluster intra-similarity: For each document $d$ in cluster $C_i$, find the cosine similarity between $d$ and all documents belonging to $C_i$}
\item{Cluster inter-similarity: For each document $d$ in cluster $C_i$, find the cosine similarity between $d$ and all documents belonging to all other clusters}
\end{itemize}

Thus the resulting sum of these values represents the overall similarities of a clustering solution. \fig{sims} shows the results from the similarity tests conducted in this experiment. The slowest clustering and reduction methods were set as a baseline, because it was assumed that these methods would perform the best. With intra-similarity and inter-similarity values normalized to 100 and 0 respectively, we can see that surprisingly, faster heuristic clustering and reduction methods perform just as well or better than more rigorous methods. $Gain$ represents the overall score used in the assessment of each method, and is computed as a method's cluster $intra$-similarity value minus its $inter$-similarity value. Thus, the conclusions from this experiment shows that fast heuristic methods are sufficient for large data sets due to their scalability and performance.   

\begin{figure}
\centering
\small
\begin{tabular}{| c | c | c | c | c |}
\hline
Reducer and Clusterer & Time & InterSim & IntraSim & Gain \\ \hline
TF-IDF*K-means & 17.52 & -0.085 & 141.73 & 141.82 \\ \hline
TF-IDF*GenIc & 3.75 & -0.14 & 141.22 & 141.36 \\ \hline
PCA*K-means & 100.0 & 0.0 & 100.0 & 100.0 \\ \hline
PCA*Canopy & 117.49 & 0.00 & 99.87 & 99.87 \\ \hline
PCA*GenIc & 11.71 & -0.07 & 99.74 & 99.81 \\ \hline
TF-IDF*Canopy & 6.58 & 5.02 & 93.42 & 88.4 \\ \hline
\end{tabular}
\caption{Experiment \#3 (Text mining). Similarity values normalized according to the combination of most rigorous reducer and clusterer. Note that $Gain$ is a value representing the difference in cluster intrasimilarity and intersimilarity.} 
\label{fig:sims}
\end{figure}

\section{Cross-Company Defect Prediction using Relevancy Filtering}

OURMINE was used to reproduce Turhan et al.'s experiment - with a\nbc classifier in conjunction with a k-Nearest Neighbor
(k-NN) relevancy filter. Relevancy filtering is used to group similar
instances together in order to obtain a learning set that is
homogeneous with the testing set. Thus, by using a training set
that shares similar characteristics with the testing set, it is
assumed that a bias in the model will be introduced. The k-NN filter
works as follows.  For each instance in the test set: \bi \item the
k nearest neighbors in the training set are chosen.  \item duplicates
are removed \item the remaining instances are used as the new
training set.  \ei

\subsubsection{Building the Experiment}

The entire script used to conduct this experiment is shown in \fig{promiseExp}. 
\begin{figure}
{\scriptsize\begin{verbatim}
1 promiseDefectFilterExp(){
2  local learners="nb"
3  local datanames="CM1 KC1 KC2 KC3 MC2 MW1 PC1"
4  local bins=10
5  local runs=10
6  local out=$Save/defects.csv
7  for((run=1;run<=$runs;run++)); do
8    for dat in $datanames; do
9	       combined=$Data/promise/combined_$dat.arff
10	       shared=$Data/promise/shared_$dat.arff
11	       blabln "data=$dat run=$run" 
12	       for((bin=1;bin<=$bins;bin++)); do
              rm -rf test.lisp test.arff train.lisp train.arff
13	           cat $shared | 
14	           logArff 0.0001 "1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19" > logged.arff
15	           makeTrainAndTest logged.arff $bins $bin
16	           goals=`cat $shared | getClasses --brief`

17	           for learner in $learners; do          
18		            blabln "WC"
19		            $learner train_shared.arff test_shared.arff | gotwant > produced.dat
20		            for goal in $goals; do
21		                extractGoals goal "$dat,$run,$bin,WC,$learner,$goal" `pwd`/produced.dat
24		            done
25		            blabln "WCkNN"
26		            rm -rf knn.arff
27		            $Clusterers -knn 10 test_shared.arff train_shared.arff knn.arff
28		            $learner knn.arff test_shared.arff | gotwant > produced.dat
29		            for goal in $goals; do
30		               extractGoals goal "$dat,$run,$bin,WCkNN,$learner,$goal" `pwd`/produced.dat                          
31             done
32		            blabln "CC"
33		            makeTrainCombined $combined > com.arff	
34		            cat com.arff | logArff 0.0001 "1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19" > logged.arff
35		            $learner logged.arff test_shared.arff | gotwant > produced.dat
36		            for goal in $goals; do
37		               extractGoals goal "$dat,$run,$bin,CC,$learner,$goal" `pwd`/produced.dat
38             done
39             blabln "CkNN"             
40             makeTrainCombined $combined > com.arff  
41             cat com.arff |
42             logArff 0.0001 "1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19" > logged.arff
43             $Clusterers -knn 10 test_shared.arff logged.arff knn.arff
44             $learner knn.arff test_shared.arff | gotwant > produced.dat
45             for goal in $goals; do
46                extractGoals goal "$dat,$run,$bin,CkNN,$learner,$goal" `pwd`/produced.dat
47             done
48    done
49  done
50  done ) | malign | sort -t, -r -n -k 12,12 > $out
\end{verbatim}}
\caption{The OURMINE script used in conducting the WC vs. CC experiment.}\label{fig:promiseExp}
\end{figure}


To begin, the data in this study were the same as used by Gay et
al.~\cite{gay09}; seven PROMISE defect data sets (CM1, KC1, KC2,
KC3, MC2, MW1, PC1) were used to build seven combined data sets
each containing $\frac{6}{7}$-th of the data. For instance, the
file {\em combined\_PC1.arff} contains all seven data sets {\em
except} PC1. This is used as the training set for the cross-company
(CC) data. For example, if we wished to learn on all training data
except for PC1, this would be a valid data set representation for
a cross-company experiment.

Next, as can be seen in line 15 of \fig{promiseExp}, a 10-way cross validation was conducted by calling $makeTrainAndTest$, which is a built-in OURMINE function that randomly shuffles the data and constructs both a test set, containing 10\% of the data, and a training set containing 90\% of the data. This was repeated ten times, and the resulting data was used in proceeding studies. For instance, in lines 18-24, the original test and training sets are used for the first WC study. However, in the WC experiment using relevancy filtering (lines 25-31), the same test set is used, but with the newly created training set. Lines 32-38 show the first CC study. This study is identical to the WC study except that as we saw before, we use $combined\_X.arff$ files, instead of $shared\_X.arff$.

I chose to use a\nbc classifier for this study because this is what was chosen in the original experiment conducted by Turhan et al. in ~\cite{turhan08}, as well as because\nbc has been shown to be competitive on PROMISE defect data against other learners ~\cite{lessmann08}.   


\subsubsection{Results}

Our results for this experiment can be found in \fig{pds} and \fig{pfs}. \fig{pds} shows $pd$ (probability of detection) values sorted in decreasing order, while \fig{pfs} shows $pf$ (probability of false alarm) values sorted in increasing order. These values are calculated as follows.
If $\{a,b,c,d\}$ are the
true negatives, 
false negatives, 
false positives, and 
true positives
(respectively) found by a binary detector then 
$pd=recall=\frac{d}{b+d}$ and
$pf=\frac{c}{a+c}$.
Note that a higher $pd$ is better, while a lower $pf$ is better. 


The last column of each figure shows quartile charts of the methods' $pd$ and $pf$ values. The black dot in the center of each plot represents the median value, and the line going from left to right from this dot show the second and third quartile respectively.

Column one of each figure gives a method its rank based on a Mann-Whitney test at 95\% confidence. A rank is determined by how many times a learner or learner/filter wins compared to another. The method that wins the most number of times is given the highest rank. 

%\begin{figure}
%\small
%\begin{center}
%\begin{tabular}{l@{~}|l@{~}|r@{~}r@{~}@{~}r@{~}|c}
%\multicolumn{2}{c}{~}&\multicolumn{5}{c}{quartiles}\\\cline{3-5}
%&min& & median & &max\\\cline{3-5}
%\multicolumn{2}{c}{~}&\multicolumn{3}{c}{pd}&2nd quartile\\
%\multicolumn{2}{c}{~}&\multicolumn{3}{c}{percentiles}&median,\\\cline{3-5}
%Rank&Treatment& 25\%& 50\% & 75\%&3rd quartile\\\hline
%1&WC (local data) + relevancy filter& 66& 73& 80&  \boxplot{0}{66}{73}{80}{3}  \\
%2&CC (imported data) + relevancy filter& 57& 71& 83&  \boxplot{0}{57}{71}{83}{5}  \\
%2&WC (local data)  & 59& 69& 83&  \boxplot{0}{59}{69}{83}{7}  \\
%3&CC (imported data)  & 49& 66& 87&  \boxplot{0}{49}{66}{87}{7}   \\\hline
%\multicolumn{5}{c}{~}&~~~~~0~~~~~~~~50~~~~100
%\end{tabular}
%\end{center}
%\caption{Probability of Detection (PD) results, sorted by median values.  }\label{fig:pds}
%\end{figure}
%\begin{figure}
%\small
%\begin{center}
%\begin{tabular}{l@{~}|l@{~}|r@{~}r@{~}@{~}r@{~}|c}
%%\multicolumn{2}{c}{~}&\multicolumn{5}{c}{quartiles}\\\cline{3-5}
%&min& & median & &max\\\cline{3-5}
%\multicolumn{2}{c}{~}&\multicolumn{3}{c}{pf}&2nd quartile\\
%\multicolumn{2}{c}{~}&\multicolumn{3}{c}{percentiles}&median,\\\cline{3-5}
%Rank&Treatment& 25\%& 50\% & 75\%&3rd quartile\\\hline
%1&CC (imported data) + relevancy filter& 17& 29& 43&  \boxplot{0}{17}{29}{43}{3}  \\
%1&CC (imported data)  & 13& 34& 51&  \boxplot{0}{13}{34}{51}{5} \\
%2&WC (local data)  & 17& 30& 41&  \boxplot{0}{17}{30}{41}{7}  \\
%3&WC (local data) + relevancy filter & 20& 27& 34&  \boxplot{0}{20}{27}{34}{8}  \\\hline
%\multicolumn{5}{c}{~}&~~~~~0~~~~~~~~50~~~~100
%\end{tabular}
%\end{center}
%\caption{Probability of False Alarm (PF) results, sorted by median values.  }\label{fig:pfs} \end{figure}

The following are important conclusions derived from these results:

\begin{itemize}
\item 
When CC data is used, relevancy filtering is crucial. According to our results, cross-company data with no 
filtering yields the worst $pd$ and $pf$ values.
\item{When relevancy filtering is performed on this CC data, we obtain better $pd$ and $pf$ results than using just CC and\nbc.}
\item{When considering only filtered data or only unfiltered data, the highest $pd$ and lowest $pf$ values are obtained by using WC data as opposed to CC data. This suggests that WC data gives the best results.}
\end{itemize}

These finds were consistent with Turhan et al.'s results: 

\begin{itemize}
\item{Significantly better defect predictors are produced from using WC data.}
\item{However, CC data leads to defect predictors nearly as effective as WC data when using relevancy filtering.}
\end{itemize}

Thus, this study also makes the same conclusions as Turhan et al. A company should use local data to develop defect predictors if that local development data is available. However, if local data is not available, relevancy-filtered cross-company data provides a feasible means to build defect predictors.

\begin{figure}
\small
\begin{center}
\begin{tabular}{l@{~}|l@{~}|r@{~}r@{~}@{~}r@{~}|c}
%\multicolumn{2}{c}{~}&\multicolumn{5}{c}{quartiles}\\\cline{3-5}
%&min& & median & &max\\\cline{3-5}
\multicolumn{2}{c}{~}&\multicolumn{3}{c}{pd}&2nd quartile\\
\multicolumn{2}{c}{~}&\multicolumn{3}{c}{percentiles}&median,\\\cline{3-5}
Rank&Treatment& 25\%& 50\% & 75\%&3rd quartile\\\hline
1&WC (local data) + relevancy filter& 66& 73& 80&  \boxplot{0}{66}{73}{80}{3}  \\
2&CC (imported data) + relevancy filter& 57& 71& 83&  \boxplot{0}{57}{71}{83}{5}  \\
2&WC (local data)  & 59& 69& 83&  \boxplot{0}{59}{69}{83}{7}  \\
3&CC (imported data)  & 49& 66& 87&  \boxplot{0}{49}{66}{87}{7}   \\\hline
\multicolumn{5}{c}{~}&~~~~~0~~~~~~~~50~~~~100
\end{tabular}
\end{center}
\caption{Experiment \#2 (WC vs. CC). Probability of Detection (PD) results, sorted by rank then median values.  }\label{fig:pds}
\end{figure}
\begin{figure}
\small
\begin{center}
\begin{tabular}{l@{~}|l@{~}|r@{~}r@{~}@{~}r@{~}|c}
%\multicolumn{2}{c}{~}&\multicolumn{5}{c}{quartiles}\\\cline{3-5}
%&min& & median & &max\\\cline{3-5}
\multicolumn{2}{c}{~}&\multicolumn{3}{c}{pf}&2nd quartile\\
\multicolumn{2}{c}{~}&\multicolumn{3}{c}{percentiles}&median,\\\cline{3-5}
Rank&Treatment& 25\%& 50\% & 75\%&3rd quartile\\\hline
1&CC (imported data) + relevancy filter& 17& 29& 43&  \boxplot{0}{17}{29}{43}{3}  \\
1&CC (imported data)  & 13& 34& 51&  \boxplot{0}{13}{34}{51}{5} \\
2&WC (local data)  & 17& 30& 41&  \boxplot{0}{17}{30}{41}{7}  \\
3&WC (local data) + relevancy filter & 20& 27& 34&  \boxplot{0}{20}{27}{34}{8}  \\\hline
\multicolumn{5}{c}{~}&~~~~~0~~~~~~~~50~~~~100
\end{tabular}
\end{center}
\caption{Experiment \#2 (WC vs. CC). Probability of False Alarm (PF) results, sorted by rank then median values.  }\label{fig:pfs} \end{figure}


\section{Commissioning a Learner through Incremental Random Sampling}


OURMINE's use is not only important to researchers, but also to practitioners. 
To demonstrate this, two very simple experiments were conducted using seven PROMISE data sets  (CM1, KC1, KC2, KC3, MC2, MW1, PC1).
The aim of this experiment is to commission a data mining system for a local site.
When selecting the right data miners for a particular source of data, three issues are:
\be
\item What learners to use?
\item What discretizers to use?
\item How much data is required for adequate learning?
\ee
Given software being released in several stages, OURMINE can be used on stage 1 data to find the right answers to the above
questions. These answers can be applied on stages 2,3,4, etc.

In Part A of this experiment, four learners (\nbc, J48, ADTree,
One-R) are trained using undiscretized data, and then the same
learners are trained on discretized data for a total of eight
combinations. While this represents a highly simplified proof-of-concept,
from it we can illustrate how our learners can be integrated with
other techniques to find the best treatment for the data set(s) of
concern. Practitioners can then short-circuit their experiments by
only performing further analyses on methods deemed worthwhile for
the current corpus. In turn, this decreases the amount of time in
which results can be obtained.

In Part B of the experiment, the winning treatment from Part A is
used with randomly selected, incremental sizes of training data.
In this experiment, it can be shown how early our quality predictors
can be applied based on the smallest number of training examples
required to learn an adequate theory. Predictors were trained using
$N$ = 100, $N$ = 200, $N$ = 300... randomly selected instances up
to $N$ = 1000. For each training set size $N$, 10 experiments were
conducted using $|Train|$ = 90\% * $N$, and $|Test|$ = 100. Both
$Train$ and $Test$ were selected at random for each experiment. Our
random selection process is modeled after an experiment conducted
by Menzies et. al.~\cite{me07i}. In that paper, it was found that
performance changed little regardless of whether fewer instances
were selected (e.g. 100), or much larger sizes on the order of
several thousand. Additionally, it was determined that larger
training sizes were actually a disadvantage, as variance increased
with increasing training set sizes.

\subsubsection{Results}

\fig{pds2} and \fig{pfs2} show the results from Part A of the experiment. As can be seen, ADTrees (Alternating Decision Trees) ~\cite{Freund99thealternating} trained on discretized data yields the best results: 
\\
\bi
\item{Mann-Whitney test ranking (95\% confidence): ADTrees + discretization provides the highest rank for both PD and PF results}
\item{Medians \& Variance: ADTrees + discretization results in the highest median/lowest variance for PD, and the lowest variance for PF, with only a 1\% increase over the lowest median} 
\ei


Results from Part B of the experiment are shown in \fig{pds3} and
\fig{pfs3}. Using the winning method from Part A, or learning using
ADTrees on discretized data, results show that unquestionably a
training size of $N=600$ instances is the best number to train our
defect predictors using the aforementioned experiment setup. This
is clear when considering $N=600$ maintains the highest Mann-Whitney
ranking (again using 95\% percent confidence), as well as the highest
PD and lowest PF medians.

More importantly, perhaps, it should be noted that while the most
beneficial number of training instances remains 600, we can still
consider a significantly smaller value of, say, $N=300$ without
much loss in performance; a training size of just 300 yields a loss
in PD ranking of only one, with a 3\% decrease in median, while PF
ranking is identical to our winning size and sporting medians of a
mere 3\% increase.

\begin{figure}[h]
\small
\begin{center}
\begin{tabular}{l@{~}|l@{~}|r@{~}r@{~}@{~}r@{~}|c}
%\multicolumn{2}{c}{~}&\multicolumn{5}{c}{quartiles}\\\cline{3-5}
%&min& & median & &max\\\cline{3-5}
\multicolumn{2}{c}{~}&\multicolumn{3}{c}{pd}&2nd quartile\\
\multicolumn{2}{c}{~}&\multicolumn{3}{c}{percentiles}&median,\\\cline{3-5}
Rank&Treatment& 25\%& 50\% & 75\%&3rd quartile\\\hline
1&J48 + discretization& 20& 66& 99&  \boxplot{0}{20}{66}{99}{7}  \\
1&ADTree + discretization& 25& 66& 97&  \boxplot{0}{25}{66}{97}{7}  \\
2&NB + discretization& 63& 73& 82&  \boxplot{0}{63}{73}{82}{7}   \\
2&One-R + discretization& 13& 56& 99&  \boxplot{0}{13}{56}{99}{7}  \\
3&J48& 29& 82& 96& \boxplot{0}{29}{82}{96}{7} \\
3&NB& 40& 79& 91& \boxplot{0}{40}{79}{91}{7}  \\
4&ADTree& 21& 83& 97& \boxplot{0}{21}{83}{97}{7} \\
4&One-R& 17& 83& 97& \boxplot{0}{17}{83}{97}{7} \\\hline
\multicolumn{5}{c}{~}&~~~~~0~~~~~~~~50~~~~100
\end{tabular}
\end{center}
\caption{Experiment \#1 - Part A - (Learner tuning). Probability of Detection (PD) results, sorted by rank then median values.  }\label{fig:pds2}
\end{figure}


\begin{figure}[h]
\small
\begin{center}
\begin{tabular}{l@{~}|l@{~}|r@{~}r@{~}@{~}r@{~}|c}
%\multicolumn{2}{c}{~}&\multicolumn{5}{c}{quartiles}\\\cline{3-5}
%&min& & median & &max\\\cline{3-5}
\multicolumn{2}{c}{~}&\multicolumn{3}{c}{pf}&2nd quartile\\
\multicolumn{2}{c}{~}&\multicolumn{3}{c}{percentiles}&median,\\\cline{3-5}
Rank&Treatment& 25\%& 50\% & 75\%&3rd quartile\\\hline
1&One-R + discretization& 0& 10& 86& \boxplot{0}{0}{10}{86}{7}  \\
1&ADTree + discretization& 2& 11& 75& \boxplot{0}{2}{11}{75}{7} \\
1&J48 + discretization& 1& 11& 80& \boxplot{0}{1}{11}{80}{7} \\
2&NB& 9& 19& 60&  \boxplot{0}{9}{19}{60}{7}  \\
2&J48& 4& 33& 72& \boxplot{0}{4}{33}{72}{7} \\
3&NB + discretization& 12& 25& 33&  \boxplot{0}{12}{25}{33}{7}   \\
3&ADTree& 3& 37& 79&  \boxplot{0}{3}{37}{79}{7}  \\
4&One-R& 3& 44& 83&  \boxplot{0}{3}{44}{83}{7}  \\\hline
\multicolumn{5}{c}{~}&~~~~~0~~~~~~~~50~~~~100
\end{tabular}
\end{center}
\caption{Experiment \#1 - Part A - (Learner tuning). Probability of False Alarm (PF) results, sorted by rank then median values.  }\label{fig:pfs2}
\end{figure}

\newpage

\begin{figure}[h]
\small
\begin{center}
\begin{tabular}{l@{~}|l@{~}|r@{~}r@{~}@{~}r@{~}|c}
%\multicolumn{2}{c}{~}&\multicolumn{5}{c}{quartiles}\\\cline{3-5}
%&min& & median & &max\\\cline{3-5}
\multicolumn{2}{c}{~}&\multicolumn{3}{c}{pd}&2nd quartile\\
\multicolumn{2}{c}{~}&\multicolumn{3}{c}{percentiles}&median,\\\cline{3-5}
Rank&Training Size& 25\%& 50\% & 75\%&3rd quartile\\\hline
1&600& 32& 88& 99&  \boxplot{0}{32}{88}{99}{7}  \\
1&700& 30& 86& 98&  \boxplot{0}{30}{86}{98}{7}   \\
1&900& 32& 86& 98&  \boxplot{0}{32}{86}{98}{7}  \\
1&800& 31& 85& 98&  \boxplot{0}{31}{85}{98}{7}  \\
1&500& 30& 84& 99& \boxplot{0}{30}{84}{99}{7} \\
1&1000& 30& 84& 99& \boxplot{0}{30}{84}{99}{7}  \\
2&300& 31& 85& 98& \boxplot{0}{31}{85}{98}{7} \\ 
2&400& 29& 84& 99& \boxplot{0}{29}{84}{99}{7} \\
3&200& 29& 83& 98& \boxplot{0}{29}{83}{98}{7} \\
3&100& 29& 77& 96& \boxplot{0}{29}{77}{96}{7} \\\hline
\multicolumn{5}{c}{~}&~~~~~0~~~~~~~~50~~~~100
\end{tabular}
\end{center}
\caption{Experiment \#1 - Part B - (Random Sampling). Probability of Detection (PD) results, sorted by rank then median values.  }\label{fig:pds3}
\end{figure}
\begin{figure}[h]
\small
\begin{center}
\begin{tabular}{l@{~}|l@{~}|r@{~}r@{~}@{~}r@{~}|c}
%\multicolumn{2}{c}{~}&\multicolumn{5}{c}{quartiles}\\\cline{3-5}
%&min& & median & &max\\\cline{3-5}
\multicolumn{2}{c}{~}&\multicolumn{3}{c}{pf}&2nd quartile\\
\multicolumn{2}{c}{~}&\multicolumn{3}{c}{percentiles}&median,\\\cline{3-5}
Rank&Training Size& 25\%& 50\% & 75\%&3rd quartile\\\hline
1&600& 1& 12& 68&  \boxplot{0}{1}{12}{68}{7}  \\
1&700& 1& 14& 70&  \boxplot{0}{1}{14}{70}{7}  \\
1&900& 1& 14& 68& \boxplot{0}{1}{14}{68}{7}  \\
1&1000& 1& 14& 69&  \boxplot{0}{1}{14}{69}{7}  \\
1&500& 1& 15& 69&  \boxplot{0}{1}{15}{69}{7}   \\
1&800& 1& 15& 69& \boxplot{0}{1}{15}{69}{7} \\
1&300& 2& 15& 69& \boxplot{0}{2}{15}{69}{7} \\ 
1&400& 1& 15& 71& \boxplot{0}{1}{15}{71}{7} \\
2&200& 2& 17& 71& \boxplot{0}{2}{17}{71}{7} \\
3&100& 4& 23& 71& \boxplot{0}{4}{23}{71}{7} \\\hline
\multicolumn{5}{c}{~}&~~~~~0~~~~~~~~50~~~~100
\end{tabular}
\end{center}
\caption{Experiment \#1 - Part B - (Random Sampling). Probability of False Alarm (PF) results, sorted by rank then median values.  }\label{fig:pfs3}
\end{figure}



\section{Component vs. Whole-based Defect Prediction}

\subsection{The Experiment}

In order to test the implications of learning using components dense with software defects, an experiment was constructed using five NASA defect data sets (CM1, KC1, MC1, PC1, PC3). These data sets were chosen because they have been studied in the field extensively, and also that they are widely available to the PROMISE community. Five were chosen due to the limited number of data sets containing noteworthy numbers of components.

For each data set, components are extracted by first determining both defective and non-defective modules contained in that data set. Once the modules are obtained, those components (named after a unique identifier) containing these modules are selected for further analyses. 

After extracting the components and corresponding number of defects, components were retrieved for further analysis from each data set if the number of defective modules per component exceeded the median number of defects across $all$ components in that data set. For example, in \fig{kc1-defects} the bottom horizontal line represents the median number of defects in the KC1 data set. Thus, those components lying under this line are not used in further stages of the experiment. The components selected (at or above the median number of defects) are considered $dense$ components. The pseudocode in \fig{dense-comp-experiment} illustrates the remaining setup of the experiment:

\begin{figure}
\begin{verbatim}

1 For run = 1 to 10
2   For each dense component C in data set D
  
3    Let Train = C
4    Let Test = All components in D except for C
   
5     For bin = 1 to 10
6      Train' = Randomly select 90% modules from Train
7      Test' = Randomly select 10% modules from Test
     
8      Learn using the Naive Bayes classifier using Train' and Test'
9     end bin
10   end component
11 end run
\end{verbatim}
\caption[Training on Dense Components Vs. All Components]{Training on dense components versus all components. The experiment performs training on modules residing in dense components, and testing on modules contained in all other components in the data set.}\label{fig:dense-comp-experiment}
\end{figure}

Lines 1 and 5 of \fig{dense-comp-experiment} illustrate the use of the 10X10-way cross validation used in the experimental process. The standard 10X10-way cross validation operates by selecting 90\% of the data randomly for training, and the remaining 10\% for testing. This process is then repeated 10 times for consistency. The experiment shown in \fig{dense-comp-experiment}, however, handles this operation in a slightly different manner. Since the objective is to analyze the performance of training on modules in components containing a high number of defects while testing on all other components' modules, a minute alteration was made to the cross-validation of the experiment. A ``pool'' of training data was constructed by focusing on only those instances $within$ a dense component, as in line 3 of the pseudocode. The available pool of testing instances, thus, are gathered from the $remaining$ components in the data set. This is employed to prevent training, and then testing on modules within the same component. Lines 6 and 7 illustrate collecting 90\% of the current dense component's instances as the final training set $Train'$, and 10\% of the modules from the available instances in components not labeled $dense$ as $Test'$.

While this represents a slight modification to the standard practice of performing a cross-validation, it is within our engineering judgement to apply techniques that best mimic current methods in an area of experimentation still in its infancy. Thus, the recentness of this specific area of research invites further techniques to be discovered and implemented.

Line 8 of \fig{dense-comp-experiment} executes the classifier (in this case, \nbc) on the previously created training and testing sets $Train'$ and $Test'$. \nbc was used because of its speed, and also because it has been shown to perform well on PROMISE defect data against other learners ~\cite{lessmann08}.

As the overall goal is to determine if training our classifiers using fewer, but more densely-packed components is advantageous to the usual practice of learning on a pool of all components (and thus all modules), comparisons are made between each approach, and the results are shown in the following section.

\begin{figure}
\begin{center}
\includegraphics[width=6in]{figures/cs-kc1-dist.pdf}
\end{center}
\caption[Component defect distribution example]{Defect distributions of components found in the KC1 data set. Note that only a small number of components contain a relatively high number of defects.}\label{fig:kc1-defects}
\end{figure}

\subsection{Results}

The metrics used in the analysis of comparing results from training on dense components over the traditional method of using all components in the data set are $pd$ (Probability of Detection), $pf$ (Probability of False Alarm) and $precision$. If $A$,$B$,$C$, and $D$ denote the true negatives, false negatives, false positives and true positives (respectively) found by a classifier, then:

\begin{equation}
pd = Recall = \frac{D}{(B+D)}
\end {equation}

and

\begin{equation}
pf = \frac{C}{(A+C)}
\end {equation}

and

\begin{equation}
precision = \frac{D}{(D+C)}
\end{equation}

Therefore, $pd$ and $precision$ values are best if maximized, while $pf$ results should be minimized.

\fig{pds-all}, \fig{pfs-all} and \fig{prec-all} show statistical rankings of each treatment, as well as quartile charts displaying the median and variance of each metric for the $combined$ data sets, as a whole, used in the experiment. Note that training on components containing a higher number of defective modules maintains higher or tied ranks with the traditional method, and yields similar medians; while $precision$ and $pd$ medians lose 3\% and 2\% respectively, learning on dense areas provides much better $pf$ medians -- almost half. 

Perhaps more interestingly are the analyses of data sets separately. Table \ref{plus-minus} demonstrates the outcome of each treatment for each data set independently. A ``+'' denotes a $win$ for a particular treatment against the other, per data set. Conversely, a ``-'' indicates a $loss$. For example, the fourth row in Table \ref{plus-minus} (data set PC1), shows that learning on dense components wins over learning on all for both $pd$ and $prec$, but $loses$ when considering $pf$ scores. A win or a loss is assigned to a treatment by examining its statistical rank {\em as well} as its median value in comparison to the opposing treatment. If the treatments are statistically different, the method receiving the highest rank is given a ``+'' for that metric. If there is a tie in the ranks, the highest (or lowest, for $pf$) is used to determine the winner. The last row of the table represents the score of each treatment, given as the sum of ``+''s for each treatment using the three metrics.

The results from this table demonstrate that learning on only components containing higher numbers of defective modules is beneficial because

\bi
\item{defect prediction performance is improved significantly}
\item{less data is required during the training phase, meaning faster runtimes and results}
\item{insight is provided for component types; software organizations can make informed decisions about how to approach certain problematic components }
\ei 


\begin{table}
\small\renewcommand\arraystretch{1.1}%
\begin{center}
\begin{tabular}{|l|l|l|l|l|}
\hline
\textbf{Project} & \textbf{Recall} & \textbf{Prob. False Alarm (Pf)} & \textbf{Precision}\\
&   \begin{tabular}{r r r c c c}
%\multicolumn{2}{c}{~}&\multicolumn{5}{c}{quartiles}\\\cline{3-5}
%&min& & median & &max\\\cline{3-5}
& & & 0\% & 50\% & 100\%  
\end{tabular} 
  & \begin{tabular}{r r r c c c}
%\multicolumn{2}{c}{~}&\multicolumn{5}{c}{quartiles}\\\cline{3-5}
%&min& & median & &max\\\cline{3-5}
& & & 0\% & 50\% & 100\%  
\end{tabular}   
 & \begin{tabular}{r r r c c c}
%\multicolumn{2}{c}{~}&\multicolumn{5}{c}{quartiles}\\\cline{3-5}
%&min& & median & &max\\\cline{3-5}
& & & 0\% & 50\% & 100\%  
\end{tabular} \\
\hline
CM1 & \begin{tabular}{l@{~}|l@{~}|r@{~}r@{~}@{~}r@{~}|c}
%\multicolumn{2}{c}{~}&\multicolumn{5}{c}{quartiles}\\\cline{3-5}
%&min& & median & &max\\\cline{3-5}
1&All&   \boxplot{0}{33.3}{84.1}{91.5}{3}  \\
2&Over&  \boxplot{0}{33.3}{79.5}{88.9}{3}   \\ 
2&Under& \boxplot{0}{33.3}{68.8}{87.2}{3}    \\ 
3&Dense& \boxplot{0}{0}{60.0}{100}{3}    \\ 
\end{tabular}
 & \begin{tabular}{l@{~}|l@{~}|r@{~}r@{~}@{~}r@{~}|c}
%\multicolumn{2}{c}{~}&\multicolumn{5}{c}{quartiles}\\\cline{3-5}
%&min& & median & &max\\\cline{3-5}
1&Dense&   \boxplot{0}{0}{0}{25}{3}  \\
2&Over&    \boxplot{0}{11}{20}{67}{3}   \\ 
2&Under&   \boxplot{0}{13}{28}{67}{3}    \\ 
2&All&     \boxplot{0}{8}{15}{67}{3}    \\ 
\end{tabular} & \begin{tabular}{l@{~}|l@{~}|r@{~}r@{~}@{~}r@{~}|c}
%\multicolumn{2}{c}{~}&\multicolumn{5}{c}{quartiles}\\\cline{3-5}
%&min& & median & &max\\\cline{3-5}
1&All&   \boxplot{0}{25}{75}{93}{3}  \\
1&Over&  \boxplot{0}{20}{75}{92}{3}   \\ 
1&Under& \boxplot{0}{17}{67}{93}{3}    \\ 
1&Dense& \boxplot{0}{0}{50.0}{100}{3}    \\ 
\end{tabular} \\
\hline
KC1 & \begin{tabular}{l@{~}|l@{~}|r@{~}r@{~}@{~}r@{~}|c}
%\multicolumn{2}{c}{~}&\multicolumn{5}{c}{quartiles}\\\cline{3-5}
%&min& & median & &max\\\cline{3-5}
1&Dense&   \boxplot{0}{46}{82}{93}{3}  \\
1&Under&  \boxplot{0}{42}{61}{89}{3}   \\ 
1&All& \boxplot{0}{36}{60}{91}{3}    \\ 
1&Over& \boxplot{0}{42}{57}{90}{3}    \\ 
\end{tabular}
 & \begin{tabular}{l@{~}|l@{~}|r@{~}r@{~}@{~}r@{~}|c}
%\multicolumn{2}{c}{~}&\multicolumn{5}{c}{quartiles}\\\cline{3-5}
%&min& & median & &max\\\cline{3-5}
1&All&     \boxplot{0}{8.5}{12.8}{64}{3}  \\
1&Over&    \boxplot{0}{10}{17}{57}{3}   \\ 
1&Under&   \boxplot{0}{9}{13}{64}{3}    \\ 
1&Dense&   \boxplot{0}{7}{17}{53}{3}    \\ 
\end{tabular} & \begin{tabular}{l@{~}|l@{~}|r@{~}r@{~}@{~}r@{~}|c}
%\multicolumn{2}{c}{~}&\multicolumn{5}{c}{quartiles}\\\cline{3-5}
%&min& & median & &max\\\cline{3-5}
1&Dense&   \boxplot{0}{33}{83}{90}{3}  \\
1&All&  \boxplot{0}{43}{75}{88}{3}   \\ 
1&Under& \boxplot{0}{42}{59}{90}{3}    \\ 
1&Over& \boxplot{0}{43}{59}{89}{3}    \\ 
\end{tabular}\\
\hline
MC1 & \begin{tabular}{l@{~}|l@{~}|r@{~}r@{~}@{~}r@{~}|c}
%\multicolumn{2}{c}{~}&\multicolumn{5}{c}{quartiles}\\\cline{3-5}
%&min& & median & &max\\\cline{3-5}
1&Over&   \boxplot{0}{60}{91}{94}{3}  \\
1&Under&  \boxplot{0}{70}{89}{93}{3}   \\ 
2&All& \boxplot{0}{34}{53}{94}{3}    \\ 
3&Dense& \boxplot{0}{33}{75}{90}{3}    \\ 
\end{tabular}
 & \begin{tabular}{l@{~}|l@{~}|r@{~}r@{~}@{~}r@{~}|c}
%\multicolumn{2}{c}{~}&\multicolumn{5}{c}{quartiles}\\\cline{3-5}
%&min& & median & &max\\\cline{3-5}
1&Over&   \boxplot{0}{6}{9}{36}{3}  \\
1&Under&  \boxplot{0}{7}{11}{30}{3}   \\ 
2&All& \boxplot{0}{6}{7}{66}{3}    \\ 
3&Dense& \boxplot{0}{6}{11}{66}{3}    \\ 
\end{tabular} & \begin{tabular}{l@{~}|l@{~}|r@{~}r@{~}@{~}r@{~}|c}
%\multicolumn{2}{c}{~}&\multicolumn{5}{c}{quartiles}\\\cline{3-5}
%&min& & median & &max\\\cline{3-5}
1&Dense&   \boxplot{0}{12}{21}{98}{3}  \\
1&All&  \boxplot{0}{10}{16}{99}{3}   \\ 
1&Under& \boxplot{0}{6}{16}{100}{3}    \\ 
1&Over& \boxplot{0}{6}{13}{100}{3}    \\ 
\end{tabular} \\
\hline
PC1 & \begin{tabular}{l@{~}|l@{~}|r@{~}r@{~}@{~}r@{~}|c}
%\multicolumn{2}{c}{~}&\multicolumn{5}{c}{quartiles}\\\cline{3-5}
%&min& & median & &max\\\cline{3-5}
1&Dense&   \boxplot{0}{71}{85}{91}{3}  \\
2&Over&  \boxplot{0}{27}{86}{93}{3}   \\ 
2&All& \boxplot{0}{29}{75}{94}{3}    \\ 
3&Under& \boxplot{0}{30}{75}{91}{3}    \\ 
\end{tabular}
 & \begin{tabular}{l@{~}|l@{~}|r@{~}r@{~}@{~}r@{~}|c}
%\multicolumn{2}{c}{~}&\multicolumn{5}{c}{quartiles}\\\cline{3-5}
%&min& & median & &max\\\cline{3-5}
1&Dense&   \boxplot{0}{9}{14}{29}{3}  \\
2&Over&  \boxplot{0}{7}{12}{73}{3}   \\ 
2&All& \boxplot{0}{6}{11}{71}{3}    \\ 
3&Under& \boxplot{0}{9}{19}{67}{3}    \\ 
\end{tabular} & \begin{tabular}{l@{~}|l@{~}|r@{~}r@{~}@{~}r@{~}|c}
%\multicolumn{2}{c}{~}&\multicolumn{5}{c}{quartiles}\\\cline{3-5}
%&min& & median & &max\\\cline{3-5}
1&Dense&   \boxplot{0}{71}{90}{91}{3}  \\
2&All&  \boxplot{0}{27}{89}{95}{3}   \\ 
2&Under& \boxplot{0}{20}{50}{95}{3}    \\ 
3&Over& \boxplot{0}{25}{58}{94}{3}    \\ 
\end{tabular} \\
\hline
PC3 & \begin{tabular}{l@{~}|l@{~}|r@{~}r@{~}@{~}r@{~}|c}
%\multicolumn{2}{c}{~}&\multicolumn{5}{c}{quartiles}\\\cline{3-5}
%&min& & median & &max\\\cline{3-5}
1&Under&   \boxplot{0}{50}{73}{83}{3}  \\
1&Over&  \boxplot{0}{29}{67}{89}{3}   \\ 
2&All& \boxplot{0}{40}{67}{87}{3}    \\ 
2&Dense& \boxplot{0}{42}{64}{86}{3}    \\ 
\end{tabular}
 & \begin{tabular}{l@{~}|l@{~}|r@{~}r@{~}@{~}r@{~}|c}
%\multicolumn{2}{c}{~}&\multicolumn{5}{c}{quartiles}\\\cline{3-5}
%&min& & median & &max\\\cline{3-5}
1&Dense&   \boxplot{0}{0}{32}{50}{3}  \\
2&Over&  \boxplot{0}{10}{30}{71}{3}   \\ 
2&Under& \boxplot{0}{16}{27}{50}{3}    \\ 
3&All& \boxplot{0}{13}{31}{60}{3}    \\ 
\end{tabular} & \begin{tabular}{l@{~}|l@{~}|r@{~}r@{~}@{~}r@{~}|c}
%\multicolumn{2}{c}{~}&\multicolumn{5}{c}{quartiles}\\\cline{3-5}
%&min& & median & &max\\\cline{3-5}
1&Dense&   \boxplot{0}{18}{67}{98}{3}  \\
1&Under&  \boxplot{0}{21}{43}{95}{3}   \\ 
1&All& \boxplot{0}{14}{38}{96}{3}    \\ 
1&Over& \boxplot{0}{12}{25}{96}{3}    \\ 
\end{tabular} \\
\hline\end{tabular}
\end{center}
\caption{Result statistics per data set. The numeric value next to each treatment represents its Mann-Whitney rank, to the right of each treatment lies the quartile chart for each. Each metric is either sorted by ranking, or in the case of a tie, descending $pd$ and $prec$ or ascending $pf$.}\label{plus-minus}
\end{table}


%\begin{figure}
%\begin{center}
%\includegraphics[width=4in]{figures/cs-component-summary.png}
%\end{center}
%\caption[Dense vs. All Component Learning - all metrics per data set.]{Each treatment is assigned a ``+'' or ``-'' if it $won$ over the other treatment, per metric, per data set. A ``+'' is assigned to a treatment winning a statistical ranking (based on a Mann-Whitney test at 95\% confidence), or the best median per metric.}\label{fig:plus-minus}
%\end{figure}

\begin{figure}
\small
\begin{center}
\begin{tabular}{l@{~}|l@{~}|r@{~}r@{~}@{~}r@{~}|c}
%\multicolumn{2}{c}{~}&\multicolumn{5}{c}{quartiles}\\\cline{3-5}
%&min& & median & &max\\\cline{3-5}
\multicolumn{2}{c}{~}&\multicolumn{3}{c}{pd}&2nd quartile\\
\multicolumn{2}{c}{~}&\multicolumn{3}{c}{percentiles}&median,\\\cline{3-5}
Rank&Treatment& 25\%& 50\% & 75\%&3rd quartile\\\hline
1&Train on Dense Components& 31& 69& 91&  \boxplot{0}{31}{69}{91}{3}  \\
2&Train on All Components& 35& 71& 93&  \boxplot{0}{35}{71}{93}{3}    \\ \hline
\multicolumn{5}{c}{~}&~~~~~0~~~~~~~~50~~~~100
\end{tabular}
\end{center}
\caption[Dense Component vs. All Component learning - $pd$ - All Data]{$PD$ values for learning on dense components compared to learning on all components across all data sets, sorted by statistical ranking via a Mann-Whitney test at 95\% confidence.}\label{fig:pds-all}
\end{figure}

\begin{figure}
\small
\begin{center}
\begin{tabular}{l@{~}|l@{~}|r@{~}r@{~}@{~}r@{~}|c}
%\multicolumn{2}{c}{~}&\multicolumn{5}{c}{quartiles}\\\cline{3-5}
%&min& & median & &max\\\cline{3-5}
\multicolumn{2}{c}{~}&\multicolumn{3}{c}{pf}&2nd quartile\\
\multicolumn{2}{c}{~}&\multicolumn{3}{c}{percentiles}&median,\\\cline{3-5}
Rank&Treatment& 25\%& 50\% & 75\%&3rd quartile\\\hline
1&Train on Dense Components& 0& 15& 52&  \boxplot{0}{0}{15}{52}{3}  \\
1&Train on All Components& 0& 26& 65&  \boxplot{0}{7}{26}{65}{3}    \\ \hline
\multicolumn{5}{c}{~}&~~~~~0~~~~~~~~50~~~~100
\end{tabular}
\end{center}
\caption[Dense Component vs. All Component learning - $pf$ - All Data]{$PF$ values for learning on dense components compared to learning on all components across all data sets, sorted by statistical ranking via a Mann-Whitney test at 95\% confidence.}\label{fig:pfs-all}
\end{figure}

\begin{figure}
\small
\begin{center}
\begin{tabular}{l@{~}|l@{~}|r@{~}r@{~}@{~}r@{~}|c}
%\multicolumn{2}{c}{~}&\multicolumn{5}{c}{quartiles}\\\cline{3-5}
%&min& & median & &max\\\cline{3-5}
\multicolumn{2}{c}{~}&\multicolumn{3}{c}{precision}&2nd quartile\\
\multicolumn{2}{c}{~}&\multicolumn{3}{c}{percentiles}&median,\\\cline{3-5}
Rank&Treatment& 25\%& 50\% & 75\%&3rd quartile\\\hline
1&Train on All Components& 20& 78& 95&  \boxplot{0}{20}{78}{95}{3}  \\
1&Train on Dense Components& 12& 75& 96&  \boxplot{0}{12}{75}{96}{3}    \\ \hline
\multicolumn{5}{c}{~}&~~~~~0~~~~~~~~50~~~~100
\end{tabular}
\end{center}
\caption[Dense Component vs. All Component learning - $precision$ - All Data]{$Precision$ values for learning on dense components compared to learning on all components across all data sets, sorted by statistical ranking via a Mann-Whitney test at 95\% confidence.}\label{fig:prec-all}
\end{figure}
