Algoritmos de Aprendizagem Baseados em
Instâncias: Técnicas de Redução
Cesar Lima Pereira
George Darmiton da Cunha Cavalcanti (Orientador)
Introdução

Aprendizado supervisionado
T
Algoritmo de Aprendizagem
x
Classificador
Conhecimento
2
Motivação

Melhora em desempenho

Remoção de:

Dados ruidosos

Dados irrelevantes
3
Definição

Técnicas de Redução
4
Características I

Representação dos dados

Direção da busca

Pontos de borda ou centrais

Função de dissimilaridade

Números de vizinhos
5
Características II

Estratégias de avaliação:

Capacidade de redução

Melhora em desempenho

Precisão em generalização

Tolerância a ruídos

Desempenho

Capacidade de aprendizagem incremental
6
Técnicas I

Condensed Nearest Neighbor Rule (CNN)

Reduced Nearest Neighbor Rule (RNN)

Edited Nearest Neighbor Rule (ENN)

Repeated Nearest Neighbor Rule (RENN)

All-KNN

Instance-Based Learning Algorithm 1 e 2 (IB2 e
IB3)
7
Técnicas II


Decremental Reduction Optimization
Procedures (DROP1, DROP2, DROP3, DROP4
e DROP5)
Decremental Encoding Length (DEL)
8
CNN
1. Adicione uma instância aleatória de T em S
2. Enquanto houver modificação no conjunto S
3. Para as demais instâncias t em T
4.
Se classe(t) ≠ classe(vizinhos de t em S)
5.
Adicione t ao subconjunto S
9
DROP1 I

Definição

Associados

k+1 Vizinhos de X: Y, W, Z e V
Y
List a s de Associa dos
X
W
Z
Y
W
Z
V
...
X
X
X
X
...
...
...
...
...
...
V
10
DROP1 II
1. Seja S = T
2. Para cada instância s em S
3. Encontre, e guarde, os k+1 vizinhos mais próximos de s
4. Adicione s à lista de associados de cada um de seus
5. Para cada instância s em S
6. Seja x = número de associados de s classificados
incluindo s
7. Seja y = número de associados de s classificados
excluindo s
8. Se (y – x) ≥ 0
9.
Remova s de S
10.
Para cada associado a de s
11.
Encontre um novo vizinho para a
12.
Adicione a à lista de associados do novo vizinho
13.
Para cada vizinho n de s
14.
Remova s da lista de associados de n
vizinhos
corretamente
corretamente
11
Experimentos I

10 bases de dados

Australian, Breast Cancer, CRX, Glass, Hepatitis,
Ionosphere, Iris, Liver, Pima Diabetes e Wine

ten-fold cross validation

Classificador KNN, com k = 3
12
Experimentos II

Medidas de distância

Euclidiana

Simple Adaptative Distance

Heterogeneous Value Difference Metric (HVDM)
13
Resultados I

