\documentclass[12pt]{report}
\topmargin=0in
\headheight=0in
\headsep=0in
\oddsidemargin=0in
\evensidemargin=0in
\textwidth=6.5in
\textheight=9in

\usepackage{setspace}
\usepackage{subfig}
\usepackage{graphicx}
\usepackage{algorithmic,cite,footmisc,multirow,url,amsmath}
\usepackage{color}
\usepackage{pslatex}
\usepackage{fullpage}
\usepackage{alltt}
\usepackage{rotating}
\usepackage{float}
\usepackage{pifont}
\usepackage{wasysym}

\newcommand{\captionfonts}{\sffamily\scriptsize}

\makeatletter  % Allow the use of @ in command names
\long\def\@makecaption#1#2{%
  \vskip\abovecaptionskip
  \sbox\@tempboxa{{\captionfonts #1: #2}}%
  \ifdim \wd\@tempboxa >\hsize
    {\captionfonts #1: #2\par}
  \else
    \hbox to\hsize{\hfil\box\@tempboxa\hfil}%
  \fi
  \vskip\belowcaptionskip}
\makeatother   % Cancel the effect of \makeatletter

\newcommand{\be}{\begin{enumerate}}
\newcommand{\ee}{\end{enumerate}}
\newcommand{\bi}{\begin{itemize}}
\newcommand{\ei}{\end{itemize}}
\newcommand{\eq}[1]{Equation~\ref{eq:#1}}
\newcommand{\fig}[1]{Figure~\ref{fig:#1}}

\definecolor{grey}{rgb}{0.2,0.2,0.2}


\singlespacing

\begin{document}
\thispagestyle{empty}

\title{\large Trade-offs of Heuristic Vs. Rigorous Algorithms in Text Mining}
\author{\normalsize Andrew Matheny \\ \\
\normalsize Thesis submitted to the \\
\normalsize College of Engineering and Mineral Resources \\
\normalsize at West Virginia University \\
\normalsize in partial fulfillment of the requirements \\
\normalsize for the degree of \\ \\
\normalsize Master of Science \\
\normalsize in \\
\normalsize Computer Science \\ \\
\normalsize Tim Menzies, Ph.D., Chair \\
\normalsize Tim McGraw, Ph.D. \\
\normalsize Andrian  Marcus, Ph.D. \\ \\
\normalsize Lane Department of Computer Science and Electrical Engineering \\ \\
\normalsize Morgantown, West Virginia \\
\normalsize 2009 \\ \\
\normalsize Keywords: clustering, dimension reduction, kmeans, genic, canopy, pca, fastmap, tfidf, \\ 
\normalsize text mining, 20newsgroups, bbc \\ \\
\normalsize Copyright \copyright~2009 Andrew Matheny }


\date{}
\maketitle


\begin{abstract}
\begin{center}
Trade-offs of Heuristic Vs. Rigorous Algorithms in Text Mining \vspace{1.5ex} \\
Andrew Matheny
\end{center}
This research assesses the cost of using heuristic methods in the field of text
mining.  
Previous research has shown many of the formal
non-heuristic algorithms to be NP-hard with positive results only in small 
domains.  Given the massive scale when dealing with unstructured textual data,
these algorithms prove to be impossible with large datasets with many dimensions.
  Many heuristic approximations have been proposed that drastically improve run-times, 
but give a result of less accuracy than the rigorous methods.  

Throughout the research, we
evaluate the trade-offs of heuristic methods to their more computationally complex 
alternatives.  We focus on algorithms for document clustering and dimensionality reduction,
and provide results detailing the run-times and cluster validity of each clusterer and reducer
 on their own, in addition to the run-times and validity scores of each clusterer and reducer combined.
  Our findings indicate that the cost of
these approximations vary when dealing with supervised vs unsupervised datasets, and provide recommended
parameters and combinations for optimization.
\end{abstract}

\doublespacing

\chapter*{Dedication}
\renewcommand{\thepage}{\roman{page}}
\setcounter{page}{3}

\begin{center}
\textit{To My Family, My Friends, and My Dog} \\
\end{center}

\chapter*{Acknowledgments}
People that I acknowledge
\singlespacing

\tableofcontents
\listoffigures
\listoftables
\pagebreak

\doublespacing

\chapter{Introduction}
\setcounter{page}{1}
\pagenumbering{arabic}
\label{introduction}
\input{introduction}

\chapter{Background and Related Work}
\label{background}
\input{background}

\chapter{Tools}
\label{tools}
\input{tools}


\chapter{Laboratory Studies}
\label{studies}
\input{studies}

\chapter{Conclusions}
\label{conclusions}
\input{conclusions}

\appendix

\singlespacing


\bibliography{myrefs}
\bibliographystyle{plain}

\pagebreak
\thispagestyle{empty}

\end{document}
