21.novelty-detection.tex

%!TeX root = ./00.ppgcc-2020.tex

\section{Fluxo de Dados e Mineração de Fluxo de Dados}

A Mineração de Dados é o processo de descoberta de padrões em conjuntos de dados
utilizando métodos derivados de aprendizagem de máquina, estatística e banco de
dados \cite{Gaber2005}. A mineração de \emph{Big Data} trata de enormes
conjuntos de dados que podem não ser processados em tempo viável devido a
limitações como memória ou armazenamento principal. Uma abordagem para minerar
esse tipo dado é a mineração de fluxo de dados. Os fluxos de dados são definidos
na Definição \ref{def:fluxodados}.

\begin{definition}
  Um \textit{Fluxo de Dados} $S$ é uma sequência massiva, potencialmente
  ilimitada de exemplos $\mathbf{X}_1, \mathbf{X}_2, \dots, \mathbf{X}_n, \dots$,
  recebida em instantes $T_1, T_2, \dots, T_n, \dots$,
  onde cada exemplo $\mathbf{X}$ tem dimensão $d$
  \cite{Aggarwal2003}.
  \label{def:fluxodados}
\end{definition}

O volume dos dados em \emph{Big Data} e a velocidade com qual eles são
produzidos afeta como os dados de um problema são modelados e manipulados.
Técnicas e algoritmos de mineração de fluxos de dados atendem esses desafios
utilizando restrições como apenas uma leitura do conjunto de dados e baixa
complexidade computacional na construção de seus algoritmos
\cite{Gama2007,Gaber2005}.
O processamento requerido para a mineração de um enorme fluxos de dados pode não
ser atendido por recursos computacionais de um único computador (nó), de forma
que pode ser necessária a distribuição dos dados e do processamento em múltiplos
nós computacionais em um sistema distribuído \cite{Gaber2005}.

% Computação distribuída é a área da ciência da computação que estuda sistemas
% em que os componentes são localizados em diferentes computadores (nós), que
% comunicam-se apenas por troca de mensagens e, para que o objetivo do sistema
% seja atingido, a cooperação entre os nós é necessária.
% Outras propriedades de um sistema distribuído são a concorrência entre os nós e
% possibilidade de
% falhas em partes independentes \cite{TanenbaumSteen2018}.

Para a construção de sistemas que apliquem técnicas de mineração de fluxos de
dados são necessárias bibliotecas e plataformas (\emph{frameworks})
que são abordadas na \refsec{frameworks}.

\subsection{Detecção de Novidade em Fluxo de Dados}

No âmbito de classificação de dados, parte da área de aprendizado de máquina, os
métodos de \acf{ND} lidam com o reconhecimento e a classificação de exemplos
que diferem de exemplos anteriores \cite{Markou2003,Perner2009,Gama2010}.
Esses métodos tratam da classificação em fluxos de dados que evoluem com o tempo.
% tempo, levando em consideração as características desse tipo de fluxos.

As características de evolução dos padrões observados em fluxos de dados contínuos são: 
Evolução de conceito (\evolution) em que novos padrões podem surgir;
Desaparecimento ou Recorrência de conceito, em que padrões podem desaparecer e
também podem reaparecer;
Mudança de conceito (\drift, deriva ou desvio) onde um padrão
gradualmente se transforma;
presença de Ruído e \emph{outliers} \cite{Gama2010}.

Os métodos de \nd são aplicados a diversos problemas como
detecção de intrusos \cite{Coull2003,Spinosa2008,Viegas2019,Cassales2019},
detecção de falhas \cite{Zhang2006},
diagnósticos médicos \cite{Perner2009},
detecção de regiões de interesse em imagens \cite{singh2004approach},
detecção de fraudes \cite{wang2003mining,Abdallah201690}, 
filtros de spam \cite{Hayat2010dct} e
detecção de variações comportamentais em um jogador \cite{Vallim20136258}.

