Apresentação - Mineração de Dadoseach.uspnet.usp.br/sarajane/wp-content/uploads/2015/08/aula01.pdf · KDD - Knowledge Discovery from Data Data Warehouse (Armaz em de dados) Data

Apresentacao - Mineracao de Dados

Clodoaldo A. M. Lima, Sarajane M. Peres

6 de agosto de 2015

Programa de Pos-Graduacao em Sistemas deInformacaoMestrado academico - EACH - USPhttp://ppgsi.each.usp.br

Clodoaldo A. M. Lima, Sarajane M. Peres Apresentacao - Mineracao de Dados 6 de agosto de 2015 1 / 39

http://ppgsi.each.usp.br

Os professores

Profa. Dra. Sarajane Marques Peres: possui graduacao em Ciencia da Computacao pela

Universidade Estadual de Maringa (1996), mestrado em Engenharia de Producao pela Universidade

Federal de Santa Catarina (1999) e doutorado em Engenharia Eletrica pela Universidade Estadual

de Campinas (2006). Atualmente e professora-pesquisadora, em regime de dedicacao exclusiva, da

Universidade de Sao Paulo, com credenciamento pleno no Programa de Pos Graduacao em

Sistemas de Informacao da USP. Tem experiencia na area de Ciencia da Computacao, com enfase

em Inteligencia Computacional. Atualmente esta pesquisando na area de Reconhecimento de

Padroes, Analise de Gestos e Analise de Textos. Atua como tutora do grupo PET-Sistemas de

Informacao da USP, sob o Programa de Educacao Tutorial do Ministerio da Educacao

http://lattes.cnpq.br/6265936760089757



Os professores

Prof. Dr. Clodoaldo Aparecido de Moraes Lima (Bolsista de Produtividade em Pesquisa do

CNPq - Nıvel 2 - CA EE - Engenharia Eletrica e Biomedica): possui graduacao em Adminstracao

de Empresa pela Faculdade de Ciencias Contabeis e Adm Machado Sobrinho (1995), graduacao em

Engenharia Eletrica pela Universidade Federal de Juiz de Fora (1997), mestrado (modalidade

Automacao), doutorado (modalidade Engenharia de Computacao) e pos-doutorado em Engenharia

Eletrica pela Universidade Estadual de Campinas (2000), (2004), (2005). Atualmente e

professora-pesquisadora, em regime de dedicacao exclusiva, da Universidade de Sao Paulo, com

credenciamento pleno no Programa de Pos Graduacao em Sistemas de Informacao da USP.

Desenvolve pesquisas na area de Processamento de Sinais, principalmente Sinais Biomedicos,

Aprendizado de Maquina, com enfase em Metodos de Kernel e de Comite de Maquinas, Sistemas

Biometricos, Modelagem nao-parametrica e Analise e Predicao de Series Temporais.




Os alunos

Alunos regulares: 21

nome

perıodo

orientador

area de pesquisa

dedicacao integral ou parcial (onde atua)

expectativa para a disciplina

Alunos especiais: 23

nome

primeira disciplina como especial (?)

futuro orientador (?)

area de pesquisa (?)

onde atua

expectativa para a disciplina


A disciplina

Objetivo

Capacitar o pesquisador na tarefa de exploracao e analise de dados a fim de descobrir

padroes e regras significativos e interessantes, por meio automatico ou

semi-automatico, considerando grandes quantidades dados.

Dinamica

aulas expositivas por um dos professores ou com a participacao dos dois

motivacao a leituras e discussoes em sala de aula

realizacao de trabalhos praticos fora da sala de aula

avaliacao por prova e realizacao de trabalhos praticos

Sylabus

Documento com informacoes basicas sobre a disciplina. Disponıvel no e-Tidia e na

homepage: http://each.uspnet.usp.br/sarajane/?page_id=10 .


http://each.uspnet.usp.br/sarajane/?page_id=10

A disciplina

Resumo do conteudo

tecnicas para pre-processamento de dados

