Temporais TD(λ) de Sutton [39] ´e detalhado, posteriormente, na se¸c˜ao 6.3.2, em que o mesmo ´e usado para reajuste dos pesos da rede neural jogadora do presente trabalho.
2.3
Clusteriza¸c˜ao
Clusteriza¸c˜ao ´e a divis˜ao de dados com base na similaridade existente entre eles formando agrupa- mentos ou clusters [40]. Isso significa que os dados pertencentes a um determinado cluster possuem mais caracter´ısticas em comum se comparados com os dados pertencentes a outro cluster.
A Figura 2.3 mostra um conjunto de dados antes da clusteriza¸c˜ao (Figura 2.3(a)) e maneiras diferentes de separa-los em grupos, onde cada cor corresponde a um grupo: na Figura 2.3(b) os dados s˜ao separados em dois clusters; na Figura 2.3(c) em trˆes clusters e na Figura 2.3(d) em cinco clusters [41].
Figura 2.3: Clusteriza¸c˜ao de um conjunto de dados (a) dados originais; (b) divis˜ao em dois clusters; (c) divis˜ao em trˆes clusters e (d) divis˜ao em cinco clusters. Cada cluster ´e representado
por uma cor diferente
´
E comum existir certa confus˜ao na defini¸c˜ao do conceito de clusteriza¸c˜ao definindo-o como clas- sifica¸c˜ao de dados. No entanto, clusterizar n˜ao ´e o mesmo que classificar dados. A principal diferen¸ca consiste no fato de que, no processo de classifica¸c˜ao, os dados devem ser distribu´ıdos a grupos previamente conhecidos, enquanto que no processo de clusteriza¸c˜ao dever´a ocorrer a “descoberta” desses grupos. Por esse motivo, o ato de clusterizar (agrupar dados) pode ser de- finido como um problema de aprendizado n˜ao supervisionado, j´a que a estrutura dos dados e as propriedades que os tornam similares s˜ao desconhecidas [20].
Como n˜ao h´a r´otulos iniciais, o objetivo da clusteriza¸c˜ao ´e encontrar uma organiza¸c˜ao v´alida e conveniente dos dados, ao inv´es de separa-los em categorias como acontece no reconhecimento de padr˜oes e na classifica¸c˜ao de dados [40].
O processo de clusteriza¸c˜ao ´e dividido em 4 etapas. Tais etapas s˜ao ilustradas na figura 2.4. Na sequˆencia s˜ao apresentadas as etapas que comp˜oem o processo de clusteriza¸c˜ao.
Figura 2.4: Etapas do processo de clusteriza¸c˜ao
Sele¸c˜ao de vari´aveis: esta etapa tamb´em pode ser denominada como pr´e-processamento, visto que consiste da identifica¸c˜ao de vari´aveis ou atributos com alto grau de relevˆancia extra´ıdos do conjunto de dados inicial;
Medidas de similaridade entre dados: para a quantifica¸c˜ao da proximidade de dois dados, ´e necess´ario adotar alguma medida de similaridade entre eles. Existem diversas maneiras de quantificar a similaridade, entre pares de dados, sendo que a escolha da medida de similaridade adequada ´e fundamental para o sucesso do processo de clusteriza¸c˜ao de dados. Maiores detalhes sobre medidas de similaridades ser˜ao apresentados na se¸c˜ao 2.3.1;
Algoritmos de clusteriza¸c˜ao: nessa etapa define-se o modo de agrupamento dos dados, que pode ser realizado de diferentes maneiras. Os algoritmos de clusteriza¸c˜ao classificam-se de acordo com as diferentes t´ecnicas empregadas por eles no agrupamento dos dados. Al- guns dos mais famosos algoritmos de clusteriza¸c˜ao ser˜ao apresentados na se¸c˜ao de t´ecnicas de clusteriza¸c˜ao (se¸c˜ao 2.3.2). Nessa se¸c˜ao, apresentar-se-´a tamb´em, brevemente, a rede Kohonem-SOM utilizada, neste trabalho, na fase de clusteriza¸c˜ao dos estados de tabuleiros de final de jogo;
Valida¸c˜ao e avalia¸c˜ao dos resultados: nessa etapa a qualidade dos clusters encontrados ´e ava- liada, j´a que s˜ao desconhecidos inicialmente. Essa valida¸c˜ao pode ser feita com base em ´ındices estat´ısticos ou atrav´es da compara¸c˜ao com outros algoritmos. Al´em disso, a an´alise dos resultados pode levar `a redefini¸c˜ao dos atributos escolhidos e/ou da medida de similari- dade, definidos nas etapas anteriores.
As quatro etapas apresentadas s˜ao essenciais para o sucesso do processo de clusteriza¸c˜ao, ou seja, para a obten¸c˜ao de bons conjuntos de dados. Todavia, as etapas de medida de similaridade e algoritmos de clusteriza¸c˜ao merecem aten¸c˜ao especial, visto que a qualidade dos clusters depende muito da boa execu¸c˜ao destas etapas. Assim sendo, estas etapas ser˜ao detalhadas nas subse¸c˜oes a seguir.
2.3.1 Medidas de Similaridade
Muitos m´etodos de clusteriza¸c˜ao utilizam, como ponto de partida, uma matriz que reflete, de ma- neira quantitativa, a proximidade entre os elementos de um conjunto de dados. Essa proximidade pode representar a distˆancia ou similaridade entre dois elementos. Quanto maior a similaridade,
2.3. Clusteriza¸c˜ao 15 ou menor a distˆancia entre dois elementos, mais pr´oximos esses elementos se encontram [42]. Essa matriz recebe o nome de matriz de similaridade ou vetor de proximidade [41], [43].
As medidas de similaridade variam de acordo com a representa¸c˜ao e escala dos atributos dos dados. Um atributo pode ter representa¸c˜ao bin´aria, discreta ou cont´ınua. A escala indica o grau de importˆancia de um atributo em rela¸c˜ao aos demais. Por exemplo, um atributo pode indicar a porcentagem de aceita¸c˜ao de um produto no mercado (onde o valor do atributo varia de 0 a 100) ou indicar o peso de uma determinada caracter´ıstica em um tabuleiro de Damas (se¸c˜ao 2.10.2), onde o valor absoluto do atributo ´e relevante. A matriz de similaridade relaciona a proximidade entre dados do conjunto inicial.
Uma maneira de medir a similaridade entre atributos ´e atrav´es do c´alculo da distˆancia entre eles. A proximidade entre dois dados xi e xj ´e denotada por d(xi, xj). A distˆancia mais utilizada no
c´alculo de similaridade entre dois dados ´e a distˆancia de Minkowski mostrada na Equa¸c˜ao 2.1, onde d ´e o n´umero de atributos do dado:
d (xi, xj) = P v u u t d X k=1 (|xik− xjk|)2, p ≥ 1 (2.1)
A distˆancia de Minkowski apresenta algumas varia¸c˜oes. A mais conhecida delas ´e a distˆancia Euclidiana que ´e formada quando p=2, conforme Equa¸c˜ao 2.2.
d (xi, xj) = v u u t d X k=1 (|xik− xjk|)2 (2.2)
Outras varia¸c˜oes da distˆancia de Minkowski s˜ao a distˆancia de Manhattan, quando p=1, e a distˆancia sup, quando p→ ∞, apresentadas nas Equa¸c˜oes 2.3 e 2.4, respectivamente.
d (xi, xj) = d X k=1 (|xik− xjk|)2 (2.3) d (xi, xj) = max 1≤k≤d|xik− xjk| (2.4)
A escolha da m´etrica a ser utilizada no processo de clusteriza¸c˜ao deve considerar os tipos de dados que ser˜ao agrupados. A varia¸c˜ao do parˆametro p define distˆancias diferentes, como pode ser observado nas Equa¸c˜oes 2.1, 2.2, 2.3 e 2.4.
Este trabalho adota a distˆancia Euclidiana para o c´alculo de medida de proximidade entre os dados que ser˜ao agrupados (clusterizados), conforme ser´a mostrado na se¸c˜ao 5.3
2.3.2 T´ecnicas de Clusteriza¸c˜ao
Na se¸c˜ao 2.3.1 relacionaram-se algumas medidas para quantificar a similaridade entre dados. O vetor de similaridade que representa essa proximidade ´e a entrada para os algoritmos de clus- teriza¸c˜ao. Os algoritmos utilizados no processo de clusteriza¸c˜ao de dados podem ser classifica- dos, por exemplo, de acordo com a abordagem utilizada na defini¸c˜ao de clusters. Neste caso, classificam-se de acordo com 3 t´ecnicas: particionamento; densidade e algoritmos hier´arquicos; e redes auto-organiz´aveis. As caracter´ısticas desses algoritmos s˜ao apresentadas, brevemente, nas subse¸c˜oes a seguir, dando destaque aos algoritmos de clusteriza¸c˜ao por redes auto-organiz´aveis, que foram utilizadas neste trabalho.
2.3.2.1 Algoritmos de clusteriza¸c˜ao por particionamento
Na clusteriza¸c˜ao por particionamento, o conjunto de dados ´e dividido em um n´umero determinado de clusters uma ´unica vez. O fato de gerar a parti¸c˜ao uma ´unica vez passa a ser uma vantagem, quando a quantidade de dados ´e muito grande e a constru¸c˜ao e armazenamento de todas as possibilidades de divis˜ao resultantes da clusteriza¸c˜ao hier´arquica tornam-se muito custosas [41]. O problema de clusteriza¸c˜ao por particionamento pode ser definido formalmente como: dado um conjunto de n dados caracterizados por d atributos cada, determine uma parti¸c˜ao do conjunto inicial de K clusters. A escolha do valor de K depende do problema abordado e pode interferir na eficiˆencia do algoritmo. O objetivo ´e maximizar a similaridade entre os elementos de um mesmo cluster e minimizar a similaridade entre elementos de clusters diferentes [40].
2.3.2.2 Algoritmos de clusteriza¸c˜ao hier´arquica
Nessa abordagem, s˜ao produzidas diversas parti¸c˜oes do conjunto de dados com base na jun¸c˜ao ou divis˜ao de clusters de acordo com a medida de similaridade. Conforme o modo de produ¸c˜ao das parti¸c˜oes, os m´etodos de clusteriza¸c˜ao hier´arquicos podem ser classificados em aglomerativos ou divis´orios [41].
Em algoritmos aglomerativos, no passo inicial, cada elemento do banco de dados forma um cluster. Nas pr´oximas itera¸c˜oes, pares de clusters da itera¸c˜ao precedente que satisfazem um certo crit´erio da distˆancia m´ınima s˜ao aglutinadas em um ´unico cluster. O processo termina quando um n´umero de clusters k fornecido pelo usu´ario ´e atingido [42].
Em algoritmos divis´orios, no passo inicial, cria-se um ´unico cluster composto pelo banco de dados inteiro. Nas pr´oximas itera¸c˜oes, os clusters s˜ao subdivididos em duas partes de acordo com algum crit´erio de similaridade. O processo termina quando se atinge um n´umero de clusters k fornecido pelo usu´ario [42].
2.4. Redes Neurais Artificiais 17