ALGORITMOS para Descoberta de
Conhecimento em Bases de Dados
prof. Luis Otavio Alvares
II/UFRGS
Sumário




Regras de associação: Apriori
Classificação: ID3, C4.5
Formação de agrupamentos: k-médias
Detecção de desvios

Regras de Associação
Regras de associação
Regras de associação ou regras associativas têm a forma
{X1, X2, ..., Xn}  Y
significando que se encontrarmos todos os itens X1, X2, ..., Xn
numa transação, então temos uma boa chance de
encontrar também Y.
dada a regra de associação
XY
X implica Y
se X então Y
se compra X então compra Y
define-se
suporte =
confiança =
Número de registros com X e Y
Número total de registros
Número de registros com X e Y
Número de registros com X
Algoritmos de Regras de Associação
AIS
SETM
Apriori
Apriori -TID
Apriori-Hybrid
Dense – Miner
MiRABIT
Algoritmo Apriori
(1) Dado um limiar de suporte minsup, no primeiro passo encontre os itens que
aparecem ao menos numa fração das transações igual a minsup. Este
conjunto é chamado L1, dos itens freqüentes.
(2) Os pares dos itens em L1 se tornam pares candidatos C2 para o segundo
passo. Os pares em C2 cuja contagem alcançar minsup são os pares
freqüentes L2.
(3) As trincas candidatas C3 são aqueles conjuntos {A, B, C} tais que todos os
{A, B}, {A, C} e {B, C} estão em L2. No terceiro passo, conte a ocorrência
das trincas em C3; aquelas cuja contagem alcançar minsup são as trincas
freqüentes, L3.
(4) Proceda da mesma forma para tuplas de ordem mais elevada, até os
conjuntos se tornarem vazios. Li são os conjuntos freqüentes de tamanho i;
Ci+1 é o conjunto de tamanho i+1 tal que cada subconjunto de tamanho i está
em Li.
Exemplo de descoberta de regras associativas

Dada a tabela abaixo onde cada registro corresponde a uma transação de um cliente, com
itens assumindo valores binários (sim/não), indicando se o cliente comprou ou não o
respectivo item, descobrir todas as regras associativas, determinando o seu suporte (sup) e
grau de certeza (conf).
TID
1
2
3
4
5
6
7
8
9
10
leite
não
sim
não
sim
não
não
não
não
não
não
café
sim
não
sim
sim
não
não
não
não
não
não
cerveja
não
sim
não
não
sim
não
não
não
não
não
pão
sim
sim
sim
sim
não
não
sim
não
não
não
manteiga
sim
sim
sim
sim
não
sim
não
não
não
não
arroz
não
não
não
não
não
não
não
não
sim
sim
feijão
não
não
não
não
não
não
não
sim
sim
não

Dada uma regra de associação “Se compra X então compra Y”, os fatores sup e conf são:
Número de registros com X e Y
sup =
Número total de registros
Número de registros com X e Y
conf =
Número de registros com X
(1) Calcular o suporte de conjuntos com um item.
Determinar os itens freqüentes com sup  0,3.
(2) Calcular o suporte de conjuntos com dois itens.
Determinar conjuntos de itens freqüentes com sup  0,3.
Obs: se um item não é freqüente em (1), pode ser ignorado aqui.
Descobrir as regras com alto fator de certeza.
(3) Calcular o suporte de conjuntos com três itens.
Determinar conjuntos de itens freqüentes com sup  0,3.
Obs: pelo mesmo motivo anterior, só é necessário se considerar conjuntos de itens que são
freqüentes pelo passo anterior.
Descobrir regras com alto fator de certeza.
C1
Conjunto de itens suporte
{leite}
2
{café}
3
{cerveja}
2
{pão}
5
{manteiga}
5
{arroz}
2
{feijão}
2
Conjunto de itens suporte
{café}
3
{pão}
5
{manteiga}
5
L1
C2 , L2
Conjunto de itens suporte
{café, pão}
3
{café, manteiga}
3
{pão, manteiga}
4
Conjunto de itens
{café, pão, manteiga}
C3, L3
suporte
3

