<commit_before>\typeout{Trabalho final de Aprendizado de Máquina}

\documentclass{article}

\usepackage[brazil]{babel}
%\usepackage{cite}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{ijcai11}

\usepackage{times}
\usepackage[alf]{abntex2cite}
\usepackage{indentfirst}

\title{Trabalho Final - Aprendizado de Máquina e Mineração de Dados}
\author{
<NAME> \\
{\bf <NAME>}  \\
{\bf <NAME>} \\
{\bf <NAME>} \\
DC -Departamento de Computação \\
UFSCar - Universidade Federal de São Carlos \\
}

\begin{document}

\maketitle

\begin{abstract}
No contexto de aprendizado de máquina, dois problemas são comumente discutidos.
O primeiro é a análise de séries temporais, ou seja, dados condicionados a uma variável tempo.
O outro é o ajuste de hiperparâmetros dos algoritmos de aprendizado para melhor se adequarem aos dados e ao enunciado do problema estudado.
Com o objetivo de analisar o comportamento de algoritmos clássicos em relação a estes dois conceitos,
neste trabalho iremos estudar o comportamento dos algoritmos de árvore de decisão, {\it Naïve-Bayes},
regressão linear e de regressão logística para a classificação de séries temporais;
também estudaremos os algoritmos de agrupamento {\it K-Means} e {\it Expectation Maximization} (EM)
e suas sensibilidades aos hiperparâmetros de cada um dos algoritmos.
Para tanto, primeiro será feita uma análise teórica sobre o funcionamento de cada um desses algoritmos,
seus usos mais comuns, e o viés indutivo relacionado a eles.
Percebemos que os algoritmos de classificação são relativamente bem comportados a dados em séries temporais,
mas que um modelo mais específico para isso, incluindo possivelmente conhecimento de domínio, têm uma acurácia superior.
Ainda é possível notar que os algoritmos de agrupamento são muito sensíveis ao número de grupos que pretende se encontrar,
principalmente quando esse valor é menor que o número real de grupos nos dados,
mas pouco sensíveis aos chutes iniciais de centroides ou médias das distribuições.
\end{abstract}

\section{Introdução}

O aprendizado de máquina tem sido bastante discutido em tempos recentes.
Uma definição comum de aprendizado de máquina é a de que uma máquina aprende uma determinada tarefa $T$,
utilizando alguma métrica de performance $P$, se o sistema melhora sua performance $P$ na tarefa $T$ conforme
uma determina experiência $E$ adquirida. \cite{mitchell06}.
Em um contexto mais prático, dizemos que dada uma função desconhecida em um domínio qualquer, $f : A \to B$,
queremos uma aproximação da função $f$ a partir de exemplos de mapeamentos entre $A$ e $B$,
esses exemplos sendo os dados do nosso aprendizado.
No mundo real, utilizamos o aprendizado de máquina em tarefas como classificação de texto,
detecção de objetos em imagens, sistemas de recomendação automática,
detecção de fraudes em cartão de créditos, mecanismos de pesquisa, entre outros.

Podemos classificar as tarefas de aprendizado de máquina em três grupos,
o aprendizado supervisionado, não-supervisionado, e semissupervisionado.
No aprendizado supervisionado, a variável de interesse (o contra-domínio da função $f$ descrita anteriormente)
é conhecida, chamada de classe. Por exemplo, a classe pode ser um valor binário ``spam/não-spam''
para um conjunto de e-mails. Para que o aprendizado seja supervisionado, todos os exemplos utilizados
no treinamento do algoritmo deve estar marcados com a classe.
Caso somente uma parte dos exemplos esteja marcado com a classe, chamamos o aprendizado de semissupervisionado.
Por fim, no aprendizado não-supervisionado, a classe é uma variável latente, ou seja, não conhecida.

Quando comparamos os diferentes algoritmos existentes para uma determinada tarefa,
devemos levar em consideração vários fatores sobre o próprio problema e sobre os dados existentes,
para que possamos tomar uma decisão sobre quão apropriado é o algoritmo a esta tarefa.
Dentre as características que devem ser estudadas,
podemos citar o {\it overfitting}, ou super-adequação aos dados,
onde o aprendiz se prende demais aos exemplos existentes e é incapaz de generalizar o conhecimento adquirido.
Outra característica é o viés indutivo, que é a estratégia utilizada para selecionar a
hipótese mais provável dentro do espaço de hipóteses possíveis para o algoritmo.

\section{Fundamentos teóricos}

Nessa seção, serão discutidos alguns aspectos teóricos dos algoritmos que serão examinados nesse trabalho.
Os algoritmos utilizados podem ser divididos em duas categorias: a de aprendizado supervisionado e de aprendizado não supervisionado.
Dentre os algoritmos utilizados, árvore de decisão, {\it Naive Bayes} e regressão são algoritmos de aprendizado supervisionado e os algoritmos de agrupamento (k-Means e {\it Expectation Maximization}) são de aprendizado não supervisionado.

Alguns dos aspectos que serão analisados nesse trabalho para cada algoritmo são séries temporais, o viés indutivo do algoritmo e sua sensibilidade a hiperparâmetros.

