Using Concept Hierarchies in
Knowledge Discovery
Usando Hierarquias
Conceituais na Descoberta
de Conhecimento
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 2004
SBIA 2004 - Marco Di Beneditto
2
Valores dos atributos
 valores existentes no BD; ou
 generalizações ou agrupamentos dos valores existentes no
BD
nível de abstração mais elevado
nível de abstração do BD
SET 2004
SBIA 2004 - Marco Di Beneditto
3
Aspectos a considerar
Utilização em qualquer SGBD relacional que suporte
consultas em SQL.
Representação de hierarquias conceituais no próprio
SGBD, sem necessitar de uma outra ferramenta.
Desnecessidade de pré-generalizar o BD num
determinado nível conceitual.
SET 2004
SBIA 2004 - Marco Di Beneditto
4
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 2004
SBIA 2004 - Marco Di Beneditto
5
Primitiva de Contagem para o cálculo
de medidas de relevância
Avaliação de hipótese de regra expressa em SQL.
SE COR ENTÃO classe=?
SELECT cor, classe, COUNT(*) FROM tabela_dados GROUP BY
cor, classe;
Regra expandida pela adição de mais um atributo.
SE COR = preta  FORMA ENTÃO classe=?
SELECT forma, classe, COUNT(*) FROM tabela_dados WHERE
cor = ‘preta’ GROUP BY forma, classe;
SET 2004
SBIA 2004 - Marco Di Beneditto
6
Saída da primitiva de contagem
Proposta por Alex Freitas (1997).
Atributo
valor
SET 2004
Av1
Av2
Av3
...
Avk
Classes
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
7
Cálculo do Suporte e Confiança com
hierarquias conceituais
SET 2004
SBIA 2004 - Marco Di Beneditto
8
Primitiva de contagem com hierarquias
conceituais
SE COR = escura  FORMA ENTÃO classe = ?
SELECT forma, classe, COUNT(*)
FROM tabela_dados
WHERE (cor = ‘preta’ OR cor = ‘marrom’)
GROUP BY forma, classe;
SET 2004
SBIA 2004 - Marco Di Beneditto
9
Codificação de Hierarquias Conceituais
 Verificar se um conceito é mais
geral que outro sem necessitar
consultar a hierarquia.
 Representar a relação de ordem
parcial entre conceitos.
 Percurso
pós-fixado
da
hierarquia conceitual
101 00 10 = 82
101
= 5 (82 >> 4)
SET 2004
SBIA 2004 - Marco Di Beneditto
10
Sistema NETUNO-HC
1. Atributos
2. Hierarquias
3. Valores mínimos das medidas de relevância
4. Largura do feixe
Banco de Dados
Algoritmo NETUNO
Regras descobertas
Teste
SET 2004
SBIA 2004 - Marco Di Beneditto
11
Experimentos preliminares - uso da
primitiva de contagem
Implementação da primitiva de contagem no algoritmo
ParDRI (Taylor, 1999). O algoritmo ParDRI realiza
consultas de alto nível utilizando os valores abaixo da raiz
da hierarquia (descendentes de QUALQUER).
Algoritmo
ParDRI
ParDRI – primitiva de contagem
Número de
Consultas
117
70
Número de
Regras
26
26
Banco de dados Cogumelo (UCI)
SET 2004
SBIA 2004 - Marco Di Beneditto
12
Taxa de acerto X Medidas de
relevância
Suporte/Confiança Cogumelo
sem HC
20% / 98%
0.9596
12% / 98%
0.9738
4% / 98%
0.9881
com HC
0.9845
0.9845
0.9845
Suporte/Confiança Adulto
sem HC
20% / 90%
0.6717
12% / 90%
0.7048
4% / 90%
0.7229
com HC
0.6762
0.7031
0.7235
Suporte: p/P
Confiança: p/(n+p) ou P(C|A)
Obs: Taxa de acerto total, sem computar os exemplos não
classificados (não cobertos por uma regra)
SET 2004
SBIA 2004 - Marco Di Beneditto
13
Número de regras descobertas
Número de regras descobertas para o BD Cogumelo
Suporte/Confiança
4%
12%
20%
SET 2004
90%
101
87
77
70
62
52
94%
105
101
79
81
65
65
SBIA 2004 - Marco Di Beneditto
98%
122
103
92
81
66
58
sem HC
com HC
14
Conclusões
1) representação eficiente das hierarquias conceituais.
 estrutura interna de representação
 codificação da hierarquia
2) redução do número de acessos ao BD.
 uso da primitiva de contagem empregando hierarquias
conceituais
SET 2004
SBIA 2004 - Marco Di Beneditto
15
Conclusões
4) Alterações nos valores mínimos das medidas de relevância.
 um valor maior de suporte tende a descobrir um conjunto de
regras com valores de mais alto nível.
5) O uso de hierarquias pode descobrir um conjunto menor de
regras.
SET 2004
SBIA 2004 - Marco Di Beneditto
16
FIM