44.avaliacao.tex

% ------------------------------------------------------------------------------
\section{Metodologia de Avaliação}\label{sec:avaliacao}

% \nota{reestrutura 2:
%   A - cenario
%   B - metodologia (como, o que vai implementar [kafka, python, flink], como avaliar)
%   C - métricas (escalabilidade, qualidade)
%   D - resultados preliminares (python/kafka, flink)
% }

A avaliação da proposta aqui apresentada é feita por meio de métricas da
literatura, divididas em duas partes: métricas de qualidade de classificação
e métricas de escalabilidade.

As métricas de qualidade de classificação escolhidas devem ser adequadas para
avaliar detecção de novidades em fluxos de dados, felizmente o tratamento necessário é
estabelecido por \citeonline{Faria2013evaluation} e expandido por
\citeonline{DaSilva2018,DaSilva2018thesis,Costa2019,Costa2019thesis}.
Além do tratamento estabelecido, as métricas adaptadas não são calculadas
somente para o conjunto completo capturado no final do fluxo, e sim para cada
exemplo $\mathbf{X}$ classificado.
Portanto, as métricas têm como índice o contador de exemplos $x$, informando a
posição do exemplo em relação ao fluxo, ou seja, as métricas são de todos os
exemplos até a instância $x$.

\begin{definition}
  O problema de Detecção de Novidades em fluxo de dados pode ser modelado como
  uma função $f$ onde, dado o um exemplo $\mathbf{X}$ de um fluxo de dados $S$,
  pertencente a uma classe real $c \in \mathbf{C}$, é associado a um rótulo $l
  \in \mathbf{L}$ podendo ser uma classe conhecida $c' \in \mathbf{C}'$, ``desconhecido''
  ou um rótulo novidade $y \in \mathbf{Y}$:
  \begin{align}
    f  &: \mathbf{X} \mapsto l  \quad \mathbf{X} \in S , \quad l \in \mathbf{L}
      &&\text{Função de classificação} \label{eq:classifieFN} \\
    \mathbf{C} &= \{ c_1, c_2, \cdots, c_m \}
      &&\text{Classes do problema} \label{eq:classes} \\
    \mathbf{C}' &\in \mathbf{C}
      &&\text{Classes no treinamento} \label{eq:knownClasses} \\
    \mathbf{Y} &= \{ y_1, y_2, \cdots, y_k \}
      &&\text{Rótulos Novidade} \label{eq:novelies} \\
    \mathbf{L} &= \{ l_1, l_2, \cdots, l_n \} = \mathbf{C}' \cup \{ \text{``desconhecido''} \} \cup \mathbf{Y}
      &&\text{Rótulos Produzidos}\label{eq:labels} 
  \end{align}
\end{definition}

O tratamento estabelecido das métricas de qualidade para mineração de fluxos de dados define
que as métricas sejam extraídas de uma matriz de erro de classificação
multi-classe $\mathbf{E}_x$ na \refequ{matrix}, adaptada para detecção de
novidade.

\begin{definition}
  Uma matriz de confusão $\mathbf{E}$ para a instância $x$, de dimensão $m \times
  n$ para $m$ classes e $n$ rótulos, é preenchida com o número de instâncias da
  classe $c_i$ classificados com o rótulo $l_j$.
  \begin{align}
    \mathbf{E}_x = (e_{ij})\in \mathbb{N} ^{m\times n}
    &= \begin{pmatrix}
      e_{1,1} & e_{1,2} & \cdots & e_{1,n} \\
      e_{2,1} & e_{2,2} & \cdots & e_{2,n} \\
      \vdots  & \vdots  & \ddots & \vdots  \\
      e_{m,1} & e_{m,2} & \cdots & e_{m,n} 
    \end{pmatrix}  \label{eq:matrix}
  \end{align}
\end{definition}

Note que a soma de todos os elementos da matriz de confusão é igual a $x$, ou
seja, a contagem de todos exemplos.

Um dos possíveis rótulos $l_j \in \mathbf{L}$ é o rótulo ``desconhecido'', que
indica um erro de classificação diferente dos demais e é tratado separadamente.
A taxa de desconhecidos $\mathit{UnkR}$ na \refequ{unkr} é uma das métricas escolhidas
pois trata deste tipo específico de erro \cite{Faria2013evaluation}.

