Mineração de Dados - each.usp.br .Mineração de Dados (Data Mining) ... Obs: Predição com Agrupamento

  • View
    212

  • Download
    0

Embed Size (px)

Text of Mineração de Dados - each.usp.br .Mineração de Dados (Data Mining) ... Obs: Predição com...

  • Minerao de Dados

    Material extrado do minicurso: Uma introduo

    Minerao de Dados (Data Mining) com Inteligncia

    Artificial ministrado pelos docentes: Prof. Dr. Clodoaldo

    Aparecido de Moraes Lima e Profa. Dra. Sarajane

    Marques Peres na Segunda Semana de Sistemas de

    Informao

  • Lim

    a, C

    . A

    . M

    . &

    Pere

    s,

    S.

    M.

    Introduo

    2

  • Lim

    a, C

    . A

    . M

    . &

    Pere

    s,

    S.

    M.

    A Evoluo

    3

    Sistemas de Gerenciamento

    de Dados em Arquivos (1960)

    Sistemas de Gerenciamento de Banco de Dados

    (SGBD SQL OLTP) (1970-1980)

    Nova Gerao de Sistemas de Informao e Dados Integrados

    (Presente e Futuro)

    Sistemas de

    Gerenciamento de

    Banco de Dados

    Avanados (OR OO

    Espacial Temporal

    Baseado em

    Conhecimento ...)

    (1980- atual)

    Anlise de Dados

    Avanada (Data

    Warehouse, OLAP,

    KDD, Data Mining)

    (1980- atual)

    Sistemas de Banco de

    Dados baseados em

    Tecnologia WEB (XML

    Integrao e

    Recuperao da

    Informao )

    (1990- atual)

    Adaptado de Han & Kamber (2006)

  • Lim

    a, C

    . A

    . M

    . &

    Pere

    s,

    S.

    M.

    Tarefas de Minerao de Dados

    Minerao de Dados:

    Tarefas Preditivas

    Classificao incluindo Descoberta de Desvios e Previso de Sries

    Regresso

    Tarefas Descritivas

    Regras de Associao incluindo Associaes Temporais

    Agrupamentos

    Sumarizao

    4 Obs: Predio com Agrupamento !!!

  • Lim

    a, C

    . A

    . M

    . &

    Pere

    s,

    S.

    M.

    Minerao de Dados : interdisciplinaridade

    5

    (Han & Kamber, 2006)

  • Lim

    a, C

    . M

    . A

    . M

    . &

    Pere

    s, S

    . M

    .

    A tarefa de Associao

    6

  • Lim

    a, C

    . M

    . A

    . M

    . &

    Pere

    s, S

    . M

    .

    Regras de Associao

    Padro Itens frequentes

    7

    Padro sequencial Padro estruturado

    frequente (grafo)

    S

    A

    B

    O

    A

    M

    A

    C

    I

    A

    N

    T

    E

    S

    A

    B

    O

    A

    M

    A

    C

    I

    A

    N

    T

    E

    pizza

    chocolate

    Consumo:

    caipirinha feijoada laranja

    Compra:

    carro seguro teclado

    mouse

    monitor

    CPU

    Comportamento:

    ingresso pipoca

  • Lim

    a, C

    . A

    . M

    . &

    Pere

    s,

    S.

    M.

    Regras de Associao

    Exemplo (Han & Kamber, 2006)

    Como gerente da marca AllElectronics, voc gostaria de saber mais sobre os hbitos de compras de seus clientes. Mais especificamente, voc gostaria de saber quais

    grupos ou conjuntos de items os clientes geralmente compram em uma visita sua

    loja.

    Para responder a essa pergunta necessrio fazer uma anlise (de mercado) das

    compras realizadas, observando os dados provenientes das transaes (compras) dos

    clientes na loja.

    Voc poderia usar os resultados dessa anlise para planejar estratgias de marketing,

    atravs de anncios, projeto de novos catlogos, rearranjo do layout da loja.

    Por exemplo, itens que so comprados juntos (em uma mesma compra) podem ser

    colocados em lugares prximos de forma a encorajar a venda de tais items.

    8 Continua ...

  • Lim

    a, C

    . A

    . M

    . &

    Pere

    s,

    S.

    M.

    Regras de Associao

    Exemplo (Han & Kamber, 2006)

    Se clientes que compram computadores tambm tendem a comprar

    antivrus (na mesma compra). Ento coloc-los em lugares prximos pode

    ajudar a aumentar as vendas dos dois produtos.

    Alternativamente, a estratgia pode ser coloc-los em lados opostos da loja

    de forma a forar o cliente andar por toda a loja e, eventualmente, escolher

    outros produtos para comprar.

    Anlise de mercado tambm pode suportar a deciso sobre quais produtos

    colocar em liquidao ou retirar do mercado.

    9 Esta seo (teoria sobre Regras de Associao) do

    minicurso baseada no Captulo 5 de Han & Kamber

    (2006).

    Fraldas e cervejas:

    uma lenda urbana?!?!

  • Lim

    a, C

    . A

    . M

    . &

    Pere

    s,

    S.

    M.

    Regras de Associao

    Representao: considere seu universo como sendo o

    conjunto de produtos (itens) vendidos na loja.

    A existncia ou ausncia de cada um desses itens pode ser

    representada por uma varivel booleana.

    Cada compra pode ser representada por um vetor de variveis

    booleanas, sendo que, de fato, nesta compra (transao) foram

    comprados apenas os itens valorados com verdadeiro.

    Analisando esses vetores, possvel descobrir itens que

    frequentemente aparecem juntos (esto associados), constituindo um

    padro de comportamento.

    Esse padro pode ser representado por meio de uma regra de

    associao.

    10

    computador antivirus

    fralda cerveja

    (Han & Kamber, 2006)

    antecedente consequente

  • Lim

    a, C

    . A

    . M

    . &

    Pere

    s,

    S.

    M.

    Regras de Associao

    Formalizando ....

    Seja L = {I1, I2, ..., Im} um conjunto de itens.

    Seja D, um conjunto de dados relevantes para a tarefa constitudo de

    transaes de banco de dados, onde cada transao T um conjunto

    de itens tal que T L.

    Cada transao associada a um identificador (TID).

    Seja A e B subconjuntos de itens.

    A transao T contm A se e somente se A T.

    Uma regra de associao uma implicao da

    forma A B, onde A L, B L e A B = .

    11

    (Han & Kamber, 2006)

  • Lim

    a, C

    . A

    . M

    . &

    Pere

    s,

    S.

    M.

    Regras de Associao

    Medidas de interessabilidade

    Suporte = utilidade da regra

    Confiana = certeza sobre a regra

    O suporte de 2% para a regra acima significa que 2% de todas as transaes

    analisadas mostram que computadores e antivirus so comprados juntos.

    A confiana de 60% da regra acima significa que 60% dos fregueses que

    compram um computador tambm compram um antivirus.

    Regras de associao interessantes so aquelas que possuem um suporte

    e uma confiana mnimos (de acordo com um limite inferior pr-

    estabelecido) !!

    12

    computador antivirus [ suporte = 2%, confiana = 60%]

    (Han & Kamber, 2006)

  • Lim

    a, C

    . A

    . M

    . &

    Pere

    s,

    S.

    M.

    Regras de Associao

    Uma regra A B existe em um conjunto de transaes D com suporte

    s, onde s a porcentagem de transaes em D que contm A U B.

    Contm tanto A quanto B

    calculado como a probabilidade P(AUB), a probabilidade da

    transao conter a unio do subconjunto A e do subconjunto B.

    suporte (A B) = P(AUB)

    13

    Uma regra A B tem confiana c no conjunto de transaes D, onde

    c a porcentagem de transaes em D contendo B dado que contm

    A. - calculada como a probabilidade condicional P(B|A).

    confiana (A B) = P(B|A)

    (Han & Kamber, 2006)

  • Lim

    a, C

    . A

    . M

    . &

    Pere

    s,

    S.

    M.

    Regras de Associao

    Definies

    Itemset: um conjunto de itens.

    k-itemset: um conjunto de k itens.

    2-itemset: um conjunto de 2 itens

    {computador, antivirus}

    Frequencia de ocorrncia de um itemset (suporte do itemset): nmero

    de transaes que contm o itemset.

    Itemset frequente: um conjunto de itens que satisfaz a um suporte

    mnimo.

    O conjunto de k-itemsets frequentes denotado por Lk.

    14

    (Han & Kamber, 2006)

  • Lim

    a, C

    . A

    . M

    . &

    Pere

    s,

    S.

    M.

    Regras de Associao

    confiana (AB) =

    P(B|A) =

    suporte (AUB) / suporte (A) =

    suporte do itemset (AUB) / suporte do itemset (A)

    Obs.: uma vez que a frequencia dos itemsets foram calculadas, os clculos do

    suporte e da confiana de uma regra podem ser facilmente realizados.

    Assim, o problema de minerar regras de associao pode ser reduzido ao

    problema de minerar os itemsets frequentes.

    15

    (Han & Kamber, 2006)

  • Lim

    a, C

    . A

    . M

    . &

    Pere

    s,

    S.

    M.

    Regras de Associao

    Processo de minerao de regras de associao:

    16

    Encontrar todos

    os itemsets

    frequentes

    Gerar regras de

    associao

    fortes a partir

    destes itemsets

    Determine o limite mnimo para o

    suporte (min-sup)

    (varia para cada aplicao e

    uma deciso de projeto)

    Regras de associao fortes so aquelas

    que satisfazem ao min-sup e ao min-conf.

    Determine o limite mnimo para a

    confiana (min-conf)

    (varia para cada aplicao e uma

    deciso de projeto)

    Passo

    mais

    custoso!!!

    (Han & Kamber, 2006)

  • Lim

    a, C

    . A