Descrição de Conceitos
Caracterização e Comparação
XXX
Descrição de Conceitos:
Caracterização e Comparação
• O que é Descrição de Conceitos?
• Caracterização baseada em generalização e resumo
• Análise da relevância de atributos
• Comparação de Classes: Discriminação entre
diferentes classes
• Estatística Descritiva em grandes bases de dados
• Discussão
O que é Descrição de Conceitos
• Mineração Descritiva versus Mineração Preditiva
– Mineração Descritiva: descreve conceitos ou conjuntos de
dados relevantes de forma concisa, resumida, informativa,
discriminante
– Mineração Preditiva: Baseado nos dados constroem-se
modelos para a previsão das tendências e das propriedades de
dados desconhecidos
• Descrição de Conceitos:
– Caracterização: fornece um sumário conciso e suscinto da
coleção de dados
– Comparação: fornece as descrições que comparam duas ou
mais coleções dos dados
Descrição de Conceitos vs. OLAP
• Descrição de Conceitos:
– pode manipular atributos complexos bem como
suas agregações
– um processo mais automatizado
• OLAP:
– Restrito a um número pequeno de dimensões e
aos atributos de tipo medida
– Processo controlado pelo usuário
Descrição de Conceitos:
Caracterização e Comparação
• O que é Descrição de Conceitos?
• Caracterização baseada em generalização e resumo
• Análise da relevância de atributos
• Comparação de Classes: Discriminação entre
diferentes classes
• Estatística Descritiva em grandes bases de dados
• Discussão
Caracterização baseada em
Generalização e Sumário
• Generalização
– Um processo que abstraia um grande conjunto de dados
relevantes em uma base de dados, de níveis conceptuais
baixos para mais elevados 1
2
3
4
Níveis conceptuais
5
– Abordagens:
• Abordagem Cubo de dados (Abordagem OLAP)
• Abordagem indução orientada atributo
Caracterização: Abordagem Cubo de Dados
• Realiza os cálculos e armazena os resultados em cubos de
dados
• Vantagens
– Implementação eficiente da generalização de dados
– Cálculo de vários tipos de medidas
• e.g., count( ), sum( ), average( ), max( )
– A generalização e a especialização podem ser executados em um cubo
dos dados pelo roll-up e pelo drill-down
• Limitações
– Manipula apenas dados não numéricos e de medidas de valores
agregados numéricos simples.
– falta da análise inteligente, não pode dizer que dimensões devem ser
usadas e que nível de generalização deve ser alcançado
Indução Atributo-Orientada
• Não se restringe a dados categóricos ou a medidas
particulares.
• Como é feito?
– Colete o conjunto de dados relevantes ( relação inicial) a
partir de uma interrogação de uma base de dados relacional
– Execute a generalização pela remoção de atributo ou pela
generalização de atributo.
– Aplique a agregação fundindo tuplas generalizadas idênticas
e acumule suas contagens respectivas.
– Apresentação interativa com usuários.
Exemplo
• DMQL: Descreve as característica gerais de
estudantes de pós-graduação na base de dados BigUniversity
use Big_University_DB
mine characteristics as “Science_Students”
in relevance to name, gender, major, birth_place,
birth_date, residence, phone#, gpa
from student
where status in “graduate”
• Interrogação SQl Correspondente:
Select name, gender, major, birth_place, birth_date,
residence, phone#, gpa
from student
where status in {“Msc”, “MBA”, “PhD” }
Princípios Básicos da Indução
Atributo-Orientada
• Focalização dos Dados: conjunto de dados relevantes, incluindo
as dimensões, e o resultado na relação inicial
• Remoção de Atributo: remove atributo A se existe um conjunto
grande de valores distintos de A mas (1) não há operador de
generalização em A, ou (2) Conceitos superiores a A são
expressos em termos de outros atributos.
• Generalização de Atributos: se existe um conjunto grande de
valores distintos de A, e se existe um conjunto de operadores de
generalização em A, então selecione um operador e generalize A.
• Controle Atributo-Limiar: tipicamente 2-8,
especificado/automático.
• Controle pelo limiar da relação generalizada: tipicamente 10-30,
especificado/automático.
Exemplo
Name
Relação
Inicial
Gender
Jim
Woodman
Scott
Lachance
Laura Lee
…
Removido
Residence
Phone #
GPA
3511 Main St.,
Richmond
345 1st Ave.,
Richmond
687-4598
3.67
253-9106
3.70
F
…
Vancouver,BC, 8-12-76
Canada
CS
Montreal, Que, 28-7-75
Canada
Physics Seattle, WA, USA 25-8-70
…
…
…
125 Austin Ave.,
Burnaby
…
420-5232
…
3.83
…
Conserva
do
Sci,Eng,
Bus
City
Removido Excl,
VG,..
M
Major
M
M
F
…
Birth_date
CS
Gender Major
Relação
Generalizada
Birth-Place
Science
Science
…
Country
Age range
Birth_region
Age_range
Residence
GPA
Canada
Foreign
…
20-25
25-30
…
Richmond
Burnaby
…
Very-good
Excellent
…
Birth_Region
Canada
Foreign
Total
Gender
M
16
14
30
F
10
22
32
Total
26
36
62
Count
16
22
…
Algoritmo Básico para a Indução
Atributo-Orientada
• InitialRel: Processamento da interrogação do conjunto de dados
relevantes para a obtenção da relação inicial
• PreGen: Baseado no número de valores distintos em cada
atributo, estabelecer o plano para cada atributo: remoção? ou a
que nível generalizar?
• PrimeGen: Baseado na etapa PreGen, realizar a generalização no
nível correto e obter a “relação generalizada de referência”,
acumulando as contagens.
• Presentation: Interação com o usuário: (1) ajustar os níveis via
drilling, (2) giro, (3) associação à regras, tabelas cruzadas,
apresentação visual.
Apresentação dos Resultados da
Generalização
• Relações Generalizadas:
– Relações em que alguns ou todos os atributos são generalizados, com as
contagens ou outros agregados acumulados.
• Tabelas cruzadas:
– Mapear os resultados na forma de tabelas cruzadas.
– Técnicas de Visualização:
– Gráfico de setores, gráfico de barras, curvas, cubos, etc.
• Regras características quantitativas:
– Mapear os resultados em regras características com informação
quantitativa associada, exemplo,
pos( x)  masculino( x) 
nascimento( x) "Canada"[t :53%] nascimento( x) "estrangeiro"[t : 47%].
Apresentação—Relação Generalizada
Apresentação—Tabelas Cruzadas
Descrição de Conceitos:
Caracterização e Comparação
• O que é Descrição de Conceitos?
• Caracterização baseada em generalização e resumo
• Análise da relevância de atributos
• Comparação de Classes: Discriminação entre
diferentes classes
• Estatística Descritiva em grandes bases de dados
• Discussão
Análise da Relevância de Atributos
• Porque?
–
–
–
–
Que dimensões devem ser incluídas?
Qual nível de generalização?
Automático vs. interativo
Redução do # atributos; mais fácil a compreensão dos
padrões
• Princípios
– Métodos estatísticos para o pré-processamento dos dados
• Filtragem dos atributos irrelevantes ou pouco relevantes
• Retenção e ordenação dos atributos relevantes
– Relevância relacionada as dimensões e aos níveis
– Caracterização analítica, comparação analítica
Análise da Relevância de Atributos
• Como?
– Coleta de Dados
– Generalização Analítica
• Usar o ganho de informações (ex., entropia ou outras medidas)
para identificar dimensões e níveis altamente relevantes.
– Análise de Relevância
• Ordenar e selecionar as dimensões e níveis mais importantes.
– Indução Orientada Atributo para a descrição de classes
• Nas dimensões/níveis selecionados
Medidas de Relevância
• As medidas de relevância avaliam o poder
classificatório de um atributo em um conjunto
de dados.
• Métodos
–
–
–
–
Ganho de informação (ID3)
Razão de ganho (C4.5)
Índice de gini
Etc.
Entropia e Ganho de Informação
• S contem si tuples da classe Ci for i = {1, …, m}
• Informação requerida para classificar qualquer tupla
arbitraria
s
s
I( s ,s ,...,s )   log
s
s
m
1
2
m
i
i
2
i 1
• Entropia do atributo A com valores {a1,a2,…,av}
s1 j  ... smj
I ( s1 j ,...,smj )
s
j 1
v
E(A) 
• Informação ganha ao ramificar no atributo A
Gain(A) I(s1, s 2 ,...,sm)  E(A)
Exemplo: Caracterização Analítica
• Tarefa
– Minerar características gerais de estudantes de pósgraduação usando caracterização analítica
• Dado
– atributos name, gender, major, birth_place, birth_date,
phone#, e gpa
– Gen(ai) = hierarquias de conceito em ai
– Ui = limiar analítico de atributo para ai
– Ti = limiar para generalização de atributo para ai
– R = limiar de relevância de atributo
Exemplo (Cont.)
• 1. Coleta de Dados
– Classe alvo: estudantes de pós
– Classe de contraste: estudantes de graduação
• 2. Generalização analítica usando Ui
– Remoção de atributos
• Remoção de name e phone#
– Generalização de atributos
• generalização de major, birth_place, birth_date and gpa
• Contagens acumuladas
– Relação candidata: gender, major, birth_country,
age_range and gpa
Exemplo (cont.)
gender
major
birth_country
age_range
gpa
count
M
F
M
F
M
F
Science
Science
Engineering
Science
Science
Engineering
Canada
Foreign
Foreign
Foreign
Canada
Canada
20-25
25-30
25-30
25-30
20-25
20-25
Very_good
Excellent
Excellent
Excellent
Excellent
Excellent
16
22
18
25
21
18
Relação candidata para a classe alvo: Estudantes de Pós (=120)
gender
major
birth_country
age_range
gpa
count
M
F
M
F
M
F
Science
Business
Business
Science
Engineering
Engineering
Foreign
Canada
Canada
Canada
Foreign
Canada
<20
<20
<20
20-25
20-25
<20
Very_good
Fair
Fair
Fair
Very_good
Excellent
18
20
22
24
22
24
Relação candidata para a classe de contraste: Estudantes de graduação (=130)
Exemplo (cont.)
• 3. Análise de Relevância
– Cálculo da informação requerida para classificar uma
tupla arbitrária
I(s 1, s 2 )  I( 120 ,130 )  
120
120 130
130
log 2