\begin{definition}
  A taxa de desconhecidos $\mathit{UnkR}_x$ (\refequ{unkr}) para um instante $x$ é definida como
  a média da taxa de desconhecidos de cada classe \cite{Faria2013evaluation}.
  % \begin{align}
  %   \mathit{UnkR}_x & = \frac{1}{m} \sum_{i=1}^{m} \mathit{UnkR}_{x, i}
  % \end{align}
  A taxa de desconhecidos de cada classe $c_i$ (\refequ{unkrXI}) é definida como o elemento
  $e_{ij} \in \mathbf{E}_x$ onde $j$ é a coluna do rótulo ``desconhecido''
  na matriz de rótulos $\mathbf{L}$ dividido pelo número de exemplos da classe.
  \begin{align}
    \mathit{UnkR}_{x, i}
      &= \frac{e_{i j} : l_j = \text{``desconhecido''}}{\sum_{j=1}^{n} e_{i j}}
      \label{eq:unkrXI}\\
    \mathit{UnkR}_x & = \frac{1}{m} \sum_{i=1}^{m} \mathit{UnkR}_{x, i}
    \label{eq:unkr}
  \end{align}
\end{definition}

Para todos os rótulos $l_j$ diferentes de ``desconhecido'', uma classe $c_i$ é
associada se o rótulo $l_j$ é procedente do modelo inicial, ou seja $l_j = c_i :
c_i \in \mathbf{C}'$ ou, em último caso, o rótulo $l_j$ é associado à classe com
o maior número de exemplos com o rótulo $l_j$, ou seja $e_{ij} = max\{ e_{aj} :
a \in [0, m] \}$ para $c_i \in \mathbf{C}$ e $l_j \in \mathbf{L}$
\cite{Faria2013evaluation}.
Estas regras de associação podem ser expressas pela função de associação vista
na Equação \ref{eq:assosiationFN}.

\begin{definition}
  A função de associações $A(l)$ é definida como:
  % $0$ se o rótulo é ``desconhecido'',
  % $i$ se o rótulo $l_j$ está no conjunto de classes $\mathbf{C}$,
  % $i$ se o rótulo $l_i$ está no conjunto de classes $\mathbf{C}$,
  \begin{align}
    A(l_j) : l_j \in \mathbf{L} \mapsto c_i \in \mathbf{C} &= \begin{cases} 
      \text{indefinido}        & \quad \text{se } l_j = \text{``desconhecido''} \\
      c_i         & \quad \text{se } \exists c_i = l_j \quad: c_i \in \mathbf{C}' \\
      c_i         & \quad \text{se } e_{ij} = max\{ e_{aj} : \in [0, m] \}
    \end{cases}
    \label{eq:assosiationFN}
  \end{align}
\end{definition}

No contexto de classificação multi-classe, a acurácia $\mathit{acc}_x$ para um
instante $x$ é definida como a média da acurácia de cada classe (\refequ{acc}).
A acurácia de cada classe $c_i$ no instante $x$, de forma semelhante à
definição da matriz de confusão, é definida como extensão da acurácia da
classificação binária (\refequ{acci}).
Para classificação binária a acurácia calculada com os valores
verdadeiro-positivo ($tp$), verdadeiro-negativo ($tn$), falso-positivo ($fp$) e
falso-negativo ($fn$).
Para cada classe $c_i$, o valor verdadeiro-positivo ($tp_i$) é definido como
número de exemplos onde o rótulo do exemplo $l$ é associado à
classe $c_i$ (\refequ{tpi}).
O valor falso-negativo ($fn_i$) são os exemplos da classe onde o
rótulo do exemplo não é associado à classe $c_i$ e o rótulo não é ``desconhecido'' (\refequ{fni}).
Os valores verdadeiro-negativo ($tn$) e falso-positivo ($fp$) são zero.
% pois dado um exemplo de classe $c_i$, ele pode ser classificado como .
% O como os valores $tp_i$ e $fp_i$ cobrem toda a matriz de confusão ($tp_i + fp_i = x$)

