Descoberta de Regras de
Classificação em Bancos de
Dados com Hierarquias
Conceituais
Descoberta em múltiplos níveis
conceituais
Padrões podem ser descobertos:
1) no nível conceitual representado no Banco de Dados (BD)
2) num nível conceitual mais elevado, utilizando informação de
hierarquias de conceitos  descoberta de padrões de alto nível
Observações:
 em geral, não existem regularidades fortes em conceitos com baixo
nível de abstração.
 regularidades em conceitos de nível mais alto de abstração, podem
ser conhecidas ou de senso comum.
 conceitos em níveis intermediários podem apresentar maior grau de
interesse.
SET 2003
2
Regras de Classificação
Seja um BD no qual uma tupla:
t = (a1, ..., an), ak  DOM (Ak) e (1  k  n) e
C = {c1, ..., cm} um conjunto finito de classes.
Regras da forma:
Se A então ci,
na qual A é uma conjunção de pares atributo-valor, i.e.,
(A1, aa)  (A2, ab) ...  (An, az), e ci é uma classe.
note que A e ci são conjunto disjuntos.
SET 2003
3
Regras de Classificação
Servem para:
 descrição intensional de um conjunto: descrição através
de uma propriedade.
 previsão da classe de um novo exemplo, ainda
desconhecido.
SET 2003
4
Hierarquia de Conceitos - Fundamentos
 um conjunto finito parcialmente ordenado de conceitos define relações de generalização e especialização
 pode ser representada como uma árvore
 os valores dos atributos estão no nível folha - menor nível
de especialização
 pode ser fornecida por um especialista de domínio ou ser
construída a partir do BD
SET 2003
5
Hierarquia de Conceitos - Tipos
1. Hierarquia de esquema (entre atributos)
rua  bairro  cidade  estado ( é uma relação de ordem
parcial)
2. Hierarquia entre valores de atributo (instância)
- {ES, MG, RJ, SP}  Sudeste
- {0.0 ... 4.9}  Insatisfatório (valores contínuos em discretos)
3. Hierarquia baseada em regras (hierarquia condicional)
- {6.5 ... 8.5}  graduação  Muito Bom
SET 2003
6
Hierarquias de Conceitos Representação e Armazenamento
 representada através de uma
árvore
 uso de tabelas relacionais.
 cada linha da tabela significa um
caminho do vértice raiz até um
vértice folha.
SET 2003
0
QUALQUER
QUALQUER
QUALQUER
QUALQUER
1
clara
clara
escura
escura
2
amarela
branca
preta
marrom
7
Medidas de Relevância
 Completude: se a regra classifica todas as instâncias da
classe.
 Consistência: se a regra não classifica uma instância de
outra classe
SET 2003
8
Medidas de Relevância - sem hierarquia
 Definição 1
um objeto ou tupla de um BD é coberto ou satisfaz uma regra se os
atributos da tupla possuem os mesmo valores que os atributos da
regra
 Definição 2
uma regra classifica corretamente uma tupla do BD se a tupla for
coberta pela regra e pertencer à classe da regra.
SET 2003
9
Medidas de Relevância - com hierarquia
 Definição 3
um objeto ou tupla de um BD é coberto ou satisfaz uma regra de alto
nível, se os atributos da tupla possuem valores que pertencem aos
conceitos dos atributos do antecedente da regra
 Definição 4
uma regra de alto nível classifica corretamente uma tupla do BD se a
tupla for coberta pela regra e pertencer à classe da regra.
SET 2003
10
Medidas de Relevância
A  C : (p, n)
 SUPORTE : número de tuplas classificadas corretamente
dividido pelo número de tuplas que pertencem à classe:
p/P
 CONFIANÇA: número de tuplas classificadas corretamente
dividido pelo número de tuplas cobertas pelo antecedente
da regra: p / (p + n).
 Valores altos de suporte e confiança: regras fortes
SET 2003
11
Primitiva de Contagem
Regras são convertidas em expressões SQL:
SE ODOR ENTÃO ?
 SELECT odor, classe, COUNT(*) FROM tabela_dados
