Seleção de Características
através de
Nearest Shrunken Centroids
DIEGO RICARDO DE ARAUJO
DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO
INSTITUTO DE CIÊNCIA EXATAS
UNIVERSIDADE FEDERAL DE JUIZ DE FORA
Introdução
Classificação de Dados
Seleção de Características
Sistema Inteligente
Testes Comparativos
Resultados
Considerações Finais
2
Descoberta de Conhecimento
em Bases de Dados
 Crescente fluxo de dados
 Dados
coletados e acumulados rapidamente
 Transformação de informação em
conhecimento útil
4
Descoberta de Conhecimento
em Bases de Dados
 Pré-processamento: dados preparados
para mineração
 Mineração de dados: extração de
conhecimento através de métodos
inteligentes
 Avaliação
 Apresentação: representação e visualização
do conhecimento para o usuário
5
Mineração de Dados
 Análise de grandes base de dados
 Extração de padrões de interesse do
modelo de dados
 Conjunto
de dados
 Domínio de conhecimento
 Métodos de mineração
 Avaliação de padrões
7
Mineração de Dados
8
Introdução
Classificação de Dados
Seleção de Características
Sistema Inteligente
Testes Comparativos
Resultados
Considerações Finais
9
Processo de classificação
 Treinamento
 Aprendizado
de conhecimento a partir de
amostras com classes conhecidas
11
Processo de classificação
 Teste
 Avaliação
do conhecimento descoberto pelo
treinamento através da predição de classe
de amostras desconhecidas
12
Avaliação dos Métodos de
Classificação
 Acurácia: índice de exatidão de classificação
de amostras desconhecidas
 Desempenho: velocidade e custo
computacional referente a utilização do
classificador
14
Avaliação dos Métodos de
Classificação
 Robustez: capacidade de realizar predições
corretas a partir de conjuntos de dados com
amostras incompletas ou com ruído
 Escalabilidade: eficiência do modelo de
conhecimento a partir de uma grande
quantidade de dados
 Interpretabilidade: compreensão do modelo
de conhecimento extraído do modelo de
dados
15
Método Nearest Centroid
 Centróide
 Centro
de distribuição de um conjunto de
amostras
 Amostras
de treinamento: centróide geral
 Amostras de determinada classe: centróide de
classe
17
Método Nearest Centroid
 Matematicamente
um espaço p-dimensional, sendo p o
numero de atributos i = 1, 2, ... , p
presentes num conjunto de dados composto
de n amostras j = 1, 2, ... , n
 Seja
 xij
a expressão do i-ésimo atributo da
amostra j. Cada amostra está associada a
uma classe k, pertencente a um conjunto
discreto de K classes, Ck = (1, 2, ... ,K)
cada classe k, estão associadas nk
amostras que compõem o modelo de dados.
A
18
Método Nearest Centroid
 Matematicamente

O i-ésimo componente dos centróides
 Geral
x i   j  1 xij / n
n
 De
classe
xik  i  C xij / nk
k
19
Método Nearest Centroid
 Função de distância
 k x   
p
*
i 1
x
*
i
 x ik
si2

2
 2 log  k
 Sendo
2
1
s 
   xij  xik 
n  K k i  Ck
2
i
 k  nk / n

K
k 1
k 1
 Classificação
20
Introdução
Classificação de Dados
Seleção de Características
Sistema Inteligente
Testes Comparativos
Resultados
Considerações Finais
21
Seleção de Características
 Teoria
 Maior
quantidade de atributos: maior poder
de discernimento
 Prática
 Informações
irrelevantes confundem e
retardam os sistemas de aprendizado
22
Seleção de Características
 Motivação
 Existência
de bases de dados com alto nível
dimensional que acarretam alto custo
computacional (baixo desempenho) e/ou
pouca acurácia no processo de mineração
de dados
23
Seleção de Características
 Eliminação de atributos
irrelevantes/redundantes do modelo de
dados
 Busca da melhoria do processo de
descoberta de conhecimento
24
Método Nearest Shrunken Centroid
 Distância estatística
xik  xi
dik 
mk  si
xik  xi  mk si dik
 Sendo