Alguns métodos de \nd tratam de novidades como uma classificação de uma
ou duas classes (binariamente) onde um conceito representa a classe normal e as anomalias
são representadas pela falta de conceito no modelo ou como um segundo conceito
no modelo.
Além da abordagem de classificação binária, podem existir múltiplos conceitos em um mesmo
conjunto de dados, para isso é necessário abordar \nd como classificação
multi-classe.
Alguns métodos que abordam \nd como classificação multi-classe não
atendem completamente características de conjuntos com 
evolução temporal,
como \evolution e \drift, deixando de detectar múltiplos padrões que surgem
simultaneamente num intervalo de avaliação \cite{Faria2016ndds,Gama2010}.

A maioria dos métodos de \nd são construídos seguindo a abordagem de aprendizado
\emph{Offline-Online}. Essa abordagem estabelece que o método seja dividido em
duas fases:
a primeira fase (\emph{Offline}) usa um conjunto de exemplos rotulados para
deles extrair conceitos conhecidos e gerar um modelo;
a segunda fase (\emph{Online}) consome um conjunto ou fluxo de exemplos não
rotulados e detecta padrões-novidade.
Além de detectar padrões-novidade, alguns algoritmos classificam cada exemplo
em um dos conceitos do modelo, ou marca o exemplo como desconhecido.
Ainda na segunda fase, para atualizar o modelo, os exemplos marcados como
desconhecidos são utilizados para a extração de novos conceitos ou variações em
conceitos conhecidos \cite{Gama2010}.

Dentre os métodos de \nd que construídos na estratégia aprendizado \emph{Offline-Online},
muitos são baseados em
% \notaPA{Precisa de uma função para medir o grau de similaridade
% NCD - Normalized Compression Distance}
algoritmos de agrupamento não supervisionados, tanto
para construção do modelo inicial como na extração de novos conceitos dos
exemplos não explicados pelo modelo marcados como desconhecidos
\cite{Spinosa2009ollinda,Masud2010ECSMiner,Faria2013Minas}.

\subsection{O algoritmo MINAS}\label{sec:minas-og}

Um algoritmo de \nd que tem recebido atenção nos últimos anos é o algoritmo
MINAS, originalmente proposto por \citeonline{Faria2013Minas}, refinado por
\citeonline{Faria2016minas} e recentemente aprimorado por
\citeonline{DaSilva2018thesis}, com o uso de conceitos \emph{Fuzzy}, e expandido por
\citeonline{Costa2019thesis}, para tratar problemas multi-rótulo além dos problemas
multi-classe já tratados na versão original.
Esse algoritmo segue a abordagem de duas fases no modelo \emph{Offline-Online} e
emprega algoritmos de agrupamento (\emph{clustering}) não supervisionados como
\emph{K-means} e \emph{CluStream}.

\newcommand{\mcluster}{\emph{micro-cluster}\xspace}
\newcommand{\mclusters}{\emph{micro-clusters}\xspace}

O algoritmo MINAS em sua fase \emph{Offline} consome um conjunto de treinamento
contendo exemplos rotulados.
Esse conjunto de treinamento é dividido em grupos usando como chave o rótulo,
e para cada grupo de exemplos o método de agrupamento é executado.
O método de agrupamento objetiva resumir um conjunto maior de exemplos em um
conjunto menor de \mclusters (Definição \ref{def:microcluster}).
A cada \mcluster é adicionado o rótulo do grupo original e todos \mclusters
são arranjados em um único conjunto formando o modelo de decisão.

\begin{definition}
  Para um grupo de exemplos $\mathbf{X} \in \mathcal{M}$, um \mcluster
  $\mathcal{M}$ é uma tupla de quatro componentes $(n, \mathbf{LS}, \mathbf{SS}, t)$
  derivados dos exemplos representados por este \mcluster onde \cite{Aggarwal2003,Faria2016minas}:
  \begin{itemize}
    \item $n$ é a contagem de exemplos,
    \item $\mathbf{LS}$ é o vetor soma linear dos exemplos sendo $\mathbf{LS}_d = \sum_{i=0}^{n} \mathbf{X}_{i,d}$,
    \item $\mathbf{SS}$ é o vetor da soma dos quadrados dos exemplos sendo $\mathbf{SS}_d = \sum_{i=0}^{n} (\mathbf{X}_{i,d})^2$,
    \item $t$ é o instante de chegada do último exemplo adicionado ao \mcluster.
  \end{itemize}
  \label{def:microcluster}
\end{definition}

