Data Mining

Como de costume, sigo divulgando congressos e seminários relevantes ligados a banco de dados. Agora é a vez daquele que eu considero o melhor dos banco de dados free, o PostgreSQL.

Nos dias 23 e 24 de Outubro de 2009, no Centro de Convenções da Unicamp em Campinas,  São Paulo, acontece a 3ª Conferência Brasileira de PostgreSQL. Segundo o site do evento, o PGCon Brasil é o maior evento sobre PostgreSQL da América Latina e em 2008 contou com a participação de 300 profissionais de informática. Neste ano serão 3 salas simultâneas com tutoriais e palestras, com a participação de desenvolvedores nacionais e internacionais do PostgreSQL.

A Google anunciou esta semana que pretende entrar na briga pelo mercado de Sistemas Operacionais com a Microsoft. Segundo o blog da empresa o Chrome OS estará disponível para NetBooks a partir de 2010.

Basta a Google lançar qualquer coisa e isto já vira notícia na WEB e, por consequência, nas disciplinas de tecnologia das Universidades. Dessa vez não foi diferente. Mal a notícia caiu na rede e os meus alunos, especialmente da disciplina de Banco de Dados, já me perguntavam como isto poderia influenciar trabalhos de Mineração de Dados.

A resposta para a questão é sim: não influencia em nada (ao menos por enquanto). A Google deixou claro que pretende lançar um sistema operacional voltado para Web, ou seja, o foco (repito, ao menos por enquanto) é o usuário final e não programadares, analistas, etc. Vai demorar muito para vermos (se é que vamos ver) um Oracle ou um PostgreSQL para Chromos OS.

Começou ontem e vai até a próxima quarta-feria (01/07), em Paris, a 15º ACM SIGKDD Conference on Knowledge Discovery and Data Mining. A conferência ocorre anualmente e é o principal evento sobre Data Mining do mundo.

Dentre as palestras, tutoriais e workshops destacam-se:

Workshop: Data Mining Case Studies and Practice Prize (DMCS #3) (Gabor Melli, Peter van der Putten, Brendan Kitts)

The 3rd Workshop on Social Network Mining and Analysis (SNA-KDD) (Lee Giles, John Yen, Prasenjit Mitra, Haizheng Zhang, Igor Perisic)

The Third International Workshop on Data Mining and Audience Intelligence for Advertising (ADKDD) (Ying Li, Arun C. Surendran, Dou Shen)

Tutorial: Planning, Running, and Analyzing Controlled Experiments on the Web (Ronny Kohavi, Roger Longbotham, John Quarto-vonTivadar)

Paralelo ao evento ocorre a KDD Cup 2009, uma Olimpíada de mineração de dados, cujo tema deste ano é Customer Relationship Management (CRM). A organização do evento disponibilizou uma grande base de dados da French Telecom Company Orange, onde os concorrentes devem encontrar consumidores propensos a comprar novos produtos e serviços.

A Teoria da Resposta ao Item (TRI) é um modelo estatístico utilizado para avaliar habilidades e conhecimentos. Seu uso mais comum está ligado a testes de múltipla escolha, que são comumente usados em provas de concursos públicos e vestibulares de universidades públicas e privadas.

A TRI permite analisar a proeficiência do candidato em cada uma das áreas presente na prova, pois cria uma escala de desempenho. O modelo analisa não apenas as questões acertadas, mas também o padrão de respostas dadas pelo aluno.  Alunos que eram um grande número de questões fáceis dificilmente acertarão questões difícei, se acertarem é porque “chutaram”.

A TRI tem ganho destaque na mídia desde que o Ministério da Educação (MEC) informou que ela será usada no novo Exame Nacional do Ensino Médio (ENEN). Este é mais um caso que mostra como a Mineração de Dados está presente no nosso dia a dia e muitas vezes nem a percebemos.

==============================================

A página de Perguntas Frequentes (FAQ) do ENEM esclarece o uso da TRI:

“16. As questões da prova terão pesos diferentes?

A nova prova do Enem será estruturada na metodologia da Teoria da Resposta ao Item (TRI), que garante a comparabilidade das notas entre diferentes edições a partir da calibração do grau de dificuldade das questões. Dessa forma, diferentemente dos anos anteriores, as questões da prova do Enem serão distribuídas em graus diferenciados de complexidade. Isso significa que, no cálculo final da nota em cada área, as questões mais difíceis valem mais que as questões menos complexas.”

Maiores informações sobre o ENEM podem ser obtidas em www.enem.inep.gov.br

O livro (retirado do site da editora):

Esta obra cobre cinco tópicos principais: dados, classificação, análise de associação, agrupamento e detecção de anomalias. Exceto pela detecção de anomalias, cada uma destas áreas é coberta em um par de capítulos. Para classificação, análise de associação e agrupamento, o capítulo introdutório cobre conceitos básicos, algoritmos representativos e técnicas de avaliação, enquanto que o capítulo mais avançado discute conceitos e algoritmos avançados. O objetivo é fornecer ao leitor uma compreensão dos fundamentos da mineração de dados, embora ainda assim cobrindo muitos tópicos avançados importantes. Devido a esta abordagem, o livro é útil tanto como ferramenta de aprendizagem quanto como referência. 
 

1 INTRODUÇÃO - 1
1.1 O Que É Mineração de Dados? - 3
1.2 Desafios Motivadores - 5
1.3 As Origens da Mineração de Dados - 7
1.4 Tarefas de Mineração de Dados - 8
1.5 Escopo e Organização do Livro - 13
1.6 Notas Bibliográficas - 15
1.7. Exercícios - 21

2 DADOS - 23
2.1 Tipos de Dados - 26
2.1.1. Atributos e Medidas - 27
2.1.2. Tipos de Conjuntos de Dados - 34
2.2 Qualidade dos Dados - 43
2.2.1 Questões de Medição e Coleta de Dados - 44
2.2.2 Questões Relacionadas a Aplicações - 52
2.3 Pré-Processamento de Dados - 53
2.3.1 Agregação - 54
2.3.2 Amostragem - 56
2.3.3 Redução da Dimensionalidade - 60
2.3.4 Seleção de Subconjunto de Característica - 62
2.3.5 Criação de Recursos (Características) - 66
2.3.6 Discretização e Binarização - 69
2.3.7 Transformação de Variáveis - 75
2.4 Medidas de Semelhança e Diferença - 78
2.4.1 Fundamentos - 78
2.4.2 Semelhança e Diferença entre Atributos Simples - 81
2.4.3 Diferenças Entre Objetos de Dados - 82
2.4.4 Semelhanças Entre Objetos de Dados - 86
2.4.5 Exemplos de Medidas de Proximidade - 87
2.4.6 Questões Relacionadas ao Cálculo de Proximidade - 95
2.4.7 Selecionando a Medida de Proximidade Correta - 98
2.5 Notas Bibliográficas - 100
2.6 Exercícios - 105

3 EXPLORANDO OS DADOS - 115
3.1 O Conjunto de Dados Íris - 116
3.2 Estatísticas de Resumo - 117
3.2.1 Frequencias e o Modo - 118
3.2.2 Porcentagens - 119
3.2.3 Medidas de Localização: Média e Mediana - 120
3.2.4 Medidas de Dispersão: Faixa e Variância - 121
3.2.5 Estatísticas de Resumo com Múltiplas Variáveis - 123
3.2.6 Outras Formas de Resumir os Dados - 124
3.3 Visualização - 125
3.3.1 Motivações para a Visualização - 125
3.3.2 Conceitos Gerais - 126
3.3.3 Técnicas - 131
3.3.4 Visualizando Dados de Dimensões Maiores - 147
3.3.5 O Que Deve e o Que Não Deve Ser Feito -154
3.4 OLAP e Análise de Dados Multidimensionais - 155
3.4.1 Representando Dados da Íris como uma Matriz Multidimensional - 156
3.4.2 Dados Multidimensionais: O Caso Geral - 158
3.4.3 Analisando Dados Multidimensionais - 161
3.4.4 Comentários Finais Sobre a Análise de Dados Multidimensionais - 165
3.5 Notas Bibliográficas - 165
3.6 ExercÌcios - 168

4 CLASSIFICAÇÃO: CONCEITOS BÁSICOS, ÁRVORES DE DECISÃO
E AVALIAÇÃO DE MODELOS - 171
4.1 Preliminares - 172
4.2 Abordagem Geral para a Resolução de um Problema de Classificação - 174
4.3 Indução da Árvore de Decisão - 176
4.3.1 Como uma árvore de Decisão Funciona - 176
4.3.2 Como Construir uma Árvore de Decisão - 179
4.3.3 Métodos para Expressar Condições de Teste de Atributos - 183
4.3.4 Métricas para Selecionar a Melhor Divisão - 186
4.3.5 Algoritmo para Indução de Árvore de Decisão - 195
4.3.6 Um Exemplo: Detecção de Robô Web - 197
4.3.7 Características de Indução de Árvore de Decisão - 200
4.4 Overfitting de Modelo - 204
4.4.1 Overfitting Devido à Presença de Ruído - 207
4.4.2 Overfitting Devido a Falta de Amostras Representativas - 209
4.4.3 Overfitting e o Procedimento de Comparação Múltipla - 211
4.4.4 Estimativa de Erros de Generalização - 212
4.4.5 Lidando com Overfitting na Indução de Árvores de Decisão - 218
4.5 Avaliando o Desempenho de um Classificador - 220
4.5.1 Método Holdout - 221
4.5.2 Sub-Amostragem Aleatória - 222
4.5.3 Validação Cruzada - 222
4.5.4 Bootstrap - 223
4.6 Métodos para Comparar Classificadores - 224
4.6.1 Avaliando um Intervalo de Confiança Quanto a Precisão - 224
4.6.2 Comparando o Desempenho de Dois Modelos - 226
4.6.3 Comparando o Desempenho de Dois Classificadores - 228
4.7 Notas Bibliográficas - 229
4.8 Exercícios - 235

5 CLASSIFICAÇÃO: TÉCNICAS ALTERNATIVAS - 245
5.1 Classificador Baseado em Regras - 245
5.1.1 Como um Classificador Baseado em Regras Funciona - 248
5.1.2 Esquemas de Ordenação de Regras - 250
5.1.3 Como Construir um Classificador Baseado em Regras - 252
5.1.4 Métodos Diretos de Extração de Regras - 252
5.1.5 Métodos Indiretos de Extração de Regras - 261
5.1.6 Características de Classificadores Baseados em Regras - 264
5.2 Classificadores de Vizinho Mais Próximo - 264
5.2.1 Algoritmo - 266
5.2.2 Características de Classificadores de Vizinho mais Próximo - 268
5.3 Classificadores Bayesianos - 269
5.3.1 O Teorema de Bayes - 270
5.3.2 Usando o Teorema de Bayes para Classificação - 271
5.3.3 O Classificador de Bayes Simples - 273
5.3.5 Redes de Crenças Bayesianas - 284
5.4 Rede Neural Artificial (ANN) - 291
5.4.1 Perceptron - 291
5.4.2 Rede Neural Artificial Multicamadas - 296
5.4.3 Características da ANN - 302
5.5 Support Vector Machine (SVM) - 303
5.5.1 Hiperplanos de Margem Máxima - 303
5.5.2 SVM Linear: Caso Separável - 306
5.5.3 SVM Linear: Caso n„o Separável - 314
5.5.4 SVM Não Linear - 319
5.5.5 Características de SVM - 326
5.6 Métodos de Grupos - 327
5.6.1 Raciocínio do Método de Grupo - 327
5.6.2 Métodos para Criar um Classificador de Grupo - 329
5.6.3 Decomposição de Variância na Tendência - 332
5.6.4 Bagging - 335
5.6.5 Boosting - 338
5.6.6 Florestas Aleatórias - 344
5.6.7 Comparação Empírica entre Métodos de Conjunto - 349
5.7 O Problema do Desequilíbrio de Classes - 350
5.7.1 Métricas Alternativas - 351
5.7.2 A Curva Característica de Operação de um Receptor - 354
5.7.3 Aprendizagem Sensível ao Custo - 358
5.7.4 Abordagens Baseadas em Amostragens - 362
5.8 O Problema de Múltiplas Classes - 363
5.9 Notas Bibliográficas - 367
5.10 Exercícios - 375

6 ANÁLISE ASSOCIATIVA:ALGORITMOS E CONCEITOS BÁSICOS - 389
6.1. Definição do Problema - 391
6.2 Geração de Conjuntos de Itens Frequentes - 395
6.2.1 O Princípio Apriori - 397
6.2.2 Geração de Conjuntos de Itens Frequentes no Algoritmo Apriori - 399
6.2.3. Geração de Candidatos e Poda - 402
6.2.4 Contagem de Suporte - 407
6.2.5 Complexidade Computacional - 411
6.3 Geração de Regras - 416
6.3.1 Poda Baseada em Confiança - 416
6.3.2 Geração de Regras no Algoritmo Apriori - 417
6.3.3 Um Exemplo: Registros de Votos em Congresso - 419
6.4 Representação Compacta de Conjuntos de Itens Frequentes - 421
6.4.1 Conjuntos Máximos de Itens Frequentes - 422
6.4.2 Conjuntos Fechados de Itens Frequentes - 423
6.5 Métodos Alternativos para Geração de Conjuntos de Itens Frequentes - 428
6.6 Algoritmo FP-Grow - 433
6.6.1 Representação Árvore FP - 434
6.6.2 Geração de Conjuntos de Itens Frequentes no Algoritmo FP-Growth - 437
6.7 Avaliação dos Padrões de Associação - 442
6.7.1 Medidas Objetivas de Interesse - 443
6.7.2 Medidas Além de Pares de Variáveis Binárias - 456
6.7.3 Paradoxo de Simpson - 458
6.8 Efeito da Distribuição Irregular do Suporte - 460
6.9 Notas Bibliográficas - 465
6.10 Exercícios - 481

7 ANÁLISE DE ASSOCIA«ÃO: CONCEITOS AVAN«ADOS - 495
7.1 Lidando com Atributos Categorizados - 495
7.2.1 Métodos Baseados em Discretização - 499
7.2.2 Métodos Baseados em Estatísticas - 504
7.2.3 Métodos sem Discretização - 506
7.3 Lidando com uma Hierarquia de Conceitos - 509
7.4 Padrões Sequenciais - 512
7.4.1 Formulação de Problemas - 512
7.4.1 Descoberta de Padrões Sequenciais - 515
7.4.3 Restrições de Tempo - 520
7.4.4 Esquemas Alternativos de Contagem - 524
7.5 Padrões de Subgrafos - 527
7.5.1 Grafos e Subgrafos - 528
7.5.2 Mineração de Subgrafos Frequentes - 530
7.5.3 Método do tipo Apriori - 533
7.5.4 Geração de Candidatas - 534
7.5.5 Poda de Candidatos - 541
7.5.6 Contagem de Suporte - 544
7.6 Padrões Infrequentes - 545
7.6.1 Padrões Negativos - 546
7.6.2 Padrões Correlacionados Negativamente - 546
7.6.3 Comparações Entre Padrões Infrequentes, Padrões Negativis e Padrões Correlacionados Negativamente - 548
7.6.4 Técnicas para Minerar Padrões Infrequentes Interessantes - 550
7.6.5 Técnicas Baseadas em Mineração de Padrões Negativos - 552
7.6.6 Técnicas Baseadas em Expectativa de Suporte - 554
7.7 Notas Bibliográficas - 559
7.8 Exercícios - 564

8 ANÁLISE DE GRUPOS: CONCEITOS BÁSICOS E ALGORITMOS - 581
8.1 Visão Geral - 584
8.1.1 O Que É Análise de Grupos? - 585
8.1.2 Diferentes Tipos de Grupos - 586
8.1.3 Diferentes Tipos de Agrupamentos - 589
8.2 K-means - 593
8.2.1 O Algoritmo K-means Básico - 593
8.2.2 K-means: Questões Adicionais - 603
8.2.3 Dividindo K-means - 606
8.2.4 K-means e Diferentes Tipos de Grupos - 608
8.2.5 Pontos Fortes e Fracos - 609
8.2.6 K-means como um Problema de Otimização - 611
8.3 Agrupamento Hierárquico Aglomerativo - 614
8.3.1 Algoritmo de Agrupamento Hierárquico Aglomerativo Básico - 615
8.3.2 Técnicas Específicas - 618
8.3.3 A Fórmula Lance-Williams para Proximidade de Grupos - 623
8.3.4 Questões Chave no Agrupamento Hierárquico - 624
8.3.5 Pontos Fortes e Fracos - 626
8.4 DBSCAN - 626
8.4.1 Densidade Tradicional: Abordagem Baseada em Centro - 627
8.4.2 O Algoritmo DBSCAN - 628
8.4.3 Pontos Fortes e Fracos - 632
8.5 Avaliação de Grupos - 634
8.5.1 Visão Geral - 635
8.5.2 Avaliação de Grupos não Supervisionados Usando Coesão e Separação - 637
8.5.3 Avaliação de Grupos não Supervisionada Usando a Matriz de Proximidade - 645
8.5.4 Avaliação Não Supervisionada de Agrupamentos Hierárquicos - 648
8.5.6 Tendência de Agrupamento - 651
8.5.7 Medidas Supervisionadas de Validade de Grupos - 652
8.5.8 Avaliando a Significância de Medidas de Validade de Grupos - 658
8.6 Notas Bibliográficas - 660
8.7 Exercícios - 665

9 ANÁLISE DE GRUPOS: QUEST’ES ADICIONAIS E ALGORITMOS - 677
9.1 Características de Dados, Grupos e Algoritmos de Agrupamento - 678
9.1.1 Exemplo: Comparando K-means com DBSCAN - 678
9.1.2 Características de Dados - 680
9.1.3 Características de Grupos - 682
9.1.4 Características Gerais de Algoritmos de Agrupamento - 684
9.2 Agrupamentos Baseados em Protótipos - 686
9.2.1 Agrupamento Difuso - 688
9.2.2 Agrupamentos Usando Modelos de Mistura - 694
9.2.3 Mapas Auto-Organizados (SOM) - 707
9.3 Agrupamentos Baseados em Densidade - 714
9.3.1 Agrupamentos Baseados em Grades - 715
9.3.2 Agrupamento de Subespaços - 719
9.3.3 DENCLUE: Um Esquema Baseada no Núcleo para Agrupamentos Baseados em Densidade - 724
9.4 Agrupamento Baseado em Grafos - 729
9.4.1 Dispersão - 730
9.4.2 Agrupamento de Árvore de Dispersão Mínima (MST) - 732
9.4.3 OPOSSUM: Particionamento Ótimo de Semelhanças Usando METIS - 733
9.4.4 Chameleon: Agrupamento Hierárquico com Modelagem Dinâmica - 734
Semelhança de Vizinhos Compartilhados Mais Próximos - 742
9.4.6 O Algoritmo de Agrupamento de Jarvis-Patrick - 746
9.4.7 Densidade SNN - 748
9.4.8 Agrupamento Baseado em Densidade SNN - 749
9.5 Algoritmos de Agrupamento Escalável - 752
9.5.1 Escalabilidade: Abordagens e Questões Gerais - 752
9.5.2 BIRCH - 756
9.5.3 CURE - 758
9.6 Qual Algoritmo de Agrupamento? - 763
9.7 Notas Bibliográficas - 767
9.8 Exercícios - 773

10 DETECÇÃO DE ANOMALIAS - 777
10.1 Preliminares - 779
10.1.1 Causas de Anomalias - 779
10.1.2 Abordagens para a Detecção de Anomalias - 781
10.1.3 O Uso de Rótulos de Classes - 782
10.1.4 Questões - 783
10.2 Abordagens Estatísticas - 786
10.2.1 Detectar Elementos Estranhos em uma Distribuição Normal Univariada - 787
10.2.2 Elementos Estranhos em uma Distribuição Normal Multivariável - 789
10.2.3 Uma Abordagem de Mistura de Modelos para Detecção de Anomalias - 791
10.2.4 Pontos Fortes e Fracos - 794
10.3 Detecção de Elementos Estranhos Baseada em Proximidade - 794
10.3.1 Pontos Fortes e Fracos - 795
10.4 Detecção de Elementos Estranhos Baseada em Densidade - 797
10.4.1 Detecção de Elementos Estranhos Usando Densidade Relativa - 798
10.4.2 Pontos Fortes e Fracos - 800
10.5 Técnicas Baseadas em Agrupamento - 801
10.5.1 Avaliando a Extensão na Qual um Objeto Pertence a um Grupo - 802
10.5.2 Impacto dos Elementos Estranhos sobre o Agrupamento Inicial - 804
10.5.3 O N˙mero de Grupos a Usar - 805
10.5.4 Pontos Fortes e Fracos - 805
10.6 Notas Bibliográficas - 806
10.7 Exercícios - 813

A- ÁLGEBRA LINEAR - 819
A.1 Vetores - 819
A.1.1 Definição - 819
A.1.2 Adição de Vetores e Multiplicação por um Escalar - 820
A.1.3 Espaços de Vetores - 821
A.1.4 O Produto de Ponto, Ortogonalidade e Projeções Ortogonais - 822
A.1.5 Vetores e Análise de Dados - 824
A.2 Matrizes - 826
A.2.1 Matrizes: Definições - 826
A.2.2 Matrizes: Adição e Multiplicação por um Escalar - 827
A.2.3 Matrizes: Multiplicação - 829
A.2.4 Transformações Lineares e Matrizes Inversas - 830
A.2.5 Eigenvalue e Decomposição de Valor Singular - 833
A.2.6 Matrizes e Análises de Dados - 835
A.3 Notas Bibliográficas - 837

B- REDUÇÃO DA DIMENSIONALIDADE - 839
B.1 PCA e SVD - 839
B.1.1 Análise dos Componentes Principais (PCA) - 840
B.1.2 SVD - 845
B.2 Outras Técnicas de Redução de Dimensionalidade - 848
B.2.1 Análise de Fatores - 848
B.2.2 Locally Linear Embedding (LLE) - 850
B.2.3 Escala Multidimensional, FastMap e ISOMAP - 852
B.2.4 Questões Comuns - 856
B.3 Notas Bibliográficas - 857

C- PROBABILIDADE E ESTATÕSTICA - 861
C.1 Probabilidade - 861
C.1.1 Valores Esperados - 864
C.2 Estatística - 866
C.2.1 Avaliação de Ponto - 866
C.2.2 Teorema do Limite Central - 867
C.2.3 Avaliação de Intervalo - 868
C.3 Teste de Hipóteses - 869

D- REGRESSÃO - 873
D.1 Preâmbulo - 873
D.2 Regressão Linear Simples - 874
D.2.1 Método de Menos Quadrados - 875
D.2.2 Analisando Erros de Regressão - 878
D.2.3 Analisando a Qualidade do Ajuste - 880
D.3 Regressão Liner Multivariável .881
D.4 Métodos de Regressão Alternativos ao de Menos Quadrados - 882

E- OTIMIZAÇÃO - 885
E.1 Otimização sem Restrições - 885
E.1.1 Métodos Numéricos - 889
E.2 Otimização com Restrições - 892
E.2.1 Restrições de Igualdade - 893
E.2.2 Restrições de Desigualdade - 894

ÍNDICE REMISSIVO - 897

Pang-Ning Tan - Pang-Ning Tan, é professor assistente no departamento de Ciência da Computação e Engenharia na Universidade Estadual de Michigan. Tem cerfificado de PHD em Ciência da Computação pela Universidade de Minnesota. Suas Pesquisas focam o desenvolvimento e aplicação em algoritmos na mineração de dados para uma grande variedade de aplicações incluindo informações médicas.

Michael Steinbach - Michael Steinbach graduado em Matemática, Estatística e PHD em Ciência da Computação na Universidade de Minnesota. É atualmente um pesquisador associado ao Departamento de Ciência da Computação e Engenheiro na Universidade de Minnesota. Anteriormente, desenvolveu uma variedade de softwares de engenharia, análise e design para Silicon Biology, Racotek e NCR. Sua pesquisa é direcionada a área de mineração de dados, bioinformática e estatística. Foi autor de mais de 20 artigos de pesquisa e é co-autor do livro Data Mining. É membro do Instituto de Engenharia Eletro e Eletrônicos(IEEE) e o Associação para Marquinaria Computacional.

Vipin Kumar - Vipin Kumar, atualmente é chefe do Departamento de Ciência da Computação e Engenharia da Universidade de Minnesota. Kumar foi organizador e co-organizador para várias conferências e workshops internacionais na área de mineração de dados. Em 2001 foi um dos fundadores da SIAM (Sociedade para Matemáticos Industriais e Aplicados), ficou como diretor até 2007.
>> Site: http://