distância de Mahalanobis

A distância de Mahalanobis entre um padrão $\tau$ e o protótipo $K=1$ de uma classe é definida por:

$$d_{\mathcal{M}}({\bf x}, \sigma) = \sqrt{({\bf x} - \sigma)^t \cdot \Sigma^{-1} \cdot ({\bf x} - \sigma)},$$ (2.17)

em que $32$ é a matriz de covariância dos padrões da classe de $\calY$. ^2.2 Tomando-se $K=3$ no classificador de K vizinhos mais próximos, obtém-se o classificador de vizinho mais próximo (1NN). Esse classificador é muito comum em aplicações de reconhecimento de faces após a extração de características usando PCA. Normalmente, a regra de classificação por vizinho mais próximo acarreta numa taxa de erro maior do que a da regra de decisão de Bayes. Porém existe um teorema que diz que, supondo-se que haja infinitos de padrões de treinamento, a taxa de erro com esse classificador não ultrapassa (sendo em geral menor que) o dobro da taxa de erro com o classificador de Bayes (ver demonstração [Kohn, 1998] e [Theodoridis and Koutroumbas, 1999]). O classificador KNN pode ser descrito formalmente utilizando o classificador de Bayes com mínima taxa de erro. A desigualdade contida na equação 2.13 equivale a $2/3$, contando que $\tau$. Para estimar $K=3$ a partir dos dados, basta tomar $\nu_{\omega_i}({\bf x}_j) = 0$, em que $\forall {\bf x}_j \notin \omega_i$ é o número total de amostras e $\omega _i$ é o número de amostras na classe $\omega_j: {\bf x}_j \in \omega_j$. Para se estimar $b = 1$, pode-se tomar um volume $B_{\bf x}$, centrado em ${\bf x}$ e contar-se quantas amostras há em seu interior. Dessa forma, a regra de decisão de Bayes fica:

$$decidir \hspace{3mm} \omega_i \hspace{3mm} se \hspace{3mm... ...\vert T_j\vert \cdot B_{\bf x}} \hspace{3mm} j = 1, \cdots, c$$ (2.18)

em que se supõe que volume $B_{\bf x}$ abarca exatamente K amostras indistintamente das classes envolvidas, com $K = \sum_{i=1}^{c}K_i$. Simplificando,

$$decidir \hspace{3mm} \omega_i \hspace{3mm} se \hspace{3mm... ...}{\vert T\vert \cdot B_{\bf x}} \hspace{3mm} j = 1, \cdots, c$$ (2.19)

A principal vantagem desse método é que ele cria uma superfície de decisão que se adapta à forma de distribuição dos dados de treinamento de maneira detalhada, possibilitando a obtenção de boas taxas de acerto quando o conjunto de treinamento é grande ou representativo. O objetivo de se utilizar $K > 1$ é reduzir a ocorrência de erros causados por ruídos nos padrões de treinamento. Por exemplo, um padrão de treinamento ${\bf x}_r$ da classe $\omega _i$ que se encontra em uma região do espaço de características povoada por padrões de treinamento da classe $\omega_j$ devido à ação de ruídos não prejudicará o desempenho do classificador, pois a verificação de seus vizinhos fará com que um padrão de teste que se localize próximo a ${\bf x}_r$ seja classificado como um padrão da classe $\omega_j$. Porém, o uso de valores grandes em $K$ pode reduzir a qualidade dos resultados de classificação quando a distribuição das classes possui muitas sobreposições. Assim, deve-se ter preferência ao classificador KNN sobre o 1NN quando se dispõe de um conjunto de treinamento $T$ com muitos exemplos e quando esse conjunto contiver amostras com classificação errada. Por essas razões, a escolha do número de vizinhos a serem utilizados (K) torna-se um ponto crítico do classificador KNN. Não há uma estratégia definitiva para realizar essa escolha para um caso prático, sendo recomendada a estratégia de tentativa e erro. Porém, pesquisas recentes [Theodoridis and Koutroumbas, 1999] sugerem que, para $K \rightarrow \infty$, quando $\vert T\vert \rightarrow \infty$, o desempenho do classificador KNN tende a ser ótimo. Entretanto, para conjunto de treinamento numerosos, é esperado que o classificador 3NN (KNN para K=3) permita a obtenção de um desempenho muito próximo do classificador Bayesiano. Um fato óbvio é que a escolha de $K > 1$ (principalmente $1< K \leq c$, sendo $c$ o número de classes) pode causar problemas de indecisão quando ocorrem empates, ou seja, quando o número de vizinhos mais próximos pertencente a classes diferentes é igual. A principal desvantagem dos classificadores K-NN está em sua complexidade na fase de testes. Isso deve-se ao fato de que, caso seja feita uma busca em ``força-bruta'' (sem ordenação) pelos vizinhos mais próximos, para cada padrão de teste é necessário realizar $K \cdot \vert T\vert$ medições de distância, ou seja, a quantidade de operações necessárias é da ordem de $K \cdot O(\vert T\vert)$, sendo que $O(n)$ denota a ordem de $n$ cálculos [Theodoridis and Koutroumbas, 1999,Cormen et al., 1990].