% (1, 2), (1, 2), (3, 4) = (1^2 + 1^2 + 3^2, 2^2 + 2^2 + 4^2)

Deste sumário extrai-se o centro e o raio que são utilizados na operação de
classificação da fase \emph{Online} \cite{Faria2016minas}.
O vetor centro é definido pelo algoritmo de agrupamento e corresponde ao
ponto médio dos exemplos do \mcluster, visto na Equação \ref{eq:centro}.
O raio pode ser definido de duas maneiras e ambas dependem no conjunto das
distâncias $D_\mathcal{M}$ entre centro e cada elemento do \mcluster.
A primeira definição de raio é o desvio padrão das distâncias em $D_\mathcal{M}$
multiplicado por um fator parametrizado \cite{Faria2016minas}, visto na Equação
\ref{eq:raio_paper}, a segunda definição é o valor máximo das distâncias em
$D_\mathcal{M}$ \cite{Faria2013source}, visto na Equação \ref{eq:raio_max}.

\begin{definition}
  O vetor centro é o ponto médio dos exemplos do \mcluster:
  \begin{align}
    centro    &= 1/n \cdot \mathbf{LS} \label{eq:centro}
  \end{align}
  O conjunto das distâncias $D_\mathcal{M}$ entre centro e cada elemento do \mcluster:
  \begin{align}
    D_\mathcal{M}  &= \{ d_i : d_i = dist(\mathbf{X}_i, centro) \} & \mathbf{X}_i \in \mathcal{M} \nonumber
  \end{align}
  O escalar raio é o desvio padrão ou o máximo do conjunto $D_\mathcal{M}$:
  \begin{align}
    \mu       &= 1/n \cdot \sum_{i=1}^{n} d_i             & d_i \in D_\mathcal{M} \nonumber \\
    \sigma^2  &= 1/n \cdot \sum_{i=1}^{n} (d_i - \mu) ^2  & d_i \in D_\mathcal{M} \nonumber \\
    \sigma    &= \sqrt{ \sigma^2 }                        & \nonumber \\
    raio_1    &= f_{raio} \cdot \sigma                    & \label{eq:raio_paper}\\
    raio_2    &= max\{ d_i \in D_\mathcal{M} \}           & \label{eq:raio_max}
  \end{align}
\end{definition}

% Aggarwal 2003
% 5: The mean is equal to CF1t/n. 
% The standard deviation is equal to sqrt( CF2t/n − (CF1t/n)2 ).

A distinção entre as duas definições de raio é importante, pois ela impacta
imensamente nos resultados.
Para cada \dataset ou problema abordado uma configuração de parâmetros afinada
é essencial, pois as características da distribuição dos valores e sua associação
às classes são geralmente únicas para cada problema.
Em testes preliminares, a implementação do algoritmo \minas com raio definido
pela distância máxima (\refequ{raio_max}) mostrou facilidade na configuração quando
comparado com a mesma implementação utilizando a definição que utiliza desvio
padrão (\refequ{raio_paper}), pois pequenas variações no parâmetro $f_{raio}$
resultavam em alta taxa de desconhecidos ou alta taxa de erro.

% \minas \cite{Faria2016minas} is an offline-online \nd algorithm, meaning it has
% two distinct phases. The first phase (offline) creates an initial model set with
% several clusters based on a clustering algorithm with a training set.
% Each cluster can be associated with only one class of the problem, but each
% class can have many clusters.

% -> which is the main focus of our work

% During its online phase, which is the main focus of our work, \minas performs
% three tasks in (near) real-time, in summary, classification, novelty detection,
% and model update tasks in a potentially infinite data stream, as shown in
% Algorithm \ref{alg:minas-main}.

Na fase \emph{Online}, listada no Algoritmo \ref{alg:minas-main}, o algoritmo
MINAS executa três operações: classificação de novos exemplos, detecção de
padrões-novidade e atualização do modelo de decisão \cite{Faria2016minas}.

