\documentclass[twocolumn,global]{svjour}
\usepackage{lastpage,url,alltt,graphicx,cite,url,fancyheadings,bar,fancyvrb}
\usepackage{rotating,wrapfig,stfloats}

\usepackage{eso-pic}
\usepackage{color}
\usepackage{type1cm}

%\makeatletter
%  \AddToShipoutPicture{%
%    \setlength{\@tempdimb}{.5\paperwidth}%
%    \setlength{\@tempdimc}{.5\paperheight}%
%    \setlength{\unitlength}{1pt}%
%      \makebox(600,900){\rotatebox{45}{\textcolor[gray]{0.80}{\fontsize{9cm}{9cm}\selectfont{Draft}}}}}
%\makeatother
%%    \put(\strip at pt\@tempdimb,\strip at pt\@tempdimc){%
 %     \makebox(500,700){\rotatebox{45}{\textcolor[gray]{0.75}{\fontsize{10cm}{10cm}\selectfont{Draft}}}}

\newenvironment{ccode}{\scriptsize\begin{alltt}}{\end{alltt}\normalsize}


   \newcommand{\code}[3]{%
     \begin{figure}[!t]%
        \fvset{  samepage=true,%
                 fontsize=\scriptsize,%
                 commandchars=\\\{\},%
                 framesep=2mm,%
                 label={\small{\textit{#1}}},%
                 labelposition=topline,%
                 %numbersep=1pt,%
                 %stepnumber=5%
                 %numbers=left,%
                 frame=single%
                 }%
            {\bf \VerbatimInput{#1}}
    \caption[#2]{#3}\label{fig:#1}%
    \end{figure}%
}

%\usepackage[para,symbol*]{footmisc}
%\setfnsymbol{lamport}
\usepackage{amssymb,times}
\DeclareFontShape{OT1}{cmtt}{bx}{n}{
  <5><6><7><8><9><10><10.95><12><14.4><17.28><20.74><24.88>cmttb9}{}

\newcommand{\mytitle}{
Improving IV\&V Techniques Through the Analysis of Project Anomalies:\\
Text Mining PITS issue reports - final report
}
\footrulewidth 0.0pt\headrulewidth 0.1pt
\lhead{}\rhead{}\chead{}\rfoot{}\lfoot{}\cfoot{}
\rhead{ {\scriptsize 
\date{\today}\newline
source: \url{http://now.unbox.org/all/trunk/doc/06/tellingmore/report4.*}\newline
download: \url{http://menzies.us/pdf/07anomalies-pits.pdf}
}}

\rhead{{\scriptsize 
\date{\today}\\
download: \url{http://menzies.us/pdf/07anomalies-pits.pdf}\\
wp: \url{http://now.unbox.org/all/trunk/doc/07/tellingmore/report4.*}
}}
\lhead{\includegraphics[width=6cm]{wvulogo.pdf}}

\newenvironment{smallitem}
 {\setlength{\topsep}{0pt}
  \setlength{\partopsep}{0pt}
  \setlength{\parskip}{0pt}
  \begin{itemize}
   \setlength{\leftmargin}{.2in}
  \setlength{\parsep}{0pt}
  \setlength{\parskip}{0pt}
  \setlength{\itemsep}{0pt}}
 {\end{itemize}}

\newenvironment{smallenum}
 {\setlength{\topsep}{0pt}
  \setlength{\partopsep}{0pt}
  \setlength{\parskip}{0pt}
  \begin{enumerate}
  \setlength{\leftmargin}{.2in}
  \setlength{\parsep}{0pt}
  \setlength{\parskip}{0pt}
  \setlength{\itemsep}{0pt}}
 {\end{enumerate}}

 
   

 \newcommand{\bd}{\begin{description}}
\newcommand{\ed}{\end{description}}
 \newcommand{\bi}{\begin{smallitem}}
\newcommand{\ei}{\end{smallitem}}
 \newcommand{\be}{\begin{smallenum}}
\newcommand{\ee}{\end{smallenum}}
\newcommand{\fig}[1]{Figure~\ref{fig:#1}}
\newcommand{\eq}[1]{Equation~\ref{eq:#1}}
\newcommand{\tion}[1]{\S\ref{sec:#1}}

%\topmargin -3cm

\begin{document}
\title{
\mytitle
\author{Tim Menzies }
\institute{Lane Department of Computer Science and Electrical Engineering, West Virginia
University,
USA
\newline
\url{tim@menzies.us}\newline
\url{http://menzies.us}\newline
}}
\maketitle \thispagestyle{fancy}
\pagestyle{fancy}

\vspace{-1cm}\begin{abstract}
This project is in two parts.
The {\em second part} will try to combine two (or more) of the IV\&V data sources
 into an active monitoring
framework where data collected during an active IV\&V project will trigger an
alert
if a project becomes unusual'' (and defining ``unusual'' is one of the goals of this project).

But before we can generalize between sources, we need to study each source in isolation
to determine its strengths and weaknesses.
Hence, the {\em first part} of this project  aims to gain experience with the various IV\&V data sources
available to researchers like myself; i.e.
		 \bi
	 \item
	 SILAP, from
	 the IV\&V planning and scoping team; 
	 \item
	 James Dabney's Bayes networks that
	 describe the IV\&V business practices of the L3
 IV\&V contractor; 
	 \item
	 The PITS issue tracking data; 
	 \item
	 The LINKER database
	 project that intends to
	 join PITS to other data sources; 
	 \item
	 Balanced score card strategy maps from NASA Langley. 
	 \item
	 and the COCOMO data sets from JPL.
	 \ei

This is the second year of a  three year project that started in  June 2006.
The project is data-rich project and much progress has already been achieved.
\bi
\item
At SAS'06, a preliminary report described what had been learned from the
SILAP data. 
A ranking was offered on the most common IV\&V work-breakdown structure (WBS) activities.
This ranking can be used for (e.g.) identifying what WBS tasks would benefit most from optimization.
\item
This report on SILAP was finalized in the first part of 2007. In summary, there exists a very strong
signal in the SILAP data for issue frequency and severity.
\item
In October'06, a preliminary report
was delivered on the Bayes network. On a limited case study, it was shown that Bayes nets
and treatment learning could generate parsimonious explanations 
for project events.
\item
A preliminary report on text mining from the
PITS issues tracking database that 
generated an expert system
which audited  a test engineer's proposed severity level.
\ei
This document updates the  preliminary PITS report. Before, the PITS report studied
two projects with a  limited range of severities (mostly severity 3 and 4).
Here, we explore five projects with a much wider
range of severities.
The results from the PITS preliminary report is confirmed.
Using text mining,
PITS can be used to generate an expert system
that audits  a test engineer's proposed severity level for an issue.
\vspace{1.4in}
\end{abstract}

\noindent
{\bf Credits:}
This work was made possible due to the heroic efforts
of Ken Costello (chief engineering at NASA IV\&V) who provided the PITS defect reports.
The text mining  technology used here was inspired by the trace-ability work of
Jane Hayes and Alex 
Dekhtyar. Alex was particularly helpful is mapping out the ABCs of text mining.
Jane also offered extensive advice on how to extend the current
system.
This research was conducted at
West Virginia University 
under NASA sub-contract project 100005549, task 5e, award 1002193r.

~\\

\noindent
{\bf Cautions}
Reference herein to
any specific commercial product, process, or service by trade name,
trademark, manufacturer, or otherwise, does not constitute or imply
its endorsement by the United States 
Government.

~\\

\noindent
{\bf Revision history :}
Much of the introductory and exposition  text of this
document comes from the preliminary report.  However,
all the results of this document have been recomputed
for the five new projects.
Also new in this report are the rule minimization
results.


~\hrule~\\
\clearpage
\rhead{\thepage\ of \pageref{LastPage}}
\lhead{Menzies: Text Mining PITS - preliminary report}
\tableofcontents
\newpage
\listoffigures
\newpage

\section{Introduction: We don't need another hero}
\begin{wrapfigure}{l}{1.75in}
\includegraphics[width=1.75in]{hero.png}
\end{wrapfigure} 

NASA's software IV\&V Program captures all of its findings in a
database called the Project and Issue Tracking System (PITS).  
The data in PITS has been collected for more
than 10 years and includes issues on robotic satellite missions and
human-rated systems.  


It is difficult, to say the least, to generate conclusions from a moving
target like PITS. Several heroic
studies have made significant conclusions using PITS data (see
\fig{heros}).  These studies were heroic in the sense
that the ``heroes'' reached their goals after tedious and complex struggling.
Worse, the extracted data was only accessible
with the help of NASA civil servants- a scarce and expensive
resource. 
\begin{figure}[!b]
\small
\begin{tabular}{|p{0.95\linewidth}|}\hline
\bi
\item
Ken Costello (IV\&V's chief engineer)  compiled statistics for NASA headquarters that showing, in nine IV\&V tasks,
the majority of issues found by IV\&V were found via an analysis of requirements documents.
\item
Marcus Fisher (IV\&V's research lead) applied a ``mid-course correction'' to one IV\&V project after checking the
progress of the IV\&V against historical records in PITS.
\item
David Raffo (University of Portland), working with Ken Costello and other civil servants, found enough cost data to partially tune his
waterfall-based model of IV\&V;
\item
In a prior report in this project, Melissa Northey (Project Manager)
performed some joins across PITS to return costs
for different IV\&V tasks;
\ei\\\hline
\end{tabular}
\caption[Heroic successes with PITS]{
A partial list of past heroic successes with PITS.
}\label{fig:heros}
\end{figure}

The problem with PITS is that 
there is a lack of consistency in how each
of the projects collected issue data.  In virtually all instances,
the specific configuration of the information captured about an
issue was tailored by the IV\&V project to meet its needs.  This has
created consistency problems when metrics data is pulled across
projects.  While there was a set of required data fields, the
majorities of those fields do not provide information in regards
to the quality of the issue and are not very suitable for comparing
projects.


NASA is very aware of the problems with PITS and is taking
active steps to improve it. At the time of this
writing, there is an on-going effort to implement a mandatory data
set in each IV\&V project database to support IV\&V effectiveness
metrics.  This effort has been in development for about a year and
is currently being executed by several projects.  However, it is
too early to make any useful observations from that data.

To be fair, PITS is hardly unique. Based on my experience with data mining
at other corporations, I assert that PITS is a typical database, useful for storing
day-to-day information and generating small-scale tactical reports (e.g. ``list the bugs
we found last Tuesday''),
but difficult to  use for high-end business strategic analysis (e.g.. ``in the past, what methods have proved most
cost effective in finding bugs?'').
Like many other databases,
it takes heroes to extract information from PITS. Sadly, most of the heroes I know
are so busy saving their own part of the world that they have little time
to save researchers like me.


Hence, in this report, we try a new approach for extracting general conclusions
from PITS data. Unlike previous heroic efforts,
our text mining and machine learning methods are
low cost,  automatic, and rapid.
We find we can build an agent to automatically review issue reports and alert when
a proposed severity is anomalous. Better, the way we generated the agent means that
we have probabilities that the agent is correct. These probabilities can be used 
to intelligently guide decision making.

An extremely surprising conclusion from this report is that the unstructured text might be a better candidate
for generating lessons learned than the structured data base fields. 
\bi
\item
While the database fields in PITS keep changing, the nature of the unstructured
text remains constant.
\item
In other words, the reason it is so hard in the past to reason about PITS  
is that we have been looking at the wrong data.
\ei
If we could properly understand unstructured text, this would be a result
of tremendous practical importance. 
A recent study\footnote{\url{http://www.b-eye-network.com/view/2098}} concluded that
\bi
\item
     80 percent of business is conducted on unstructured information;
\item     85 percent of all data stored is held in an unstructured format
(e.g.  the unstructured text descriptions of issues found in PITS);
  \item   Unstructured data doubles every three months;
\ei

That is, if we can tame the text mining problem, it would be possible to reason and learn from a much wider range of
NASA
data than ever before.
\newpage
\section{Concept of Operations}
NASA uses a five-point scale  to score issue severity.
The scale ranges one to five, worst to dullest, respectively.
A different scale is used 
for robotic and human-rated
missions (see \fig{define} and \fig{define1}).
The data used in this report comes from robotic missions.

Using text mining and machine learning methods,
this report shows that it is possible to
automatically generate
a {\em review agent}
from PITS issue reports
via the process of \fig{exprt}.
This agent can check the validity of the severity levels assigned to issues:
\bi
\item
After seeing an issue in some {\em artifact}, a human {\em analyst}
generates some text {\em notes} and assigned a severity
level {\em severityX}. 
\item
An agent learns a predictor for issue severity
level from logs
of
$\{notes,severityX\}$. A 
{\em training} module (a)~updates the agent beliefs and (b) determines
how much {\em self-confidence} a {\em supervisor} might have in
the {\em agent}'s conclusions.
\item 
Using the learned knowledge,
the {\em agent} reviews the {\em analysts}'s text and generates its own
{\em severityY} level. 
\item
If the agent's proposed {\em severityY}
differs from the {\em severityX} level
of the human {\em analyst}, then a human
{\em supervisor} can decide to review the human {\em analyst}'s {\em severityX}.
To help in that process, the
{\em supervisor} can review the {\em self-confidence} information to decide
if they trust the agent's recommendations. 
\ei
This agent would be of useful under the following circumstances:
\bi
\item 
When a less-experienced test engineer has assigned the wrong
severity levels. \item
When experienced test engineers are operating
under urgent time pressure demands, they could use the agent to
automatically and quickly
audit their conclusions.
\item
For agents that can detect severity one and two-level errors with high probability, the
agent could check for the rare, but extremely dangerous case, that an IV\&V team has missed
a high-severity problem.
\ei

\begin{figure}
\footnotesize
\begin{tabular}{|p{\linewidth}|}\hline
\begin{description}
\item[\em Severity 1:]
Prevent the accomplishment of an essential capability;
or jeopardize safety, security, or other requirement designated critical.
\item[\em Severity 2:]
Adversely affect the accomplishment of an essential capability and no work-around solution is known ;
or adversely affect technical, cost or schedule risks to the 
project or life cycle support of the system, and no work-around solution is known.
\item[\em Severity 3:]
Adversely affect the accomplishment of an essential capability but a work-around solution is known;
or  adversely affect technical, cost, or schedule risks to the project or life cycle support of the system, but a work-around solution is known.
\item[\em Severity 4:]
Results in user/operator inconvenience but does not affect a required operational or mission essential capability; or
results in inconvenience for development or maintenance personnel, but does not affect the accomplishment of these responsibilities.
\item[\em Severity 5:] Any other issues.
\end{description}\\\hline
\end{tabular}
\caption{Severities for robotic missions.}\label{fig:define}
\end{figure}
\begin{figure}
\footnotesize
\begin{tabular}{|p{\linewidth}|}\hline
\begin{description}
\item[\em Severity 1:]
A failure which could result in the loss of the human-rated
system, the loss of flight or ground personnel, or a permanently
disabling personnel injury.
\item[\em Severity 1N:]
 A failure which would otherwise
be Severity 1 but where an established mission procedure precludes
any operational scenario in which the problem might occur, or the
number of detectable failures necessary to result in the problem
exceeds requirements.
\item[\em Severity 2:]
A failure which could result in loss of
critical mission support capability. 
\item[\em Severity 2N:]
A failure which would
otherwise be Severity 2 but where an established mission procedure
precludes any operational scenario in which the problem might occur
or the number of detectable failures necessary to result in the
problem exceeds requirements.
\item[\em Severity 3:]
 A failure which is perceivable
by an operator and is neither Severity 1 nor 2.
\item[\em Severity 4:]
A failure which
is not perceivable by an operator and is neither Severity 1 nor 2.
\item[\em Severity 5:]
A problem which is not a failure but needs to be corrected such as
standards violations or maintenance issues.
\end{description}\\\hline
\end{tabular}
\caption{Severities for human-rated missions.}\label{fig:define1}
\end{figure}
\begin{figure*}
\begin{center}
\includegraphics[width=3in]{expert.pdf}
\end{center}
\caption[Reviewing severity levels]{An agent for reviewing 
issue severity levels.
Gray nodes denote humans.}\label{fig:exprt}
\end{figure*}
 
\clearpage
\section{How it Works}
The essential problem of text mining is {\em dimensionality reduction}.
Standard machine learners work well for instances that are nearly all fully described
using dozens (or fewer) attributes~\cite{witten99}.
But text mining applications (e.g. analyzing PITS detect reports) must process thousands of unique words,
and any particular paragraph may only mention a few of them~\cite{byrn99,salton83introduction}.
Therefore, before we can apply machine learning to text mining, we have to reduce the number
of dimensions (i.e. attributes) in the problem.

There are several standard methods for dimensionality reduction 
such as {\em tokenization, stop lists, stemming, Tf*Idf} and {\em InfoGain}.
All these methods are discussed below.
\subsection{Tokenization}
\fig{token} shows the tokenizer used in this study:
\bi
\item
{\tt Clean} replaces certain punctuation
with blanks spaces. 
\item
The file {\tt bad.txt} contains some
non-printable escape characters which are removed from the issue reports.
\item
Finally, {\tt lowerCase} sends all text to lower case.
\ei
\begin{figure}[!b]
\scriptsize
\begin{verbatim}
clean() {
      gawk '{gsub(Bad,""); print $0}' \
         Bad=`cat $Here/bad.txt` $1 |
      sed 's/[\"\.\*\/\\\(\)\{\}\[\]><\(\)]/ /g'   
}
lowerCase() { 
      tr A-Z a-z $1 ; 
}
\end{verbatim}
\caption{Tokenization}\label{fig:token}
\end{figure}

\subsection{Stop lists}
Another way to reduce dimensionality is to remove ``dull'' words via a 
{\em stop list}
of ``dull'' words. \fig{stop} shows a sample of the stop list used in this
study. IV\&V's chief engineer, Ken Costello, reviewed this list and removed
``counting words'' such as ``one'', ``every'', etc, arguing that ``reasoning about
number of events could be an important requirement''.
\fig{stopper} shows code for a stop-list function.
Note that our code supports use a {\em keep list} of words we want to retain
(but, in this study, the keep list was empty).
\begin{figure}
\begin{alltt}\scriptsize
a           about    across   again      against
almost      alone    along    already    also
although    always   am       among      amongst
amongst    amount   an       and        another
any         anyhow   anyone   anything   anyway
anywhere    are      around   as         at
...         ...      ...      ...        ...  
\end{alltt}
\caption[Stop words]{24 of the 262 stop words used in this study.}\label{fig:stop}
\end{figure}

\begin{figure}
\scriptsize
\begin{verbatim}
stops()     { gawk ' 
   NR==1 {  
        while (getline < Stops)  Stop[$0] = 1;
        while (getline < Keeps)  Keep[$0] = 1; 
    }
    { for(I=1;I<=NF;I++) 
        if (Stop[$I] && ! Keep[$I]) 
            $I=" "
       print $0
    }'  \
      Stops="$Here/stop_words.txt" \
      Keeps="$Here/keep_words.txt"  \
     $1
}
\end{verbatim}
\caption{Applying a stop-list.}\label{fig:stopper}
\end{figure}
\subsection{Stemming}
Terms with a common stem will
usually have similar meanings. For example, all these words relate to the same concept.
\bi
\item
        CONNECT
    \item    CONNECTED
     \item   CONNECTING
     \item   CONNECTION
     \item   CONNECTIONS
\ei
Porter's stemming algorithm~\cite{porter80}
 is the standard stemming tool. It repeatedly replies a set of pruning rules to the end of words until
the surviving words are unchanged. The pruning rules ignore the semantics of a word and just perform syntactic pruning (e.g. \fig{stem1}).
\begin{figure} \scriptsize \begin{verbatim}
RULE                EXAMPLE
----                -------
ATIONAL ->  ATE     relational     ->  relate
TIONAL  ->  TION    conditional    ->  condition
                    rational       ->  rational
ENCI    ->  ENCE    valenci        ->  valence
ANCI    ->  ANCE    hesitanci      ->  hesitance
IZER    ->  IZE     digitizer      ->  digitize
ABLI    ->  ABLE    conformabli    ->  conformable
ALLI    ->  AL      radicalli      ->  radical
ENTLI   ->  ENT     differentli    ->  different
ELI     ->  E       vileli         ->  vile
OUSLI   ->  OUS     analogousli    ->  analogous
IZATION ->  IZE     vietnamization ->  vietnamize
ATION   ->  ATE     predication    ->  predicate
ATOR    ->  ATE     operator       ->  operate
ALISM   ->  AL      feudalism      ->  feudal
IVENESS ->  IVE     decisiveness   ->  decisive
FULNESS ->  FUL     hopefulness    ->  hopeful
OUSNESS ->  OUS     callousness    ->  callous
ALITI   ->  AL      formaliti      ->  formal
IVITI   ->  IVE     sensitiviti    ->  sensitive
BILITI  ->  BLE     sensibiliti    ->  sensible
\end{verbatim} \caption{Some stemming rules.}\label{fig:stem1}
\end{figure}

Porter's stemming algorithm has been coded in any 
number of languages\footnote{\url{http://www.tartarus.org/martin/PorterStemmer}} such as the Perl {\em stemming.pl}
used in this study (see \fig{stem2}).
\begin{figure} \scriptsize \begin{verbatim}
stemming()  { perl $Here/stemming.pl $1 ; }
\end{verbatim} \caption{Using a downloaded stemmer.}\label{fig:stem2}
\end{figure}

Stemming is the end of our pre-processing (a sequence that began with
the {\tt clean} function shown above). Recall that
the complete sequence was
\[\scriptsize
clean \rightarrow lowerCase\rightarrow stops \rightarrow stems 
\]
This full sequence is shown in \fig{all}. 
\begin{figure} \scriptsize \begin{verbatim}
selectColumns() {
    gawk -F, '$3 {OFS=","; print $4 "," $3}' -
}
cleans() {
    for i in $Files; do
        (cd $Dir; clean tab${i}5.csv 2> /dev/null | 
        lowerCase | 
        stops | 
        stemming | 
        selectColumns > $Temp/ok_$i 
    done
}
Files="a b c d e
Dir=$Root/mine/trunk/doc/07/telling/data/raw 
cleans
\end{verbatim}
\caption{Preparation.}\label{fig:all}
\end{figure}


\subsection{Tf*IDF}
Tf*Idf is shorthand for ``term frequency times inverse document
frequency''. This calculation models the intuition that jargon
usually contains technical words that appear a lot, but only in a
small number of paragraphs.  For example, in a document describing
a space craft, the terminology relating to the power supply may be
appear frequently in the sections relating to power, but nowhere
else in the document.

Calculating Tf*Idf is a relatively simple matter.
If there be $Words$ number of document
and each
word $I$ appear $Word[I]$ number of times inside a set of $Documents$
and if
$Document[I]$ be the documents containing $I$,
then:
\[
Tf*Id = Word[i]/Words*log(Documents/Document[i])
\]

\begin{figure} \scriptsize \begin{verbatim}
#update counters for all words in the record
function train()  {
    Documents++; 
    for(I=1;I<NF;I++) {
        if( ++In[$I,Documents]==1) 
            Document[$I]++   
        Word[$I]++    
        Words++ 
   }
}
# computer tfidf for one word
function tfidf(i) { 
    return Word[i]/Words*log(Documents/Document[i]) 
}
\end{verbatim} \caption{tfidf.awk.}\label{fig:tfidfawk}
\end{figure}

\begin{figure} \scriptsize \begin{verbatim}
tfidf() { 
    gawk  -f tfidf.awk --source '
      { train() }
  END { OFS=","; for(I in Word) print I, tfidf(I) } ' $1 ; 
      } ' $1 
} 
tfidf | sort -t, -n +0 | tail -100
\end{verbatim} \caption[Finding the 100 highest 
                        Tf*Idf words]{Finding the 
              100 highest Tf*Idf words using the $tfidf.awk$ code of \fig{tfidfawk}. 
         }\label{fig:tfidf}
\end{figure}

%\begin{figure*}
%\scriptsize
%\begin{verbatim}
%     1	learn() {
%     2	        X=$1
%     3	        cd $Temp
%     4	        cp $HOME/svns/wisp/trunk/weka/lib/weka.jar $Temp
%     5	        java -cp ./weka.jar weka.core.converters.CSVLoader $X.csv > $X.arff
%     6	        java   -Xmx1024M -cp ./weka.jar \
%     7	                weka.filters.supervised.attribute.AttributeSelection \
%     8	            -S "weka.attributeSelection.Ranker -T -1.7976931348623157E308 -N -1"  \
%     9	            -E  "weka.attributeSelection.InfoGainAttributeEval"                    \
%    10	            -i  $X.arff \
%    11	                -o ${X}_fs.arff
%    12	
%    13	        for i in 100 50 25 12 6 3
%    14	        do 
%    15	                printf "\n\n---| $X $i  |------------------------\n\n"
%    16	                java  $java  -Xmx1024M -cp ./weka.jar \
%    17	                        weka.filters.unsupervised.attribute.Remove  -R "${i}-100" \
%    18	                        -i ${X}_fs.arff  \
%    19	                        -o ${X}_fs${i}.arff
%    20	                printf "learning...\n\n"
%    21	                java  $java  -Xmx1024M -cp ./weka.jar \
%    22	                        weka.classifiers.rules.JRip -F 3 -N 2.0 -O 2 -S 1 \
%    23	                        -i -t  ${X}_fs${i}.arff 
%    24	        done 
%    25	}
%\end{verbatim}
%\caption{Source code for the data mining.}\label{fig:reduce}
%\end{figure*}
%


The standard way to use this measure  is to cull all but the $k$ top Tf*Idf ranked
stopped, stemmed tokens. This study used $k=100$ (see \fig{tfidfawk} and \fig{tfidf}).
   
\subsection{InfoGain}

According to the $InfoGain$ measure,
the {\em best} words  are those that  
{\em most simplifies} the target
concept (in our case, the distribution of severities).
Concept ``simplicity'' is measured using information theory.
Suppose a data set has 80\% severity=5 issues and  20\% severity=1
issues.
Then that data set has a class distribution $C_0$ 
with classes $c(1)=severity5$ and $c(2)=severity1$
with frequencies $n(1)=0.8$ and $n(2)=0.2$.
The
number of bits required to encode an arbitrary class 
distribution $C_0$ is $H(C_0)$ defined as follows:
\begin{equation}\label{eq:ent}{
\left.\begin{array}{rcl}
N&=&\sum_{c{\in}C}n(c)\\
p(c)& =& n(c)/N \\
H(C)&=& -{\sum}_{c{\in}C} p(c)log_2p(c)
\end{array}\right\}
}\end{equation}

If $A$ is a set of attributes, the number of bits required to encode
a class after observing an attribute is:
\[H(C|A) = -{\sum}_{a{\in}A} p(a) {\sum}_{c{\in}C} p(c|a)log_2(p(c|a)\]
The highest ranked
attribute $A_i$ is the one with the largest {\em information gain};
i.e the one that most
reduces the encoding required for the data {\em after}
using that attribute; i.e.
\begin{equation}\label{eq:infogain}
InfoGain(A_i) = H(C) - H(C|A_i)
\end{equation}
where $H(C)$ comes from \eq{ent}.
In this study, we will use InfoGain to find  the top $N \in \{100,50,25,12,6,3\}$ most informative tokens. 
%\begin{figure}
%\begin{center}
%\begin{tabular}{|c|c|c|}\hline
%l & p & s\\
%\includegraphics[width=1in]{sever_l.pdf} &
%\includegraphics[width=1in]{sever_p.pdf} &
%\includegraphics[width=1in]{sever_s.pdf}\\\hline
%\end{tabular}
%\end{center}
%\caption{Severities.}\label{fig:severs}
%\end{figure}
%
%\begin{figure*}[!b]
%\begin{center}
%\begin{tabular}{p{0.51in}r|p{0.7in}|p{0.8in}|p{0.7in}|p{0.8in}|p{0.5in}|}
%\multicolumn{2}{l}{project=l}       &\multicolumn{3}{c}{Found in}\\\cline{3-5}
%   		  &	                &Requirements& Design& Implementation\\\cline{1-5}
%  Created in &Requirements     &28          &     8 &   79\\\cline{3-5}
%             &Design           &            &    23 &     \\\cline{3-5}
%             &Implementation   &            &       &   15\\\cline{3-5}
%\\
%\multicolumn{2}{l}{project=p}       &\multicolumn{3}{c}{Found in}\\\cline{3-7}
%           &                 & Design
%					& SW requirements design
%					& SW Preliminary design
%					& Implementation
%					& SW implementation\\\hline
% Created in &Design                            &362          &    &      &      &\\\cline{3-7}
%            &SW requirements design            &             &    &   50 &       & 87\\\cline{3-7}
%            &Subsystems requirements design    &             &    &      &        &19\\\cline{3-7}
%            &Implementation                    &             &    &      &    69&\\\cline{3-7}
%            &SW implementation                 &             &    &      &       & 165\\\cline{3-7}
%\end{tabular}
%\end{center}
%\caption[Leakage matrices]{Leakage matrices for project=l (above) and project=b (below).}\label{fig:leaks}
%\end{figure*}

\subsection{Rule Learning}

A data miner was then called
to learn rules that  predict for the severity attribute using the terms found above.
The learner used here was a JAVA version of Cohen's RIPPER rule learner~\cite{cohen95r,witten05}.
RIPPER  is useful for generating very small rule sets.
 The generated rules
are of the form
\mbox{$if \rightarrow then$}:
\[\scriptsize
\underbrace{Feature_1 = Value_1 \wedge Feature_2 = Value_2 \wedge \ldots }_{condition} \longrightarrow 
\underbrace{Class}_{conclusion}\]

RIPPER, is a {\em covering} algorithm that runs over the data in
multiple passes. Rule covering algorithms
learns one rule at each pass for the {\em majority class}.
All the examples
that satisfy the conditions are marked as {\em covered} and removed
from the data set. The algorithm then recurses on the remaining data. 
The
output of a rule covering algorithm is an ordered {\em decision list} of rules where
$rule_j$ is only tested if all conditions in $rule_{i<j}$ fail. 

One
way to visualize a covering algorithm is to imagine the data as a
table on a piece of paper. If there exists a clear pattern between
the features and the class,define that pattern as a rule and cross
out all the rows covered by that rule.  As covering recursively
explores the remaining data, it keeps splitting the data into:\bi\item
what is easiest to explain, and\item any remaining ambiguity that
requires a more detailed analysis.\ei

%\noindent
%For each data mining experiment:
%\bi
%\item The input is \$X.arff 
%(and $\$X \in \{a,b,c,d,e\}$)
%which contains the frequency counts of
%the top 100 terms found via TF*IDF.
%\item
%The output is a set of rules predicting
%for issue severity.
%\ei
%
% 
%\noindent
%\fig{reduce} shows the 
%source code for the 
%data mining:
%\bi
%\item Line 2 catches the name of the input file;
%\item Line 3 moves the program to a temporary directory (since the code is about to
%generate several intermediary files);
%\item Lines 4 and 5 prepare the data for the WEKA data mining toolkit: line 4 copies the WEKA
%source code to the temporary directory and line 5 converts the csv file holding the issue reports to  the
%.arff file format used by the WEKA.
%\item Lines 6 to 12 run the infogain feature subset selector. A new arff file is generated (\$X\_fs.arff)
%that sorts the attributes top to bottom according to their information content.
%\item Lines 13 to 27 build rules using the top $N \in \{100,50,25, 12, 6,3\}$ ranked terms.
%Line 16 to 19 remove some of the terms from \$X\_fs.arff, store the remaining terms in \$X\_fs\$N.arff,
%then learns rules from those terms using the RIPPER rule learner.
%\ei
%
\subsection{Assessing the Results}
It is a methodological error to assess the rules learned from a data miner using the data used in training.
Such a {\em self-test}
can lead to an over-estimate of the value of
that model.

{\em Cross-validation}, on the other hand,
assesses a learned model using data {\em not}
used to generate it.
The data is divided into, say, 10 buckets. Each bucket is set aside as a test set and
a model is learned from the remaining data. This learned model is then assessed using the
test set. Such cross-validation studies
are the 
preferred evaluation method when the
goal  is to produce predictors intended to  predict future 
events~\cite{witten05}. 

Mean results from a 10-way cross-validation can be assessed via a {\em confusion matrix}
such as  \fig{10way}. 
\begin{figure}
\small
\begin{verbatim} 
  a   b   c   d   <-- classified as
--- --- --- ---
321  12  21   0 |   a = 1
157  41   8   1 |   b = 2
 49   3 259   0 |   c = 3
 21   1   2   2 |   d = 4
\end{verbatim}
\caption{Sample 10-way classification results.}\label{fig:10way}
\end{figure}
In that figure,    some rule learner has generated predictions for classes \{a,b,c,d\} which denote
issues of severity \{1,2,3,4\} (respectively). As shown top left of this matrix,
the rules correctly classified issue reports
of severity=1 as severity=1 321 times (mean results in 10-way cross-val).
However, some severity=1 issues were 
incorrectly classified as severity=2 and severity=3 in 12 and 21 cases (respectively).

A confusion matrices can be summarized as follows.
Let $\{A,B,C,D\}$ denote the
true negatives, 
false negatives, 
false positives, and 
true positives
(respectively). When predicting for class ``a'', then for \fig{10way}:
\bi
\item
A are all the examples where issues of severity=1 were classified as 
severity=1; i.e. A=321.
\item
B are all the examples where lower severity issues were 
classified as severity=1; i.e. B=157+49+21;
\item
C are all the examples where severity=1 issues were classified as something else;
i.e. C=21+12
\item
D are the remaining examples; i.e. D=41+8+1=2+259+0+1+2+2.
\ei
$A,B,C,D$ can be combined in many ways. 
Recall (or $pd$) comments on how much of the target was found.
\begin{equation}
pd=recall=D/(B+D)
\end{equation}
Precision (or $prec$) comments on how many of the instances that
triggered the detector actually containing the target concept.
\begin{equation}
prec=precision=D/(D+C)\\
\end{equation}
The $f$-measure is the harmonic mean of precision and 
recall. It has the property that if {\em either} precision or recall
is low, then the $f$-measure is decreased. The $f$ measure is useful
for dual assessments that include {\em both} precision and recall.
\begin{equation}
\mbox{{\em f-measure}}=\frac{2 \cdot prec \cdot pd}{prec + pd}\\
\end{equation}
 
\begin{figure}
\small
\begin{center}
\begin{tabular}{rrr|r}
$precision$ & $pd=recall$ & $f$-measure &  severity\\\hline
0.893 &    0.833  &   0.862 &   1\\
0.586  &   0.907  &   0.712  &  2\\
0.719  &   0.198  &   0.311 &   3\\
0.667  &   0.077  &   0.138 &   4
\end{tabular}  
\end{center}
\caption{Some precision, recall, f-measures
from \fig{10way}.}\label{fig:prf1}
\end{figure}
\begin{figure}[!b]
\footnotesize
\begin{center}\begin{tabular}{lrrr}
data set & severity & number\\\hline
a        & 1        & 0       \\
         & 2        & 311       \\
         & 3        & 356     \\
         & 4        & 208     \\
         & 5        & 26     \\\hline
b        &  1       & 0       \\
        & 2        & 23      \\
         & 3        & 523     \\
         & 4        & 382     \\
         &  5       & 59      \\\hline
c        & 1         & 0      \\
         & 2         & 0       \\
         &  3       & 132     \\
         & 4        & 180     \\
        &  5        & 7       \\\hline
d       &  1        & 0        \\
         &  2        & 1        \\
         & 3        & 167      \\
          & 4       & 13       \\
          & 5       & 1       \\\hline
e        &  1       & 0        \\
         &  2       & 24      \\
         &  3       & 517      \\
         &   4      & 243      \\
          & 5       & 41       
\end{tabular}\end{center}
\caption{Data sets in the this study.}\label{fig:domains}
\end{figure}
\begin{figure}[!b]
\begin{center}
\includegraphics[width=1.6in]{prep_a.pdf}
\includegraphics[width=1.6in]{prep_b.pdf}
\includegraphics[width=1.6in]{prep_c.pdf}
\includegraphics[width=1.6in]{prep_d.pdf}
\includegraphics[width=1.6in]{prep_e.pdf}
\end{center}
\caption{Effects of stopping and stemming.}\label{fig:stopstem}
\end{figure}

%Another statistic is relative weighted
%sum of $f$-measures times their domain importance. If 
%severities
%$\{s_1,s_2,s_3,s_4,s_5\}$
%represent severities \{1,2,3,4,5\}, each of which has
%exponentially more important by some factor $\alpha$,
%then:
%\[
%W= \frac{\sum_i^5 frequency(s_i)*\alpha^{5-i}}{\sum_i^5 \alpha^{5-1}
%}
%\]
Note that 
all these measures fall in the range \[0\le \{pd,prec,f\} \le 1\]Also,
the {\em larger} these values, the better the model.
\fig{prf1} shows the $precision$, $recall$, and $f$-measure values
for \fig{10way}.

%\section{start}
%
%The first of these principles is simply this: {\princa}.
\section{Results}
 
\subsection{Data}
The above methods where applied to \{a,b,c,d,e\},
five anonymous PITS projects supplied by Ken Costello
(see \fig{domains}).
All these systems were robotic.
Note that this data has no severity one issues
(these are quite rate and few severity five issues
(these often not reported since they have such a low
priority).
 


\subsection{Stopping and Stemming}

\fig{stopstem} shows some disappointing results for stopping and stemming.
In these data sets, stopping and stemming
methods barely reduced the number of tokens.
\begin{figure}
\begin{center}
\includegraphics[width=3.5in]{tfidf.pdf}
\end{center}
\caption[Tf*Idf scoring for the stopped, stemmed tokens]{Tf*Idf scoring for 
the stopped, stemmed tokens.  Note that most tokens can be ignored  since
they have very low Tf*Idf scores.}\label{fig:tfidf3}
\end{figure}


\subsection{Tf*Idf}
Tf*Idf proved to be more powerful than stopping or stemming.
\fig{tfidf3}  shows that in all data sets, there exist a very small
number of words with high Tf*Idf scores. 
These top 100 terms are shown in \fig{order1} and \fig{order2}.
We have shown these lists to domain experts but, to date, we have
not found any particular domain insights from these words. However,
as shown below, even if we don't understand {\em why} these terms were
chosen, they are can be used very effectively for the task of predicting
issue severity.
\input{order}
\begin{figure} \scriptsize \begin{verbatim}
NR ==1 { 
	# grab the words we want to count
	while (getline < "top100") Want[$0] = 1;
    # write the header
    for(I in Want) 
              printf("%s,",I); 
    print "severity"
}
NR > 1 { # rewrite each record as counts of "Want" 
        gsub(/ /,"",$2);  counts($1,Want,  $2) 
}
function counts(str,want,klass,   sum,out,i,j,n,tmp,got) {
    n=split(str,tmp," ");
    for(i=1;i<=n;i++) 
        if (tmp[i] in want) 
             got[tmp[i]]++;
    for(j in want) {
        sum += got[j]
        out = out got[j]+0 ",";  
    }
    if (sum)
        print out "_" klass
}
\end{verbatim}
\caption{Re-writing issue reports as frequency counts.}\label{fig:counter}
\end{figure} 
\begin{figure}[!t]
\begin{center}
\includegraphics[width=3.5in]{f.pdf}
\end{center}
\caption[Frequency counts in the data]{Frequency counts seen in the cells
of our data. Note that our data is mostly sparse:
only 10\% of the time (or less) were there frequency counts at or over 1.
In most data sets, frequency counts of 0 (i.e. empty cell)
appeared in 90\%
 of the cells..}\label{fig:sever}
\end{figure}


\subsection{Learning} 
The issue reports
for each data set were then rewritten as frequency counts for those top 100 tokens
(with the severity
value for each record written to the end of line-
see \fig{counter}). 
As shown in \fig{sever} the resulting data sets
are quite sparse. This figure
shows the distributions of the frequency counts 
of the cells in the data sets. Note that most cells have a zero
frequency count; 10\% of the cells have a frequency count of one, 
and frequency counts higher  than 10 
occur in only $\frac{1}{100}\%$ of cells, or less.

\fig{a100}
shows the rules and confusion matrix see when
learning from 
the top 100 tokens of data set ``a''.
This rule set is a little hard to read  so \fig{a3}
shows
the same experiment, but only using the top 3 ranked tokens.
In those rules {\tt sr} is a stemmed version of {\tt srs}; i.e.
systems requirements specification.
Note that the rules of \fig{a100} use
only  a subset of the 100 terms in the data set.
That is, for data set ``a'', there exists
a handful of terms that most predict for issue
severity.
% A=0,B=0.78,C=0.683,D=0.196,E=0, X=16*A+8*B+4*C+2*D+E,W is X/31,F is (A+B+C+D+E)/5.  
Similar results hold for
same results repeat for data sets \{b,c,d,e\} (see \fig{b100} to \fig{e3}).
That is, even when learning from all 100 tokens, most of the rules
use a few dozens terms or less.
Even though few tokens were used, in many cases, the $f$ measures are quite
large:
\bi
\item Data set ``a'', for issues of severity=2,  $f=78{\ldots}82\%$;
\item Data set ``a'', for issues of severity=3,  $f=69{\ldots}71\%$;
\item Data set ``b'', for issues of severity=3,  $f=70{\ldots}71\%$;
\item Data set ``c'', for issues of severity=3,  $f=80{\ldots}92\%$;
\item Data set ``c'', for issues of severity=4,  $f=86{\ldots}92\%$;
\item Data set ``d'', for issues of severity=3,  $f=96{\ldots}98\%$;
\item Data set ``d'', for issues of severity=4,  $f=87{\ldots}87\%$;
\item Data set ``e'', for issues of severity=3,  $f=79{\ldots}80\%$;
\ei
These results are better than they might first appear:
\bi
\item
These results are listed in the format, e.g. of $f=79{\ldots}80\%$.
and show the results from using the $N=3{\ldots}N=100$ tokens.
Note how using just a vanishingly small number of tokens
performed nearly as well as using a much larger number of tokens.
\item Recall
that these are all results from a 10-way cross-validation
which usually over-estimates model error~\cite{demsar06}, That is,
the real performance values are {\em higher} than the values
shown above.
\ei

For other severities, the results are not as positive. 
Recalling \fig{domains},
none of
our data sets had severity=1 errors so the absence of severity=1
results in the above list is not  a concern. However, not
all datasets resulted in good predictors for severity=2 errors.
In all cases where this was observed, the data set had very
few examples of such issues:
\bi 
\item 
Data set ``b'', only has 22 records of severity=2;
\item
Data set ``c'', has zero records of severity=2;
\item
Data set ``d'', only has 1 record of severity=2;
\item
Data set ``e'', only has 21 record of severity=2;
\ei
\begin{figure*}
\scriptsize
\begin{verbatim}
          if  CONDITION                                                    then  SEVERITY  USED / INCORRECT
          if (script <= 0) and (section >= 2) and (l4 >= 1) and (cdh >= 1) then    4      35.0 /   0.0
     else if (sr <= 1) and (issu >= 1) and (code >= 3)                     then    4      12.0 /   1.0
     else if (sr >= 2) and (rvm >= 1)                                      then    2     183.0 /   9.0
     else if (sr >= 2) and (l4 >= 1)                                       then    2      55.0 /   1.0
     else if (within >= 2) and (state <= 0) and (system <= 0)              then    2      22.0 /   2.0
     else if (verifi >= 1) and (fsw >= 1)                                  then    2      10.0 /   1.0
     else if (control >= 1) and (code >= 1) and (attitud >= 4)             then    2       5.0 /   0.0
     else if (l3 >= 2) and (obc <= 0) and (perform <= 0)                   then    2      19.0 /   7.0
     else if (script >= 1) and (trace >= 1)                                then    2       3.0 /   0.0
     else if true                                                          then    3     554.0 / 219.0 
     
        a   b   c   d   <-- classified as
      321  12  21   0 |   a = 3
      157  41   8   1 |   b = 4
       49   3 259   0 |   c = 2
       21   1   2   2 |   d = 5
\end{verbatim}
\caption{Data set ``a''; top 100 tokens; learned rules.}\label{fig:a100}
\end{figure*}  
\begin{figure*}\scriptsize \begin{verbatim}
          if  CONDITION              then  SEVERITY  USED / INCORRECT
          if (rvm <= 0) and (sr = 3) then     4       52.0 /  21.0
     else if (sr >= 2)               then     2      289.0 /  54.0
     else if true                    then     3      557.0 / 245.0
     

       a   b   c   d   <-- classified as
      314  13  27   0 |   a = 3
      158  25  24   0 |   b = 4
       69  10 232   0 |   c = 2
       25   0   1   0 |   d = 5
\end{verbatim}
\caption{Data set ``a''; top 3 tokens; learned rules. }\label{fig:a3}
\end{figure*}  
\begin{figure*}
\scriptsize
\begin{verbatim}
          if  CONDITION                                                      then  SEVERITY  USED / INCORRECT
          if (arrai >= 2) and (line >= 1) and (us <= 1)                      then    2       7.0 /   0.0
     else if (base >= 4)                                                     then    2       3.0 /   0.0
     else if (fsw <= 0) and (declar >= 1)                                    then    4      86.0 /  26.0
     else if (fsw <= 0) and (complet >= 1) and (section <= 0)                then    4      27.0 /   4.0
     else if (fsw <= 0) and (statement >= 1) and (need <= 0) and (valu <= 0) then    4      36.0 /  10.0
     else if true                                                            then    3     819.0 / 332.0
     
        a   b   c   d   <-- classified as
      120 253   0   4 |   a = 4
       69 445   0   7 |   b = 3
       11  47   0   0 |   c = 5
        2   9   0  11 |   d = 2
\end{verbatim}
\caption{Data set ``b''; top 100 tokens; learned rules.}\label{fig:b100}
\end{figure*}  
\begin{figure*}\scriptsize \begin{verbatim}
           if  CONDITION                   then  SEVERITY  USED / INCORRECT
           if (fsw <= 0) and (declar >= 1) then    4      94.0 /  34
      else if true                         then    3     884.0 / 383.0

        a   b   c   d   <-- classified as
       60 317   0   0 |   a = _4
       20 501   0   0 |   b = _3
        3  55   0   0 |   c = _5
       11  11   0   0 |   d = _2
\end{verbatim}
\caption{Data set ``b''; top 3 tokens; learned rules. }\label{fig:b3}
\end{figure*}  

\begin{figure*}
\scriptsize
\begin{verbatim}
          if  CONDITION                                     then  SEVERITY  USED / INCORRECT
         if (section >= 2) and (matrix >= 1) and (icd >= 1) then      5      7.0 /  1.0
    else if (softwar >= 1)                                  then      3     95.0 /  3.0
    else if (parent <= 0) and (trace <= 0)                  then      3     48.0 / 14.0
    else if true                                            then      4    167.0 /  4.0
     
        a   b   c   <-- classified as
      162  14   4 |   a = _4
        7 123   0 |   b = _3
        2   1   4 |   c = _5
\end{verbatim}
\caption{Data set ``c''; top 100 tokens; learned rules.}\label{fig:c100}
\end{figure*}  
\begin{figure*}\scriptsize \begin{verbatim}
          if  CONDITION               then  SEVERITY  USED / INCORRECT
          if  (softwar >= 1)          then      3     95.0 /  3.0
     else if  true                    then      4    222.0 / 44.0
     
        a   b   c   <-- classified as
      169  11   0 |   a = _4
       37  93   0 |   b = _3
        6   1   0 |   c = _5
\end{verbatim}
\caption{Data set ``c''; top 3 tokens; learned rules. }\label{fig:c3}
\end{figure*}  

\begin{figure*}
\scriptsize
\begin{verbatim}
          if  CONDITION               then  SEVERITY  USED / INCORRECT
          if (switch >= 2)            then     4     11.0 / 1.0
     else if true                     then     3    167.0 / 4.0)
 
        a   b   c   d   <-- classified as
        0   0   1   0 |   a = _2
        0  10   2   0 |   b = _4
        0   1 163   0 |   c = _3
        0   0   1   0 |   d = _5
\end{verbatim}
\caption{Data set ``d''; top 100 tokens; learned rules. }\label{fig:d100}
\end{figure*}  
\begin{figure*}\scriptsize \begin{verbatim}
          if  CONDITION               then  SEVERITY  USED / INCORRECT
          if  (switch >= 2)           then     4      11.0 / 1.0
     else if  true                    then     3     167.0 / 4.0)
     
        a   b   c   d   <-- classified as
        0   0   1   0 |   a = _2
        0  10   2   0 |   b = _4
        0   1 163   0 |   c = _3
        0   0   1   0 |   d = _5
\end{verbatim}
\caption{Data set ``d''; top 3 tokens; learned rules. }\label{fig:d3}
\end{figure*}  

\begin{figure*}
\scriptsize
\begin{verbatim}
          if  CONDITION                                                      then  SEVERITY  USED / INCORRECT
          if (trace >= 1) and (test >= 1) and (case >= 3)                    then     2     3.0  /   0.0
     else if (error >= 1) and (line >= 2)                                    then     2     3.0  /   0.0
     else if (convent >= 2) and (declar <= 0) and (function <= 0)            then     5     6.0  /   0.0
     else if (case >= 2) and (sr >= 3)                                       then     5     6.0  /   1.0
     else if (refer >= 1) and (section >= 3) and (refer <= 1)                then     5     7.0  /   2.0
     else if (the >= 1) and (fsw >= 2)                                       then     4    47.0  /   5.0
     else if (control <= 0) and (convent >= 3)                               then     4    25.0  /   3.0
     else if true                                                            then     3   723.0  / 214.0
     
        a   b   c   d   <-- classified as
        1  20   0   0 |   a = _2
        3 490   3  20 |   b = _3
        0  26   9   6 |   c = _5
        0 167   1  74 |   d = _4
\end{verbatim}
\caption{Data set ``e''; top 100 tokens; learned rules.}\label{fig:e100}
\end{figure*}  
\begin{figure*}\scriptsize \begin{verbatim}
          if  CONDITION                     then  SEVERITY  USED / INCORRECT
          if  (the >= 1) and (convent >= 3) then    4       30.0 /   8.0
     else if  true                                  3      790.0 / 275.0

        a   b   c   d   <-- classified as
        0  21   0   0 |   a = _2
        0 515   0   1 |   b = _3
        0  34   0   7 |   c = _5
        0 222   0  20 |   d = _4
\end{verbatim}
\caption{Data set ``e''; top 3 tokens; learned rules. }\label{fig:e3}
\end{figure*}  
\section{Discussion}

%The adage ``garbage in, garbage out''
%refers to the way computers 
%can unquestioningly process any nonsense input
%and generate seemingly impressive, but totally nonsensical
%output. Wikipedia speculates\footnote{
%\url{http://en.wikipedia.org/wiki/Garbage_in,_garbage_out}}
% that the adage
%may be first attributed, in a verbose form,
%to Charles Babbage (1791 to 1871). Babbage, designer of  the first
%programmable devices, remarked that:
%\begin{quote}
%On two occasions I have been asked, 'Pray, Mr. Babbage, 
%if you put into the machine wrong figures, will the right answers come out?' 
%I am not able rightly to apprehend the kind of confusion of ideas that could provoke such a question.
%\end{quote}
%A related, but more worrying, problem  is ``garbage in, gospel
%out''. In this second form of GIGO, the audience accepts bogus
%results from computer systems with unquestioning faith.  Data mining
%professionals must remain forever vigalent for the GIGO problem.
%In the $21^{st}$ century, there now exist many public domain data
%miners which can be installed in minutes and process hundreds of
%thousands of records in a few hours (or less). But before we can
%believe the output of such miners, we need to first trust that the
%input is worthy of mining.

Over the years, the Project Issue Tracking System (PITS) has been
extensively and repeatedly modified.  Prior attempts at generating
generalized conclusions from PITS have required significant levels
of manual, hence error-prone, processing.

Here, we show that conclusions can be reached from PITS without
heroic effort. Using text mining and machine learning methods, we
have shown that it is possible to automatically generate predictors
for severity levels from the free text entered into PITS.

Better yet, our rules are self-certifying. Our data mining
generation methods builds the rules and prints performance 
statistics (the confusion matrix). With those statistics,
these
 rules support
the following dialogue:
\begin{quote}
{\em Tim wrote the problem report and he says this is a severity 5 issue. But the agent
says that its a severity 3 issue with probability 83\%. Hmmm... the agent seems
pretty sure of itself- better get someone else to take a look at the issue.}
\end{quote}
When this work began, we thought that we were conducting a baseline
text mining experiment that would serve as a (low)
baseline against which we could assess more
sophisticated methods.
However, for data sets with more that 30 examples of high severity
issues, we always found good issue predictors (with high $f$-measures).

Further, we did so using surprisingly little domain knowledge.
In call cases where large $f$-measures were seen using the
top 100 terms, similar $f$ measures were seen when
using 3 terms. This is a very exciting result since it speaks
to the {\em usability} of this work. 
It would be a simple to matter to apply these rules. E
Given that a few
frequency counts are enough to predict for issue severity,
even a manual method would suffice.

We end this report with one caution.
As seen in \fig{a100} to \fig{e3},
the learned predictors are different for
different data sets. We hence recommend adding these
text mining tools to PITS and, on  a regular basis,
generate new rules relevant to just one project.

\newpage
\bibliographystyle{abbrv}
\bibliography{refs}
\end{document}


\end{document}
\subsection{Another Mining Method}

Since the structured data in PITS is problematic, this research
elected to study PITS' unstructured data. Several fields within the
database support long strings of free text.


\section{Under the Hood}
While
\fig{sever} shows the high-level business view of the tool,
the full details are shown in \fig{process}.
\begin{figure}[!t]
\begin{center}
\includegraphics[width=3.2in]{process.pdf}
\end{center}
\caption{Text mining- the details.}\label{fig:sever}
\end{figure}
Text mining~\cite{byrn99,salton83introduction} is different from machine
learning~\cite{witten99} in that the latter deals with more structured data.
A standard machine learning task is to:
\bi
\item 
Input a table characterized by
dozens (or less) of attributes;
\item And output 
a theory that connects the independent attributes to a single class attribute.
\ei
Text mining is different in that the number of attributes is much larger
and the table of data may be vary sparse: 
\bi
\item
The number of attributes equals the number of unique words in the documents.
For example, the PITS data 
contains hundreds to thousands of unique words per project.
\item
Most words don't appear in most documents. Hence a matrix storing documents and words
in the rows/columns (respectively) would contain many empty cells.
\ei
\fig{process} converts  a text mining problem ito a machine learning problem.
In essence,
this means finding and deleting all but the most ``important'' words.
This section describes how such ``important'' words are recognized.

\subsection{Tokenization}

\begin{figure}
\begin{alltt}\scriptsize
a           about    across   again      against
almost      alone    along    already    also
although    always   am       among      amongst
amongst    amount   an       and        another
any         anyhow   anyone   anything   anyway
anywhere    are      around   as         at
...         ...      ...      ...        ...  
\end{alltt}
\caption[Stop words]{24 of the 262 stop words used in this study.}
\end{figure}

\begin{figure}
\scriptsize
\begin{verbatim}
stops()     { gawk ' 
   NR==1 {  
        while (getline < Stops)  Stop[$0] = 1;
        while (getline < Keeps)  Keep[$0] = 1; 
    }
    { for(I=1;I<=NF;I++) 
        if (Stop[$I] && ! Keep[$I]) 
            $I=" "
       print $0
    }'  \
      Stops="$Here/stop_words.txt" \
      Keeps="$Here/keep_words.txt"  \
     $1
}
\end{verbatim}
\caption{Tokenization.}\label{fig:tokens}
\end{figure}
\section{Data Mining}
\subsection{Decision Tree Learning}
One way to view OneR's defect predictions rules is a decision tree
of maximum depth one whose leaves are either the label {\em defective}
or {\em defect-free}. The J48 learner builds decision trees of any depth. For example, J48 
executing on the {\em kc4} data set can return:

{\scriptsize\begin{verbatim}
CALL_PAIRS <= 0: defectFree 
CALL_PAIRS > 0
|  NUMBER_OF_LINES <= 3.12: defectFree 
|  NUMBER_OF_LINES > 3.12
|  |  NORMALIZED_CYLOMATIC_COMPLEXITY <= 0.02
|  |  |   NODE_COUNT <= 3.47: defective 
|  |  |   NODE_COUNT > 3.47: defectFree 
|  |  NORMALIZED_CYLOMATIC_COMPLEXITY>0.02: defective 
\end{verbatim}}
\noindent
which may be read as follows: ``a module is defective if it has non-zero call-pairs and has more than
3.12 lines and hasn't  a low normalized cyclomatic complexity (0.02) or it has a low normalized
cyclomatic complexity and a low node-count (up to 3.47)''. 

Note that J48 predictors can be more
complex and explore more special cases than OneR. J48's predictors would out-perform OneR if
defect prediction required such elaboration.

J48 is a JAVA implementation of Quinlan's C4.5 (version 8)
algorithm~\cite{quinlan92}. The algorithm recursively {\em splits}
a data set according to tests on attribute values in order to
separate the possible predictions (although attribute tests are chosen one at a
time in a greedy manner, they are dependent on results of previous
tests). C4.5/J48 uses information theory to assess candidate splits:
the {\em best split} is the one that {\em most simplifies} the target
concept.  
Concept simplicity is measured using information theory.
Suppose a data set has 80\% defect-free modules and  20\% defective modules.
Then that data set has a class distribution $C_0$ with classes $c(1)=defectFree$ and $c(2)=defective$
with frequencies $n(1)=0.8$ and $n(2)=0.2$.
The
number of bits required to encode an arbitrary class distribution $C_0$ is $H(C_0)$ defined as follows:
\begin{equation}\label{eq:ent}{
\left.\begin{array}{rcl}
N&=&\sum_{c{\in}C}n(c)\\
p(c)& =& n(c)/N \\
H(C)&=& -{\sum}_{c{\in}C} p(c)log_2p(c)
\end{array}\right\}
}\end{equation}
A split divides $C_0$ (before the split) into $C_1$ and $C_2$
(after the split). The best split leads to the simplest concepts;
i.e. maximize $H(C_0) - (H(C_1) + H(C_2))$.

Various  {\em attribute subset  selection}
algorithms~\cite{hall03} (hereafter, {\em subsetting}) find what attributes can be deleted, without
damaging the performance of the learned predictor.
The simplest and fastest
subsetting
method is to rank attributes from the most
informative to least informative. After discretizing numeric 
data\footnote{E.g. given an attribute's
minimum and maximum values, replace a particular value $n$ with $(n - min)/((max - min)/10)$.
For more on discretization, see~\cite{dou95}.}
then if $A$ is a set of attributes, the number of bits required to encode
a class after observing an attribute is:
\[H(C|A) = -{\sum}_{a{\in}A} p(a) {\sum}_{c{\in}C} p(c|a)log_2(p(c|a)\]
The highest ranked
attribute $A_i$ is the one with the largest {\em information gain};
i.e the one that most
reduces the encoding required for the data {\em after}
using that attribute; i.e.
\begin{equation}\label{eq:infogain}
InfoGain(A_i) = H(C) - H(C|A_i)
\end{equation}
where $H(C)$ comes from \eq{ent}.
In {\em iterative InfoGain subsetting}, predictors are  learned
using the  $i=1,2...,N$-th top-ranked attributes.
Subsetting  terminates when $i+1$ attributes perform no better than
$i$.


\subsection{l}

\begin{figure}
\scriptsize
\begin{verbatim}
child <= 0
|   buffer <= 0
|   |   sr <= 0
|   |   |   after <= 0
|   |   |   |   gnac <= 0
|   |   |   |   |   statement <= 0
|   |   |   |   |   |   potenti <= 0
|   |   |   |   |   |   |   fswr <= 0
|   |   |   |   |   |   |   |   sb <= 0
|   |   |   |   |   |   |   |   |   variabl <= 0: _3 
|   |   |   |   |   |   |   |   |   variabl > 0: _4 
|   |   |   |   |   |   |   |   sb > 0: _4 
|   |   |   |   |   |   |   fswr > 0: _4 
|   |   |   |   |   |   potenti > 0: _3
|   |   |   |   |   statement > 0: _4 
|   |   |   |   gnac > 0: _4 
|   |   |   after > 0: _4 
|   |   sr > 0: _4 
|   buffer > 0
|   |   cfe <= 1: _3 
|   |   cfe > 1: _4
child > 0: _4 
\end{verbatim}

\begin{verbatim}
  a  b  c   <-- classified as
 76 11  0 |  a = _3
 32 21  0 |  b = _4
  1  0  0 |  c = _2
\end{verbatim}
\caption{"L"'s results with all attributes.}
\end{figure}

\begin{figure}
\scriptsize

\begin{verbatim}
child <= 0
|   after <= 0
|   |   gnac <= 0: _3 
|   |   gnac > 0: _4 
|   after > 0: _4 
child > 0: _4 
\end{verbatim}


\begin{verbatim}
  a  b  c   <-- classified as
 87  0  0 |  a = _3
 48  5  0 |  b = _4
  1  0  0 |  c = _2
\end{verbatim}
\caption{"L"'s results with just
after,
child,
close,
document,
fswr,
gnac,
level,
lroc,
result,
statu.}
\caption{Results: data set l with InfoGain.}
\end{figure}

\section{Text Mining}


Text Analysis software operates in 5 stages:

   1.

      Extraction of the text contained in your documents (meaning conversion of multiple file formats).
   2.

      Lexical analysis: Words identification, optionally using grammatical rules and a lexicon (for example, "bushes" and "bush" can belong to the same word).
   3.

      Semantic analysis: Solve language ambiguities, optionally using a specific dictionary (thesaurus or semantic network). For example, the word "bush" can be related to "George Bush" or to a Plant (Shrub).
   4.

      Statistics: Group together closely related terms appearing throughout the text. For example, "bush" and "president" can be grouped into the "politics" cluster.
   5.

      Sorting (keywords lists) and showing (graphs, etc.) the results. 
\bibliographystyle{abbrv}
\bibliography{refs}
\end{document}

XXX one gram, two gram, three gram
XXX semantic less
XXX normalization
XXX min counts, max counts
XXX symbol table management (words to/from integers)
XXX spare matrix,
XXX dimensionality reduction: svd, tdidf, td, idf, infogain, min/max counts

XXX XXX another set with more sverity 1
%XXX large corpus- standard parts, stablizexe the ontology