algoritmos de classificacao

algoritmos de agrupamento

algoritmos de descoberta de regras de associacao

Datas mais importantes - avaliacoes individuais

5 de novembro: prova (P)

26 de novembro: entrega e apresentacao do trabalho T1

10 de dezembro: entrega do trabalho T2

xx de dezembro: prova substitutiva (fechada)

Media final

(P+T1)+T22


A disciplinaBibliografia geral

Han, J.; Kamber, M., Pei, J. Data Mining: Concepts and Technique. Series

Editor Morgan Kaufmann Publishers, 2nd Ed., 2005

Witten, I. H.; Frank, E. Data Mining: Practical Machine Learning Tools and

Techniques, Morgan Kaufmann, 2nd Ed, 2005.

livros e artigos cientıficos sobre diferentes tecnicas e algoritmos - indicados

pelos professores no decorrer da disciplina

Polıticas

A programacao de aulas e preliminar e esta sujeita a mudancas.

A programacao de prova sera alterada apenas por motivos consequentes de acoes ou determinacoes

da universidade.

Nao serao admitidos atrasos na entrega do trabalho, sendo que o aluno que nao entregar em dia

recebera nota 0 na respectiva avaliacao.

Nao existe abono de faltas – procure “guardar” os 25

Eventuais problemas referentes a disciplina deverao ser tratados PESSOALMENTE junto ao(s)

professor(es), em horario previamente agendado ou logo apos o termino das aulas.


TrabalhosT1 - Pre-processamento e Descoberta de Regras de Associacao

bases de dados UCI (Machine Learning Repository) ou Kaggle ou similares - ainda por definir;

pre-processamento

descoberta de regras de associacao

analise

entrega de relatorio e das codificacoes

apresentacao em aula (dinamica ainda a definir)

T2 - Pre-processamento e Construcao de Modelos Classificadores ou de Agrupamento

bases de dados (definidas pelos professores):

sinais ECG e/ou EMG

bases de dados textuais

sinais de movimento (3D)

pre-processamento

construcao de modelos classificadores ou de agrupamento - a escolha do aluno

analise

entrega de relatorio e das codificacoes

Para todos os trabalhos, serao permitidos o uso de frameworks (como WEKA) ou ambientes de programacao (R, MATLAB), desde que haja

documentacao disponıvel que permita conhecer e controlar os algoritmos que estao sendo aplicados.


Alinhando os conceitos ....

OLTP - OnLine Transactional Process

OLAP - OnLine Analytical Process

KDD - Knowledge Discovery from Data

Data Warehouse (Armazem de dados)

Data Mining (Mineracao de dados)


Suporte Operacional X Suporte Analıtico

Caracterısticas de uma situacao operacional (dia a dia):

Clientes fazem perguntas aos atendentes sobre a disponibilidade de

produtos e decidem por compra-los.

Em paralelo aos eventos de venda, produtos sao produzidos,

transportados e estocados. As informacoes sao atualizadas nos sistemas

correlatos.

Essas informacoes sao gerenciadas em gerenciadores de bancos de dados

e usadas para propositos operacionais.

Para responder as perguntas dos clientes, executar transacoes de venda

e outras tarefas operacionais, os atendentes (operadores) consultam

estes bancos de dados para obter informacoes operacionais.



Exemplo de situacao analıtica:

Um gerente de marca inicia uma sessao analıtica consultando sobre a

rentabilidade da marca por regiao.

cada numero obtido (de rentabilidade) refere-se a media de todos os

produtos da marcar comercializados em todas as lojas de cada regiao,

por perıodos determinados de tempo.

Cerca de centenas de milhares, ou milhoes, de “pedacos de dados” sao

transformados em numeros de rentabilidade → tratados de uma

informacao derivada de alto nıvel.

Se os numeros obtidos parecem nao usuais, o gerente precisa entao

iniciar uma busca sobre o porque eles nao sao usuais.