log 2
 0.9988
250
250 250
250
– Cálculo da entropia de cada atributo: ex. principal
For major=”Science”:
S11=84
S21=42
I(s11,s21)=0.9183
For major=”Engineering”: S12=36
S22=46
I(s12,s22)=0.9892
For major=”Business”:
S23=42
I(s13,s23)=0
S13=0
Numero de
estudantes de pós em
“Ciências”
Número de estudantes de
graduação em “Ciências”
Exemplo (cont.)
• Cálculo da informação esperada requerida para classificar
uma dada amostra se S for particionado segundo o atributo
E(major) 
126
82
42
I ( s11, s 21 ) 
I ( s12 , s 22 ) 
I ( s13 , s 23 )  0.7873
250
250
250
• Cálculo do ganho de informação para cada atributo
Gain(major
)  I(s1, s 2 )  E(major) 0.2115
– Ganho de informação de todos os atributos
Gain(gender)
= 0.0003
Gain(birth_country)
= 0.0407
Gain(major)
Gain(gpa)
= 0.2115
= 0.4490
Gain(age_range)
= 0.5971
Exemplo (cont.)
• 4. Derivação da relação inicial de trabalho (W0)
– R = 0.1
– Remoção de atributos irrelevantes ou pouco relevantes da relação
candidato => remover gender, birth_country
– Remoção da relação candidato classe de contraste
major
Science
Science
Science
Engineering
Engineering
age_range
20-25
25-30
20-25
20-25
25-30
gpa
Very_good
Excellent
Excellent
Excellent
Excellent
count
16
47
21
18
18
Relação inicial de trabalho da classe alvo W0: Estudantes de pós
• 5. Realizar Indução Orientada Atributo em W0 usando Ti
Descrição de Conceitos:
Caracterização e Comparação
• O que é Descrição de Conceitos?
• Caracterização baseada em generalização e resumo
• Análise da relevância de atributos
• Comparação de Classes: Discriminação entre
diferentes classes
• Estatística Descritiva em grandes bases de dados
• Discussão
Mineração da Comparação de Classes
•
•
Comparação: Comparação de duas ou mais classes.
Método:
–
–
–
–
–
•
Partição do conjunto de dados relevantes em classe alvo e
classe(s) de contraste(s)
Generalize ambas as classes nos mesmos níveis superiores de
conceitos
Compare tuplas de mesmo nível superior de descrição
Apresente para cada tupla a sua descrição e duas medidas:
• suporte – distribuição na classe isolada
• comparação – distribuição entre as classes
Destaques as tuplas com características discriminantes fortes
Análise de Relevância:
–
Encontre atributos que melhor distinguem diferentes classes.
Exemplo
• Tarefa
– Comparar estudantes de pós e de graduação usando regras
discriminantes.
– Interrogação DMQL
use Big_University_DB
mine comparison as “grad_vs_undergrad_students”
in relevance to name, gender, major, birth_place, birth_date, residence,
phone#, gpa
for “graduate_students”
where status in “graduate”
versus “undergraduate_students”
where status in “undergraduate”
analyze count%
from student
Exemplo (cont.)
• Dado
– atributos name, gender, major, birth_place,
birth_date, residence, phone# e gpa
– Gen(ai) = hierarquias de conceitos nos atributos ai
– Ui = limiar analítico de atributo para ai
– Ti = limiar para generalização de atributo para ai
– R = limiar de relevância de atributo
Exemplo (cont.)
• 1. Coleta de dados
– Classes alvo e contraste
• 2. Análise da Relevância de Atributos
– Remoção dos atributos name, gender, major, phone#
• 3. Generalização sincronizada
– Controlada pelos limiares de dimensão especificados pelo
usuário
Exemplo (cont.)
Birth_country
Canada
Canada
Canada
…
Other
Age_range
20-25
25-30
Over_30
…
Over_30
Gpa
Good
Good
Very_good
…
Excellent
Count%
5.53%
2.32%
5.86%
…
4.68%
Relação Generalizada Para a Classe Alvo: Estudantes de Pós
Birth_country
Canada
Canada
…
Canada
…
Other
Age_range
15-20
15-20
…
25-30
…
Over_30
Gpa
Fair
Good
…
Good
…
Excellent
Count%
5.53%
4.53%
…
5.02%
…
0.68%
Relação Generalizada para a Classe de Contraste: Estudantes de Graduação
Exemplo (cont.)
• 4. Apresentação
– Como relações generalizadas, tabelas cruzadas,
gráfico de barras, gráfico de setores, ou regras
– Medidas de contraste para refletir a comparação
entre as classes alvo e de contraste
• ex. contagem%
Regras Discriminantes
• Cj = Classe alvo
• qa = a generalização de uma tupla cobre algumas
tupas da classe alvo
– Mas também pode cobrir algumas da classe de contraste
• d-weight
– range: [0, 1]
d  we i gh t
cou n t(qa  Cj)
m
 cou n t(q  C )