Distância Euclidiana
Precisão (%)
Hepatitis
Ion osph ere Média
KNN
82,63 ± 3,02 84,62 ± 3,44 83,62
CNN
78,04 ± 4,39 85,20 ± 3,78 81,62
RNN
76,79 ± 2,60 84,91 ± 3,79 80,85
ENN
83,33 ± 3,92 83,19 ± 3,46 83,26
RENN
83,33 ± 3,92 83,19 ± 3,46 83,26
All-KNN 83,96 ± 4,60 84,04 ± 3,32 84,00
IB2
72,83 ± 4,45 85,48 ± 2,94 79,16
IB3
78,08 ± 2,71 83,19 ± 4,64 80,64
DEL
82,63 ± 4,06 84,33 ± 3,03 83,48
DROP1
82,63 ± 3,02 83,45 ± 3,37 83,04
DROP2
84,50 ± 4,35 85,48 ± 2,55 84,99
DROP3
81,96 ± 2,95 85,47 ± 1,58 83,71
DROP4
80,58 ± 3,53 88,02 ± 2,42 84,30
DROP5 85,17 ± 4,14 87,18 ± 2,04 86,17
Média
81,18
84,84
83,01
Redu ção (%)
Hepatitis
Ion osph ere
KNN
100,00 ± 0,00 100,00 ± 0,00
CNN
37,77 ± 0,98 25,77 ± 0,62
RNN
36,56 ± 1,25 25,83 ± 0,59
ENN
81,72 ± 0,75 84,87 ± 0,52
RENN
81,72 ± 0,75 84,87 ± 0,52
All-KNN 87,81 ± 0,41 90,06 ± 0,37
IB2
25,88 ± 0,97 19,15 ± 0,87
IB3
10,39 ± 1,45 9,43 ± 2,82
DEL
86,81 ± 0,60 92,47 ± 0,31
DROP1
9,75 ± 0,51 6,49 ± 0,39
DROP2
16,78 ± 1,24 11,08 ± 0,70
DROP3
12,26 ± 0,83 6,49 ± 0,42
DROP4
11,76 ± 0,83 8,67 ± 0,51
DROP5
12,12 ± 0,97 9,18 ± 0,64
Média
43,67
41,03
Média
100,00
31,77
31,19
83,30
83,30
88,94
22,51
9,91
89,64
8,12
13,93
9,37
10,22
10,65
42,35
Tempo (s)
Hepatitis
Ion osph ere Média
KNN
0,000 ± 0,000 0,000 ± 0,000 0,000
CNN
0,031 ± 0,003 0,183 ± 0,016 0,107
RNN
0,081 ± 0,011 0,452 ± 0,134 0,267
ENN
0,032 ± 0,002 0,271 ± 0,002 0,152
RENN
0,060 ± 0,000 0,501 ± 0,004 0,281
All-KNN 0,063 ± 0,002 0,546 ± 0,017 0,305
IB2
0,004 ± 0,003 0,035 ± 0,004 0,020
IB3
0,069 ± 0,008 1,319 ± 0,298 0,694
DEL
0,129 ± 0,004 1,240 ± 0,026 0,685
DROP1 0,169 ± 0,003 1,398 ± 0,043 0,784
DROP2 0,225 ± 0,008 3,350 ± 0,057 1,788
DROP3 0,292 ± 0,007 4,864 ± 0,058 2,578
DROP4 0,293 ± 0,008 4,166 ± 0,050 2,230
DROP5 0,408 ± 0,010 5,549 ± 0,104 2,979
Média
0,133
1,705
0,919
14
Resultados II

Distância Adaptativa
Precisão (%)
Hepatitis
Ion osph ere Média
KNN
80,63 ± 2,63 93,16 ± 1,68 86,89
CNN
80,00 ± 4,41 92,58 ± 2,05 86,29
RNN
78,54 ± 4,93 93,72 ± 1,88 86,13
ENN
79,33 ± 5,35 92,59 ± 2,54 85,96
RENN
79,33 ± 5,35 92,59 ± 2,54 85,96
All-KNN 80,58 ± 4,32 92,59 ± 2,36 86,59
IB2
76,79 ± 4,34 92,30 ± 2,03 84,55
IB3
70,88 ± 6,37 89,75 ± 1,20 80,31
DEL
78,17 ± 4,13 93,44 ± 1,36 85,81
DROP1
76,25 ± 7,01 76,37 ± 6,82 76,31
DROP2 83,83 ± 3,16 87,17 ± 4,22 85,50
DROP3
75,00 ± 7,35 79,22 ± 3,65 77,11
DROP4
78,08 ± 2,20 90,03 ± 2,45 84,06
DROP5
78,08 ± 3,46 87,74 ± 3,99 82,91
Média
78,25
89,52
83,88
Redu ção (%)
Hepatitis
Ion osph ere
KNN
100,00 ± 0,00 100,00 ± 0,00
CNN
38,14 ± 1,12 17,60 ± 0,76
RNN
37,06 ± 0,97 16,37 ± 0,51
ENN
82,29 ± 0,50 95,44 ± 0,25
RENN
82,29 ± 0,50 95,44 ± 0,25
All-KNN 88,89 ± 0,60 94,21 ± 0,47
IB2
23,44 ± 1,04 14,37 ± 0,57
IB3
11,11 ± 1,05 13,04 ± 0,61
DEL
89,39 ± 0,99 97,47 ± 0,22
DROP1
8,61 ± 1,24 6,55 ± 0,40
DROP2
14,55 ± 1,10 12,25 ± 0,48
DROP3
8,10 ± 0,77 11,33 ± 0,37
DROP4
10,11 ± 0,98 10,83 ± 0,47
DROP5
9,82 ± 1,22 12,44 ± 0,68
Média
43,13
42,67
Média
100,00
27,87
26,71
88,87
88,87
91,55
18,91
12,08
93,43
7,58
13,40
9,72
10,47
11,13
42,90
Tempo (s)
Hepatitis
Ion osph ere
KNN
0,000 ± 0,000 0,000 ± 0,000
CNN
0,204 ± 0,008 0,634 ± 0,057
RNN
0,583 ± 0,103 1,565 ± 0,239
ENN
0,177 ± 0,002 1,465 ± 0,033
RENN
0,298 ± 0,003 2,678 ± 0,056
All-KNN 0,571 ± 0,013 5,582 ± 0,223
IB2
0,032 ± 0,005 0,178 ± 0,014
IB3
0,950 ± 0,187 6,272 ± 0,514
DEL
0,845 ± 0,038 5,810 ± 0,196
DROP1 1,915 ± 0,019 26,512 ± 0,181
DROP2 2,406 ± 0,043 33,753 ± 0,387
DROP3 2,184 ± 0,036 33,300 ± 0,279
DROP4 1,967 ± 0,024 30,974 ± 0,352
DROP5 2,218 ± 0,045 28,593 ± 0,349
Média
1,025
12,665
Média
0,000
0,419
1,074
0,821
1,488
3,077
0,105
3,611
3,328
14,214
18,080
17,742
16,471
15,406
6,845
15
Resultados III

