\documentclass[a4paper]{article}
\usepackage{listings}
\usepackage[utf8]{inputenc}
\usepackage[brazil]{babel}
\usepackage{graphicx}
\usepackage[colorlinks, urlcolor=blue]{hyperref}

\renewcommand{\familydefault}{\sfdefault}
\title{Relatório de trabalho prático \\ Métodos Estatísticos \\ Geração de dendrograma}
\author{João Paulo Pizani Flor \\ Mauricio Oliveira Haensch}
\date{\today}


\begin{document}
\maketitle
\thispagestyle{empty}
\pagebreak

%-------------------------------------------------------------------------------------
\section{Introdução}
    \paragraph{}
    Para o módulo de métodos estatísticos da disciplina, o primeiro trabalho prático tem como objetivo implementar a geração de um dendrogama com base num conjunto de dados, além de utilizar o dendrograma gerado para separar os padrões de entrada num número arbitrário de classes. A descrição do trabalho pode ser vista a seguir:

    \paragraph{}
    Implementar o Método de Unificação ou Agrupamento em Árvore (dendrograma). O sistema deve ser capaz de ler um conjunto qualquer de dados em formato texto, por exemplo separado por \textit{tabs}. Deve possuir interface gráfica que apresente o dendrograma gerado. Bole um “analisador de dendrograma” que encontre o local ótimo de corte, dados dois limites: \textit{maxClass} e \textit{minClass}. Para testes tome um conjunto de quatro \textit{sets} de dados:

    \begin{itemize}
	\item (2) Os dados da flor do Gênero Iris e dos carros disponíveis na página;
	\item (1) Os dados de câncer cerebral (gliomas): http://www.inf.ufsc.br/~patrec/glioma-daumas-duport.xls
	\item (1) Outro conjunto qualquer (por exemplo, veja os ”Links Úteis”)
    \end{itemize}



%-------------------------------------------------------------------------------------
\pagebreak
\section{Ferramentas utilizadas}
    \paragraph{}
    A linguagem utilizada para implementação do programa era de livre escolha dos alunos, assim como outras ferramentas que pudessem ser utilizadas para representação gráfica dos padrões, por exemplo. As ferramentas escolhidas para a implementação do trabalho foram:

    \begin{description}
	\item[Linguagem de programação - Python:] Escolhida por ser uma linguagem já bem conhecida pela equipe, que está sendo utilizada para todos os trabalhos práticos até então. Conta com boas bibliotecas e documentação, além de agilizar o desenvolvimento. 
	\item[Interface gráfica - PyQt:] \textit{Binding} do framework gráfico Qt para a linguagem Python, escolhida por já ser conhecida pelos integrantes e também é o framework gráfico sendo utilizado nos demais trabalhos da disciplina.
	\item[Pydot:] \textit{Binding} para a linguagem Python do software de visualização de grafos GraphViz. A representação gráfica do dendrograma gerado é feita através dessa ferramenta.
    \end{description}

    \paragraph{}
    O trabalho foi desenvolvido no ambiente Linux/Ubuntu e para executá-lo são necessários alguns pacotes\footnote{os nomes dos pacotes citados são específicos para a distribuição Ubuntu, para outras distribuições devem ser procurados os pacotes correspondentes.} para a interface gráfica:

    \begin{itemize}
	\item pyqt4-dev-tools
	\item libqtgui4
	\item libqtcore4
	\item python-pydot
    \end{itemize}