O processo de aprendizado de máquina geralmente envolve a extração de informações mais gerais acerca de um evento com base em um conjunto de instâncias conhecidas desse evento.
Em lógica, o processo de se obter conhecimentos gerais a partir de exemplos específicos é denominado indução.
Como, em geral, um conjunto de instâncias não é suficiente para generalizar todos os casos possíveis,
deve-se haver um conjunto de pressuposições acerca do problema que permitam a generalização.
Em aprendizado de máquina, esse conjunto de pressuposições é chamado de viés indutivo do algoritmo.

Há vários tipos de viés indutivo para os algoritmos de aprendizado de máquina.
Exemplos são o viés de busca, ou de preferência e o viés de linguagem, ou restrição.
O viés indutivo de cada algoritmo apresentado será discutido nessa seção.

Na terminologia de aprendizado de máquina, hiperparâmetros são características do algoritmo de aprendizado de máquina,
não inferidos do conjunto de dados de treinamento, que influenciam diretamente no desempenho do algoritmo de aprendizado de máquina.
Quanto mais sensível a hiperparâmetros for um algoritmo, mais seu desempenho será afetado pelos valores desses hiperparâmetros.

É comum que se faça uma otimização desses hiperparâmetros para cada problema que se deseja resolver,
já que a configuração ótima geralmente se altera de um problema para o outro.

\subsection{Algoritmos supervisionados}

Em algoritmos de dados supervisionado, é dado um conjunto de dados de treinamento rotulados para o algoritmo.
As variáveis não rótulo são denominadas atributos e a variável rótulo é comumente chamada de variável alvo, ou variável resposta.
O objetivo dos algoritmos de aprendizado supervisionado é determinar a relação existente entre os atributos e a variável alvo,
de forma a predizer o valor da variável alvo para um dado não rotulado.
A função que relaciona os atributos e a variável alvo é denominada função hipótese.

Os elementos do conjunto de dados de treinamento são também chamados de instâncias e são comumente representados por vetores de atributos.
É comum denominar-se a tarefa de aprendizado supervisionado de classificação, quando a variável alvo é discreta, e de regressão, quando a variável alvo é contínua.

\subsubsection{Árvore de Decisão}

O algoritmo de árvore de decisão é um algoritmo simbólico de classificação, em que a variável alvo geralmente possui duas classes.
Nesse algoritmo, cada valor de atributo ou da variável alvo é visto como uma expressão lógica, de forma que cada instância é vista como uma conjunção de expressões lógicas.

A saída do algoritmo é uma árvore de decisão, que pode ser vista como um conjunto de regras que determinam associam um valor da saída para cada conjunção de entradas.
Essa árvore é obtida a partir do conjunto de dados de treinamento, verificando-se as frequências dos valores dos atributos com relação aos valores da variável alvo.

Os algoritmos de árvore de decisão vistos durante a disciplina foram o ID3 e o C4.5.
Ambos os algoritmos utilizam métricas com base na entropia para a determinação da ordem da colocação dos atributos na árvore.
No caso do ID3, utiliza-se o ganho de informação, enquanto no caso do C4.5, utiliza-se a razão de informação.

A entropia pode ser vista como uma medida da quantidade de informação sobre a classe que pode ser obtida a partir de um conjunto de dados.
Seja $S$ um conjunto de amostras, $p^+$ a proporção de exemplos positivos de um evento nessa amostra e $p^-$ a proporção de eventos negativos dessa amostra.
A entropia desse conjunto é definida por:

\begin{equation}
\mathrm{Entropia}(S) = -(p^+ \log_2(p^+)) - (p^- \log_2(p^-))
\end{equation}

O valor da entropia varia entre 0 e 1 e é menor quanto menos igualmente distribuído for o conjunto de dados com relação à classe.
O ganho de informação e a razão de informação são métricas que buscam indicar o atributo que fornece mais informação sobre a classe,
ou seja, o atributo que, em média, quando se dividir a árvore em ramos, mais diminuirá a entropia do conjunto.
A razão de informação leva também em conta atributos com muitos valores, dividindo-se o ganho pela informação intrínseca({\it split information}) de cada atributo.

Seja $S$ um conjunto de dados, $A$ um atributo, $V(A)$ o conjunto de valores possíveis desse atributo e $S_{Av}$ o subconjunto de $S$ em que atributo $A$ possui valor $v \in V(A)$.
Então, o ganho de informação e a razão de informação do atributo $A$, com relação ao conjunto $S$, são definidos por:

\small
\begin{equation}
\mathrm{Ganho}(S,A)=\mathrm{Entropia}(S)-\sum_{v \in V(A)}\frac{\left|S_{Av}\right|}{\left|S\right|} \mathrm{Entropia}(S_{Av})
\end{equation}

\begin{equation}
\mathrm{Razao}(S,A)=\frac{\mathrm{Ganho}(S,A)}{\mathrm{SplitInformation}(S,A)}
\end{equation}

\begin{equation}
{\tiny \mathrm{SplitInformation}(S,A) = -\sum_{v\in V(A)} \frac{\left|S_{Av}\right|}{\left|S\right|} \log_2\left(\frac{\left|S_{Av}\right|}{\left|S\right|}\right)}
\end{equation}
\normalsize

Tanto o algoritmo ID3 como o algoritmo C4.5 utilizam uma estratégia de subida de encosta para a determinação dos atributos dos nós,
em que, uma vez determinado o atributo de um nó, o algoritmo continua para suas subárvores, sem retornar para esse nó.