Regras candidatas com dois itens com o seu valor de certeza:
Conjunto de itens: {café, pão}
Se café Então pão
conf = 1,0
Se pão Então café
conf = 0,6
Conjunto de itens: {café, manteiga}
Se café Então manteiga conf = 1,0
Se manteiga Então café conf = 0,6
Conjunto de itens: {pão, manteiga}
Se pão Então manteiga
Se manteiga Então pão
conf = 0,8
conf = 0,8

Regras candidatas com três itens com o seu valor de certeza:
Conjunto de itens: {café, manteiga, pão}
Se café, manteiga Então pão
conf = 1,0
Se café, pão Então manteiga
conf = 1,0
Se manteiga, pão Então café
conf = 0,75
Se café Então manteiga, pão
conf = 1,0
Se manteiga Então café, pão
conf = 0,6
Se pão Então café, manteiga
conf = 0,6

Padrões descobertos, minsup = 0,3 e minconf = 0,8:
Se café Então pão
conf = 1,0
Se café Então manteiga conf = 1,0
Se pão Então manteiga
conf = 0,8
Se manteiga Então pão
conf = 0,8
Se café, manteiga Então pão
conf = 1,0
Se café, pão Então manteiga
conf = 1,0
Se café Então manteiga, pão
conf = 1,0
portanto, suporte e confiança são usados como
filtros, para diminuir o número de regras geradas
mas, se considerarmos a regra
Se A então B
com confiança de 90%
podemos garantir que seja uma regra interessante?
LIFT
a regra (1) Se A então B com confiança de 90%
NÃO é interessante se B aparece em cerca de 90% das
transações, pois a regra não acrescentou nada em termos de
conhecimento.
já a regra (2): Se C então D com confiança de 70% e´ muito
mais importante se D aparece, digamos, em 10% das transações.
lift = confiança da regra / suporte do conseqüente
lift da regra (1) = 0,9 / 0,9 = 1
lift da regra (2) = 0,7 / 0,1 = 7
Improvement
 Foi
proposto para diminuir o número de
regras geradas, utilizando o princípio de que
uma regra mais simples é uma regra
melhor, desde que a regra mais complexa
ou mais longa tenha confiança menor ou
igual do que a regra mais simples ou menor.
Exemplos

78,78% das cirurgias múltiplas são realizadas em
pessoas do sexo masculino. Esta regra se mostra
interessante, pois a concentração para o sexo
masculino não condiz com a realidade da base de
dados que na sua maioria é do sexo feminino. Ao se
estudar esta regra foi encontrada além da relação do
procedimento com o sexo masculino também com a
faixa etária de 0 a 9 anos. Não foram encontradas
razões, dentro dos atributos da base de dados, que
justificassem a concentração deste procedimento
neste sexo e faixa etária. Esta situação foi
encaminhada para o setor de avaliação e controle
para um melhor estudo.

80,45% das herniorrafias inguinais (unilateral)
múltiplas são realizadas em pessoas do sexo
masculino. Estudando mais profundamente foi
verificado que este procedimento estava concentrado
em crianças de 0 a 4 anos, caracterizando um erro
de nomenclatura nos procedimentos, pois nesta
idade um procedimento de urologia muito comum é
o tratamento da hidrocele comunicante muito
parecido com a herniorrafia inguinal. Foram tomadas
medidas para que tal procedimento fosse registrado
de forma correta pelos hospitais, pois a herniorrafia
inguinal pode levar a uma internação de urgência ou
emergência, aumentado seu custo, já o tratamento
da hidrocele comunicante é um procedimento
eletivo.
Exemplo: Conhecer o perfil do cliente associado com as
compras que o mesmo faz na loja
 Regras geradas:
 6.CASAAPTO=CASA SEXO=F 1036 ==> RESIDPROPALUG=PROPRIA 1033 conf:(1)
 22.ESTADOCIVIL=CASADO 2330 ==> RESIDPROPALUG=PROPRIA 2243 conf:(0.96)
 39.NODEFILHOS=0 1061 ==> CASAAPTO=CASA 1017 conf:(0.96)
 98.ESTADOCIVIL=CASADO SEXO=M 1390 ==> CASAAPTO=CASA 1279 conf:(0.92)
