ads:
Idilio Drago
Estudo comparativo de algoritmos de classificação
em bases de dados com atributos temporais
Vitória - ES, Brasil
27 de setembro de 2007
ads:
Livros Grátis
http://www.livrosgratis.com.br
Milhares de livros grátis para download.
Idilio Drago
Estudo comparativo de algoritmos de classificação
em bases de dados com atributos temporais
Dissertação apresentada ao Programa de Pós-
Graduação em Informática da Universidade Fe-
deral do Espírito Santo para obtenção do título
de Mestre em Informática.
Orientador:
Flávio Miguel Varejão
PROGRAMA DE PÓS-GRADUAÇÃO EM INFORMÁTICA
DEPARTAMENTO DE INFORMÁTICA
CENTRO TECNOLÓGICO
UNIVERSIDADE FEDERAL DO ESPÍRITO SANTO
Vitória - ES, Brasil
27 de setembro de 2007
ads:
Dados Internacionais de Catalogação-na-publicação (CIP)
(Biblioteca Central da Universidade Federal do Espírito Santo, ES, Brasil)
Drago, Idilio, 1980-
D759e Estudo comparativo de algoritmos de classificação em bases de dados
com atributos temporais / Idilio Drago. – 2007.
79 f. : il.
Orientador: Flávio Miguel Varejão.
Dissertação (mestrado) – Universidade Federal do Espírito Santo,
Centro Tecnológico.
1. Reconhecimento de padrões. 2. Análise de séries temporais
-Processamento de dados. 3. Árvores de decisão. I. Varejão, Flávio
Miguel. II. Universidade Federal do Espírito Santo. Centro Tecnológico.
III. Título.
CDU: 004
Dissertação de Mestrado sob o título “Estudo comparativo de algoritmos de classificação
em bases de dados com atributos temporais”, defendida por Idilio Drago e aprovada em 27 de
setembro de 2007, em Vitória, Estado do Espírito Santo, pela banca examinadora constituída
pelos doutores:
Prof. Dr. Flávio Miguel Varejão
Orientador
Prof. Ph.D. Thomas Walter Rauber
Examinador Interno
Prof. Dr. Alexandre Plastino
Examinador Externo
Sumário
Lista de Figuras
Lista de Tabelas
Resumo
Abstract
1 Introdução p.11
2 Vizinho mais próximo e medidas de similaridade p.16
2.1 O algoritmo do vizinho mais próximo . . . . . . . . . . . . . . . . . . . . . p.16
2.2 Medidas de similaridade . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 18
2.2.1 Distância Euclidiana . . . . . . . . . . . . . . . . . . . . . . . . . . p. 18
2.2.2 Correlação linear . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 20
2.2.3 Distância de Hamming . . . . . . . . . . . . . . . . . . . . . . . . . p.21
2.2.4 Distância de edição . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 22
2.2.5 DTW - Dynamic time warping . . . . . . . . . . . . . . . . . . . . . p.26
2.2.6 Métricas baseadas em transformações . . . . . . . . . . . . . . . . . p. 29
2.3 Combinando várias métricas em um mesmo classificador . . . . . . . . . . . p.32
3 Árvores de decisão com características temporais p.35
3.1 Árvores de decisão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 35
3.2 Construção de árvores de decisão . . . . . . . . . . . . . . . . . . . . . . . . p.37
3.2.1 Tratamento de atributos temporais . . . . . . . . . . . . . . . . . . . p. 38
3.3 Poda e combinação de árvores de decisão . . . . . . . . . . . . . . . . . . . p. 41
4 Avaliação experimental p.44
4.1 Ajuste de parâmetros e estimativa do erro de classificação . . . . . . . . . . . p. 44
4.2 Comparação de algoritmos de classificação . . . . . . . . . . . . . . . . . . p. 46
4.2.1 Comparação de dois classificadores em um mesmo domínio . . . . . p. 47
4.2.2 Comparação de vários classificadores em múltiplos domínios . . . . . p. 48
4.3 Avaliação de métricas para determinação do vizinho mais próximo . . . . . . p. 52
4.4 Árvore aleatória com adaptação para dados temporais . . . . . . . . . . . . . p. 56
4.5 Árvore de decisão convencional com adaptação para dados temporais . . . . p.59
4.6 Discussão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p.62
4.7 Indicação de consumidores de energia elétrica para inspeção . . . . . . . . . p. 64
5 Conclusões p.70
5.1 Trabalhos futuros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 71
Referências Bibliográficas p.73
Apêndice A -- Alguns experimentos adicionais p.77
Lista de Figuras
1.1 Um problema de classificação de séries temporais. Existem 3 classes, que se
distinguem pelo formato da série. O quarto exemplo tem classe desconhecida. p.13
2.1 Cálculo da distância Euclidiana. Uma pequena variação de fase pode ocasio-
nar diferença significativa na medida. . . . . . . . . . . . . . . . . . . . . . p. 19
2.2 Duas seqüências com distorções locais no eixo do tempo. Por volta do ins-
tante t = 20 há uma inversão no atraso entre as séries. . . . . . . . . . . . . . p.25
2.3 Uma representação discreta das séries e o alinhamento produzido. . . . . . . p. 25
2.4 Seqüência de geração dos pesos na heurística criada para treinar o algoritmo
NN com várias métricas. . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 34
Lista de Tabelas
2.1 Limites para divisãoda Distribuição Normal Padrão em cinco intervaloseqüi-
prováveis. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p.22
2.2 Computando DTW com janela de ajuste r = 2. Neste caso, o caminho na
tabela de cálculo não pode se afastar mais de 2 unidades da diagonal. . . . . . p.28
4.1 Taxa de erro média (percentual) do algoritmo do vizinho mais próximo com
métricas diversas. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 52
4.2 Valores-p e média dos postos da comparação de métricas contra a distância
Euclidiana. Valores ainda sem o ajuste requerido pela multiplicidade. . . . . p.54
4.3 Vizinho mais próximo com combinação de métricas e melhor resultado indi-
vidual. Taxa de erro média (percentual). . . . . . . . . . . . . . . . . . . . . p. 55
4.4 Taxa de erro média (percentual) da árvore aleatória com métricas temporais
em diversos problemas de classificação. O melhor desempenho em cada pro-
blema é escrito em negrito. . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 57
4.5 Valores-p e média dos postos da comparação entre a adaptação com métricas
e a versão original da árvore extremamente aleatória. Valores ainda sem o
ajuste requerido pela multiplicidade. . . . . . . . . . . . . . . . . . . . . . . p.58
4.6 Combinação de métricas e melhor resultado individual da árvore de decisão
aleatória adaptada. Taxa de erro média (percentual). . . . . . . . . . . . . . . p.58
4.7 Taxa de erro média (percentual) da árvore de decisão (podada) com métricas
temporais. O melhor desempenho em cada problema é escrito em negrito. . . p.60
4.8 Valores-p e média dos postos da comparação da árvore com adaptação tem-
poral contra a versão não adaptada da árvore extremamente aleatória. . . . . . p. 60
4.9 Taxa de erro média (percentual) da combinação por bagging de árvores de
decisão (sem poda) com métricas temporais. O melhor desempenho em cada
problema é escrito em negrito. . . . . . . . . . . . . . . . . . . . . . . . . . p.61
4.10 Valores-p e média dos postos da comparação de um comitê de árvores com
adaptação temporal (combinadas por bagging) contra a versão não adaptada
da árvore extremamente aleatória. . . . . . . . . . . . . . . . . . . . . . . . p.62
4.11 Resultado da melhor métrica em cada uma das quatro formas de classificação
avaliadas. Melhor resultado de cada problema em negrito. . . . . . . . . . . . p.63
4.12 Taxa de erro média (percentual) da árvore aleatória e do algoritmo do vizinho
mais próximo avaliados com os dados normalizados. . . . . . . . . . . . . . p.67
4.13 Taxa de erro média (percentual) da árvore aleatória e do algoritmo do vizinho
mais próximo avaliados com os dados não normalizados. . . . . . . . . . . . p. 67
4.14 F-measure média (percentual) da árvore aleatória e do algoritmo do vizinho
mais próximo avaliados com os dados normalizados. . . . . . . . . . . . . . p.67
4.15 F-measure média (percentual) da árvore aleatória e do algoritmo do vizinho
mais próximo avaliados com os dados não normalizados. . . . . . . . . . . . p. 68
4.16 Matriz de confusão do algoritmo do vizinho mais próximo usando a distância
Manhattan. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p.69
4.17 Matriz de confusão do classificador bayesiano com características extraídas. . p. 69
A.1 Taxa de erro do algoritmo do vizinho mais próximo com métricas de simila-
ridade. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p.77
A.2 Taxa de erro da árvore aleatória com métricas temporais. . . . . . . . . . . . p.79
A.3 Taxa de erro da combinação por bagging de árvores de decisão (sem poda). . p.79
Resumo
Uma série temporalé um conjunto de dados que possuemalguma relação variávelno tempo.
O tipo mais simples de série temporal é representado por uma única variável amostrada em ins-
tantes regulares. Problemas de classificação supervisionada são definidos como a tarefa de
associar um rótulo a exemplos desconhecidos, a partir de informações obtidas de casos com
rótulos conhecidos. Quando os casos a classificar são compostos por características tempo-
rais, métodos especiais devem ser usados em algumas etapas da construção do classificador.
Extração de características estáticas que descrevem as temporais e adaptação de algoritmos de
classificação para manipulação direta deste tipo de atributo são as duas principais soluções ado-
tadas neste tipo de problema. Há duas formas usuais de adaptar algoritmos de classificação
para dados temporais: desenvolvendo modelos matemáticos para descrever as séries associadas
a cada classe; comparando diretamente as séries entre si ou as séries em relação a casos conside-
rados padrões. Este trabalho trata apenas de métodos de classificação baseados em comparação
de séries temporais. A questão central, neste caso, é definir medidas de semelhança entre as
séries. A partir de dois trabalhos, que enumeram um conjunto de métricas supostamente mais
apropriadas para comparação de séries temporais, versões adaptadas do algoritmo do vizinho
mais próximo e do algoritmo de treinamento de árvores de decisão são apresentadas. Sabendo
que, em problemas com dados não temporais, a combinação de várias árvores de decisão gera
classificadores mais precisos, é proposta uma nova versão, especial para dados temporais, do
método de treinamento de comitês de árvores extremamente aleatórias. Além disso, para ve-
rificar a suposição de que várias medidas de similaridade diferentes produzem, em conjunto,
melhores classificadores, um método de combinação de medidas por ponderação é proposto.
Uma avaliação experimental é realizada em um conjunto de problemas reais para verificar a ex-
pectativa de melhoria da taxa de acerto dos classificadores adaptados, em relação aos mesmos
algoritmos sem adaptação. No caso do algoritmo do vizinho mais próximo e da nova adaptação
da árvore extremamente aleatória, os resultados experimentais mostram uma considerável me-
lhoria em relação às versões originais. Os resultados em um dos problemas reais - de seleção
de consumidores de energia elétrica para inspeção, são descritos em mais detalhes por se tratar
de um problema ainda pouco explorado.
Abstract
A time series is a sequence of data points taken at more or less regular intervals. Supervi-
sed classification is defined as the task of assigning a label to cases, based on the information
learned from examples with known labels. Special algorithms are needed when the examples
are represented by temporal features. The two main approaches to this kind of classification
problem are the extraction of static (non-temporal) features from the time series and the de-
velopment of special learning algorithms to deal with temporal features. In general, there are
two ways for adapting learning algorithms to handle temporal data: developing a mathematical
model to represent the time series for each class; or comparing directly the series to each other
or to template cases. This work address only the classification based on direct comparisons of
time series features. We focus on using similarity measures between series. Based on some me-
trics, suitable for temporal data, we adapted the nearest neighbor classifier and the building step
of the decision tree algorithm. In order to improve the accuracy of the decision tree approach,
we evaluated the bagging meta-algorithm with the temporal tree and proposed a new training
algorithm for building a committee of extremely randomized trees. Furthermore, we verified
the assumption that various similarity metrics together may produce a more accurate classifier
by proposing a new heuristic, based on weights, to combine the measures in the nearest neigh-
bor decision rule and a test with several metrics to the decision tree approach. We carried out a
set of experiments on real-world problems to verify the hypothesis that the new algorithms are
better than the classical ones. The results showed a considerable improvement over the original
versions, when evaluating the nearest neighbor algorithm and the new extremely randomized
tree. We also described the results obtained in a new temporal classification problem - the fraud
detection on power distribution services.
11
1 Introdução
Uma série temporal pode ser definida como um conjunto de dados que têm entre si alguma
relação variável no tempo. Pode-se, portanto, chamar de série temporal quaisquer conjuntos
de dados reais amostrados no tempo. Por exemplo, o número de acidentes de trânsito por
mês, o número de batimentos cardíacos por minuto de um paciente durante uma internação e o
consumo mensal de energia elétrica de um cliente durante o ano são eventos representáveis na
forma de séries temporais.
Roddick & Spiliopoulou (2002) organizam as informações encontradas em situações reais
em quatro categorias, de acordo com o tipo de relação de temporalidade existente:
• Estáticas: nenhum contexto temporal é incluído e nenhum pode ser inferido.
• Seqüência: lista ordenada de eventos, sem marcação do tempo. Nesta categoria incluem-
se as coleções de eventos ordenados, mas sem marcos de tempo. Normalmente, pode-se
obter, a partir deste tipo de dados, somente relacionamentos do tipo “aconteceu antes”,
“aconteceu depois” etc.
• Com marcos de tempo (timestamped): representa uma seqüência programada de even-
tos, tomados em intervalos mais ou menos regulares, com marcação do tempo. Como
exemplos, pode-se citar: censos, dados de satélites meteorológicos, dados de vendas com
marcos de tempo e atividades da Internet.
• Inteiramente temporal: cada registro possui uma relação temporal variável, com marcos
de tempo e, possivelmente, mais de uma dimensão (informação multidimensional). Como
exemplos, pode-se citar os dados de medições de equipamentos (ou processos) realizadas
por vários sensores simultaneamente.
Normalmente, define-se classificação como um caso especial do aprendizado automático
em que se possui um conjunto de informações (atributos)sobre vários exemplosde algum objeto
do mundo real, e cada exemplo conhecido está associado a uma etiqueta (classe discreta). A
12
partir destes exemplos conhecidos, deseja-se construir um sistema que seja capaz de etiquetar
(atribuir a classe) a exemplos em que apenas os atributos são conhecidos.
A construção de um sistema de classificação é, geralmente, subdividida em algumas etapas:
obtenção dos dados, preparação dos dados (pré-processamento), seleção/extração de atributos,
escolha do algoritmo de classificação, treinamento do classificador e avaliação do classificador
treinado. Diversos algoritmos e técnicas existem em cada uma destas etapas, a maior parte des-
tinados a problemas com atributos estáticos. Theodoridis & Koutroumbas (2006) apresentam
alguns métodos aplicáveis às primeiras etapas, principalmente para seleção/extração de atribu-
tos (por exemplo, algumas heurísticas de seleção de características e o método de análise de
componentes principais para extração de novas características a partir das inicialmente existen-
tes). Sobre as demais etapas, Duda, Hart & Stork (2001) são a principal referência, por apre-
sentar boa parte dos algoritmos de classificação mais relevantes, dentre os quais, os modelos
baseados na teoria de Bayes, o algoritmo do vizinho mais próximo, o perceptron multicamadas
e as árvores de decisão.
Quando existem atributos não estáticos dentre os que representam os exemplos que se de-
seja classificar, técnicas alternativas devem ser usadas em algumas das etapas da construção
do classificador. As principais alterações acontecem nas fases de preparação dos dados, se-
leção/extração de atributos e escolha do algoritmo de classificação. O mais comum é criar
procedimentos nas etapas de preparação dos dados e seleção/extração de atributos para alterar o
formato das informações temporais (por exemplo, para converter, por interpolação, dados com
marcos de tempo para seqüências igualmente espaçadas) ou extrair características estáticas a
partir das temporais e, então, descartar os dados originais e utilizar somente as novas carac-
terísticas com os algoritmos “convencionais” de classificação. Existem, porém, algoritmos de
classificação que podem lidar diretamente com os dados temporais.
Embora seja comum encontrar problemas reais em que os atributos sejam dos três tipos
não estáticos, este trabalho aborda apenas problemas com atributos do tipo seqüência. A partir
deste ponto, os termos série temporal e atributo temporal estarão sempre se referindo a atribu-
tos desse tipo. Os problemas estudados serão sempre de classificação de séries temporais uni-
dimensionais, ou seja, toda a informação disponível para classificar resume-se a uma seqüência
de valores de uma mesma variável, tomados em intervalo constante de tempo. A tarefa será
etiquetar séries temporais (completas) com classe desconhecida, a partir de séries com classe
conhecida. A Figura 1.1 ilustra algumas séries temporais de um problema de classificação deste
tipo. Neste problema, há três classes de séries que se distinguem pela forma - os três primeiros
quadros da figura. O quarto quadro mostra uma nova série, cuja classe é desconhecida.
13
Exemplo 1 - classe A
Exemplo 2 - classe B
Exemplo 3 - classe C
Exemplo 4 - classe desconhecida
Figura 1.1: Um problema de classificação de séries temporais. Existem 3 classes, que se distin-
guem pelo formato da série. O quarto exemplo tem classe desconhecida.
Em problemas de classificação de séries temporais, quando há conhecimento específico
sobre o processo gerador dos dados a classificar que permita que características estáticas espe-
ciais sejam criadas para formação da base de aprendizado, a melhor opção parece ser usar este
conhecimento para extrair informações não temporais das séries e treinar classificadores “con-
vencionais”. Por exemplo, os padrões que definem as classes na Figura 1.1 são bastante nítidos.
Embora existam ruídos deformando e distorcendo as séries é possível modelar características
com forte poder de discriminação para esse problema - para distinguir entre a segunda e a ter-
ceira classe bastaria uma única característica que indicasse a tendência da série, por exemplo.
Todavia, nem sempre há esse tipo de informação sobre o processo gerador dos dados temporais
e, em muitos casos, somente os exemplos com os rótulos das classes estão disponíveis.
Em problemas com padrões fortemente relacionados à forma, como no caso da Figura 1.1,
é comum recorrer a um conjunto de extratores de características de propósito geral, para criar
a maior quantidade possível de informação sobre as séries, e posteriormente selecionar neste
conjunto as características mais relevantes para discernir as classes do problema. Nesta linha,
14
Mörchen (2003) utiliza características estáticas obtidas por meio das transformadas de Fourier
e de Wavelets. Nanopoulos, Alcock & Manolopoulos (2001) extraem estatísticas descritivas das
séries para compor a base de treinamento em problemas temporais. Ambos relatam resultados
melhores do que a solução, aparentemente ingênua, de treinar classificadores “convencionais”
fazendo com que cada ponto da variável no tempo seja uma característica não temporal.
Outros autores descrevem formas de classificação de séries temporais que, ao invés de ex-
traírem informações estáticas das séries, manipulam diretamente estes dados durante a constru-
ção do classificador. Nesta abordagem, duas linhas principais são geralmente seguidas: ou se
tenta gerar modelos matemáticos para descrever as séries associadas a cada classe do problema,
ou se tenta classificar através da comparação dos exemplos entre si ou através da comparação
dos exemplos a casos considerados padrões (template matching). Pode-se citar Murphy (2002),
Ge & Smyth (2000) e Abou-Moustafa, Cheriet & Suen (2004) como exemplos de trabalhos que
seguem a primeira linha.
Neste trabalho serão avaliadas somente formas de classificação baseadas na comparação
direta entre séries temporais. Nesta forma de classificação, a questão central é decidir quando
duas séries são consideradas semelhantes. Antunes & Oliveira (2001) e Savary (2002) listam
diversas maneiras de calcular a similaridade entre seqüências, que podem ser o ponto de partida
para a adaptação do algoritmo do vizinho mais próximo e para extensão do algoritmo de treina-
mento de árvores de decisão para manipulação de atributos temporais. O restante deste trabalho
tratará somente das adaptações desses dois algoritmos com algumas das métricas listadas por
esses autores.
São três as motivações principais para estudar estas adaptações:
• Antunes & Oliveira (2001) e Savary (2002) listam diversas medidas de comparação de
séries temporais e sugerem a utilização delas como fundamento do algoritmo do vizinho
mais próximo. Ambos não fazem, porém, nenhuma avaliação da qualidade do classifica-
dor produzido com estas medidas em problemas reais.
• Yamada et al. (2003) mostram uma extensão do algoritmo de treinamento de árvores de
decisão que utiliza métricas de similaridade e comparação direta entre séries temporais.
Não há, entretanto, uma avaliação da qualidade desta adaptação em relação a do algoritmo
do vizinho mais próximo.
• O problema real de indicação de consumidores de energia elétrica para inspeção, apresen-
tado na seção 4.7, é um problema de classificação de séries temporais. Deseja-se verificar
se estes algoritmos são apropriados a ele. Neste caso, há também resultados obtidos por
15
classificadores “convencionais” com características estáticas triviais, que servirão como
base de comparação.
O Capítulo 2 apresenta resumidamente o método de classificação do vizinho mais próximo
e as medidas descritas em Antunes & Oliveira (2001) e Savary (2002). Além disso, parece ser
correto suporque métricas distintas possam produzir informações diferentes sobreas seqüências
e, eventualmente, gerar classificadores mais precisos se forem combinadas. Uma forma de
combinação de várias medidas através de ponderações é proposta neste capítulo.
No Capítulo 3 é apresentado um resumo do algoritmo de treinamento de árvores de deci-
são e a adaptação de Yamada et al. (2003) para manipulação de características temporais. Em
problemas com atributos não temporais, existem diversos trabalhos que mostram métodos que
combinam várias árvores de decisão para criação de classificadores mais precisos. O Capítulo 3
apresenta também o método de construção de comitês de árvores extremamente aleatórias, pro-
posto por Geurts, Ernst & Wehenkel (2006) para atributos não temporais. Baseado no trabalho
de Yamada et al. (2003), uma adaptação deste método é proposta para manipulação de atributos
temporais.
O Capítulo 4 faz uma avaliação experimental dos métodos de classificação apresentados e
propostos nos capítulos anteriores. Os principais objetivos desta avaliação são:
• Verificar a expectativa de melhoria da taxa de acerto do classificador com métricas de
similaridade especiais, dado um problemaqualquer de classificação com dados temporais,
considerando como base da comparação o vizinho mais próximo “convencional”, que
calcula a distância euclidiana entre os exemplos.
• Comparar o desempenho do algoritmo de treinamento de árvores de decisão e de treina-
mento de árvores extremamente aleatórias para atributos temporais, em relação ao desem-
penho das versões “convencionais” destes algoritmos e também em relação à adaptação
do vizinho mais próximo.
• Verificar se a combinação de diversas métricas de similaridade melhora a precisão dos
classificadores.
• Avaliar estes métodos de classificação usando os dados do problema real de indicação de
consumidores de energia elétrica para inspeção.
O Capítulo 5 resume os principais resultados obtidos e indica as possíveis continuações
deste trabalho.
16
2 Vizinho mais próximo e medidas de
similaridade
No contexto de classificação em que existam séries temporais como características, a abor-
dagem mais comum, ao lado da extração de novascaracterísticas estáticas, é adaptar o algoritmo
não paramétrico do vizinho mais próximo para manipulação dos dados temporais. Tal adapta-
ção consiste em selecionar uma medida de similaridade mais adequada ao problema em questão,
em substituição à distância Euclidiana.
Neste capítulo, o algoritmo é apresentado resumidamente. São apresentadas também al-
gumas medidas de similaridade utilizadas na comparação de séries temporais. As principais
fraquezas do algoritmo são brevemente discutidas e as conseqüências da alteração da medida
de comparação em relação a estas fraquezas são analisadas.
2.1 O algoritmo do vizinho mais próximo
O princípio do desenvolvimento da classificação usando a regra de decisão do vizinho mais
próximo é, normalmente, atribuído a Cover & Hart (1967). Neste trabalho, os autores iniciam
a apresentação do algoritmo listando os dois extremos distintos do problema de classificação:
ou conhece-se a distribuição conjunta dos dados e das classes do problema, caso em que uma
análise de Bayes leva à regra ótima de decisão e ao mínimo erro teórico, ou não se conhece
nada sobre a distribuição além daquilo que é possível extrair a partir de exemplos conhecidos
do problema em questão.
Enquanto no primeiro caso a regra de decisão é fortemente justificada, no segundo, ao
contrário, não se tem convicção sobre as regras criadas e a qualidade da classificação estará
diretamente relacionada à qualidade dos dados disponíveis.
Supondo que os exemplos conhecidos são independentes e identicamente distribuídos em
relação à distribuição original dos dados, uma heurística normalmente aceita para classificação
de casos desconhecidos é considerar que as observações suficientemente próximas (de acordo
17
com alguma métrica preestabelecida) pertencerão à mesma classe.
Tal heurística, também chamada de NN (Nearest Neighbor), é formalizada por Cover &
Hart (1967) da seguinte maneira: seja o conjunto de pares S = {(x
1
,
θ
1
),...,(x
n
,
θ
n
)}, repre-
sentando as instâncias conhecidas do problema. Em cada par, x
i
= [x
i1
,x
i2
,. . .,x
im
]
t
é o vetor de
atributos e
θ
i
é a classe do exemplo i. Para os problemas de interesse neste trabalho, os valores
de
θ
i
são todos pertencentes a um conjunto discreto {c
1
,c
2
,...,c
l
}. Deseja-se determinar o valor
de
θ
quando um novo par (x,
θ
) for apresentado ao sistema de classificação. Neste novo par,
apenas os valores de x puderam ser observados. Chama-se x
′
∈ {x
1
,x
2
,. . .,x
n
} de o vizinho
mais próximo de x se
δ
(x
′
,x) = min
δ
(x
i
,x) i = 1, 2, ..., n (2.1)
onde
δ
(x
k
,x
j
) mede a similaridade entre dois exemplos quaisquer e é minimizada quanto mais
semelhantes eles forem. Atribui-se à classe
θ
do exemplo desconhecido (x,
θ
) o valor de
θ
′
do
par (x
′
,
θ
′
). Caso vários exemplos estejam à mesma distância do novo exemplo a classificar,
atribui-se a classe da maioria de seus vizinhos a
θ
.
Uma extensão natural do classificador do vizinho mais próximo é considerar os k vizinhos
mais próximos do exemplo desconhecido. Esta variação, também chamada de kNN, aparen-
temente faz uso mais adequado dos dados do problema, decidindo por voto qual será a classe
escolhida. Neste caso, é desejável que k seja suficientemente grande, a fim de minimizar a pro-
babilidade de que poucos exemplos com classificação incorreta determinem a classe de outros,
mas é também desejável que k seja o menor possível, a fim de evitar que exemplos de classes
distintas se misturem na regra de decisão.
A principal vantagem do algoritmo é a simplicidade, dado que não é necessária uma etapa
de treinamento. Breiman et al. (1984, p. 16) citam como seus principais pontos fracos:
1. A heurística é sensível à escolha da métrica de similaridade e, normalmente, não há uma
alternativa melhor que as demais em todas as situações.
2. A forma ingênua de implementação da heurística, que armazena todos os exemplos co-
nhecidos e busca exaustivamente pelo vizinho mais próximo, não é computacionalmente
interessante se a base de casos for numerosa.
3. Não há uma maneira satisfatória para tratamento de informações categóricas (simbóli-
cas) e a heurística é altamente sensível a valores ausentes, exemplos ruidosos, atributos
irrelevantes etc.
4. A heurística não gera informações extras (e possivelmente relevantes) a partir dos dados.
18
As próximas seções apresentam algumas medidas de similaridade alternativas, que têm sido
utilizadas por serem, supostamente, mais adequadas a problemas com dados temporais. A sub-
seção 2.2.6 fala, brevemente, sobre formas mais eficientes do algoritmo, que são dependentes
da escolha da medida. As fraquezas relacionadas ao tipo dos dados (simbólicos, ruidosos etc.)
não serão discutidos neste trabalho. A geração de informações adicionais sobre os dados é uma
qualidade normalmente atribuída às árvores de decisão, tema do próximo capítulo.
2.2 Medidas de similaridade
Nesta seção são apresentadas as métricas mais comuns para mensuração da similaridade
entre os exemplos no algoritmo do vizinho mais próximo, quando os dados são temporais. No
restante deste capítulo, será assumido que o vetor de características é formado simplesmentepor
um único atributo e que este é uma série temporal de tamanho d (problema unidimensional).
2.2.1 Distância Euclidiana
A escolha inicial, e também a mais freqüente, para comparação de duas séries temporais, é
considerar que elas são vetores em um espaço com d dimensões e calcular a distância Euclidiana
entre estes. Dadas duas seqüências y e z quaisquer, Devijver & Kittler (1982, p. 232) definem a
distância como
δ
(y,z) = [(y−z)
t
(y−z)]
1/2
=
d
∑
i=1
(y
i
−z
i
)
2
1/2
. (2.2)
Há várias limitaçõesassociadas a esta medida para comparação de sériestemporais. Agrawal
et al. (1995) dizem que a distância é muito sensível a ruídos, a pequenas variações de fase entre
as seqüências e a translações e escalamentos horizontais. Como ilustração, a Figura 2.1 mos-
tra um exemplo extremo em que duas seqüências possuem exatamente os mesmos contornos,
porém com uma pequena defasagem no eixo do tempo. Na figura, a distância Euclidiana entre
estas duas instâncias é maior do que a distância Euclidiana delas em relação a linha reta pon-
tilhada, que representa o valor médio das séries. Se este fosse o caso em um problema real, o
algoritmo NN escolheria a linha pontilhada como vizinho mais próximo das duas seqüências.
No caso das limitações associadas às diferenças de escala e translações verticais, uma solu-
ção amplamente aceita é normalizar todas as seqüências antes do cálculo da similaridade. Cada
série é normalizada independentemente das demais e, geralmente, se usa a normalização linear
para um intervalo fixo ou a normalização que converte a média e a variância da série para zero
19
Tempo
0 5 10 15 20 25 30 35 40 45 50 55 60 65 70
0
1
2
3
4
5
6
Figura 2.1: Cálculo da distância Euclidiana. Uma pequena variação de fase pode ocasionar
diferença significativa na medida.
e um, respectivamente. Na segunda alternativa, cada valor é substituído através da fórmula
y
′
i
=
(y
i
−
y)
σ
y
, (2.3)
onde y é a média e
σ
y
é o desvio padrão dos valores que compõem a seqüência. O segundo tipo
de normalização é mais apropriado por ser menos sensível a ruídos (HAN; KAMBER, 2001,
p. 115).
Se a média e a dispersão das séries contiverem padrões relevantes para a classificação, estas
informações podem ser adicionadas aos dados como novas características estáticas. Os algorit-
mos de classificação experimentados neste trabalho, porém, classificam sempre comparando os
exemplos entre si e não considerarão nenhuma característica estática. Em todos os casos expe-
rimentados, os dados foram normalizados usando a Equação 2.3 e a média e o desvio padrão
foram descartados.
As limitações associadas a ruídos e a variações de fase podem ser contornadas substituindo
a distância Euclidiana por alguma outra métrica mais sofisticada - nas próximas seções algumas
destas métricas são descritas.
Por fim, sobre a distância Euclidiana, ainda é interessante notar que, exceto pela forma de
normalização das séries, que no caso de atributos não temporais é realizada considerando os
valores de todos os exemplos (no caso das séries cada exemplo é normalizado separadamente),
a forma de cálculo da similaridade produzirá o mesmo resultado que seria obtido caso cada
amostra da variável temporal fosse considerada uma característica não temporal. Assim, qual-
quer outra medida já usualmente empregada com o algoritmo NN pode substituir a Euclidiana.
Por exemplo, Devijver & Kittler (1982) apresentam algumas medidas de similaridade alternati-
vas: Manhattan, Chebychev, quadrática etc. Nenhuma delas, porém, parece possuir formulação
mais apropriada a dados temporais. Nos experimentos do Capítulo 4 a distância Manhattan,
20
definida por
δ
(y,z) =
d
∑
i=1
|y
i
−z
i
|
, (2.4)
também foi considerada. A expectativa é que o classificador com esta medida talvez seja me-
lhor do que o Euclidiano em alguns casos, mas que não será possível dizer que há diferença
significante entre eles.
2.2.2 Correlação linear
No contexto de casamento de padrões, uma métrica utilizada com freqüência como medida
de similaridade é a correlação linear. Theodoridis & Koutroumbas (2006) citam, como exem-
plos de aplicação, problemas em que se deseja encontrar um padrão preestabelecido em um
conjunto de dados que pode contê-lo, por exemplo, um objeto em uma imagem ou um trecho
de uma série temporal (subseqüência) na série completa.
O coeficiente de correlação é uma medida estatística que determina a relação linear entre
duas variáveis aleatórias. É definido como
ρ
y,z
=
σ
yz
σ
y
σ
z
=
d
∑
i=1
(y
i
−
y)(z
i
−z)
d
∑
i=1
(y
i
−
y)
2
d
∑
i=1
(z
i
−
z)
2
1/2
. (2.5)
O coeficiente de correlação possui valor no intervalo [−1,1], sendo que os extremos impli-
cam relação linear perfeita (no sentido positivo ou negativo) e zero implica que não há relação
linear entre as variáveis.
É importante observar que o vizinho mais próximo de um exemplo qualquer, determinado
pelo coeficiente de correlação, é o mesmo que o determinado pela distância Euclidiana, se as
séries estiverem normalizadas de acordo com a Equação 2.3. Neste caso, de acordo com a
Equação 2.5,
ρ
y,z
=
∑
d
i=1
y
i
z
i
, porque
σ
y
=
σ
z
= 1 e y = z = 0. Já a distância Euclidiana (ao
quadrado) entre as séries será
δ
2
(y,z) =
d
∑
i=1
(y
i
−z
i
)
2
(2.6)
δ
2
(y,z) =
d
∑
i=1
(y
i
−
y)
2
−2
d
∑
i=1
y
i
z
i
+
d
∑
i=1
(z
i
−
z)
2
(2.7)
δ
2
(y,z) = 2−2
d
∑
i=1
y
i
z
i
(2.8)
21
ou seja, o valor das duas métricas diferem apenas por soma e multiplicação de constantes e
pela função de raiz quadrada, que não interferem na ordem dos vizinhos dos exemplos. Em
problemas com dados já previamente normalizados, como os apresentados no Capítulo 4, a
classificação com estas medidas é idêntica.
Por fim, a medida de correlação, como descrita acima, considera boa apenas a correlação
positiva. Considerar boa também a correlação negativa, fazendo com que a métrica seja igual
ao valor absoluto da Equação 2.5, é uma opção que pode ser útil se for de interesse considerar
iguais os exemplos simétricos em relação ao eixo temporal. Neste caso, a métrica não será mais
equivalente à distância Euclidiana, evidentemente.
2.2.3 Distância de Hamming
A distância de Hamming, introduzida por Hamming (1950), é definida como o número de
coordenadas nas quais dois vetores diferem. A distância é normalmente calculada quando as
seqüências possuem um alfabeto finito e é especialmente útil como uma forma de determinação
da similaridade entre cadeias de caracteres (strings).
A distância de Hamming entre os vetores de caracteres y e z é calculada por
δ
(y,z) =
d
∑
i=1
t(y
i
,z
i
), (2.9)
onde t(y
i
,z
i
) = 1, se y
i
= z
i
e t(y
i
,z
i
) = 0, caso contrário.
Para aplicação da distância de Hamming como medida de similaridade, as séries temporais
devem passar por duas tarefas de pré-processamento: normalização e discretização. O pro-
cesso de normalização é o mesmo já descrito na seção 2.2.1. Para discretização, deve-se definir
um número fixo de símbolos válidos (alfabeto) e converter cada valor da série para um destes
símbolos. Normalmente, criam-se intervalos de larguras iguais ou intervalos que contenham
a mesma quantidade de pontos (freqüências iguais). A primeira forma é considerada inferior
por dividir os pontos da série de maneira muito desigual, especialmente se os dados contiverem
ruídos (HAN; KAMBER, 2001, p.131).
Caso seja possível assumir que a distribuição dos pontos das séries siga uma distribuição
especial (por exemplo a Normal), Lin et al. (2003) utilizam uma forma de discretização que tem
a propriedade adicional, computacionalmente bastante desejável, de varrer cada seqüência ape-
nas uma vez. Para tal, considerando que a série foi normalizada, basta recorrer a uma tabela de
probabilidades para determinação dos pontos de cortes que definem os intervalos. Por exemplo,
22
a Tabela 2.1 lista os limites para criação de 5 intervalos eqüiprováveis, assumindo a Distribuição
Normal Padrão. Caso se queira discretizar as séries em 5 intervalos, basta substituir cada valor
numérico pelo caractere associado ao intervalo que o contém.
Alfabeto a b c d e
Limites (−∞,−0.84] (−0.84,−0.25] (−0.25,0.26] (0.26,0.85] (0.85, ∞)
Tabela 2.1: Limites para divisão da Distribuição Normal Padrão em cinco intervalos eqüiprová-
veis.
Em relação à distância Euclidiana, a combinação da discretização das séries e do cálculo
da distância de Hamming só é vantajosa pelo processo de discretização, que pode reduzir o
ruído ao remover as variações abruptas (altas freqüências) das séries. O processo de discretiza-
ção, porém, trata de maneira insatisfatória pontos que estejam muito próximos, mas que foram
discretizados como símbolos diferentes devido à posição dos limites dos intervalos. No caso
da distância de Hamming, estes pontos aumentam o valor da distância, quando na prática a
diferença real entre eles pode ser muito menor do que a largura dos intervalos.
Uma possível alternativa, implementada por Bozkaya, Yazdani & Özsoyoglu (1997) em
conjunto com a distância de edição (apresentada na próxima seção), é considerar que os pontos
são iguais se a distância entre eles for menor do que um limite
δ
. Tal variação parece fazer uso
mais apropriado dos valores numéricos sem sacrificar a desejável característica de redução do
ruído. O valor de
δ
, neste caso, deve ser ajustado e influenciará decisivamente no valor final da
métrica (e possivelmente na precisão da classificação). Em todos os experimentos apresentados
nos próximos capítulos, esta foi a forma de discretização escolhida.
2.2.4 Distância de edição
A distância de edição, introduzida por Levenshtein (1966) e por isto também chamada de
distância de Levenshtein, é definida como a quantidade mínima de operações necessárias para
transformar uma cadeia de caracteres em outra qualquer. As operações permitidas para tal são
a substituição, a adição e a remoção de caracteres.
Assim como no caso da distância de Hamming, para aplicação da distância de edição na
comparação de séries temporais numéricas, é preciso que estas sejam normalizadas e discreti-
zadas para um alfabeto finito de símbolos.
A distância de edição entre dois vetores de caracteres y e z de tamanho d pode ser en-
contrada através de programação dinâmica, a partir da relação de recorrência apresentada, por
exemplo, em Gusfield (1997, p.218). A definição é feita com base na função D(i, j), que re-
23
presenta o menor número de operações que transformam os primeiros i caracteres de y nos
primeiros j caracteres de z. Os casos bases da relação são definidos como
D(i,0) = i (2.10)
D(0, j) = j. (2.11)
Intuitivamente, o primeiro caso significa que para transformar i caracteres de y em zero
caracteres de z são necessárias i operações de exclusão. De forma semelhante, para transformar
zero caracteres de y em j caracteres de z são necessárias j operações de inclusão. Para i > 0 e
j > 0, a distância é definida como
D(i, j) = min
D(i, j−1) + 1
D(i−1, j) + 1
D(i−1, j−1) +t(i, j)
(2.12)
onde t(i, j) = 0, se y
i
= z
j
e t(i, j) = 1, caso contrário. Neste caso, o número de operações será
o mínimo entre três opções:
• Transformar i caracteres de yem j−1 caracteres de z usando a menor quantidade possível
de operações e então incluir z
j
em y.
• Transformar i−1 caracteres de y em j caracteres de z usando a menor quantidade possível
de operações e então excluir y
i
.
• Transformar i −1 caracteres de y em j −1 caracteres de z usando a menor quantidade
possível de operações e então substituir y
i
por z
j
se eles forem diferentes.
A prova de que D(i, j) realmente calcula a menor quantidade de operações necessárias para
executar a transformação pode ser encontrada em Gusfield (1997, p.218-219) e não será aqui
transcrita. Como se deseja computar a distância de edição das seqüências y e z completas, a
medida de similaridade será
δ
(y,z) = D (d,d). (2.13)
A implementação ingênua (recursiva) da relação acima produz uma árvore com número
de nós exponencial em relação a dimensão d dos vetores. Porém, usando a forma tradicional
de computação tabular da programação dinâmica, pode-se encontrar a distância de edição em
O(d
2
) operações. Para tal, usa-se uma matriz de dimensões d + 1, que é preenchida e avaliada
de acordo com o Algoritmo 1.
24
Algoritmo 1 Computa a distância de edição entre dois vetores de caracteres y e z
Entrada: M, uma matriz quadrada com dimensões d + 1;
y e z, as séries temporais.
Saída: distância de edição entre y e z
1: para i = 0 até d faça
2: m
i,0
← i
3: m
0,i
← i
4: fim para
5: para i = 1 até d faça
6: para j = 1 até d faça
7: se y
i
= z
j
então
8: t ← 0
9: senão
10: t ← 1
11: fim se
12: m
i, j
← min(m
i, j−1
+ 1,m
i−1, j
+ 1,m
i−1, j−1
+t)
13: fim para
14: fim para
15: retorne m
d,d
Em relação à distância Euclidiana, a estratégia de discretização das séries e cálculo da dis-
tância de edição possui algumas vantagens relevantes. Em primeiro lugar, assim como no caso
da distância de Hamming, o processo de discretização diminui o efeito de variações abruptas e
pode reduzir a influência de ruídos. Se a forma de discretização de Bozkaya, Yazdani & Öz-
soyoglu (1997) for utilizada, a condição da linha 7 do Algoritmo 1 é alterada para |y
i
−z
j
| <
δ
e o algoritmo passa a receber séries apenas normalizadas para o cálculo.
Ainda em relação à distância Euclidiana, as operações de inserção e exclusão realizadas
durante o cálculo da distância de edição corrigem variações de fase entre as seqüências. Além
de casos onde o desalinhamento de fase ocorre nas séries completas, como o ilustrado na Figura
2.1, a distância de edição corrige variações locais no eixo do tempo, permitindo que séries com
pequenas distorções temporais transitórias sejam alinhadas e tenham menor valor de distância
entre si. Por exemplo, a Figura 2.2 mostra duas seqüências com distorções locais no eixo do
tempo.
Usando o método de discretização em cinco intervalos, descrito na seção 2.2.3, a partir
destas séries seriam geradas as seqüências da Figura 2.3. Como ilustração, as duas seqüências
estão alinhadas com traços verticais, que marcam os caracteres que coincidiriam durante o
cálculo da distância, e com traços horizontais, que marcam os pontos onde ocorreriam inserções
ou exclusões de caracteres. A distância de edição neste exemplo é 6. Casos extremos como os
da Figura 2.1 são menos prováveis nesta situação.
25
Tempo
0 5 10 15 20 25 30 35 40 45 50
-2
-1
0
1
2
Figura 2.2: Duas seqüências com distorções locais no eixo do tempo. Por volta do instante
t = 20 há uma inversão no atraso entre as séries.
Figura 2.3: Uma representação discreta das séries e o alinhamento produzido.
Diversas variações da distância de edição podem ser encontradas na literatura. As mais
comuns são geradas a partir da introdução de custos para realização de cada operação. Gusfield
(1997, p.224) apresenta a seguinte recorrência como forma geral da distância de edição com
pesos nas operações
D(i,0) = p
d
×i (2.14)
D(0, j) = p
d
× j (2.15)
D(i, j) = min
D(i, j−1) + p
d
D(i−1, j) + p
d
D(i−1, j−1) +t(i, j)
(2.16)
onde t(i, j) = p
c
, se y
i
= z
j
e t(i, j) = p
s
, caso contrário. Nesta formalização, as operações
de inclusão e exclusão de caracteres são simétricas e possuem peso igual a p
d
, a operação de
substituição de caracteres possui peso p
s
e o casamento de caracteres possui peso p
c
. Na versão
da distância proposta por Levenshtein p
c
= 0 e p
s
= p
d
= 1.
A partir desta formalização, é possível deduzir que a distância de Hamming é um caso
especial da distância de edição, no qual a operação de substituição de caracteres possui custo
unitário, as operações de inserção e exclusão de caracteres possuem custo infinito e a operação
de casamento de caracteres possui custo zero.
Outra variação muitopopular é o algoritmo que calcula a maior subseqüênciacomum (LCSS
- Longest common subsequence). Neste caso, deseja-se maximizar o total de concordâncias
26
entre as duas seqüências. A LCSS é calculada de maneira semelhante à distância de edição
através da seguinte recorrência
L (i,0) = L (0, j) = 0 (2.17)
L (i, j) =
L (i−1, j −1) + 1 se y
i
= z
i
L (i−1, j) se L (i−1, j) ≥ L (i, j−1)
L (i, j−1) caso contrário
(2.18)
Porque se deseja uma métrica para minimização, a distância entre duas seqüências será
δ
(y,z) = d −L (d,d) (2.19)
Apesar da formulação um pouco diferente, quando computado entre duas seqüências, o va-
lor da maior subseqüência comum também pode ser obtido a partir da distância de edição com
pesos nas operações. Para tal, basta configurar a formulação geral de maneira que a operação de
substituição de caracteres possua custo infinito, as operações de inserção e exclusão de carac-
teres possuam custo unitário e a operação de casamento de caracteres possua custo zero. Após
calcular a distância de edição com esta configuração de pesos, o valor da LCSS pode ser obtido
através da relação a seguir, cuja prova é apresentada, por exemplo, por Bozkaya, Yazdani &
Özsoyoglu (1997).
D(d,d) = 2[d −L (d,d)] (2.20)
2.2.5 DTW - Dynamic time warping
No contexto de reconhecimento de padrões, umas das primeiras aplicações que necessitou
de técnicas que tratassem o casamento aproximado de séries temporais foi o reconhecimento
de palavras faladas. Sakoe & Chiba (1978) são citados como os primeiros autores a terem
utilizado uma solução baseada em alinhamento de séries e programação dinâmica neste tipo de
aplicação. A medida de similaridade, conhecida como DTW (Dynamic time warping), procura
remover distorções locais entre as séries antes de calcular a distância entre elas. Esta última
característica é a principal diferença entre a distância de edição e DTW: enquanto a primeira,
de certa forma, conta os pontos que não se equivalem após alinhar as seqüências da melhor
maneira possível, o algoritmo DTW calcula a distância entre as seqüências (usando os valores
numéricos originais) após também alinhá-las da melhor maneira possível. No algoritmo DTW,
as operações de inserção e exclusão de caracteres realizadas pela distância de edição podem ser
interpretadas como alongamentos realizados nas séries.
27
A forma de cálculo da similaridade pelo algoritmo DTW é definida através da seguinte
recorrência
DTW(i, j) =
γ
(y
i
,z
j
) + min
DTW(i, j −1)
DTW(i−1, j)
DTW(i−1, j −1)
(2.21)
onde DTW(i, j) é uma função que calcula a similaridade entre os i primeiros pontos de y e os
j primeiros pontos de z após alinhá-los e
γ
(y
i
,z
j
) é uma função que computa a distância entre
dois pontos (normalmente, usa-se a distância Euclidiana).
Sakoe & Chiba (1978) descrevem ainda algumas possíveis melhorias a serem realizadas no
algoritmo com o objetivo de evitar que os alongamentos produzam distorções exageradas entre
as séries. Em primeiro lugar, deseja-se que as distorções diminuam a distância total, através da
eliminação das diferenças de fase. Porém, as séries alinhadas serão maiores que as originais.
Uma forma mais justa de avaliar a similaridade é fazer uma ponderação da distância em relação
ao tamanho das seqüências. Desta forma, seria escolhido o alinhamento que produzisse a menor
distância média por ponto e não a menor distância total. Embora aparentemente benéfica, tal al-
teração favorece que grandes diferenças de fase sejam desconsideradas pelo algoritmo, situação
não desejada em problemas reais.
A segunda melhoria visa exatamente restringir a maior diferença de fase (local) que pode
ser corrigida pelo algoritmo. Tal melhoria é obtida impondo uma restrição adicional ao método
de cálculo, para que apenas um número máximo de distorções em uma direção seja permitido.
Este valor máximo de operações permitidas é chamado de janela de ajuste. O Algoritmo 2
descreve os passos para o cálculo da distância com esta nova restrição.
O efeito da janela de ajuste pode ser melhor visualizado através da matriz de cálculo usada
para computar a distância. Considere a Tabela 2.2, que representa a matriz M do Algoritmo
2. As linhas da matriz representam os pontos da série y e as colunas representam os pontos da
série z. Cada célula (i, j) contém a distância entre y
i
e z
j
. O algoritmo DTW busca o caminho
com a menor distância total para chegar ao ponto (d,d), a partir do ponto (1, 1). A partir de
um ponto qualquer, o algoritmo pode seguir em três direções, sendo que um passo na diagonal
indica que os pontos estão alinhados, um passo a baixo indica que a série z foi alongada e um
passo à direita indica que a série y foi alongada. A restrição da janela de ajuste força que o total
de alongamentos em uma direção nunca seja maior que uma constante (r). Neste caso, apenas
uma parte da matriz é avaliada e nas células das fronteiras da janela algumas direções não são
mais permitidas. Na Tabela 2.2, apenas as células que seriam avaliadas estão preenchidas com
a indicação dos caminhos possíveis.
28
Algoritmo 2 Computa a distância entre duas séries temporais y e z usando o algoritmo DTW
com janela de ajuste.
Entrada: M, uma matriz quadrada com dimensões d + 1;
r, o tamanho da janela de ajuste;
y e z, as séries temporais.
Saída: a distância entre as séries y e z alinhadas
1: m
i, j
← ∞ ∀[(0 ≤ i ≤d) ∧(0 ≤ j ≤ d)]
2: m
0,0
← 0 // Inicialização da matriz
3: para i = 1 até d faça
4: se (i−r) > 0 então
5: j ← i−r
6: senão
7: j ← 1
8: fim se
9: repita
10: m
i, j
←
γ
(y
i
,z
j
) + min(m
i, j−1
,m
i−1, j
,m
i−1, j−1
)
11: j ← j+ 1
12: enquanto [( j ≤ d) ∧( j < i+ r)]
13: fim para
14: retorne m
d,d
M
i, j
z
1
z
2
z
3
z
4
.. . z
d−3
z
d−2
z
d−1
z
d
y
1
→
↓ց
→
↓ց
↓ց
y
2
→
↓ց
→
↓ց
→
↓ց
↓ց
y
3
→
ց
→
↓ց
→
↓ց
→
↓ց
.. .
y
4
→
ց
→
↓ց
→
↓ց
.. . .. .
.. . .. . .. . .. . .. . . ..
y
d−3
.. . .. .
→
↓ց
→
↓ց
↓ց
y
d−2
.. .
→
↓ց
→
↓ց
→
↓ց
↓
y
d−1
→
ց
→
↓ց
→
↓ց
↓
y
d
→ →
M
d,d
Tabela 2.2: Computando DTW com janela de ajuste r = 2. Neste caso, o caminho na tabela de
cálculo não pode se afastar mais de 2 unidades da diagonal.
Alguns trabalhos já têm analisado a variação do desempenho do classificador do vizinho
mais próximo com DTW em função do tamanho da janela de ajuste. Xi et al. (2006) mostram
que a influência do parâmetro na precisão do classificador é relevante e que as melhores con-
figurações são obtidas com janelas relativamente pequenas. Nesta situação, a normalização da
distância de acordo com o tamanho das séries alongadas não causa diferença significativa. A
restrição de janela também pode ser aplicada às medidas da seção anterior (distância de edição
e LCSS). As três medidas, portanto, possuem um parâmetro em comum, que deve ser ajustado,
com provável influência no resultado da classificação. Um detalhe interessante é que janelas
menores aceleram o cálculo das medidas. O caso extremo, com janela de tamanho zero, im-
29
plica em tempo de cálculo linear, e não mais quadrático.
Uma característica importante do algoritmo DTW é que ele calculará exatamente a distân-
cia Euclidiana, caso nenhum alongamento aconteça (ou seja, se as séries já estiverem completa-
mente em fase). Assim como no caso da distância Euclidiana, é necessário normalizar as séries
para remoção de diferenças de escala e deslocamentos verticais.
Em comparação à distância de edição, a medida dispensa o passo de discretização. Como
conseqüência, o algoritmo parece mais apropriado a dados numéricos, embora, teoricamente,
ele seja mais vulnerável a influências de ruídos. Na prática, conforme mostrado no Capítulo
4, ambos geram bons resultados, superiores ao do algoritmo do vizinho mais próximo com a
distância Euclidiana.
2.2.6 Métricas baseadas em transformações
Uma estratégia para determinar a similaridade entre seqüências é realizar uma transforma-
ção dos dados originais para um novo domínio e então calcular a semelhança entre elas de
acordo com esta nova representação. Por exemplo, o método de discretização e utilização de
medidas de casamento aproximado de strings segue essa estratégia.
Antunes & Oliveira (2001) e Savary (2002) citam trabalhos que utilizam as transformadas
de Fourier e Wavelets para representação das seqüências. A principal referência de ambos é
o trabalho de Agrawal, Faloutsos & Swami (1993), que trata de uma estratégia para recupe-
ração eficiente de seqüências em bancos de dados, baseada em propriedades da Transformada
Discreta de Fourier.
A Transformada Discreta de Fourier de um sinal x de tamanho d é a seqüência X de núme-
ros complexos, também de tamanho d, definida por
X
k
=
1
√
d
d−1
∑
t=0
x
t
e
−i2
π
tk
d
k = 0, 1, . . .,d −1 (2.22)
onde i é a unidade imaginária (i =
√
−1). Como x é um sinal real, X
0
será um número real
com valor proporcional à média de x (X
0
= 0, no caso de séries normalizadas como nas seções
anteriores).
A principal observação de Agrawal, Faloutsos & Swami (1993) é que o Teorema de Parse-
val e a característica linear da transformação garantem que, dadas duas séries x e y quaisquer,
d−1
∑
t=0
|x
t
−y
t
|
2
=
d−1
∑
k=0
|X
k
−Y
k
|
2
. (2.23)
30
Em palavras, a distância Euclidiana dos coeficientes obtidos pela transformação é a mesma
distância das séries originais. Tal observação permite que os coeficientes sejam usados na cons-
trução de estruturas de dados para recuperação eficiente do vizinho mais próximo.
A consulta pelo vizinho mais próximo, implementada da forma mais ingênua, exige que
cada um dos exemplos conhecidos da base de treinamento seja comparado ao exemplo des-
conhecido para determinação do vizinho. Este procedimento pode ser acelerado por meio de
índices, através de alguma estrutura de dados de particionamento do espaço de características,
como k-d-tree (BENTLEY, 1975; FREIDMAN; BENTLEY; FINKEL, 1977), r-tree (GUTT-
MAN, 1984), entre outras. Estes índices podem ser usados em problemas com dados de (prati-
camente) qualquer tipo, mas têm uma limitação conhecida de não funcionarem bem com muitas
dimensões (características) - por exemplo, Bentley (1975) sugere que a k-d-tree só é útil se o
número de casos a indexar for maior do que 2
2m
, onde m é o total de características da base de
dados.
Em problemas com dados temporais, se cada ponto da série for considerado uma dimensão,
as estruturas de indexação não proporcionarão ganhos de desempenho. Para resolver esta ques-
tão, em problemas com séries de variação suave, Agrawal, Faloutsos & Swami (1993) observam
que a Transformada de Fourier concentra a maior parte do sinal (energia) em alguns poucos co-
eficientes de baixa freqüência. Utilizando apenas alguns coeficientes para construção do índice,
é possível recuperar de maneira eficiente séries temporais longas. As consultas ao índice, po-
rém, não retornam mais o mesmo conjunto de exemplos retornado pela busca exaustiva, uma
vez que parte da informação foi descartada. Agrawal, Faloutsos & Swami (1993) mostram que
o resultado das consultas ao índice contém o resultado da busca exaustiva. Assim, as consultas
são realizadas em duas etapa: na primeira, usa-se o índice para recuperar uma aproximação do
resultado final; na segunda, o resultado aproximado é filtrado no domínio original.
Embora o procedimento original tenha sido desenhado para recuperação de exemplos a
partir da distância Euclidiana, algumas extensões existem para indexação de outras medidas
de similaridade. Por exemplo, Keogh & Ratanamahatana (2005) apresentam uma aproximação
que permite indexar DTW usando as mesmas estruturas de dados. Algumas outras estruturas,
como metrics trees (UHLMANN, 1991), podem ser usadas para indexar medidas que respeitem
as propriedades de um espaço métrico (inigualdade triangular, simetria etc.), como a distância
de edição.
Todos estes métodos são exatos, ou seja, produzirão classificadores idênticos aos obtidos
originalmente. A utilidade deles, portanto, limita-se a melhorar o tempo dos algoritmos e não
a precisão da classificação. A Transformada de Fourier, neste caso, serve apenas como uma
31
ferramenta para compactar a informação existente nos dados, e não para formular uma nova
medida de similaridade.
É possível, porém, usar as propriedades da Transformada de Fourier para formular novas
métricas de comparação. Por exemplo, ao representar os coeficientes (complexos) na forma
polar, translações do eixo do tempo nos dados originais não alteram o módulo dos valores no
domínio transformado. Esta propriedade é usada com freqüência na extração de características
estáticas (ou invariantes a translações) de séries temporais.
Os experimentos do Capítulo 4, porém, se limitarão a avaliar o desempenho da classificação
usando apenas os primeiros coeficientes da transformada. Agindo assim, somente a informação
de baixa freqüência (que define as variações suaves das séries) é considerada. Um possível
ganho deste tratamento é desprezar os ruídos de alta freqüência, que distorcem o formato das
seqüências. Nesta abordagem, o número de coeficientes a considerar durante o cálculo da dis-
tância é um parâmetro da métrica que deve ser ajustado, com provável influência na precisão
da classificação. Ao permitir que o número de coeficientes da medida varie, a nova métrica po-
derá ser ajustada para que todos sejam utilizados, situação em que a classificação será a mesma
obtida com a distância Euclidiana.
Agrawal, Faloutsos & Swami (1993) observam ainda que qualquer transformação que pre-
serve a distância Euclidiana pode substituir a Transformada de Fourier na tarefa de compactar
as séries para indexação. Dependendo do problema, outras transformadas podem compactar
mais informação em menos coeficientes, acelerando ainda mais a busca pelo vizinho mais pró-
ximo. A família de Transformadas Discretas de Wavelets (DAUBECHIES, 1992) são as mais
utilizadas neste contexto (por exemplo, por Struzik & Siebes (1999), Chan & Fu (1999)).
A Transformada Discreta de Wavelet de um sinal x de tamanho d (neste caso, d deve ser
potência de 2) é a seqüência c de coeficientes obtida por
c
j,k
=
1
d
d−1
∑
t=0
x
t
ψ
j,k
(t). (2.24)
onde a Wavelet Mãe, chamada de
ψ
(t), será transformada por escalamentos e translações pela
relação
ψ
j,k
(t) = 2
j/2
ψ
(2
j
t −k) (2.25)
com j determinando o fator de escala diático (produto por uma potência de 2), k determinando
a translação e j = 0,.. .log
2
(d) −1 e, para cada resolução j, k = 0. . .2
j
−1.
A Wavelet de Haar é o exemplo mais elementar de base wavelet. A Wavelet Mãe desta
32
família é definida como:
ψ
Haar
(t) =
1, 0 ≤t < 0.5
−1, 0.5 ≤ t < 1
0, caso contrário
(2.26)
No caso da utilização da Transformada Discreta de Wavelet para compactação das séries,
Wu, Agrawal & Abbadi (2000) mostram que o desempenho do índice produzido é semelhante
ao obtido com a Transformada de Fourier, com o desempenho variando de acordo com o tipo
do dado a ser indexado.
Assim como no caso da Transformada de Fourier, as Transformadas Wavelets podem ser
usadas para criação de medidas de similaridade. Nos experimentos do Capítulo 4, foi explo-
rado o aspecto da análise em múltiplas resoluções da transformada. Considerando apenas os
coeficientes das primeiras resoluções (parâmetro j), pode-se observar o sinal de acordo com um
nível de detalhe diferenciado. Assim como no caso da Transformadas de Fourier, ao utilizar
somente as primeiras resoluções, apenas a parte suave da série é considerada e os detalhes (altas
freqüências) são desprezados. O número de resoluções é um parâmetro da métrica que deve ser
ajustado. Caso todas as resoluções estejam no cálculo da distância, o valor será o mesmo que
o da distância Euclidiana e o classificador não sofrerá alteração. Espera-se que a métrica seja
mais adequada por remover distorções (ruídos), que alteram a forma das seqüências.
2.3 Combinando várias métricas em um mesmo classificador
Dado que existem várias medidas de similaridade disponíveis, uma possível extensão do
algoritmo do vizinho mais próximo é implementar a regra de decisão com base em um conjunto
de medidas. Yao &Ruzzo (2006), em uma aplicação prática diferente, utilizam o algoritmo com
várias medidas de similaridade e realizam uma etapa de treinamento, através de métodos de
regressão, para determinar pesos associados às métricas no cálculo da distância entre exemplos.
Tal abordagem pode ser imediatamente relacionada ao problema de seleção de características,
no qual há um conjunto de atributos, dentre os quais são selecionados alguns para treinamento
do classificador. No problema de seleção de características, pode-se apenas aceitar pesos 0 ou
1, situação em que as características apenas são incluídas ou não no conjunto final, ou ainda
pesos diversos, dando maior importância para as que pareçam ser mais relevantes.
Kohavi, Langley & Yun (1997) apresentam um método simples e relativamente eficiente
de seleção de características por distribuição de pesos, que pode ser empregado para o caso
33
de ponderação das métricas. Ao invés de considerar os pesos como valores reais, apenas
um subconjunto de pesos discretos são avaliados. Na implementação de Kohavi, Langley &
Yun (1997), o intervalo [0,1] é dividido k em partes iguais, com cada valor discreto separado
por uma constante de divisão d = 1/k. Os valores possíveis para os pesos serão, portanto,
0,1/k, 2/k,...,(k−1)/k,1. A busca pela melhor configuração de pesos é feita através de uma
heurística e a qualidade dos pesos é determinada pelo erro médio do algoritmo do vizinho mais
próximo no conjunto de treinamento com cada configuração. O método de busca segue uma
estratégia gulosa para alterar os pesos e persiste na busca até que, em um número consecutivos
de passos, não haja melhoria no erro de classificação.
A forma de distribuição de pesos de Kohavi, Langley & Yun (1997), porém, aceita que
configurações redundantes sejam avaliadas. Suponha que existam apenas duas características
e que os pesos possíveis sejam determinados por d = 0,2. O vizinho mais próximo de um
exemplo considerando pesos 0,2 e 0,4, é o mesmo que o determinado pelos pesos 0,4 e 0,8, por
exemplo.
Para evitar essa redundância, uma nova heurística de distribuição de pesos e busca pela
melhor configuração foi criada. O Algoritmo 3 descreve a heurística, que prevê a soma dos
pesos distribuídos entre as medidas de similaridade sempre igual a 1 e cada métrica recebendo
um valor discreto nos moldes da heurística de Kohavi, Langley & Yun (1997).
No Algoritmo 3, a função que estima o erro de classificação (linha 4) recebe como parâ-
metros o vetor de pesos, o conjunto de métricas e os dados de treinamento. Cada métrica está
relacionada a um peso de acordo com a posição deste no vetor. A estimativa do desempenho é
feita usando o procedimento de validação leave-one-out, que consiste em realizar n execuções
do algoritmo de classificação, nas quais apenas um dos n exemplos da base de treinamento é
reservado para teste de validação. O erro total será a soma de elementos classificados incorre-
tamente.
A restrição de que a soma dos pesos seja sempre igual a 1 faz com que existam
C
k
|M|+k−1
=
|M|+k−1
k
(2.27)
combinações possíveis para os pesos, onde |M|é o total de métricas que podem ser combinadas.
Tal relação pode ser provada supondo que existam k unidades de peso (iguais a d) para serem
distribuídas entre |M| compartimentos e que alguns destes podem ficar vazios. Há, portanto, k
símbolos com |M|−1 separadores, que determinam quais dos símbolos pertencem a cada um
dos compartimentos. Como os símbolos e os separadores não são distintos, o total de maneiras
de organizá-los é determinado pela equação 2.27.
34
Algoritmo 3 Faz busca pela configuração de pesos que maximiza o desempenho do algoritmo
do vizinho mais próximo com diversas métricas.
Entrada: S, o conjunto de instâncias de treinamento;
M, o conjunto de métricas de similaridade;
d, o grão mínimo dos pesos a distribuir.
Saída: P, vetor de tamanho m contendo a configuração de pesos melhor avaliada.
1: me ← ∞ // Menor erro obtido.
2: Q
0
← 1 e Q
1...m−1
← 0 // Inicializa o vetor de pesos para avaliação.
3: repita
4: e ← estime_erro(Q,M, S) // Estima o erro da configuração de pesos.
5: se e < me então
6: Atualize P e me
7: fim se
8: i ← m−1 // A variável i indicará se ainda há mais configurações a testar.
9: repita
10: i ← i−1
11: enquanto [(i ≥ 0) ∧(Q
i
= 0)]
12: se i ≥ 0 então // Ainda há configuração a testar. Gera a próxima configuração.
13: tmp ← Q
m−1
14: Q
m−1
← 0
15: Q
i+1
←tmp+ d
16: Q
i
← Q
i
−d
17: fim se
18: enquanto [(me > 0.0) ∧(i ≥ 0)]
19: retorne P
O Algoritmo 3 enumera todas as C
k
|M|+k−1
combinações possíveis de pesos, seguindo uma
ordem semelhante à lexicográfica. Por exemplo, suponha que existam apenas 3 métricas e que
k = 2. Neste caso, há 6 formas possíveis de combinar as métricas, sendo que em 3 apenas uma
métrica terá 100% do peso e nas demais duas métricas terão 50% do peso cada. O Algoritmo 3
enumeraria os pesos deste exemplo de acordo com a ordem da Figura 2.4.
Figura 2.4: Seqüência de geração dos pesos na heurística criada para treinar o algoritmo NN
com várias métricas.
35
3 Árvores de decisão com características
temporais
Neste capítulo outra técnica de classificação amplamente conhecida, as árvores de decisão,
é apresentada e adaptada a dados temporais. Em relação ao método do vizinho mais próximo,
a classificação por árvores é reconhecida, principalmente, por ser mais flexível a dados hetero-
gêneos, por ser mais rápida durante a fase de consulta e por, em teoria, produzir classificadores
interpretáveis.
A adaptação do algoritmo de construção de árvores apresentada neste capítulo também
é baseada na utilização de métricas de similaridade entre séries temporais. Conforme será
mostrado, o algoritmo permite que características não temporais sejam usadas juntamente com
as séries na construção da árvore e, exceto por considerações de desempenho, os pontos fracos
do método são os mesmos da versão não adaptada.
3.1 Árvores de decisão
Uma árvore de decisão é um classificador formado por testes organizados em uma estrutura
de dados em forma de árvore, na qual cada nó terminal (folha) é associado a uma classe e cada
nó interno (galho) é associado a um teste que dividirá o universode um atributoem subconjuntos
disjuntos. A classificação de exemplos desconhecidos é feita percorrendo a árvore a partir da
raiz, avaliando os atributos do exemplo desconhecido de acordo com os testes dos nós internos,
até que uma folha seja atingida. Ao exemplo desconhecido é dada a classificação da folha
encontrada (DUDA; HART; STORK, 2001, p. 394).
A principal característica que fomenta a popularidade das árvores de decisão é a relativa
simplicidade de interpretação do classificador criado. A partir de uma árvore de decisão, pode-
se criar regras que descrevem o problema unindo os nós que levam até as folhas de mesma
classificação em expressões lógicas, através de disjunções e conjunções. Na prática, as árvores
36
de decisão criadas a partir de problemas reais complexos são também complexas, e as regras
extraídas necessitam de reduções e processamento adicional para interpretação.
Além disso, em comparação a outros algoritmos de classificação mais sofisticados, o trei-
namento de uma árvore de decisão é eficiente e o método não faz nenhuma suposição adicional
sobre os dados do problema. O algoritmo de construção pode lidar tanto com dados contínuos
como discretos, possui adaptações para manipulação de dados com valores ausentes e os testes
dos nós intermediários podem acomodar expressões complexas como, por exemplo, combina-
ções lineares de diversos atributos. Por ser flexível, a inclusão de testes para manipulação de
atributos temporais é simples, conforme apresentado nas próximas seções.
Apesar de muito maleáveis, as árvores de decisão são sabidamente inferiores a outros algo-
ritmos de aprendizado, como as redes neurais artificiais, quando considerada apenas a precisão
do classificador construído. Geurts (2002, p. 5) atribui esta deficiência à alta variância existente
no método de construção da árvore. Ao criar testes que separam os exemplos de treinamento
em conjuntos disjuntos, o método de construção pode prosseguir até que, em cada folha, exis-
tam apenas elementos de mesma classificação. Este método de construção, porém, é instável
em relação aos exemplos do treinamento: pequenas alterações nos exemplos podem levar a
árvores completamente diferentes. Além de decrescer a precisão, tal instabilidade prejudica a
interpretação da árvore, uma vez que não é mais possível confiar plenamente nas regras criadas.
Uma maneira de melhorar a precisão de uma árvore de decisão é simplificar a sua estrutura,
removendonós que prejudiquem a classificação. Tal método, conhecido como poda, idealmente
tem a sua disposição um conjunto de dados independente da amostra de treinamento - para
estimar o erro de cada sub-árvore após a remoção (ou não) de seus filhos - e a árvore obtida
após o processo será, possivelmente, mais precisa que a original (QUINLAN, 1993, p. 40).
Além da poda, métodos que agregam diversas árvores construídas para o mesmo problema
são comumente usados com resultados mais significativos na melhoria da precisão. Tais mé-
todos, porém, implicam em mais custo computacional e menos clareza na interpretação do
problema.
Nas próximas seções serão apresentados alguns algoritmos para construção de árvores de
decisão. Apesar de existirem diversas variações possíveis tanto para construção quanto para
poda ou combinação de árvores, foram implementados apenas alguns dos melhores algoritmos,
de acordo com a avaliação experimental de Geurts (2002). Tal restrição foi imposta porque
o desejado é avaliar somente a adaptação para características temporais do algoritmo e não
variações nas partes comuns dos algoritmos antes e depois da adaptação.
37
3.2 Construção de árvores de decisão
O Algoritmo 4 descreve o método de construção de árvores de decisão usado por Geurts
(2002), que produz somente árvores de decisão binárias. O algoritmo é iniciado com o conjunto
completo de exemplos conhecidos, que é separado em subconjuntos de acordo com uma medida
que qualifica a divisão, até que uma condição de parada seja atingida.
Algoritmo 4 Construção iterativa de uma árvore de decisão binária.
Entrada: S = {(x
1
,
θ
1
),.. ., (x
n
,
θ
n
)}, o conjunto de instâncias de treinamento.
Saída: árvore de decisão a partir de S
1: Crie o nó raiz R
2: R.ls ← S // Conjunto de exemplos do nó raiz
3: L ← {R} // Lista de nós a explorar
4: enquanto L = /0 faça
5: Selecione e remova um nó N de L
6: se nao_expandir(N) então
7: N.tipo ← folha
8: N.
θ
← calcule_
θ
(N)
9: senão
10: N.tipo ← galho
11: Crie o nó N.esquerda
12: Crie o nó N.direita
13: Divida N.ls entre N.esquerda e N.direita de acordo com uma função de divisão
14: L ←L∪N.esquerda∪N.direita
15: fim se
16: fim enquanto
17: retorne R
Duas funções auxiliares do Algoritmo 4 não dependem do tipo dos atributos da base de
dados: a função que verifica se o nó ainda deve ser expandido (linha 6) e a função que atualiza
a classe associada às folhas (linha 8). No primeiro caso, a função permite que a árvore seja
expandida até que todos os elementos das folhas pertençam à mesma classe ou até que todos os
atributos dos exemplos do nó sejam constantes. No segundo caso, a função associa a classe da
maioria dos exemplos à folha em questão.
A função que divide o conjunto de exemplos entre os nós filhos (linha 13) é a que deve
considerar o tipo dos atributos (numérico, simbólico, temporal etc.) durante a construção da
árvore de decisão. A versão original de Geurts (2002, p. 86) está preparada somente para
manipular atributos numéricos e é formada por duas partes principais: uma rotina que gera os
testes para dividir os exemplos e uma rotina que avalia a qualidade da divisão.
A rotina que gera os testes utiliza os exemplos do nó para determinar dois parâmetros: um
atributo de referência a e um valor limiar
ξ
. Os exemplos x
i
são divididos de forma que o
38
primeiro filho conterá os casos em que x
ia
<
ξ
e o segundo filho os casos em que x
ia
≥
ξ
.
Para determinação dos parâmetros, uma busca exaustiva é feita considerando todos os atribu-
tos e, para cada atributo, todos os valores possíveis dos exemplos. O atributo e o valor que
maximizarem a rotina de avaliação são escolhidos como referência para divisão do nó.
Para avaliar a qualidade da divisão, foi utilizado somente o ganho de informação. Quinlan
(1993, p. 22) define o ganho de informação G(S,R) como sendo a redução da entropia das
classes após a divisão dos exemplos do nó. Formalmente, é definido como
G(S, R) = I(S) −
k
∑
i=1
|R
i
|
|S|
×I(R
i
) (3.1)
onde S é o conjunto de instâncias pertencentes ao nó, R = {R
1
,. . .,R
k
} contém os exemplos
pertencentes a cada filho após aplicação do teste de divisão (k = 2 no Algoritmo 4), |R
i
| e |S|
são as cardinalidades dos conjuntos e I(T) é a entropia no conjunto T, definida como
I(T) = −
l
∑
i=1
N
i
|T|
×log
2
N
i
|T|
(3.2)
sendo que l é a quantidade de classes do problema e N
i
é o número de exemplos da classe i no
conjunto T. É interessante observar que o valor de I(T) é máximo quando a razão N
i
/|T| = 1/l
para todas as classes i, e é mínimo quando apenas uma classe está contida em T. Isso faz com
que o ganho de informação seja máximo quando cada conjunto R
i
contiver somente elementos
de mesma classificação. Quinlan (1993, p. 23) define ainda a taxa de ganho, que é a razão entre
o ganho de informação e a entropia dos conjuntos divididos. Tal normalização é introduzida
para penalizar as divisões que gerarem muitos conjuntos contendo poucos exemplos - situação
especialmente desinteressante quando o número de filhos for ilimitado. Dado que o Algoritmo
4 constrói apenas árvores binárias, a normalização torna-se desnecessária.
3.2.1 Tratamento de atributos temporais
Assim como no caso dos atributos numéricos, a função que divide o conjunto de exemplos a
partir de atributos temporais é também formada por duas rotinas: uma que cria os testes e outra
que avalia a divisão. Como no caso de dados numéricos, o ganho de informação é utilizado
como medida de qualidade. Desta forma, a qualidade da divisão gerada por atributos tempo-
rais pode ser diretamente comparada à gerada por atributos de outro tipo qualquer, e árvores
de decisão podem ser construídas a partir de base de dados mistas sem nenhuma adaptação
adicional.
Yamada et al. (2003) constroem um teste para atributos temporais a partir de um exemplo
39
pertencente a lista de casos do nó a ser dividido, chamado de exemplo padrão x
p
. A divisão é
feita com base em uma medida de distância entre duas séries temporais
δ
(y,z), um atributo tem-
poral a e um valor limiar
ξ
. Um exemplo x
i
é inserido no primeiro filho do nó se
δ
(x
ia
,x
pa
) <
ξ
e no segundo, caso contrário.
O Algoritmo 5 ilustra o método de busca pelo exemplo padrão x
p
e pelo valor limiar
ξ
em
um atributo temporal. O algoritmo faz busca exaustiva, considerando todos os exemplos como
candidatos a exemplo padrão. O algoritmo deve ser repetido para cada atributo temporal, caso
existam vários na mesma base de dados.
Algoritmo 5 Determina o exemplo padrão e o limiar que maximizam o ganho de informação,
dado um atributo temporal.
Entrada: S = {(x
1
,
θ
1
),.. ., (x
n
,
θ
n
)}, conjunto de instâncias de treinamento do nó;
a, índice do atributo temporal.
Saída: x
p
, o exemplo padrão;
ξ
, o limiar.
1: mg ← −∞ // Melhor ganho de informação
2: md ← −∞ // Maior distância no corte
3: para todo x
j
∈ S faça
4: D ← /0 // Lista pares (exemplo, distância)
5: para todo x
k
∈ S faça
6: D ← D∪(x
k
,
δ
(x
ja
,x
ka
))
7: fim para
8: Ordene D usando a distância como chave
9: para i = 2 até n faça
10: R
1
← D[1...(i−1)] e R
2
← D[i...n]
11: g ← calcule_ganho(S,R) // R = {R
1
,R
2
}
12: d ← (distancia(D[i]) −distancia(D[i−1]))
13: se (g > mg) ∨[(g = mg) ∧(d > md)] então
14: mg ← g, md ← d e x
p
← x
j
15:
ξ
← (distancia(D[i]) +distancia(D[i−1]))/2
16: fim se
17: fim para
18: fim para
19: retorne x
p
e
ξ
Caso mais de um teste seja avaliado com o mesmo ganho de informação, o Algoritmo 5
considera melhor o teste que deixar os exemplos mais distantes das fronteiras das regiões dos
filhos do nó. Assim, o desempate é feito a partir da distância entre o exemplo mais distante
do exemplo padrão inserido no primeiro filho e o exemplo mais próximo do exemplo padrão
inserido no segundo filho (linhas 12 e 13). É importante notar também que o exemplo padrão
não é descartado na divisão, sendo inserido sempre no primeiro filho. Neste caso, o mesmo
exemplo pode ser a referência em mais de um nível da árvore.
40
Em relação à medida de distância do Algoritmo 5, apesar de Yamada et al. (2003) usarem
apenas DTW, qualquer uma das apresentadas no Capítulo 2 pode ser escolhida como métrica
de referência. Os experimentos apresentados no Capítulo 4 mostram que a escolha da métrica
influencia a precisão do classificador em problemas distintos, o que sugere imediatamente que,
ao escolher o atributo e o teste que irá dividir os exemplos em um nó, é importante considerar
várias medidas de similaridade. O Algoritmo 5 pode ser parametrizado para receber também a
métrica de similaridade, e a escolha da melhor métrica é feita diretamente com base no ganho
de informação.
Em relação à complexidade computacional, o Algoritmo 5 é mais ineficiente que o similar
para atributos numéricos. No caso de atributos numéricos, cada valor possível de cada atributo é
considerado um candidato a limiar de corte. Para cada candidato, deve ser computado o ganho
de informação, que é obtido em O(l) (l é o número de classes do problema) se existir uma
tabela com a freqüência de cada classe em cada conjunto da divisão. Tal tabela pode ser criada
em O(n) operações e, para cada candidato, atualizada em tempo constante, se os valores dos
atributos forem ordenados antes da avaliação. Assim, para avaliar n valores candidatos em um
atributo, é necessário ordenar os exemplos (O(n log n)) e, para cada valor, atualizar as tabelas de
freqüências dos nós e calcular o ganho de informação. Assim, supondo que existam m atributos
numéricos, gasta-se tempo O(mn log n) + O(mnl) para descobrir o melhor teste em um nó.
Neste caso, como o número de exemplos é geralmente muito maior do que o número de classes,
o tempo do algoritmo é dominado pelo tempo de ordenação de m vetores de tamanho n.
No caso do Algoritmo 5, também será necessário ordenar vetores de tamanho n (um para
cada atributo temporal, se o problema for multidimensional) e calcular o ganho de informação
para cada corte possível. O tempo do algoritmo, porém, é dominado pela formação dos vetores
de distâncias D, que demandará O(n
2
t
m
) para cada métrica em cada atributo temporal, onde t
m
é o tempo para calcular a distância entre duas séries temporais. Supondo que as séries temporais
sejam longas e que várias métricas estejam sendo avaliadas (algumas com complexidade qua-
drática em relação ao tamanho da série temporal), o tempo para determinação do melhor corte
torna-se excessivo e o treinamento com características temporais será bem mais ineficiente que
o treinamento apenas com características numéricas. Estas considerações de desempenho, po-
rém, não inviabilizam o algoritmo, visto que as exigências de tempo na etapa de treinamento
são menos rígidas e que o classificador produzido é bastante eficiente no momento da consulta.
41
3.3 Poda e combinação de árvores de decisão
O algoritmo de construção de árvores de decisão apresentado na seção anterior segue o
método tradicional, que divide os exemplos até que cada folha seja pura, ou seja, contenha
apenas elementos de mesma classificação
1
. Este procedimento, porém, produz classificadores
que, normalmente, não classificam bem conjuntos de dados independentes, devido ao ajuste
excessivo aos dados de treinamento.
Uma maneira de tentar reduzir o ajuste da árvore aos dados de treinamento é, após construí-
la da forma convencional, podar os nós que não contribuirão para classificar dados independen-
tes. Apesar de existirem diversas formas de poda, apenas a heurística apresentada por Quinlan
(1993, p. 40) foi considerada. A heurística constrói a árvore a partir do conjunto completo
de treinamento, sem reservar dados para a etapa de poda, e elimina uma sub-árvore caso uma
métrica, chamada erro esperado, seja reduzida após a operação.
O erro esperado é calculado a partir dos limites do intervalo de confiança de uma distri-
buição binomial, dados um valor fixo de confiança desejado, o número N de tentativas (total de
elementos pertencentes à sub-árvore) e o número E de sucessos (elementos com classificação
incorreta). O método de poda parte das folhas até a raiz, avaliando o erro esperado de cada
sub-árvore antes e depois da poda e eliminando os ramos nos quais houve redução da métrica.
Apesar de melhorar o desempenho da classificação em alguns casos, os métodos de poda
não são os mais apropriados quando o objetivo é exclusivamente melhorar a precisão da árvore
de decisão. Para este fim, métodos que combinem vários classificadores e decidam (normal-
mente) por voto a classe final dos exemplos desconhecidos são mais recomendados.
Dentre as várias opções possíveis - por exemplo boosting (SCHAPIRE, 1990), random
forests (BREIMAN, 2001) etc., apenas dois algoritmos de combinação de classificadores foram
considerados na análise experimental: o método original de bagging (bootstrap aggregating)
de Breiman (1996), por apresentar bons resultados e ser um dos primeiros propostos para tal
fim; e o algoritmo extra-tree (extremely randomized trees - árvores extremamente aleatórias)
de Geurts, Ernst & Wehenkel (2006), por ser simples, computacionalmente eficiente e produzir
resultados comparáveis aos melhores algoritmos de combinação disponíveis.
O método de bagging procura reduzir a variância de um algoritmo de classificação instável
2
1
É normal, principalmente quando os atributos são simbólicos, que algumas folhas não sejam puras, mas que
não seja possível separar os exemplos, porque todos têm atributos iguais. Neste caso, a folha é associada à classe
da maioria dos exemplos.
2
O algoritmo do vizinho mais próximo não é instável e, por isto, o seu desempenho de classificação, normal-
mente, não é melhorado através da combinação por bagging.
42
criando classificadores distintos a partir de conjuntos diferentes de treinamento e decidindo a
classe dos exemplos desconhecidos através do voto da maioria dos classificadores. Como na
prática, geralmente, não há dados suficientes para criar vários conjuntos aleatórios independen-
tes de treinamento, recorre-se ao processo de amostragem por bootstrap: criam-se T conjuntos
de treinamento selecionando, com reposição, N casos no conjunto de exemplos original. O mé-
todo de bagging usado durante os experimentos apresentados no Capítulo 4 combinam sempre
árvores de decisão construídas de acordo com o algoritmo da seção anterior, sem a etapa de
poda.
Ao contrário do método de bagging, que tenta reduzir a variância do algoritmo de classifi-
cação instável modificando o conjunto de treinamento, o algoritmo extra-tree busca o mesmo
objetivo, porém combinando por voto árvores construídas de forma (extremamente) aleatória.
O algoritmo extra-tree segue o mesmo procedimento do Algoritmo 4, distinguindo-se apenas
pelo processo de seleção do atributo e formação do teste que dividirá os exemplos em cada nó
da árvore.
A versão apresentada em Geurts, Ernst & Wehenkel (2006) está preparada somente para
dados numéricos e escolhe o atributo que formará o teste a partir de um subconjunto de atribu-
tos, selecionado de forma aleatória. Para cada atributo do subconjunto, o limiar que definirá o
corte do teste também é escolhido aleatoriamente. A função que avalia a qualidade dos cortes
é usada apenas para decidir a melhor opção neste subconjunto, evitando que testes comple-
tamente ineficazes sejam criados. Desta forma, o algoritmo extra-tree, assim como a versão
determinística da construção de árvores de decisão, tolera dados com algumas características
inúteis ou redundantes.
Como a seleção dos testes de divisão é aleatória, árvores construídas a partir do mesmo
conjunto de dados serão diferentes e, portanto, não é necessário usar amostras distintas (ou
criadas por bootstrap) para treinamento de cada uma das árvores.
O Algoritmo 6 apresenta um método de construção de árvores extremamente aleatórias
capaz de manipular atributos numéricos e atributos temporais. O algoritmo é uma junção da
versão para atributos numéricos de Geurts, Ernst & Wehenkel (2006) com o Algoritmo 5 de
cortes determinísticos para atributos temporais. No caso dos atributos temporais, somente a
seleção do exemplo de referência em cada nó é feita aleatoriamente. A seleção do valor limiar
é sempre realizada com base no exemplo que divide os casos em dois conjuntos de tamanhos
iguais, após ordená-los de acordo com a distância em relação ao exemplopadrão. Esta heurística
foi adotada para evitar que cortes ineficazes fossem criados (cortes que concentrem os exemplos
apenas em um dos filhos). O algoritmo pode ainda ser estendido para que sejam consideradas
43
várias métricas durante a criação de testes em atributos temporais. Neste caso, após escolher
aleatoriamente o exemplo padrão, é preferida a métrica que maximizar o ganho de informação,
usando sempre a mesma heurística para determinação da distância de corte.
Algoritmo 6 Extra-tree: divide um nó considerando atributos numéricos e temporais.
Entrada: S = {(x
1
,
θ
1
),.. ., (x
n
,
θ
n
)}, conjunto de instâncias de treinamento do nó.
Saída: R
m
, divisão dos exemplos para os nós filhos.
1: mg ← −∞ // Melhor ganho de informação
2: Selecione aleatoriamente K atributos A = {a
i
,a
2
,...,a
k
}
3: para todo a
i
∈ A faça
4: Selecione aleatoriamente um exemplo x
k
5: se a
i
é um atributo numérico então
6: R
1
← {x
j
|x
ja
i
< x
ka
i
} e R
2
← {x
j
|x
ja
i
≥ x
ka
i
}
7: senão // a
i
é um atributo temporal
8: D ← /0 // Lista pares (exemplo, distância)
9: para todo x
j
∈ S faça
10: D ←D∪(x
j
,
δ
(x
ka
i
,x
ja
i
))
11: fim para
12: Ordene D usando a distância como chave
13: R
1
← D[1...(
n
2
−1)] e R
2
← D[
n
2
...n]
14: fim se
15: g ← calcule_ganho(S, R) // R = {R
1
,R
2
}
16: se (g > mg) então
17: mg ← g e R
m
= {R
1
,R
2
}
18: fim se
19: fim para
20: retorne R
m
Em relação à complexidade computacional da criação do corte em um atributo temporal
no Algoritmo 6, a forma aleatória de escolha do exemplo padrão exige apenas uma chamada à
função de distância para cada exemplo em cada atributo avaliado. Como resultado, o tempo total
para construir uma árvore usando este algoritmo é da mesma ordem que o tempo de construção
de uma árvore determinística com características numéricas.
Por fim, é importante ressaltar que o algoritmo de construção e combinação de árvores alea-
tórias contribui apenas para melhoria da precisão do classificador e da eficiência computacional
do método. A facilidade de interpretação atribuída às árvores de decisão, neste caso, é bas-
tante sacrificada. Como o foco da avaliação experimental nos capítulos seguintes é somente a
precisão, nenhuma medida para compensar o dano à interpretação das árvores será avaliada.
44
4 Avaliação experimental
Neste capítulo é feita uma avaliação experimental dos algoritmos apresentados nas seções
anteriores. Inicialmente, o desempenho dos algoritmos de classificação adaptados é comparado
ao das versões originais, tanto no caso do método do vizinho mais próximo, quanto no caso das
árvores de decisão. Após isto, as formas de combinação de diversasmétricas de similaridadesão
avaliadas e comparadas entre si. Nos dois casos, a comparação é feita com base em uma amostra
de problemas exemplos, apresentada a seguir. Por fim, as técnicas são aplicadas ao problema
real de indicação de consumidores suspeitos de fraudes na distribuição de energia elétrica e os
resultados são comparados aos obtidos a partir de bases com características estáticas extraídas
das séries temporais de consumo de energia.
Antes de apresentar os resultados, as próximas seções descrevem os procedimentos segui-
dos durante a experimentação. Em especial, são descritos o método de ajuste dos algoritmos
parametrizáveis e o procedimento empregado para comparação de dois ou mais algoritmos.
4.1 Ajuste de parâmetros e estimativa do erro de classifica-
ção
Os procedimentos de comparação descritos na próxima seção requerem que as médias (e,
em alguns casos, a variância) do erro de classificação dos algoritmos sejam estimadas para cada
problema avaliado. Em situações em que o tamanho da amostra de exemplos conhecidos é
limitado, o procedimento de validação cruzada é o mais empregado para este tipo de estima-
tiva (DIETTERICH, 1998). Para determinar a taxa de erro por validação cruzada, os exemplos
conhecidos são divididos aleatoriamente em k conjuntos disjuntos, e o procedimento de treina-
mento e aferição é repetido durante k rodadas, nas quais o conjunto k é usado para aferição do
erro e os demais para treinamento do algoritmo. A taxa de erro final será a média das obtidas
nas k repetições do experimento.
Nos capítulos 2 e 3 foram apresentadas as técnicas de classificação do vizinho mais próximo
45
e de árvores de decisão. Ambas possuem parâmetros ajustáveis que, possivelmente, alteram a
precisão do classificador. Esta interferência normalmente varia de acordo com o problema,
o que exige uma etapa de ajuste em cada avaliação. No caso das versões conjugadas com
métricas de similaridade, novos parâmetros são introduzidos para configuração das métricas.
Por exemplo, a métrica DTW tem o tamanho da janela como valor a ser ajustado.
A busca pela melhor configuração é um passo a ser realizado na etapa de treinamento do
classificador. Quando o procedimento de validação cruzada é utilizado para estimativa do erro
de classificação, a busca pela melhor configuração deve ser realizada em cada passo da valida-
ção, considerando somente os k −1 conjuntos reservados para o treinamento naquele passo -
considerar todos os dados durante o ajuste dos parâmetros pode subestimar o erro de classifica-
ção.
A busca pela melhor configuração dos parâmetros em uma base de exemplosé normalmente
feita através de alguma heurística, dado que o espaço de soluções possíveis (configurações
válidas dos parâmetros) é extenso e que a aferição do erro para cada configuração (função
objetivo do problema de minimização) pode ser bastante árdua, já que requer o treinamento de
um classificador. Em um ensaio com validação cruzada, a heurística de busca deve ser ainda
mais eficiente, ou o procedimento de estimativa torna-se computacionalmente inviável.
O Algoritmo 7, que segue a estrutura geral do método de avaliação sugerido por Salzberg
(1997), resume o processo de estimativa do erro de classificação implementado, considerando
a etapa de ajuste de parâmetros.
Algoritmo 7 Estimativa do erro de classificação com ajuste de parâmetros.
Entrada: S = {(x
1
,
θ
1
),.. ., (x
n
,
θ
n
)}, conjunto de instâncias de treinamento;
P = {p
1
,p
2
,. . .,p
e
}, os vetores de valores a explorar de cada parâmetro.
Saída: e
m
, o erro médio nas k execuções da validação cruzada.
1: Faça Y ← {Y
1
,Y
2
,...,Y
k
} // Subconjuntos disjuntos e aleatórios de S para validação cruzada
2: para todoY
i
∈Y faça
3: T ←Y −{Y
i
} // Conjunto de treinamento da rodada
4: Faça R ← {R
1
,R
2
,...,R
q
} // Subconjuntos disjuntos e aleatórios de T
5: Determine p
m
, a configuração que minimizou o erro médio de classificação aferido por
validação cruzada em R
6: Treine o classificador configurado por p
m
usando todo o conjunto T
7: Atualize e
m
de acordo com o erro do classificador em Y
i
8: fim para
9: retorne e
m
O método de busca pela melhor configuração (linha 5) recebe como entrada o conjunto de
valores a explorar dos parâmetros e avalia todas as |p
1
|×|p
2
|. . . ×|p
e
| combinações possíveis
destes valores. No caso dos parâmetros numéricos, apenas alguns pontos discretos são passados
46
ao método para avaliação. Este procedimento não atende ao requisito de eficiência, caso o
número de valores possíveis seja alto. Para contornar esta limitação, apenas os parâmetros das
métricas foram ajustados. Tal decisão é aceitável porque o principal objetivo dos experimentos
é verificar a influência da escolha da métrica de similaridade na precisão dos classificadores e
comparar o classificador original ao adaptado. Ao apresentar os resultados, serão descritos os
parâmetros mantidos constantes e os intervalos dos parâmetros das métricas explorados durante
a validação cruzada.
Ainda sobre o Algoritmo 7, em cada rodada da validação cruzada, o conjunto de treina-
mento foi dividido sempre em três subconjuntos disjuntos (q = 3 na linha 4), usados para esti-
mar a qualidade das configurações. A configuração escolhida foi a que minimizou o erro médio
na validação cruzada nestes três subconjuntos. Este pequeno número de divisões na avaliação
também se deve às restrições computacionais impostas pelo ajuste exaustivo adotado.
4.2 Comparação de algoritmos de classificação
Conforme descrito no Capítulo 1, a avaliação experimental apresentada a seguir tem como
objetivos principais: avaliar se as versões dos algoritmos do vizinho mais próximo e árvores
de decisão, combinados com medidas de similaridade, em geral, são mais precisas do que as
versões originais em problemas de classificação com dados temporais; avaliar se a combina-
ção de métricas proporciona algum ganho de precisão relevante; verificar se estas adaptações
são adequadas ao problema especial de classificação de possíveis fraudadores do sistema de
distribuição de energia elétrica.
Embora muito relacionadas, as três avaliações demandam métodos de comparação diferen-
tes. Dietterich (1998) descreve uma hierarquia de questões de natureza estatística encontradas
em trabalhos de aprendizado automático, que podem ser relacionadas às avaliações desejadas.
Nos dois primeiros casos, há um algoritmo base (a versão original) e vários alternativos (as ver-
sões adaptadas com cada uma das métricas). Havendo uma amostra aleatória de problemas de
classificação de domínios que respeitem as restrições enumeradas no Capítulo 1 (ou seja, dados
temporais, unidimensionais etc.), deseja-se saber qual algoritmo, possivelmente, irá produzir o
classificador mais preciso, dado um novo problema qualquer do mesmo tipo. No terceiro caso,
há apenas um problema de classificação e há uma amostra relativamente pequena de dados com
rótulos conhecidos. Deseja-se saber qual dos algoritmos disponíveis produzirá o classificador
mais preciso neste problema selecionado. Por possuir, em princípio, resposta mais simples, a
terceira questão é discutida antes das demais.
47
4.2.1 Comparação de dois classificadores em um mesmo domínio
Para comparar o desempenho de dois classificadores em um mesmo domínio há diversas
alternativas. Provavelmente, o teste mais utilizado em artigos sobre mineração de dados é o
teste-t para dados pareados. Neste teste, o conjunto de dados rotulados é usado para estimar a
média e a variância de uma medida de qualidade dos classificadores. Como não há dados em
abundância, a estimativa é, normalmente, feita por validação cruzada, na qual os subconjuntos
de cada etapa necessariamente devem ser os mesmos para os dois classificadores.
A diferença entre as duas medidas aferidas em cada etapa da validação é calculada e
assume-se que esta diferença seja uma amostra aleatória de uma distribuição normal, com mé-
dia e variância desconhecidas. Chamando estas diferenças de p
i
= p
A
i
− p
B
i
e assumindo ainda
que os dois classificadores são iguais (hipótese nula), a estatística
t
k
=
p
√
k
∑
k
i=1
(p
i
−
p)
2
k−1
, (4.1)
onde k é o número de conjuntos da validação cruzada e p =
1
k
∑
k
1
p
i
, seguirá uma distribuição
t com k−1 graus de liberdade. A hipótese nula é rejeitada se a probabilidade do valor |t
k
| ser
obtido (valor-p) for menor do que um limite
α
% preestabelecido - usa-se com freqüência 5%.
Neste caso, ahipótese alternativa diz que há diferença entre os classificadores, com significância
de
α
% (DEGROOT; SCHERVISH, 2001).
Dietterich (1998) mostra que o teste-t para dados pareados, formulado como na equa-
ção 4.1, possui debilidades que o torna pouco seguro em avaliações de mineração de dados,
especialmente se as medidas de desempenho tiverem sido estimadas por validação cruzada.
Durante a validação, cada par de conjuntos de treinamento compartilha 80% dos exemplos, o
que prejudica a capacidade do teste em estimar a variância causada por diferenças nos dados
do treinamento. Na prática, a estimativa da variância será subestimada e o valor de |t
k
| será
artificialmente grande, fazendo com que a hipótese nula seja mais facilmente rejeitada. Diette-
rich (1998) sugere como alternativas o teste de McNemar, que verifica se a diferença entre os
classificadores é significante contanto o número de acertos e de erros em comum dos métodos,
e uma correção para o teste-t para dados pareados, que ele chama de 5x2cv.
Embora o teste de McNemar seja muito seguro, ele é pouco flexível, pois não permite que
outras métricas de classificação, além da taxa de erro, sejam usadas na comparação. Em relação
à correção do teste-t para dados pareados, Nadeau & Bengio (2003) avaliam algumas possí-
veis alternativas (inclusive o 5x2cv) e sugerem uma correção conservadora para a estimativa da
48
variância, baseada no total de sobreposição entre os conjuntos da validação. Supondo que ape-
nas uma validação cruzada seja feita, o teste-t corrigido para dados pareados é definido pela
seguinte equação:
t
c
=
p
1
k
+
1
k−1
σ
2
, (4.2)
onde k é o número de conjuntos da validaçãocruzada e
σ
2
=
∑
k
i=1
(p
i
−
p)
2
k−1
. Como no caso anterior,
t
c
segue uma distribuição t com k−1 graus de liberdade e, em relação à equação 4.1, o valor de
t
c
é menos sensível ao valor de k. O procedimento para rejeição da hipótese nula é análogo ao
da formulação anterior.
4.2.2 Comparação de vários classificadores em múltiplos domínios
Métodos estatísticos de comparações múltiplas são mais apropriados quando o desejado é
avaliar diversas variáveisaleatórias simultaneamente (no caso o erro médio dos classificadores).
Salzberg (1997) mostra que realizar comparações de todos os algoritmos par a par (por exemplo,
usando o teste-t para dados pareados) e reportar diferenças sem considerar a multiplicidade do
experimento é uma falácia estatística. Mesmo realizando múltiplas comparações, ao reportar
os resultados, espera-se mostrar que existem diferenças entre os algoritmos com significância
de
α
%. Tal nível de significância pode ser interpretado como sendo a probabilidade de uma
amostra de dados aleatória gerar o resultado atual, supondo que os algoritmos classifiquem
igual (hipótese nula). Se o valor
α
for baixo (geralmente menor que 5%), rejeita-se a hipótese
nula. O nível de significância pode ser também interpretado como sendo a probabilidade de
rejeitar a hipótese nula quando ela era verdadeira (ou probabilidade de cometer um erro do Tipo
I). O problema, ao realizar múltiplas comparações individuais, é que o valor da significância
em cada um dos experimentos deve ser ajustado para garantir que o conjunto completo de testes
tenha probabilidade baixa de erro do Tipo I.
Demsar (2006) faz um resumo de métodos estatísticos para comparação de algoritmos em
múltiplos domínios. Neste tipo de comparação, vários problemas são avaliados por todos os
classificadores envolvidos. Demsar (2006) sugere como mais adequados o Teste ANOVA para
medidas repetidas e o similar não-paramétrico Teste de Friedman. Para evitar as suposições do
Teste ANOVA sobre normalidade da distribuição e igualdade de variância das variáveis aleató-
rias, o autor elege o Teste de Friedman como o mais apropriado para a situação. O requisito do
teste é que exista uma amostra aleatória de problemas de classificação. Ao contrário do teste-t,
que requer a estimativa da variância do erro, apenas a estimativa da média do erro é necessária
49
em cada um dos problemas. A fonte de variabilidade, neste caso, é o comportamento do erro
dos classificadores em problemas distintos (e supostamente independentes).
O Teste de Friedman, cuja descrição detalhada pode ser encontrada, por exemplo, em
(SHESKIN, 2000), testa a hipótese nula de que em c ≥ 2 experimentos diferentes e depen-
dentes (também chamados de tratamentos), pelo menos dois representem variáveis aleatórias
com medianas diferentes. No caso da comparação de classificadores, os c tratamentos são evi-
dentemente dependentes, dado que todos os classificadores tiveram a precisão aferida, em cada
um dos problemas, a partir da mesma amostra de dados e ainda a partir da mesma divisão du-
rante a validação cruzada. Para realização do teste, o erro apurado dos classificadores, em cada
problema, é ordenado e recebe um posto, que variará de 1 até c. O melhor algoritmo recebe o
índice 1 e o pior o índice c. Em caso de empates, é atribuída aos classificadores empatados a
média dos postos que estes deveriam receber.
O Teste de Friedman compara o valor médio dos postos obtidos pelos classificadores em
todos os problemas avaliados. Se a hipótese nula for verdadeira e os classificadores forem equi-
valentes, as médias dos postos dos classificadores devem ser iguais. Chamando estas médias
de R
j
, com j = 1, . .., c, o teste mede uma estatística derivada do quadrado dos desvios de R
j
em relação
R (a média esperada, caso a hipótese nula seja verdadeira). Sob estas condições, a
estatística de Friedman, definida como
χ
2
r
=
12N
c(c+ 1)
c
∑
j=1
R
2
j
−
c(c+ 1)
2
4
(4.3)
segue uma distribuição
χ
2
com (c−1) graus de liberdade, se os valores de c e N forem sufici-
entemente grandes - na Equação, N representa o tamanho da amostra que, no caso, é o número
de problemas independentes avaliados. Demsar (2006) sugere N > 10 e c > 5 como uma boa
aproximação. O autor apresenta ainda a seguinte definição, derivada da estatística de Friedman,
para corrigir o excesso de conservadorismo da versão original:
F
r
=
(N −1)
χ
2
r
N(c−1) −
χ
2
r
, (4.4)
onde F
r
segue uma distribuição F com (c−1) e (c−1)(N −1) graus de liberdade.
Se o valor encontrado de F
r
indicar baixa probabilidade do resultado experimental ser ob-
tido, rejeita-se a hipótese nula. A hipótese alternativa é a sua negação, ou seja, o teste indica que
pelo menos um par de classificadores é diferente, de acordo com a significância definida. Neste
caso, inicia-se a segunda parte do teste, para determinar quais são os pares de classificadores
50
diferentes. Para isto, computa-se
z =
(R
i
−R
j
)
c(c+ 1)
6N
(4.5)
para determinar se a diferença entre os classificadores i e j é significante. O valor de |z| é usado
para encontrar a probabilidade do resultado (valor-p) considerando uma distribuição normal.
O valor limite para considerar a diferença significante deve ser, porém, ajustado de acordo
com o número de comparações realizadas. Se todos os c classificadores forem avaliados par a
par, c(c−1)/2 comparações são efetuadas. Quando existe um classificador referência, c −1
comparações são feitas. Dois métodos de ajuste do valor limite foram usados: a Correção de
Bonferroni e o Método de Holm.
A Correção de Bonferroni divide o valor limite pelo número de comparações realizadas
e considera significante apenas as comparações que apresentarem valor-p menor que esta ra-
zão. Por exemplo, caso cinco comparações estejam sendo realizadas e o nível de significância
desejado seja 5%, serão significantes apenas as comparações com valor-p menor que 1%.
Embora bastante segura, a Correção de Bonferroni é muito conservadora, especialmente
quando todos os classificadores são comparados par a par. É normal, nestas situações, que o
Teste de Friedman reporte a existência de diferenças, mas que a segunda etapa, com a Correção
de Bonferroni, não consiga identificá-las. O Método de Holm é menos conservador por ajustar
o valor limite seqüencialmente, de acordo com o número de análises já realizadas. Nesta forma
de ajuste, todas as comparações são feitas e os valores-p encontrados são ordenados. O menor
valor-p é contraposto ao valor limite dividido pelo total de comparações realizadas - por exem-
plo, c−1 se existir um classificador referência. Caso o resultado seja significante, passa-se ao
segundo menor valor-p, que é contraposto ao valor limite dividido pelo total de comparações
menos 1 (c−2 no exemplo anterior). O procedimento continua até que o valor-p não permita
mais rejeitar a hipótese de que o par de classificadores é igual. Todas as demais comparações
(que não foram analisadas) também falham e os classificadores envolvidos são considerados
similares. Tanto o Método de Holm quanto a Correção de Bonferroni podem ser usados em
outros tipos de comparações múltiplas, para correção do nível de significância em repetições
de experimentos em um mesmo conjunto de dados (por exemplo, várias repetições do teste-t
para dados pareados). Combiná-los com o Teste de Friedman, porém, aumenta as chances de
encontrar diferenças nos dados quando elas, de fato, existem.
O ponto mais crítico ao comparar vários classificadores em diversos domínios é o processo
de amostragem. Para que o resultado do Teste de Friedman seja realmente válido, a amostra
de dados do experimento, que neste caso são problemas diferentes de classificação, deve ser
51
necessariamente aleatória. A dificuldade em conseguir tal amostra é evidente. Nas avaliações
apresentadas a seguir, foram usados todos os problemas (vinte) disponíveis no repositório orga-
nizado por Keogh et al. (2006), além de mais dois problemas disponibilizados por Geurts (2002)
e Ligteringen et al. (1997). No caso do repositório de Keogh et al. (2006), mesmo oriundos de
diversos autores, vários problemas são formados por dados sintéticos, provavelmente desenha-
dos para validação de alguma nova técnica de interesse do autor original
1
. Em alguns casos,
os dados, embora reais, são variações de um mesmo problema, pré-processado de maneiras
diferentes.
Além desta falta de aleatoriedade, a comparação que segue está dividida em blocos, cada
um para avaliar a adaptação de um algoritmo diferente (NN, árvore aleatória etc.). Em uma
configuração ideal, cada um destes blocos deveria ser avaliado a partir de uma amostra aleatória
distinta. Dada a limitação do número de problemas disponíveis, isto é evidentemente impossí-
vel. Embora seja possível corrigir os limites de significância (por exemplo, usando o Método
de Holm) levando em conta também esta repetição da amostra em experimentos que, em princí-
pio, não deveriam estar relacionados, a quantidade total de comparações realizadas exigiria um
ajuste muito severo, que ocultaria completamente as possíveis diferenças em cada conjunto de
experimentos.
Este tipo de deficiência em análises experimentais parece ser recorrente em trabalhos da
área de mineração de dados. Prechelt (1996), Salzberg (1997) e, mais recentemente, Keogh
& Kasetty (2003) atestam o quanto a falta de avaliações mais abrangentes e, em muitos casos,
também a ausência de metodologia adequada, comprometem parte dos trabalhos publicados na
área. A avaliação de Demsar (2006), de trabalhos ainda mais recentes, mostra uma boa evolução
em relação aos métodos experimentais que, mesmo assim, ainda podem ser melhorados de
acordo com os procedimentos descritos pelo autor (e aqui adotados). Porém, a deficiência em
relação aos repositórios de dados para experimentação parece não resolvida.
Mesmo com estas restrições, é importante ressaltar que a amostra usada nos experimentos
apresentados a seguir é, possivelmente, a maior e mais completa disponível - especialmente
quando considerados apenas problemas de classificação no formato de interesse. Embora esta
deficiência na amostragem imponha um limite em relação à abrangência das conclusões perante
o universo de problemas de classificação, ela não impede que, no mínimo, fortes indícios sejam
atestados.
1
Não serão descritos os detalhes da preparação de cada uma destas bases. Keogh et al. (2006) listam as publi-
cações nas quais é possível encontrar tais descrições.
52
4.3 Avaliaçãode métricaspara determinaçãodo vizinhomais
próximo
Esta seção descreve os resultados da classificação usando o algoritmo do vizinho mais pró-
ximo com as métricas descritas no Capítulo 2. A Tabela 4.1 lista a média do erro de classificação
em cada um dos 22 problemas disponíveis nos repositórios públicos sobre o assunto. A primeira
coluna contém o nome do problema no repositório
2
. O melhor resultado em cada problema é
escrito em negrito.
Tabela 4.1: Taxa de erro média (percentual) do algoritmo do vizinho mais próximo com métri-
cas diversas.
Euc. Man. Fou. Wav. DTW E.D. LCSS Ham.
50 Words 31,27 27,74 29,95 28,73 20,77 18,90 19,78 30,50
Adiac 32,91 35,59 33,67 34,31 34,19 44,29 44,81 44,04
Beef 40,00 46,67 45,00 45,00 41,67 28,33 28,33 43,33
CBF 1,18 1,83 0,00 0,00 0,11 0,22 0,32 1,72
CBF_tr 2,38 2,58 0,08 0,08 0,10 0,38 0,22 3,10
Coffee 0,00 0,00 0,00 1,82 0,00 0,00 1,82 0,00
ECG200 9,50 6,50 9,00 1,00 10,50 13,50 11,00 12,00
Face/All 5,02 3,82 4,93 4,18 1,64 0,89 1,11 4,31
Face/Four 5,34 2,65 7,95 7,15 5,34 1,78 1,78 2,65
Fish 18,57 20,29 18,57 18,57 15,43 8,86 10,00 19,14
Gun/Point 6,50 4,50 6,50 8,00 2,50 2,00 1,50 3,00
Lighting 2 24,73 19,73 23,93 21,47 13,10 27,20 19,73 25,60
Lighting 7 35,05 29,38 31,55 27,34 23,13 26,58 30,17 36,45
Olive Oil 11,67 11,67 16,67 23,33 10,00 51,67 51,67 51,67
OSU Leaf 34,40 34,16 36,42 37,10 27,36 13,80 16,29 37,56
Pump 0,00 0,00 2,50 0,00 0,00 0,00 0,00 0,00
S. Leaf 18,13 17,24 15,82 16,89 13,07 8,89 9,42 16,00
S. Control 7,83 9,67 0,83 1,00 0,83 4,00 3,17 13,50
Trace 15,00 12,50 15,00 11,50 0,50 5,50 1,00 14,50
Two Pat. 1,52 0,34 0,48 0,72 0,00 0,02 0,02 0,08
Wafer 0,08 0,13 0,15 0,14 0,14 0,13 0,14 0,07
Yoga 6,27 6,39 6,27 6,39 5,12 2,97 3,55 8,55
Todos os resultados foram obtidos por validação cruzada com ajuste de parâmetros como
descrito na Seção 4.1. No caso das bases disponíveis em (KEOGH et al., 2006), o organizador
do repositório disponibiliza os dados separados em dois conjuntos distintos, para treinamento e
teste. Os resultados deste capítulo foram obtidos por validação cruzada no conjunto completo,
aleatoriamente embaralhado. O Apêndice A mostra os resultados com a divisão original, que
2
Todas as bases podem ser encontradas através deste nome em (KEOGH et al., 2006), exceto CBF_tr, encon-
trada em (GEURTS, 2002), e Pump, em (LIGTERINGEN et al., 1997).
53
não alteram as conclusões deste capítulo.
Conforme já mencionado, apenas os parâmetros das métricas foram ajustados. Todos os
resultados foram obtidos com o número de vizinhos (possível parâmetro do classificador) cons-
tante e igual a 1. No caso das métricas, como todos os parâmetros são numéricos e contínuos,
foram definidos os limites de um intervalo e um incremento com os quais foram gerados os
valores discretos avaliados no processo de busca.
A primeira e a segunda métricas da tabela não possuem parâmetros ajustáveis. Tratam-
se da distância Euclidiana (coluna sob o título Euc.) e da distância Manhattan (coluna sob o
título Man.). Para a métrica DTW, o parâmetro existente é o tamanho da janela de ajuste, que
foi avaliado para todos os valores naturais entre 0 e 100 (unidades percentuais em relação ao
tamanho da série).
No caso da distância de edição (coluna sob o título E.D. na Tabela 4.1) e da LCSS, os
parâmetros a ajustar são o tamanho da janela e o limiar
δ
que indica se dois valores representam
o mesmo caractere (usado em substituição ao processo de discretização). Os valores buscados
para a janela de ajuste foram os mesmo usados com DTW. Para
δ
, foram considerados os valores
entre 0,1 e 1,0 com incremento 0,1, sendo que este intervalo foi eficiente porque todos os dados
foram previamente normalizados (para média 0 e desvio padrão 1). Os mesmo valores de
δ
foram avaliados para a distância de Hamming (coluna sob o título Ham.), que possui apenas
este parâmetro a ajustar.
As distâncias calculadas a partir dos primeiros k coeficientes da Transformada de Fourier
(coluna sob o título Fou.) ou das j primeiras resoluções da Transformada Wavelet (coluna sob
o título Wav. na tabela) possuem o número k de coeficientes e o número j de resoluções como
parâmetros, respectivamente. Ambos foram avaliados para todos os valores naturais entre 1 e
100 (unidades percentuais em relação ao total de coeficientes/resoluções).
Sobre os resultados na Tabela 4.1, a primeira constatação é que nenhuma métrica é melhor
em todas as situações. É também importante notar que a melhor métrica foi, em 16 dentre os
22 problemas, ou DTW ou a distância de edição. Além disto, quando comparadas apenas estas
duas medidas, a diferença entre os resultados obtidos em vários problemas é numericamente
bastante relevante. Esta diversidade de resultados era esperada e indica que cada métrica se
adaptou melhor a alguns problemas, possivelmente por suas características individuais, como
correção de defasagens, filtragem de ruídos etc.
A partir desta tabela de resultados, a primeira pergunta a responder é se há alguma evi-
dência de que pelo menos dois classificadores são diferentes - hipótese alternativa do Teste de
54
Friedman. A hipótese nula é que todas as variações são iguais e que os resultados na tabela
são apenas obra do acaso. Para esta tabela de dados, o Teste de Friedman reporta probabilidade
de 0,05% deste resultado ocorrer, supondo que a hipótese nula seja verdadeira - é, portanto,
bastante seguro rejeitá-la.
Neste caso, a questão passa a ser determinar quais classificadores são diferentes entre si.
Apenas 7 comparações foram feitas, sempre contrapondo uma métrica à forma normal do algo-
ritmo (distância Euclidiana). A Tabela 4.2 mostra os valores-p encontrados, ainda sem nenhum
ajuste para comparações múltiplas, e as médias dos postos obtidos pelos classificadores a partir
dos dados da Tabela 4.1. O classificador de referência obteve posto médio de 5,32.
Tabela 4.2: Valores-p e média dos postos da comparação de métricas contra a distância Eucli-
diana. Valores ainda sem o ajuste requerido pela multiplicidade.
Man. Fou. Wav. DTW E.D. LCSS Ham.
Valor-p% 62,2 71,2 55,9 0,1 0,7 2,1 42,4
Média (ref. 5,32)
4,95 5,05 4,89 2,93 3,34 3,61 5.91
Considerando o nível de significância usual de 5% e a Correção de Bonferroni, o resultado
na Tabela 4.2 é significante se o valor for menor que 0,71%. Assim, os resultados com a
distância de edição e DTW podem ser considerados significantes. O resultado com LCSS apenas
fica perto do limite quando analisado com o Método de Holm com nível de significância de
10%, ou seja, é difícil afirmar que a medida é melhor do que a distância Euclidiana, embora
haja algumas evidências. Em relação às demais métricas, não há nenhuma evidência de que elas
sejam mais adequadas a este tipo de problema, embora, em alguns casos, o classificador seja
mais preciso do que o original.
A partir destes resultados, pode-se concluir que é possível obter, em geral, classificadores
melhores variando a métrica do algoritmo. Em especial, as melhores escolhas são a distância
de edição e DTW. Como análise final, a Tabela 4.3 mostra os resultados obtidos através da
combinação de várias métricas, de acordo com o procedimento descrito na Seção 2.3. A tabela
mostra também o melhor resultado de cada linha da Tabela 4.1.
Paragerar os resultados da Tabela 4.3, apenas os pesos das métricas foram variados. Usando
o método de busca do Algoritmo 3, com 8 métricas, pesos variando entre 0 e 1, passo 0,1 e soma
total dos pesos distribuídos entre as métricas sempre igual a 1, foram testadas aproximadamente
20.000 configurações distintas de pesos em cada problema. Como seria claramente inviável
testar todas as combinações possíveis de parâmetros das métricas para cada configuração de
pesos, foi usado um ajuste fixo em cada problema. O ajuste escolhido foi um dos 10 obtidos
durante a validação cruzada do experimento anterior - em geral, a configuração das métricas foi
55
Tabela 4.3: Vizinho mais próximo com combinação de métricas e melhor resultado individual.
Taxa de erro média (percentual).
Combinação Individual Combinação Individual
50 Words 18,56 18,90 Lighting 2 14,00 13,10
Adiac 35,98 32,91 Lighting 7 25,99 23,13
Beef 30,00 28,33 Olive Oil 13,33 10,00
CBF 0,00 0,00 OSU Leaf 14,02 13,80
CBF_tr 0,08 0,08 Pump 0,00 0,00
Coffee 0,00 0,00 S. Leaf 9,60 8,89
ECG200 1,00 1,00 S. Control 1,17 0,83
Face/All 1,02 0,89 Trace 0,50 0,50
Face/Four 2,65 1,78 Two Pat. 0,00 0,00
Fish 11,43 8,86 Wafer 0,07 0,07
Gun/Point 5,00 1,50 Yoga 3,30 2,97
bastante estável nos passos da validação cruzada em um mesmo problema.
Os resultados da Tabela 4.3 mostram que o procedimento não foi bem sucedido. Em apenas
1 problema foi obtido resultado melhor do que o anterior. Em 8 problemas o resultado foi
exatamente o mesmo: a configuração de pesos escolhida, nestes casos, marcou peso máximo
para a melhor métrica individual e peso zero para todas as demais.
Nos 13 problemas em que o resultado foi inferior houve distribuiçãode pesos entre algumas
métricas. Portanto, no conjunto de treinamento de cada passo da validação cruzada, a distribui-
ção de pesos parecia ser mais precisa do que a opção (também avaliada) de apenas uma métrica
com peso máximo. Isso sugere que, além da provável influência negativa da falta de ajuste
dos parâmetros das métricas, a suposta melhoria no conjunto de treinamento era causada por
super-ajuste aos dados.
Além destas duas possíveis explicações, é ainda bastante seguro supor que combinar estas
medidas de similaridade não gera resultados melhores porque elas são fortemente correlacio-
nadas. Em alguns casos, tal correlação é evidente: DTW e a distância dos k coeficientes de
Fourier, por exemplo, podem ser configuradas para retornar exatamente o mesmo valor que a
distância Euclidiana. Em alguns problemas, filtrar os ruídos, como faz a distância dos k coefici-
entes de Fourier, pode ser mais vantajoso. Em outros, remover as distorções no eixo do tempo,
como faz DTW, é mais adequado. É difícil, porém, imaginar que exista muita informação extra
na distância original (Euclidiana), após verificar que tais transformações eram mais vantajosas.
Após estes experimentos, o procedimento que parece ser mais adequado para utilização
do classificador do vizinho mais próximo em problemas temporais é realizar um treinamento
com cada uma das métricas isoladamente e escolher a que minimizou o erro no conjunto de
56
treinamento. Se há alguma restrição em experimentar todas as métricas, a escolha mais acertada
é optar ou por DTW ou pela distância de edição. Nos dois casos, é necessária uma etapa de
ajuste de parâmetros, dado que eles influenciam decisivamente na precisão do classificador.
4.4 Árvore aleatória com adaptação para dados temporais
Nesta seção é feita uma avaliação da influência da escolha da métrica na construção de ár-
vores de decisão aleatórias. Assim como no caso da avaliação do algoritmo do vizinho mais
próximo, inicialmente serão apresentados os resultados da validação com cada uma das métrica
isoladamente. Após isto, é apresentado o resultado do algoritmo com várias métricas combina-
das. Na próxima seção são apresentados os mesmos resultados, porém para árvores de decisão
convencionais (com poda).
A Tabela 4.4 mostra os resultados do algoritmo nos 22 problemas disponíveis para vali-
dação experimental. Em relação à Tabela 4.1, há uma nova coluna, chamada de “Num.”, que
contém o resultado da avaliação considerando cada valor da variável temporal uma caracte-
rística numérica. Os resultados desta coluna não utilizaram, portanto, nenhuma métrica para
comparação dos exemplos. Esta coluna será a base das comparações que seguem, uma vez que
trata-se da forma convencional do algoritmo.
Os resultados na Tabela 4.4 também foram obtidos por validação cruzada, como descrito na
Seção 4.1. Os resultados foram gerados combinando por voto 50 árvores aleatórias, treinadas
de acordo com o Algoritmo 6. Para os experimentos com métricas de similaridade, como todas
as bases são temporais e unidimensionais, apenas 1 atributo é avaliado em cada nó durante a
construção das árvores. No caso dos experimentos da coluna “Num.”, o Algoritmo 6 tratará
cada valor das séries como uma característica numérica e independente das demais.
O total de árvores participantes da decisão final (50) foi escolhido arbitrariamente e man-
tido fixo durante todos os experimentos. Possivelmente, o número de árvores necessário para
obtenção do mesmo resultado é menor para a maioria dos problemas - Breiman (1996) chega
a uma conclusão semelhante em sua avaliação experimental sobre o procedimento de bagging.
Usar menos árvores é relevante porque reduz o esforço computacional do treinamento (por um
fator proporcional ao número de árvores). Os experimentos, porém, avaliam apenas a precisão,
por isso não vem ao caso determinar o número mínimo de árvores necessárias para produção do
resultado.
Sobre os parâmetros das métricas, nesta avaliação foi feita uma busca pela melhor con-
figuração nos mesmos intervalos (e incrementos) da busca com o algoritmo do vizinho mais
57
Tabela 4.4: Taxa de erro média (percentual) da árvore aleatória com métricas temporais em
diversos problemas de classificação. O melhor desempenho em cada problema é escrito em
negrito.
Num. Euc. Man. Fou. Wav. DTW E.D. LCSS Ham.
50 Words 35,36 32,49 31,93 32,49 30,50 25,08 26,96 23,32 35,47
Adiac 33,29 35,85 39,05 35,85 37,00 32,26 32,65 33,29 39,94
Beef 38,33 36,67 46,67 48,33 38,33 40,00 40,00 35,00 50,00
CBF 1,08 0,32 0,32 0,00 0,00 0,11 0,00 0,00 0,00
CBF_tr 2,78 0,88 0,66 0,14 0,16 0,16 0,20 0,08 0,52
Coffee 1,67 0,00 7,12 0,00 0,00 0,00 0,00 1,82 1,82
ECG200 13,50 11,00 13,00 11,50 1,00 12,00 12,50 10,50 11,50
Face/All 8,71 8,76 7,78 8,04 7,07 2,62 1,29 1,60 9,42
Face/Four 5,42 6,25 8,89 9,80 10,67 7,98 2,69 1,78 5,38
Fish 22,57 19,71 24,57 20,57 19,43 19,43 11,43 13,43 23,14
Gun/Point 2,00 5,00 6,50 7,50 6,50 3,00 1,50 2,00 6,00
Lighting 2 18,90 22,23 22,93 20,60 20,63 13,87 19,70 18,03 22,17
Lighting 7 32,83 30,74 27,24 28,70 32,29 20,32 27,96 27,91 31,53
Olive Oil 8,33 10,00 13,33 10,00 18,33 15,00 63,33 63,33 65,00
OSU Leaf 38,00 37,54 36,86 33,94 38,68 29,17 21,69 20,11 38,22
Pump 7,50 0,00 0,00 2,50 0,00 0,00 0,00 5,00 0,00
S. Leaf 12,36 15,11 14,31 13,87 15,20 11,38 9,24 8,71 13,51
S. Control 4,17 2,83 2,83 0,83 0,67 0,83 1,83 1,67 3,83
Trace 14,50 7,50 12,00 8,50 8,50 0,50 5,50 4,00 12,00
Two Pat. 17,28 3,10 1,16 1,56 1,92 0,00 0,10 0,00 0,48
Wafer 0,21 0,17 0,17 0,20 0,21 0,21 0,13 0,15 0,13
Yoga 6,46 7,76 8,42 7,67 7,61 6,73 4,27 4,91 9,67
próximo.
Os resultados da Tabela 4.4 mostram que não há uma melhor escolha para todos os pro-
blemas, também no caso das árvores aleatórias. DTW, distância de edição e LCSS apresentam
o melhor resultado em 19 dos 22 problemas. As diferenças entre as medidas em um mesmo
problema, novamente, variam bastante e, na maioria dos casos, é numericamente relevante.
Para determinar se há alguma evidência de que pelo menos dois classificadores nesta tabela
são diferentes, foi aplicado o Teste de Friedman. A hipótese nula de que todos os classificadores
são iguais pode ser rejeitada com segurança, dado que o teste reporta que a probabilidade do
resultado ocorrer, supondo que a hipótese nula seja verdade, é menor que 0,001%.
A Tabela 4.5 mostra os valores-p encontrados nas 8 comparações, que contrapõem as adap-
tações com métricas de similaridade à versão original, que supõe características numéricas. Na
tabela é mostrada também a média dos postos obtida por cada classificador. O classificador de
referência obteve posto médio igual a 6,34.
58
Tabela 4.5: Valores-p e média dos postos da comparação entre a adaptação com métricas e a
versão original da árvore extremamente aleatória. Valores ainda sem o ajuste requerido pela
multiplicidade.
Euc. Man. Fou. Wav. DTW E.D. LCSS Ham.
Valor-p% 34,9 89,1 21,5 21,5 0,1 0,0 0,0 82,6
Média (ref. 6,34) 5,57 6,45 5,32 5,32 3,50 3,18 2,80 6,52
Considerando o nível de significância de 5% e a Correção de Bonferroni, os resultados
da Tabela 4.5 são significantes se o valor for menor que 0,625%. Desta forma, neste tipo de
problema, é possível afirmar que a árvore aleatória adaptada com as métricas DTW, distância de
edição e LCSS é melhor do que a versão original do algoritmo. Não é possível dizer o mesmo
das demais métricas, dado que nenhuma é significante, mesmo se a análise fosse feita pelo
Método de Holm com nível de significância relaxado.
Os resultados confirmam que a adaptação é melhor do que a versão original neste tipo de
problema, porém somente para algumas medidas de similaridade. A partir desta conclusão, o
Algoritmo 6 foi executado mais uma vez, porém considerando todas as medidas de similaridade
ao mesmo tempo. Nesta versão, após determinar aleatoriamente o exemplo de referência, é
escolhida a métrica que maximizar o ganho de informação na divisão dos exemplos do nó. Dado
que o número de combinações possíveis de configurações de parâmetros é extremamente alto,
foi usado um ajuste fixo para todas as métricas em cada problema (um dos 10 ajustes produzidos
durante a validação cruzada no experimento anterior). A Tabela 4.6 mostra o melhor resultado
obtido usando apenas uma métrica por vez e o resultado da combinação de todas as medidas de
similaridade.
Tabela 4.6: Combinação de métricas e melhor resultado individual da árvore de decisão aleató-
ria adaptada. Taxa de erro média (percentual).
Combinação Individual Combinação Individual
50 Words 21,33 23,32 Lighting 2 17,17 13,87
Adiac 29,32 32,26 Lighting 7 18,87 20,32
Beef 43,33 35,00 Olive Oil 18,33 10,00
CBF 0,00 0,00 OSU Leaf 21,02 20,11
CBF_tr 0,12 0,08 Pump 0,00 0,00
Coffee 0,00 0,00 S. Leaf 8,36 8,71
ECG200 0,50 1,00 S. Control 0,50 0,67
Face/All 1,78 1,29 Trace 0,50 0,50
Face/Four 2,69 1,78 Two Pat. 0,02 0,00
Fish 12,86 11,43 Wafer 0,13 0,13
Gun/Point 2,50 1,50 Yoga 5,27 4,27
O resultado da Tabela 4.6 mostra que, ao combinar as métricas, em 6 problemas houve
59
melhoria, em 11 o resultado foi inferior e em 5 foi exatamente o mesmo que o melhor re-
sultado individual. É provável que, se fosse viável realizar o mesmo ajuste de parâmetros na
versão combinada, os resultados seriam mais próximos da melhor métrica individual. O custo
computacional do ajuste dos parâmetros de várias métricas (em conjunto) inviabiliza a solução
combinada.
A conclusão final é que o mais adequado parece ser escolher, usando o conjunto de trei-
namento, apenas a melhor métrica individual. Para cada métrica disponível, é necessária uma
etapa de ajuste dos parâmetros. Se não é possível avaliar um grande número de métricas, as
melhores escolhas são LCSS, DTW e a distância de edição. Os resultados podem ser também
comparados ao melhor resultado do algoritmo do vizinho mais próximo, mas antes disto serão
apresentados os resultados da árvore de decisão convencional.
4.5 Árvore de decisão convencional com adaptação para da-
dos temporais
Nesta seção são apresentados alguns resultados usando a árvore de decisão com o teste
de divisão especial para tratamento de atributos temporais, descritos nos algoritmos 4 e 5. Os
resultados a seguir foram gerados de forma semelhante aos das seções anteriores, porém há uma
diferença relevante: nos experimentos anteriores, foi possível realizar um ajuste de parâmetros
detalhado, dado que os algoritmos eram eficientes. O teste de divisão do Algoritmo 5 é bastante
ineficiente o que inviabiliza o ajuste na forma como ele foi concebido.
Yamada et al. (2003), autores originais do teste do Algoritmo 5, em sua avaliação experi-
mental, utilizam somente uma métrica (DTW) e uma configuração de parâmetros fixa em todos
os problemas avaliados. Os resultados da Tabela 4.7 foram obtidos de forma semelhante, po-
rém, para cada problema, uma configuração diferente foi gerada. O ajuste escolhido para cada
problema foi o melhor obtido em uma das execuções da validação cruzada dos experimentos
com a árvore aleatória (o mesmo que gerou os resultados da Tabela 4.6).
Na Tabela 4.7, a coluna “Num.” contém o resultado da validação com a árvore extrema-
mente aleatória sem nenhuma adaptação temporal. Mesmo sem o auxílio de nenhuma ferra-
menta estatística, é fácil notar que a árvore com adaptação temporal classifica pior do que a
árvore aleatória convencional. Em apenas 6 problemas uma das várias adaptações consegue
taxa de erro menor do que a versão original. Considerando o procedimento de comparação das
seções anteriores, todas as métricas são consideradas estatisticamente diferentes do algoritmo
de referência pelo Método de Holm com 5% de significância (pela Correção de Bonferroni,
60
Tabela 4.7: Taxa de erro média (percentual) da árvore de decisão (podada) com métricas tem-
porais. O melhor desempenho em cada problema é escrito em negrito.
Num. Euc. Man. Fou. Wav. DTW E.D. LCSS Ham.
50 Words 35,36 56,35 57,68 58,79 56,91 50,28 54,92 55,91 59,78
Adiac 33,29 56,21 57,10 56,98 57,87 52,61 46,73 48,27 62,09
Beef 38,33 56,67 50,00 56,67 46,67 50,00 53,33 51,67 53,33
CBF 1,08 6,13 3,87 3,33 2,90 5,16 3,76 3,44 2,80
CBF_tr 2,78 21,22 15,08 13,92 12,68 11,56 7,74 6,48 13,88
Coffee 1,67 3,64 1,82 5,30 5,30 10,61 14,39 14,39 14,39
ECG200 13,50 15,50 14,50 16,00 0,50 15,50 18,00 21,00 15,50
Face/All 8,71 38,40 35,47 41,51 34,13 20,27 17,60 20,76 37,82
Face/Four 5,42 30,24 18,70 19,72 16,01 12,41 11,62 21,42 15,18
Fish 22,57 36,86 41,43 36,57 38,57 35,43 29,14 26,29 43,43
Gun/Point 2,00 15,00 12,00 17,00 17,00 9,00 13,50 9,00 20,00
Lighting 2 18,90 26,50 25,53 26,43 28,10 23,80 18,97 24,73 23,03
Lighting 7 32,83 44,75 35,67 42,61 45,39 36,28 33,62 38,50 39,11
Olive Oil 8,33 16,67 18,33 16,67 16,67 25,00 31,67 35,00 33,33
OSU Leaf 38,00 54,52 50,43 53,64 53,83 53,17 35,50 40,24 58,38
Pump 7,50 0,00 0,00 5,00 5,00 0,00 5,00 12,50 5,00
S. Leaf 12,36 31,02 31,82 32,00 31,02 30,93 23,02 24,62 34,84
S. Control 4,17 11,83 11,83 2,50 3,67 5,67 6,83 7,50 12,83
Trace 14,50 23,50 27,00 23,50 25,00 4,00 6,00 10,50 22,50
Two Pat. 17,28 47,82 37,30 43,54 44,90 16,02 16,80 21,32 30,78
Wafer 0,21 2,46 1,70 2,11 2,26 1,72 1,48 1,12 1,56
Yoga 6,46 19,85 24,12 20,30 20,55 29,15 19,39 28,33 20,76
somente a distância de edição não é diferente). Dado que a média dos postos das adaptações
é maior do que a média dos postos da referência, todas são piores do que a versão original. A
Tabela 4.8 mostra os valores-p e as médias dos postos obtidos a partir dos resultados da Tabela
4.7. A média dos postos da referência é 1,73 e está escrita na primeira coluna da tabela.
Tabela 4.8: Valores-p e média dos postos da comparação da árvore com adaptação temporal
contra a versão não adaptada da árvore extremamente aleatória.
Euc. Man. Fou. Wav. DTW E.D. LCSS Ham.
Valor-p% 0,0 0,0 0,0 0,0 0,4 1,5 0,0 0,0
Média (ref. 1,73)
6,50 5,59 6,16 5,64 4,14 3,73 4,98 6,50
Estes resultados indicam que a árvore adaptada não é uma boa escolha para este tipo de
problema. Yamada et al. (2003) reportam bons resultados, inclusive em comparações com o
algoritmo do vizinho mais próximo. Os experimentos deles, porém, são feitos em menos pro-
blemas e todos multidimensionais. Dado que os problemas aqui avaliados são, em princípio,
mais simples (por serem unidimensionais), não é prudente dizer que a adaptação não tem utili-
dade em nenhuma situação. É certo, porém, que de todas as alternativas avaliadas esta foi a de
61
pior desempenho.
Uma vez que a construção de apenas uma árvore de decisão adaptada e podada parece
não ser uma boa alternativa, o mesmo procedimento foi experimentado para um comitê de
árvores adaptadas, porém não podadas e combinadas por voto. Neste caso, como o algoritmo
é determinístico, foram feitas amostras por bagging nos conjuntos de treinamento durante a
validação. Como a construção de cada árvore é ineficiente, apenas 15 foram construídas para
composição do comitê. Novamente, não foi feito ajuste de parâmetros e foram utilizadas as
mesmas configurações que produziram a tabela anterior.
A Tabela 4.9 mostra o erro médio obtido em cada problema. A primeira coluna contém,
novamente, o resultado da árvore aleatória sem adaptação temporal.
Tabela 4.9: Taxa de erro média (percentual) da combinação por bagging de árvores de decisão
(sem poda) com métricas temporais. O melhor desempenho em cada problema é escrito em
negrito.
Num. Euc. Man. Fou. Wav. DTW E.D. LCSS Ham.
50 Words 35,36 39,23 37,90 38,34 38,23 28,40 32,49 29,50 40,22
Adiac 33,29 40,98 44,17 40,46 42,25 37,77 34,82 36,36 47,11
Beef 38,33 45,00 46,67 45,00 46,67 48,33 46,67 40,00 46,67
CBF 1,08 1,40 1,08 0,97 0,86 0,86 0,97 0,54 0,75
CBF_tr 2,78 2,34 1,50 1,04 1,10 0,70 0,72 0,60 0,98
Coffee 1,67 3,49 8,94 3,49 3,49 7,12 5,30 3,49 5,30
ECG200 13,50 15,00 14,00 13,00 1,00 15,00 13,50 14,00 15,50
Face/All 8,71 12,98 11,73 12,49 10,40 5,96 3,20 3,91 13,78
Face/Four 5,42 16,96 14,35 14,27 15,14 10,67 5,34 7,98 5,34
Fish 22,57 25,71 31,14 25,71 28,57 23,14 16,86 17,71 26,57
Gun/Point 2,00 11,00 9,50 12,00 12,00 6,00 8,00 4,00 8,00
Lighting 2 18,90 20,60 20,50 20,60 19,67 17,17 21,30 21,30 21,37
Lighting 7 32,83 38,47 30,79 31,48 32,19 25,15 29,36 27,27 32,24
Olive Oil 8,33 16,67 16,67 18,33 23,33 26,67 40,00 46,67 41,67
OSU Leaf 38,00 40,95 41,83 41,85 43,19 35,28 23,74 23,29 43,87
Pump 7,50 0,00 0,00 2,50 7,50 0,00 2,50 7,50 2,50
S. Leaf 12,36 17,51 17,78 18,22 18,22 16,18 11,56 12,27 18,22
S. Control 4,17 5,67 5,67 2,50 1,33 3,67 5,33 4,67 7,17
Trace 14,50 18,50 23,50 16,00 17,50 4,00 4,50 5,00 15,00
Two Pat. 17,28 9,60 3,80 4,74 5,90 0,06 0,30 0,16 1,72
Wafer 0,21 1,19 1,13 0,28 1,03 1,02 0,35 0,88 0,31
Yoga 6,46 9,18 9,24 9,79 9,49 18,00 17,97 17,30 11,52
Os resultados do comitê são visivelmente melhores do que o de uma árvore individual. Na
Tabela 4.9, apenas em sete oportunidades a versão original é melhor do que as adaptações.
Embora o melhor resultado apareça na maior parte dos casos entre as métricas DTW, LCSS e
distância de edição (13 casos dentre os 22), nestesexperimentos não há o mesmo domínio destas
62
métricas, como nos experimentos anteriores. Esta dispersão dos resultados fica ainda mais clara
quando computados os valores-p da comparação de cada métrica contra a versão convencional
da árvore aleatória (o Teste de Friedman reporta probabilidade desprezível do resultado ocorrer,
supondo que todos classificadores são iguais). A Tabela 4.10 mostra os valores-p e a média dos
postos de cada classificador. A média dos postos do classificador de referência, neste caso, é
3,77.
Tabela 4.10: Valores-p e média dos postos da comparação de um comitê de árvores com adapta-
ção temporal (combinadas por bagging) contra a versão não adaptada da árvore extremamente
aleatória.
Euc. Man. Fou. Wav. DTW E.D. LCSS Ham.
Valor-p% 0,2 0,5 8,8 1,5 82,6 84,7 84,7 0,1
Média (ref. 3,77)
6,30 6,07 5,18 5,77 3,95 3,93 3,61 6,41
Os números da Tabela 4.10 mostram que em apenas 1 caso (LCSS) a média dos postos é
melhor do que a média do classificador de referência. Mesmo assim, a diferença não é sig-
nificante. Em vários casos, é possível dizer que o classificador de referência é superior com
significância de 5% (ajustado com o Método de Holm).
Dado que em apenas 7 casos o classificador de referência foi superior, é possível supor que
realizar o treinamento do bagging de versões adaptadas e escolher a métrica com menor erro
no conjunto de treinamento é mais vantajoso do que usar a árvore aleatória original. Porém,
olhando os resultados da adaptação da árvore aleatória (com métricas), e dada a diferença de
desempenho das duas adaptações, fica claro que não vale a pena investir na versão da árvore de
decisão apresentada nesta seção.
4.6 Discussão
Nesta seção é apresentado um resumo dos resultados experimentais das adaptações dos al-
goritmos de classificação. Quatro formas de classificação foram adaptadas por meio de medidas
de similaridade supostamente mais adequadas ao tipo de problema de interesse: o algoritmo do
vizinho mais próximo, o algoritmo de construção de árvore de decisão com poda, a combinação
por bagging de árvores de decisão sem poda e a construção de árvores de decisão aleatórias.
A Tabela 4.11 mostra o melhor resultado obtido por cada forma de classificação em cada pro-
blema, dentre as várias métricas experimentadas. O resumo na tabela não inclui a versão não
adaptada da árvore aleatória.
A primeira constatação é que a adaptação da árvore de decisão podada e a combinação por
bagging destas árvores (sem poda) não produzem bons classificadores. Há alguns outros fatores
63
Tabela 4.11: Resultado da melhor métrica em cada uma das quatro formas de classificação
avaliadas. Melhor resultado de cada problema em negrito.
Árv. Temp. Bag. Árv. Temp. Árv. Aleatória Viz. mais Próx.
50 Words 50,28 28,40 23,32 18,90
Adiac 46,73 34,82 32,26 32,91
Beef 46,67 40,00 35,00 28,33
CBF 2,80 0,54 0,00 0,00
CBF_tr 6,48 0,60 0,08 0,08
Coffee 1,82 3,49 0,00 0,00
ECG200 0,50 1,00 1,00 1,00
Face/All 17,60 3,20 1,29 0,89
Face/Four 11,62 5,34 1,78 1,78
Fish 26,29 16,86 11,43 8,86
Gun/Point 9,00 4,00 1,50 1,50
Lighting 2 18,97 17,17 13,87 13,10
Lighting 7 33,62 25,15 20,32 23,13
Olive Oil 16,67 16,67 10,00 10,00
OSU Leaf 35,50 23,29 20,11 13,80
Pump 0,00 0,00 0,00 0,00
S. Leaf 23,02 11,56 8,71 8,89
S. Control 2,50 1,33 0,67 0,83
Trace 4,00 4,00 0,50 0,50
Two Pat. 16,02 0,06 0,00 0,00
Wafer 1,12 0,28 0,13 0,07
Yoga 19,39 9,18 4,27 2,97
que podem servir de justificativa para utilização destas técnicas, como a suposta facilidade de
interpretação das regras de classificação treinadas, porém, considerando apenas a precisão da
classificação, não há motivos para utilizar estes algoritmos nos problemas avaliados. Contra
estes algoritmos ainda há o fato deles serem os mais ineficientes dentre os experimentados.
A junção da árvore aleatória de Geurts, Ernst & Wehenkel (2006) com um teste para atribu-
tos temporais, baseado no método de divisão de Yamada et al. (2003), mostra-se uma alternativa
relevante. Por exemplo, Xi et al. (2006) afirmam que:
“Se o desejado é um classificador de séries temporais preciso, a combinação do
algoritmo do vizinho mais próximo com DTW é muito difícil de ser batida. [...]
1NN-DTW parece ser a melhor escolha para classificação de séries temporais.” (XI
et al., 2006, tradução nossa).
Se foram contrapostos os resultados da melhor métrica da árvore aleatória (na Tabela 4.11)
e os resultados do algoritmo do vizinho mais próximo com a métrica DTW (na Tabela 4.1), em
64
apenas 2 problemas a combinação 1NN-DTW venceria (e perderia em 15). Fica claro, portanto,
que a árvore aleatória com várias métricas (inclusive DTW) é um forte concorrente, contra a
parceria 1NN-DTW.
Considerando, porém, o melhor resultado do algoritmo do vizinho mais próximo com várias
métricas (Tabela 4.11), não há mais este domínio. Dentre os 22 problemas, em 4 o melhor
resultado foi obtido por uma árvore aleatória, em 8 pelo algoritmo do vizinho mais próximo e
em 10 por ambos. A partir destes resultados, não é possível dizer que um dos dois algoritmos
é absolutamente melhor, mas o vizinho mais próximo classifica pior em menos situações. É
possível, portanto, concluir que o algoritmo do vizinho mais próximo composto com algumas
métricas (em especial, DTW, LCSS e a distância de edição) é realmente muito difícil de ser
batido, mas a árvore aleatória consegue, geralmente, igualar o desempenho.
Dado que os algoritmos produzem resultados semelhantes, uma possível justificativa para
escolher entre eles é o desempenho computacional. A versão ingênua do algoritmo do vizinho
mais próximo usada nos experimentos não realiza nenhuma tarefa de treinamento e faz busca
exaustiva pelo vizinho mais próximo na etapa de consulta. A árvore aleatória implementada
é mais vantajosa, porque realiza um treinamento (eficiente), que acelera também a etapa de
consulta. Não é justo, porém, concluir que a árvore seja a melhor escolha por este motivo, dado
que existem métodos para acelerar o algoritmo do vizinho mais próximo (citados no Capítulo
2), que devem ser considerados em uma comparação justa sobre desempenho.
4.7 Indicação de consumidores de energia elétrica para ins-
peção
O problema de indicação de consumidores de energia elétrica para inspeção surgiu da ne-
cessidade da concessionária do Estado doEspírito Santo de melhorar o processo de identificação
e fiscalização dos consumidores. O principal objetivo é diminuir os prejuízos financeiros com
o desvio irregular da energia distribuída e diminuir os gastos no processo de inspeção de con-
sumidores, que hoje é feito sem apoio computacional suficiente para otimização da escolha dos
clientes que devem ser submetidos a estas inspeções.
O combate ao desvio irregular de energia é majoritariamente feito através de inspeções em
regiões geográficas onde é detectado alto índice de perdas na comercialização da energia. Assim
que uma região é eleita para ser inspecionada, todas as unidadesconsumidorassão visitadas para
verificação de anomalias nas ligações elétricas. Este procedimento de inspeção é caro e pouco
eficiente porque visita diversas unidades sem evidências de desvio.
65
O objetivo da concessionária de energia elétrica ao estudar técnicas de classificação é me-
lhorar o processo de seleção de unidades consumidoras para inspeção, aumentando a probabi-
lidade da descoberta de irregularidades. Para isto, a concessionária tem disponível informações
dos clientes armazenadas em bancos de dados, que foram disponibilizadas para tarefas de mi-
neração. Estes dados já têm sido usados no treinamento de classificadores e indicação de casos
para inspeções em campo, conforme descrito em Cometti & Varejao (2005). Até então, as in-
formações mais relevantes para a criação dos classificadores têm sido extraídas do histórico
de consumo mensal de energia dos consumidores e do histórico de inspeções realizadas pela
concessionária.
Os dados das inspeções são compostos pela data da última visita e pelo resultado obtido.
Os resultados possíveis são agrupados em duas categorias: fraude ou normal. Os dados de
consumo são representados pelo mês e ano da medição e pelo valor apurado do consumo. A
partir destas informações, bases de dados com exemplos de consumidores inspecionados foram
criadas, contendo como características os valores dos últimos 24 meses de consumo antes da
última inspeção e o resultado obtido (a classe que se deseja inferir). O problema, assim es-
crito, torna-se um caso de classificação de séries temporais e os algoritmos apresentados neste
trabalho podem ser apropriados, se houver padrões a inferir a partir destas séries.
O objetivo principal dos experimentos desta seção é aplicar os métodos de classificação
avaliados nas seções anteriores e comparar o resultado aos obtidos com a estratégia convenci-
onal de extração (e seleção) de características estáticas descrita em Cometti & Varejao (2005).
A comparação apresentada a seguir irá contrapor os algoritmos das seções anteriores, treinados
usando apenas a série temporal do consumo de energia, contra os mesmo algoritmos, treinados
a partir de informações estáticas triviais, extraídas das séries. Deseja-se saber se estas técnicas,
focadas na seleção de protótipos e na forma das curvas, se ajustam melhor ao problema. Além
disso, uma rede bayesiana, disponível no sistema Weka de Witten & Frank (2005) e treinada
com a configuração padrão do sistema, foi usada como medida de referência para avaliar a
relevância dos resultados.
Para realização dos experimentos foi criada uma única base de dados, formada por um
único atributo temporal - a série dos valores do consumo mensal de energia nos últimos 2 anos
antes da inspeção - de um conjunto de consumidores inspecionados recentemente em regiões
da periferia da Grande Vitória. No total, a base de dados contém 3.385 exemplos, sendo que
cada exemplo está marcado como Fraude ou Normal. A probabilidade a priori da classe mais
relevante (fraude) é de aproximadamente 16,5%.
Dado o desequilíbrio entre as classes e a maior importância da classe menos freqüente,
66
outras medidas são mais adequadas do que a taxa de erro para avaliar o desempenho dos classi-
ficadores. Por exemplo, as medidas de desempenho por classe, derivadas da matriz de confusão
(MONARD; BARANAUSKAS, 2002), podem ser combinadas para formação de uma métrica
que avalie a capacidade do classificador em relação à classe menos freqüente.
As medidas - precisão, que representa o percentual corretamente classificado dentre os
elementos apontados como sendo da classe de interesse; e especificidade, que representa o
percentual dos elementos da classe de interesse que foram corretamente classificados - são
independentes e o desejado é que as duas sejam maximizadas simultaneamente. A função de
mérito, neste caso, deve preferir classificadores que equilibrem o valor das duas medidas. Para
esta tarefa, Rijsbergen (1979) sugere uma função, normalmente conhecida como F-measure,
que combina duas grandezas através da seguinte relação:
F(E
i
,P
i
) =
P
i
E
i
(1−
α
)P
i
+
α
E
i
0 ≤
α
≤ 1, (4.6)
onde E
i
representa a especificidade e P
i
a precisão da classe i. O valor
α
é um fator para
ponderar as duas grandezas e dar maior importância a uma delas, de acordo com a necessidade.
Para os casos em que
α
= 0.5, a F-measure é igual à média harmônica entre a precisão e a
especificidade. Nas avaliações a seguir, o valor
α
foi configurado para 0.7, fazendo com que a
precisão tenha contribuição um pouco maior para a métrica.
Para formação da base de dados com características estáticas, foram extraídas das séries as
seguintes informações: média, desvio padrão, curtose, assimetria, maior diferença de consumo
entre dois meses consecutivos (percentual e absoluta), menor diferença de consumo entre dois
meses consecutivos (percentual e absoluta). Além disso, os três últimos valores do consumo
antes da inspeção foram incluídos na base e utilizados como características numéricas (não
temporais). Todos os resultados apresentados a seguir foram obtidos por validação cruzada
(com 10 conjuntos)e os parâmetros das métricasforam ajustados de acordo com o procedimento
descrito na Seção 4.1.
A Tabela 4.12 mostra a taxa de erro dos classificadores do vizinho mais próximo e árvore
aleatória treinados com as diversas métricas. Neste caso, as séries de consumo foram normali-
zadas para que ficassem com média igual a 0 e desvio padrão 1. O melhor resultado da árvore
aleatória na tabela ilustra o problema com o desbalanceamento das classes: o melhor resultado
foi obtido classificando a maioria dos exemplos na classe mais provável, conforme ficará claro
nas tabelas seguintes.
A Tabela 4.13 mostra os resultados dos mesmos métodos de classificação, porém gerados
com os dados sem normalização. Avaliando somente a taxa de erro não fica clara nenhuma
67
Tabela 4.12: Taxa de erro média (percentual) da árvore aleatória e do algoritmo do vizinho mais
próximo avaliados com os dados normalizados.
Euc. Man. Fou. Wav. DTW E.D. LCSS Ham.
1NN 26,56 26,68 26,88 26,26 26,38 22,96 21,00 23,60
Árv. Aleat.
16,90 16,66 22,07 22,81 17,02 16,95 16,84 16,75
diferença entre as duas tabelas, embora a taxa, na maioria dos casos, seja menor na Tabela
4.13. Nesta tabela também está escrita a taxa de erro dos classificadores treinados somente
com as características extraídas das séries. Como a taxa de erro é uma medida secundária neste
problema com classes desbalanceadas, nenhuma conclusão justa pode ser obtida a partir destes
resultados.
Tabela 4.13: Taxa de erro média (percentual) da árvore aleatória e do algoritmo do vizinho mais
próximo avaliados com os dados não normalizados.
Euc. Man. Fou. Wav. DTW E.D. LCSS Ham. Extração
1NN 23,19 22,78 24,82 24,55 23,25 21,60 21,48 21,48 24,67
Árv. Aleat. 16,87 16,90 20,92 19,38 16,78 16,63 16,69 16,63 17,76
As próximas tabelas listam os valores da F-measure média obtidos pelos classificadores
durante a validação cruzada. Ao contrário da taxa de erro, a F-measure é uma medida a ser
maximizada. Os melhores resultados nas tabelas, portanto, são os que apresentarem maior
valor percentual.
A Tabela 4.14 mostra a F-measure média obtida pelos classificadores com as métricas a
partir dos dados normalizados. Nesta tabela é interessante notar que o problema com a menor
taxa de erro da Tabela 4.12 é um dos piores pela avaliação com a F-measure. Além disto, é
possível concluir que a árvore aleatória classifica muito pior do que o algoritmo do vizinho
mais próximo neste problema.
Tabela 4.14: F-measure média (percentual) da árvore aleatória e do algoritmo do vizinho mais
próximo avaliados com os dados normalizados.
Euc. Man. Fou. Wav. DTW E.D. LCSS Ham.
1NN 23,74 25,43 23,47 23,54 22,69 23,32 24,67 22,82
Árv. Aleat. 13,69 10,20 14,88 18,10 13,69 8,05 11,37 7,10
A Tabela 4.15 mostra os resultados dos mesmos classificadores, obtidos a partir dos dados
sem nenhuma normalização. A tabela mostra também a F-measure dos classificadores treinados
com as características extraídas das séries. No caso da árvore aleatória, o melhor resultado foi
obtido a partir destas características.
Ainda sobre os resultados nas tabelas 4.14 e 4.15, em apenas alguns casos (com a árvore
68
Tabela 4.15: F-measure média (percentual) da árvore aleatória e do algoritmo do vizinho mais
próximo avaliados com os dados não normalizados.
Euc. Man. Fou. Wav. DTW E.D. LCSS Ham. Extração
1NN 24,65 28,63 24,14 25,71 27,62 25,72 25,29 27,59 27,18
Árv. Aleat.
21,25 16,63 18,84 21,07 16,84 1,56 4,36 0,00 21,98
aleatória) o resultado não foi melhor com os dados sem normalização. Isto mostra que há
algum padrão a reconhecer nos dados relacionado ao valor médio e à dispersão do consumo.
Além disto, considerando um método que classifique os exemplos de maneira completamente
aleatória, porém assinalando a classe fraude para 16,5% (probabilidade a priori) dos exemplos,
o valor esperado da F-measure deste classificador seria de aproximadamente 20,65%. Ou seja,
a maior parte dos resultados da árvore aleatória, neste problema, são piores do que os de um
classificador que retira dos dados apenas a informação sobre a probabilidade a priori das classes.
A partir destes resultados, e considerando apenas os dados sem normalização, deseja-se tes-
tar as hipóteses nulas de que os dois resultados obtidos com características extraídas são iguais
aos dois melhores resultados obtidos com métricas de similaridade - distância Manhattan, no
caso do algoritmo do vizinho mais próximo, e distância Euclidiana, no caso da árvore aleatória.
Caso não seja possível rejeitar estas hipóteses, a adaptação não trouxe ganho algum em relação
aos algoritmos originais. Além disto, deseja-se também testar a hipótese nula de que um algo-
ritmo bayesiano classifica da mesma forma que o algoritmo do vizinho mais próximo com a
distância Manhattan, opção que obteve o melhor resultado neste problema.
Para testar as hipóteses foi utilizado o teste-t corrigido para dados pareados. Na primeira
comparação, a média das diferenças entre as F-measures do algoritmo do vizinho mais próximo
com a distância Manhattan e do mesmo algoritmo com as características estáticas é 1,45% e
o desvio padrão 6,49%. A partir destes valores, o teste reporta 63,76% de probabilidade do
resultado experimental acontecer, se a hipótese nula for verdadeira. Portanto, não há evidências
de que exista diferença entre as duas abordagens.
No caso da árvore aleatória, a média das diferenças entre o melhor resultado com métricas
e o resultado com características extraídas é 0,73% e o desvio padrão 11,32%. De acordo com
o teste-t corrigido, há 89,12% de probabilidade deste resultado ocorrer e, também neste caso,
não há evidências de que exista diferença entre as duas abordagens.
O classificador bayesiano do sistema Weka, com as características extraídas, obteve taxa de
erro média de 22,01% e F-measure média de 38,60% com desvio padrão de 3,34%. O valor
é bem maior do que o melhor obtido pelos demais classificadores (28,63%). O teste-t reporta
apenas 0,45% de probabilidade do resultado ocorrer: é bastante seguro rejeitar a hipótese nula
69
(já considerando os ajustes pelas múltiplas comparações) e, portanto, há diferença significante
entre os algoritmos.
As Tabelas 4.16 e 4.17 mostram a matriz de confusão dos dois classificadores da última
comparação. O classificador bayesiano erra 2 casos normais a mais do que o vizinho mais
próximo com a métrica, porém acerta mais 87 casos de fraudadores.
Tabela 4.16: Matriz de confusão do algoritmo do vizinho mais próximo usando a distância
Manhattan.
Predita
N F
Real N 2.392 434
F 401 158
Tabela 4.17: Matriz de confusão do classificador bayesiano com características extraídas.
Predita
N F
Real N 2.390 436
F 314 245
A conclusão final desta seção é que, no problema de seleção de consumidores de energia
elétrica para inspeção, apesar da principal informação disponível (consumo mensal) ser uma
série temporal, não há um padrão forte relacionado à forma desta série e, por isto, os algoritmos
com medidas de similaridade mais adequadas a dados temporais não têm desempenho satisfató-
rio. Apesar das versões com métricas dispensarem o conhecimento requerido para a criação das
características estáticas, somente alguns atributos triviais já bastam para que um classificador
convencional supere desempenho destas versões, neste problema.
70
5 Conclusões
Este trabalho apresentou um estudo experimental de métodos de classificação em problemas
com atributostemporais. Das várias formas possíveis de tratamento deste tipo de atributo, foram
estudados apenas algoritmos de classificação que manipulam diretamente as séries e classificam
com base em medidas de similaridade entre seqüências.
No caso da adaptação do algoritmo do vizinho mais próximo, pelo menos duas medidas
avaliadas (DTW e distância de edição) parecem ser sistematicamente melhores do que a usada
na versão original do algoritmo. As demais medidas não foram consistentemente melhores,
mas em alguns problemas apresentaram bons resultados. A proposta de combinação de várias
métricas neste algoritmo teve resultado inferior ao melhor obtido apenas com uma métrica,
provavelmente porque as medidas são muito correlacionadas e porque houve super-ajuste no
treinamento.
A avaliação das adaptações de árvores de decisão mostrou que apenas uma única árvore (po-
dada) não tem desempenho competitivo. O algoritmo de construção de árvores extremamente
aleatórias, por outro lado, produz classificadores com desempenho comparável ao do algoritmo
do vizinho mais próximo. No caso da árvore aleatória, três métricas (LCSS, DTW e distância
de edição) geraram classificadores consistentemente melhores do que a versão não adaptada
do algoritmo. As demais medidas classificaram melhor apenas em alguns casos isolados. A
combinação de várias métricas na árvore aleatória foi mais bem sucedida do que a combinação
no vizinho mais próximo, mas, mesmo assim, o desempenho foi geralmente inferior ao obtido
pela melhor métrica em cada problema.
Por fim, os testes no problema real de seleção de consumidores de energia elétrica para
inspeção não produziram bons resultados. Isso sugere que não há padrão relacionado ao formato
das séries a descobrir nos dados. Os resultados com características estáticas extraídas das séries,
apesar de melhores, também não foram bons, o que evidencia a dificuldade de produzir bons
classificadores nesse problema.
71
5.1 Trabalhos futuros
A abrangência da avaliação experimental sobre classificação com características temporais
apresentada neste trabalho é visivelmente limitada. Em primeiro lugar, porque apenas alguns
poucos tipos de algoritmos de classificação foram considerados. Além disto, todos foram cons-
truídos a partir da mesma idéia de classificação por comparação com “modelos”, através de
alguma medida de similaridade.
Apesar de várias métricas de similaridade terem sido avaliadas, há um grande número de
medidas propostas que podem, eventualmente,ser melhores do que as estudadas, pelo menos em
alguns problemas específicos. Mesmo que apenas algumas poucas medidas avaliadas durante a
elaboração deste trabalho tenham sido constantemente melhores do que a trivial (Euclidiana), e
apesar da verificação de Keogh & Kasetty (2003) enumerar várias que também não a superam,
há, ainda, outras métricas que merecem análise mais apurada. Por exemplo, tanto Savary (2002)
quanto Antunes & Oliveira (2001) citam formas de criar modelos descritores das séries usando
métodos probabilísticos como Cadeias Ocultas de Markov (HMM - Hidden Markov Models) e
calcular a similaridade entre os exemplos através de distâncias computadas entre os modelos.
Abou-Moustafa, Cheriet & Suen (2004) e Ge & Smyth (2000) implementam classificadores
de séries temporais usando tal abordagem. Dado que a classificação de séries temporais tem
uma relação forte com o problema de reconhecimento de voz, e considerando que este tipo de
classificação é usado em reconhecimento de voz com sucesso (assim como DTW), é possível
que bons classificadores possam ser construídos também com esta abordagem.
Ainda em relação aos algoritmos avaliados, outros métodos, além das árvores de decisão
e do algoritmo do vizinho mais próximo, podem ser apropriados a problemas com dados tem-
porais e também precisam ser considerados. Por exemplo, as Redes Bayesianas Dinâmicas,
descritas por Murphy (2002), que estendem as Redes Bayesianas “convencionais” e englobam
as Cadeias Ocultas de Markov, não foram experimentadas. Alguns autores, como Bahlmann,
Haasdonk & Burkhardt (2002), mostram adaptações de Suport Vector Machines que se utilizam
de medidas como DTW no problema de classificação de caracteres manuscrito que, assim como
reconhecimento de voz, é intimamente ligado ao problema de classificação de séries temporais.
Sobre os algoritmos implementados e avaliados neste trabalho, os resultados obtidos com
a árvore aleatória adaptada e com o algoritmo do vizinho mais próximo com métricas de si-
milaridade foram bastante satisfatórios. Ambos podem ser facilmente estendidos para suportar
atributos temporais multidimensionais. Desta maneira, será possível reproduzir os resultados
experimentaisde Yamada et al. (2003) e verificar se, nesta situação, a árvore de decisão proposta
72
pelos autores é um pouco mais competitiva do que em problemas unidimensionais.
Além disso, os algoritmos implementados foram reconhecidamente bem sucedidos clas-
sificando unicamente através da comparação de exemplos. Embora, exceto no problema de
indicação de consumidores de energia para inspeção, não tenha sido experimentada a estratégia
de extração de características estáticas, é certo que esta estratégia seria bem sucedida, se fosse
possível desenhar características especiais para cada problema. Uma possível linha de pesquisa
é investigar a criação de classificadores que combinem características extraídas das séries com
classificação baseada em exemplos (ou modelos).
A combinação de várias métricas em um mesmo classificador não se mostrou promissora
nos experimentos do Capítulo 4, especialmente no caso do vizinho mais próximo. Se novas
medidas de similaridade forem incluídas ao sistema de classificação, novas avaliações expe-
rimentais deverão ser realizadas. Um método mais eficiente de combinação das métricas é
necessário para que seja possível também ajustar os parâmetros das medidas.
No caso do algoritmo do vizinho mais próximo, ainda será preciso investir em formas de
integração do ajuste de parâmetros e da combinação (ou escolha) de métricas às estruturas
de dados para aceleração do algoritmo. No caso da árvore aleatória, o ajuste de parâmetros
não é problema, dada a eficiência do método de treinamento. É preciso, porém, avaliar outras
heurísticas para escolha das métricas nos nós da árvore, já que a apresentada no Capítulo 3 não
conseguiu repetir o desempenho da melhor métrica individual.
73
Referências Bibliográficas
ABOU-MOUSTAFA, K. T.; CHERIET, M.; SUEN, C. Y. Classification of time-series
data using a generative/discriminative hybrid. In: IWFHR ’04: Proceedings of the Ninth
International Workshop on Frontiers in Handwriting Recognition (IWFHR’04). Washington,
DC, USA: IEEE Computer Society, 2004. p. 51–56. ISBN 0-7695-2187-8.
AGRAWAL, R.; FALOUTSOS, C.; SWAMI, A. Efficient Similarity Search in Sequence
Databases. Proceedings of the 4th International Conference on Foundations of Data
Organization and Algorithms, Chicago, USA, p. 69–84, 1993.
AGRAWAL, R. et al. Fast Similarity Search in the Presence of Noise, Scaling, and Translation
in Time-Series Databases. Proceedings of the 21th International Conference on Very Large
Data Bases, p. 490–501, 1995.
ANTUNES, C. M.; OLIVEIRA, A. L. Temporal Data Mining: An Overview. In: Proceedings
of the Workshop on Temporal Data Mining. San Francisco, EUA: [s.n.], 2001. Knowledge
Discovery and Data Mining (KDD 01).
BAHLMANN, C.; HAASDONK, B.; BURKHARDT, H. On-line handwriting recognition
with support vector machines: A kernel approach. In: IWFHR ’02: Proceedings of the Eighth
International Workshop on Frontiers in Handwriting Recognition (IWFHR’02). Washington,
DC, USA: IEEE Computer Society, 2002. p. 49. ISBN 0-7695-1692-0.
BENTLEY, J. L. Multidimensional binary search trees used for associative searching.
Communications of the ACM, ACM Press, New York, NY, USA, v. 18, n. 9, p. 509–517, 1975.
ISSN 0001-0782.
BOZKAYA, T.; YAZDANI, N.; ÖZSOYOGLU, M. Matching and Indexing Sequences of
Different Lengths. In: CIKM ’97: Proceedings of the sixth international conference on
Information and knowledge management. New York, NY, USA: ACM Press, 1997. p. 128–135.
ISBN 0-89791-970-X.
BREIMAN, L. Bagging Predictors. Machine Learning, Kluwer Academic Publishers,
Hingham, MA, USA, v. 24, n. 2, p. 123–140, 1996. ISSN 0885-6125.
BREIMAN, L. Random forests. Machine Learning, Kluwer Academic Publishers, Hingham,
MA, USA, v. 45, n. 1, p. 5–32, 2001. ISSN 0885-6125.
BREIMAN, L. et al. Classification and Regression Trees. New York, N.Y: Chapman & Hall,
1984. ISBN 0412048418.
CHAN, K. pong; FU, A. W.-C. Efficient time series matching by wavelets. In: ICDE ’99:
Proceedings of the 15th International Conference on Data Engineering. Washington, DC,
USA: IEEE Computer Society, 1999. p. 126. ISBN 0-7695-0071-4.
74
COMETTI, E. S.; VAREJAO, F. M. Melhoramento da identificação de perdas comerciais
através da análise computacional inteligente do perfil de consumo e dos dados cadastrais
de consumidores. Vitória, Brasil, 2005. Relatório final de projeto de P&D ESCELSA/Aneel,
ciclos 2003/2004.
COVER, T.; HART, P. E. Nearest Neighbor Pattern Classification. IEEE Transactions on
Information Theory, v. 13, n. 1, p. 21–27, Jan 1967.
DAUBECHIES, I. Ten Lectures on Wavelets. [S.l.]: SIAM, 1992. (CBMS-NSF Reg. Conf.
Series in Applied Math.).
DEGROOT, M. H.; SCHERVISH, M. J. Probability and statistics. 3nd. ed. [S.l.]: Addison
Wesley, 2001. ISBN 0321240753.
DEMSAR, J. Statistical Comparisons of Classifiers over Multiple Data Sets. Journal of
Machine Learning Research, v. 7, n. 1, p. 1–30, 2006.
DEVIJVER, P. A.; KITTLER, J. Pattern Recognition: A Statistical Approach. London:
Prentice Hall, 1982.
DIETTERICH, T. G. Approximate Statistical Test For Comparing Supervised Classification
Learning Algorithms. Neural Computation, v. 10, n. 7, p. 1895–1923, 1998.
DUDA, R. O.; HART, P. E.; STORK, D. G. Pattern Classification. 2nd. ed. New York: John
Wiley and Sons, 2001.
FREIDMAN, J. H.; BENTLEY, J. L.; FINKEL, R. A. An Algorithm for Finding Best Matches
in Logarithmic Expected Time. ACM Transactions on Mathematical Software (TOMS), ACM
Press, New York, NY, USA, v. 3, n. 3, p. 209–226, 1977. ISSN 0098-3500.
GE, X.; SMYTH, P. Deformable markov model templates for time-series pattern matching.
In: KDD ’00: Proceedings of the sixth ACM SIGKDD international conference on Knowledge
discovery and data mining. New York, NY, USA: ACM Press, 2000. p. 81–90. ISBN
1-58113-233-6.
GEURTS, P. Contributions to decision tree induction: bias/variance tradeoff and time series
classification. Tese (Doutorado) — Department of Electrical Engineering and Computer
Science, University of Liege, Belgium, May 2002.
GEURTS, P.; ERNST, D.; WEHENKEL, L. Extremely randomized trees. Machine Learning,
Kluwer Academic Publishers, Hingham, MA, USA, v. 63, n. 1, p. 3–42, 2006. ISSN
0885-6125.
GUSFIELD, D. Algorithms on strings, trees, and sequences: computer science and
computational biology. New York, NY, USA: Cambridge University Press, 1997. ISBN
0-521-58519-8.
GUTTMAN, A. R-trees: a dynamic index structure for spatial searching. In: SIGMOD ’84:
Proceedings of the 1984 ACM SIGMOD international conference on Management of data.
New York, NY, USA: ACM Press, 1984. p. 47–57. ISBN 0-89791-128-8.
HAMMING, R. W. Error detecting and error correcting codes. Bell System Technical Journal,
v. 29, n. 2, p. 147–160, 1950.
75
HAN, J.; KAMBER, M. Data Mining: Concepts and Techniques. San Francisco, CA, USA:
Morgan Kaufmann Publishers Inc., 2001. ISBN 1558604898.
KEOGH, E.; KASETTY, S. On the Need for Time Series Data Mining Benchmarks: A Survey
and Empirical Demonstration. Data Mining and Knowledge Discovery, Springer, v. 7, n. 4, p.
349–371, 2003.
KEOGH, E.; RATANAMAHATANA, C. A. Exact indexing of dynamic time warping. Knowl.
Inf. Syst., Springer-Verlag New York, Inc., New York, NY, USA, v. 7, n. 3, p. 358–386, 2005.
ISSN 0219-1377.
KEOGH, E. et al. The UCR Time Series Classification/Clustering. 2006.
Http://www.cs.ucr.edu/˜eamonn/time_series_data.
KOHAVI, R.; LANGLEY, P.; YUN, Y. The utility of feature weighting in nearest-neighbor
algorithms. In: 9th European Conference on Machine Learning. Prague, Czech Republic:
Springer-Verlag, 1997.
LEVENSHTEIN, V. I. Binary Codes Capable of Correcting Deletions, Insertions and
Reversals. Soviet Physics Doklady, v. 10, n. 8, p. 707–710, Feb 1966.
LIGTERINGEN, R. et al. Machine diagnostics by neural networks: experimental setup. In:
Proceedings of ASCI97. Heijen, The Netherlands: [s.n.], 1997. p. 185–190.
LIN, J. et al. A symbolic representation of time series, with implications for streaming
algorithms. In: DMKD ’03: Proceedings of the 8th ACM SIGMOD workshop on Research
issues in data mining and knowledge discovery. New York, NY, USA: ACM Press, 2003. p.
2–11.
MONARD, M. C.; BARANAUSKAS, J. A. Conceitos sobre Aprendizado de Máquina. In:
Sistemas Inteligentes. 1. ed. Barueri, SP: Manole, 2002. cap. 04, p. 35–53.
MURPHY, K. P. Dynamic bayesian networks: representation, inference and learning. Tese
(Doutorado) — UC Berkeley, Computer Science Division, Jul 2002. Chair-Stuart Russell.
MöRCHEN, F. Time series feature extraction for data mining using DWT and DFT. [S.l.], 2003.
Technical Report, Department of Mathematics and Computer Science Philipps-University
Marburg.
NADEAU, C.; BENGIO, Y. Inference for the Generalization Error. Machine Learning,
Springer, v. 52, n. 3, p. 239–281, 2003.
NANOPOULOS, A.; ALCOCK, R.; MANOLOPOULOS, Y. Feature-based Classification of
Time-series Data. Nova Science Publishers, Inc., Commack, NY, USA, p. 49–61, 2001.
PRECHELT, L. A study of experimental evaluations of neural network learning algorithms:
Current research practice. Neural Networks, v. 9, n. 3, p. 457–462, Apr 1996.
QUINLAN, J. R. C4.5: programs for machine learning. San Francisco, CA, USA: Morgan
Kaufmann Publishers Inc., 1993. ISBN 1-55860-238-0.
RIJSBERGEN, C. van. Information Retrieve. 2. ed. London: Butterworth, 1979.
76
RODDICK, J. F.; SPILIOPOULOU, M. A survey of temporal knowledge discovery paradigms
and methods. IEEE Transactions on Knowledge and Data Engineering, v. 14, n. 4, p. 750–767,
Jul/Aug 2002.
SAKOE, H.; CHIBA, S. Dynamic Programming Algorithm Optimization for Spoken Word
Recognition. IEEE Transactions on Acoustics, Speech, and Signal Processing, v. 26, n. 1, p.
43–49, Feb 1978.
SALZBERG, S. L. On Comparing Classifiers: Pitfalls to Avoid and a Recommended
Approach. Data Mining and Knowledge Discovery, Kluwer Academic Publishers, Hingham,
MA, USA, v. 1, n. 3, p. 317–328, 1997.
SAVARY, L. Notion of Similarity in (Spatio-)Temporal Data Mining. In: ECAI’02 Workshop
on Knowledge Discovery from (Spatio-)Temporal Data. [S.l.: s.n.], 2002. p. 63–71.
SCHAPIRE, R. E. The Strength of Weak Learnability. Machine Learning, Kluwer Academic
Publishers, Hingham, MA, USA, v. 5, n. 2, p. 197–227, 1990. ISSN 0885-6125.
SHESKIN, D. J. Handbook of Parametric and Nonparametric Statistical Procedures. 2nd. ed.
[S.l.]: Chapman & Hall/CRC, 2000.
STRUZIK, Z. R.; SIEBES, A. The haar wavelet transform in the time series similarity
paradigm. Lecture Notes in Computer Science, v. 1704, p. 12–22, Jan 1999.
THEODORIDIS, S.; KOUTROUMBAS, K. Pattern Recognition. Amsterdam: Else-
vier/Academic Press, 2006. ISBN 0123695317.
UHLMANN, J. K. Satisfying general proximity/similarity queries with metric trees.
Information processing letters, Elsevier Science, v. 40, n. 4, p. 175–179, 1991.
WITTEN, I. H.; FRANK, E. Data Mining: Practical Machine Learning Tools and Techniques.
2nd. ed. [S.l.: s.n.], 2005.
WU, Y.-L.; AGRAWAL, D.; ABBADI, A. E. A comparison of dft and dwt based similarity
search in time-series databases. In: CIKM ’00: Proceedings of the ninth international
conference on Information and knowledge management. New York, NY, USA: ACM Press,
2000. p. 488–495. ISBN 1-58113-320-0.
XI, X. et al. Fast time series classification using numerosity reduction. In: ICML ’06:
Proceedings of the 23rd international conference on Machine learning. New York, NY, USA:
ACM Press, 2006. p. 1033–1040. ISBN 1-59593-383-2.
YAMADA, Y. et al. Decision-tree Induction from Time-series Data Based on a Standard-
example Split Test. In: Proceedings of the 12th International Conference on Machine Learning.
[S.l.: s.n.], 2003. p. 840–847.
YAO, Z.; RUZZO, W. L. A Regression-based K nearest neighbor algorithm for gene function
prediction from heterogeneous data. BMC Bioinformatics, v. 7, n. Suppl 1, p. S11, Mar 2006.
77
APÊNDICE A -- Alguns experimentos adicionais
Neste apêndice são exibidos alguns resultados complementares aos apresentados no Capí-
tulo 4. Os dados de cada problema, disponíveis em (KEOGH et al., 2006), estão divididos em
dois arquivos: um para o treinamento e outro para o teste de validação. Para realizar os experi-
mentos apresentados no Capítulo 4, os dois conjuntos de dados foram fundidos e os exemplos
embaralhados antes da execução da validação cruzada. As tabelas A.1, A.2 e A.3 mostram o
resultado da classificação usando a divisão original dos dados.
Tabela A.1: Taxa de erro do algoritmo do vizinho mais próximo com métricas de similaridade.
Euc. Man. Fou. Wav. DTW E.D. LCSS Ham.
50 Words 36.92 33.19 34.29 34.29 23.52 20.44 18.68 32.53
Adiac 38.88 40.15 40.15 39.64 39.13 49.87 50.38 50.38
Beef 33.33 36.67 33.33 33.33 30.00 26.67 23.33 33.33
CBF 14.78 11.11 3.22 6.78 0.22 3.22 3.11 11.11
Coffee 0.00 3.57 0.00 3.57 0.00 3.57 0.00 3.57
ECG200 12.00 11.00 13.00 2.00 12.00 11.00 10.00 12.00
Face/All 28.64 27.87 28.58 28.05 19.23 19.94 19.88 28.17
Face/Four 21.59 15.91 19.32 6.82 11.36 3.41 6.82 9.09
Fish 21.71 20.57 21.71 21.71 16.57 8.00 7.43 24.00
Gun/Point 8.67 4.67 8.67 10.00 8.67 3.33 2.67 6.00
Lighting 2 24.59 18.03 29.51 19.67 9.84 26.23 21.31 22.95
Lighting 7 42.47 28.77 36.99 35.62 28.77 34.25 34.25 30.14
Olive Oil 13.33 16.67 16.67 16.67 13.33 53.33 53.33 53.33
OSU Leaf 48.35 45.04 48.35 49.59 38.02 23.14 19.42 47.11
S. Leaf 21.12 21.12 18.40 17.76 15.36 9.44 11.04 20.00
S. Control 12.00 12.00 1.00 1.00 1.33 4.00 4.00 17.67
Trace 24.00 24.00 26.00 26.00 1.00 9.00 5.00 24.00
Two Pat. 9.33 3.88 4.60 5.93 0.00 0.00 0.00 1.88
Wafer 0.45 0.47 0.44 0.44 0.41 0.20 0.26 1.01
Yoga 16.97 17.10 17.77 17.43 15.67 13.43 13.93 19.93
Por terem usado validação cruzada ao invés de divisão percentual fixa, os resultados do
Capítulo 4 são uma estimativa mais confiável do erro médio de classificação. Os resultados
78
deste apêndice, porém, podem ser diretamente comparados aos listados no repositório do qual
é possível obter os dados.
A Tabela A.1 mostra o erro obtido no conjunto de validação pelo algoritmo do vizinho
mais próximo com as métricas de similaridade. Os valores das colunas referentes à distância
Euclidiana e à DTW devem coincidir com os reportados por Keogh et al. (2006). Em alguns
casos, há diferenças insignificantes, provavelmente ocasionadas por detalhes da implementação
do ajuste de parâmetros.
As Tabelas A.2 e A.3 mostram os resultados, nos mesmos problemas, da árvore de decisão
aleatória e do bagging de árvores de decisão convencionais adaptadas aos dados temporais. Em
relação aos resultados do Capítulo 4, o erro apurado para as árvores com esta divisão fixa parece
estar ainda mais distante do erro do algoritmo do vizinho mais próximo.
Este comportamento era esperado, especialmente no caso da árvore aleatória - Geurts, Ernst
& Wehenkel (2006) citam que a técnica é mais eficiente para conjuntos maiores porque nestas
situações o viés do procedimento de treinamento é reduzido. Esta é, inclusive, mais uma justifi-
cativa para a utilização do conjunto completo dos dados no treinamento de cada uma das árvores
aleatórias, e não amostras obtidas pelo processo de bagging. A divisão percentual original dos
dados reserva, quase sempre, uma porcentagem menor para o treinamento. Isto faz com que
os resultados das árvores sejam mais afetados do que o resultado do algoritmo do vizinho mais
próximo.
79
Tabela A.2: Taxa de erro da árvore aleatória com métricas temporais.
Euc. Man. Fou. Wav. DTW E.D. LCSS Ham.
50 Words 34.95 34.07 34.51 34.29 27.25 27.91 27.03 34.73
Adiac 40.67 43.48 41.69 40.92 38.88 36.57 35.29 44.25
Beef 53.33 40.00 43.33 46.67 36.67 40.00 36.67 43.33
CBF 7.56 6.11 6.44 7.78 0.44 4.11 6.89 10.78
Coffee 0.00 7.14 3.57 3.57 7.14 0.00 7.14 3.57
ECG200 10.00 14.00 14.00 2.00 12.00 13.00 7.00 17.00
Face/All 30.77 31.42 30.65 31.72 19.11 22.78 19.76 32.13
Face/Four 26.14 29.55 26.14 14.77 18.18 6.82 6.82 22.73
Fish 24.00 31.43 25.71 25.71 24.00 14.86 13.71 22.29
Gun/Point 11.33 11.33 13.33 12.00 3.33 9.33 8.67 22.00
Lighting 2 29.51 22.95 21.31 19.67 14.75 21.31 19.67 22.95
Lighting 7 35.62 31.51 30.14 30.14 21.92 28.77 27.40 34.25
Olive Oil 13.33 20.00 16.67 16.67 20.00 66.67 66.67 66.67
OSU Leaf 48.35 47.93 50.00 47.11 41.32 31.82 27.27 48.35
S. Leaf 16.48 16.00 16.64 16.16 13.28 9.44 9.76 14.56
S. Control 5.33 6.00 0.67 1.00 1.67 3.33 3.00 6.33
Trace 22.00 30.00 21.00 24.00 2.00 14.00 6.00 27.00
Two Pat. 16.30 8.73 10.83 10.98 0.03 1.08 0.28 3.78
Wafer 0.78 0.50 0.55 0.49 0.60 0.36 0.62 0.42
Yoga 17.77 18.80 19.50 18.40 16.77 15.87 16.80 20.83
Tabela A.3: Taxa de erro da combinação por bagging de árvores de decisão (sem poda).
Euc. Man. Fou. Wav. DTW E.D. LCSS Ham.
50 Words 41.10 41.54 42.64 39.56 30.77 35.39 33.19 42.42
Adiac 47.57 45.52 47.06 47.06 39.13 38.62 40.92 49.62
Beef 53.33 50.00 53.33 40.00 46.67 40.00 43.33 40.00
CBF 15.67 12.22 7.67 6.44 9.22 13.56 13.11 13.11
Coffee 10.71 21.43 10.71 10.71 17.86 14.29 10.71 14.29
ECG200 13.00 12.00 13.00 0.00 13.00 14.00 14.00 16.00
Face/All 38.17 38.34 38.82 35.74 26.63 21.83 22.43 38.34
Face/Four 26.14 44.32 38.64 36.36 25.00 10.23 28.41 28.41
Fish 32.00 36.00 32.00 32.00 27.43 15.43 17.71 31.43
Gun/Point 18.67 21.33 19.33 19.33 11.33 15.33 9.33 16.00
Lighting 2 27.87 29.51 22.95 21.31 16.39 22.95 26.23 24.59
Lighting 7 38.36 31.51 36.99 26.03 27.40 32.88 30.14 35.62
Olive Oil 16.67 23.33 13.33 13.33 36.67 33.33 40.00 40.00
OSU Leaf 49.17 48.35 48.35 49.59 49.59 38.84 37.19 52.07
S. Leaf 18.88 23.20 20.00 22.24 19.52 12.64 14.88 20.64
S. Control 10.00 10.00 2.00 2.00 1.67 8.33 6.00 7.67
Trace 33.00 41.00 31.00 35.00 5.00 7.00 18.00 23.00
Two Pat. 27.25 18.45 21.65 23.33 0.83 1.58 1.43 9.53
Wafer 1.62 1.57 0.99 1.09 1.25 1.40 1.06 1.35
Yoga 18.90 21.33 19.03 19.20 19.60 19.83 19.47 24.33
Livros Grátis
( http://www.livrosgratis.com.br )
Milhares de Livros para Download:
Baixar livros de Administração
Baixar livros de Agronomia
Baixar livros de Arquitetura
Baixar livros de Artes
Baixar livros de Astronomia
Baixar livros de Biologia Geral
Baixar livros de Ciência da Computação
Baixar livros de Ciência da Informação
Baixar livros de Ciência Política
Baixar livros de Ciências da Saúde
Baixar livros de Comunicação
Baixar livros do Conselho Nacional de Educação - CNE
Baixar livros de Defesa civil
Baixar livros de Direito
Baixar livros de Direitos humanos
Baixar livros de Economia
Baixar livros de Economia Doméstica
Baixar livros de Educação
Baixar livros de Educação - Trânsito
Baixar livros de Educação Física
Baixar livros de Engenharia Aeroespacial
Baixar livros de Farmácia
Baixar livros de Filosofia
Baixar livros de Física
Baixar livros de Geociências
Baixar livros de Geografia
Baixar livros de História
Baixar livros de Línguas
Baixar livros de Literatura
Baixar livros de Literatura de Cordel
Baixar livros de Literatura Infantil
Baixar livros de Matemática
Baixar livros de Medicina
Baixar livros de Medicina Veterinária
Baixar livros de Meio Ambiente
Baixar livros de Meteorologia
Baixar Monografias e TCC
Baixar livros Multidisciplinar
Baixar livros de Música
Baixar livros de Psicologia
Baixar livros de Química
Baixar livros de Saúde Coletiva
Baixar livros de Serviço Social
Baixar livros de Sociologia
Baixar livros de Teologia
Baixar livros de Trabalho
Baixar livros de Turismo