%-------------------------------------------------------------------------------------        
\pagebreak
\section{Alguns resultados}
    \paragraph{}
    A interface para este trabalho ficou simples, dado o número pequeno de funcionalidade exigidas. É possível carregar um conjunto de dados separados por vírgulas (.csv) para que seja analisado, gerar o dendrograma, que é exibido em uma janela separada, e encontrar classes para os dados analisados com base no dendrograma gerado e no número de classes desejada (passado por parâmetros como um intervalo). O resultado da classificação das entradas é apresentado em forma de texto.

    \subsection{Leitura de dados de entrada}
    \paragraph{}
    Os dados de entrada a serem carregados devem seguir o padrão a seguir, com um caso por linha, com os valores dos atributos podendo ser inteiros ou ponto flutuante:

    \color{blue}
    \begin{verbatim}
    atributo1,atributo2,atributo3,atributo4
    atributo1,atributo2,atributo3,atributo4
    atributo1,atributo2,atributo3,atributo4
    atributo1,atributo2,atributo3,atributo4
    \end{verbatim}
    \color{black}

    \subsection{Geração de dendrograma}
    \paragraph{}
     Para demonstrar o resultado de nossa implementação utilizaremos um caso de uso simples. Na imagem abaixo é exibido o dendrograma gerado com um subconjunto dos casos da flor de gênero Iris. A árvore foi gerada com o algoritmo de distância simples (menor distância) e a representação gráfica foi feita com a biblioteca \textit{pydot}.

 %  	\begin{figure}[h!]
 	    \begin{center}
 		\includegraphics[width=0.7\textwidth,keepaspectratio]{imgs/dendrograma.png}
 	    \end{center}
	    \textit{Um dendrograma gerado para um subconjunto pequeno de casos da flor de gênero Iris.}
%  	    \label{fig:dendrograma}
%  	\end{figure}

    \paragraph{}
    Os nodos folha são nomeados seguindo o padrão \textit{"p" + número} (como \textit{p0}, \textit{p1},
    \textit{p2}), e os nodos que unem as folhas da árvore foram nomeados apenas com números em ordem
    crescente, indicando a ordem em que foram feitas as junções. Por exemplo, conforme a figura demonstrada, a
    primeira junção feita (nodo "0") uniu as folhas p0 e p4, indicando que os casos de entrada representados
    por esses nodos eram os mais próximos segundo a métrica utilizada, distância euclidiana. Um dendrograma
    mais complexo está anexo ao relatório, baseado no arquivo inteiro das flores de gênero Iris (150 casos). 

    \subsection{Agrupamento em classes}
    \paragraph{}
    A partir do dendrograma gerado é possível que o usuário escolha o número mínimo e máximo de classes a serem encontradas pelo algoritmo (que podem eventualmente ter o mesmo valor para que seja encontrado um número específico de classes). A saída gerada para a aplicação do algoritmo de análise do dendrograma gerado pelo caso anterior, com o subconjunto dos casos da flor Iris, pode ser visto a seguir. Para este caso, foram utilizados como número mínimo de classes a serem encontradas 4, e o máximo 7.

    \color{blue}
    \begin{verbatim}
    1.788854382,1.90065778087,2.39791576166,2.5,0
    -0.894427191,0.22360679775,-0.417028828114,1.0,1
    -0.894427191,-0.782623792125,0.521286035143,-0.5,2
    0.111803398875,-1.11803398875,-0.417028828114,-0.5,2
    -0.559016994375,-0.4472135955,-1.35534369137,-0.5,2
    -1.56524758425,-1.45344418537,-0.417028828114,-0.5,2
    0.782623792125,0.559016994375,-0.417028828114,-0.5,3
    0.4472135955,0.894427191,-0.417028828114,-0.5,3
    0.782623792125,0.22360679775,0.521286035143,-0.5.3
    \end{verbatim}
    \color{black}

    \paragraph{}
    Conforme o exemplo acima, na saída gerada após o agrupamento dos vetores os atributos iniciais correspondem aos valores estandardizados dos vetores de entrada, enquanto o último valor separado por vírgula corresponde à classe designada àquela entrada específica. 


%-------------------------------------------------------------------------------------
\pagebreak
\section{Referências}

  \begin{itemize}
    \item Python - \url{http://www.python.org/}
    \item Qt - \url{http://doc.qt.nokia.com/}
    \item pyQt - \url{http://www.riverbankcomputing.co.uk/software/pyqt/intro}
    \item Pydot - \url{http://code.google.com/p/pydot/}
  \end{itemize}

\end{document}
