Campus Party2010

Ary Fagundes Bressane NetoFlávio Soares Corrêa da Silva

LIDET – USPJaneiro 2010

Ary Fagundes Bressane Neto Graduação: BCC, UNESP/Bauru (2007) Mestrado: CC, USP/Butantã (conclusão prevista para 2010) Experiência diversificada em Ciência da Computação Pesquisador do LIDET

Flávio Soares Corrêa da Silva Graduação: POLI-USP (1984) Mestrado: POLI-USP (1989) PhD: Inteligência Artificial, Edinburgh University (1992) Livre-docência: USP (1999) Experiência diversificada em CC, com foco em IA Pesquisador do LIDET

Universidade de São Paulo

Fundação: 1934 Ranking internacional: aprox. 100ª no mundo 56 mil alunos de graduação 25 mil alunos de pós-graduação 6 mil docentes Aprox. 10 % da produção científica do Brasil

Departamento de Ciência da Computação

Início de atividades: 1972 Mais de mil alunos de graduação formados 39 docentes em atividade Reconhecido centro de pesquisas e ensino, no Brasil e no

Exterior

LIDET: Laboratory of Interactivity and Digital Entertainment Technology Início de atividades: 2005 Intensas atividades em pesquisa e ensino Inteligência Artificial Aplicada Jogos de Computador Sistemas Interativos Inteligentes Governabilidade Eletrônica

Atividades em colaboração com LIAMF (Laboratório de Lógica, Inteligência Artificial e Métodos Formais da USP) e CCSL (Centro de Competência em Software Livre da USP)

Cooperação internacional com centros de pesquisa no Chile, Reino Unido, Itália e Espanha

Coordenador: Flávio Soares Corrêa da Silva Equipe: estudantes de mestrado (6) e doutorado (6)

Introdução sobre Data Mining

Apresentação e funcionamento do WEKA

WEKA + Java

“Nós estamos afogados em informação masfamintos por conhecimento”

John Naisbett

1. World Data Centre for Climate 6 petabytes de dados

2. National Energy Research Scientific Computing Center (EUA)

2.8 petabytes de dados

3. AT&T 323 terabytes de informação 1.9 trilhões de registros de chamadas telefônicas

4. Google 91 milões de pesquisas por dia 33 trilhões de registros

Fonte: http://www.businessintelligencelowdown.com/

5. Sprint 2.85 trilhões de linhas no banco de dados 365 milhões de registros de ligações telefonicas por dia

6. ChoicePoint 250 terabytes de dados pessoais Informação de 250 milhões de pessoas

7. YouTube 100 milhões de vídeos assisitdos por dia 65,000 vídeos adicionados por dia 60% de todos os vídeos assistidos online 45 terabytes de vídeos

Fonte: http://www.businessintelligencelowdown.com/

8. Amazon 59 milhões de usuários ativos 42 terabytes de dados

9. Central Intelligence Agency (EUA) Informações sobre mais de 250 países e instituições Número desconhecido de informações confidenciais

10. Library of Congress (EUA) 130 milhões de itens (livros, fotografias, mapas, etc.) 29 milhões de livros 10,000 novos itens adicionados por dia 5 milhões de documentos digitais 20 terabytes de informação em texto

Fonte: http://www.businessintelligencelowdown.com/

“A habilidade de mandar, dirigir e selecionar informação pode chegar a ser uma fonte de

poder comparável aos grandes recursos naturais, tecnológicos e econômicos”

Wilbur Schramm

Medicina Diagnóstico Sintomas Exames de imagem Exames laboratoriais

Departamento de Vendas Clientes com diferentes perfis Clientes procurando sugestões

Ciência Seqüenciamento genético

Design Novos materiais

Fonte: http://www.businessintelligencelowdown.com/

Departamento de Vendas (CRM) Presencial Virtual

Departamento de Marketing

Investimentos

Aplicações de Recursos do Governo

Bases de Dados integradas para consultas analíticas de históricos

Qual a tecnologia atende a essa demanda?

KDD (Knowledge Discovery in Databases)

“Descoberta de conhecimento de Base de

Dados é um processo não-tivial de

identificação de padrões válidos, novos,