\begin{algorithm}[htb]
  % \DontPrintSemicolon
  \SetKwFunction{nearestCluster}{clusterMaisPróximo}
  \SetKwFunction{clustering}{agrupamento}
  \SetKwFunction{NoveltyDetection}{DetecçãoNovidade}
  \SetKwFunction{handleModelSleep}{moveModeloAntigo}
  \SetKwFunction{removeOldSamples}{removeExemplosAntigos}
  % 
  \SetKwProg{Function}{Função}{:}{}
  \SetKw{continue}{continue}
  % 
  \SetKwInOut{KwIn}{Entrada}
  \SetKwInOut{KwOut}{Saída}
  \KwIn{Modelo, fluxoEntrada}
  \KwOut{fluxoSaída}
  % 
  \SetKwData{cleaningWindow}{janelaLimpeza}
  \SetKwData{noveltyDetectionTrigger}{gatilhoDetecçãoNovidade}
  \SetKwInOut{KwParams}{Parâmetros}
  \KwParams{\cleaningWindow, \noveltyDetectionTrigger}
  % \KwSty{Parameters}: \cleaningWindow, \noveltyDetectionTrigger\\
  % 
  \SetKwFunction{MinasOnline}{MinasOnline}
  \Function{\MinasOnline{Modelo, fluxoEntrada}}{
    Desconhecidos $\gets$ $\emptyset$, ModeloAntigo $\gets$ $\emptyset$ \;
    últimaLimpeza $\gets 0$ , proximaNovidade $\gets 0$\;
    % sampleIn $\gets 0$\;
    \ForEach{ {$exemplo_{i}$} $\in$ fluxoEntrada }{
      % exemplo.rótulo $\gets$ unknown\;
      % (distância, cluster) $\gets$ \nearestCluster(exemplo, Modelo)\;
      maisPróximo $\gets$ \nearestCluster(exemplo, Modelo)\;
      \eIf{maisPróximo.distância $<$ maisPróximo.cluster.raio}{
        exemplo.rótulo $\gets$ maisPróximo.cluster.rótulo\;
        maisPróximo.cluster.últimoUso $ \gets i $ \;
      }
      {
        exemplo.rótulo $\gets$ ``desconhecido''\;
        Desconhecidos $\gets$ Desconhecidos $\cup$ exemplo\;
        \If{$|\;Desconhecidos\;| \geq$ \noveltyDetectionTrigger}{
          % \tcc{Novelty Detection}
          novidades $\gets$ \NoveltyDetection(Modelo $\cup$ ModeloAntigo, *Desconhecidos)\;
          Modelo $\gets$ Modelo $\cup$ novidades\;
        }
        \If{ $ i > $ ( últimaLimpeza $ + $ \cleaningWindow )}{
          Modelo $\gets$ \handleModelSleep(Modelo, *ModeloAntigo, últimaLimpeza)\;
          Desconhecidos $\gets$ \removeOldSamples(Desconhecidos, últimaLimpeza)\;
          últimaLimpeza $ \gets i $\;
        }
      }
      fluxoSaída.adicione(exemplo)\;
    }
  }
  \caption{Fase \emph{online} interpretada do algoritmo \minas \cite{Faria2016minas}.}
\label{alg:minas-main}
\end{algorithm}

A primeira operação é a classificação, onde exemplos do fluxo de dados
são consumidos e avaliados pelo modelo de decisão.
O modelo de decisão avalia cada exemplo calculando a distância euclidiana
entre o exemplo e todos \mclusters do modelo, selecionando o
\mcluster de menor distância.
Se a distância entre o exemplo e o centro do \mcluster for menor que
o raio do \mcluster, o exemplo é classificado com o rótulo do \mcluster
e o sumário estatístico do \mcluster é atualizado.
%  (especialmente elemento $t$ usado para remoção de modelos antigos).
Caso a distância (mínima no modelo) seja maior que o raio,
o exemplo é marcado como desconhecido e armazenado
no conjunto de desconhecidos \cite{Faria2016minas}.

A segunda operação da fase \emph{Online} é a detecção de padrões novidade
listada no Algoritmo \ref{alg:minas-nd} que é executada quando o tamanho do
conjunto de desconhecidos é maior que um parâmetro predefinido.
Esta operação utiliza o agrupamento (\emph{clustering} descrito na fase
\emph{Offline}) e valida os \mclusters gerados verificando sua
representatividade e coesão.
A representatividade é avaliada com o número de exemplos do conjunto de
desconhecidos que é englobado pelo novo \mcluster, onde o valor mínimo de
exemplos é parametrizado.