a
i
i 1
• Forma de uma regra discriminante quantitativa
 X, target_class(X)  condition(X) [d : d_weight]
Exemplo
Status
Birth_country
Age_range
Gpa
Count
Graduate
Canada
25-30
Good
90
Undergraduate
Canada
25-30
Good
210
Distribuição de efetivos entre estudantes de pós e de graduação para uma tupla
generalizada
• Regra discriminante quantitativa
X , graduate_ student( X ) 
birth _ country( X ) "Canada"age_ range( X ) "25  30" gpa( X ) " good" [d : 30%]
– onde 90/(90+120) = 30%
Descrição de uma Classe
• Regras características quantitativas
 X, target_class(X)  condition(X) [t : t_weight]
– Condição necessária
• Regra discriminante quantitativa
 X, target_class(X)  condition(X) [d : d_weight]
– Condição suficiente
• Regra de descrição quantitativa
 X, target_class(X) 
condition1(X)[t : w1, d : w1]  ... conditionn(X)[t : wn, d : wn]
– Condição necessária e suficiente
Exemplo
Location/item
TV
Computer
Both_items
Count
t-wt
d-wt
Count
t-wt
d-wt
Count
t-wt
d-wt
Europe
80
25%
40%
240
75%
30%
320
100%
32%
N_Am
120
17.65%
60%
560
82.35%
70%
680
100%
68%
Both_
regions
200
20%
100%
800
80%
100%
1000
100%
100%
Tabela cruzada mostrando t-weight, d-weight e o número total (em milhares) de TVs e
computadores vendidos em AllElectronics em 1998
• Regra de descrição quantitativa para classe alvo Europa
 X,Europe(X)