potencialmente úteis e compreensíveisembutidos nos dados”

Usama Fayyad, Gregory Piatetsky-Shapiro,

Padhraic Smyth

Wal Mart Banco Itaú Bank of America

Banco Nossa Caixa Full Tilt Poker

The KDD Process for Extracting UsefulKnowledge from Volumes of Data

Mineraçãode Dados

AtividadesPreditivas

Classificação Regressão

AtividadesDescritivas

Regras de Associação

Sumarização

Clusterização

Soluções Proprietárias

SPSS Clementine SAS Enterprise Miner STATISTICA Data Miner

IBM Intelligent Miner Data Mining Suite Oracle Data Mining Microsoft SQL Server (Microsoft BI)

Excel

Matlab

Soluções Open Source

WEKA RapidMiner KNIME

R

Código próprio

Waikato Environment for Knowledge Analysis

Univesidade de Waikato

Projeto financiado pelo Governo da NZ (1993)

Desenvolver uma ferramenta no estado da arte Explorar os campos de aplicação Desenvolver novos métodos

Open Source (GNU General PublicLicense)

100% Java

Ferramentas Pré-processamento Sumarização Classificação Regressão Clusterização Regras de Associação Visualização

http://www.cs.waikato.ac.nz/ml/weka/

Stable GUI version 3.6 Windows Mac OS X Linux java -jar weka.jar

Book version 3.4

Developer version 3.7

@RELATION iris

@ATTRIBUTE sepallength REAL

@ATTRIBUTE sepalwidth REAL

@ATTRIBUTE petallength REAL

@ATTRIBUTE petalwidth REAL

@ATTRIBUTE class {Iris-setosa,

Iris-versicolor, Iris-virginica}

@DATA

5.1,3.5,1.4,0.2,Iris-setosa

4.9,3.0,1.4,0.2,Iris-setosa

4.7,3.2,1.3,0.2,Iris-setosa

4.6,3.1,1.5,0.2,Iris-setosa

@RELATION iris

@ATTRIBUTE sepallength REAL

@ATTRIBUTE sepalwidth REAL

@ATTRIBUTE petallength REAL

@ATTRIBUTE petalwidth REAL

@ATTRIBUTE class {Iris-setosa,

Iris-versicolor, Iris-virginica}

@DATA

5.1,3.5,1.4,0.2,Iris-setosa

4.9,3.0,1.4,0.2,Iris-setosa

4.7,3.2,1.3,0.2,Iris-setosa

4.6,3.1,1.5,0.2,Iris-setosa

@relation <relation-name>

@RELATION iris

@ATTRIBUTE sepallength REAL

@ATTRIBUTE sepalwidth REAL

@ATTRIBUTE petallength REAL

@ATTRIBUTE petalwidth REAL

@ATTRIBUTE class {Iris-setosa,

Iris-versicolor, Iris-virginica}

@DATA

5.1,3.5,1.4,0.2,Iris-setosa

4.9,3.0,1.4,0.2,Iris-setosa

4.7,3.2,1.3,0.2,Iris-setosa

4.6,3.1,1.5,0.2,Iris-setosa

@attribute <attribute-name> <datatype>

integerReal<nominal-specification>

stringdate [<date-format>]

@RELATION iris

@ATTRIBUTE sepallength REAL

@ATTRIBUTE sepalwidth REAL

@ATTRIBUTE petallength REAL

@ATTRIBUTE petalwidth REAL

@ATTRIBUTE class {Iris-setosa,

Iris-versicolor, Iris-virginica}

@DATA

5.1,3.5,1.4,0.2,Iris-setosa

4.9,3.0,1.4,0.2,Iris-setosa

4.7,3.2,1.3,0.2,Iris-setosa

4.6,3.1,1.5,0.2,Iris-setosa

@data

@RELATION iris

@ATTRIBUTE sepallength REAL

@ATTRIBUTE sepalwidth REAL

@ATTRIBUTE petallength REAL

@ATTRIBUTE petalwidth REAL

@ATTRIBUTE class {Iris-setosa,

Iris-versicolor, Iris-virginica}

@DATA

5.1,3.5,1.4,0.2,Iris-setosa