mk  1/ nk  1/ n
26
Método Nearest Shrunken Centroid
 Função de limiarização suave
d 'ik  sign dik  .  dik  
27
Método Nearest Shrunken Centroid
 Dessa forma
x'ik  xi  mk si d 'ik
 Se dado atributo i, ∃∆ tal que ∀k tem-se
d’ik = 0, então o i-ésimo componente dos
centróides são eliminados pois não interferem
na tarefa de classificação
 k x   
p
*
i 1
x
*
i
 x ik
si2

2
 2 log  k
28
Shrunken Centroids
29
Introdução
Classificação de Dados
Seleção de Características
Sistema Inteligente
Testes Comparativos
Resultados
Considerações Finais
30
Sistema Inteligente
31
Sistema Inteligente
 File: arquivo físico da base de dados
 *.arff
 *.dat
 Sample: amostra da base de dados.
Composta por seus atributos (values) e
identificada por sua classe
32
Sistema Inteligente
 DataBase: representação da base de
dados. Composta de um conjuntos de
amostras (samples)
 Centroid: centróide de um conjunto de
amostras
33
Sistema Inteligente
 NearestCentroidClassifier: classificador
NSC
de treinamento: trainingSet
 Conjunto de teste: testSet
 Centróides de classe: classCentroids
 Centróide geral: overallCentroids
 Classificação de amostra: classify(sample)
 Conjunto
34
Sistema Inteligente
 Shrinker
 Seleção
de características
 Realiza a redução dos centróides
shrinkCentroids()
NearestCentroidClassifier
searchDelta()
crossValidation()
de kfolds
35
Introdução
Classificação de Dados
Seleção de Características
Sistema Inteligente
Testes Comparativos
Resultados
Considerações Finais
36
Metodologia
 Sub-divisão das bases de dados
 Testes
de classificação
75%
conjunto de treinamento
25% conjunto de teste
 Seleção
de características
Dados
originais
Dados reduzidos
38
Metodologia
 Validação Cruzada
39
Metodologia
 Validação Cruzada
 Neste
trabalho convencionou-se a utilização de
validação cruzada de 10 folhas como ponto de
partida para o processo de avaliação de
classificação
40
Metodologia
 Bases de dados utilizadas
Breast
 Colon
 Glasses
 Iris
 Leukemia
 Lymphoma
 Prostate

41
Metodologia
 Classificadores utilizados


NSC
Weka: suíte de mineração de dados
 Naive-Bayes
 SMO
 Multilayer Perceptron
 J48
 Random Forest
42
Testes Comparativos
Por Base de Dados
43
Breast
44
Colon
45
Glasses
46
Iris
47
Leukemia
48
Lymphoma
49
Prostate
50
Testes Comparativos
Por Classificador
51
NSC
52
Naive-Bayes
53
SMO
54
Multilayer Perceptron
55
J48
56
Random Forest
57
Introdução
Classificação de Dados
Seleção de Características
Sistema Inteligente
Testes Comparativos
Resultados
Considerações Finais
58
Resultados
 Média por Base de Dados
 Média por Classificador
59
Resultados
 Numero de Atributos x Desempenho
 Grande
redução do número de atributos
 Ganho considerável de desempenho
 Maiores índices
 Bases
de dados de alto nível dimensional
60
Resultados
 Acurácia
 Perda
pouco significativa de acurácia
 Melhores índices
 Base
de dados: Leukemia (+2,22%)
 Classificador: Multilayer Perceptron (+0,96%)
 Piores
índices
 Base
de dados: Breast (-8%)
 Classificador: Random Forest (-3,43%)
61
Resultados
 Desempenho x Acurácia
 Ganho
de desempenho e de acurácia
Bases de dados de alto nível dimensional
62
Introdução
Classificação de Dados
Seleção de Características
Sistema Inteligente
Testes Comparativos
Resultados
Considerações Finais
63
Considerações Finais
 Ganho considerável de desempenho
 Queda pouco significativa de acurácia
 Melhores resultados em bases de dados
de alto nível dimensional
64
Considerações Finais
 Trabalhos Futuros
 Estudos
 Outros
comparativos
métodos de seleção de características
 Variação
da proporção entre número de
amostras de treinamento e teste
65