176.SEXO=F 1369 ==> RESIDPROPALUG=PROPRIA 1164 conf:(0.85)
 5.ESTADOCIVIL=SOLTEIRO BAIRRO=BELA_VISTA RESIDPROPALUG=ALUGADA 282 ==> MORAQTTEMPO=1 282 conf:(1)
 11.ESTADOCIVIL=VIUVO OBJCOMPRA=CONSTR_PREDIO/APTO/CASA_PROPRIA 200 ==> CASAAPTO=APTO 200 conf:(1)
 13.ESTADOCIVIL=VIUVO RESIDPROPALUG=ALUGADA 192 ==> CASAAPTO=APTO 192 conf:(1)
 37.PRIMEIRAVEZ=NAO FAIXETFILHO=SEM_FILHOS SEXO=M 700 ==> CASAAPTO=CASA 697 conf:(1)
 67.BAIRRO=CENTRO SEXO=F 811 ==> PRIMEIRAVEZ=NAO 798 conf:(0.98)
 69.ESTADOCIVIL=CASADO OBJCOMPRA=REFORMA_EM_CASA 840 ==> RESIDPROPALUG=PROPRIA 819 conf:(0.98)
 13.ESTADOCIVIL=CASADO FAIXETFILHO=ADULTO 819 ==> RESIDPROPALUG=PROPRIA 819 conf:(1)
 16.FAIXETFILHO=SEM_FILHOS BAIRRO=BELA_VISTA MORAQTTEMPO=1 282 ==> ESTADOCIVIL=SOLTEIRO 282 conf:(1)
384.ESTADOCIVIL=SOLTEIRO BAIRRO=BELA_VISTA 331 ==> FAIXETFILHO=SEM_FILHOS 327 conf:(0.99)
 79.FAIXETFILHO=ADULTO RESIDPROPALUG=ALUGADA SEXO=F 192 ==> CASAAPTO=APTO 192 conf:(1)
379.OBJCOMPRA=REFORMA_EM_CASA 993 ==> RESIDPROPALUG=PROPRIA 957 conf:(0.96)
 17.SUBCATEGPRODUTO=ROLO_PARA_PINTURA 41 ==> OBJCOMPRA=REFORMA_EM_CASA 22 conf:(0.54)
 9.PRIMEIRAVEZ=SIM SEXO=F 84 ==> FAIXETFILHO=SEM_FILHOS 71 conf:(0.85)
 34.PRIMEIRAVEZ=SIM 343 ==> SEXO=M 259 conf:(0.76)
 35.SUBCATEGPRODUTO=LUVA 96 ==> SEXO=M 72 conf:(0.75)
 41.SUBCATEGPRODUTO=ADAPTADOR 30 ==> SEXO=M 22 conf:(0.73)
 44.FAIXETFILHO=ADULTO SUBCATEGPRODUTO=REJUNTE 28 ==> SEXO=F 20 conf:(0.71)
 46.SUBCATEGPRODUTO=CHUVEIRO 38 ==> SEXO=M 27 conf:(0.71)
 47.SUBCATEGPRODUTO=REDUCAO 27 ==> SEXO=M 19 conf:(0.7)
 52.SEXO=F SUBCATEGPRODUTO=PISO 31 ==> FAIXETFILHO=ADULTO 21
 54.SUBCATEGPRODUTO=TOMADA 70 ==> SEXO=M 47 conf:(0.67)
 56.SUBCATEGPRODUTO=FITA_VEDA_ROSCA 30 ==> SEXO=M 20 conf:(0.67)
 72.FAIXETFILHO=ADULTO 1136 ==> SEXO=F 705 conf:(0.62)
269.SUBCATEGPRODUTO=LUVA 96 ==> SEXO=M 72 conf:(0.75)
344.FAIXETFILHO=CRIANCA 765 ==> SEXO=M 487 conf:(0.64)
386.SUBCATEGPRODUTO=PISO 74 ==> SEXO=M 43 conf:(0.58)
 88.PRIMEIRAVEZ=NAO 3065 ==> SEXO=F 1285 conf:(0.42)