Um padrão é considerado coeso se o valor $\mathit{silhueta}$, Equação
\ref{eq:silhueta}, é maior que $0$.
O valor $\mathit{silhueta}$ por sua vez é calculado com os valores:
$b$ a distância do novo \mcluster até o mais próximo contido no modelo atual;
$a$ o desvio padrão das distâncias entre o centro do novo \mcluster e cada
exemplo representado no novo \mcluster.

\begin{align}
  a = \sigma &= \mathit{SD}\{ dist(\mathbf{X}_i, centro) : \mathbf{X}_i \in \mathcal{M} \} \nonumber\\
  b &= min\{ dist( centro_{novo}, centro(\mathcal{M}_i)) : \mathcal{M}_i \in {Modelo}\}\nonumber\\
  \mathit{silhueta} &= \frac{b - a}{max(b, a)} \label{eq:silhueta}
\end{align}

% No entanto, se o valor raio for definido como o $f_{raio} \cdot \mathcal{M}_{\sigma}$ Equação
% \ref{eq:raio_paper}, se um novo \mcluster é formado apenas por exemplos
% desconhecidos e, todo exemplo desconhecido tem distância ao cluster mais próximo
% maior do que o raio do cluster mais próximo,
% segue que o conjunto de distâncias $d_{novo} = \{ dist( centro_{novo}, centro(\mathcal{M}_i)) : \mathcal{M}_i \in {Modelo}\}$
% é definido com $centro_{novo} = 1/n \cdot \mathbf{LS}$
% onde $\mathbf{LS} = \sum_{i=0}^{n} X \in \mathcal{M}_{novo}$
% e como $\forall X \in \mathcal{M}_{novo} \land \mathcal{M}_i \in {Modelo}$
% segue que
% $dist( X, centro(\mathcal{M}_i)) > \mathcal{M}_i(raio) = f_{raio} \cdot \mathcal{M}_\sigma $,
% segue que $\nexists d \in d_{novo} : d < (f_{raio} \cdot \mathcal{M}_{i \sigma}) \forall \mathcal{M}_i \in {Modelo}$
% portanto $b \geq (f_{raio} \cdot \mathcal{M}_{i \sigma}) \forall \mathcal{M}_i \in {Modelo}$
% e como $a = \sigma$ e $b / f_{raio} \geq \sigma$, 
% então sendo $f_{raio} < 0$
% $silhueta = \frac{b-a}{\lceil a, b \rceil} = \frac{b - \sigma}{\lceil b, \sigma \rceil} \implies 0 < silhueta < 1$.
% Sendo então todo \mcluster criado à partir de exemplos desconhecidos coeso.
% % $a = \mathcal{M}_{raio} / f_raio$
% % e que \nonumber\\
% % o valor de
% % $a$ será sempre menor do que o valor $b$
% % Sendo $a, b \geq 0$,
% % Se $a > b$, então $b-a \leq 0$, portanto  $si = \frac{b-a}{a}$, et

