Extensões do algoritmo BRkNN para aprendizado multirrótulo

Prévia do material em texto

Extensões do algoritmo de aprendizado de máquina
multirrótulo BRkNN
Denis Moreira dos Reis1, Everton Alvares Cherman1, Newton Spolaôr1,
Maria Carolina Monard1
1Laboratório de Inteligência Computacional
Instituto de Ciências Matemáticas e de Computação
Universidade de São Paulo
{denismr,evertoncherman}@gmail.com,mcmonard@icmc.usp.br
Abstract. Unlike single-label learning, in multi-label learning each example in
the training set is associated with a set of labels which are usually correlated.
Given an unclassified example, the task of a multi-label classifier is to output
the example label set whose size is unknown a priori. To this end, the single-
label k Nearest Neighbor algorithm has been used as a base to develop several
lazy multi-label learning algorithms, such as the BRkNN algorithm. This work
proposes some extensions to BRkNN, among them the use of the Heterogeneous
Value Difference Metric, which considers information from the labels. Illustra-
tive experiments on benchmark datasets show the usefulness of the proposed
extensions.
Resumo. Diferentemente do aprendizado monorrótulo, cada exemplo de trei-
namento no aprendizado multirrótulo está associado a um conjunto de rótulos
usualmente correlacionados. Dado um exemplo não rotulado, a tarefa de um
classificador multirrótulo é predizer o conjunto de rótulos para esse exemplo.
O algoritmo monorrótulo k Nearest Neighbor tem sido utilizado como uma base
para desenvolver vários algoritmos de aprendizado multirrótulo lazy, como
o algoritmo BRkNN. Neste trabalho são propostas algumas extensões para o
BRkNN, como o uso da medida Heterogeneous Value Difference Metric, a qual
considera informação dos rótulos. Experimentos ilustrativos em conjuntos de
dados benchmark mostram a eficácia preditiva dessas extensões.
1. Introdução
O aprendizado supervisionado monorrótulo é uma tarefa tradicional em aprendizado de
máquina na qual os exemplos do conjunto de treinamento estão associados a um único
rótulo yi do conjunto de possı́veis rótulos L, i.e., yi ∈ L com |L| > 1. No caso em que
|L| = 2 a tarefa é chamada de aprendizado binário, enquanto é denominada aprendizado
multiclasse para |L| > 2.
Contudo, existem diversas aplicações, como anotação de mı́dias [Liu et al. 2010],
bioinformática [Park et al. 2011] e categorização de texto [Esuli and Sebastiani 2009],
em que os exemplos do conjunto de treinamento estão associados não apenas a um único
rótulo, mas um conjunto de rótulos Y , com Y ⊆ L. Nesse caso, a tarefa de aprendizado
é denominada multirrótulo [Tsoumakas et al. 2009].
Diversos algoritmos têm sido desenvolvidos para tratar o problema mul-
tirrótulo [Carvalho and Freitas 2009]. Esses algoritmos podem ser organizados em dois
grupos distintos, como proposto em [Tsoumakas et al. 2009]: 1) Adaptação de algorit-
mos; e 2) Transformação de problema. No primeiro grupo, o problema multirrótulo é
tratado diretamente por um algoritmo de aprendizado multirrótulo. No caso do segundo
grupo, os algoritmos de aprendizado multirrótulo transformam o problema multirrótulo
em um ou mais problemas monorrótulo e, assim, algoritmos de aprendizado monorrótulo
podem ser utilizados para a resolução do problema. Um método tradicional deste segundo
grupo é Binary Relevance (BR), o qual transforma o problema multirrótulo em diversos
problemas binários, um para cada rótulo do problema multirrótulo.
O algoritmo k Nearest Neighbor (kNN) tem sido explorado para resolução do
problema multirrótulo, principalmente pela sua simplicidade e também pela sua eficácia
em diversos casos [Younes et al. 2011, Spyromitros et al. 2008, Zhang and Zhou 2005].
Basicamente, o kNN busca k exemplos de treinamento (vizinhos) similares ao exemplo
a ser rotulado E, conforme uma medida de similaridade. Após encontrar os vizinhos,
analisa-se seus rótulos para predizer a classificação de E. Uma maneira intuitiva para
aplicar o algoritmo tradicional kNN em dados multirrótulo é por meio do método BR.
No entanto, no trabalho de [Spyromitros et al. 2008], foi proposto o algoritmo BRkNN,
o qual obtém os mesmos resultados do uso do kNN conjuntamente com BR, porém é |L|
vezes mais rápido. Além disso, foram propostas duas extensões para melhoria na eficácia
preditiva do BRkNN.
Neste trabalho, são propostas extensões no algoritmo BRkNN em três aspectos
distintos, dos quais dois são relacionados ao peso dado aos k vizinhos no momento de
definição do conjunto de rótulos a ser predito, enquanto o outro aspecto refere-se à medida
de similaridade utilizada, no qual, a medida Heterogeneous Value Difference Metric é
adaptada para uso no problema multirrótulo. Experimentos ilustrativos realizados em
quatro conjuntos de dados benchmark sugerem que as extensões melhoram o desempenho
do BRkNN.
O restante desse trabalho está organizado da seguinte maneira: na Seção 2 são
apresentados conceitos básicos de aprendizado multirrótulo e as medidas de avaliação de
classificadores multirrótulo comumente utilizadas. Na Seção 3, o algoritmo kNN tradici-
onal é descrito com maior detalhamento, bem como a estratégia baseada nesse algoritmo
para tratar com o problema multirrótulo e os trabalhos relacionados. Na Seção 4 são apre-
sentados o protocolo experimental, os resultados e a discussão. Por fim, na Seção 5 são
descritos a conclusão e trabalhos futuros.
2. Aprendizado multirrótulo
No aprendizado multirrótulo, a entrada do algoritmo consiste de um conjunto D de N
exemplos Ei = (xi,Yi), i.e., D = {(x1,Y1), (x2,Y2), . . . , (xN ,YN)}. Os xi são tipicamente
vetores da forma (xi1,xi2, . . . ,xiM) com valores categóricos ou numéricos, tal que xij
refere-se ao valor do atributo j, denominado Xj , do exemplo Ei. Cada exemplo Ei está
associado a um conjunto de rótulos Yi, onde Yi ⊆ L e L = {y1, y2, y3, . . . , yq} — Ta-
bela 1.
Neste cenário, o objetivo de algoritmos de aprendizado multirrótulo é gerar um
classificador H tal que, dado um exemplo não rotulado E = (x, ?), prediz o conjunto
Tabela 1. Conjunto de dados multirrótulo.
X1 X2 . . . XM Y
E1 x11 x12 . . . x1M Y1
E2 x21 x22 . . . x2M Y2
...
...
... . . .
...
...
EN xN1 xN2 . . . xNM YN
de rótulos Y ao qual deve ser associado, i.e., H(E) → Y . A principal diferença en-
tre aprendizado multirrótulo e aprendizado monorrótulo é que os rótulos no conjunto de
rótulos no aprendizado multirrótulo estão frequentemente correlacionados, enquanto que
os possı́veis valores da classe (rótulos) no aprendizado monorrótulo são mutuamente ex-
clusivos.
Métodos de aprendizado multirrótulo são organizados em categorias, entre elas
adaptação de algoritmo e transformação do problema [Tsoumakas et al. 2009]. A pri-
meira categoria abrange métodos que estendem algoritmos de aprendizado especı́ficos
de modo a tratar dados multirrótulo diretamente. O algoritmo BRkNN utilizado neste
trabalho situa-se nessa categoria. A segunda categoria, exemplificada pelas abordagens
Binary Relevance (BR) e Label Powerset (LP), é independente de algoritmo, possibili-
tando o uso de qualquer algoritmo do estado da arte de aprendizado monorrótulo para
realizar aprendizado multirrótulo. A abordagem BR transforma o problema multirrótulo
em |L| problemas de classificação binária. Posteriormente, a predição do multirrótulo de
um exemplo a ser classificado E é obtida por meio da união dos rótulos preditos pelos
classificadores binários que classificam esse exemplo como positivo. Por outro lado, a
abordagem LP transforma um problema multirrótulo em um problema multiclasse, con-
siderando cada conjunto de rótulos idênticos em D como um valor da classe no conjunto
multiclasse, i.e., um conjunto de exemplos monorrótulo no qual a classe assume mais de
dois valores.
As medidas para avaliar classificadores monorrótulo consideram apenas os dois
possı́veis estados da classificação de um exemplo: correta ou incorreta. Entretanto, na
classificaçãomultirrótulo elas devem também levar em conta estados “parcialmente” cor-
retos. Assim, várias medidas tem sido propostas para avaliar classificadores multirrótulo,
as quais consideram diversos aspectos da classificação. Uma discussão sobre essas medi-
das foge ao escopo deste trabalho e pode ser encontrada em [Tsoumakas et al. 2009]. A
seguir são apresentadas as medidas utilizadas neste trabalho.
As medidas que consideram as diferenças entre o conjunto de rótulos esperado
Yi e o predito Zi nos exemplos do conjunto de teste são chamadas Baseadas em Exem-
plos. Neste trabalho utilizamos três delas, Hamming Loss, Accuracy e Subset Accuracy,
definidas pelas Equações 1 a 3.
Hamming Loss(H,D) =
1
N
N∑
i=1
|Yi∆Zi|
|L|
. (1)
Accuracy(H,D) =
1
N
N∑
i=1
|Yi ∩ Zi|
|Yi ∪ Zi|
. (2)
SubsetAccuracy(H,D) =
1
N
N∑
i=1
I(Zi = Yi). (3)
onde ∆ representa a diferença simétrica entre dois conjuntos; I(verdadeiro) = 1 e I(falso)
= 0.
Outras medidas dissecam o processo de avaliação do classificador em medidas
separadas para cada rótulo e ponderam esse valor sobre todos os rótulos. Esse tipo de
medida é chamada Baseada em Rótulos. Neste trabalho utilizamos a Micro averaged
F-Measure (Fb) definida pela Equação 4.
Fb(H,D) =
2
∑q
j=1 TPyj
2
∑q
j=1 TPyj +
∑q
j=1 FPyj +
∑q
j=1 FNyj
. (4)
onde TPyi , FPyi , TNyi e FNyi representam, respectivamente, o número de verdadei-
ros/falsos positivos/negativos para um rótulo yj do conjunto de rótulos L.
Todas essas medidas tem valores no intervalo [0..1]. Exceto Hamming Loss, para a
qual menores valores indicam melhor desempenho do classificador, os valores das outras
medidas devem ser maximizadas.
3. Algoritmo Nearest Neighbor
O kNN é um algoritmo de aprendizado lazy que busca identificar os k vizinhos mais simi-
lares ao exemplo E a ser classificado [Aha and Kibler 1991], para após decidir o rótulo
a ser atribuı́do a E levando em consideração os rótulos desses k exemplos mais simila-
res. Assim, além do valor de k e do conjunto de treinamento a ser utilizado, é necessário
escolher a medida que quantifica a similaridade entre o exemplo a ser classificado e os
exemplos de treinamento, bem como o procedimento para decidir o rótulo a ser atribuı́do
ao exemplo E [Batista and Silva 2009].
Diversas medidas de similaridade tem sido propostas. Entre elas, a distância Eu-
clideana ou a de Manhattan normalizadas são frequentemente utilizadas. Porém, elas
não são apropriadas para atributos categóricos. Esse problema pode ser tratado utili-
zando a métrica overlap para atributos categóricos e a distância normalizada para atributos
numéricos [Aggarwal et al. 2001, Wilson and Martinez 2000]. Essa abordagem, denomi-
nada Heterogeneous Euclidean-Overlap Metric (HEOM), é definida pela Equação 5.
HEOM(xaj,xbj) =
{
overlap(xaj,xbj), se Xj for categórico
range normalized diff(xaj,xbj), se Xj for numérico.
(5)
onde o valor da função overlap é 1 para atributos categóricos com valores diferentes e 0
caso contrário. A range normalized diff é a diferença entre os valores dos dois atributos
normalizada pelos valores mı́nimo e máximo desse atributo no conjunto de treinamento.
Após encontrados os k exemplos mais próximos, é necessário deci-
dir a rotulação do exemplo E. Considerando aprendizado monorrótulo, seja
{(E1,y1), (E2,y2), . . . , (Ek,yk)} o conjunto desses k exemplos. O rótulo y do exemplo
E é determinado pela Equação 6.
y = max
(y,yj)∈L
k∑
j=1
wjδ(y, yj). (6)
onde wi é o peso atribuı́do a cada um dos rótulos dos k exemplos mais próximos, δ(a,b) =
1 se a = b e 0 caso contrário. Várias funções de peso podem ser definidas. Por exemplo,
se wj = 1 ∀ j, então o rótulo mais frequente (moda) é atribuı́do a E. Outras funções de
peso consideram a distância dj , j = 1..k, de E ao exemplo mais próximo Ej . Algumas
dessas funções são generalizadas por meio da inclusão de um parâmetro q ∈ R, q ≥ 0.
Caso wj = d
−q
j para q > 0, então os rótulos dos exemplos mais próximos a E tem maior
peso. Os valores q = 1 e q = 2 são os mais frequentemente utilizados.
3.1. Nearest Neighbor para classificação multirrótulo
O método BRkNN [Spyromitros et al. 2008] tratado neste trabalho, utiliza a abordagem
BR para transformar o problema multirrótulo. Entretanto, o BRkNN executa |L| vezes
mais rápido que o método padrão baseado em kNN e BR, pois apenas uma busca pelos k
vizinhos mais próximos é realizada. Para classificar um exemplo, duas extensões desse
método, denominadas BRkNN-a e BRkNN-b foram também propostas nesse trabalho. Es-
sas extensões consideram o valor de confiança de cada rótulo, dado pela porcentagem dos
k vizinhos que contém esse rótulo, para decidir os rótulos que fazem parte do multirrótulo
predito. Desse modo, são capazes de tratar diretamente o problema multirrótulo.
No caso do BRkNN-a, o procedimento para seleção dos rótulos é idêntico ao
BRkNN. Caso o valor de confiança seja superior a 0,5, o rótulo correspondente é con-
siderado parte do multirrótulo predito. Para evitar a predição de multirrótulos vazios caso
nenhum rótulo for selecionado, o BRkNN-a considera o rótulo de maior confiança como
parte do multirrótulo final. Por outro lado, o BRkNN-b prevê antecipadamente o número
s de rótulos do multirrótulo predito como a média aritmética arredondada das quanti-
dades de rótulos dos k exemplos mais próximos. Assim, o multirrótulo predito não é
vazio, sendo constituı́do pelos [s] rótulos de maior confiança, onde [s] indica o inteiro
mais próximo de s.
3.1.1. Extensões propostas
Neste trabalho são propostas e implementadas três extensões ao algoritmo BRkNN, as
quais estão relacionadas com a medida de similaridade, função de peso e a estimativa do
número de rótulos que participam do multirrótulo predito, apresentadas a seguir.
1 - Medida de similaridade. Como mencionado, a medida de similaridade é um
parâmetro importante no algoritmo kNN. Ainda que a medida HEOM seja frequentemente
utilizada devido à sua simplicidade, ela não considera informações adicionais fornecidas
pelos atributos categóricos, as quais podem melhorar o poder de predição do classificador.
A extensão proposta consiste na substituição da medida HEOM pela me-
dida Heterogeneous Value Difference Metric (HVDM) [Wilson and Martinez 2000] no
BRkNN. A medida HVDM utiliza a medida Normalized Difference (ND) para cal-
cular a distância entre atributos numéricos, e a medida Value Difference Metric
(VDM) [Stanfill and Waltz 1986] para calcular a distância entre atributos categóricos. A
medida ND é definida pela Equação 7.
ND(xaj,xbj) =
|xaj − xbj|
4σXj
. (7)
onde xaj e xbj são os valores do atributo Xj de dois exemplos (Ea, Eb),a 6= b, e σXj
é o desvio padrão dos valores do atributo numérico Xj . O valor 4σXj é utilizado para
normalizar o valor de ND(xaj,xbj) no intervalo [0..1], pois aproximadamente 95% dos
valores em uma distribuição normal estão separados por até dois desvios padrão da média.
A medida VDM, definida pela Equação 8, calcula a distância entre valores ca-
tegóricos do atributo Xj .
V DM(xaj,xbj) =
|L|∑
i=1
|
Nxaj ,yi
Nxaj
−
Nxbj ,yi
Nxbj
|p. (8)
onde Nxaj é a quantidade de exemplos de treinamento com valor xaj; Nxaj ,yi é a quanti-
dade de exemplos de treinamento com valor xaj e rótulo yi; e p é uma constante de ajuste,
usualmente 1 ou 2. Assim, VDM considera que dois valores de um atributo categórico Xj
são similares se eles possuem classificações similares, i.e., correlações similares com um
rótulo.
Neste trabalho, para implementar a medida HVDM no contexto multirrótulo, foi
usada a transformação LP apenas para o cálculo das distâncias entre os atributos ca-
tegóricos dos exemplos de treinamento e o exemplo a ser classificado.
2 - Generalização da função de peso para rotulação de exemplos. A segunda extensão
proposta consiste na generalização da função de peso wj= d
−q
j , j = 1..k — Equação 6.
Como mencionado, os valores q = 1 e q = 2 são usualmente utilizados. Contudo, é
interessante fornecer a BRkNN mais flexibilidade para escolher outras funções de peso wj
com o objetivo de ponderar de diferentes maneiras as distâncias entre os vizinhos mais
próximos, o que pode levar a uma melhor predição do classificador. Na implementação
realizada neste trabalho o valor de q é definido pelo usuário.
3 - Estimativa do número de rótulos do multirrótulo predito. No BRkNN original as
distâncias dj , j = 1..k, são somente utilizadas para encontrar os k vizinhos mais próximos
de E. Porém, essa informação pode ser utilizada para apoiar a estimativa do número s
de rótulos do multirrótulo predito pelo algoritmo. Neste trabalho é proposta a estimativa
definida pela Equação 9.
s = b
∑k
j=1 d
−b
j · |Yi|∑k
j=1 d
−b
j
+ 0.5c. (9)
onde |Y1|, |Y2|, . . . , |Yk| são, respectivamente, o número de rótulos de cada um dos k
vizinhos e b ∈ R, b ≥ 0 um parâmetro dessa estimativa. Caso b > 0, esse parâmetro atua
como um fator de atenuação, dando maior importância ao número de rótulos dos exemplos
mais próximos ao exemplo a ser classificado. Na implementação realizada neste trabalho
o valor de b é definido pelo usuário.
Para ilustrar as duas últimas extensões, considere o exemplo na Figura 1, que
mostra os k = 7 vizinhos mais próximos do exemplo E, com L = {y1,y2,y3}.
Figura 1. Vizinhos mais próximos de um exemplo a ser rotulado.
Na Tabela 2 são mostradas as distâncias entre cada exemplo e o exemplo E a ser
classificado, bem como o valor da função de peso wj de cada um dos k=7 vizinhos mais
próximos, para q = 0,1 e 2.
Tabela 2. Valor da função de peso wj para q = 0, 1 e 2.
wj
(E,Y ) dj q = 0 q = 1 q = 2
(E1,{y3}) 0,12 1,00 8,33 69,44
(E2,{y2,y3}) 0,06 1,00 16,67 277,78
(E3,{y1,y3}) 0,06 1,00 16,67 277,78
(E4,{y1}) 0,03 1,00 33,33 1111,11
(E5,{y1,y2,y3}) 0,10 1,00 10,00 100,00
(E6,{y2,y3}) 0,30 1,00 3,33 11,11
(E7,{y3}) 0,26 1,00 3,85 14,79
Na Tabela 3 é mostrado o peso total de cada rótulo que participa do multirrótulo
e o multirrótulo que seria predito pelo BRkNN para os diferentes valores de q. Quanto ao
número de rótulos que devem participar do multirrótulo (Equação 9) seria 2 para b = 1 e
1 para b = 2.
As extensões propostas foram implementadas no framework Mu-
lan [Tsoumakas et al. 2011], que disponibiliza livremente algoritmos para aprendizado
multirrótulo, o qual é muito utilizado pela comunidade.
Tabela 3. Predição dos multirrótulos pelo BRkNN para q = 0, 1 e 2 e b = 1 e 2.
Y
y1 y2 y3 s = 2 para b = 1 s = 1 para b = 2
q = 0 3,00 3,00 6,00 {y2,y3} {y3}
q = 1 60,00 30,00 58,85 {y1,y3} {y1}
q = 2 1488,89 388,89 750,90 {y1,y3} {y1}
3.1.2. Trabalhos relacionados
Além do BRkNN, outros métodos baseados no kNN tem sido desenvolvidos
para aprendizado multirrótulo. No mesmo trabalho em que o BRkNN foi pro-
posto [Spyromitros et al. 2008] , os autores também propuseram e avaliaram a utilização
do método chamado LPkNN, o qual simplesmente transforma o problema multirrótulo em
um problema monorrótulo multiclasse, analogamente ao método LP, e aplica o algoritmo
kNN diretamente ao problema transformado.
O método MLkNN [Zhang and Zhou 2005] é outra adaptação do algoritmo kNN
para tratar dados multirrótulo. A principal diferença desse método para o BRkNN é a
utilização das probabilidades a priori e a posteriori, estimadas diretamente do conjunto
de treinamento, para a predição de novos exemplos. Uma generalização do método
MLkNN possibilita considerar a dependência de rótulos durante o aprendizado mul-
tirrótulo [Younes et al. 2011]. De modo similar a outros algoritmos baseados no kNN,
cada exemplo a ser predito nesse método tem seus k vizinhos identificados no conjunto
de treinamento. O princı́pio maximum a posteriori é utilizado em escopo global para atri-
buir um conjunto de rótulos para um exemplo a ser predito, de modo a oferecer suporte
para o tratamento da dependência de rótulos. Esse princı́pio possibilita, por exemplo,
que o número de rótulos distintos na vizinhança seja considerado durante o processo de
predição, diferentemente do que ocorre no MLkNN.
Os algoritmos MLkNN, LPkNN e BRkNN foram comparados utilizando algumas
bases de dados no trabalho de Spyromitros [Spyromitros et al. 2008]. Os autores utili-
zaram os frameworks Mulan e Weka para a execução dos experimentos, com parâmetros
considerados padrão para o algoritmo kNN monorrótulo, como distância euclidiana como
medida de similaridade entre exemplos. Os resultados apresentados, calculados a partir
da média obtida variando k com valores no intervalo [1..30], indicaram superioridade do
BRkNN e do LPkNN sobre o algoritmo MLkNN. Adicionalmente, BRkNN foi superior a
LPkNN em mais conjuntos de dados, o que reforça a motivação para incluir no BRkNN as
extensões propostas neste trabalho.
4. Experimentos
A fim de ilustrar as modificações propostas, foram utilizados quatro conjuntos de da-
dos, dois com atributos categóricos e dois com atributos numéricos, considerando di-
ferentes funções de peso (Equação 6), bem como diferentes estimativas para calcular s
(Equação 9). O BRkNN estendido foi executado variando o parâmetro q da função de
peso com valores inteiros no intervalo [0..10] e o parâmetro b da estimativa de s com va-
lores inteiros no intervalo [0..3]. O número k de vizinhos mais próximos variou entre 3,
5, 7, 9, 11 e 13. Foram também avaliadas as medidas de similaridade HEOM e HVDM.
Nesse caso, foi definido p = 2 para a medida HVDM (Equação 8).
Os experimentos foram realizados utilizando o framework Mulan. Foi utilizada a
estratégia de validação cruzada de 10 folds, com folds pareados. Os classificadores foram
avaliados utilizando as quatro medidas de avaliação definidas na Seção 2. Os gráficos
foram gerados por meio do framework R1.
4.1. Conjuntos de dados utilizados
Os quatro conjuntos de dados, descritos na Tabela 4, foram obtidos do repositório do Mu-
lan2. Para cada conjunto de dados, nessa tabela é mostrado: o domı́nio (A); o número de
exemplos (N ), de atributos (M ) e de rótulos (|L|); a Cardinalidade de Rótulo (CR), dada
pelo número médio de rótulos associados com cada exemplo – Equação 10; a Densidade
de Rótulo (DR), ou cardinalidade normalizada – Equação 11; e o número de Combinações
Distintas (CD) de rótulos.
CR(D) =
1
|D|
|D|∑
i=1
|Yi| (10) DR(D) =
1
|D|
|D|∑
i=1
|Yi|
|L|
. (11)
Tabela 4. Descrição dos conjuntos de dados multirrótulo utilizados.
Conjunto de dados A N M |L| CR DR CD
1-emotions música 593 72 6 1,87 0.31 27
2-scene imagem 2407 294 6 1,07 0.18 15
3-genbase biologia 662 1186 27 1,25 0,05 32
4-medical texto 978 1449 45 1,25 0,03 94
Os conjuntos de dados emotions e scene são descritos por atributos numéricos,
enquanto os conjuntos genbase e medical são descritos por atributos categóricos.
4.2. Resultados e discussão
Os resultados dos experimentos realizados variando os valores dos parâmetros k, q e b
foram tabulados e encontram-se disponı́veis para consulta3. Devido à falta de espaço, a
seguir são mostrados graficamente os resultados de um desses experimentos utilizando os
seguintes parâmetros: k = 7, q = 0, b = 0 e p = 2.
Na Figura 2 é apresentado, para as quatro medidas de avaliação consideradas, o de-
sempenho do classificador BRkNN usando a medida de similaridade HEOM e a HVDM,
implementada neste trabalho, em cada conjunto de dados. Como mencionado, a medida
Hamming Loss é a única que deve ser minimizada na classificação.
Pode ser observado que o único conjunto de dados para o qual não houve melho-
ria nas medidas de avaliação dos classificadores utilizando HEOM e HVDM é o conjunto
genbase. Para as quatro medidas de avaliação consideradas, os valores estiveram den-
tro do desvio-padrão. Entretanto, para esse conjunto de dados, os valores das medidas
utilizando HEOMestão perto do ótimo. Assim, não há espaço para serem melhorados.
1http://www.r-project.org
2http://mulan.sourceforge.net/datasets.html
3http://www.labic.icmc.usp.br/pub/mcmonard/ResultadosExperimentaisENIA2012.
pdf
Hamming Loss
em
ot
io
ns
H
E
O
M
em
ot
io
ns
H
V
D
M
sc
en
e
H
E
O
M
sc
en
e
H
V
D
M
ge
nb
as
e
H
E
O
M
ge
nb
as
e
H
V
D
M
m
ed
ic
al
H
E
O
M
m
ed
ic
al
H
V
D
M
0.0
0.2
0.4
0.6
0.8
1.0
Subset Accuracy
em
ot
io
ns
H
E
O
M
em
ot
io
ns
H
V
D
M
sc
en
e
H
E
O
M
sc
en
e
H
V
D
M
ge
nb
as
e
H
E
O
M
ge
nb
as
e
H
V
D
M
m
ed
ic
al
H
E
O
M
m
ed
ic
al
H
V
D
M
0.0
0.2
0.4
0.6
0.8
1.0
Accuracy
em
ot
io
ns
H
E
O
M
em
ot
io
ns
H
V
D
M
sc
en
e
H
E
O
M
sc
en
e
H
V
D
M
ge
nb
as
e
H
E
O
M
ge
nb
as
e
H
V
D
M
m
ed
ic
al
H
E
O
M
m
ed
ic
al
H
V
D
M
0.0
0.2
0.4
0.6
0.8
1.0
Micro averaged F Measure
em
ot
io
ns
H
E
O
M
em
ot
io
ns
H
V
D
M
sc
en
e
H
E
O
M
sc
en
e
H
V
D
M
ge
nb
as
e
H
E
O
M
ge
nb
as
e
H
V
D
M
m
ed
ic
al
H
E
O
M
m
ed
ic
al
H
V
D
M
0.0
0.2
0.4
0.6
0.8
1.0
Figura 2. Resultados usando BRkNN (k = 7, q = 0 e b = 0) com as medidas de
similaridade HEOM e HVDM.
Contudo, nos demais conjuntos de dados, as medidas de avaliação são melhores
para os classificadores gerados utilizando HVDM, com destaque para o conjunto de dados
medical, o qual é descrito por atributos categóricos.
Como pode ser observado na Figura 2, o conjunto de dados emotions obteve a
maior redução do valor de Hamming Loss, seguido de scene e medical. Quanto às medidas
Subset Accuracy, Micro Averaged F-measure e Accuracy, o conjunto de dados medical
obteve o maior incremento nos valores, seguido de emotions e scene. Esses resultados
mostram a superioridade da medida de similaridade HVDM.
Para ilustrara o efeito da variação dos parâmetros q na função de peso e b na esti-
mativa no número de rótulos no multirrótulo predito utilizando a medida de similaridade
HVDM, foram gerados mapas de calor. Um mapa de calor colore cada célula (i,j) con-
forme um determinado valor relacionado aos ı́ndices i e j.
Neste trabalho, foram utilizados os ı́ndices correspondem a valores dos parâmetros
q no intervalo [0..10] e b no intervalo [0..3]. Os valores representados nas células corres-
pondem à medida de avaliação Micro Averaged F-Measure (Fb). Quanto mais alto o valor
em uma célula, mais próximo de vermelho é a cor nessa célula. Devido a falta de espaço,
na Figura 3 é mostrado o mapa de calor considerando k = 7 para o conjunto de dados
medical. Tabelas e mapas de calor das outras medidas e dos outros conjuntos de dados
obtidos variando k, q e b também estão disponı́veis para consulta3.
0 1 2 3
0
2
4
6
8
10
Micro averaged F−Measure com K=7 [q/b]
0.72
0.73
0.74
0.75
0.76
Figura 3. Mapa de calor usando BRkNN estendido variando q e b e a medida
HVDM para medical.
Valores pouco usuais para o parâmetro q, i.e., diferentes de 0, 1 ou 2, levaram
aos melhores resultados para a medida Fb. Entretanto, vale observar que a diferença nos
resultados obtidos variando os parâmetros q e b foi geralmente pequena. Por exemplo,
para os resultados mostrados na Figura 3, essa diferença é menor ou igual a 0,05, a qual
não supera o desvio padrão.
5. Conclusão
Neste trabalho foram propostas três extensões para o algoritmo de classificação mul-
tirrótulo BRkNN. Dentre essas extensões, a que mostrou maior impacto foi a medida
de similaridade Heterogeneous Value Difference Metric na busca pelos vizinhos mais
próximos em dados categóricos e numéricos.
Trabalhos futuros incluem a avaliação das extensões propostas utilizando mais
conjuntos de dados benchmark, bem como conjuntos de dados artificiais, de modo a for-
talecer a avaliação experimental.
Agradecimentos
À FAPESP pelo apoio recebido para a realização deste trabalho. A Victor Augusto Mo-
raes Carvalho pelo auxı́lio no desenvolvimento do trabalho.
Referências
Aggarwal, C. C., Hinneburg, A., and Keim, D. A. (2001). On the surprising behavior of
distance metrics in high dimensional space. In International Conference on Database
Theory, páginas 420–434.
Aha, D. and Kibler, D. (1991). Instance-based learning algorithms. Machine Learning,
6:37–66.
Batista, G. E. A. P. A. and Silva, D. F. (2009). How k-nearest neighbor parameters affect
its performance. In X Argentine Symposium on Artificial Intelligence, páginas 95–106.
Publicado em CD-ROM.
Carvalho, A. C. P. L. F. D. and Freitas, A. A. (2009). A tutorial on multi-label classi-
fication techniques, volume 5 of Studies in Computational Intelligence 205, páginas
177–195. Springer-Verlag.
Esuli, A. and Sebastiani, F. (2009). Active learning strategies for multi-label text classifi-
cation. In European Conference on IR Research on Advances in Information Retrieval,
páginas 102–113.
Liu, X., Shi, Z., Li, Z., Wang, X., and Shi, Z. (2010). Sorted label classifier chains for
learning images with multi-label. In International conference on Multimedia, páginas
951–954.
Park, H., Park, D., and Kwon, H.-C. (2011). Two-phase prediction of protein functions
from biological literature based on gini-index. In International Conference on Ubiqui-
tous Information Management and Communication, páginas 1–10.
Spyromitros, E., Tsoumakas, G., and Vlahavas, I. (2008). An empirical study of lazy
multilabel classification algorithms. In Hellenic conference on Artificial Intelligence,
páginas 401–406, Berlin, Heidelberg.
Stanfill, C. and Waltz, D. (1986). Toward memory-based reasoning. Communications of
the ACM, 29(12):1213–1228.
Tsoumakas, G., Katakis, I., and Vlahavas, I. (2009). Mining multi-label data. Data
Mining and Knowledge Discovery Handbook, páginas 1–19.
Tsoumakas, G., Spyromitros, E., Vilcek, J., and Vlahavas, I. (2011). Mulan: A java library
for multi-label learning. Journal of Machine Learning Research, 12:2411–2414.
Wilson, D. R. and Martinez, T. R. (2000). Reduction Techniques for Exemplar-Based
Learning Algorithms. Machine learning, 38(3):257–286.
Younes, Z., Abdallah, F., Denoeux, T., and Snoussi, H. (2011). A dependent multilabel
classification method derived from the k-nearest neighbor rule. EURASIP Journal on
Advances in Signal Processing, 2011:1–14.
Zhang, M.-L. and Zhou, Z.-H. (2005). A k-nearest neighbor based algorithm for multi-
label classification. IEEE International Conference on Granular Computing, 2:718–
721.