Atividades Operacionais Atividades AnalıticasMais frequentes Menos frequentesMais previsıveis Menos previsıveis

O montante de dados acessado O montante de dados acessado pornas consultas e menor consulta e maior

As consultas trabalham, As consultas trabalham,principalmente, com dados primarios principalmente, com dados derivados

(brutos, basicos)Requer dados atuais Requer dados passados, atuais

e projetadosPoucas, se existentes, derivacoes Muitas derivacoes complexas

complexas


Exercıcio

Negocios Suporte Operacional Suporte AnalıticoFazenda de ovelhas

(5000 a.c.)Comerciante de Veneza

(seculo 15)Transporte ferroviario

(seculo 19)Banco

(seculo 20)Varejo de vestuario

(seculo 20)Redes Sociais

(seculo 21)


Negocios Suporte Operacional Suporte AnalıticoFazenda de ovelhas Atividade para obter

(5000 a.c.) leite, la e carne

Comerciante de Veneza(seculo 15)

Transporte ferroviario(seculo 19)

Banco(seculo 20)

Varejo de vestuario(seculo 20)

Redes Sociais(seculo 21)


Negocios Suporte Operacional Suporte AnalıticoFazenda de ovelhas Atividade para obter Aumentar ou diminuir o

(5000 a.c.) leite, la e carne rebanho, permanecer oumudar de pasto

Comerciante de Veneza(seculo 15)

Transporte ferroviario(seculo 19)

Banco(seculo 20)

Varejo de vestuario(seculo 20)

Redes Sociais(seculo 21)


Negocios Suporte Operacional Suporte AnalıticoFazenda de ovelhas Atividade para obter Aumentar ou diminuir o

(5000 a.c.) leite, la e carne rebanho, permanecer oumudar de pasto

Comerciante de Veneza Comprar/vender tecidos Estabelecer precos,(seculo 15) ou especiarias escolher fornecedores e

criar linhas de produtosTransporte ferroviario Transportar produtos e Tracar as linhas, contratar

(seculo 19) pessoas funcionariosBanco Emprestar dinheiro e Lidar com taxas de juros,

(seculo 20) tomar dinheiro descobrir o mercado alvo,emprestado os clientes alvo

Varejo de vestuario Comprar e vender Como alocar prateleiras,(seculo 20) produtos, estocar, quando baixar precos,

transportar quanto comprarRedes Sociais Suportar gerenciamento de Descobrir perfis,

(seculo 21) mensagens, post, fotos analisar humor,e contas pessoais com e sugerir links.relacoes entre usuarios


KDD - Knowledge Discovery from Data

“Mineracao de dados” e uma das etapas do processo de descoberta de conhecimento.

Nao se trata de um sinonimo para KDD (e muito menos para BI - Business

Intelligence)

Descoberta de conhecimento como um processo consite de uma sequencia iterativa de

passos:

Limpeza de dados: remocao de ruıdo e de dados inconsistentes;

Integracao de dados: combinacao de multiplas fontes de dados;

Selecao de dados: escolha dos dados que sao relevantes para a analise pretendida;

Transformacao de dados: organizacao dos dados em uma forma apropriada paramineracao (por meio de operacoes de resumo ou agregacao, por exemplo);

Mineracao de dados: o processo inteligente aplicado para extracao de padroes;

Avaliacao de padroes: identificacao de padroes que realmente interessam erepresentam conhecimento, com base em medidas de “interessabilidade”(interestingness);

Apresentacao do conhecimento: visualizacao dos resultados por meio de tecnicas derepresentacao de conhecimento usadas para apresentar o conhecimento ao usuario.



Definicoes

OLTP

Sistemas de informacao preparados para executar transacoes online e processamento de consultas,

suportando operacoes de rotina de uma organizacao. Trabalham com sistema de gerenciamento de banco

de dados.

OLAP

Sistemas de informacao que organizam e apresentam dados em varios formatos com o objetivo de suportar