(item (X)" TV" ) [t : 25%,d : 40%] (item (X)" com puter") [t : 75%,d : 30%]
Descrição de Conceitos:
Caracterização e Comparação
• O que é Descrição de Conceitos?
• Caracterização baseada em generalização e resumo
• Análise da relevância de atributos
• Comparação de Classes: Discriminação entre
diferentes classes
• Estatística Descritiva em grandes bases de dados
• Discussão
Mineração das Características de dispersão dos Dados
•
Motivação
–
•
Características de tendência central e de dispersão
–
•
•
Para compreender melhor os dados: tendência central, variação e
espalhamento
Média, mediana, max, min, quantis, variância, etc.
Dimensões numéricas corresponde aos intervalos ordenados
–
Dispersão dos dados: analisado com múltiplas granularidades de
precisão
–
Análise de Boxplot ou quantl nos intervalos ordenados
Análise de dispersão em medidas calculadas
–
Análises Boxplot ou quantl no cubo transformado
Medidas de Tendência Central
•
Media
–
•
1 n
x   xi
n i 1
n
Média aritmética ponderada
Mediana: medida holística
–
•
i 1
n
i
i
w
i 1
i
Valor na posição média se o número de valores é par, ou média dos
valores de posição média senão
–
x 
w x
Estimação via interpolação
mediana L1  (
n / 2  ( f )l
f mediana
Moda
–
Valor mais frequente nos dados
–
Unimodal, bimodal, trimodal
–
Formula empírica:
mean mode 3  (mean median)
)c
Medidas de dispersão
•
•
Quartis, outliers e boxplots
–
Quartils: Q1 (25o percentil), Q3 (75o percentil)
–
Amplitude Inter-quartil: IQR = Q3 – Q1
–
Resumo cinco números: min, Q1, Mediana, Q3, max
–
Boxplot: nas extremidades da caixa estão os quartis, a mediana é a
linha central, extremos, e plota individualmente os outliers
–
Outlier: usualmente, um valor maior/menor do que 1.5 x IQR
Variancia e Desvio-padrão
–
Variancia s2: (algebraica,
cálculo escalável)
n
1
1
s
–
2

