\documentclass[a4paper]{article}

%% Unicode support
\usepackage[utf8x]{inputenc}
\usepackage{ucs}
\usepackage{autofe}

\usepackage{fullpage}
\usepackage{times}
\usepackage[T1]{fontenc}
\usepackage{a4}
\usepackage{epstopdf}
\usepackage{graphicx}
\usepackage{mathtools}
\usepackage{amssymb}
\usepackage{hyperref}
\usepackage{color}


%% Code
\usepackage{inconsolata}
\usepackage{minted}
\usepackage{fancyvrb}
\usemintedstyle{default}
\newminted{r}{gobble=4,linenos,mathescape,fontfamily=tt,fontsize=\footnotesize,xleftmargin=\parindent}



%% Metainformation
%% PDF stuff
\usepackage{datetime}
\usepackage{ifpdf}
\ifpdf
\pdfinfo{
    /Author (Joao Paulo Pizani Flor, Tomas Kadlec)
    /Title (Implementation of a classification tree-growing algorithm in R)
    /Keywords (Data Mining, Classification Trees, R)
    /CreationDate (D:\pdfdate)
}
\fi

\title{Implementation of a classification tree-growing algorithm in R}

\date{\today}

\author
{
    João Paulo Pizani Flor, Tomaš Kadlec \\
    Department of Information and Computing Sciences, \\
    Utrecht University - The Netherlands \\
    e-mail: j.p.pizaniflor@students.uu.nl
}



%% The document itself
\begin{document}
    \maketitle

    \section{Introduction}
    \label{sec:intro}
        This report describes the solution to the first practical assignment of the master course
        "Data Mining" at Utrecht University, taught in the 1st period of the academic year
        2013/2014.


    \section{Organization of the distributed package}
    \label{sec:organization}
        The handed-in solution is organized as follows:
        \begin{description}
            \item[R workspace] The R workspace image containing both the \emph{code} and the
                \emph{datasets} used for analysis is under the package root with name
                \texttt{``RData''}

            \item[R Source] The source code of the functions implemented is located in the package
                root with the name \texttt{``classificationTree.R''}. This file is just a
                \emph{concatenation} of the files \texttt{``treeBuild.R''} and
                \texttt{``treeClassify.R''}. In a running R session, the code can be loaded by
                issuing the command \texttt{source(``classificationTree.R'')}.

            \item[Datasets] The datasets available for usage are available under the
                \texttt{``datasets''} subdirectory, in CSV format.
        \end{description}


    \section{Requirements on the data to be analyzed}
    \label{sec:requirements}
        According to what was described in the assignment specification, some assumptions are made
        on the inputs to the algorithm. If some of the following requirements is NOT met, then the
        program will display \textbf{undefined behaviour}. On the other hand, if the input data
        meets the following requirements, then the algorithm complies with the specification (to the
        extent of our knowledge)

        \begin{itemize}
            \item The dataset to be analyzed (excluding the classes) should be stored in R as a
                \textbf{dataframe}, i.e, not as a matrix or vector.

            \item The \textbf{class} parameter is a \textbf{vector of integer} values, in which each
                element corresponds to the class of an observation in the dataset.

            \item Both parameters \texttt{nmin} and \texttt{minleaf} to the \texttt{tree.grow}
                function should be \textbf{lesser than or equal} to the number of observations, i.e.
                \[
                    (N_{\text{min}} \le \text{Ob})  \wedge  (\text{MINLeaf} \le \text{Ob})
                \]
        \end{itemize}

        It's important to notice that in our implementation, the class attribute \textbf{does not}
        need to be binary. The calculation of impurity using the gini index is working in the
        general case of (integer) categorical values.


    \section{Training and classification process}
    \label{sec:process}
        We tested our algorithms using two datasets: the ``Pima Indians Diabetes Database'',
        provided in the Data Mining course webpage, and the ``Adult Breast Cancer Database'',
        obtained from the online UCI Machine Learning repository\cite{Bache+Lichman:2013}.

        The ``Pima Indians Diabetes'' dataset complied with the requirements of our algorithm, as exposed in section
        \ref{sec:requirements}. The ``Adult Breast Cancer Database'' has 16 incompletely recorded cases, i.e. some 
        of the attributes are undefined. We have therefore removed these records to meet the input requirements. 
        Additionaly, the Breast Cancer dataset has a class attribute with a
        non-standard encoding: instead of using the values 0 and 1, they use 2 and 4. This was not a
        problem, though, because our impurity calculation uses the general case of the gini index.

        It should be noted that the impurity function to be used can be passed \textbf{as a parameter}
        to the \texttt{tree.grow} function.  We have implemented the \textbf{generalized} gini index
        (\texttt{impurity.gini} which is used by default. However, as of R 3.0 the built-in
        \texttt{table} function is notably slow and can use as much as 95\% of cpu time when the
        tree is being constructed. For binary clas attributes the considerably faster version
        \texttt{impurity.gini.bin} can be used.

        \subsection{Testing the accuracy of the built classification trees}
        \label{subsec:accuracytest}
            Having chosen the datasets on which to work, we proceeded to growing classification
            trees with a subset of each dataset, and then using the built tree to classify the
            remaining data points. Our experimental setting was as follows:
            \begin{description}
                \item[Performance measure] We use the proportion of correct guesses of a class value
                    (probability of a correct guess) as measure of the performance of the
                    classification tree. This value, of course, is expressed as a function of the
                    arguments \texttt{nmin} and \texttt{minleaf}

                \item[Size of training set] For each of the two datasets used, we established a
                    partition of 70\% of the data points used for training and 30\% for
                    classification.

                \item[Choice of the training set] The number of data points to be used for training
                    is sampled randomly from the dataset.

                \item[Number of tests performed] As a random choice is being performed, we chose to
                    run 10 rounds of this ``performance test'' over each dataset, giving more
                    confidence in the results obtained.
            \end{description}

            As the performance of the classification is a function of two arguments (\texttt{nmin}
            and \texttt{minleaf}), the plot for this function is 3-dimensional. One example of
            performance plot (the one for the ``PIMA'' dataset) can be seen in
            Figure \ref{fig:plot-pima}. The performance for the other dataset (the ``Adult Breast
            Cancer'' dataset), can be visualized in Figure \ref{fig:plot-cancer}.

            \begin{figure}
                \begin{center}
                    \includegraphics[width=1.0\textwidth]{plot-pima.pdf}
                \end{center}
                \label{fig:plot-pima}
                \caption{Performance plot for the PIMA dataset}
            \end{figure}

            \begin{figure}
                \begin{center}
                    \includegraphics[width=1.0\textwidth]{plot-cancer.pdf}
                \end{center}
                \label{fig:plot-cancer}
                \caption{Performance plot for the cancer dataset}
            \end{figure}


    \bibliographystyle{plain}
    \bibliography{references}

\end{document}