O algoritmo C4.5 também possui um mecanismo de poda, que busca eliminar ramos da árvore que fornecem menos informações para a classificação das instâncias.

Há diversas maneiras de realizar a poda em árvores de decisão,
uma delas consiste em separar um conjunto de dados de teste,
representar a árvore de decisão como um conjunto de regras do tipo se então,
em seguida, para cada antecedente de cada regra, comparar o desempenho da árvore no conjunto de teste com o desempenho dela,
retirando-se esse antecedente. Caso o desempenho da árvore melhore, esse antecedente é retirado da regra.
Isso diminui o tamanho dos ramos da árvore de decisão, tornando-a menos suscetível ao {\it overfitting}.

Tanto no algoritmo ID3 quanto no C4.5,
verifica-se uma tendência de escolha de árvores mais curtas.
Isso se à escolha dos atributos dos nós, que é feita com base nos nós que fornecem mais informação sobre a classe.
Os algoritmos seguem a estratégia de subida de encosta,
já que, após escolhido um nó, o algoritmo segue para suas subárvores, não retornando mais a esse nó.

Enquanto essa estratégia não necessariamente retorna a menor árvore possível, a árvore encontrada é geralmente uma das menores possíveis. Dessa forma, diz-se que os algoritmos ID3 e C4.5 possuem um viés de busca, ou preferência, já que dão preferência a árvores mais curtas, ou seja, hipóteses mais simples. 

A preferência por hipóteses mais curtas (comumente chamada na literatura de navalha de Occam) permite que o algoritmo generalize melhor para dados não vistos,
já que hipóteses mais longas tendem a ser mais específicas para o conjunto de dados.

Um hiperparâmetro de importância para a árvore de decisão é a utilização ou não da poda e qual forma de poda é utilizada;
outro hiperparâmetro importante quando lidando com atributos contínuos ou com um domínio muito grande é a discretização feita para esses atributos,
já que ela determina a ramificação da árvore.

\subsubsection{{\b \it Naive Bayes}}

O algoritmo de {\it Naive Bayes} é um algoritmo probabilístico de classificação.
Ele utiliza o teorema de Bayes e a pressuposição de independência dos atributos, dada a classe,
para estimar a probabilidade de cada classe a partir do conjunto de treinamento,
dos atributos do dado observado e de algum conhecimento a priori sobre a distribuição da classe.

O {\it Naive Bayes} é geralmente é considerado um algoritmo {\it lazy} por não ser necessária a construção de um modelo,
ainda que um modelo probabilístico seja gerado.
Em contrapartida, o algoritmo de árvore de decisão mencionado acima é considerado um algoritmo {\it eager}, pois gera um modelo, sendo a árvore o modelo gerado.

Dessa forma, o algoritmo de {\it Naive Bayes} deve ser generalizado toda vez que um dado de entrada é recebido.
Isso faz com que o tempo de treinamento seja reduzido, porém gasta-se mais tempo na classificação.

Para se determinar a probabilidade da classe, dados os atributos observados (posteriori),
sabendo-se, de antemão, a distribuição da classe (priori), utiliza-se o teorema de Bayes.
Seja $h \in H$ uma hipótese possível em um espaço de hipóteses $H$,
$D \in \mathcal{D}$ os atributos do dado observado, pertencentes ao espaço de atributos $\mathcal{D}$,
então, a probabilidade da hipótese condicionada pelos atributos é dada por:

\begin{equation}
P(h|D) = \frac{P(D|h) P(h)}{P(D)}
\end{equation}

Considerando-se a hipótese como sendo a classe $c_j \in C$
atribuída ao dado observado, pertencente ao conjunto de classes $C$, e $D$ um vetor de atributos $D = (a_1,a_2,\cdots,a_n)$, tem-se:

\begin{equation}
P(c_j|a_1,a_2,\cdots,a_n) = \frac{P(a_1,a_2,\cdots,a_n|c_j) P(c_j)}{P(a_1,a_2,\cdots,a_n)}
\end{equation}

Dessa forma, a hipótese de máximo a posteriori pode ser determinada obtendo-se o valor de $c_j$ que maximize a expressão acima.
Como o denominador é constante com relação a $c_j$, encontra-se:

\begin {equation}
c_{j_{MAP}} = \operatorname*{arg\,max}_{c_j \in C} P(a_1,a_2,\cdots,a_n|c_j) P(c_j)
\end {equation}

O termo $P(a_1,a_2,\cdots,a_n|c_j)$ pode ser expandido da seguinte forma:

\small
\begin {multline}
P(a_1,a_2,\cdots,a_n|c_j) = \\
= P(a_1|a_2,a_3,\cdots,a_n,c_j) P(a_2|a_3,\cdots,a_n,c_j) \cdots P(a_n|c_j)
\end{multline}
\normalsize

O número de operações necessárias para determinar a probabilidade acima ou a quantidade de memória necessária para armazenar essas probabilidades de antemão cresce muito rapidamente em relação à quantidade de variáveis,
o que torna a determinação do máximo a posteriori inviável computacionalmente.

O {\it Naive Bayes} resolve esse problema assumindo independência condicional entre os atributos,
dada a classe, ou seja, a probabilidade da conjunção de $n$ atributos,
dada a classe é igual ao produto das probabilidades de cada atributo, dada a classe. Dessa forma:

\begin{multline}
P(x_k|x_{k+1},\cdots,x_n|c_j) = \frac{P(x_k,\cdots,x_n,c_j)}{P(x_{k+1},\cdots,x_n,c_j)} \\
= \frac{P(x_k,\cdots,x_n|c_j) P(c_j)}{P(x_{k+1},\cdots,x_n|c_j) P(c_j)} = \frac{P(x_k,\cdots,x_n|c_j)}{P(x_{k+1},\cdots,x_n|c_j)} \\
= P(x_k|c_j)
\end{multline}

Assim, segue que:

\small
\begin{multline}
P(a_1|a_2,a_3,\cdots,a_n,c_j) P(a_2|a_3,\cdots,a_n,c_j) \cdots P(a_n|c_j) \\
= P(a_1|c_j) P(a_2|c_j) \cdots P(a_n|c_j) = \prod_{i=1}^n P(a_i,c_j)
\end{multline}
\normalsize

Dessa forma, o classificador {\it Naive Bayes}, $c_{j_{NB}}$ é dado por:

\begin{equation}
c_{j_{NB}} = \operatorname*{arg\,max}_{c_j \in C} \prod_{i=1}^n P(a_i|c_j) \, P(c_j)
\end{equation}

\begin{equation}
P(a_i|c_j) = \frac{\mathrm{frequencia}(a_i,c_j)}{\mathrm{frequencia}(c_j)}
\end{equation}

Apesar da pressuposição de independência do {\it Naive Bayes}
(que pode ser considerada um viés indutivo do algoritmo) aparentar ser bastante restritiva,
o algoritmo ainda apresenta bom desempenho em diversas classes de problemas.
A independência condicional dada a classe permite a determinação mais rápida da posteriori.

Pela expressão do classificador Naive Bayes, observa-se que,
se um atributo não foi observado para alguma classe, sua probabilidade será igual a zero.
Isso torna a resposta do algoritmo bastante dependente dos dados,
já que, caso um atributo não seja observado no conjunto, desconsidera-se todos os outros.

Para se evitar isso, é comum que se utilize algum tipo de suavização, por exemplo,
adicionando-se uma observação em cada atributo de cada classe,
o que equivale a somar $\frac{1}{|C|}$ no numerador e 1 no denominador na determinação das probabilidades condicionais.

\subsubsection{Regressão}

Regressão é uma técnica da Estatística cujo objetivo consiste em inferir a relação entre uma variável dependente com outras variáveis independentes.Em outras palavras, um conjunto de variáveis explicam outra variável, permitindo a descrição de um conjunto de dados.

Em Aprendizado de Máquina, Regressão consiste em um problema canônico, ajudando a predizer um valor real de uma dada instância a partir de um conjunto de instâncias de treinamento. As tarefas de Regressão integram o chamado Aprendizado Supervisionado, sendo as técnicas divididas em dois grandes grupos: regressão linear e regressão não-linear. A regressão linear tem uma função linear de relação entre a variável resposta e as variáveis explicatórias, enquanto que a regressão não-linear tem uma função não-linear.

Uma possível área de aplicação de Regressão e de Aprendizado de Máquina ocorre em aplicações envolvendo séries temporais.Uma série temporal pode ser entendida basicamente como uma coleção de observações feitas sequencialmente ao longo de um intervalo de tempo. Assim, entender a relação entre observações vizinhas no tempo é um problema crucial.Aplicações destes conceitos vão desde áreas de finanças, economia, medicina, física, entre outras.

\subsection{Algoritmos não-Supervisionados}

Algoritmos não-supervisionados são utilizados em aplicações de aprendizado não-supervisionado, onde o conjunto de instâncias de treinamento não possui rótulos associados como em tarefas supervisionadas. Desta forma, estes algoritmos devem aprender padrões e relações entre um conjunto de instâncias não rotuladas.

Como já dito anteriormente, duas tarefas canônicas em aprendizado não-supervisionado são agrupamento e regras de associação. Redes neurais também podem se enquadrar neste tipo de aprendizado. Em tarefas de agrupamento dezenas de algoritmos encontram-se disponíveis, variando desde a estratégia usada para agrupar até em relação às características do conjunto de dados. Destacam-se algoritmos baseados em densidade, como o DBSCAN, em conectividade, como o K-Means e em distribuição como o Expectation-Maximization.Para tarefas relacionadas à regras de associação, os algoritmos mais populares são o Apriori, o Eclat e o FP-growth.  

\subsubsection{{\b \it k-Means}}

\subsubsection{{\b \it Expectation Maximization}}

\section{Experimentos e Resultados}

\subsection{Algoritmos Supervisionados}

\subsubsection{Árvore de Decisão}

\subsubsection{{\b \it Naive Bayes}}

\subsubsection{Regressão}

\subsection{Algoritmos não Supervisionados}

\subsubsection{{\b \it k-Means}}

\subsubsection{{\b \it Expectation Maximization}}

\section{Conclusões}

%% The file named.bst is a bibliography style file for BibTeX 0.99c
\bibliography{main}

\end{document}

<commit_msg>Corrigindo iremos estudar -> estudaremos<commit_after>\typeout{Trabalho final de Aprendizado de Máquina}

\documentclass{article}

\usepackage[brazil]{babel}
%\usepackage{cite}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{ijcai11}