GROUP BY odor, classe;
SE FORMA = ACHATADA  ODOR ENTÃO ?
 SELECT odor, classe, COUNT(*) FROM tabela_dados
WHERE forma = ‘achatada’ GROUP BY odor, classe;
SET 2003
12
Cálculo do Suporte e Confiança (cont.)
Classes
Atributo
valor
SET 2003
Av1
Av2
Av3
...
Avk
C1 C2 C3 ... Cn
T11 T12 T13 ... T1n T1+
T21
T2+
T31
T3+
...
Tk1 ... ... ... Tkn Tk+
T+1 T+2 T+3 ... T+n T++
Tuplas por classe
Tuplas
por valor
de atributo
13
Cálculo do Suporte e Confiança (cont.)
Suporte: p / P => T11 / T+1
Confiança: p / (p + n) => T11 / T1+
SET 2003
14
Busca por Padrões em Múltiplos Níveis
Estratégias de mineração
1) especialização progressiva - top down
2) generalização progressiva - bottom up
SET 2003
15
Espaço de Regras
SET 2003
16
Tamanho do Espaço de Regras
 tuplas com i atributos.
 cada atributo possui k valores possíveis
 número de possibilidades de tuplas: T = k i.
 número de diferentes de regras: R = (k+1) i
SET 2003
17
Problema de Busca
Estado Inicial
Operadores
Teste do Estado Meta
SET 2003
regra vazia
aplicação das operações na
especialização das regras
cálculo das medidas de relevância para
comparação com os valores mínimos
18
Especialização de Hipóteses de Regras
Se (A1,v1)  (A2, v2) ... (Ai, vi) então cn
especialização na
hierarquia
adição de par Av
Se (A1,v1)  (A2, v2) ... (Ai, v’i) então cn
Se (A1,v1) ...(Ai, vi)  (Ai+1, vi+1) então cn
uso de
hierarquias de conceitos
SET 2003
19
Algoritmo de Busca - geral
nós  CRIA-LISTA (regra vazia)
laço faça
se a lista de nós estiver vazia então devolva falha
nó  SELECIONE(nós)
se TESTA-META(nó) então armazena nó
senão nós  INSERE-LISTA (nós, EXPANDA(nó))
fim
SET 2003
20
Geração das Regras
R’: cor = escura
R’1: cor = escura  forma = achatada
R’: cor = escura
R’2: cor = preta
SET 2003
21
Geração das Regras
 Propriedade
o número de tuplas cobertas por uma regra mais específica é
menor ou igual ao número de tuplas cobertas pela regra mais
geral.
Operações
Adição de atributo
Especialização na hierarquia
SET 2003
SUPORTE CONFIANÇA

 ou 

 ou 
22
Poda do Espaço de Regras
 Expansão de nós cujo valor de suporte seja menor que o
mínimo.
 Tabelas de co-ocorrência (especialização pela adição de
atributos):
1) expansão de nós inexistentes no BD;
2) expansão de nós com valor de suporte menor que o mínimo
SET 2003
23
Poda no Espaço de Regras
ID
1
2
3
4
5
COR
marrom
branca
verde
verde
branca
X
X
SET 2003
X
ODOR
amêndoa
peixe
anis
amêndoa
anis
X
X
X
24
Sistemas de Descoberta
ParDRI (Merwyn Taylor, UMA, EUA)
– ParkaDB - linguagem de representação do
conhecimento + SGBD.
– tabelas de co-ocorrências.
DBMiner (Jiawei Han, SFU, Canadá)
– generalização de tabelas - IOA (Indução Orientada a
Atributo).
– nível de generalidade determiando pelo usuário.
SET 2003
25
Critérios de Avaliação do
Conjunto de Regras
1) Precisão de classificação
– conjunto de teste
2) Complexidade do conjunto de regras
– quantidade e tamanho das regras
3) Precisão em BD com ruído
4) Equivalência Semântica
5) Eficiência do Algoritmo de Busca
– nós expandidos
SET 2003
26
Objetivos do Trabalho
1) Desenvolvimento de um sistema de descoberta de regras de
classificação, denominado NETUNO, utilizando múltiplas
hierarquias conceituais.
2) Estender a idéia de primitiva de contagem considerando hierarquias
conceituais.
3) Comparação do Sistema NETUNO com outros sistemas.
4) Paralelo entre a busca exaustiva por regras e as técnicas de seleção
de características
SET 2003
27
Cronograma
Objetivos
1
2
3
4
Escrita
SET 2003
MAI