as diferentes necessidades de diferentes usuarios. Geralmente trabalham com sistemas de gerenciamento de

data warehouses.

Data Warehouse

Banco de dados mantido separadamente dos bancos de dados operacionais da organizacao. Ele contem

dados orientado a assuntos, integrados (a partir de fontes heterogeneas), variantes no tempo e nao volateis.

Mineracao de Dados

Processo para extracao de conhecimento de um grande montante de dados. Melhor seria nomear de

“knowledge mining”.


OLAP X Mineracao de Dados

Diferenca basica

As funcoes ou algoritmos tipicamente encontrados nas ferramentas OLAP (tais como

agregacao - nas suas mais variadas formas - de dimensoes) sao funcoes de modelagem

descritiva. Ja as funcoes ou algoritmos encontrados nas ferramentas de Mineracao de

Dados (tais como modelos de regressao, arvores de decisao, redes neurais artificiais,

algoritmos de clustering) sao funcoes de modelagem exploratoria e de descoberta de

padroes - embora tambem sejam consideradas formas de descrever os dados.

Caracterıstica OLAP

OLAP fornece estruturas de dados sofisticadas formada por dimensoes com hierarquias

e formas de realizar referencias cruzadas entre as dimensoes.

Caracterıstica Mineracao de Dados

Mineracao de dados entende o mundo em termos de variaveis e instancias.


OLAP

(a) Modelo Snowflake (b) Cubo de Dados


Mineracao de Dados

CONJUNTO DE DADOS


Dados - Conjunto de Dados


Dados - Atributos - Valores

Dado

Instancia de um fenomeno.

atributos identificadores

atributos descritivos

atributos de classe

Valores Quantitativos ou numericos

discretos (idade, quantidade de pessoas)

contınuos (salario, peso)

Valores Qualitativos ou categoricos

nominais (estado civil, cor dos olhos)

ordinais (grau de instrucao, estagio da doenca)


Mineracao de Dados - Tarefas

Preditivas e Descritivas

Tarefas preditivas usam os valores dos atributos descritivos para predizer valores

futuros ou desconhecidos de outros atributos de interesse.

Classificacao - predicao categorica

Regressao - predicao numerica

Tarefas descritivas tem o objetivo de encontrar padroes que descrevem os dados

de uma maneira que o ser humano possa interpretar.

Agrupamento

Sumarizacao

Modelagem de dependencias (regras de associacao)

Deteccao de desvios


Predicao (Classificacao e Regressao)

Classificacao e o processo de encontrar um modelo (ou funcao) que mapeia os dados para suas classes ouconceitos correspondentes, com o proposito de proporcionar o uso do modelo para predizer a classe de ouconceito de um objeto (ou dado) cujo rotulo nao e conhecido. Para o mesmo objetivo, porem considerandorespostas em um universo contınuo, a tarefa de regressao e estabelecida. O modelo derivado e baseado naanalise de um conjunto de dados de treinamento - dados cujos rotulos sao conhecidos.

Exemplo de classificacao:

classificar os itens de venda de acordo com a resposta de cada um a campanhas de marketing (boa resposta,resposta media e nenhuma resposta). O modelo mapeia itens de forma que determinadas caracterısticaslevam a uma determinada resposta para as campanhas: produtos de uma determinada marca e de umdeterminado preco nao respondem bem a campanhas de marketing. Como predicao o modelo pode indicarse um determinado novo produto deve ou nao entrar em uma campanha.

Exemplo de regressao:

suponha que se deseja agora predizer o quanto um produto sera lucrativo no futuro, com baseado em dadoshistorico de vendas.


Analise de grupos (clustering)

Analise de dados sem consultar um rotulo (de classe ou conceito) conhecido.

Geralmente, nesta tarefa, os rotulos dos dados de treinamento nao estao presentes. Os

dados sao agrupados com base em princıpios de maximizacao da distancia interclasses

(minimizacao da similaridade) e minimizacao da distancia intraclasses (maximizacao

da similaridade).

