Algoritmo Plug-in LVQ para Servidor SQL - PDF
Algoritmo Plug-in LVQ para Servidor SQL
Download "Algoritmo Plug-in LVQ para Servidor SQL"
Eduarda Bárbara Candal de Almada
1 Algoritmo Plug-in LVQ para Servidor SQL Licínia Pedro Monteiro Dissertação para obtenção do Grau de Mestre em Engenharia Informática e de Computadores (MEIC) Júri Presidente: Prof.ª Doutora Ana Almeida e Paiva Orientador: Prof. Doutor Andreas Miroslaus Wichert Vogal: Prof. Doutor Diogo Ferreira Setembro 2008
2 Agradecimentos Foi possível concretizar este trabalho devido à ajuda de algumas pessoas que directa ou indirectamente para ele contribuíram, e às quais aqui agradeço. Em primeiro lugar, agradeço à pessoa que tornou este trabalho possível e que foi uma enorme ajuda durante todo o processo de execução, o Professor Andreas Wichert que com a sua boa vontade e espírito alegre, resolvia todos os pequenos problemas que iam surgindo e que me dava ânimo para continuar. A sua disponibilidade e paciência foram intermináveis e sem ele este trabalho não teria sido possível. Seguidamente gostaria de agradecer à minha família, pais e irmão, que sempre me apoiaram e foram muito compreensivos quanto ao tempo que não lhes dava atenção para dedicar a este trabalho. Obrigado pela compreensão e pelos sorrisos quando o trabalho não corria como gostava. Gostaria também de agradecer ao meu namorado, que leu este trabalho várias vezes e corrigiu alguns erros, que sem ele ainda hoje cá estariam. Agradeço-lhe a atenção demonstrada durante todas as noites que lhe falava deste trabalho, e sem ser a sua área, me tentava compreender. Obrigado pela paciência. Agradeço aos companheiros de gabinete onde a maioria deste trabalho foi implementado e escrito, foi bom ter alguém tão alegre e bem-disposto com quem partilhar os problemas e as pequenas conquistas. Obrigado a todos pela companhia e pelo vosso apoio. Gostaria de agradecer também a todos os meus amigos de quem estive um pouco mais afastada para fazer frente a este desafio, todos os poucos minutos passados com eles neste último ano foram revitalizantes e davam-me novas forças para continuar este projecto. Desculpem pela pouca atenção que vos dispensei, obrigado pela compreensão e pelo carinho. Por último, quero agradecer á pessoa que tornou este trabalho físico, dando-lhe vida para que o leitor possa folhear as suas páginas. Obrigada amiga, foste incansável quando imprimiste este trabalho em tempo recorde. 2
3 Resumo Este trabalho pretende descrever a nova funcionalidade desenvolvida no âmbito do Data Mining. Nos últimos anos esta área sofreu grandes modificações, e a mineração de dados é vista como uma área em expansão, muito importante em qualquer empresa, nomeadamente nas tarefas de classificação e previsão de dados. O objectivo deste projecto é implementar um novo algoritmo para realizar essas tarefas na ferramenta mais usada para as efectuar, o Microsoft SQL Server 2005 [16, 19]. Existem outras ferramentas utilizadas no mercado para Data Mining e integração de novos algoritmos, tais como as disponibilizadas pelo Oracle [11, 29] e SAS [7, 8]. Ambas as ferramentas apresentam alguns inconvenientes no que trata de integrar novos algoritmos. Como exemplo, o SAS oferece pouca informação no que respeita a esse tipo de desenvolvimento, o que iria tornar bastante difícil este trabalho. Além disso, visto que a ferramenta da Microsoft é a mais procurada pelas empresas e a mais utilizada, oferecendo alguma literatura e ajuda para a integração de novos algoritmos, revelou-se a escolha mais adequada para o desenvolvimento desta tese. Nesta ferramenta já são disponibilizados vários algoritmos, como é o caso de Árvores de Decisão [6, 10, 17], Redes Neuronais Artificiais [6, 9, 10, 12, 17], Clustering [6, 10, 17], entre outros. O novo algoritmo, Learning Vector Quantization [1, 2, 13, 15, 16], vem acrescentar valor a esta ferramenta, pois é um algoritmo fácil de perceber, simples, com tempos de execução semelhantes aos algoritmos referidos e cujos resultados de classificação são superiores. Como é um caso especial de Redes Neuronais Artificiais, este algoritmo tem uma aprendizagem supervisionada [17, 18], e uma das grandes vantagens que a sua integração com o Microsoft SQL Server 2005 [16, 19] oferece é a opção do utilizador poder ver os vectores de referência que terão um papel importante na classificação dos vectores de teste fornecidos pelo utilizador. Palavras-chave Data Mining, Data Warehouse, Aprendizagem Supervisionada, Aprendizagem Não Supervisionada, Àrvores de Decisão, Clustering, Nearest Neighbor, Redes Neuronais, Naive Bayes, Microsoft SQL Server, ORACLE, SAS e Learning Vector Quantization, Integração e Algoritmo Plug-In. 3
4 Abstract In the last years Data Mining area underwent great changes. It is seen as an expanding area of the greatest importance in every company in tasks like data classification and data prevision. The goal of this work is to implement a new data mining algorithm in Microsoft SQL Server 2005, this way adding to its functionality. We considered other Tools in the data mining market in order to plug-in new algorithms, namely Oracle and SAS. Both these tools developed present the same inconvenient: offers little information to the programmer about this subject, and in SAS case, the new algorithm should be implemented in a proper language. Besides that, the Tool offered by Microsoft is the most used by companies, and offers tutorials and help for the integration, that?s why that was the chosen Tool. In this Tool some of the most known algorithms are implemented, like Decision Trees, Artificial Neural Networks and Clustering. The goal of this new algorithm, Learning Vector Quantization, is to increase the value of the Tool. The algorithm has a simple structure and is very easy to understand. His execution times are similar to the algorithms here referred, and the classification results are very good. As this algorithm is a special case of Artificial Neural Networks, it has a supervised learning. His big advantage is the possibility of the final codebook vectors being seen by the user. This way the user can use that information to maximize the accuracy of the algorithm in the classification task. Key Words Data Mining, Data Warehouse, Supervised Learning, Unsupervised Learning, Decision Trees, Clustering, Nearest Neighbour, Artificial Neural Networks, Naïve Bayes, Microsoft SQL Server 2005, Oracle, SAS, Learning Vector Quantization, Integration and Plug-in Algorithm. 4
5 Índice Agradecimentos... 2 Resumo... 3 Abstract... 4 Índice... 5 Lista de Tabelas... 7 Lista de Figuras... 7 Lista de Matrizes... 9 Lista de Gráficos Introdução Data Mining Objectivos Estrutura Vista geral Tarefas de Data Mining Classificação Previsão Regressão Associação Clustering Técnicas de Data Mining Árvores de decisão Nearest Neighbor Naive Bayes Redes Neuronais Artificiais Learning Vector Quantization Clustering Ferramentas Microsoft SQL Server SAS Oracle Comparação das ferramentas Learning Vector Quantization (LVQ) Decisão Óptima LVQ Optimized-Learning-Rate LVQ1 (OLVQ1) LVQ
6 3.5 LVQ Diferenças entre LV1, LVQ2 e LVQ Considerações gerais Inicialização dos vectores de referência Aprendizagem Regra de paragem Vantagens Microsoft SQL Server Interfaces Interfaces do algoritmo usando C Interfaces do algoritmo usando C# Plug-In O modelo: Learning Vector Quantization Construir um Algoritmo Plug-in Personalizar o algoritmo Microsoft SQL Server com LVQ Arquitectura do utilizador Criar uma fonte de dados Criar uma vista sobre os dados Construir o modelo Realizar previsões sobre o modelo Personalizar os parâmetros Experiências Teste básico Teste avançado Testes avançados: AdventureWorksDW Conclusão das experiências Conclusão Anexo: Arquitectura Microsoft SQL Server Arquitectura do servidor Arquitectura do cliente Fluxo de dados Glossàrio Bibliografia
7 Lista de Tabelas 5.1 Parâmetros do primeiro teste básico, com todos os valores por omissão dos parâmetros do algoritmo Parâmetros do algoritmo para o segundo teste básico Parâmetros do algoritmo LVQ para o terceiro teste básico Descrição das amostras de treino e de teste para o teste avançado Parâmetros do algoritmo LVQ para o primeiro teste avançado Parâmetros do algoritmo LVQ para o segundo teste avançado Parâmetros do algoritmo LVQ para o terceiro teste avançado Parâmetros da primeira experiência do algoritmo LVQ para o primeiro teste com AdventureWorksDW onde os conjuntos de treino e de teste eram representados pela mesma tabela, vtargetmail Parâmetros da segunda experiência do algoritmo LVQ para o primeiro teste com AdventureWorksDW onde os conjuntos de treino e de teste eram representados pela mesma tabela Parâmetros da terceira experiência do algoritmo LVQ para o primeiro teste com AdventureWorksDW onde os conjuntos de treino e de teste eram representados pela mesma tabela Parâmetros da primeira experiência do algoritmo LVQ para o segundo teste com AdventureWorksDW onde o conjunto de treino representa 80% dos casos da tabela vtargetmail e o conjunto de teste é representado por 20% dessa mesma tabela Lista de Figuras 2.1 O processo de classificação de dados: (a) Aprendizagem - os dados de Treino são analisadas por um algoritmo de classificação. Aqui o atributo que representa a etiqueta da classe é credit_rating, e o modelo de aprendizagem é representado na forma de Classification Rules. (b) Classificação - os dados de teste são usadas para estimar a exactidão das regras de classificação Árvore de decisão para o conceito buys_computer (sim ou não), indicando se é provável que um cliente da AllElectronics compre um computador. Cada nó não folha representa um teste a um atributo. Cada nó folha representa uma classe Uma rede neuronal feed-forward com múltiplas camadas: Uma amostra de treino, alimenta a camada de entrada. Ligações pesadas existem entre cada camada, onde denota o peso de uma unidade de uma camada para uma unidade da camada anterior
8 2.4 Uma camada escondida ou de saída : As entradas desta camada são saídas da camada anterior. Estes são multiplicados pelo peso correspondente, de maneira a formar uma soma pesada. Uma função não linear de activação é aplicada à saída da rede Clustering de um conjunto de objectos baseado no método k-means (o meio de cada cluster está marcado por um + ) (a) Pontos pequenos: sobreposição de duas funções de densidade Gaussiana correspondente à classe S1 e S2 com os seus centróides a serem mostrados pela cruz branca e preta, respectivamente. Curva sólida: fronteira de decisão de Bayes. (b) Pontos pretos largos: vectores de referência da classe S1. Círculos abertos: vectores de referência da classe S2. Curva sólida: fronteira de decisão no LVQ. Curva partida: fronteira de decisão de Bayes Ilustração da janela do algoritmo LVQ2, onde e são os vectores de referencia mais próximos do vector de aprendizagem, e são as respectivas distancias de a e Classes C++ que implementam as interfaces COM [5, 14] Tratamento de chamadas a funções COM Lista dos algoritmos disponíveis, mostrando o novo algoritmo, ainda sem nome; Janela para a criação de uma nova ligação à base de dados que contém as tabelas com os dados de aprendizagem e de classificação Menu que oferece ao utilizador a escolha de uma fonte de dados já criada para realizar uma vista sobre esses dados Janela onde o utilizador poderá escolher as tabelas indicadas para aprendizagem e classificação que irão fazer parte da estrutura de mineração Lista de algoritmos disponíveis, onde se destaca o novo algoritmo Menu onde são especificadas as colunas (atributos) de entrada e saída Ilustração do painel de previsões com os campos Source, Field e Alias preenchidos Lista apresentada com os valores previstos pelo modelo na coluna Previsto e os valores reais na coluna Actual Propriedades do modelo de mineração criado ao longo desta secção Menu onde são especificados os parâmetros de entrada do algoritmo LVQ Arquitectura do servidor de Analysis Services Arquitectura do cliente do Analysis Services Fluxo de dados de um Algoritmo Plug-in
9 Lista de Matrizes 5.1 Matriz de confusão do primeiro teste básico do algoritmo LVQ, com um conjunto de treino e de teste artificial contendo vectores de duas dimensões Matriz de confusão do segundo teste básico do algoritmo LVQ, com um conjunto de treino e de teste artificial contendo vectores de duas dimensões Matriz de confusão do terceiro teste básico do algoritmo LVQ, com um conjunto de treino e de teste artificial contendo vectores de duas dimensões Matriz de confusão do primeiro teste avançado do algoritmo LVQ. Estes resultados foram obtidos através do conjunto de teste com 2000 casos, onde cada vector possuía 36 dimensões Matriz de confusão do segundo teste avançado do algoritmo LVQ. Estes resultados foram obtidos através do conjunto de teste com 2000 casos, onde cada vector possuía 36 dimensões Matriz de confusão do terceiro teste avançado do algoritmo LVQ. Estes resultados foram obtidos através do conjunto de teste com 2000 casos, onde cada vector possuía 36 dimensões Matriz de confusão do primeiro teste do algoritmo Árvores de Decisão cujos conjuntos de treino e de teste partilham os mesmos dados residentes na tabela vtargetmail Matriz de confusão do primeiro teste do algoritmo Clustering, cujos conjuntos de treino e de teste partilham os mesmos dados residentes na tabela vtargetmail Matriz de confusão do primeiro teste do algoritmo Naive Bayes, cujos conjuntos de treino e de teste partilham os mesmos dados residentes na tabela vtargetmail Matriz de confusão do primeiro teste do algoritmo Redes Neuronais, cujos conjuntos de treino e de teste partilham os mesmos dados residentes na tabela vtargetmail Matriz de confusão da primeira experiência do algoritmo LVQ, cujos conjuntos de treino e de teste partilham os mesmos dados residentes na tabela vtargetmail Matriz de confusão da segunda experiência do algoritmo LVQ, cujos conjuntos de treino e de teste partilham os mesmos dados residentes na tabela vtargetmail Matriz de confusão da terceira experiência do algoritmo LVQ, cujos conjuntos de treino e de teste partilham os mesmos dados residentes na tabela vtargetmail Matriz de confusão do segundo teste do algoritmo Árvores de Decisão, onde o conjunto de treino é composto por 80% dos casos da tabela vtargetmail e o conjunto de teste representa os casos restantes dessa tabela Matriz de confusão do segundo teste do algoritmo Clustering, onde o conjunto de treino é composto por 80% dos casos da tabela vtargetmail e o conjunto de teste representa os casos restantes dessa tabela Matriz de confusão do segundo teste do algoritmo Redes Neuronais, onde o conjunto de treino é composto por 80% dos casos da tabela vtargetmail e o conjunto de teste representa os casos restantes dessa tabela
10 5.17 Matriz de confusão da primeira experiência do segundo teste do algoritmo LVQ, onde o conjunto de treino é composto por 80% dos casos da tabela vtargetmail e o conjunto de teste representa os casos restantes dessa tabela Matriz de confusão da segunda experiência do segundo teste do algoritmo LVQ, onde o conjunto de treino é composto por 80% dos casos da tabela vtargetmail e o conjunto de teste representa os casos restantes dessa tabela Lista de Gráficos 5.1 Ilustração dos vectores de referência finais, onde se pode verificar a presença de três clusters de classes diferentes Ilustração dos vectores de referência finais, onde se pode ver a presença de dois clusters distintos da classe 1 e da classe 3, enquanto a classe 2 apenas apresenta um cluster Ilustração dos vectores de referência finais, onde se pode ver a presença de dois clusters distintos da classe 1 e da classe 3, enquanto a classe 2 apenas apresenta um cluster bem definido com alguns vectores a saírem fora da sua área Representação gráfica da precisão parcial da classificação dos clientes sem casa própria do primeiro teste com AdventureWorksDW Representação gráfica da precisão parcial da classificação dos clientes com casa própria do primeiro teste com AdventureWorksDW Representação gráfica da precisão parcial da classificação dos clientes sem casa própria do segundo teste com AdventureWorksDW Representação gráfica da precisão parcial da classificação dos clientes com casa própria do segundo teste com AdventureWorksDW
11 1 Introdução O Data Mining surge numa época em que o problema de espaço de armazenamento de dados já não existe. A grande razão do seu aparecimento ter atraído muita atenção na indústria de informação traduz-se disponibilidade de grandes quantidades de dados e na necessidade eminente de tornar esses dados em informação útil e em conhecimento [11]. A abundância de dados conjugada com a necessidade de ferramentas de análise de dados poderosas, tem sido descrita como uma situação de riqueza de dados mas pobreza de informação [11]. O crescimento do número de dados recolhidos e guardados em grandes e numerosas bases de dados excedeu a nossa habilidade humana de compreensão sem poderosas ferramentas. Como resultado, dados recolhidos em grandes bases de dados tornaram-se túmulos de dados arquivos de dados raramente visitados. Consequentemente, decisões importantes são frequentemente tomadas, não baseadas na informação guardada nas bases de dados, mas baseadas na intuição de quem toma a decisão, simplesmente porque essa pessoa não tem as ferramentas para extrair o conhecimento valioso embebido nas grandes quantidades de dados [9, 11]. O Data Mining [9, 11] foi criado para trazer respostas aos problemas de organização dos dados num Data Warehouse [8, 9, 11], ou de organização dos dados de maneira a obter conjuntos com algumas semelhanças, para deles realizar algumas previsões úteis para a empresa. O Data Mining usa vários algoritmos ou técnicas para encontrar padrões entre os dados, os quais serão depois usados para a previsão pretendida. Existem duas abordagens ou categorias por onde se dividem os mais famosos algoritmos de Data Mining, dependendo do tipo de aprendizagem que pode ser supervisionada ou direccionada e não supervisionada ou não direccionada. Nesta irá focar a aprendizagem supervisionada, dado que o algoritmo Learning Vector Quantization inclui-se nesse grupo. 1.1 Data Mining O Data Mining [9, 11] pode ser visto como um resultado da evolução natural das tecnologias de informação. O fantástico progresso da tecnologia hardware dos computadores levou a uma quantidade enorme de computadores poderosos, equipamento para recolha de dados e meios de armazenamento. Esta tecnologia fornece um grande avanço às indústrias de bases de dados e de informação, e torna disponível um grande número de bases de dados e repositórios de informação para a gestão de transacções, retorno de informação e análise de dados. Os dados podem ser agora guardados em diferentes tipos de bases de dados. Uma arquitectura de base de dados que recentemente emergiu foi o Data Warehouse [8, 9, 11], um repositório de múltiplas e heterogéneas fontes de dados, organizados sobre um esquema unificado num único sítio, de modo a facilitar tomadas de decisões de gestão. A tecnologia de Data Warehouse inclui limpeza de dados, integração de dados e On-Line Analytical Processing (OLAP) [9, 11], que são técnicas de análise com funcionalidades (sumarização, consolidação e agregação). Apesar das ferramentas OLAP suportarem análise multidimensional e tomadas de decisão, ferramentas de análise de dados 11
12 adicionais são requeridas para análises mais profundas, tais como classificação de dados, clustering e a caracterização das mudanças dos dados ao longo do tempo. O Data Mining [9, 11] refere-se à extracção ou mineração de conhecimento de largas quantidades de dados. Data Mining é apenas um passo simples na descoberta do conhecimento nas bases de dados, pois é o processo de descobrir conhecimento interessante de largas quantidades de dados guardados quer em base de dados ou em Data Warehouses. Data Mining [9, 11] consegue encontrar informação descritiva e preditiva. Qual o tipo de informação a escolher depende do que se quer fazer com os resultados. Quando se escolhe obter informação preditiva o objectivo é derivar informação que oferece pistas sobre um evento futuro. A informação descritiva descreve eventos passados duma maneira que se tornaria difícil ver através de meios normais, oferecendo-nos a oportunidade de tomar decisões baseado em novas relações descobertas [9]. As ferramentas de Data Mining efectuam análise de dados e podem esconder padrões de dados importantes, contribuindo em larga escala para as estratégias de negócio, bases de conhecimento, pesquisa científica e médica. 1.2 Objectivos A finalidade desta tese é adicionar funcionalidade à ferramenta disponibilizada pela Microsoft, Microsoft SQL Server 2005 [11], no campo do Data Mining. Esta nova funcionalidade consiste no desenvolvimento de uma nova técnica [9] de Data Mining já existente mais ainda não incorporada na ferramenta mencionada. A técnica baseia-se na tarefa de classificação e dá pelo nome de Learning Vector Quantization [1, 2], um algoritmo desenvolvido por Kohonen do qual existem várias versões. O facto de ser uma técnica de classificação pressupõe que o algoritmo faça primeiro a sua aprendizagem da rede através de um conjunto inicial de dados, e após essa aprendizagem irá tentar prever o campo que o utilizador nomear para previsão. Esta tese vem contribuir para um aumento do número de técnicas de Data Mining [9, 11] disponíveis pela ferramenta oferecida pela Microsoft. Sendo um algoritmo muito fácil de perceber, e que se baseia em algumas técnicas já existentes, como é o caso de Nearest Neighboor [3, 5, 9, 11], torna-se mais rápido e simples. Uma das grandes vantagens que oferece ao utilizador é a possibilidade deste observar os vectores de referência finais, que irão ser usados para a classificação de dados. Através desta visualização dos vectores de referência finais o utilizador consegue tirar conclusões sobre como estão dispostos esses vectores em clusters, ou quais os novos valores tomados por eles, e daí tirar informação necessária para encontrar os melhores valores para os parâmetros de entrada do algoritmo. 1.3 Estrutura Seguidamente será apresentada a estrutura desta tese, bem como o conteúdo de cada um dos seus capítulos. 12
13 O capítulo 2 fornece uma vista geral das tarefas de Data Mining [9] bem como uma descrição mais detalhada de todo o processo e uma arquitectura de um sistema típico de Data Mining [9, 11]. Ainda neste capítulo estarão descritas algumas técnicas de Data Mining mais utilizadas tais como Árvores de Decisão [3, 5, 9, 11, 18], Naive Bayes [3, 5, 9, 11, 18], Redes Neuronais [3, 4, 5, 6, 9, 11, 18] e Clustering [3, 5, 9, 11, 18]. O capítulo 3 propõe uma visita ao algoritmo central desta tese, onde se irá viajar através da sua história, oferendo uma descrição precisa sobre cada uma das actualizações do algoritmo. O capítulo 4 será dedicado à ferramenta de integração do algoritmo LVQ, o Microsoft SQL Server 2005, dà detalhes sobre a sua arquitectura, oferece uma descrição do método de integração do algoritmo e também uma pequena explicação da sua interface com o algoritmo recorrendo a duas linguagens de programação mais utilizadas em integração de algoritmos: C++ 1, linguagem na qual foi desenvolvido o trabalho desta tese e C# [13]. O capítulo 5 descreve a arquitectura de interacção com o utilizador com recurso a imagens reais da integração do algoritmo. Neste capítulo consta também a descrição das experiências mais relevantes realizadas ao trabalho. O capítulo 6 faz as conclusões finais e no capítulo 7 encontra-se um glossário de termos, com as descrições dos termos mais utilizados nesta tese. 1 SQL Server Data Mining. [Online] [Cited: Novembro 20, 2007.] 13
14 2 Vista geral O Data Mining [9, 11] foi criado para responder às necessidades das grandes organizações que, com o passar do tempo foram armazenando grandes quantidades de dados nas suas bases de dados e posteriormente no seu Data Warehouse [8]. Hoje em dia todas as grandes empresas têm o seu Data Warehouse [8, 11], um armazém central de dados, com estruturas de armazenamento desenhadas para guardar grandes quantidades de informação e que oferecem uma rápida resposta ao processamento de transacções eficientes. Além dos problemas de dados inconsistentes e inválidos, as grandes organizações vêem-se perante um problema maior: o de tratamento dos dados, ou seja, de distribuição e organização dos dados para futura utilização. A essa necessidade o Data Mining oferece um conjunto de técnicas [3, 4, 5, 6, 9, 11] para organizar os dados de acordo com padrões [4] semelhantes encontrados, para posterior utilização em previsões. Estes padrões não são mais do que um conjunto de eventos que ocorrem com frequência suficiente no conjunto de dados considerado e que revelam relações entre si [11]. Para encontrar estes padrões, o processo de Data Mining necessita de um algoritmo matemático e estatístico que transforma o caso (cada item de dados utilizado como fonte para um modelo) de dados originais no modelo de Data Mining. Quando um algoritmo é associado a uma estrutura de dados, a estrutura é populada com dados de uma maneira que reflecte a existência de relações e padrões do conjunto original, permitindo predição baseada nesses dados [9, 11]. Um modelo de Data Mining [11] não é mais do que uma estrutura física de um subconjunto de dados compilados num algoritmo de Data Mining, juntamente com a descrição do conjunto original. Esta estrutura contém os padrões presentes nas bases de dados e é usada como base a partir da qual se faz previsões. Por juntar informação dos conjuntos de dados originais, a aplicação de Data Mining constrói um subconjunto de dados que são compilados usando um algoritmo Data Mining. Este conjunto de resultados pode então ser usado para fazer previsões contra os dados da amostra [9, 11]. Podemos então concluir que o Data Mining apresenta-se como sendo um processo assistido por computador para encontrar e analisar enormes conjuntos de dados, encontrar padrões desconhecidos e relações, e retirar deles algum significado, fazendo a classificação dos dados existentes num Data Warehouse. Data Mining envolve descrever o passado para poder prever o futuro [9, 11]. O Data Mining pode encontrar informação descritiva e preditiva. O objectivo da informação descritiva é descrever eventos passados, oferecendo a oportunidade de tomar decisões baseado em novas relações descobertas, enquanto o objectivo da informação preditiva é derivar a informação que oferece pistas sobre um evento futuro [11]. As tarefas e técnicas disponibilizadas são o núcleo de um sistema de Data Mining. Alguns sistemas oferecem apenas uma tarefa como, por exemplo, a classificação. Outros acabam por oferecer maior variedade como tarefas de previsão, associação ou clustering. 14
15 2.1 Tarefas de Data Mining Em Data Mining uma tarefa corresponde a um tipo de problema de descoberta de conhecimento para o qual se pretende arranjar um uma solução. Conseguimos distribuí-las las por dois grandes grupos: Classificação e Previsão. se aqu aqui outras tarefas de Data Mining que apesar de se poderem incluir No entanto, consideram-se num ou noutro grupo, apresentam algumas propriedades interessantes que lhes faz merecer esta diferenciação Classificação A tarefa de classificação consiste em construir um modelo aplicável a dados não classificados visando categorizá-los em classes. Esta tarefa prevê etiquetas de classes, ou seja variáveis discretas. O objectivo é encontrar fórmulas, rmulas, regras ou padrões a partir de um conjunto de dados de treino, de modo a organizar esses dados em classes. Um registo é examinado e classificado de acordo com uma classe predefinida. Essas fórmulas ou regras irão depois ser aplicadas num conjunto de dados de teste. A classificação de dados é um processo de dois passos [Figura 2.1]. No primeiro primei passo o modelo é construído descrevendo um conjunto predeterminado de classes de dados dados,, através da d análise de tuplos da base de dados descritos por atributos atributos.. Figura 2.1 O processo de classifica classificação de dados: (a) Aprendizagem - os dados de Treino são analisadas por um algoritmo de classificação. Aqui o atributo que representa a etiqueta da classe é credit_rating,, e o modelo de aprendiza aprendizagem é representado na forma de Classification Rules. Rules (b) Classificação - os dados de teste este são usadas para estimar a exactidão das regras de classificação [9]. Cada tuplo é assumido como pertencendo a uma classe predefinida, representada por um dos atributos e chamada de etiqueta da classe. Os tuplos de dados analisados para construir o modelo mod formam o conjunto de dados de treino. Como a etiqueta da classe de cada amostra retirada da base de dados é fornecida, este passo é também conhecido ccomo omo aprendizagem supervisionada (a aprendizagem do modelo é supervisionada na medida em que é dito qua quall a classe a que cada amostra de treino pertence). No segundo passo, o modelo é usado para classificação da classe de 15
16 uma nova amostra, a amostra de teste, onde a percentagem de classificação certa para cada amostra é calculada. Como exemplo de tarefas de classificação temos a classificação de um pedido de crédito como sendo de baixo, médio ou alto risco. [9, 11] Previsão Na Previsão as operações são efectuadas sobre um conjunto de dados contínuos e ordenados, de modo a extrair um modelo preditivo que consiga prever valores futuros de outras variáveis de interesse. A previsão é usada para definir um valor para uma variável continua desconhecida. Dado um item e um dado modelo de previsão, pretende-se com esta tarefa prever o valor de um atributo específico do item, usando valores contínuos ou ordenados. Esta tarefa tem também as mesmas duas fases consideradas na tarefa de Classificação. Muitas vezes a tarefa de Previsão é vista como a construção e uso de um modelo para prever a classe de uma amostra sem etiqueta. Nesta visão, a Classificação é um dos tipos de problemas de previsão, usada para prever valores discretos, sendo que a Previsão é usada para prever valores contínuos. Como exemplo de uma tarefa de previsão temos o caso, dado um modelo de previsão e um conjunto de transacções de um cartão de crédito deverá ser possível prever se uma transacção específica é ou não fraudulenta. [9, 11] Regressão A regressão é a análise de dependência de valores de certos atributos em relação a valores de outros atributos constantes no mesmo item e a posterior produção de um modelo que possa prever os valores destes atributos para futuros registos. Dado que a regressão opera sobre valores contínuos, é normalmente inserida nas tarefas de previsão, apesar de poder também ser usada em tarefas de classificação. [9] Associação Esta tarefa consiste em identificar associações entre atributos no mesmo item ou associações entre itens diferentes. Um exemplo clássico é determinar quais os produtos que costumam ser colocados juntos num carrinho de compras. [9] Clustering A tarefa de Clustering consiste no agrupamento de um conjunto de dados em subconjuntos de classes com características semelhantes. No Clustering, não existem à partida classes predefinidas e os itens são agrupados de acordo com a semelhança, o que a diferencia da tarefa de classificação. 16
17 Esta tarefa é também conhecida por ter uma aprendizagem não supervisionada, pois a etiqueta da classe de cada amostra de treino não é conhecida, e o número ou conjunto de classes a serem aprendidas podem não ser conhecidas previamente. Um exemplo poderá ser dado um conjunto de clientes de uma loja, identificar aqueles que compram o mesmo tipo de produtos. [9] 2.2 Técnicas de Data Mining Organizações aplicam as tecnologias Data Mining aos seus armazéns de dados por dois motivos: Para registar o passado dos dados (guardar histórico) Para prever o futuro através dos dados Ultimamente usam a informação tirada dos computadores para fazer decisões sobre o futuro dos dados. O tipo de informação que uma organização quer, determina o tipo de modelo construído e os algoritmos aplicados à estrutura de dados. O objectivo do Data Mining [9, 11] é encontrar regras compreensíveis e relações em conjuntos de casos. Essas regras podem então ser usadas para prevenir ameaças futuras, para salvaguardar os perfis dos clientes, para controlo de riscos, ou apenas para descrever e explicar os conteúdos de uma dada base de dados. Devido à preparação exigida, Data Mining não é um processo completamente automatizado. O processo requer que tomemos uma série de factores em conta sobre os dados e o seu uso pretendido para depois aplicar os melhores métodos de Data Mining. [11] Não existe tal coisa como um método superior de Data Mining, no mundo do Data Mining é geralmente aceite que independentemente do método escolhido, vão existir trade-offs. Nenhum método simples resulta para todas as pessoas. Existem dois tipos de Data Mining que separam os vàrios algoritmos ou métodos existentes, que seguidamente serão explorados e definidos. Data Mining direccionado ou supervisionado De forma a realizar operações de Data Mining Direccionado [9, 11], todos os factores conhecidos, ou variáveis de entrada, necessitam de ser dadas para que o engenho do Data Mining possa encontrar as melhores relações entre esses atributos e para que uma regra seja construída dentro do modelo de Data Mining. A previsão é baseada em valores desconhecidos ou variáveis alvo, significando isto que o engenho de Data Mining irá encontrar o valor mais provável para esses valores desconhecidos baseado nos valores conhecidos fornecidos com as variáveis de entrada. O Data Mining supervisionado usa as mais populares técnicas de Data Mining e algoritmos, tais como Árvores de Decisão [3, 5, 9, 11, 18] e Redes Neuronais [3, 4, 5, 6, 9, 11, 18], classifica os dados para realizar previsões ou estimativas com o objectivo de derivar valores alvo, ou a etiqueta da classe alias, é a necessidade dos valores alvo que dá ao Data Mining direccionado a sua direcção. Uma larga variedade de negócios usam-no, tais como bancos, cadeias de retalho, empresas farmacêuticas. [11] 17
18 2.2.1 Árvores de decisão É um algoritmo muito conhecido usado por todas as ferramentas de Data Mining disponíveis comercializadas. as. Este termo descreve um número de algoritmos específicos, tal como Chi-squared Automated Interaction Detector (CHAID) e o C4.5 e o processo do algoritmo que eles partilham, o que resulta em modelos que parecem árvores. [9, 11] Os algoritmos de Árvores de Decisão [6, 5, 9, 11, 18] são recomendados para tarefas preditivas que requerem um modelo de classificação orientado e, como tal, são desenhados para problemas que se resolvem segregando casos em grupos discretos. Por exemplo, as árvores de decisão são frequentemente utilizadas para prever quais os clientes mais prováveis de responder a marketing por e os mais prováveis de serem aprovados para empréstimos. Uma Árvore de Decisão [3, 5, 9, 11, 18, 19], é uma árvore onde cada nó não terminal representa um teste ou decisão sobre o item considerado, cada ramo representa o resultado do teste, e os nós folha representam a classe ou classes de distribuição. O objectivo principal é separar as classes em que os dados estão agrupados. Tuplos de classes diferentes tendem a ser colocadas em subconjuntos diferentes, cada um descrito por regra simples [Figura 2.2].. Essas regras podem ser expressas como declarações lógicas, numa linguagem como SQL, de modo a que possam ser aplicadas directamente a novos tuplos. Uma vantagem deste método é a maneira a intuitiva de descrever nós com regras [Figura 2.2]. Contudo perceber o significado de uma regra ra com fundamento pode ser um sério problema para a aproximação por Árvores de Decisão. O problema é originado do facto de à medida que a árvore expande para baixo os seus níveis, existe poucos registos deixados nos nós desses níveis da árvore de classificação que está a ser construída. [9, 11] Figura 2.2 Árvore de decisão para o conceito buys_computer (sim ou não), indicando se é provável que um cliente da AllElectronics compre um computador. Cada nó não folha representa um teste a um atributo. Cada nó folha representa uma classe [9]. Uma árvore de decisão separa os dados num número largo de conjuntos que se tornam mais pequenos à medida que se tornam mais específicos. Quanto mais largo é o número de diferentes casos a examinar, mais pequeno é cada próximo conjunto separado de exemplos de treino, o que, devido aos números encolhidos, inspira menos confiança que a classificação adicional correcta que pode ser executada exactamente. [9, 11] Se a árvore se torna demasiado grande devido ao largo número de pequenos ramos, então existe uma boa hipótese de que as regras dentro desses nós não se apliquem a nenhum estudo estatístico 18
19 justificável, sobretudo porque cada um dos nós desses ramos geralmente contém uma pequena percentagem suspeita de todos os casos. [9, 11] CART, CHAID e C4.5 Quando um algoritmo de Árvores de Decisão é aplicado a um problema de Data Mining o seu resultado parece-se com uma árvore. Vamos agora olhar para alguns dos algoritmos de árvores de decisão mais usados no mundo [11]: Classification and regression tree (CART): é o algoritmo mais usado no mundo devido ao seu eficiente sistema de classificação. Os seus atributos que têm valores preditivos são escolhidos assim que se determina que eles introduzem ordem ao conjunto de dados. São usados para separar a piscina de dados existente em dois nós, e seguintes ramos ou folhas que sejam posteriormente criados. Uma das características mais úteis do CART é a habilidade de lidar com dados desaparecidos aquando da construção da árvore. Ele saberá quando não usar um determinado valor para saber se uma divisão de ramo deve de ser feita. Uma característica única do CART é a restrição da divisão binária. Esta causa a divisão dos nós apenas em dois nós filhos, o que produz uma árvore mais profunda que as outras. Uma árvore mais profunda é considerada mais económica com os dados e como resultado é capaz de detectar mais estruturas antes de poucos dados serem deixados para anàlise. Cada nó numa hierarquia divide os seus registos pelos nós abaixo de si. Se um nó tem poucos registos cessa a divisão, enquanto os outros nós continuam. [11] Chi-Squared Automatic Interaction Detector (CHAID): este algoritmo usa os testes de análise Chi-Squared para validar a árvore. Devido a este tipo de análise focar-se num grupo de tabelas para determinar a distribuição de um dado valor, os atributos do conjunto de dados devem ser forçados em grupos que possam ser testados; Como são determinadas as divisões As árvores de decisão usam um algoritmo de indução para decidir a ordem pela qual as divisões ocorrem [9, 11]. O algoritmo indutivo desenha conclusões baseado em instâncias repetidas de um evento. As divisões são determinadas aplicando análises estatísticas sobre os atributos de dados que fazem os casos. O objectivo geral é construir árvores que sejam o mais desequilibradas possível, em termos de distribuição desses atributos. Em outras palavras, o algoritmo procura colocar mais que um tipo de atributos num dado nó. Quando for possível o algoritmo vai tentar ter todos os nós puros, o que significa que o nó contém apenas casos com 100% de um dado tipo de variáveis [11]. As árvores de decisão também criam regras. Cada nó pode ser escrito como um conjunto de regras que fornece uma descrição da função daquele nó em particular na árvore, tal como dos nós que levam a ele [11]. 19
20 Como são derivadas as previsões Uma vez a árvore construída pode ser usada para um dos seus propósitos mais importantes, prever os valores desaparecidos para novos casos. Existem duas aproximações para realizar previsões [11]: Pode escolher-se um caso e seguir os seus caminhos, que são determinados pelos seus atributos, para ver em que folha acaba; Pode usar-se cada nó folha para derivar uma nova regra Navegar pela árvore Uma vez que a árvore está preenchida, pode ser usada para prever novos casos começando pelo nó raiz da árvore e continuando o caminho para os ramos, que são baseados nos atributos do novo caso, antes de chegar ao nó folha. O caminho que o novo caso segue é baseado nos valores que causaram a divisão e não nas variáveis independentes na nova instância. Um problema que poderá ocorrer está relacionado com as possibilidades presentes num dado nó terem aproximadamente a mesma oportunidade de ocorrerem. O melhor método é permitir ao operador decidir o que fazer em casos como este. [11] Problemas das Árvores de Decisão Se, por acaso, for gerada uma árvore pura, então as previsões baseadas nos casos usados para construir o modelo irão sempre mostrar os resultados 100% exactos. Contudo, uma vez que se começa a fazer previsões baseadas em casos que são independentes do conjunto de treino, a árvore 100% pura será péssima a fazer previsões, porque as regras suportadas pela árvore são demasiado restritas para reflectir o mundo real [3, 5, 11, 18] Quando usar árvores de decisão Quando for aplicado confiantemente o esquema de segmentação a um conjunto de dados que reflecte um grupo de potenciais clientes [11]; Quando se identificar possíveis relações interactivas entre variáveis duma maneira que levará a perceber como mudar uma variável pode afectar outra [11]; Quando se fornecer uma representação visual das relações entre variáveis na forma de uma árvore [11]; Quando for simplificada a mistura de atributos e categorias para ficar com os essenciais necessários para fazer previsões [11]; Quando forem explorados os dados para identificar variáveis importantes num conjunto que pode ser usado eventualmente como alvo [11]; Nearest Neighbor Este método é menos utilizado que o descrito na secção anterior ou que o método de Naive Bayes, para classificação em sistemas comerciais de Data Mining. [9] 20