4.9,3.0,1.4,0.2,Iris-setosa

4.7,3.2,1.3,0.2,Iris-setosa

4.6,3.1,1.5,0.2,Iris-setosa

Classificação Árvores de Decisão Redes Neurais Artificiais

Clusterização Kmeans

Regras de Associação APriori

Técnica que constrói um classificador utilizando uma estrutura de árvore onde os nós folhas representam as classes e os nós internos representam um teste sobre um atributo

Exemplos Oferta de crédito Diagnóstico médico

Figura Geométrica# lados

Triângulo

=3 >3

Poupador Bens Rendimento anual

Oferecer Crédito

Cliente1 Médio Alto 75.000 Sim

Cliente2 Baixo Baixo 50.000 Não

Cliente3 Alto Médio 25.000 Não

Cliente4 Médio Médio 50.000 Sim

Cliente5 Baixo Médio 100.000 Sim

Cliente6 Alto Alto 25.000 Sim

Cliente7 Baixo Baixo 25.000 Não

Cliente8 Médio Médio 75.000 Sim

Poupador Bens Rendimento anual

Oferecer Crédito

Cliente7 Baixo Baixo 25.000 Não

Cliente3 Alto Médio 25.000 Não

Cliente6 Alto Alto 25.000 Sim

Cliente2 Baixo Baixo 50.000 Não

Cliente4 Médio Médio 50.000 Sim

Cliente1 Médio Alto 75.000 Sim

Cliente8 Médio Médio 75.000 Sim

Cliente5 Baixo Médio 100.000 Sim

Rendimento

Oferecer Crédito

=25.000=50.000 >=75.000

Poupador Bens Rendimento anual

Oferecer Crédito

Cliente7 Baixo Baixo 25.000 Não

Cliente3 Alto Médio 25.000 Não

Cliente6 Alto Alto 25.000 Sim

Cliente2 Baixo Baixo 50.000 Não

Cliente4 Médio Médio 50.000 Sim

Cliente1 Médio Alto 75.000 Sim

Cliente8 Médio Médio 75.000 Sim

Cliente5 Baixo Médio 100.000 Sim

Rendimento

Bens BensOferecer Crédito

= 25.000= 50.000

>= 75.000

Não Oferecer Crédito

Oferecer Crédito

Não Oferecer Crédito

Oferecer Crédito

≠ Alto = Alto = Médio = Alto

Poupador Bens Rendimento anual

Oferecer Crédito

Cliente1 Médio Alto 75.000 Sim

Cliente2 Baixo Baixo 50.000 Não

Cliente3 Alto Médio 25.000 Não

Cliente4 Médio Médio 50.000 Sim

Cliente5 Baixo Médio 100.000 Sim

Cliente6 Alto Alto 25.000 Sim

Cliente7 Baixo Baixo 25.000 Não

Cliente8 Médio Médio 75.000 Sim

Rendimento

Bens BensOferecer Crédito

=25.000=50.000

>=75.000

Não Oferecer Crédito

Oferecer Crédito

Não Oferecer Crédito

Oferecer Crédito

≠ Alto =Alto Médio Alto

Modelos matemáticos que permite aprendizado e generalização Esse aprendizado está associado a capacidade de adaptar seus parâmetros como conseqüência da sua iteração com o meio externo Estrutura similar as redes neurais biológicas

Exemplos Oferta de crédito Diagnóstico médico Detectar fraudes

X1

X2

X3

Xn

Wn

W3

W2

W1

u f(u) y = f(u)

X1

X2

X3

Xn

Wn

W3

W2

W1

u f(u) y = f(u)

u = valor de ativaçãof(u) = função de propagação

Homem / Mulher

Idade

IMC

Consumo cigarro

Consumo álcool

Atividade física

Risco Câncer

CamadaEntrada

CamadaEscondida

CamadaSaída

Técnica que mapeia um item em um dos vários clusters, onde clusters são agrupamentos de itens de dados baseados em alguma métricas de similaridade. Permite compreender os agrupamentos naturais ou estruturas subjacentes a um conjunto de dados.

Exemplos: Identificação de grupos distintos de clientes (público-alvo) Identificar a taxonomia de plantas e animais Agrupar estudantes por desempenho e dificuldades para adotar