JUN

JUL

AGO


SET
OUT
NOV
DEZ











28
Algoritmo de Busca
1. gerar as hierarquias numéricas
2. gerar as listas de co-ocorrências
3. LISTA-REGRAS-DESCOBERTAS  
4. nós  CRIA-LISTA (regra vazia)
laço faça
se a lista de nós estiver vazia então devolva LISTA-REGRASDESCOBERTAS
nó  SELECIONE(nós)
se TESTA-META(nó) então armazena nó LISTA-REGRASDESCOBERTAS
senão nós  INSERE-LISTA (nós, EXPANDA(nó))
fim
29
Modelo funcional
Propagando a contagem de tuplas
pela Hierarquia
QUALQUER
57
clara
27
escura
30
Av1: preta
T11 = 21
SET 2003
Av2 : marrom
T21 = 9
Atributo A = cor
Classe = C1
Av3 : amarela
Av4 : branca
T31 = 10
T41 = 17
31
Cache em tabelas
São criados dois tipos de cache:
Cache 1 - para cada atributo, são criadas tabelas contendo todas as
tuplas cujos valores correspondem aos vértices de mais alto nível
(imediatamente abaixo da raiz).
C1 = (ID_tupla, Valor, Classe)
SET 2003
32
Cache em tabelas (cont.)
São criados dois tipos de cache:
Cache 2 - para cada regra é criada uma tabela que contém todas as
tuplas que satisfazem a regra.
C2 = (ID_tupla)
Uma regra especializada pela adição de mais um atributo:
C2
C1
SET 2003
33
Geração de Hierarquias Numéricas
Abordagem de baixo para cima.
Agrupa valores individualmente em intervalos.
Critério: menor aumento na entropia.
Sucessivamente, os intervalos são agrupados
seguindo o mesmo critério, até formar o vértice
raiz.
Vértice raiz vai do menor ao maior valor existente
no BD.
SET 2003
34
Geração de Hierarquias Numéricas
10 ~ 60
33 ~ 60
10 ~ 27
10
SET 2003
25
53 ~ 60
33 ~ 40
25 ~ 27
27
33
40
53
60
35
Avaliação
Banco de dados sobre cogumelos obtido do
repositório de BD de aprendizado de máquina da
UCI, EUA
contém 8416 tuplas, 23 atributos, 2 classes
(cogumelos comestíveis e venenosos)
SET 2003
36
Algoritmo implementado
 utiliza SGBD PostgresSQL onde são armazenadas as
hierarquias de conceitos e o BD
 para a execução do algoritmo, o BD deve ser
representado numa única tabela
 redução do espaço de hipóteses:
 co-ocorrência entre as tuplas - pares (A,v) que ocorrem
nas tuplas.
 medidas de relevância.
 uma regra descoberta não irá compor uma outra regra.
SET 2003
37
FIM
Hierarquia de Esquema
Rua
Bairro
Cidade
Estado
Paissandu Flamengo
Rio de Janeiro RJ
Matão
Cid Universitária São Paulo
SP
rua  bairro  cidade  estado
estado
cidade
bairro
rua
Hierarquia entre valores do atributo
província  região  país
Província
AB
BC
MB
SK
ON
QC
Hierarquia entre valores do atributo
10000 - 75000
10000 - 40000
10000 - 25000
25000 - 40000
Esta do
RJ
SP
MG
ES
PR
RS
SET 2003
40000 - 75000
40000 - 55000
55000 - 75000
Re nda
32100
25500
25403
70000
12500
50000
41
Hierarquia condicional
qualquer
forte
fraco
ruim
regular
excelente
R2
R1
0.0 ~ 4.5
muito bom
4.5 ~ 6.5
R1 = {4.5 ~ 6.5}  pós-graduação  ruim
R2 = {4.5 ~ 6.5}  graduação  regular