Um Estudo sobre Técnicas de Aprendizado de Máquina aplicadas à

Anais do VI Simpósio de Informática da Região Centro do RS - SIRC/RS 2007 - ISBN 978-85-88667-76-1
Santa Maria - RS, outubro de 2007.
Um Estudo sobre Técnicas de Aprendizado de Máquina
aplicadas à Mineração de Dados
Maicon de Brito do Amarante1, Denise Regina Pechmann1
1
Departamento de Engenharias e Ciência da Computação – Universidade Regional
Integrada do Alto Uruguai e das Missões (URI) – Campus Santiago – RS – Brasil
{maicon,deniserp}@urisantiago.br
Abstract. This paper presents a comparative study between the application of
Artificial Neural Networks and the k-Means algorithm, for Data Mining. Such
machine learning techniques are used as tools for data classification and
clustering. The database used treats on a psychological experiment that
analyses the human behavior based in a scale.
Resumo. Este artigo apresenta um estudo comparativo entre a aplicação de
Redes Neurais Artificiais (RNAs) e o algoritmo de clusterização k-Means,
para a Mineração de Dados. Tais técnicas de aprendizado de máquina são
utilizadas, neste trabalho, como ferramentas para a classificação e
clusterização de dados de um experimento psicológico que analisa o
comportamento do ser humano baseado em uma escala.
1. Introdução
A abrangência e o volume dos dados produzidos nos ramos científico-econômico vêm
crescendo de tal maneira que a tarefa de extração de informações úteis torna-se cada vez
mais complexa. Especialistas e sistemas inteligentes dependem destas informações para
que lhes sirvam de suporte à tomada de decisões. As abordagens triviais de obtenção do
conhecimento demonstram-se ineficientes ou impraticáveis, por isso mostra-se
necessária a aplicação de técnicas de aprendizado de máquina que tornem esta tarefa
factível.
A Mineração de Dados é uma das etapas do processo de descoberta de
conhecimento em grandes bases de dados, que permite, ao usuário, inferir informações
úteis a partir dos dados extraídos. Partindo deste contexto, neste trabalho, investiga-se a
aplicação de RNAs e do algoritmo de clusterização k-Means para Mineração de Dados.
A base de dados utilizada foi criada por Klahr e Siegler (1978) a partir de experimentos
sobre a análise do comportamento humano baseado no movimento de uma régua.
Alguns trabalhos relacionados com técnicas de classificação utilizando estes dados
podem ser encontrados em [Noreen 2004] e [Stefano 2004].
Na seção 2 descreve-se a mineração de dados, suas etapas e tarefas, juntamente
com as técnicas de aprendizado de máquina utilizadas nesta investigação. Na seção 3,
serão detalhados os experimentos realizados, iniciando pela preparação da base de
dados, a aplicação dos algoritmos de classificação e clusterização utilizados, até a
análise dos seus resultados. Finalizando, a seção 4 apresenta uma discussão sobre os
resultados obtidos com cada um dos métodos aplicados.
Anais do VI Simpósio de Informática da Região Centro do RS - SIRC/RS 2007 - ISBN 978-85-88667-76-1
Santa Maria - RS, outubro de 2007.
2. Mineração de Dados
A grande variedade de dados coletados e armazenados em um ritmo cada vez mais
acelerado, tem demonstrado a necessidade do surgimento de uma nova geração de
teorias da computação, bem como de ferramentas que auxiliem os seres humanos a
extraírem informações úteis deste crescente volume de dados [Fayyad et al. 1997].
Considerando uma empresa qualquer, esses dados expressariam desde pedidos de
compras até acessos à loja virtual. Dados que aparentemente sem sentido, podem dar
origem a informações que auxiliam na tomada de decisões e gerenciamento das
atividades desta empresa [Zaiane 2000].
Segundo Fayyad et al. (1996), a Mineração de Dados é o processo de
identificação de padrões válidos, novos, potencialmente úteis e compreensíveis,
embutidos nos dados. Sendo estes padrões definidos como modelos extraídos dos dados,
determinados por um número de características comuns a eles [Symeonidis e Mitkas
2005].
O processo de descoberta de conhecimento em bases de dados pode ser descrito
através de três etapas: o pré-processamento, a Mineração de Dados (ou extração de
padrões) e o pós-processamento.
O pré-processamento é fundamental, pois normalmente os dados disponíveis não
se encontram na forma adequada para extração do conhecimento. Esta etapa envolve as
tarefas de: extração e integração de dados em formatos heterogêneos; transformação
para um formato legível ao algoritmo de extração de padrões; limpeza dos dados
coletados, evitando informações mal formadas ou fora de intervalos aceitáveis e,
finalmente, a redução dos dados, melhor aproveitando os limitados recursos
computacionais [Rezende 2003].
A etapa de Mineração de Dados é bastante complexa, pois é responsável por
encontrar padrões e regularidades nos dados. Ela apresenta-se como um conjunto de
técnicas e ferramentas inteligentes, capazes de cooperar na exploração dos dados. Entre
algumas das técnicas pode-se citar: redes neurais, indução de regras e árvores de
decisão.
Esta é uma etapa iterativa, direcionada ao cumprimento dos objetivos definidos
na identificação do problema. Nesta etapa é realizada a escolha, a configuração e a
execução de um ou mais algoritmos de extração do conhecimento. Uma tarefa é
escolhida de acordo com os objetivos desejáveis para a solução a ser encontrada,
podendo estar agrupada em atividades preditivas ou descritivas. A predição consiste na
generalização de exemplos (classificação, regressão), enquanto a descrição consiste na
identificação de comportamentos intrínsecos do conjunto de dados, sem possuírem
classes específicas (clusterização, regras de associação, etc.) Por fim, um algoritmo é
escolhido para realizar a extração de padrões (RNA, árvores de decisão, redes
bayesianas,...) [Rezende 2003] [Fayyad et al. 1997].
Finalmente, a etapa de pós-processamento visa propiciar que o conhecimento
extraído possa ser utilizado na resolução de problemas reais [Rezende 2003].
A classificação ou reconhecimento de padrões em RNAs é definida por [Haykin
2001] como o processo pelo qual um padrão recebido é atribuído a uma classe dentre
um número pré-determinado de classes (categorias). Uma rede neural realiza o
Anais do VI Simpósio de Informática da Região Centro do RS - SIRC/RS 2007 - ISBN 978-85-88667-76-1
Santa Maria - RS, outubro de 2007.
reconhecimento de padrões passando inicialmente por uma seção de treinamento,
durante a qual se apresenta repetidamente à rede um conjunto de padrões de entrada
junto com a categoria a qual cada padrão pertence. Posteriormente, novos padrões
inéditos, mas pertencente à mesma população de padrões, são apresentados à rede
treinada, para que esta realize a classificação.
A clusterização é um processo de agrupamento de objetos físicos ou abstratos
em classes similares. É realizada a identificação dos grupos ou clusters de acordo com
alguma medida de distância, como a distância Euclidiana. Os clusters surgem de
agrupamentos de dados que se encontram próximos em um determinado espaço [Chen
et al. 1996]. Geralmente a clusterização procura dividir uma base de dados em pequenas
bases uniformes, para melhor compreender o espaço de dados, simplificando a análise
[Kaufman e Rousseeuw 1990]. A clusterização pode ser realizada através de algoritmos
de particionamento, sendo o k-Means um algoritmo bastante representativo dentre eles
[Symeonidis e Mitkas 2005].
3. Experimentos
Objetivando a identificação de padrões nos dados analisados, os experimentos
realizados neste trabalho utilizam duas técnicas de aprendizado de máquina amplamente
aplicadas à Mineração de Dados: as RNAs e o algoritmo k-Means. As RNAs são
aplicadas para a tarefa de classificação e o algoritmo k-Means para a tarefa de
clusterização. A escolha destas duas técnicas deve-se à possibilidade de análise e
comparação entre dois tipos de aprendizado, o supervisionado e o não supervisionado.
Desta forma, para a aplicação de ambas as técnicas utilizou-se o mesmo conjunto de
dados, sempre considerando suas peculiaridades, quando da preparação da base de
treinamento.
O conjunto de dados desta investigação foi originalmente gerado para modelar o
resultado de um experimento psicológico, que analisa o comportamento humano
baseado na predição do movimento de uma régua [Klahr e Siegler 1978]. Cada padrão
desta base de dados possui quatro dados de entrada (peso à esquerda e distância à
esquerda, peso à direita e distância à direita) e a classe a qual pertence. As classes
representam o tipo de movimento da régua: se à esquerda, à direita ou balanceado. A
base conta com 625 casos distribuídos entre as 3 classes, como mostra a Tabela 1.
Tabela 1 — Distribuição dos padrões da base de dados de acordo com as
classes.
Classe
Número de padrões
Balanceada
49
Esquerda
288
Direita
288
3.1. Preparação da Base de Treinamento
Para a realização do treinamento com ambas as técnicas, foi realizada uma divisão da
base de dados disponível em base de treinamento e base de validação. A base para
Anais do VI Simpósio de Informática da Região Centro do RS - SIRC/RS 2007 - ISBN 978-85-88667-76-1
Santa Maria - RS, outubro de 2007.
treinamento corresponde a 70% dos dados, selecionados de forma aleatória. Já a de
validação corresponde aos 30% restantes. A separação dos dados entre as bases, foi
executada através de um programa feito em C, que realizava a seleção aleatória dos
padrões cuidando para manter a proporcionalidade da distribuição das classes, ou seja,
cada classe possuía 70% dos seus padrões representados para treinamento e 30% para
validação.
Para a tarefa de classificação, devido a representação das classes ser alfabética
(L = esquerda, R = direita, B = balanceado), houve a necessidade de representá-las
numericamente, optando pelo formato binário dos equivalentes decimais 1, 2 e 3, que
correspondem à esquerda, à direita e balanceado.
3.2. Classificação
Para a tarefa de classificação buscou-se obter resultados satisfatórios através do
treinamento e validação de Redes Neurais do tipo MLP (Multi-Layer Perceptron),
utilizando o algoritmo backpropagation. O software JavaNNS [Zell et al. 2007] foi
usado como ferramenta para geração e treinamento das RNAs.
No treinamento das RNAs foram empregadas diferentes topologias para
encontrar a configuração ideal. Todas as topologias escolhidas para o treinamento
possuíam 4 neurônios na camada de entrada e 3 neurônios na camada de saída,
representando, respectivamente, o número de dados de entrada da base utilizada e o
número de classes. Variou-se o número de neurônios na camada oculta, entre 1 e 15
neurônios, a fim de determinar a topologia mais adequada ao experimentos. Para cada
topologia ttreinada, foram submetidas 5 inicializações diferentes.
A seleção do número de ciclos para treinamento, foi realizada através de várias
rodadas de treinamento, até que se identificasse um número médio de ciclos onde o erro
se tornava estável. Com base nestes treinamentos, o número de ciclos escolhido para ser
utilizado nos experimentos foi de 2.000 ciclos.
A primeira topologia de RNA utilizada para o treinamento (4-1-3), possuía
apenas 1 neurônio na camada oculta, obtendo um valor de erro consideravelmente alto,
que não permitiria uma classificação correta. Com 2 neurônios na camada oculta,
também obteve-se um desempenho próximo a topologia anterior. A partir da topologia
com 10 neurônios na camada oculta, foram obtidos resultados aceitáveis. O desempenho
médio da topologia com 15 neurônios para as diferentes inicializações, foi superior a
média alcançada pela topologia com 10 neurônios. Entretanto, na primeira tentativa
com 10 neurônios, obtivemos um erro médio quadrático (Mean Squared Error - MSE)
de aproximadamente 0,0064, resultado não igualado pela topologia de média superior.
A Tabela 2 exibe a média dos erros MSE obtidos por topologia treinada. Cada topologia
é denominada pelo número de neurônios da camada de entrada (4), da camada oculta (1,
2, 5, 10, 15) e de saída (3), respectivamente.
Tabela 2 — Média dos erros para 5 treinamentos de cada topologia.
Topologia
4-1-3
4-2-3
4-5-3
4-10-3
Média dos erros
0,1836
0,1295
0,0790
0,0231
Anais do VI Simpósio de Informática da Região Centro do RS - SIRC/RS 2007 - ISBN 978-85-88667-76-1
Santa Maria - RS, outubro de 2007.
4-15-3
0,0080
A validação das redes obtidas na etapa de treinamento, com o menor valor de
erro, foi realizada através da utilização das redes treinadas, em um programa que
simulava a classificação dos dados contidos na base de validação. Utilizando o
aplicativo snns2c disponibilizado com o pacote SNNS, transformou-se cada uma das
redes numa biblioteca da linguagem C, que pode ser utilizada juntamente com o
programa para classificação.
Como foi citado anteriormente, apesar da média de acertos da rede com
topologia 4-15-3 ter sido melhor que a da topologia 4-10-3, o resultado obtido na
primeira inicialização da configuração 4-10-3 foi superior às redes de topologia maior.
Os resultados da validação para as melhores redes, treinadas com 10 e 15 neurônios
ocultos, podem ser observados nas Tabelas 3 e 4, na forma de matriz de confusão.
Nestas tabelas, as linhas correspondem às saídas desejadas, ou seja, a classe à qual
pertence o padrão apresentado, e as colunas representam a classificação resultante da
utilização da RNA treinada. Através desta matriz podemos visualizar os erros
precisamente onde eles ocorreram, sendo que qualquer valor fora da diagonal principal
simboliza um erro obtido.
Tabela 3 — Matriz de confusão para melhor rede obtida, de topologia 4-10-3.
Saída Desejada
Classe1 Classe2 Classe3
Saída
Obtida
Classe1
85
0
0
Classe2
0
15
1
Classe3
1
0
85
Tabela 4 — Matriz de confusão para uma rede de topologia 4-15-3.
Saída Desejada
Classe1 Classe2 Classe3
Saída
Obtida
Classe1
85
0
1
Classe2
0
13
0
Classe3
1
2
85
3.3. Clusterização
A clusterização com o algoritmo k-Means, foi realizada utilizando o software R [R
Development Core Team 2007]. Em primeiro lugar, a base de dados teve seu formato
adequado para a leitura do software R, apenas suprimindo as colunas que representavam
as classes, já que se trata de um método não supervisionado.
Anais do VI Simpósio de Informática da Região Centro do RS - SIRC/RS 2007 - ISBN 978-85-88667-76-1
Santa Maria - RS, outubro de 2007.
O k-Means foi aplicado à uma matriz contendo os dados do experimento.
Utilizou-se o número de classes existentes nos dados originais para representar o
número de centróides esperados com a clusterização.
Os experimentos realizados com o algoritmo de clusterização apresentaram
número de padrões divididos entre os clusters bastante diferente dos resultados
encontrados na classificação. Um dos resultados obtidos para a clusterização apresentou
os três clusters contendo 168, 135 e 135 padrões, sendo seus centróides determinados
pelos valores da Tabela 5.
Tabela 5 — Valores dos centróides para os 3 clusters, utilizando as 4 variáveis
de entrada.
Cluster 1
Cluster 2
Cluster 3
V1
1.959
2.820
4.350
V2
2.912
2.467
3.750
V3
1.959
4.347
2.578
V4
2.709
3.413
2.936
Uma forma de visualizar o resultado obtido com a clusterização é apresentada na
Figura 1. Observa-se, através de gráficos, os clusters formados com a aplicação do
algoritmo e os centróides calculados para os 3 clusters. O conjunto de gráficos mostrado
à esquerda da figura apresenta o resultado da clusterização, diferenciando cada um dos
clusters através de cores (vermelho, verde e preto), e utilizando a combinação dos 4
atributos de entrada da base de dados para os eixos dos gráficos (V1, V2, V3 e V4).
O gráfico à direita na Figura 1, mostra a melhor combinação de eixos para
visualizar a separação entre os clusters. São apresentados, também, os centróides
utilizados para descrever os clusters.
Figura 1 — A figura à esquerda apresenta o resultado gráfico da clusterização
dos dados da base de treinamento, utilizando 3 clusters com o algoritmo kMeans. À direita, são apresentados os 3 centróides identificados através da
Anais do VI Simpósio de Informática da Região Centro do RS - SIRC/RS 2007 - ISBN 978-85-88667-76-1
Santa Maria - RS, outubro de 2007.
clusterização (salientados na forma de quadrados). Para os eixos do gráfico
são utilizados dois atributos de entrada (V1 e V3).
Uma forma de verificar o resultado obtido com a clusterização é apresentada na
Tabela 6. Apresenta-se uma matriz de confusão comparando as quantidades de padrões
da base de treinamento por classe e por cluster. Assim, tenta-se associar cada uma das
classes a um dos clusters identificados. As linhas da tabela representam o número de
padrões de cada uma das três classes identificadas pela base de treinamento, e as
colunas representam o número de padrões associados aos clusters.
Tabela 6 — Matriz Classes Reais X Clusterização
Número de Padrões por Cluster
Cluster
1
Cluster
2
Cluster
3
Classe1
Número de Padrões
Classe2
por Classe
61
105
36
12
13
10
Classe3
95
17
89
Através da Tabela 6, percebe-se que a classe 1 possui maior número de padrões
no cluster 2 (105 padrões), a classe 2 também possui maior número de padrões no
cluster 2 e a classe 3 possui maior número de padrões no cluster 1. Desta forma, não foi
possível fazer uma associação entre os clusters encontrados e as classes representadas
pelos dados. Considerando que o algoritmo de clusterização k-Means tenta encontrar
similaridades entre os dados através de medidas de distância e que a base de dados
utilizada possuía pouca variação entre os valores de cada atributo, é compreensível que
qualquer tipo de associação, entre os resultados desta técnica e os obtidos com a
classificação usando RNAs, se torne bastante difícil.
4. Conclusão
A aplicação de técnicas eficientes para mineração de dados tende a se tornar cada vez
mais necessária, resultante do enorme volume de dados que são e continuarão sendo
produzidos. Tanto os métodos de aprendizado de máquina supervisionados quanto os
não supervisionados tem grande importância, cada um sendo aplicado em diferentes
situações, obtendo-se resultados que são improváveis através de técnicas comuns, não
inteligentes.
À medida que os sistemas inteligentes ganharem mais espaço, e certamente
ganharão, pois a cada dia o avanço da tecnologia dá provas disso, estas técnicas de
aprendizado tornar-se-ão ainda mais importantes, pois não serão apenas os especialistas
que utilizarão estas informações, serão os próprios sistemas, capazes de atuar sobre o
ambiente onde estarão inseridos.
Anais do VI Simpósio de Informática da Região Centro do RS - SIRC/RS 2007 - ISBN 978-85-88667-76-1
Santa Maria - RS, outubro de 2007.
Os experimentos relatados neste trabalho, possibilitaram um aprofundamento
maior na aplicação de técnicas de aprendizado de máquina para tarefas de mineração de
dados, em particular na utilização de RNAs e do algoritmo de clusterização k-Means.
Cada uma das técnicas obteve resultados bastante diferentes nos experimentos
realizados. Com as RNAs foi possível obter valores de erro bastante baixos e bons
resultados na classificação, tornando interessante a sua aplicação. Os resultados obtidos
com a clusterização não foram representativos para a aplicação escolhida, mas
contribuíram de forma positiva para a análise dos temas tratados e para a identificação
de futuros trabalhos na área.
Referências Bibliográficas
Chen, M., Han, J. and P. Yu. (1996) Data mining: An overview from database
perspective. IEEE Transactions on Knowledge and Data Eng., USA.
Fayyad, U., Piatetsky-Shapiro, G. and Smyth, P. (1996) “Knowledge discovery and data
mining: Towards a unifying framework”. In: Knowledge Discovery and Data
Mining, pages 82-88.
Fayyad, U., Piatetsky-Shapiro, G. and Smyth, P. (1997) “From Data Mining to
Knowledge Discovery in Databases”, In: Proceedings of the Fourteenth National
Conference on Artificial Intelligence, AAAI Press/ MIT Press books, USA.
Haykin, S. (2001) Redes Neurais: princípios e prática. 2.ed. Bookman, Porto Alegre.
Kaufman, L., Rousseeuw, P. J. (1990). Finding groups in data. Wiley, New York.
Klahr, D. e Siegler, R. S. (1978). The Representation of Children's Knowledge. In H.
W. Reese & L. P. Lipsitt (Eds.), Advances in Child Development and Behavior, pp.
61-116. Academic Press, New York.
Noreen, S., Sharkey, A. J. C. (2004). Evolving an Effective Ensemble. The University
Of Sheffield. Sheffield.
R Development Core Team (2007). R: A language and environment for statistical
computing. R Foundation for Statistical Computing, Vienna, Austria. ISBN 3900051-07-0, URL http://www.R-project.org.
Rezende, S. O. (2003). Sistemas Inteligentes - Fundamentos e Aplicações. 1.ed. Editoria
Manole Ltda, São Paulo.
Stefano, M. (2004). Aprendimento Autimatico. La Sapienza, Roma.
Symeonidis, A. L., Mitkas, A. P. (2005). In: Agent Intelligence Through Data Mining,
Springer, New York.
Zaiane, O. R. (2000). WEB Mining: Concepts, Practices and Research. In: Anais do
Simpósio Brasileiro de Banco de Dados, XV SBBD, João Pessoa. p. 410-474.
Zell, A., Mamier, G., Vogt, M., Mache, N., Huebner, R., Herrmann, K., Soyez, T.,
Schmalzl M., Sommer, T., Hatzigeorgiou, A., Doering, S., Posselt, D., Schreiner, T.
SNNS, Stuttgart Neural Network Simulator, User manual, Version 4.1. University of
Stuttgart, Comp. Science Dept., Report No. 6/95.