Distância HVDM
Precisão (%)
Hepatitis
Ion osph ere Média
KNN
81,38 ± 3,39 84,60 ± 3,39 82,99
CNN
79,33 ± 3,36 85,47 ± 3,12 82,40
RNN
80,00 ± 2,77 84,91 ± 2,84 82,46
ENN
83,29 ± 2,94 81,18 ± 3,04 82,24
RENN
83,29 ± 2,94 81,18 ± 3,04 82,24
All-KNN 83,33 ± 3,89 83,17 ± 2,67 83,25
IB2
75,00 ± 5,29 84,89 ± 2,45 79,94
IB3
36,67 ± 13,70 88,88 ± 3,12 62,77
DEL
80,08 ± 3,43 84,32 ± 3,59 82,20
DROP1
80,04 ± 4,91 85,75 ± 3,70 82,89
DROP2
83,29 ± 3,34 89,17 ± 2,11 86,23
DROP3
81,96 ± 4,59 82,63 ± 2,16 82,29
DROP4 84,54 ± 2,67 85,75 ± 3,02 85,14
DROP5
82,08 ± 5,10 87,17 ± 2,55 84,63
Média
78,16
84,93
81,55
Redu ção (%)
Hepatitis
Ion osph ere
KNN
100,00 ± 0,00 100,00 ± 0,00
CNN
36,63 ± 0,66 25,70 ± 0,66
RNN
37,05 ± 1,99 25,77 ± 0,85
ENN
81,73 ± 1,43 84,24 ± 0,48
RENN
81,73 ± 1,43 84,24 ± 0,48
All-KNN 89,89 ± 0,56 90,35 ± 0,37
IB2
24,01 ± 0,83 19,28 ± 0,65
IB3
4,80 ± 2,14 16,56 ± 0,52
DEL
88,96 ± 0,95 92,78 ± 0,22
DROP1
8,39 ± 1,09 6,58 ± 0,37
DROP2
14,41 ± 1,29 11,65 ± 0,49
DROP3
9,68 ± 1,82 7,06 ± 0,52
DROP4
9,90 ± 1,73 9,12 ± 0,37
DROP5
12,26 ± 1,75 10,03 ± 0,49
Média
42,82
41,67
Média
100,00
31,17
31,41
82,98
82,98
90,12
21,65
10,68
90,87
7,49
13,03
8,37
9,51
11,15
42,24
Tempo (s)
Hepatitis
Ion osph ere Média
KNN
0,000 ± 0,000 0,000 ± 0,000 0,000
CNN
0,215 ± 0,016 0,265 ± 0,019 0,240
RNN
0,657 ± 0,152 0,544 ± 0,151 0,601
ENN
0,242 ± 0,003 0,368 ± 0,005 0,305
RENN
0,437 ± 0,003 0,666 ± 0,011 0,552
All-KNN 0,484 ± 0,004 1,140 ± 0,046 0,812
IB2
0,032 ± 0,003 0,053 ± 0,003 0,043
IB3
0,657 ± 0,116 1,309 ± 0,188 0,983
DEL
0,610 ± 0,014 1,731 ± 0,019 1,171
DROP1 0,817 ± 0,017 2,509 ± 0,044 1,663
DROP2 1,082 ± 0,037 4,368 ± 0,056 2,725
DROP3 1,222 ± 0,035 5,200 ± 0,086 3,211
DROP4 1,435 ± 0,010 5,157 ± 0,097 3,296
DROP5 2,200 ± 0,153 7,700 ± 0,115 4,950
Média
0,721
2,215
1,468
16
Resultados IV