\usepackage{times}
\usepackage[alf]{abntex2cite}
\usepackage{indentfirst}

\title{Trabalho Final - Aprendizado de Máquina e Mineração de Dados}
\author{
<NAME> \\
{\bf <NAME>}  \\
{\bf <NAME>} \\
{\bf <NAME>} \\
DC -Departamento de Computação \\
UFSCar - Universidade Federal de São Carlos \\
}

\begin{document}

\maketitle

\begin{abstract}
No contexto de aprendizado de máquina, dois problemas são comumente discutidos.
O primeiro é a análise de séries temporais, ou seja, dados condicionados a uma variável tempo.
O outro é o ajuste de hiperparâmetros dos algoritmos de aprendizado para melhor se adequarem aos dados e ao enunciado do problema estudado.
Com o objetivo de analisar o comportamento de algoritmos clássicos em relação a estes dois conceitos,
neste trabalho estudaremos o comportamento dos algoritmos de árvore de decisão, {\it Naïve-Bayes},
regressão linear e de regressão logística para a classificação de séries temporais;
também estudaremos os algoritmos de agrupamento {\it K-Means} e {\it Expectation Maximization} (EM)
e suas sensibilidades aos hiperparâmetros de cada um dos algoritmos.
Para tanto, primeiro será feita uma análise teórica sobre o funcionamento de cada um desses algoritmos,
seus usos mais comuns, e o viés indutivo relacionado a eles.
Percebemos que os algoritmos de classificação são relativamente bem comportados a dados em séries temporais,
mas que um modelo mais específico para isso, incluindo possivelmente conhecimento de domínio, têm uma acurácia superior.
Ainda é possível notar que os algoritmos de agrupamento são muito sensíveis ao número de grupos que pretende se encontrar,
principalmente quando esse valor é menor que o número real de grupos nos dados,
mas pouco sensíveis aos chutes iniciais de centroides ou médias das distribuições.
\end{abstract}

\section{Introdução}

O aprendizado de máquina tem sido bastante discutido em tempos recentes.
Uma definição comum de aprendizado de máquina é a de que uma máquina aprende uma determinada tarefa $T$,
utilizando alguma métrica de performance $P$, se o sistema melhora sua performance $P$ na tarefa $T$ conforme
uma determina experiência $E$ adquirida. \cite{mitchell06}.
Em um contexto mais prático, dizemos que dada uma função desconhecida em um domínio qualquer, $f : A \to B$,
queremos uma aproximação da função $f$ a partir de exemplos de mapeamentos entre $A$ e $B$,
esses exemplos sendo os dados do nosso aprendizado.
No mundo real, utilizamos o aprendizado de máquina em tarefas como classificação de texto,
detecção de objetos em imagens, sistemas de recomendação automática,
detecção de fraudes em cartão de créditos, mecanismos de pesquisa, entre outros.

Podemos classificar as tarefas de aprendizado de máquina em três grupos,
o aprendizado supervisionado, não-supervisionado, e semissupervisionado.
No aprendizado supervisionado, a variável de interesse (o contra-domínio da função $f$ descrita anteriormente)
é conhecida, chamada de classe. Por exemplo, a classe pode ser um valor binário ``spam/não-spam''
para um conjunto de e-mails. Para que o aprendizado seja supervisionado, todos os exemplos utilizados
no treinamento do algoritmo deve estar marcados com a classe.
Caso somente uma parte dos exemplos esteja marcado com a classe, chamamos o aprendizado de semissupervisionado.
Por fim, no aprendizado não-supervisionado, a classe é uma variável latente, ou seja, não conhecida.

Quando comparamos os diferentes algoritmos existentes para uma determinada tarefa,
devemos levar em consideração vários fatores sobre o próprio problema e sobre os dados existentes,
para que possamos tomar uma decisão sobre quão apropriado é o algoritmo a esta tarefa.
Dentre as características que devem ser estudadas,
podemos citar o {\it overfitting}, ou super-adequação aos dados,
onde o aprendiz se prende demais aos exemplos existentes e é incapaz de generalizar o conhecimento adquirido.
Outra característica é o viés indutivo, que é a estratégia utilizada para selecionar a
hipótese mais provável dentro do espaço de hipóteses possíveis para o algoritmo.

\section{Fundamentos teóricos}

Nessa seção, serão discutidos alguns aspectos teóricos dos algoritmos que serão examinados nesse trabalho.
Os algoritmos utilizados podem ser divididos em duas categorias: a de aprendizado supervisionado e de aprendizado não supervisionado.
Dentre os algoritmos utilizados, árvore de decisão, {\it Naive Bayes} e regressão são algoritmos de aprendizado supervisionado e os algoritmos de agrupamento (k-Means e {\it Expectation Maximization}) são de aprendizado não supervisionado.

Alguns dos aspectos que serão analisados nesse trabalho para cada algoritmo são séries temporais, o viés indutivo do algoritmo e sua sensibilidade a hiperparâmetros.

O processo de aprendizado de máquina geralmente envolve a extração de informações mais gerais acerca de um evento com base em um conjunto de instâncias conhecidas desse evento.
Em lógica, o processo de se obter conhecimentos gerais a partir de exemplos específicos é denominado indução.
Como, em geral, um conjunto de instâncias não é suficiente para generalizar todos os casos possíveis,
deve-se haver um conjunto de pressuposições acerca do problema que permitam a generalização.
Em aprendizado de máquina, esse conjunto de pressuposições é chamado de viés indutivo do algoritmo.