estratégias de ensino mais eficientes e adequadas

Atributo1 Atributo2

Item1 1 1

Item2 1 2

Item3 2 2

Item4 4 5

Item5 5 5

Item6 5 6

KMeans(# de Clusters)

KMeans(2)

0

1

2

3

4

5

6

7

0 1 2 3 4 5 6 7

0

1

2

3

4

5

6

7

0 1 2 3 4 5 6 7

Passo 1 – Determinar os centróides

Passo 2 – Calcular a distância entre cada item e os centróides

P(1,1) P(1,2) P(2,2) P(4,5) P(5,5) P(5,6)

C1 0,0 1,0 1,4 5,0 5,7 6,4

C2 1,0 0,0 1,0 4,2 5,0 5,7

0

1

2

3

4

5

6

7

0 1 2 3 4 5 6 7

Passo 3 – Associar cada item a um grupo

P(1,1) P(1,2) P(2,2) P(4,5) P(5,5) P(5,6)

C1 0,0 1,0 1,4 5,0 5,7 6,4

C2 1,0 0,0 1,0 4,2 5,0 5,7

0

1

2

3

4

5

6

7

0 1 2 3 4 5 6 7

Passo 4 – Recalcular o centróide como a média dos itens do grupo

P(1,1) P(1,2) P(2,2) P(4,5) P(5,5) P(5,6)

C1 0,0 1,0 1,4 5,0 5,7 6,4

C2 1,0 0,0 1,0 4,2 5,0 5,7

0

1

2

3

4

5

6

7

0 1 2 3 4 5 6 7

Passo 2 – Calcular a distância entre cada item e os centróides

P(1,1) P(1,2) P(2,2) P(4,5) P(5,5) P(5,6)

C1 0,0 1,0 1,4 5,0 5,7 6,4

C2 3,1 2,6 1,7 2,0 2,5 3,4

0

1

2

3

4

5

6

7

0 1 2 3 4 5 6 7

Passo 3 – Associar item ponto a um grupo

P(1,1) P(1,2) P(2,2) P(4,5) P(5,5) P(5,6)

C1 0,0 1,0 1,4 5,0 5,7 6,4

C2 3,1 2,6 1,7 2,0 2,5 3,4

0

1

2

3

4

5

6

7

0 1 2 3 4 5 6 7

Passo 4 – Recalcular o centróide como a média dos itens do grupo

P(1,1) P(1,2) P(2,2) P(4,5) P(5,5) P(5,6)

C1 0,0 1,0 1,4 5,0 5,7 6,4

C2 3,1 2,6 1,7 2,0 2,5 3,4

0

1

2

3

4

5

6

7

0 1 2 3 4 5 6 7

Passo 2 – Passo 3 – Passo 4 – Resultado Final

P(1,1) P(1,2) P(2,2) P(4,5) P(5,5) P(5,6)

C1 0,5 0,5 0,9 4,5 5,1 5,9

C2 5,6 4,9 4,2 0,7 0,4 0,7

0

1

2

3

4

5

6

7

0 1 2 3 4 5 6 7

O objetivo é encontrar um conjunto de atributos que quando presentes implicam na presença de outro conjunto de atributos

Exemplos: Análise de nota fiscal de compra Associação de palavras em textos Combate à corrupção

P1 P2 P3 P4 P5 P6

T1 x x x x x

T2 x x

T3 x x x

T4 x x

T5 x x

Apriori (Suporte mínimo, Confiança)

Apriori (2, 60%)

P1 P2 P3 P4 P5 P6

T1 x x x x x

T2 x x

T3 x x x

T4 x x

T5 x x

Produto Freq.

P1 4

P2 4

P3 2

P4 1

P5 1

P6 2

Produto Freq.

P1 4

P2 4

P3 2

P6 2

Suporte mínimo = 2

P1 P2 P3 P4 P5 P6

T1 x x x x x

T2 x x

T3 x x x

T4 x x

T5 x x

Produto Freq.

P1, P2 3

P1, P3 1

P1, P6 2

P2, P3 2

P2, P6 1

P3, P6 0

Produto Freq.

P1, P2 3

P1, P6 2

P2, P3 2

Suporte mínimo = 2

P1 P2 P3 P4 P5 P6

T1 x x x x x

T2 x x

T3 x x x

T4 x x

T5 x x

Produto Freq.

P1, P2, P3 1

P1, P2, P6 1

P1, P3, P6 0

P2, P3, P6 0

Suporte mínimo = 2

VAZIO !!!

Produto Freq.

P1, P2 3

P1, P6 2

P2, P3 2

Produto Freq. Conf.

P1, P2 3 3/4 = 75%

P2, P1 3 3/4 = 75%

P1, P6 2 2/4 = 50%

P6, P1 2 2/2 = 100%

P2, P3 2 2/4 = 50%

P3, P2 2 2/2 = 100%

Confiança (A⇒B) = freqüência(AB) freqüência(A)

Confiança = 60%

Produto Freq. Conf.

P1, P2 3 3/4 = 75%

P2, P1 3 3/4 = 75%

P6, P1 2 2/2 = 100%

P3, P2 2 2/2 = 100%

P1 P2 P3 P4 P5 P6

T1 x x x x x

T2 x x

T3 x x x

T4 x x

T5 x x

Produto Freq. Conf.

P1, P2 3 3/4 = 75%

P2, P1 3 3/4 = 75%

P6, P1 2 2/2 = 100%

P3, P2 2 2/2 = 100%

{P1} ⇒ {P2}: sup_min = 3; conf=75%{P2} ⇒ {P1}: sup_min = 3; conf=75%{P6} ⇒ {P1}: sup_min = 2; conf=100%{P3} ⇒ {P2}: sup_min = 2; conf=100%

Escândalo dos “Cartões Coorporativos”

“Planalto pressiona e ministra da Igualdade Racial cai por uso irregular de cartão.”

“A ministra vinha resistindo ao pedido de demissão. Mas foi atropelada pela divulgação sobre o uso do cartão num freeshop (R$ 461,16), no aluguel sistemático de carros (mais de R$ 110 mil, sem licitação) e em seu período de férias (R$ 2.969,01), como revelou ontem a Folha. Matilde gastou R$ 171 mil com o cartão em 2007, a recordista entre os ministros.”

Folha de S. Paulo 02/02/2008

Escândalo dos “Cartões Coorporativos”

“Cartão de Pagamento do Governo Federal: uma Análise de Regras de Associação”Workshop Franco-Brasileiro sobre Mineração de Dados (2009)Dr. Michel Silva, Me. Marcelo Stopanovski, Me. Henrique Rocha, Bel. David CosacSecretaria de Prevenção da Corrupção e Informações Estratégicas, Controladoria-Geral da União

{“LOCAÇÃO DE AUTOMÓVEL SEM CONDUTOR”, “R$ 1000 a R$ 1500”} → {“SEC. ESPECIAL DE POLÍTICAS DE PROMOÇÃO DA IGUALDADE RACIAL”}: suporte = 1,15% e confiança = 86,67%.

Ressalta-se que esse exemplo é exatamente o pivô das discussões sobre cartões, configurado no aluguel de carros em viagens.

@relation weather.symbolic

@attribute outlook {sunny, overcast, rainy}@attribute temperature {hot, mild, cool}@attribute humidity {high, normal}@attribute windy {TRUE, FALSE}@attribute play {yes, no}

@datasunny,hot,high,FALSE,nosunny,hot,high,TRUE,no

overcast,hot,high,FALSE,yes

WEKA + Java

Bases de Dados integradas para consultas analíticas de históricos estão em todo lugar

Papel do profissional de Ciência da Computação

Data Mining (KDD) pode ser implementado em diversas áreas

WEKA é uma ferramenta flexível Diversos algoritmos Permite a descoberta de conhecimento tanto via interface com o

usuário quando embutida na aplicação do desenvolvedor Pode ser utilizada não somente para Data Mining

Integração de dados Otimização de algoritmos Incorporação de conhecimento prévio Visualização científica

Mineração em dados multimídia

Obrigado!

Ary Fagundes Bressane Netobressane@ime.usp.br

Flávio Soares Corrêa da Silvafcs@ime.usp.br