\begin{algorithm}[htb]
  \SetKwFunction{nearestCluster}{clusterMaisPróximo}
  \SetKwFunction{clustering}{agrupamento}
  \SetKwFunction{NoveltyDetection}{DetecçãoNovidade}
  \SetKwFunction{handleModelSleep}{moveModeloAntigo}
  \SetKwFunction{removeOldSamples}{removeExemplosAntigos}
  % 
  \SetKwProg{Function}{Função}{:}{}
  \SetKw{continue}{continue}
  % 
  \SetKwInOut{KwIn}{Entrada}
  \SetKwInOut{KwOut}{Saída}
  \SetKwInOut{KwParams}{Parâmetros}
  % 
  \SetKwData{minExamplesPerCluster}{minExemplos}
  \SetKwData{noveltyFactor}{fatorNovidade}
  \KwParams{\minExamplesPerCluster, \noveltyFactor}
  % 
  \Function{\NoveltyDetection{Modelo, Desconhecidos}}{
    novoModelo $\gets$ $\emptyset$\;
    \ForEach{novo $\in$ \clustering(Desconhecidos)}{
      \If{$(|\;novo.exemplos\;| \geq$ \minExamplesPerCluster $) \land (\;novo.silhueta\; > 0)$}{
        maisPróximo $\gets$ \nearestCluster(novo, Modelo)\;
        \eIf{maisPróximo.distância $<$ (maisPróximo.cluster.raio $\times$ \noveltyFactor)}{
          novo.rótulo $\gets$ maisPróximo.cluster.rótulo\;
          novo.tipo $\gets$ ``extensão''\;
        }{
          novo.rótulo $\gets$ proximaNovidade\;
          proximaNovidade $\gets$ proximaNovidade $+ 1$\;
          novo.tipo $\gets$ ``novidade''\;
        }
        % novo.últimoUso $ \gets i $ \;
        \label{alg:MINAS-nd:reclassify}
        Desconhecidos $\gets$ Desconhecidos $-$ novo.exemplos\;
        novoModelo $\gets$ novoModelo $\cup$ novo\;
      }
    }
    \Return{novoModelo}\;
  }
  \caption{Detecção de Novidades interpretada do algoritmo \minas \cite{Faria2016minas}.}
  \label{alg:minas-nd}
\end{algorithm}

Para atribuição de rótulos aos \mclusters gerados, o algoritmo MINAS
encontra no modelo atual o \mcluster mais próximo pela distância
euclidiana e classifica em dois tipos de conceitos.
Se a distância é menor que um parâmetro predefinido,
o novo \mcluster gerado recebe como rótulo o valor de extensão
de conceito conhecido.
Caso contrário, se o novo \mcluster está mais distante,
um novo conceito foi encontrado e o rótulo marca um padrão novidade.
Após a atribuição do rótulo do novo \mcluster, ele é adicionado
ao modelo de decisão.

% \minas attempts to classify each incoming unlabeled instance according to the
% current decision model. Instances not explained by the current model
% receive an \textit{unknown} label and are stored in an unknowns-buffer.
% When the unknowns-buffer reaches a preset threshold, \minas executes the
% Novelty Detection function.
% After a set interval, samples in the unknowns-buffer are considered to be
% noise or outliers and removed.
% The algorithm also has a mechanism to forget clusters that became obsolete and
% unrepresentative of the current data stream distribution, removing them from
% the Model and storing in a Sleep Model for possible recurring pattern
% detection \cite{Faria2016minas}.

% The Novelty Detection function, illustrated in Algorithm \ref{alg:MINAS-nd},
% groups the instances to form new clusters, and each new cluster is validated to
% discard the non-cohesive or unrepresentative ones.
% Valid clusters are analyzed to decide if they represent an extension of a
% known pattern or a completely new pattern. In both cases, the model absorbs the
% valid clusters and starts using them to classify new instances.

% O \minas, como já foi discutido na Seção \ref{sec:minas-og}, classifica
% exemplos e detecta
% novidades em DS e considera em sua composição \emph{concept drift} e
% \emph{concept evolution}, sendo capaz de classificar como extensão de classe
% conhecida e identificar padrões novidade sem intervenção de especialista
% \cite{Faria2016minas}.