Há vários tipos de viés indutivo para os algoritmos de aprendizado de máquina.
Exemplos são o viés de busca, ou de preferência e o viés de linguagem, ou restrição.
O viés indutivo de cada algoritmo apresentado será discutido nessa seção.

Na terminologia de aprendizado de máquina, hiperparâmetros são características do algoritmo de aprendizado de máquina,
não inferidos do conjunto de dados de treinamento, que influenciam diretamente no desempenho do algoritmo de aprendizado de máquina.
Quanto mais sensível a hiperparâmetros for um algoritmo, mais seu desempenho será afetado pelos valores desses hiperparâmetros.

É comum que se faça uma otimização desses hiperparâmetros para cada problema que se deseja resolver,
já que a configuração ótima geralmente se altera de um problema para o outro.

\subsection{Algoritmos supervisionados}

Em algoritmos de dados supervisionado, é dado um conjunto de dados de treinamento rotulados para o algoritmo.
As variáveis não rótulo são denominadas atributos e a variável rótulo é comumente chamada de variável alvo, ou variável resposta.
O objetivo dos algoritmos de aprendizado supervisionado é determinar a relação existente entre os atributos e a variável alvo,
de forma a predizer o valor da variável alvo para um dado não rotulado.
A função que relaciona os atributos e a variável alvo é denominada função hipótese.

Os elementos do conjunto de dados de treinamento são também chamados de instâncias e são comumente representados por vetores de atributos.
É comum denominar-se a tarefa de aprendizado supervisionado de classificação, quando a variável alvo é discreta, e de regressão, quando a variável alvo é contínua.

\subsubsection{Árvore de Decisão}

O algoritmo de árvore de decisão é um algoritmo simbólico de classificação, em que a variável alvo geralmente possui duas classes.
Nesse algoritmo, cada valor de atributo ou da variável alvo é visto como uma expressão lógica, de forma que cada instância é vista como uma conjunção de expressões lógicas.

A saída do algoritmo é uma árvore de decisão, que pode ser vista como um conjunto de regras que determinam associam um valor da saída para cada conjunção de entradas.
Essa árvore é obtida a partir do conjunto de dados de treinamento, verificando-se as frequências dos valores dos atributos com relação aos valores da variável alvo.

Os algoritmos de árvore de decisão vistos durante a disciplina foram o ID3 e o C4.5.
Ambos os algoritmos utilizam métricas com base na entropia para a determinação da ordem da colocação dos atributos na árvore.
No caso do ID3, utiliza-se o ganho de informação, enquanto no caso do C4.5, utiliza-se a razão de informação.

A entropia pode ser vista como uma medida da quantidade de informação sobre a classe que pode ser obtida a partir de um conjunto de dados.
Seja $S$ um conjunto de amostras, $p^+$ a proporção de exemplos positivos de um evento nessa amostra e $p^-$ a proporção de eventos negativos dessa amostra.
A entropia desse conjunto é definida por:

\begin{equation}
\mathrm{Entropia}(S) = -(p^+ \log_2(p^+)) - (p^- \log_2(p^-))
\end{equation}

O valor da entropia varia entre 0 e 1 e é menor quanto menos igualmente distribuído for o conjunto de dados com relação à classe.
O ganho de informação e a razão de informação são métricas que buscam indicar o atributo que fornece mais informação sobre a classe,
ou seja, o atributo que, em média, quando se dividir a árvore em ramos, mais diminuirá a entropia do conjunto.
A razão de informação leva também em conta atributos com muitos valores, dividindo-se o ganho pela informação intrínseca({\it split information}) de cada atributo.

Seja $S$ um conjunto de dados, $A$ um atributo, $V(A)$ o conjunto de valores possíveis desse atributo e $S_{Av}$ o subconjunto de $S$ em que atributo $A$ possui valor $v \in V(A)$.
Então, o ganho de informação e a razão de informação do atributo $A$, com relação ao conjunto $S$, são definidos por:

\small
\begin{equation}
\mathrm{Ganho}(S,A)=\mathrm{Entropia}(S)-\sum_{v \in V(A)}\frac{\left|S_{Av}\right|}{\left|S\right|} \mathrm{Entropia}(S_{Av})
\end{equation}

\begin{equation}
\mathrm{Razao}(S,A)=\frac{\mathrm{Ganho}(S,A)}{\mathrm{SplitInformation}(S,A)}
\end{equation}

\begin{equation}
{\tiny \mathrm{SplitInformation}(S,A) = -\sum_{v\in V(A)} \frac{\left|S_{Av}\right|}{\left|S\right|} \log_2\left(\frac{\left|S_{Av}\right|}{\left|S\right|}\right)}
\end{equation}
\normalsize

Tanto o algoritmo ID3 como o algoritmo C4.5 utilizam uma estratégia de subida de encosta para a determinação dos atributos dos nós,
em que, uma vez determinado o atributo de um nó, o algoritmo continua para suas subárvores, sem retornar para esse nó.

O algoritmo C4.5 também possui um mecanismo de poda, que busca eliminar ramos da árvore que fornecem menos informações para a classificação das instâncias.

