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

\renewcommand{\familydefault}{\sfdefault}
\title{Relatório de trabalho prático \\ Métodos Estatísticos \\ Algoritmo de K-Médias}
\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 segundo trabalho prático tem como objetivo implementar o algoritmo K-Médias, que agrupa um conjunto de dados em \textit{k} \textit{clusters}, utilizando o teste de Fisher para avaliar o resultado obtido. A descrição do trabalho pode ser vista a seguir:

    \paragraph{}
    Implemente o método das k-Médias de maneira que o programa gerado seja capaz de ler o mesmo conjunto de dados que foi sugerido para a técnica da classificação em árvore. A escolha de k pode ser tanto um valor entrado manualmente como pode ser um valor dentro de uma faixa que você dá; se você usar uma faixa, faça o método iterar por todos os valores de k dentro da faixa, guardando em separado cada resultado. Implemente o teste de Fisher usando a seu critério o cálculo da distribuição F ou então uma tabela de valores críticos de F para validar o resultado. 

%-------------------------------------------------------------------------------------
\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[NumPy:] Biblioteca\footnote{O pacote para essa biblioteca no ambiente Linux/Ubuntu é \textit{python-numpy}.} da linguagem Python utilizada para computação científica, com diversas estruturas e funções otimizadas. Para este trabalho, utilizamos algumas de suas funções de álgebra linear, para fazer operações com matrizes (transposição) e cálculo de média e desvio padrão de um conjunto de dados. 
    \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
    \end{itemize}

%-------------------------------------------------------------------------------------        
\pagebreak
\section{Alguns resultados}
    \paragraph{}
    Para este trabalho, é possível carregar um conjunto de dados separados por vírgulas (.csv) para que seja utilizado para o algoritmo de K-Médias, com \textit{k} sendo um valor passado pelo usuário. Os dados de entrada a serem carregados devem seguir o padrão demonstrado abaixo, 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}

    \paragraph{}
    O algoritmo de K-Médias possui um princípio de funcionamento simples, seguindo os passos seguintes:

    \begin{enumerate}
      \item São encontrados \textbf{k} pontos aleatórios que irão definir as classes na primeira tentativa de classificação;
      \item Os demais pontos são classificados em uma das categorias de acordo com alguma métrica de distância;
      \item Após todos os pontos terem sido classificados, são calculados novos pontos médios para representar cada classe;
      \item Até que não haja nenhuma mudança dos pontos médios, repita os dois passos anteriores.
    \end{enumerate}

    \paragraph{}
    Após aplicarmos o algoritmo de K-Médias, resultando no agrupamento dos padrões de entrada em \textbf{k} classes, devemos aplicar um teste de fisher, avaliando o quão boa foi a divisão encontrada pelo algoritmo. Com essa abordagem, é possível detectar o melhor número de \textit{clusters} ao operar numa faixa de classes desejadas pelo usuário.

    \paragraph{}
    Para efeito de testes, geramos um conjunto de dados de duas dimensões para aplicarmos os algoritmos implementados e poder ser feita a visualização dos resultados de forma gráfica. Na figura \ref{fig:nao_classificados} estão os dados sem a aplicação do algoritmo de K-Médias. Aplicando o algoritmo para encontrar duas classes, o resultado pode ser visto na figura \ref{fig:classificados_2classes}.
    
    \begin{figure}[h!]
	\begin{center}
	    \includegraphics[width=0.7\textwidth]{imgs/nao_classificados.png}
	\end{center}
	\caption{Dados carregados, antes da classificação.}
	\label{fig:nao_classificados}
    \end{figure}

    \begin{figure}[h!]
	\begin{center}
	    \includegraphics[width=0.7\textwidth]{imgs/classificados_2classes.png}
	\end{center}
	\caption{Dados agrupados em 2 classes.}
	\label{fig:classificados_2classes}
    \end{figure}

    %Tentar fazer o teste de Fisher funcionar corretamente e mostrar o exemplo para [3,7] classes
    \paragraph{}
    O teste de Fisher foi calculado em separado para cada uma das coordenadas, e então consideramos o pior
    caso entre as coordenadas, ou seja, o máximo dos valores obtidos.

    \paragraph{}
    Esse cálculo foi repetido para cada um dos n (número de classes) na faixa definida pelo usuário, e o
    n com menor valor do teste de Fisher é aceito como o melhor particionamento do conjunto de dados.

    \paragraph{}
    Por exemplo, na figura \ref{fig:fisher3a7}, o usuário requisita um particionamento do conjunto de
    dados entre 3 a 7 classes, e o melhor particionamento encontrado foi em 3 classes distintas, cada
    uma representada por uma cor na figura.

    \begin{figure}[h!]
        \begin{center}
            \includegraphics[width=0.7\textwidth]{imgs/classificados_3a7_classes.png}
        \end{center}
        \caption{Dados agrupados em 3 classes.}
        \label{fig:fisher3a7}
    \end{figure}



%-------------------------------------------------------------------------------------
\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 Numpy - \url{http://numpy.scipy.org/}
  \end{itemize}

\end{document}