Exemplo de analise de grupos:

Identificacao de subpopulacoes homogeneas de clientes. Tais subpopulacoes podem

representar grupos alvo em campanhas de marketing.


Mineracao de padroes frequentes,associacoes e correlacoes

Padroes frequentes sao padroes que ocorrem frequentemente em um conjunto de

dados. Podem ser do tipo:

item: conjuntos de itens que aparecem juntos em transacoes;

sequencias: conjuntos de itens (ou comportamento) que sao frequentementeobservados um apos o outro;

subestruturas: formas frequentes observadas em um conjunto de dados (um hierarquiapor exemplo).

Exemplo de analise de associacao:

buys (X ,“computer”) → buys (X , “software”)

Exemplo de analise de correlacao:

↑ buys (X ,“computer”) → buys (X , “software”) =⇒ ↑ buys (X ,“printers”) → buys

(X , “ink”)


Resumo das principais tarefas deMineracao de Dados



Exercıcios

Qual(is) tarefa(s) de Mineracao de Dados sao pertinentes e/ou uteis em cada um dos

contextos? Mostre que a tarefa escolhida pode ser aplicada ao contexto e que tipo de

“conjunto de dados” poderia ser fornecido ao algorıtmos que implementara a tarefa.

O cliente de uma operadora de cartoes de credito tem seus cartoes roubados.

Os ladroes comecam a realizar compras com os cartoes em estabelecimentos

comerciais de diferentes cidades, em curtos espacos de tempo.

Os clientes de um site de vendas fazem um cadastro onde inserem informacoes

pessoais diversas, entre elas estao habitos diarios de lazer, tipo de trabalho,

situacao familiar, etc. So depois disso, tais clientes estao aptos a realizar

compras. Mediante as informacoes fornecidas no cadastro e os itens de compra

de cada cliente, o sistema de inteligencia do site e capaz de unir clientes

parecidos e extrair informacoes gerais sobre ele, que permitem a empresa

entender sua clientela e melhorar o seu atendimento.


Um site governamental sobre informacoes gerais ao cidadao de um estado

brasileiro armazena um historico da ordem de acessos dos usuarios a suas

paginas. A partir destas informacoes, o sistema inteligente de engenharia de

software e interface humano computador propoes uma reoganizacao das

informacoes que estao disponıveis no site.

Alguns analistas do mercado financeiro possuem informacoes de diferentes

naturezas que permitem conhecer o ambiente economico e polıtico de um paıs.

A partir destas informacoes, esses analistas tem condicoes de determinar valores

para determinados ındices e taxas referentes a economia do paıs.

Investidores do mercado de acoes, antes de decidir sobre em que acoes aplicar,

fazem uma analise do historico (evolucao previa) do rendimento daquelas acoes.

Um cursinho pre-vestibular utiliza uma estrategia que, a partir do

preenchimento de um questionario, encaminha um aluno para um grupo

especıfico de estudo que atenda as suas necessidades.


Uma escola do ensino medio resolve organizar seus alunos a fim de descobrir

quais alunos estao capacitados para participar de maratonas de matematica,

portugues, historia, etc. Para isso, a escola usa as informacoes das notas que os

alunos obtiveram nas diferentes avaliacoes e atividades de diferentes materias,

informacoes sobre preferencias dos alunos por conteudos, habilidades de

resolucao de problemas rapidamente e eficientemente, dados observados sobre

os alunos em relacao ao rendimento sob situacoes de pressao.

Um site de notıcias que recebe reportagens de diferentes agencias de notıcias

internacionais criou um sistema inteligente que, automaticamente, encaminha

uma notıcia recem-chegada para uma determinada localizacao na sua

homepage. Tal localizacao e decidida com base nas caracterısticas dos textos e

nas informacoes neles contidas.


Em uma regiao remota do paıs, onde existem poucos profissionais da area da

saude, o diagnostico medico e suportado por um sistema que, dado os sintomas

do paciente, retorna o tipo de doenca que pode estar associado.