Há diversas maneiras de realizar a poda em árvores de decisão,
uma delas consiste em separar um conjunto de dados de teste,
representar a árvore de decisão como um conjunto de regras do tipo se então,
em seguida, para cada antecedente de cada regra, comparar o desempenho da árvore no conjunto de teste com o desempenho dela,
retirando-se esse antecedente. Caso o desempenho da árvore melhore, esse antecedente é retirado da regra.
Isso diminui o tamanho dos ramos da árvore de decisão, tornando-a menos suscetível ao {\it overfitting}.

Tanto no algoritmo ID3 quanto no C4.5,
verifica-se uma tendência de escolha de árvores mais curtas.
Isso se à escolha dos atributos dos nós, que é feita com base nos nós que fornecem mais informação sobre a classe.
Os algoritmos seguem a estratégia de subida de encosta,
já que, após escolhido um nó, o algoritmo segue para suas subárvores, não retornando mais a esse nó.

Enquanto essa estratégia não necessariamente retorna a menor árvore possível, a árvore encontrada é geralmente uma das menores possíveis. Dessa forma, diz-se que os algoritmos ID3 e C4.5 possuem um viés de busca, ou preferência, já que dão preferência a árvores mais curtas, ou seja, hipóteses mais simples. 

A preferência por hipóteses mais curtas (comumente chamada na literatura de navalha de Occam) permite que o algoritmo generalize melhor para dados não vistos,
já que hipóteses mais longas tendem a ser mais específicas para o conjunto de dados.

Um hiperparâmetro de importância para a árvore de decisão é a utilização ou não da poda e qual forma de poda é utilizada;
outro hiperparâmetro importante quando lidando com atributos contínuos ou com um domínio muito grande é a discretização feita para esses atributos,
já que ela determina a ramificação da árvore.

\subsubsection{{\b \it Naive Bayes}}

O algoritmo de {\it Naive Bayes} é um algoritmo probabilístico de classificação.
Ele utiliza o teorema de Bayes e a pressuposição de independência dos atributos, dada a classe,
para estimar a probabilidade de cada classe a partir do conjunto de treinamento,
dos atributos do dado observado e de algum conhecimento a priori sobre a distribuição da classe.

O {\it Naive Bayes} é geralmente é considerado um algoritmo {\it lazy} por não ser necessária a construção de um modelo,
ainda que um modelo probabilístico seja gerado.
Em contrapartida, o algoritmo de árvore de decisão mencionado acima é considerado um algoritmo {\it eager}, pois gera um modelo, sendo a árvore o modelo gerado.

Dessa forma, o algoritmo de {\it Naive Bayes} deve ser generalizado toda vez que um dado de entrada é recebido.
Isso faz com que o tempo de treinamento seja reduzido, porém gasta-se mais tempo na classificação.

Para se determinar a probabilidade da classe, dados os atributos observados (posteriori),
sabendo-se, de antemão, a distribuição da classe (priori), utiliza-se o teorema de Bayes.
Seja $h \in H$ uma hipótese possível em um espaço de hipóteses $H$,
$D \in \mathcal{D}$ os atributos do dado observado, pertencentes ao espaço de atributos $\mathcal{D}$,
então, a probabilidade da hipótese condicionada pelos atributos é dada por:

\begin{equation}
P(h|D) = \frac{P(D|h) P(h)}{P(D)}
\end{equation}

Considerando-se a hipótese como sendo a classe $c_j \in C$
atribuída ao dado observado, pertencente ao conjunto de classes $C$, e $D$ um vetor de atributos $D = (a_1,a_2,\cdots,a_n)$, tem-se:

\begin{equation}
P(c_j|a_1,a_2,\cdots,a_n) = \frac{P(a_1,a_2,\cdots,a_n|c_j) P(c_j)}{P(a_1,a_2,\cdots,a_n)}
\end{equation}

Dessa forma, a hipótese de máximo a posteriori pode ser determinada obtendo-se o valor de $c_j$ que maximize a expressão acima.
Como o denominador é constante com relação a $c_j$, encontra-se:

\begin {equation}
c_{j_{MAP}} = \operatorname*{arg\,max}_{c_j \in C} P(a_1,a_2,\cdots,a_n|c_j) P(c_j)
\end {equation}

O termo $P(a_1,a_2,\cdots,a_n|c_j)$ pode ser expandido da seguinte forma:

\small
\begin {multline}
P(a_1,a_2,\cdots,a_n|c_j) = \\
= P(a_1|a_2,a_3,\cdots,a_n,c_j) P(a_2|a_3,\cdots,a_n,c_j) \cdots P(a_n|c_j)
\end{multline}
\normalsize

O número de operações necessárias para determinar a probabilidade acima ou a quantidade de memória necessária para armazenar essas probabilidades de antemão cresce muito rapidamente em relação à quantidade de variáveis,
o que torna a determinação do máximo a posteriori inviável computacionalmente.

O {\it Naive Bayes} resolve esse problema assumindo independência condicional entre os atributos,
dada a classe, ou seja, a probabilidade da conjunção de $n$ atributos,
dada a classe é igual ao produto das probabilidades de cada atributo, dada a classe. Dessa forma:

