Considerar indiscriminadamente a influência de todos os exemplos identificados, como os vizinhos mais próximos, pode induzir em erro. Um processo de contornar esta limitação do método dos vizinhos mais próximos, consiste na discriminação positiva dos exemplos que estão mais próximos. O algoritmo pode ser descrito da seguinte forma:
K-NearestNeighborWheigh(x, DDDD)
Sejam {z , ..., z1 K }YD, os k-vizinhos mais próximos de x.
Retorna ( ) ( ) ( ( )) K i v C i 1 i 1 ˆc x arg max v,c S x, δ ∈ = =
∑
z zTendo em conta que o método pondera a distância dos exemplos ao caso em análise, passa a ser possível eliminar a definição da vizinhança, i. e., podem assim ser considerados na determinação da classificação a estimar, todos os exemplos presentes no conjunto de treino, uma vez que a influência dos exemplos é ponderada em função da distância à observação em análise. O método passa, então, a ser considerado como um método global.
Considerações finais
O método dos vizinhos mais próximos é pouco estável, sendo fortemente dependente da posição relativa dos exemplos presentes, no conjunto de desenho. A posição dos vizinhos presentes num subespaço é determinante e pequenas alterações podem conduzir a
alterações significativas nos resultados finais, o que conduz à existência de uma grande variação de desempenho, dependendo do conjunto de desenho utilizado [70].
A existência de um vasto conjunto de desenho pode parecer suficiente para assegurar a aplicação teórica óptima do método dos k-vizinhos, por viabilizar um amplo conjunto de vizinhos próximos da observação a classificar, permitindo determinar correctamente a classificação a atribuir. Todavia, a intuição é traída pelo aumento da dimensionalidade, que conduz ao crescimento exponencial do hipercubo, facto que foi apelidado pela maldição da dimensionalidade [71]. Tendo em conta que o método dos vizinhos mais próximos pode ser visto como um processo de mapeamento do conjunto de entrada para o conjunto de saída, fazer a cobertura do espaço de entrada ocupa recursos proporcionais à dimensão do hipercubo que descreve o espaço de representação. A manutenção da distância média entre exemplos obriga ao seu crescimento exponencial em função do acréscimo da dimensionalidade. Partindo do princípio que o número de exemplos é estável, ao aumento do hipercubo corresponde: i) a dispersão dos exemplos; ii) a representação de zonas de espaço irrelevantes, tendo em conta que estão vazias. Concluindo, aumentar o número de exemplos não contribui, necessariamente, para preencher as porções vazias de hiperespaço, que são, muito provavelmente, definidos por características irrelevantes e que não contribuem para a melhor definição do problema. A solução nestes passa pela redução da dimensionalidade com a realização de uma melhor escolha das características que fazem parte do vector de representação.
2.2.4.6 Árvores de Decisão
Os algoritmos mais conhecidos para a indução de árvores de decisão, têm por base o ID3 e o C4.5. Formalmente, uma árvore de decisão é um grafo acíclico, em que cada nó, ou constitui um nó de decisão, com dois ou mais sucessores, ou é um nó folha. O nó de decisão possui um método de selecção baseado nos valores de um atributo, que permite navegar na árvore até se atingir um nó folha, ao qual está atribuída uma classificação. Genericamente, o modelo é induzido por aproximação à função-objectivo, utilizando, para tal, funções em formato de árvore de decisão. Este método pode ser considerado como um método de pesquisa no espaço de hipóteses de todas as árvores passíveis de serem construídas com o conjunto de atributos. A estratégia seguida por esta categoria de métodos baseia-se no princípio da divisão e conquista, caracterizando-se pela abordagem recursiva de um problema complexo através da sua divisão em problemas mais simples.
A eficácia do algoritmo está fortemente relacionada com o processo de selecção dos atributos, sendo diversos os métodos propostos com vista à resolução deste problema. De uma forma geral, há concordância nos casos-limite: inutilidade de atributos que mantêm as
partições, em que apenas estão presentes exemplos de uma classe. A diferença reside nos casos intermédios. Os algoritmos mais utilizados são o ID3 [72] e C4.5 [73] que implementam métodos de pesquisa sobre todo o espaço. O ID3 e o C4.5 utilizam o conceito de entropia, que enfatiza a selecção dos atributos, baseada na pureza das partições [65]. O processo de pesquisa das hipóteses materializa-se a partir de árvores simples para complexas, utilizando uma estratégia trepa-colina23 no espaço de hipóteses. A estratégia trepa-colina, aliada à inexistência de processos de «backtracking», conduz à identificação de soluções óptimas locais, mas compromete a determinação de soluções óptimas globais. Os métodos são particularmente robustos no que respeita à existência de ruído no conjunto de desenho, mas apresentam um desvio indutivo, para árvores de pequena dimensão e para árvores que possuam os atributos de maior ganho de informação, perto da raiz.
As ideias-base, que suportam o algoritmo ID3, são:
• a árvore de decisão – Numa árvore de decisão, a cada nó corresponde um atributo e, a cada arco, um valor possível do atributo. As folhas da árvore especificam a classificação a atribuir a uma observação que seja descrita pelo percurso efectuado até si, desde a raiz da árvore;
• a selecção de atributos – A cada nó da árvore de decisão deve ser associado o atributo mais discriminante dentre os que não foram seleccionados para o percurso;
• a medida Entropia, introduzida por Claude Shannon [74], é a medida utilizada para efectuar a selecção dos atributos mais discriminantes.
O C4.5 extende as capacidades do ID3, entre outras, permitindo:
• a manipulação de atributos sem valores, permitindo: i) na construção da árvore, o cálculo do ganho da informação, utilizando somente as observações que possuem valores, ou pela atribuição do valor mais comum; e ii) no processo de decisão pela associação de probabilidades às estimativas possíveis;
• a manipulação de atributos contínuos, pela partição do atributo, num conjunto discreto de intervalos;
• a ponderação do custo do atributo, através da normalização do valor do ganho de informação, pelo valor estimado para o custo do atributo;
• a realização da poda das árvores de decisão.
Nos dois casos, a determinação do ganho de informação é, assim, fundamental para realizar a selecção dos atributos. Para tal, é necessário assumir que as N observações do conjunto D são equiprováveis, logo que a probabilidade de ocorrência de cada uma é de pm = 1N ,
sendo a informação transmitida por cada observação de −log ( p)2 =log ( n )2 , (e. g., no caso de existirem 8 observações, log ( 8 )2 =3). Por outras palavras são necessários três bits para identificar cada observação. Genericamente, sendo P =( p , p , ..., p )1 2 N uma distribuição probabilística, então, a transmissão de informação associada a esta distribuição, apelidada de «Entropia de P» é descrita por:
1 2 1 2 2 2 N 2 N
Info( D ) =E( P ) = −p log ( p ) −p log ( p ) −...−p log ( p )24 (35) O particionamento do conjunto de exemplos D em k classes, induz a que informação necessária para identificar um elemento de D seja Info( D ) =E( P ) , em que P é a distribuição de probabilidades da partição ( C ,C , ...C ) . 1 2 N
Todavia, o cálculo da informação necessária para identificar um exemplo, (caso o conjunto D tenha sido particionado em R subconjuntos, pela utilização do atributo A ), passa a ser uma i média ponderada do valor necessário para cada partição, por outras palavras:
R i i i i 1 D Info( A , D ) Info( D ) D = =
∑
. (36)A diferença entre a equação (35) e a equação (36) representa o ganho de informação obtido pelo conhecimento do atributo A , i. e., o facto de se conhecer o valor do atributo altera o i valor da Entropia, conduzindo a um novo estado de conhecimento sobre o exemplo em análise, sendo assim:
i i
GI( A ,T ) =E( T ) −E( A ,T ) (37)
O ganho de informação, associado a cada atributo, pode ser utilizado na construção de árvores de decisão, onde, para cada nó, é seleccionado o atributo que fornece maior ganho de informação, desde que ainda não esteja presente nesse caminho, desde a raiz da árvore. O anexo A.1 apresenta em maior detalhe alguns dos conceitos base essenciais ao domínio desta temática.