PROPOSTA ORIENTADA A REDES DE PETRI PARA REPRESENTAÇÃO DO PODER DE CLASSIFICAÇÃO FLÁVIO HENRIQUE BATISTA DE SOUZA, CARLOS ANDREY MAIA, CRISTIANO LEITE CASTRO, ANTÔNIO P. BRAGA, RODNEY R. SALDANHA 1. Programa de Pós-Graduação em Engenharia Elétrica - Universidade Federal de Minas Gerais - Av. Antônio Carlos 6627, 31270-901, Belo Horizonte, MG, Brasil E-mails: [email protected],[email protected], [email protected], [email protected],[email protected] Abstract This paper presents an alternative method based on Petri nets for calculating the Area Under the ROC Curve (AUC). The proposed method enables a more accurate visualization and an adjustable numerical precision. Experiments with Multi Layer Perceptron Neural Networks applied to a UCI's spam detection database showed that our strategy is promising. We also present ideas to extend our methodology to multiclass problems. Keywords Multi Layer Perceptron; Petri Nets; ROC curve; Area Under the Curve Resumo Este artigo apresenta um método alternativo baseado em redes de Petri para o cálculo da área sob a curva ROC (AUC). O método proposto permite uma visualização mais exata e uma precisão numérica ajustável. Experimentos com Redes Neurais Perceptron Multi Camadas aplicadas ao banco de dados UCI de detecção de spam mostrou que nossa estratégia é promissora. Nós também apresentamos idéias para estender a nossa metodologia para problemas multiclasse. Palavras-chave Multi Layer Perceptron; Redes de Petri; Área Sob a Curva 1 Introdução A Área Abaixo da Curva ROC, do inglês Area Under the Curve (AUC), é uma medida global que representa o poder de classificação de um determinado algoritmo de aprendizagem, independentemente dos custos e/ou desbalanceamento das classes. A metodologia tradicional para o cálculo da AUC, descrita em Fawcett(2006), considera o somatório de áreas trapezoidais obtidas com base nas saídas ordenadas de um classificador para um conjunto de dados. Neste trabalho é proposto um novo método para obtenção da AUC que, em contraste com a metodologia tradicional, possibilita a visualização do processo de construção das subáreas e ajuste da precisão numérica. A estimação da AUC se dá a partir de uma topologia de redes de Petri (rP’s) que simula a variação discreta do limiar de decisão do classificador. Quanto maior o número de módulos adotado nessa estrutura, maior a precisão e, com isso, maior a sensibilidade da estrutura de diferenciar classificadores que produzem curvas ROC semelhantes. Para testar as capacidades do método proposto, uma base de dados real e classificadores baseados em Redes Multi Layer Perceptron (MLP) foram utilizados para obter as matrizes de confusão, que serviram como entrada para as rP´s. O restante do artigo está organizado da seguinte forma: na Seção 2 há uma descrição da curva ROC, AUC e o método tradicional de sua estimação; na Seção 3 é analisada a teoria das redes de Petri; a Seção 4 apresenta a proposta que utiliza as redes de Petri na obtenção da AUC; na Seção 5 são feitos experimentos com seis versões da MLP, que resultaram em testes e discussões com relação à estrutura proposta na Seção 6. Na Seção 7 é feita uma proposta para estudos futuros com relação à classificação de múltiplas classes com rPs e a Seção 8 apresenta as considerações finais. 2 Curva ROC e AUC A curva ROC é uma técnica para visualizar, organizar e selecionar classificadores de acordo com suas performances. A curva ROC tem sido muito utilizada na visualização de comportamento de sistemas de diagnósticos e comparação de algoritmos. Também nota-se grande importância em pesquisas de aprendizado com classes desbalanceadas e sensíveis ao custo (Fawcett,2006;Castro, Braga,2013). Um classificador binário atua na obtenção de um mapeamento dos padrões para uma classe predita. Para a distinção entre a classe atual e a classe predita, Fawcett (2006) utiliza a identificação {Y, N} para as classes preditas como positiva (p) e negativa(n), respectivamente. Dado um classificador agindo sobre um padrão, existem quatro possibilidades de retorno onde, se o padrão é (p) e classificado como (Y), é obtido um Verdadeiro Positivo (TP); se for classificado como (N) é contado como um Falso Negativo (FN). Se o padrão é (n) e classificado como (N), então é obtido um Verdadeiro Negativo (TN); se classificado como (p), é contado como Falso Positivo (FP), como mostra a Figura 1. De acordo com Fawcett (2006), a curva ROC é a demonstração gráfica dos possíveis pontos de operação entre classificadores, dimensionando pontos que remetem a uma apresentação da taxa de TP versus a taxa de FP para cada limiar de decisão. A taxa de TP é normalmente referida como “Sensibilidade” e a taxa de FP é referida como “Especificidade”, como mostra a Figura 2. A curva ROC inicia no ponto (0,0) e utiliza o conceito gerado pela matriz de confusão, onde o limiar da decisão é ajustado como 1 tal que todos os padrões são considerados negativos. Quando o limiar diminui, a sensibilidade aumenta e a especificidade diminui. O processo de obtenção da curva termina quando todos os padrões são classificados como positivos, conduzindo a sensibilidade a 1 e especificidade a 0, o ponto (1,1) do plano ROC (mostrado na Figura 2, onde os marcadores circulares mostram os limiares de decisão com passo de tamanho 0.1)(Woods,Bowye;1997). Uma medida do poder global de classificação, que independe dos custos e do desbalanceamento entre as classes e é dada pela Área Abaixo da Curva ROC (AUC). Uma vez que a AUC é uma parte de uma área quadrada, seu valor sempre estará entre 0 e 1. Fig. 1. Matriz da Confusão A AUC tem uma propriedade estatística importante, pois a AUC de um classificador é equivalente à probabilidade do classificador atribuir maior valor a um padrão positivo aleatoriamente escolhido do que a um negativo aleatoriamente escolhido (Fawcett,2006). Fig. 2. Exemplo de curva ROC Na Figura 3, Fawcett (2006) demonstra uma representação gráfica da AUC de dois classificadores, A e B, onde B mostra uma área superior à de A. O algoritmo tradicional que provê a AUC, utilizando-se dos somatórios das áreas de trapezóides obtidos a partir da ordenação do conjunto de dados em função das saídas de classificador é dado a seguir (Fawcett ,2006): Fig. 3. Representação da AUC Entradas: Seja , o conjunto de exemplos de teste; ( ), a estimativa probabilística do classificador de que o exemplo é positivo; e , o número de exemplos positivos e negativos. Saídas: , a área sob a curva ROC. Condição: > 0 e > 0 ← ordenado em ordem decrescente 1: por 2: ← ←0 3: ← ←0 4: ← 0 5: ← −∞ 6: ← 1 7: while ≤ | | do 8: if ( ) ≠ then 9: , , ) ← + #$%&'() *_%$'%( , 10: ← () 11: ← ← 12: 13: end if 14: if é um exemplo positivo then 15: ← +1 16: else /* i é um exemplo negativo */ 17: ← +1 18: end if 19: ← + 1 20: end while 21: ← + #$%&'() *_%$'%( , , , ) 22: ← /( × ) /* escala de × em unidade quadrada*/ 23: end 1:function #$%&'() *_%$'%(.1, .2, 01, 02) 2: 1%2' ← |.1 − .2| 3: 3' 4ℎ#6 7 ← (01 + 02)/2 4: return: 1%2' × 3' 4ℎ#6 7 5: end function 3 Redes de Petri De acordo com Cassandras(2008), a representação gráfica de uma rede de Petri (rP) consiste num grafo composto por nós ligados por segmentos orientados, denominados arcos (A). Este grafo conta com dois tipos de nós, denominados lugares (P) ( e transições (T). Os lugares (P)) são representados por círculos e as transições (T)) são representadas por barras ou retângulos. Cada arco é dirigido e terminado por uma seta. Os arcos interligam um lugar a uma transição ou uma transição a um lugar. Uma rP é um grafo bipartido e direcionado. O número de lugares e trantra sições é finito e não nulo. Tal estrutura considera a marcação x,, gerando uma quíntupla (P,T,A,w,x). (P,T,A, 4 Proposta A proposta deste trabalho é uma forma de representação discreta da área formada pela AUC. A estrutura básica, desenvolvida com redes de Petri, pode ser trabalhada por módulos. Quanto maior o número de módulos, maior a precisão. Com isso, maior a sensisens bilidade da estrutura de diferenciar classificadores que possuem AUCs muito próximas ou ROCs R semelhantes. As estruturas obedecem ao seguinte conceito: formas geométricas, de fácil interpretação, são gerager das pelos lugares finais que são apresentados no funcionamento da estrutura. Após a obtenção das áreas finais, a média entre elas irá apresentar apresent a capacidade de classificação do algoritmo testado. A estrutura básica é demonstrada na Figura 4. 4 Lugares são seqüenciados de forma a simular um decréscimo de unidades de medida (começando em 10 e terminando em 0). Um lugar , que não está na seqüência cia de decréscimo de 10 a 0, é o que controla a ação de busca, ou seja, enquanto houver fichas nesse lugar específico, haverá decréscimo na seqüência. Fig. 4. Estrutura Básica de análise O funcionamento é estruturado da seguinte forfo ma: o lugar não seqüenciado terá um número de fichas proporcional aos Índices de Verdadeiros PosiPos tivos e Falsos Positivos que o algoritmo de classificlassif cação apresentar. Com isso a seqüência de decréscidecrésc mo irá ser realizada. Ao término dos disparos, é feito um calculo dass áreas, onde seus lados a serem multimult plicados serão o valor final do decréscimo da altura λ (de 10 a 0) e o valor escalar 1. Contudo, em análises, as AUC’s tendem a apreapr sentar valores muito próximos, o que representa um problema de sensibilidade para um método m discreto. Por isso, foi feita uma proposta que considera a adiad ção de módulos. Tais módulos consideram a estrutuestrut ra básica demonstrada na Figura 4 e permite a expanexpa são da arquitetura e maior detalhamento da análise. 5 Experimentos Durante os experimentos, foi utilizada uma base de dados reais. Tais dados foram obtidos através do repositório Irvine Machine Learning Repository, da Universidade da Califórnia. O conjunto de dados foi desenvolvido por Mark Hopkins, Erik Reeber, GeorGeo ge Forman e Jaap Suermondt em conjunto com a Hewlett-Packard Packard e gerado no período entre junho e julho de 1999. O dataset set conta com 58 variáveis: variáveis • 48 são atributos do tipo word_freq_WORD, contínuas e reais {0,…,100}: Corresponde à frefr qüência percentual de palavras dos e-mails e analisados que correspondem ao percentual da incidênincidê cia da palavra WORD, onde é feita a razão entre número de ocorrências da palavra WORD p;<=> e número total de palavras p?<?@A no e-mail analisado. Uma palavra é qualquer string de caractecaract res alfanuméricos éricos limitados por caracteres nãonão alfanuméricos ou um end-of of-string (fim de expressão). Assim,, 48 palavras diferentes foram referenrefe ciadas. • 6 são atributos do tipo char_freq_CHAR, contícont nuas e reais {0,…,100}: freqüência percentual p de caracteres no e-mail , onde é feita a razão entre número de ocorrências de cada CHAR 9BCDE e número total de caracteres 9FGFDH no e-mail analisado; • 1 atributo capital_run_length_average, real e conco tínuo {1,...}: comprimento médio de seqüências ininterruptas de letras as maiúsculas; • 1 atributo capital_run_length_longest, apital_run_length_longest, contínuo contí e inteiro {1,…}: comprimento da maior seqüência ininterrupta de letras maiúsculas; • 1 atributo capital_run_length_total, contínuo e inteiro {1,...}: soma do comprimento das seqüênseqüê cias ininterruptas uptas de letras maiúsculas ou o númenúm ro total de letras maiúsculas no e-mail; e • 1 atributo de classe nominal de spam{0,1}: denota se o e-mail mail foi considerado spam (1) ou não (0). As variáveis de entrada :I das MLPs analisadas foram adequadas à condição de d que n ={1,…,57} seriam para classificação, pois :JK foi considerada a variável y a ser obtida. O dataset conta com 1813 padrões consideradoss spam e 2788 padrões de emails considerados normais. Foram experimentadoss 6 tipos de redes MLPs (Multi Layer Perceptron)) para servir de benchmarbenchma king para a análise das estruturas propostas para qualificação de classificadores: Backpropagation (Padrão, Batch, com Momentum e Weight Decay) (Krogh, Hertz, 1992), Rprop e Quickprop (Parma ( et al.,1999) .Todas as estruturas uras foram implementadas na plataforma R (Bergmeir,, 2014) e contaram com a configuração de testes onde 75% dos padrões utilizautiliz dos para treinamento e 25% para teste; teste 5000 Épocas; 1 camada oculta com 10 neurônios e Taxa de Aprendizado em 0.1. As Figura 5-10 mostram as curvas 0 .2 0 .0 0 .4 0 .2 se n s 0 .6 0 .4 0 .8 se n s 0 .6 1 .0 0.8 1 .0 ROC’s resultantes de cada MLP utilizada durante os experimentos. 0.0 0.2 0.4 0.6 0.8 1.0 0 .0 1 - spec 0.0 0.2 0.4 0.6 0.8 1.0 Fig. 9. ROC - MLP Backpropagation Rprop 1 - spec 0 .4 0 .2 0.2 0 .0 sen s 0 .6 0 .4 se n s 0.8 0 .6 0.8 1.0 1 .0 Fig. 5. ROC - MLP Backpropagation Padrão 0.0 0.0 0.2 0.4 0.6 0.8 1.0 1 - spec 0.0 0.2 0.4 0.6 0.8 1.0 1 - spec Fig. 10. ROC - MLP Backpropagation Qprop Fig. 6. ROC - MLP Backpropagation Batch 0.0 0.2 0 .4 sen s 0 .6 0.8 1.0 6 Resultados 0.0 0.2 0.4 0.6 0.8 1.0 1 - spec 0.0 0.2 0 .4 sen s 0 .6 0.8 1.0 Fig. 7. ROC - MLP Backpropagation Momentum 0.0 0.2 0.4 0.6 0.8 1.0 1 - spec Fig. 8. ROC - MLP Backpropagation Weight Decay Para ilustrar as capacidades do método proposto foram realizados experimentos com os índices de Verdadeiros Positivos e Falsos Positivos apresentados pelos algoritmos de classificação testados na seção anterior. Além disso, uma estrutura de 4 módulos, como mostra a Figura 11, foi implementada para a análise proposta. A flexibilidade, que é uma característica intrínseca das rPs, está presente quando se vê as possibilidades de expansão e retração da estrutura de acordo com a sensibilidade desejada pelo projetista. Com a estrutura de 4 módulos, podem ser visualizadas questões como: o número máximo L(M6N) de fichas centrais L é o número de módulos multiplicados por 10; a seqüência de disparos é realizada de forma que cada módulo apresenta sua análise independente e somente quando o módulo é esgotado há a transferência entre eles, como é mostrado na Figura 12. O valor estimado como o poder de classificação de cada algoritmo é obtido pela expressão (10), onde a área média AP é o somatório das alturas λR que cada módulo apresentar no final da análise, dividido pelo número S de módulos da estrutura multiplicados por 10. U ∑X AP = (10) RZU λR UV.X A Tabela 1 mostra a primeira análise, onde são levantados os índices de VP (Verdadeiros Positivos) e FP (Falsos Positivos) de cada algoritmo testado. Suas ponderações devem ser feitas de acordo com o número máximo L(M6N) de fichas que a estrutura deve aceitar (no caso, 40); o número de L somente considerando o índice (no caso bV ) e a área de classificação média AP . Na Tabela 1 também são demonstrados os valores de AUC obtidos pelo métomét do tradicional. Contudo o número de fichas centrais L que cada algoritmo obtém está de acordo com o poder de classificação que estes apresentam. Observe na Tabela 1 que o método Qprop apresentou menor AUC que o método Batch, contradizendo a estimativa do mém todo tradicional. Isso ocorreu, pois o número de L não ponderou o índice de [ . dependentes do número de módulos empregados na análise, pois quanto maior o número de módulos, mais detalhada é a representação gráfica e a AP obtida. Tabela 1.. Estrutura de 4 – FC com FP MLP Padrão Batch Momentum Weight Decay Rprop Qprop gh ijk gh lm gh lm gh lm gh lm gh lm gh lm VP FP 0,904 36,140 0,911 36,429 0,900 35,991 0,915 36,601 0,906 36,250 0,824 32,969 0,050 2,014 0,065 2,617 0,051 2,022 0,049 1,946 0,058 2,333 0,039 1,565 AUC FC (Trad.) 0,9266 0,9226 0,9246 0,9325 0,9239 0,8925 op 2 0,95 3 0,925 2 0,95 2 0,95 2 0,95 2 0,95 Tabela 2.. Estrutura de 4 e 10 Módulos – FC com Ponderação MLP Fig. 11. Estrutura – 4 Módulos Fig. 12. Estrutura – 4 Módulos – Sequência de disparos Com isso, uma segunda análise foi realizada com uma ponderação, como mostra a equação (11): FC T L M6N VPe^B _`a f (11) ^B _`a " Pode ser observado que, de acordo com a Tabela 2, a estrutura está sensível tanto aos VPs quanto aos FPs (assim como na AUC) e agora está sincronizado com as formas de curvas ROC. Um exemplo é que o Qprop, que demonstrou a pior curva ROC e a menor AUC, agora possui a menor AP . Foram realizados experimentos com uma estruestr tura com 10 módulos e a Tabela 2 mostra os resultaresult dos obtidos. Tal estrutura não somente conseguiu abstrair as diferenças entre os algoritmos analisados, como também conseguiu um grau de sensibilidade muito maior que a de 4 módulos. A nova estrutura conseguiu demonstrar a pior classificação por parte da Qprop e também foi capaz de diferenciar a melhor estrutura (Weight Decay) apesar de uma diferença muito pequena das demais. Outra tra vantagem é que a estrutura proposta consegue maior distinção, em visualização, entre os algoritmos que apresentam uma AUC semelhante,, como pode ser notado nos valores obtidos pelo método tradicional (os valores também se encontram na Tabela 2). 2) Entretanto, são gh ijk gh lm gh nmm gh lm Batch gh nmm gh lm Momentum gh nmm gh lm Weight Decay gh nmm gh lm Rprop gh nmm gh lm Qprop gh nmm Padrão VP FP 36,140 90,351 36,429 91,071 35,991 89,977 36,601 91,503 36,250 90,625 32,969 82,422 2,014 5,036 2,617 6,543 2,022 5,056 1,946 4,864 2,333 5,832 1,565 3,912 AUC FC op (Trad.) 6 0,85 0,9266 15 0,85 6 0,85 0,9226 15 0,85 6 0,85 0,9246 15 0,85 5 0,875 0,9325 13 0,87 6 0,85 0,9239 15 0,85 9 0,775 0,8925 21 0,79 7 Proposta Futura - Análises para classificação de múltiplas classes De acordo com Fawcett (2006), uma situação que possui uma dificuldade a ser considerada é a classificlassif cação com múltiplas classes. A geração da superfície ROC multidimensional envolve a ponderação das saídas do classificador por todas as possíveis combicomb nações de custos entre classes. Esse procedimento possui elevado custo computacional (exponencial), podendo limitar o uso da análise ROC quando o número de classes é muito grande (Landgrebe and Duin, 2008). Uma proposta que pode ser analisada é a obtenobte ção de áreas, formadas pelas rP’s para múltiplas classes. Em primeira instância, pode ser considerada a estrutura mais simples, com m FC(10), como mostra a Figura 13. Nesta estrutura, é possível uma visualizavisualiz ção de todas as classes, contudo, assim como na matriz da confusão, deverão ser considerados os momentos de análise de cada classe individualmente (ex.: no momento que a Classe 1 está sendo analisaanalis da, os pontos FP’s serão em relação às Classes 2 e 3). Essa estrutura consegue demonstrar a relação de pontos VP’s daa Classe 1, que vão decrescendo. À medida que o classificador deixa de apresentar uma classificação correta para o padrão. Ao mesmo tempo, à medida que os pontos FP’s vão sendo apresentados, eles já são representados de acordo com cada classe possível (nesse caso, Classes 2 e 3) e de forma crescente. Em suma, os erros são apresentados pelo decréscimo de VP’s e aumento de FP’s (de acordo com cada classe). Fig. 13. Estrutura para 3 Classes – 1 Módulo Assim como nas estruturas descritas na seção anterior, podem ser acrescentados módulos para análise de sensibilidade, desde que seja adicionado 1 módulo para cada classe para manter o sincronismo e a coerência da representação(ex.: adicionar 1 módulo para VP da Classe 1 implica em adicionar 1 módulo de FP para classe 2 e outro para classe 3), como mostra a Figura 14. de poder de classificação, tomando por referência a matriz da confusão. Conforme apresentado nos resultados, a estrutura de 4 módulos se mostrou simples, mantendo um grau baixo de sensibilidade para algoritmos que tenham as capacidades de classificação parecidas (mas não idênticas). Já a estrutura de 10 módulos demonstrou tanto a capacidade de apresentar a devida resposta do poder de classificação de cada algoritmo, como também demonstrou uma sensibilidade muito maior que a estrutura de 4 módulos. Adicionalmente, as AUCs obtidas por nossas abordagens se mostraram espaçadas e de melhor visualização (apesar de dependentes do número de módulos) que as obtidas pela metodologia descrita em Fawcett (2006), principalmente nos experimentos que orientam a proposta com múltiplas classes. As estruturas são independentes dos algoritmos e apresentaram capacidade de extensão. Agradecimentos Agradecemos a FAPEMIG, CAPES, PPGEEUFMG e CNPq pelo apoio à pesquisa. Referências Bibliográficas Fig. 14. Estrutura para 3 Classes – 2 Módulos Um detalhe importante é que não importa o número de classes analisadas pelo classificador (podendo ser 3 ou mais), a estrutura pode representar cada uma delas, se respeitada a forma de adição e ligação de módulos, o que resolve o problema que foi descrito por Fawcett (2006) para obtenção de AUCs para problemas com múltiplas classes. A questão a ser ainda trabalhada são os números das Fichas Centrais iniciais de cada análise (tanto VP’s quanto FP’s), que serão desenvolvidos futuramente. 8 Conclusão Este trabalho apresentou uma proposta orientada a redes de Petri para estimação do poder global de classificação. As redes de Petri possibilitam representar uma estrutura capaz de assimilar as diferenças Bergmeir, C., Benítez,J. M. Neural Networks in R using the Stuttgart Neural Network Simulator (SNNS). July, 2014. Cassandras CG, Lafortune S. Introduction to Discrete Event Systems. 2ªed.. Editora Springer. 2008. Castro, C. L., Braga, A.P.. "Novel cost-sensitive approach to improve the multilayer perceptron performance on imbalanced data." Neural Networks and Learning Systems, IEEE Transactions on 24.6 (2013): 888-899. De Wilde,P. Neural Network Models.2ªed. Springer Science & Business Media. 1997. 174p. Fawcett, T. An introduction to ROC analysis. Pattern Recognition Letters 27. 2006.861–874. Krogh, A., Hertz, J.A. A Simple Weight Decay Can Improve Generalization. Advances in Neural Information Processing Systems 4. 1992. p950957. Ed. Morgan Kaufmann. Landgrebe, T. and Duin, R. (2008). Efficient multiclass roc approximation by decomposition via confusion matrix perturbation analysis, IEEE Trans. Pattern Anal. Mach. Intell. 30: 810–822. Parma, G.G., Menezes, B.R., Braga,A.P.. "Neural networks learning with sliding mode control: the sliding mode backpropagation algorithm." International Journal of Neural Systems 9.03 (1999): 187-193. Silva, M., Valette, R. "Petri nets and flexible manufacturing."Advances in Petri nets 1989. Springer Berlin Heidelberg, 1990. 374-417. Woods, K.; Bowye; K.W. "Generating ROC curves for artificial neural networks." Medical Imaging, IEEE Transactions on 16.3 (1997): 329-337.