Média Geral (HVDM)
KNN
CNN
RNN
ENN
RENN
All-KNN
IB2
IB3
DEL
DROP1
DROP2
DROP3
DROP4
DROP5
Média
Precisão (%)
82,45
81,46
80,91
82,25
82,25
82,70
78,46
77,04
81,68
77,14
82,10
80,67
81,57
79,63
80,74
Armazen amen to (%)
100,00
35,17
35,32
82,64
82,64
90,51
24,70
13,69
67,53
12,28
19,13
12,53
14,14
14,43
43,19
17
Resultados V

Média Geral (Euclidiana)

Gráfico (tempo de execução)
KNN
CNN
RNN
ENN
RENN
Al l -KNN
IB2
Tem po (s)
IB3
DEL
DROP1
DROP2
DROP3
DROP4
DROP5
0 ,0 0 0
0 ,5 0 0
1 ,0 0 0
1 ,5 0 0
2 ,0 0 0
2 ,5 0 0
3 ,0 0 0
3 ,5 0 0
4 ,0 0 0
4 ,5 0 0
5 ,0 0 0
18
Resultados VI

Medidas de Distância (Precisão)
100,00
90,00
Euclidiana
Adaptativa
HVDM
Precisão
80,00
70,00
60,00
in
W
e
a
er
es
et
ab
e
er
is
ph
Di
os
m
Pi
v
Li
s
Ir i
n
Io
t it
pa
He
nc
Ca
n
lia
ra
s
as
Gl
X
CR
st
st
ea
Br
Au
er
Bases d e Dad os
Eu clidian a
Adaptativa
HVDM
Au stralian
82,85
82,31
79,54
Breast Can cer
95,04
95,49
92,50
CRX
83,80
82,21
80,16
Glass
64,32
63,75
64,23
Hepatitis
81,16
77,20
78,82
Ion osph ere
84,88
87,28
85,02
Iris
94,67
94,83
92,80
Liver
63,92
64,17
61,00
Pima Diabetes
70,21
70,00
71,29
Win e
70,38
68,89
94,91
Média
79,12
78,61
80,03
19
Resultados VII

Medidas de Distância (Armazenamento)
Armazenamento (%)
50,00
45,00
40,00
Euclidiana
Adaptativa
HVDM
35,00
30,00
25,00
in
W
e
a
er
es
et
ab
e
er
is
ph
Di
os
m
Pi
v
Li
s
Ir i
n
Io
t it
pa
He
nc
Ca
n
lia
ra
s
as
Gl
X
CR
st
st
ea
Br
Au
er
Bases d e Dad os
Eu clidian a
Adaptativa
HVDM
Au stralian
38,79
37,82
36,36
Breast Can cer
33,19
32,35
32,87
CRX
38,69
38,66
36,18
Glass
39,87
41,21
39,37
Hepatitis
37,31
36,49
36,51
Ion osph ere
34,87
36,79
35,49
Iris
30,06
36,76
30,14
Liver
43,60
43,44
45,77
Pima Diabetes
39,55
38,42
40,85
Win e
34,38
35,23
28,66
Média
37,03
37,72
36,22
20
Conclusão I

CNN e RNN


ENN, RENN e All-KNN


Ótimos filtros
IB2 e IB3


Melhor relação: precisão x redução x tempo
Boa redução
DEL

Redução tímida porém boa precisão
21
Conclusão II

DROP1


Melhor taxa de redução
DROP2-5

Melhor relação: precisão x redução
22
Algoritmos de Aprendizagem Baseados em
Instâncias: Técnicas de Redução
Cesar Lima Pereira
George Darmiton da Cunha Cavalcanti (Orientador)