\begin{multline}
P(x_k|x_{k+1},\cdots,x_n|c_j) = \frac{P(x_k,\cdots,x_n,c_j)}{P(x_{k+1},\cdots,x_n,c_j)} \\
= \frac{P(x_k,\cdots,x_n|c_j) P(c_j)}{P(x_{k+1},\cdots,x_n|c_j) P(c_j)} = \frac{P(x_k,\cdots,x_n|c_j)}{P(x_{k+1},\cdots,x_n|c_j)} \\
= P(x_k|c_j)
\end{multline}

Assim, segue que:

\small
\begin{multline}
P(a_1|a_2,a_3,\cdots,a_n,c_j) P(a_2|a_3,\cdots,a_n,c_j) \cdots P(a_n|c_j) \\
= P(a_1|c_j) P(a_2|c_j) \cdots P(a_n|c_j) = \prod_{i=1}^n P(a_i,c_j)
\end{multline}
\normalsize

Dessa forma, o classificador {\it Naive Bayes}, $c_{j_{NB}}$ é dado por:

\begin{equation}
c_{j_{NB}} = \operatorname*{arg\,max}_{c_j \in C} \prod_{i=1}^n P(a_i|c_j) \, P(c_j)
\end{equation}

\begin{equation}
P(a_i|c_j) = \frac{\mathrm{frequencia}(a_i,c_j)}{\mathrm{frequencia}(c_j)}
\end{equation}

Apesar da pressuposição de independência do {\it Naive Bayes}
(que pode ser considerada um viés indutivo do algoritmo) aparentar ser bastante restritiva,
o algoritmo ainda apresenta bom desempenho em diversas classes de problemas.
A independência condicional dada a classe permite a determinação mais rápida da posteriori.

Pela expressão do classificador Naive Bayes, observa-se que,
se um atributo não foi observado para alguma classe, sua probabilidade será igual a zero.
Isso torna a resposta do algoritmo bastante dependente dos dados,
já que, caso um atributo não seja observado no conjunto, desconsidera-se todos os outros.

Para se evitar isso, é comum que se utilize algum tipo de suavização, por exemplo,
adicionando-se uma observação em cada atributo de cada classe,
o que equivale a somar $\frac{1}{|C|}$ no numerador e 1 no denominador na determinação das probabilidades condicionais.

\subsubsection{Regressão}

Regressão é uma técnica da Estatística cujo objetivo consiste em inferir a relação entre uma variável dependente com outras variáveis independentes.Em outras palavras, um conjunto de variáveis explicam outra variável, permitindo a descrição de um conjunto de dados.

Em Aprendizado de Máquina, Regressão consiste em um problema canônico, ajudando a predizer um valor real de uma dada instância a partir de um conjunto de instâncias de treinamento. As tarefas de Regressão integram o chamado Aprendizado Supervisionado, sendo as técnicas divididas em dois grandes grupos: regressão linear e regressão não-linear. A regressão linear tem uma função linear de relação entre a variável resposta e as variáveis explicatórias, enquanto que a regressão não-linear tem uma função não-linear.

Uma possível área de aplicação de Regressão e de Aprendizado de Máquina ocorre em aplicações envolvendo séries temporais.Uma série temporal pode ser entendida basicamente como uma coleção de observações feitas sequencialmente ao longo de um intervalo de tempo. Assim, entender a relação entre observações vizinhas no tempo é um problema crucial.Aplicações destes conceitos vão desde áreas de finanças, economia, medicina, física, entre outras.

\subsection{Algoritmos não-Supervisionados}

Algoritmos não-supervisionados são utilizados em aplicações de aprendizado não-supervisionado, onde o conjunto de instâncias de treinamento não possui rótulos associados como em tarefas supervisionadas. Desta forma, estes algoritmos devem aprender padrões e relações entre um conjunto de instâncias não rotuladas.

Como já dito anteriormente, duas tarefas canônicas em aprendizado não-supervisionado são agrupamento e regras de associação. Redes neurais também podem se enquadrar neste tipo de aprendizado. Em tarefas de agrupamento dezenas de algoritmos encontram-se disponíveis, variando desde a estratégia usada para agrupar até em relação às características do conjunto de dados. Destacam-se algoritmos baseados em densidade, como o DBSCAN, em conectividade, como o K-Means e em distribuição como o Expectation-Maximization.Para tarefas relacionadas à regras de associação, os algoritmos mais populares são o Apriori, o Eclat e o FP-growth.  

\subsubsection{{\b \it k-Means}}

\subsubsection{{\b \it Expectation Maximization}}

\section{Experimentos e Resultados}

\subsection{Algoritmos Supervisionados}

\subsubsection{Árvore de Decisão}

\subsubsection{{\b \it Naive Bayes}}

\subsubsection{Regressão}

\subsection{Algoritmos não Supervisionados}

\subsubsection{{\b \it k-Means}}

\subsubsection{{\b \it Expectation Maximization}}

\section{Conclusões}

%% The file named.bst is a bibliography style file for BibTeX 0.99c
\bibliography{main}

\end{document}


{'fraction_non_alphanumeric': 0.06141965838191674, 'fraction_numerical': 0.0033752684872660325, 'mean_word_length': 5.111736208782622, 'pattern_counts': {'":': 0, '<': 11, '<?xml version=': 0, '>': 12, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '754747', 'n_tokens_mistral': 13754, 'n_tokens_neox': 13512, 'n_words': 5438}