226.SUBCATEGPRODUTO=PISO 74 ==> RESIDPROPALUG=PROPRIA 60 conf:(0.81)
Classificação: árvores de decisão
Árvore de decisão
montante
médio
E=não
alto
E=sim
salário
baixo
baixo
alto
E=sim
conta
não
E=não
sim
E=sim
Árvores de Decisão
As árvores de decisão são representações gráficas
que consistem:


de nodos que representam os atributos;
de arcos que correspondem ao valor de um
atributo;
 de nodos folha que designam uma classificação.
Árvores de decisão
As árvores de decisão:
 particionam recursivamente um conjunto de
dados, até que cada subconjunto obtido deste
particionamento contenha casos de uma única
classe;
 organizam dados de maneira compacta;
 classificam novos casos.
Exemplo:
caso
1
2
3
4
5
6
7
8
9
10
11
12
13
14
montante
médio
médio
baixo
alto
alto
alto
baixo
médio
médio
alto
médio
baixo
baixo
alto
idade
sênior
sênior
sênior
média
jovem
jovem
jovem
média
jovem
média
média
jovem
sênior
média
salário
baixo
baixo
baixo
baixo
alto
alto
alto
baixo
alto
alto
alto
baixo
alto
baixo
conta
sim
não
sim
sim
sim
não
não
sim
sim
sim
não
não
sim
não
empréstimo
não
não
sim
sim
sim
não
sim
não
sim
sim
sim
sim
sim
não
Algoritmo ID3 [Quinlan 86]
Passos para construção de uma árvore de decisão:
1. Seleciona um atributo como sendo o nodo raiz ;
2. Arcos são criados para todos os diferentes valores do
atributo selecionado no passo 1;
3. Se todos os exemplos de treinamento sobre uma folha
pertencerem a uma mesma classe, esta folha recebe o
nome da classe. Se todas as folhas possuem uma
classe, o algoritmo termina;
4. Senão, o nodo é determinado com um atributo que não
ocorra no trajeto da raiz, e arcos são criados para todos
os valores. O algoritmo retorna ao passo 3.
Algoritmo ID3
Entropia
Quantidade necessária de informação para identificar a
classe de um caso
Entropia(S) = -(p1 log 2 p1 + p2 log 2 p2 + ...+ pn log 2 pn )
sendo n o número de valores possíveis da classe
Ganho de informação
Redução esperada da entropia
Ganho (S, A) = Entropia(S) -  ((|Sv| / |S|)*Entropia(Sv))
onde Sv é um subconjunto de S correspondente a um valor do atributo A
Entropia e Ganho de Informação
Considerando apenas 2 valores possíveis, a entropia é dada pela
fórmula:
Entropia (S) = - (p+ log2 p+ + p- log2 p-)
Onde:
S é a totalidade de amostras do conjunto
p+ é a proporção de amostras positivas
p- é a proporção de amostras negativas
Exemplo:
Se S é uma coleção de 14 exemplos com 9 instâncias positivas e
5 negativas, então:
Entropia (S) = - (9/14) Log 2 (9/14) – (5/14) Log 2 (5/14) = 0.940
Ganho de Informação
O ganho de informação é dado por:
Gain (S, A) = Entropia (S) -  ((|Sv| / |S|) * Entropia (Sv))
Onde:
Gain (S, A) é o ganho do atributo A sobre o conjunto S
Sv = subconjunto de S para um valor do atributo A
|Sv| = número de elementos de Sv
|S| = número de elementos de S
Nodo raiz
Selecionando o melhor atributo:
Entropia(S) = - 9/14 log2 (9/14) - 5/14 log 2 (5/14) = 0,940
caso
montante
idade
salário
conta
empréstimo
Entropia(montante=médio)
= - 2/5baixo
log2 (2/5)sim
- 3/5 log não
1
médio
sênior
2 (3/5) = 0,971
2
médio
sênior
baixo
não
não
Entropia(montante=baixo)
= - 4/4 baixo
log2 (4/4) sim
- 0/4 log2sim
(0/4) = 0
3
baixo
sênior
4
alto
média
baixo
sim
sim
Entropia(montante=alto)
=
3/5
log
(3/5)
2/5
log
(2/5)
2
2 sim = 0,971
5
alto
jovem
alto
sim
6
alto
jovem
alto
não
não
Gain (S,montante)
=
0,940
(5/14)
0,971
(4/14)
0
(5/14) 0,971 = 0,246
7
baixo
jovem
alto
não
sim
8
médio
média
baixo
sim
não
Gain (S,idade)
= 0,940 - (4/14)
(5/14) 0,971
9
médio
jovem 1 -alto
sim - (5/14)
sim0,722 = 0,049
10
alto
média
alto
sim
sim
11
médio
alto
não 0,985 sim
Gain (S,salário)
= 0,940 - média
(7/14) 0,592
- (7/14)
= 0,151
12
baixo
jovem
baixo
não
sim
13
baixo
sênior 0,811
alto - (6/14)
sim1 = 0,047
sim
Gain (S,conta)
= 0,940 - (8/14)
14
alto
média
baixo
não
não
Escolha do próximo atributo
{C1,C2,...C14}
[9+, 5-]
montante
médio
baixo
alto
{C1,C2,C8,C9,C11}
[2+, 3-]
{C3,C7,C12,C13}
[4+, 0-]
{C4,C5,C6,C10,C14}
[3+, 2-]
?
sim
?
Qual atributo pode ser testado aqui?
Escolha o próximo atributo
Qual é o melhor atributo?
Smédio = {C1,C2,C8,C9,C11}
Gain (Smédio, idade) = 0,971 - (2/5)0 - (2/5)1 - (1/5)0 = 0,571
Gain (Smédio, salário) = 0,971 - (3/5)0 - (2/5)0 = 0,971
Gain (Smédio, conta) = 0,971 - (3/5)0,918 - (2/5)1= 0,020
{C1,C2,...C14}
[9+, 5-]
montante
médio
baixo
alto
{C1,C2,C8,C9,C11}
[2+, 3-]
{C3,C7,C12,C13}
[4+, 0-]
{C4,C5,C6,C10,C14}
[3+, 2-]
salário
sim
?
baixo
{C1,C2,C8}
[0+, 3-]
alto
{C9,C11}
[2+, 0-]
Resultado
montante
médio
E=não
alto
E=sim
salário
baixo
baixo
alto
E=sim
conta
não
E=não
sim
E=sim
Avaliação da árvore de decisão
Avaliação através da taxa de acertos/erros:

taxa_de_acertos = Nacertos / Ntotal
 taxa_de_erros = Nerros / Ntotal
Utilizando o conjunto de treinamento:

proporção_de_acertos = 14 / 14 = 100%
 proporção_de_erros = 0 / 14 = 0%
Conjunto de teste
caso montante idade
salário
conta
empréstimo
15
16
17
18
19
20
21
alto
alto
alto
alto
alto
alto
alto
sim
não
sim
não
não
sim
sim
sim
não
sim
não
não
sim
sim
médio
médio
baixo
baixo
alto
alto
médio
sênior
sênior
jovem
sênior
média
jovem
jovem
empréstimo
(predito)
sim
sim
sim
sim
não
sim
sim
Proporção de acertos/erros
Utilizando o conjunto de teste:

proporção_de_acertos = Nacertos / Ntotal
proporção_de_acertos = 5 / 7 = 71,4%

proporção_de_erros = Nerros / Ntotal
proporção_de_erros = 2 / 7 = 28,6%
Algoritmo C4.5 [Quinlan 93]
O algoritmo C4.5 possibilita:
 trabalhar com valores contínuos
 trabalhar com valores indisponíveis
 podar árvores de decisão
 derivar regras
Atributos com valores contínuos
caso
1
2
3
4
5
6
7
8
9
10
11
12
13
14
montante
médio
médio
baixo
alto
alto
alto
baixo
médio
médio
alto
médio
baixo
baixo
alto
Idade
sênior
sênior
sênior
média
jovem
jovem
jovem
média
jovem
média
média
jovem
sênior
média
salário
780
980
860
760
1250
3210
4560
990
1250
6780
8900
670
567
670
conta
sim
não
sim
sim
sim
não
não
sim
sim
sim
não
não
sim
não
empréstimo
não
não
sim
sim
sim
não
sim
não
sim
sim
sim
sim
sim
não
Atributos com valores contínuos
Envolve o seguinte teste:
atributo <= valor ou atributo > valor
e os seguintes passos:


ordenar os valores de forma crescente (670, 760, ... 8900)
selecionar o valor que favorecerá na redução da
informação necessária (990)
Atributos com valores contínuos
Considerando o teste:
salário <= 990 ou salário > 990
obtemos a árvore:
montante
médio
não
alto
sim
salário
< = 990
baixo
conta
> 990
sim
não
não
sim
sim
Poda de árvores de decisão
A poda de uma árvore de decisão é realizada:
 considerando a taxa de erros
 substituindo uma subárvore por um nodo folha
Derivação de regras
montante
médio
não
alto
sim
salário
baixo
baixo
conta
alto
sim
não
não
sim
sim
se (montante = médio) e (salário = baixo) então empréstimo = não
se (montante = médio) e (salário = alto) então empréstimo = sim
se (montante = baixo) então empréstimo = sim
...
Detecção de desvios
Desvios: árvores de decisão
dados que não se enquadram no modelo pré-definido
Desvios: formação de agrupamentos

agrupamentos com um número pequeno de casos
Desvios: regras de associação

se tenho uma regra do tipo

X Y

com grau de confiança de 98%, podemos considerar os
2% restantes como desvio
Desvios: estatística
análise univariada: usada para atributos isolados
se o atributo for numérico, pode-se utilizar o desvio
padrão
Numa distribuição normal N (,2)
onde  é a média e 2 a variância
podemos considerar desvio os valores que estão a 3
ou mais desvios-padrão da média, para mais ou para
menos
Desvios: estatística
Análise multivariada: para análise de mais de
uma variável




regressão linear (para dados numéricos)
qui-quadrado (para dados categóricos)
análise de correspondência (para dados categóricos)
análise de resíduos em tabelas de contingência
(para dados categóricos)
Formação de agrupamentos
Exemplos
Objetivo : Conhecer o perfil do cliente que compra na loja
 Cluster 0
51,82% da população - perfil de um consumidor casado, com residência própria,
predominantemente em casas contra uma pequena parcela que reside em apartamentos, que já fez
mais de uma compra na loja, dividindo-se quase que igualmente entre homens e mulheres.
Objetivo : Conhecer o perfil do cliente que compra na loja
 Cluster 1
17,15% da população - clientes sem filhos, solteiros, que residem em casas próprias, sendo a
maioria cliente antigo; 47% com estado civil casado estão, na sua grande maioria, casados a
menos de 1 ano.
Objetivo : Conhecer o perfil do cliente que compra na loja
 Cluster 3
14,60% da população - clientes do sexo feminino, com filhos adultos, com idade dos 50 aos 65
anos em sua maioria, residindo a maior parte em casas mas com um número relativamente grande
morando em apartamentos (25%), todos com residência própria, e que também já compraram mais
de uma vez na loja; o bairro, para 60% dos casos, é “CENTRO”.
Objetivo : Conhecer o perfil do cliente que compra na loja
 Cluster 4
9,49% dos casos - pessoas que moram em residências alugadas, sem filhos ou com filhos
pequenos, a maioria do sexo masculino, morando predominantemente em casas. Dividem-se
principalmente entre solteiros e casados, sendo grande parte deles casada a menos de 1 ano.
Softwares p/ mineração







Intelligent Miner – IBM
Weka – softwre livre – Nova Zelândia
Darwin – Oracle
Sipina – universitário p/ árvores de decisão
Clementine – 1º?
Microsoft OLE DB for Data Mining
...