%\documentclass[onecolumn,draftcls,journal,compsoc]{IEEEtran}
%\documentclass[technote]{IEEEtran}
%\documentclass{sig-alternate}
\documentclass{speauth}

\usepackage[dvips,colorlinks,bookmarksopen,bookmarksnumbered,citecolor=red,urlcolor=red]{hyperref}

%\def\baselinestretch{2} 
\usepackage{graphicx}
\usepackage{cite}
\usepackage{wrapfig,url}
\newcounter{over}
\newcounter{max}
\newcommand{\fred}[2]{\setcounter{over}{#2}\addtocounter{over}{#1}}
\newcommand{\boxplot}[5]{%
\scalebox{0.5}{\textcolor{white}{\setcounter{max}{#4}\addtocounter{max}{#5}\fred{#4}{-#2}}%
\begin{picture}(100,10)%
\put(0,0){\line(0,1){8}}%
\put(100,0){\line(0,1){8}}%
%\put(#1,4){\circle*{1}}%
%\put(\themax,4){\circle*{1}}%
\put(#2,4){\line(1,0){\theover}}%
\put(#3,4){\circle*{8}}%
%\put(#4,4){\line(1,0){#5}}%
\put(50,0){\line(0,1){8}}%
\end{picture}}
} 
\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{5cm}{5cm}\selectfont{Draft v5}}}}}
%\makeatother
\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}}

%\usepackage{times}
\usepackage{alltt}
\usepackage{url}
% IEEE Computer Society needs nocompress option
% requires cite.sty v4.0 or later (November 2003)
\usepackage{cite}
% normal IEEE
 % \usepackage{cite}

% correct bad hyphenation here
\hyphenation{op-tical net-works semi-conduc-tor}


\pdfpagewidth=8.5in
\pdfpageheight=11in


\begin{document}
\def\cop{Copyright \copyright\ 2010 John Wiley \&\ Sons, Ltd.}

%\SPE{1}{6}{00}{00}{2000} %for times fonts
\SPE{1}{7}{00}{00}{2010}

\runningheads{A. Nelson et al.}
{Verifying the Scalability of Text Mining Methods Used in STEP-like Corpora}



%\conferenceinfo{PROMISE'09,} {May 18--19, 2009, Vancouver, Canada} 
%\conferenceinfo{~} {~} 

%\CopyrightYear{2009}

%\crdata{978-1-60558-036-4/08/05}


%\CopyrightYear{2008} % Allows default copyright year (200X) to be over-ridden - IF NEED BE.
%\crdata{0-12345-67-8/90/01}  % Allows default copyright data (0-89791-88-6/97/05) to be over-ridden - IF NEED BE.

\title{Verifying the Scalability of Text Mining Methods Used in STEP-like Corpora}
\author{Adam Nelson, Tim Menzies, Gregory Gay\corrauth\comma\footnotemark[1]}

\longaddress{Lane Department of  Computer Science and Electrical Engineering, West Virginia University, Morgantown, WV, USA}


\corraddr{Lane Department of  Computer Science and Electrical Engineering, West Virginia Unviersity, Morgantown, WV, USA}

\footnotetext[1]{E-mail: anelson8@mix.wvu.edu, tim@menzies.us, gregoryg@csee.wvu.edu}


\cgsn{Publishing Arts Research Council}{98--1846389}

\received{1 October 2009}
\revised{?? December 2009}
\noaccepted{}

\keywords{open source, data mining}

%\titlenote{Submitted to the PROMISE 2008 workshop on repeatable SE experiments.
%%A draft version of this paper may be downloaded fro
%\url{http://menzies.us/pdf/08keys.pdf}
%}

%\begin{abstract}
%When researchers want to repeat, improve or refute prior conclusions, it is useful to have
%a
%complete and operational description of prior experiments.
%If those descriptions are overly long or complex, then sharing their details may not be informative.

%OURMINE is a scripting environment for the development and
%deployment of data mining experiments. 
%Using OURMINE,
%data mining novices can specify and execute intricate experiments,  
%while researchers can publish their complete experimental rig alongside their conclusions.
%This is achievable because of OURMINE's succinctness. 
%For example, this paper presents an experiment documented in the OURMINE syntax. %two experiments documented in the OURMINE syntax.
%Thus, the brevity and simplicity of OURMINE recommends it as a better tool for documenting, executing, and sharing data mining experiments.
%\end{abstract}

\begin{center}
  \includegraphics[width=7.0cm]{archeology}
\end{center}

\section{Executive Summary}
This document is the final report of the "HAMLET" task where we tested if the computational core of that tool applies (and can scale) to STEP documents.

In summary, we found  trade-off between the efficacy of HAMLET's analysis and the runtimes of the algorithms. That is, the slower methods (that will not scale) perform arguably better
than the quicker methods that might scale to larger corpuses.
However, and this is very good news, the trade-off is very weak. For STEP-like documents, we found that very little is lost when the faster (more scalable) methods are applied.

In conclusion, we assert that information retrieval methods, like those used in HAMLET, can be applied to STEP-like documents.

\clearpage
\tableofcontents
%\clearpage
%\listoffigures
\clearpage
\section{Background}

Information retrieval (IR) is
\bi
\item
The science of searching for information/meta-data within documents.
\item
IR is interdisciplinary,
based on computer science, mathematics, library science, information
science, information architecture, cognitive psychology, linguistics,
statistics and physics.
\item
We explore IR methods since they are designed to scale to very large corpora.
More rigorous approaches require far CPU and memory and fundamentally
cannot scale to large corpora.
\ei

IR is also the art of exploring very large collections, without first imposing complex
structure on those collections. It it therefore ideally suited to the 
overhead of an engineer building {\bf new} designs while reflecting
over {\em old} designs.
~\\

IR is the core technology used within WVU's HAMLET tool. HAMLET
is a software archaeology tool that checks new designs against
old designs:
\bi
\item
Given a partial description of the current design...
\item
... HAMLET searchers prior designs looking for items that
should be added/deleted to/from the current design.
\ei
HAMLET 
is designed to be ``glue'' that permits the searching of
technical data in large
heterogeneous collections:
\bi
\item
The tool
makes minimal assumptions about the 
nature of the engineering documents being explored.
\item
Specially, HAMLET treats all STEP documents, project memos,
spreadsheets, records in a database, in exactly the same way; namely
as a matrix of $T$ terms in $D$ documents.
\ei

\subsection{Issues of Practicality}
IR works because human languages follow very simple
mathematical patterns. Zipf's Law state that the probability
of finding items at frequency $P$ follows a log-log distribution;
i.e. most things occur very rarely and only a few things occur
very often.
%\begin{center}
%insert % \includegraphics[width=3in]{zipf-drupalorg_0.eps}  
%\end{center}
That is, human technical documents have a very simple and regular
structure. Simple $T*D$ matrices (see $TF*IDF$) are hence often enough to record
and analyze that structure.

Given that regular and repeated structure, the next natural question is ``can we exploit that regularity?''. Specifically, can we compress the data around those
regular structures such that large scale queries can be run, faster, even for very large corpuses?
Any real-world collection of documents many contain 10,000 to 1000,000 of terms and documents. The art of IR is throwing away the irrelevancies.
HAMLET has two such ``compression'' operators:\\

\bi
\item {\bf Reduction:} discard irrelevant terms
\item {\bf Cluster:} group documents together
effectively replacing multiple documents 
with a single meta-document
\ei

For example, Figure 1 groups 
terms by their information content and
the documents by their distance to each other:
\bi
\item We can now discard low information terms (those low in the term tree)
\item We can now group together similar documents (those close to each other)
\ei

\begin{figure}
\begin{center}
\includegraphics[width=2.5in, angle=270]{clusterbig}
\end{center}
\caption{Row and column pruning.}\label{fig:onex}
\end{figure}

\newpage
\section{What is HAMLET, and how can we certify its tools?}

HAMLET is an ``anything browser'' (Figure 2) that aims to reduce the cognitive
overhead of an engineer building {\bf new} designs while reflecting
over {\em old} designs. The tool makes minimal assumptions about the 
nature of the engineering documents being explored
and is designed to be ``glue'' that permits the searching of
technical data in large, heterogeneous collections. 

Using technology from
AI, information retrieval, program comprehension, and text mining,
HAMLET allows designers to ``dig up'' prior designs, study those designs,
and apply any learned insights to new tasks.

However, the ``compression operators'' (see above) upon which HAMLET is constructed must be certified. 
Thus, we have utilized OURMINE (described below) for this certification, as well as
 to verify the theories behind each operator.


\begin{figure}
%\begin{center}
    \includegraphics[width=4.0in]{fig3}
\caption{HAMLET's directed browsing.}\label{fig:hammy}
%\end{center}
\end{figure}


  

\newpage

%\section{Why is it called ``HAMLET''?}

%HAMLET is a ``software archaeology'' tool to  uncover lessons from past
%designs. It was named after the famous Shakespeare quote
%``to be or not to be?''. For the designer of a technical 
%product, the analogous question is ``to do or not to do?''
%HAMLET finds the deltas between the current design and
%old design to compute:
%\bi
%\item ``What else'': what is {\em absent} in
% the current design but is {\em present} in old designs.
%\item ``What not''; what is {\em present} in  the
%current design but is {\em absent} in old designs.
%\ei
%Note that designers are not obliged to always add the ``what else'' results or always avoid the 
%``what not'' results. However, those two queries will allow a designer to assess their current 
%design with respect to the space of prior designs.

%\subsection{Reduction Methods}
%The following methods are Ranked top to bottom, 
%slowest to fastest,
%most-thorough to simplest.

%{\bf PCA:}  PCA (principal components analysis) treats every
%row in $T*D$ as a point in N-dimensional space. PCA seeks new
%dimensions that are better fits to those points.
%For example,
%the data shown below in two dimensions 
%could be approximated in a single new dimension feature
%(shown as a dashed lined).
%\begin{center}
% dsds %\includegraphics[width=2in]{pca.eps}
%\end{center}

%{\bf FASTMAP:} FASTMAP is a heuristic data reduction method
%that uses a heuristic trick to find a line between
%the two
%points that could be furthest apart. A plane is added at right angles
%to the end of
%this line. The line is then pushed into the plane, mapping points in
%$N$ dimensions to $N-1$. This process repeats until, say, $N=50$ and
%the resulting points can be handled with more efficiency or even plotted in a 
%visualization if $N$ is low enough.

%{\bf TF*IDF:} (term frequency times inverse document
%frequency). Zipf's Law tells us that the words that matter
%appear a lot, but this is only useful if the words don't occur
%in the majority of documents (think words like "with", "does", or "their").
%Calculating Tf*Idf is a relatively simple and linear matter.
%Let there be a set of documents $D$ (where each document is itself
%a set) along with a set of terms $T$. Term frequency, $tf(t_i,D_j)$ is the
% number of times the word $t_i$ occurs in document $D_j$.  Document frequency, 
%$df(t_i)$ is the total number of documents the term appears in (helps
%prune out our "with", "does", etc. words).  Specifically,
%\begin{center}
% $Tf*Idf(t,D_j) = \frac{tf(t_i,D_j)}{|D_j|}log(\frac{|D|}{df(t_i)})$
%\end{center}

%Which can be used for term reduction by creating

%\begin{center}
%$Tf*Ifd_{sum}(t)=\displaystyle\sum_{D_j \in D} Tf*Idf(t, D_j)$
%\end{center}
%for each term, sorting the terms on this value,
%and returning the top $N$.


%\section{Introduction}
%A recent survey article~\cite{zannier06} revealed the sad state of
%empirical software engineering. Zannier et al.~\cite{zannier06}
%sampled 5\% of the 1227 papers presented in the 29 history of the
%International Conference on Software Engineering. Of the sampled
%papers, 70\% claimed to contain some form of empirical evaluation.
%However, on closer inspection, Zannier et al. found that most (98\%
%of so-called empirical papers) used self-confirmatory studies where
%developers assessed their own methods (rather than check methods
%from other researchers).
%
%What an we do to improve the poor state-of-the-art in empirical software engineering?
%

% -- CUT OFF HERE FROM ORIGINAL
%Since 2004,  the authors have been involved in an open source data mining experiment. Researchers
%submitting to the PROMISE conference on predictive models in software engineering are encouraged to offer not just conclusions,
%but also the data they used to generate those conclusions. The result is nearly 100 data sets, all on-line,
%freely available for download~\footnote{\url{http://promisedata.org/data}}. 

%The premise of this paper is that after {\em data sharing} comes {\em experiment
%sharing}; i.e.  the PROMISE repository should grow to include not just data, but the code
%required to run experiments over that data. This simplifies the goal of letting other researchers 
%repeat, or even extend, data mining experiments of others. Repeating experiments is not only essential 
%in confirming previous results, but also in providing an inciteful understanding of the fundamentals 
%involving those experiments. Thus, it is important to have a prepared set of clearly defined and operational experiments that can be utilized in order to achieve similar prior results.     

%This simplifies the goal of letting other researchers
%repeat, and maybe even improve, the experimental results of others. 
%Consequently, we have been assessing data mining toolkits such as the 
%WEKA\footnote{\url{http://www.cs.waikato.ac.nz/ml/weka/}} tool of \fig{weka},
%``R''\footnote{\url{http://www.r-project.org/}},
%the ORANGE\footnote{\url{http://magix.fri.uni-lj.si/orange/}} tool of \fig{orange},
%RAPID-I\footnote{\url{http://rapid-i.com/}},
%MLC++~\footnote{\url{http://www.sgi.com/tech/mlc/}}, and 
%MATLAB\footnote{\url{http://www.mathworks.com}}.
%We find that they are
%are 
%not suitable for  
%publishing experiments.  
%Our complaint with these tools is same as that offered by
%Ritthoff et al.~\cite{ritthoff01}:
\begin{figure}
\begin{center}
\includegraphics[width=4in]{weka}
\end{center}
\caption{The WEKA toolit running the J48 decision tree learner.}\label{fig:weka}
\end{figure}

%\begin{figure}
%\begin{center}
%\includegraphics[width=4in]{orange}
%\end{center}
%\caption{Orange's visual programming environment. Green lines indicate data streams passed between functions.}\label{fig:orange}
%\end{figure}

%\begin{figure}
%\begin{center}
%\includegraphics[width=2in]{yale}
%\end{center}
%\caption{Rapid-I's operator trees. From ~\cite{mie06}. Internally, this tree is a nested XML expression that is traversed
%top-down to complete an experiment.}\label{fig:yale}
%\end{figure}
%
%\bi
%\item 
%Proprietary tools such as MATLAB are not freely available.
%\item
% Real-world experiments
%are more complex than 
%running one algorithm. 
%\item
%Rather, such experiments or applications require {\em intricate combinations}
%of a large 
%number of tools that include data miners, data pre-processors and report regenerators.
%\ei

%Many developers and data mining researchers have realized the need to "wire up" data mining tools in order create an interconnection between intricate combinations of tools required for publishable, large-scale experiments. These tools include data miners, data pre-processors and report generators. 

%However, the need to ``wire up'' data miners within a multitude of other tools has been addressed in many ways. 
%In WEKA's visual {\em knowledge flow} programming environment, for example,
%nodes represent different pre-processors/ data miners/ etc while arcs represent how data flows between them.
%A similar visual environment is offered by many other tools including ORANGE (see \fig{orange}).
%The YALE tool (now RAPID-I) built by Ritthoff et al. formalizes these visual environments by generating
%them from  XML
%schemas describing
%{\em operator trees} like \fig{yale}.
%The need to extend data mining tools is well established.

%The need to ``wire up'' data miners within a multitude of other tools has been addressed in many ways. 
%In WEKA's visual {\em knowledge flow} programming environment, for example,
%nodes represent different pre-processors/ data miners/ etc while arcs represent how data flows between them.
%A similar visual environment is offered by many other tools including ORANGE (see \fig{orange}).
%The YALE tool (now RAPID-I) built by Ritthoff et al. formalizes these visual environments by generating
%them from  XML
%schemas describing
%{\em operator trees} like \fig{yale}.

%Ritthoff et al. argues (and we agree) that
%the standard interface of (say) WEKA does not support the rapid generation of
%these intricate combinations. Also, according to Menzies~\cite{me00v}, while visual systems provide motivation for beginners, they fail in providing a good explanation device for many software engineering and 
%knowledge engineering problems, as many of these problems are not inherently spatial.  


%In our experience these
%visual environments are either
%overly elaborate,
%discouraging or distracting: 
%\bi
%\item
%These standard data mining toolkits may be overly elaborate. As shown throughout this paper, very simple UNIX scripting tools suffice for the specification,
%execution, and communication of experiments.
%\item Some data mining novices are discouraged by the tool complexity. These novices shy away
%from extensive modification and experimentation.
%\item Other developers may become  so enamored with the impressive software engineering
%inside these tools that they waste much time  building environments to support data mining,
%but never get around to the data mining itself.
%\ei
%A similar experience is reported by our colleagues in WVU Department of Statistics.
%In order to support teaching, they 
%hide these data mining tools inside high-level scripting environments. Their scripting environments
%shield the user from the complexities of ``R''
%by defining high-level LISP code that, internally, calls ``R''.
%While a powerful language, we find that LISP can be 
%arcane to many audiences. 

\newpage
\section{What is OURMINE?}
OURMINE is a data mining scripting envrionment. The current kit has tools written in
BASH/ GAWK/ JAVA/ PERL/ and there is no technical block to adding
other tools written in other languages.

% Other toolkits impose strict limitations of the usable languages:
%\bi
%\item
% MLC++ requires C++  
%\item
%Extensions to WEKA (Figure 3) must be written in JAVA.
%\ei
%Our preference  for  BASH~\cite{ramey94}/GAWK~\cite{awkbook} over, say, LISP is partially a matter of
%taste but we defend that selection as follows.  Once a student
%learns, for example, RAPID-I's XML configuration tricks, then those learned
%skills are highly specific to that  toolkit.  On the other
%hand, once a student learns BASH/GAWK methods for data pre-processing
%and reporting, they can apply those scripting tricks to any number
%of future UNIX-based applications.

This paper introduces OURMINE and the experiment using it as follows:
\bi
\item First, we describe the base tool and offer some samples of coding in OURMINE;
\item Next, we demonstrate the scalability of faster reduction and clustering methods compared to 
more rigorous ones using OURMINE as a testing environment
\ei

%This paper is an extension of  a prior publication~\cite{gay09}:
%\bi
%\item This paper details functionality added since that last paper was published;
%\item This paper adds a new experiment to the description of OURMINE (see \tion{tmine}).
%\ei

OURMINE was developed to help graduate students at West Virginia University document and execute their 
data mining experiments.
The toolkit 
uses UNIX shell scripting. As a result, any tool
that can be executed from a command prompt can be seemlessly combined with other tools.

For example,  \fig{clean} shows a simple bash
function used in OURMINE to clean text data before conducting any
experiments using it. Line 5 passes text from a file, performing
tokenization, removing capitals and unimportant words found in a
stop list, and then in the next line performing Porter's stemming
algorithm on the result. 

OURMINE allows connectivity between tools
written in various languages as long as there is always a command-line
API available for each tool.
For example, the modules of \fig{clean} are written using BASH,
Awk and Perl. Another example of a function utilized by OURMINE can be seen in 
Figure 6, showing an entire Awk script to perform a TF*IDF (explained below) reduction. 

\begin{figure}
{\scriptsize\begin{verbatim}
 1 clean(){
 2    local docdir=$1
 3    local out=$2
 
 4   for file in $docdir/*; do
 5      cat $file | tokes | caps | stops $Lists/stops.txt > tmp 
 6	     stems tmp >> $out 
 7	     rm tmp
 8   done
 9 }\end{verbatim}}
\caption{An OURMINE function to clean text documents and collect the results. 
$Tokes$ is a tokenizer; $caps$ sends all words to lower case;
$stops$ removes the stop workds listed in "\$Lists/stops.txt"; and
$stems$ performs Porter's stemming algorithm (removes confusing suffixes).
 }\label{fig:clean}
\end{figure}

The following sections describe OURMINE's functions and applications.

\subsection{Built-in Data and Functions}

In order to encourage more experimentation, 
the default OURMINE installation comes with numerous data sets:

\bi
\item {\em Text mining data sets:} including STEP data sets (numeric): ap203, ap214, bbc, bbcsport, law, 20 Newsgroup subsets [sb-3-2, sb-8-2, ss-3-2, sl-8-2]\footnote{\url{http://mlg.ucd.ie/datasets}}
\item {\em Discrete UCI datasets:} anneal, colic, hepatitis, kr-vs-kp, mushroom, sick, waveform-5000, audiology, credit-a, glass, hypothyroid, labor, 
pcolic, sonar, vehicle, weather, autos, credit-g, heart-c, ionosphere, letter, primary-tumor, soybean, vote,\newline weather.nominal,
breast-cancer, diabetes, heart-h, iris, lymph, segment, splice, vowel;
\item {\em  Numeric UCI datasets:} auto93, baskball, cholesterol, detroit, fruitfly, longley, pbc, quake, sleep, autoHorse, bodyfat, cleveland, 
echoMonths, gascons, lowbwt, pharynx, schlvote, strike, autoMpg, bolts, cloud, elusage, housing, mbagrade, pollution, sensory, veteran, 
autoPrice, breastTumor, cpu, fishcatch, hungarian, meta, pwLinear, servo, vineyard.
\item The defect prediction data sets from {\em the PROMISE repostitory}:  CM1, KC1, KC2, KC3, MC2, MW1, PC1
\ei

OURMINE also comes with a variety of built-in functions to perform data mining and text mining tasks. For a sample of these functions, see \fig{functions}. %For a complete list, see the appendix.
\begin{figure}
\small
\begin{description}
\item[abcd] provides analysis of experiments, such as {\em pd,pf,accuracy} and {\em precision} values;
%footnotetext[1]{
%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}$,
%$pf=\frac{c}{a+c}$,
%$prec=precision=\frac{d}{d+c}$,
%$acc=accuracy=\frac{a+d}{a+b+c+d}$,
%$f=\frac{2*pd*pf}{pd + pf}$,
%and 
%$balance=1-\sqrt{(1-pf)^2 + pd^2}/\sqrt{2}$ .}
\item[clean] clean text for further processing, removing tokens, capitalizations, stop words, etc.;
\item[docsToSparff] constructs a sparse arff file based on a directory of documents;
\item[docsToTfidfSparff] generates a sparse arff file of TF-IDF values based on a directory of documents;
\item[funs] shows a sorted list of all available functions in OURMINE;
\item[logArff] logs all numeric values in a data set ;
\item[malign] neatly aligns text into columns;
\item[nb] Runs Naive Bayes on the data given;
\item[rankViaInfoGain] ranks attributes by InfoGain values;
\item[makeTrainAndTest] splits a dataset into a test set and a training set as $train$.arff and $test$.arff, as well as $train$.lisp and $test$.lisp. 
\end{description}
\caption{A small sample of the available OURMINE functions. Built-in functions give the user something with which to start and begin running demos and experiments immediately. For a detailed list of available tools, please see the appendix.}\label{fig:functions}
\end{figure}


\begin{figure}
{\scriptsize\begin{verbatim}
function train() { #update counters for all words in the record 
  Docs++; 
  for(I=1;I<NF;I++) { 
    if( ++In[$I,Docs]==1) 
    Doc[$I]++ 
    Word[$I]++ 
    Words++ } 
} 
function tfidf(i) { #compute tfidf for one word 
  return Word[i]/Words*log(Docs/Doc[i]) 
} \end{verbatim}}
\caption{A GAWK implementation of TF-IDF.}\label{fig:tfidf}
\end{figure}

%\subsection{Adding/Modifying OURMINE Code}

%OURMINE uses an interpreted system, thus, it is a simple matter to extend or modify its functionality.
%For example, if a user wished to add a {\em myFunctions.sh} to be used in the environment

%\begin{itemize}
%\item{Create an executable {\em myFunctions.sh} containing any custom scripts}
%\item{Include this file in {\em \$HOME/opt/ ourmine/our/lib/sh/minerc.sh }}
%\end{itemize}

%Once this basic structure of OURMINE is learned, however, more advanced additions can be made such as:
%including multiple directories of BASH files, some of whose functions call code written in other files and other languages located elsewhere in the codebase. This gives a nearly limitless opportunity for customization.
\newpage
\section{Certifying our theories with OURMINE}

%OURMINE is not just a simple demonstration system for novice data miners.
%It can also be used to generate journal-level publishable results. 
%In the last three years, the authors of this paper have published six papers in leading software engineering
%journals and conferences using
%OURMINE~\cite{turhan08,gay09,me07b,me06d,me05c,me05d}.

%In order to demonstate OURMINE's use in leading edge research,
%we present here a recent text mining result from an as-yet-unpublished WVU masters thesis. 

%two experiments.
%Experiment \#1 reproduces an important recent result by Turhan et al.~\cite{turhan08}.
%Kitchenham et al. report that there is no clear consensus on the relative value of effort estimation
%models learned from either local or imported data~\cite{kitch07}. Since this matter has not be previously
%studied in the defect prediction literature, Turhan et al. conducted a series of experiments with ten data sets
%from different companies. In their {\em within-company} (WC) experiments, defect predictors were learned
%from 90\%  of the local data, then tested on the remaining 10\%. In the {\em cross-company} (CC) experiments,
%defect predictors wehre learned from nine companies then tested on the tenth. Turhan et al. found that the CC
%predictions were useless since they suffered from very high false alarm rates. However, after applying a simple
%{\em relevancy filter},
%they found that imported CC learning yielded predictors that were nearly as good as the local
%WC learning. 

%Experiment \#2 checks a recent text mining result from an as-yet-unpublished WVU masters thesis.
Matheny~\cite{matheny09} benchmarked various lightweight learning methods (TF*IDF, the GENIC stochastic clusterer)
against other, slower, more rigorous learning methods (PCA, K-means). As expected, the rigorous learning methods
ran  much slower than the stochastic methods. But, unexpectedly, Matheny found that the leightweight methods perform
nearly as well as the rigorous methods.

In a mature scientific discipline, it is standard practice to reproduce important results. 
%Both the results
The results need to be reproduced since they are important:
\bi
%\item If the Experiment \#1 results are correct, then organizations make quality predictions about their source code,
%even when they lack local historical logs.
\item If the results from the experiment are correct, then text mining methods can scale to much larget data sets.
%\item If the Experiment \#2 results are correct, then text mining methods can scale to much larger data sets.
\ei
The rest of this section describes the use of OURMINE to reproduce %Experiment \#1 and \#2.
the experiment.

 
%The first experiment, based on those conducted by Turhan et
%al.~\cite{turhan08}, as well as Gay et al.~\cite{gay09}, focuses
%on binary defect prediction. In~\cite{turhan08}, Turhan et al.
%conducted three experiments to rule in favor of cross-company (CC)
%data obtained from other sites, or within-company (WC) data gathered
%locally. The conclusions of those experiments show that CC data,
%when applied using {\em relevancy filtering}, as explained below,
%can lead to defect predictors almost as effective as WC data. Thus,
%as stated by Gay et al., ``...while local data is the preferred
%option, it is feasible to use imported data provided that it is
%selected by a relevancy filter.''
%
%The second experiment was a small-scale reproduction of that conducted
%by a graduate computer science student at West Virginia University
%to be used in a Master's thesis. The purpose of the experiment is
%to show that faster heuristic means of clustering and dimensionality
%reduction yield results comparable to slower, more rigorous methods
%when examining these methods' runtimes, cluster similarities, as
%well as cluster purities.
%
%In the following sections we describe the experiments and show some of the scripts used to conduct them. Finally we analyze the results.
%
%\subsection{Experiment I}

%OURMINE was used to reproduce Turhan et al.'s experiment - with a Naive Bayes 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}. 

%To begin, the data in this study were the same as used by Gay et al.; 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, which is used as the training set for the cross-company (CC) data.

%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$.

%We chose to use a Naive Bayes 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 Naive Bayes has been shown to perform better on PROMISE defect data sets than other learners~\cite{lessmann08}.   

%\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  blabln
%51  done
%52  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}

%\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 loses compared to another. The method that lost the least 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 filtuer & 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 Naive Bayes.}
%\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.


\subsection{The Experiment}\label{sec:tmine}

As stated above, the purpose of this experiment conducted for this paper is to verify if lightweight data mining
methods perform slower or 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 intially 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, we will focus on two methods:

\be
\item
PCA, or Principal Components Analysis, is a reduction method that
treats every instance in a dataset as a point in N-dimensional
space. PCA looks for new dimensions that better fit these points.
PCA involves the calculation of the eigenvalue decomposition 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 syntethesized that is more relevant to the data distribution.
\begin{figure}
\begin{center}
\includegraphics[width=2.25in]{pca}
\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, we 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}
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{Trade-Offs}

As shown in Figures 8 and 9, as methods get faster (top to bottom), they find less and less
structure in the data.

On the other hand, the slower more thorough methods are much, much slower. The 
following chart shows that:
\bi
\item The run-time of our more rigorous reduction method (PCA)
runs orders of magnitude slower than the other methods. 
\item  Our least-thorough method runs in nearly constant time, even if
we increase the number of words.  However, this method has the benefit 
transparency to users.  That is, the features are English words and
not synthesized mathematical representations.
\ei

\begin{figure}
\begin{center}
\includegraphics{ap203_pca}
\end{center}
\caption{PCA ($D*T^2$)}\label{fig:ap203_pca}
\end{figure}

\begin{figure}
\begin{center}
\includegraphics{ap203_tfidf}
\end{center}
\caption{TF*IDF ($t*N$)}\label{fig:ap203_tfidf}
\end{figure}


\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 computationaly 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}


Figure 10 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 oppurtunity 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 Figure 10 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 Figure 11, whose overall structure is very similar to Figure 10.

\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 specific documents. 

 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}  

\newpage
\section{Results and Conclusions}



The resulting sum of cluster similarity values represents the overall similarities of a clustering solution. Figure 12 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. Thus, the conclusions from this experiment shows that fast heuristic methods are sufficient for large data sets due to their scalability.


We have used OURMINE to reproduce and check an important result.
From the experiment, we concluded that:
\begin{itemize}
\item{When examining cluster inter/intra similarities resulting from each clustering/reduction solution, we found that faster heuristic methods can outperform more rigorous ones when observing decreases in runtimes.}
\item{This means that faster solutions are suitable on large datasets due to $scalability$.}
\end{itemize}
\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{Similarity values normalized according to the combination of most rigorous reducer and clusterer.} 
\label{fig:sims}
\end{figure}

\newpage
\section{Looking at STEP and Beyond}

In theory, there is nothing stopping STEP/EXPRESS from
recording and storing
all aspects of a project: 
\bi
\item
  STEP/EXPRESS is
as expressive as other technical document standards (e.g. UML) and
offers a generic method for storing part-of and is-a
information, constraints, types, and the rules associated with a
technical document. However,
in practice, the potential of STEP/EXPRESS is often not realized.
\ei

We list below some limits to the practice of STEP.
While these limits might change in the future (e.g. if
all the following issues were fixed and all organizations switch to using highly
structured technical documentation), the historical record would still be starved
for large numbers of examples.

{\bf Incomplete meta-knowledge}
Much work has focused on writing
EXPRESS schemas. Numerous such {\em application protocols} (AP) have been defined
including 
AP-203 (for geometry)
and AP-213 (for numerical control) amongst others.

While much effort went into creating these APs, very few have been stress-tested
in the field. That is, the majority of these APs have 
been {\em written} more than they have
been {\em read} (exceptions:  the above-mentioned AP-203 and AP-213 are frequently used and reused in 
$21^{st}$ century CAD/CAM manufacturing processes),
~\\

{\bf Incomplete tool support}  Perhaps because of the relative immaturity of the APs, current
CAD/CAM tools offer limited support for the STEP APs. Many
tools support geometry (AP-203), but the
support for the other  APs listed above  is, to say the lesat, very minimal.
~\\

{\bf  Incomplete design rationale support} 
From a cognitive perspective, STEP/EXPRESS does not support the entire design cycle.
Rather, it only supports the last stages of recording and transferring the final
design (but not the interim
steps along the way). 
~\\

{\bf Heterogeneity}
STEP/EXPRESS documents
are stored {\em along side} a much larger set of supporting documents in multiple formats:
\bi
\item
A recent study\footnote{\url{http://www.b-eye-network.com/view/2098}} concluded that
     80 percent of business is conducted on unstructured information.
Also,     85 percent of all data stored is held in an unstructured format
(e.g.  the unstructured text descriptions of issues found in PITS).
  Further,    Unstructured data doubles every three months.
\item
So if we only focus on STEP, we are exploring a {\bf small fraction}
of the problem. 
\ei
If we can understand large heterogeneous collections
that include
STEP/EXPRESS knowledge and numerous other products
in a wide
variety of formats,
it would be possible to reason and learn from a very wide range of
data. 

\newpage
\bibliography{refs}

%-- BURAK EXP HERE 
%\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 filtuer & 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}


\end{document}