% \begin{definition}
%   A função de associações $A = (a_j) \in \mathbb{N}^n$ um item $a_j$ é
%   igual ao índice $i$ da classe $c_i$ associada ao rótulo $l_j$ sendo:
  \begin{align}
    tp_i            &= \sum_{j=1}^{n} e_{ij}        \quad \text{ se } l_j \neq \text{``desconhecido''} \text{ e } A(l_j) = c_i \label{eq:tpi}\\
    fn_i            &= \sum_{j=1}^{n} e_{ij}        \quad \text{ se } l_j \neq \text{``desconhecido''} \text{ e } A(l_j) \neq c_i \label{eq:fni}\\
    \mathit{acc}_i  &= \frac{tp + tn}{tp+fn+fp+tn}  = \frac{tp_i}{fn_i + tp_i} \label{eq:acci}\\
    \mathit{acc}_x & = \frac{1}{m} \sum_{i=1}^{m} \mathit{acc}_{i} \label{eq:acc}
  \end{align}
% \end{definition}

Concluindo as métricas de qualidade de classificação, a métrica de erro
combinado ($err$) é a média do erro de cada classe, sendo o erro de cada classe
o valor falso-negativo ($fn_i$) dividido pelo número de exemplos da classe.

\begin{align}
\mathit{err} &= \frac{1}{m} \sum_{i=1}^{m} \frac{fn_i}{fn_i + tp_i}
\end{align}

% \begin{definition}
%   A função de associações $A = (a_j) \in \mathbb{N}^n$ um item $a_j$ é
%   igual ao índice $i$ da classe $c_i$ associada ao rótulo $l_j$ sendo:
%   \begin{align}
%     FPR_i &= \frac{fp_i}{fp_i + tn_i}  & FNR_i = \frac{fn_i}{fn_i + tp_i} \\
%      \label{eq:cer}
%   \end{align}
% \end{definition}

% In the confusion matrix $M = m_{ij} \in \mathbb{N} ^{c \times{} l}$, computed by
% our evaluation script, each row denotes % one of the data sets original 
% the actual class $c$ and each column denotes the predicted label $l$ present in
% the captured output stream.
% Thus, each cell $M_{c, l}$ contains the count of examples from the test data set
% of class $c$ found in the output stream with the label $l$ assigned by the under
% evaluation experiment.

% Na matriz de confusão $\mathbf{E}_n$, a posição $e_{i,j}$

% As métricas de qualidade de classificação selecionadas para avaliar a
% implementação do \mfog são a 
% taxa de desconhecidos $UnkR_n$ na \refequ{unkr} \cite{Faria2013evaluation},
% acurácia média $acc_n$ na \refequ{acc}
% e Macro F-score ($Fscore$ na \refequ{fscore}, também referido na literatura por
% F1M) \cite{Sokolova2009,DaSilva2018thesis}.
% As métricas são extraídas para todos os exemplos classificados (instantes $n$)
% da respectiva matriz de erro $\mathbf{E}_n$.

% % \nota{'para todos os instantes n' ??}

% % \nota{Explicar o que significa cada elemento nas fórmulas}