O algoritmo \minas original \cite{Faria2016minas} tem uma implementação
de referência\footnote{
  A implementação de referência do algoritmo \minas está disponível em \url{http://www.facom.ufu.br/~elaine/MINAS}.
}
\cite{Faria2013source}, aqui referida como \refminas, escrita em Java utilizando
os algoritmos base como \emph{K-means} e \emph{CluStream} da biblioteca MOA
\cite{MOA}.

Além do algoritmo \minas, existem derivados que estendem a implementação
original seguindo sua estrutura básica, duas notáveis são FuzzyND e MINAS-LC.
O algoritmo FuzzyND foi proposto em \citeonline{DaSilva2018,DaSilva2018thesis} e
incrementa o algoritmo original aplicando teoria de conjuntos \emph{fuzzy}
modificando a representação de \cluster, o algoritmo de agrupamento, a manutenção
do modelo para exemplos conhecidos e para novidades.
O algoritmo MINAS-LC foi proposto por \citeonline{Costa2019thesis} e trata a
classificação multi-rótulo, porém não trata evoluções de conceito (\emph{Concept
Evolution}).
Estes trabalhos foram importantes para entender MINAS e ajudaram a construir uma
ideia geral do algoritmo e como proceder para criação de uma versão distribuída.

% \subsubsection{Algoritmo Extensão FuzzyND}

% A modificação afeta o método de construção de \clusters, método de classificação
% de exemplos e método de detecção de novidades de acordo com a nova representação.

% A avaliação do algoritmo FuzzyND foi feita por meio de experimentos usando 3 
% \datasets sintéticos (\emph{MOA3}, \emph{RBF}, \emph{SynEDC})
% e por comparação com o MINAS.
% O método de avaliação utilizado baseia-se na matriz de confusão incremental
% descrita por \citeonline{Faria2016ndds}, extraindo dessa matriz duas métricas:
% acurácia (\emph{Macro F-Score}) \cite{Sokolova2009} e
% taxa de desconhecidos (\emph{UnkR}) \cite{Faria2016minas}.
% Em geral, o algoritmo FuzzyND detecta melhor novidades e, consequentemente,
% é mais robusto a valores atípicos (\emph{outlier}), porém perde a capacidade
% de reconhecer padrões recorrentes.

% \subsubsection{Algoritmo Extensão MINAS-LC e MINAS-BR}
% \label{sub:minas-derivados}

% As alterações fundamentais propostas são:
% a representação de \cluster onde MINAS-LC troca o rótulo, que era única, por uma multi-rótulo;
% a transformação de problema aplicada ao conjunto de treinamento para transformá-lo de um
% conjunto multi-rótulo para um conjunto multi-classe (simplificação)
% em duas variações \emph{Label Powerset} e \emph{Pruned Sets} com
% mineração de conjunto de itens frequentes.

% Já o trabalho de \citeonline{Costa2019}, estende o algoritmo original para que
% classifique um exemplo com uma ou mais rótulos usando a transformação
% \emph{Binary Relevance}, o que deu origem ao algoritmo MINAS-BR.
% O algoritmo modifica a representação do modelo, originalmente conjunto de \clusters, para
% um grupo de \clusters por classe (rótulo).
% Também modifica o método de agrupamento, substituindo a inicialização do 
% algoritmo \emph{K-means}, originalmente aleatória, pelo algoritmo 
% \emph{Leader Incremental Clustering} \cite{Vijaya2004505}.

% O algoritmo MINAS-BR também é experimentalmente avaliado com 4 \emph{data sets}
% sintéticos: \emph{MOA-3C-5C-2D}, \emph{MOA-5C-7C-2D}, \emph{MOA-5C-7C-3} da
% ferramenta MOA \cite{MOA} e \emph{4CRE-V2}
% \footnote{
%   A versão original do \dataset 4CRE-V2 está disponível em
%   \url{https://sites.google.com/site/nonstationaryarchive/home}.
% }
% gerados pelo método \emph{Radial Basis Function} \cite{souza2015,Costa2019}.
% O algoritmo MINAS-BR foi comparado com 7 algoritmos da literatura também
% disponíveis na ferramenta MOA \cite{MOA}, diferente da avaliação do FuzzyND que
% compara diretamente com MINAS. Para análise, os 7 algoritmos foram divididos em
% dois grupos \cite{Costa2019}.
% O primeiro grupo de 3 algoritmos com acesso às rótulos corretas para
% atualização do modelo e com a técnica ADWIN (\emph{ADaptive WINdowing}) para detectar
% mudanças de conceito (\emph{Concept Drift})
% O segundo grupo com os 4 algoritmos sem acesso às rótulos corretas,
% ou seja, sem \emph{feedback} externo, mesma condição do MINAS-BR \cite{Costa2019}.

% A avaliação elencada por \citeonline{Costa2019} leva em consideração que as classes
% contidas no conjunto de testes podem não ter correlação direta com os padrões identificados
% pelos algoritmos.
% Para tratar a divergência, uma estratégia baseada em proposta anterior por
% \citeonline{Faria2016ndds} foi apresentada com alterações para exemplos multi-rótulo.
% Após associação entre padrões de novidade e classes novidade foi possível calcular
% métricas tradicionais.
% A estratégia é executada na fase de classificação seguindo as regras:

% \begin{enumerate}

%   \item após o consumo do exemplo $X_n$;
  
%   \item para todo padrão $P_i$ (rótulo atribuída) identificado sem
%   associação até o momento;
  
%   \item com classes novidade $y_j$ (rótulo real) presentes em exemplos antes
%   $X_n$;
  
%   \item preenche-se a tabela de contingência $\mathbf{T}_{(i,j)}$ relacionando
%   padrão $P_i$ e classe $y_j$;
  
%   \item calcula-se o grau de dependência $\mathit{F1}$ derivado da tabela de
%   contingência $\mathit{F1}_{(i,j)} = f(\mathbf{T}_{(i,j)})$;
  
%   \item valores $\mathit{F1}_{(i,j)} = 0$ são descartados;
  
%   \item dentre os valores restantes: o padrão $P_i$ é associado à classe $y_j$
%   se $\mathit{F1}_{(i,j)}$ é máximo.

% \end{enumerate}

% As métricas utilizadas por \citeonline{Costa2019} após a associação de classes e
% padrões são as tradicionais taxa de desconhecidos (\emph{UnkRM}) e \emph{F1M}.
% Os resultados apresentados indicam que MINAS-BR capturou todas as novidades dos
% \datasets sintéticos de teste e mostrou, como esperado, melhores métricas que os
% 4 algoritmos equivalentes da literatura ficando abaixo dos 3 com \emph{feedback}
% externo.

% Os trabalhos abordados nessa \refsec{nd}, têm em
% comum, além do algoritmo base, as métricas de avaliação acurácia (\emph{Macro F-Score} e \emph{Macro
% F-Measure} F1M) e taxa de desconhecidos, aplicadas com devido tratamento.
% Também é comum entre eles o uso de \datasets sintéticos.
% Outro potencial não explorado do MINAS é em aplicações reais, ou seja,
% consumindo além de \datasets reais, fluxos realistas em ambientes simulados ou
% reais porém considerando uso de recursos computacionais.

% Observando a arquitetura dos algoritmos abordados na \refsec{nd}, nota-se as semelhanças:
% a fase offline centrada no processo de agrupamento e criação de modelo;
% a fase online dividida em classificação (com atualização das estatísticas do modelo)
% e detecção de padrões, onde novamente o processo de agrupamento é central.
% Portanto, apesar de outros trabalhos expandirem o algoritmo com diferentes técnicas, seu
% núcleo continua relevante.

Algumas propostas de modificação no algoritmo \minas foram recorrentes durante
as discussões no desenvolvimento deste trabalho porém, como estão fora do escopo
deste trabalho, ficam somente aqui registradas para algum trabalho futuro.
As modificações são:

\begin{enumerate}[label={\alph*)}]

  \item Na fase \emph{offline} a verificação de sobreposição de \clusters
  pertencentes a classes distintas e tratamento adequado;
  
  \item Diferentes métodos de cálculo de distância entre pontos além da
  distância euclidiana;
  
  \item Mudança de representação de \clusters de esferas ($\mathbf{X}, d$) para
  retângulos ($\mathbf{X}, \mathbf{D}$) no espaço $\mathbb{R}^d$, melhorando o
  tratamento de conjuntos de dados onde as características representadas por
  cada dimensão são completamente independentes;
  % Author: Isso altera a função de pertinência.
  % \notaPA{cacofonia}
  
  % \item um modo interativo onde o \cluster é formado, mostrado ao especialista
  % que o classifica como inválido (ruído ou não representativo) ou válido,
  % podendo conter uma ou mais classes e, se contiver mais que uma classe corte em
  % grupos menores até conter somente uma classe;
  
  % \item ainda considerando interação com especialista, a possibilidade de
  % injetar um exemplo não pertencente a uma classe, ou seja, marcar o exemplo
  % como não pertencente a uma classe para mantê-lo na memória de
  % desconhecidos e, eventualmente forçar criação de um \cluster que represente
  % uma classe geometricamente próxima mas semanticamente distinta;

  \item Em uma implementação de avaliação, ajuste automático de parâmetros
  otimizando para o máximo de classificações corretas e mínimo tempo de execução
  para um conjunto de dados fornecido.

\end{enumerate}