n 1
(x
i 1
i
 x)
2

n 1
n
[ xi
i 1
Desvio padrão s é a raiz quadrada da variância s2
2
n
1

( xi ) 2 ]
n i 1
Análise com Boxplot
• Sumário cinco números de uma distribuição:
Mínimo, Q1, Mediana, Q3, Maximo
• Boxplot
– No inicio e no final da caixa estão o primeiro e o
terceiro quartil: a altura da caixa é o IRQ
– A mediana é destacada por uma linha dentro da
caixa
– Extremos: duas linhas fora da caixa destacam o
mínimo e o máximo
Um Boxplot
Um boxplot
Mineração de medidas de Estatística
Descritiva em Grandes Bases de Dados
• Variância
1 n
1 
1
2
2
2
s 
(
x

x
)

x


x

 i
 i
 i 
n  1 i 1
n  1 
n

2
• Desvio padrão: raiz quadrada da variância
– Mede a dispersão em torno da média
– É zero se e somente se todos os valores são iguais
– Tanto o desvio quanto a variância são algebraicos
Análise de Histograma
– Histograma de freqüências
• Método gráfico univariado
• Consiste em um conjunto de retângulos justapostos que refletem a
freqüência das classes presentes nos dados
Diagrama Quantil
• Mostra todos os dados (permite ao usuário acessar tanto o
comportamento global como as ocorrências não usuais)
• Diagrama quantil
– Para os xi classificados em ordem crescente, fi indica que
aproximadamente 100 fi% dos datas são menores ou
iguais a xi
Diagrama Quantil-Quantil (Q-Q)
• Mostra os quantis de uma distribuição univariada contra os
correspondentes quantis de uma outra
• Permite que o usuário veja se há um deslocamento ao ir de
uma distribuição a outra
Diagrama de Dispersão
• Fornece uma primeira visão de dados bi-variados para
identificar clusters de pontos, outliers, etc
• Cada par de valores é tratado como um par de coordenadas e
desenhado como pontos no plano
Curva de Loess
• Adiciona uma curva suave em um diagrama de dispersão para
fornecer uma melhor percepção dos padrões de dependência
• Uma Curva de Loess é ajustada pelo controle de dois
parâmetros: um parâmetro de suavização, e o grau dos
polinômios que serão ajustados via regressão
Descrição de Conceitos:
Caracterização e Comparação
• O que é Descrição de Conceitos?
• Caracterização baseada em generalização e resumo
• Análise da relevância de atributos
• Comparação de Classes: Discriminação entre
diferentes classes
• Estatística Descritiva em grandes bases de dados
• Discussão
Indução Orientada-Atributo vs
Aprendizagem à partir de exemplos
• Diferenças na filosofia e nas suposições básicas
– Aprendizagem à partir de exemplos: exemplos positivos
usados para a generalização e negativos para a
especialização
– Em mineração apenas exemplos positivos: o drill-down
retorna a generalização à um estado prévio
• Diferenças no tamanho do conjunto de treinamento
• Diferença nos métodos de generalização
– Aprendizagem de máquina generaliza na base tupla por
tupla
– Mineração generaliza na base atributo por atributo
Mineração Incremental e Paralela para a
Descrição de Conceitos
• Mineração Incremental: revisão baseada em dados
recentemente adicionados DB
– Generalize DB no mesmo nível de abstração da relação
generalizada R para obter R
– União R U R, i.e., fusionar a contagem e as outras
estatísticas para produzir uma nova relação R’
• Filosofia similar pode ser aplicada a amostragem de
dados, mineração paralela e/ou distribuída, etc.