% \begin{align}
%   \mathit{acc}_n        &= \frac{1}{M} \sum_{i=1}^{M} \frac{tp_i + tn_i}{tp_i+fn_i+fp_i+tn_i}
%   = \frac{1}{M} \sum_{i=1}^{M} \frac{\#Acc_i}{\#ExC_i}  \label{eq:acc} \\
%   \mathit{CER}_n        &= \frac{1}{M} \sum_{i=1}^{M} \frac{fp_i + fn_i}{tp_i+fn_i+fp_i+tn_i}
%   = \frac{1}{M} \sum_{i=1}^{M} \frac{\#Acc_i}{\#ExC_i}  \label{eq:cer} \\
%   \mathit{Precision}_n  &= \frac{1}{M} \sum_{i=1}^{M} \frac{tp_i}{tp_i+fp_i} \\
%   \mathit{Recall}_n     &= \frac{1}{M} \sum_{i=1}^{M} \frac{tp_i}{tp_i+fn_i} \\
%   \mathit{Fscore}\beta_n &= (\beta^2 +1) \cdot
%   \frac{
%   \mathit{Precision} \cdot \mathit{Recall}
%   }{
%     \beta^2 \cdot \mathit{Precision} +\mathit{Recall}
%   }\\
%   \mathit{Fscore}1_n   &= 2 \cdot \frac{
%     \mathit{Precision} \cdot \mathit{Recall}
%     }{
%       \mathit{Precision} +\mathit{Recall}
%     } \label{eq:fscore}
% \end{align}
% % = 2 \cdot \frac{tp}{2 \cdot tp + fn + fp}
% % \mathcal{L}         &= \frac{-1}{N} \sum_{i=1}^{M} \sum_{j=1}^{J} y_{i,j} \log(p_{i,j})

% % \nota{usar coeficiente d-intra vs d-extra grupo para determinar K de
% % cada label. Também pode-se usar os mesmos coeficientes para _log_}

% A transformação do fluxo de saída em uma matriz de erro é realizada no \sink,
% \notahl{como tratar o paralelismo desse elemento?\\
% Ele dá conta de todo o fluxo recebido dos classificadores?}
% \hlhl{onde} 
% \hlhl{tem-se disponível o fluxo original}
% \hlhl{com as rótulos corretas e o fluxo resultante}
% \hlhl{da classificação.}
% Esse módulo deve levar em consideração que pode haver reclassificação de um
% evento, previamente rotulado como desconhecido, em padrões oriundos de classe
% novidade ou extensão devido ao processo de detecção de novidades executado
% posteriormente ao surgimento do padrão em questão.

% Portanto os resultados são computados em função do fluxo de saída, então os $n$ nas
% equações são o índice do evento de saída.
% $\mathbf{unk}$ é o conjunto de eventos marcados como desconhecidos.
% \nota{oque eh unk? nesse paragrafo acima, erro de compilacao do latex?}

% \nota{frase confusa, eh so tirar o COMO e quebrar a frase: Esse módulo deve levar em consideração que
% COMO pode haver reclassificação de um evento, previamente rotulado como
% desconhecido, em padrões oriundos de classe novidade ou extensão devido ao
% processo de detecção de novidades executado posteriormente ao surgimento
% do padrão em questão}

% \begin{align}
%   E_{n,i,j} &= \bordermatrix{~ & c_i & \neg c_i \cr
%   l_j       & TP = \alpha           & FP = \gamma - \alpha                 \cr
%   \neg l_j  & FN = \beta - \alpha   & TN = n - (\alpha + \beta + \gamma)  \cr} \\
%   FM1       &= \frac{TP}{TP+\frac{FP+FN}{2}}
% \end{align}

% Os valores da matriz de erro para 

% \begin{align}
%   \alpha _j &= max( \{ |e_{i,j}|: i = 1 .. I \wedge \in \mathbf{E}_n \})
%           & \text{máximo da linha (rótulo)} \\
%   a_j &= i: |e_{i,j}| = \alpha _j
%           & \text{índice da classe associada à rótulo} \\
%   \beta   &= \sum_{j = 0}^{J} e_{i,j} : e_{i,j} \in \mathbf{E}_n
%           & \text{soma de uma coluna (rótulo)} \\
%   \gamma  &= \sum_{i = 0}^{I} a_{i,j} : e_{i,j} \in \mathbf{E}_n
%           & \text{soma de uma linha (classe)}
% \end{align}

Para a validação da corretude da implementação do \mfog com relação ao algoritmo
\minas original, ambos são executados com o mesmo \dataset de avaliação e as métricas de
qualidade de classificação são comparadas.

% As métricas de escalabilidade selecionadas são: número de nós processadores,
% tipo de processadores, uso de memória, tempo de processamento, taxa de eventos
% processados e latência entre a produção e classificação de um evento.

% \begin{align}
%   \Delta { } t_n       &= t_{n,sink} - t_{n,source} \label{eq:delta-t} \\
%   \overline{\Delta { } t}_n       &= \frac{1}{N} \sum_{i=1}^{N} \Delta { } t_n  \label{eq:avg-delta-t} \\
%   \alpha &= \# processors \\
%   \gamma &= \frac{\overline{\Delta { } t}}{}
% \end{align}

% \nota{
% como assim os resultados sao validos so se tiverem essas metricas? Entao quer
% dizer que qual medida eh valida? Vc quis dizer que se as medicoes que vc extrair
% com essas metricas forem iguais as medicoes do minas original, entao ai eh
% valido. Eh Isso?
% }

% Da implementação do \mfog é prevista a execução de experimentos com \datasets
% diversos, em especial os \datasets reais como \emph{Kyoto 2006+},
% que contenham evolução de conceitos.
% Os resultados desses experimentos irão conter as seguintes métricas:

% \begin{enumerate}[label={\alph*)}]
%   \item Qualidade de classificação (taxa de desconhecidos, acurácia e erro);
%   \item Escalabilidade (número de processadores, volume processado, tempo
%   decorrido);
%   \item Recursos computacionais utilizados (memória, tempo de processamento,
%   operações de leitura e escrita).
% \end{enumerate}

% ------------------------------------------------------------------------------
% Conclusão artigo

% We have used two types of evaluation measurements for each experiment:
% a measure of the full experiment execution time
% % extracted by using \emph{GNU Time 1.9} measuring 
% and, a set of qualitative measurements % será que é relevante falar da captura em Python?
% extracted by a Python script.

Um programa de avaliação foi construído seguindo as técnicas de referência como
matriz de confusão multi-classe com associação de classe de rótulo
\cite{Faria2016minas} para extrair medidas de qualidade de classificação.
Este programa recebe duas entradas, o conjunto de dados de teste e o fluxo de
saída capturado.
Com estas informações o programa gera a matriz de confusão do instante final, associação de
classes e rótulos, resumo de qualidade final com
\emph{Hits} (acurácia), \emph{Misses} (erro), \emph{Unknowns} (taxa de
desconhecidos) e, um gráfico de visualização do fluxo com as métricas e
marcadores de novidades para cada instante do fluxo de saída capturado.

As métricas de escalabilidade extraídas são o número de processadores, tempo de
processamento e latência de eventos e, estas métricas permitem o cálculo de
\emph{speedup} prático.

% % Our script computed the
% Our evaluation script was build following reference techniques like
% multi-class confusion matrix with label-class association \cite{Faria2016minas}
% to extract classification quality measurements.
% This script takes two inputs, the test data set and the captured output stream,
% and outputs the confusion matrix, label-class association,
% final quality summary with:
% \emph{Hits} (true positive), \emph{Misses} (Err), \emph{Unknowns} (UnkR); and
% stream visualization chart with per example instance summary with novelty label markers.
% % 
% % For clarity, it is necessary to detail how to interpret and compare each measure,
% % as for some it is trivial but others are not so much.

% In the confusion matrix $M = m_{ij} \in \mathbb{N} ^{c \times{} l}$, computed by
% our evaluation script, each row denotes % one of the data sets original 
% the actual class $c$ and each column denotes the predicted label $l$ present in
% the captured output stream.
% Thus, each cell $M_{c, l}$ contains the count of examples from the test data set
% of class $c$ found in the output stream with the label $l$ assigned by the under
% evaluation experiment.

% For the data set under use, original classes are $c \in \{N, A\}$, and for the
% labels we have the training class
% \emph{``N''}, \emph{unknown} label \emph{``-''} and the novelties $i \in
% \mathbb{N}$ so $l \in \{N, -\} \cup \mathbb{N}$.

% Added to the original confusion matrix $M$ are the rows \emph{Assigned} and
% \emph{Hits}.
% \emph{Assigned} row represents which original class $c$ (or if \emph{unknown},
% \emph{``-''}) the label $l$ is assigned to, this is computed by using the
% original class if $c = l$ or by associated novelty label to original class as
% described in \cite{DeFaria2015evaluation} section 4.1
% (class from where the most samples came from).
% \emph{Hits} row shows the true positive count for each label $l$
% with assigned class $c$, being the same value as cell $M_{c, l}$.
% % computed by coping the value of the 
% %  where the label is the same
% % and the class $c$ is the value in the above \emph{Assigned} row.
% The \emph{Hits} row is also used to compute the overall true positive
% in the summary table and stream visualization chart.
% % accuracy.
% One complete matrix is shown in Tab. \ref{tab:java-matrix}.