Função Critério Baseada em Distância Nebulosa para $c$ Classes

A distância nebulosa proposta em [Lowen and Peeters, 1998], foi definida para o cálculo da distância entre dois conjuntos nebulosos. Em [Campos et al., 2001] (trabalho descrito na seção 3.4), propusemos a utilização dessa medida de distância como função critério para realizar seleção de características utilizando o método de busca proposto em [Pudil et al., 1994] (SFSM). Em aplicações práticas, como reconhecimento de pessoas, usualmente há mais de duas classes (mais de duas pessoas a serem reconhecidas). Por isso, é necessário criar uma solução para o fato de que uma distância só pode ser medida entre dois elementos. Conforme mencionado anteriormente, uma solução possível é calcular o ínfimo das distância entre todos os pares de conjuntos, conforme a seguinte equação:

$$g_p^{\tau} (\nu_1, \nu_2, \cdots, \nu_{c}) = \inf_{k = 2, \cdots, c; l = 1, \cdots, m} d_p^{\tau}(\nu_k,\nu_l)$$ (5.1)

De acordo com o que foi discutido na seção 3.4.5, a complexidade de tempo para calcular-se $d_p^{\tau}(\nu_k,\nu_l)$ é de $O(\vert T\vert^2) + O(\vert T\vert) \cdot O(b^2)$, sendo, no pior caso, $O(\vert T\vert^2)$, e, no melhor caso, $O(\vert T\vert^3)$, em que $\forall {\bf x}_j \notin \omega_i$ é o número total de padrões no conjunto de treinamento composto por duas classes. Suponhamos que cada classe possua $\vert T\vert/c$ padrões de treinamento. Para implementar a equação 5.1, é necessário calcular $c^2$ vezes a distância $d_p^{\tau}(\nu_k,\nu_l)$, o que resulta em uma complexidade de

$$O(c^2) \cdot (O({{\vert T\vert^2} / {c^2}}) + O({\vert T\vert / c}) \cdot O(b^2)) =$$ (5.2)

$$O({\vert T\vert^2}) + O(c) \cdot O(\vert T\vert) \cdot O(b^2)$$ (5.3)

Isso implica que, no pior caso, o tempo de execução da função critério da equação 5.1 é de $O(c) \cdot O(\vert T\vert^3)$ e, no melhor caso é de $O(\vert T\vert^2)$.

Como os algoritmos de busca para seleção de características avaliam, através da função critério, muitos conjuntos de características para chegarem ao resultado final, é necessário que essa seja o mais eficiente possível. Para implementar uma função critério eficiente, com as mesmas propriedades que a função proposta na seção 3.4 para problemas com mais de duas classes, propusemos uma função critério baseada na seguinte diferença local:

$$f_{\bf x}^{\tau}(\nu_1, \nu_2, \cdots, \nu_{c}) = \inf_{{\bf... ...; i = 1, \cdots, j} \vert \nu_i({\bf y}) - \nu_j({\bf z})\vert$$ (5.4)

Note que essa equação é bastante semelhante à 3.36, com a diferença de que deve ser calculado o ínfimo da diferença entre os graus de pertinência de todos os padrões de todas as classes que estão na bola $B({\bf x}, \tau)$. Assim, a função critério fica:

$$f_p^{\tau} (\nu_1, \nu_2, \cdots, \nu_{c}) = [\int_{\calF}[f... ... x}^{\tau}(\nu_1, \nu_2, \cdots, \nu_{c})]^p d{\bf x} ]^{1/p},$$ (5.5)

Conforme o método que utilizamos para efetuar a fuzzificação (vide seção 3.4.3),
$\nu_{\omega_i}({\bf x}_j) = 0$ se ${\bf x}_j \notin \omega_i$. Por isso, para implementar a diferença local da equação 5.4, pode ser empregado um algoritmo praticamente idêntico ao algoritmo DIFERENÇALOCAL (vide seção 3.4.5). A diferença é que o número de padrões que pode ser incluído em uma bola $B({\bf x}, \tau)$ pode ser maior, pois é possível ocorrerem casos em que, em uma mesma bola, haja padrões de mais de duas classes.

Supondo novamente que cada classe possui $\vert T\vert/c$ padrões de treinamento, temos que há um total de $\forall {\bf x}_j \notin \omega_i$ padrões no espaço de características. Com isso, a complexidade desse algoritmo é da ordem de:

$$O((c \cdot \vert T\vert/c)^2) + O(c \cdot \vert T\vert/c) \cdot O(b^2) =$$ (5.6)

$$O(\vert T\vert^2) + O(\vert T\vert) \cdot O(b^2)$$ (5.7)

o que significa uma vantagem em relação à função da equação 5.1 para problemas com um número de classes $c$ grande.

Assim, no melhor caso, ou seja, quando cada bola contiver apenas elementos de até duas classes diferentes, a complexidade dessa função critério será de $O(\vert T\vert^2)$. No entanto, no pior caso, quando todas as bolas utilizadas no cálculo da diferença local englobam padrões de todas as classes existentes no espaço de características, a complexidade da função critério da equação 5.5 será de:

$$O((c \cdot \vert T\vert/c)^2) + O(c \cdot \vert T\vert/c) \cdot O((c \cdot \vert T\vert/c)^2) =$$ (5.8)

$$O(\vert T\vert^3)$$ (5.9)

Portanto, no pior caso esse algoritmo não apresenta, vantagens sobre a função da equação 5.1. Porém, é importante ressalvar que se pode deduzir que o caso médio (com uma bola de tamanho próximo do ideal) da função critério da equação 5.5 certamente será mais rápido que o da função da equação 5.1.

Considerando que todas as classes possuem distribuições aproximadamente isotrópicas, pode-se verificar que a função $f_p^{\tau} (\nu_{\omega_1}, \nu_{\omega_2}, \cdots, \nu_{\omega_c})$ (com a diferença local da equação 5.4) possui propriedades semelhantes a todas as que foram descritas na seção 3.4.6. Os mesmos efeitos que ocorrem na diferença $d_{\bf x}^{\tau}$ e na distância $d_p^{\tau} (\nu_{\omega_i}, \nu_{\omega_j})$ em relação à compacidade, distância entre os protótipos e tamanho da bola são esperados para a diferença local $f_{\bf x}^{\tau}$ para a função $f_p^{\tau} (\nu_{\omega_1}, \nu_{\omega_2}, \cdots, \nu_{\omega_c})$. Obviamente, deve-se considerar que há vários protótipos e várias classes de padrões (ao invés de 2), e que todas as classes possuem o comportamento mencionado. Pode-se mostrar que todas prováveis relações entre os resultados de $d_p^{\tau} (\nu_{\omega_i}, \nu_{\omega_j})$ para as possibilidades mostradas na página também são válidas para $f_p^{\tau} (\nu_{\omega_1}, \nu_{\omega_2}, \cdots, \nu_{\omega_c})$. Obviamente, devemos lembrar que aquelas relações ocorrem com 2 classes. A generalização dessas propriedades para $c$ classes é válida para a função $f_p^{\tau} (\nu_{\omega_1}, \nu_{\omega_2}, \cdots, \nu_{\omega_c})$. Por exemplo, os casos 3.(a) e 3.(b) ocorrem na função $f_p^{\tau} (\nu_{\omega_1}, \nu_{\omega_2}, \cdots, \nu_{\omega_c})$ quanto algumas classes possuem compacidade grande e outras possuem compacidade pequena.