Em um restaurante sofisticado da cidade de Sao paulo, a sobremesa e cortesia

da casa. Contudo, o cliente nao tem o direto de escolher o que vai comer. O

restaurante escolhe a sobremesa com base nas escolhas de entradas e prato

principal escolhidos pelo cliente, baseando-se em experiencias anteriores obtidas

em uma epoca em que o cliente tinha o direito de escolher a sua sobremesa.

Uma empresa de telecomunicacoes disponibiliza ao seu cliente um atendimento

automatizado. O cliente interage com um “robo” que lhe faz perguntas

especıficas e espera por respostas que se enquadrem em um modelo de

descricao da fala.


(baseado no exemplo de Goldschmidt, pag. 159) Uma empresa de telefonia tem

um bando de dados com informacoes obtidas por meio do preenchimento de

um questionario por clientes selecionados. A partir destas informacoes foi

construıdo um sistema capaz de caracterizar o potencial de compras de todos

os clientes e, sobre tal potencial, acoes de marketing especıficas para cada

clientes sao realizadas.

(baseado no exemplo de Goldschmidt, pag. 160) Uma empresa de fast-food

realiza promocoes para estimular a venda combinada de produtos. Essas

promocoes estao embasadas em conhecimento adquirido de uma base de dados

que contem informacoes de transacoes de venda de itens realizadas durante um

determinado perıodo de captacao de dados a partir de um ponto de venda de

uma loja.


(baseado no exemplo de Goldschmidt, pag. 160) O PRODERJ realiza um

processo de reintegracao das pessoas de rua do estado. Esse processo esta

baseado no perfil de cada pessoa, determinado com base em informacoes

coletadas sobre ela. Com o desenvolvimento de tal processo, o orgao passou a

incluir na base a informacao sobre o resultado do processo de reintegracao (se a

pessoa foi ou nao reintegrada com sucesso) e, a partir de um momento, passou

a automatizar o processo de decisao sobre o programa mais adequado para

cada pessoa.

(baseado no exemplo de Goldschmidt, pag. 161) Um sistema de analise do

historico de pagamento de impostos e capaz de verificar se um determinado

contribuinte esta ou nao praticando crime de sonegacao.

Um sistema de rede social e capaz de analisar um grupo de usuarios e extrair

caracterısticas em comum destes usuarios.


Um supermercado armazena as informacoes sobre todas as compras realizadas.

O sistema e capaz de avaliar as compras e descobrir produtos que geralmente

sao comprados pelos memos clientes, visando organizar a disposicao dos

produtos de forma que o cliente consuma mais.

Uma rempresa que presta servios de TV por assinatura possui um sistema

capaz de estimar a probabilidade de um cliente deixar de usar seus servicos

baseado em seu perfil de uso.

Um departamento de transito possui um sistema para auxiliar a fiscalizacao. O

sistema e capaz de processar as imagens captadas por radares e reconhecer

todos os detalhes da placa, alem de verificar se a cor e o modelo correspondem

aos verificados no documento do carro.


Um departamento de Saude Publica utiliza um sistema capaz de estimar a

incidencia de uma determinada doenca numa determinada regiao em um

determinado perıodo, visando planejar os recursos necessarios para minimizar o

impacto da doenca na populcacao.

Uma empresa bancaria precisa rapidamente prever qualquer tentativa de

invasao da sua rede de computadores. Para isso, a empresa utiliza um sistema

capaz de detectar invasoes, analisando comportamentos suspeitos.

Uma empresa de cartao de credito define o limite do cartao de seus clientes

atraves de um sistema que analisa as informacoes do cliente e retorna um limite

que o cliente deve ser capaz de pagar, apresentando baixo risco de

inadimplencia.



Documents

Apresentação - Mineração de Dadoseach.uspnet.usp.br/sarajane/wp-content/uploads/2015/08/aula01.pdf · KDD - Knowledge Discovery from Data Data Warehouse (Armaz em de dados) Data