Com a finalidade de atestar se as diferenças entre os métodos determinísticos para inicialização dos centros de grupos que foram propostos neste trabalho e demais algoritmos são significativas ou não, foi utilizada a estatística do teste de Friedman (FRIEDMAN,
1937, 1940). O teste de Friedman é um teste não-paramétrico (livre da distribuição de probabilidade dos dados) utilizado para comparar dados amostrais vinculados, ou seja, quando o mesmo indivíduo é avaliado mais de uma vez.
Para realizar o teste de Friedman foram criadas 50 versões das bases de dados origi- nais (Iris, Blocks, Spambase, Moons, Blobs, S4) utilizando 90% dos dados, selecionados aleatoriamente. O teste de Friedman foi executado utilizando os valores dos índices DB, SF e CR. Foi usado também o tempo de execução e número de iterações dos algoritmos.
6.1
Teste de Friedman
O teste de Friedman é um teste não-paramétrico, ou seja, não utiliza os parâmetros da distribuição de probabilidades dos dados estudados, ou uma estimativa destes, para o cálculo de sua estatística. Ao invés de usar os valores numéricos dos dados, utiliza os postos (ranks) atribuídos aos dados ordenados para o cálculo da estatística. Este teste é adequado para comparar o desempenho de diferentes algoritmos quando aplicados a vários conjuntos de dados (SHELDON; FILLYAW; THOMPSON, 1996; CHAH et al., 2011). O teste
de Friedman determina se os algoritmos analisados produzem resultados com diferenças significativas.
A estatística de Friedman é uma alternativa não-paramétrica para o teste em blocos ao acaso. Assim, suponha que Xij representa o resultado experimental do fator (ou “bloco”)
Tabela 40: Tabela de blocos x tratamentos Tratamentos Blocos 1 2 ... k 1 X11 X12 ... X1k 2 X21 X22 ... X2k ... ... ... ... ... n Xn1 Xn2 ... Xnk
Para calcular a estatística do teste de Friedman, as k observações são ordenadas da menor para a maior de forma separada em cada um dos n blocos e os ranks {1, 2, ..., k} são atribuídos para cada bloco da tabela de observações. Assim, a posição esperada de qualquer observação é (k + 1)/2. Sendo r(Xij) o rank da observação Xij, a soma de todos
os ranks da coluna j (ou seja, de cada tratamento) é definida por:
Rj = n
X
i=1
r(Xij), 1 ≤ j ≤ k (6.1)
A estatística de Friedman é calculada da seguinte forma:
χ2r = 12 nk(k + 1) k X j=1 R2j − 3n(k + 1) (6.2)
onde Rj, j = 1, ..., k é o somatório do rank da j-ésima coluna. χ2r é aproximadamente qui
quadrado com k − 1 graus de liberdade.
No teste de Friedman é testada a hipótese nula (H0) de que todos os k tratamentos são
semelhantes, contra a hipótese alternativa (H1), de que existe pelo menos um tratamento
diferente. A hipótese (H0) é rejeitada em um nível de significância α, se χ2r ≥ χ2α com
k − 1 graus de liberdade. O valor χ2
α pode ser encontrado em referências da estatística. A tabela qui quadrado
utilizada neste trabalho que está disponível no apêndice B foi retirada de Walck (WALCK,
2007).
Opcionalmente calcula-se o p-valor de χ2
r e compara-se este valor com o α adotado.
Caso o p-valor seja maior que α então a hipótese H0 é verdadeira, caso contrário a hipótese
H1 é verdadeira. O p-valor, também denominado nível descritivo do teste, é a probabi-
(estatística) quando a hipótese H0 é verdadeira. O p-valor, que depende diretamente de
uma dada amostra, tenta fornecer uma medida da força dos resultados de um teste, em contraste a uma simples rejeição ou não rejeição. Se a hipótese nula for verdadeira e a chance da variação aleatória for a única razão para as diferenças amostrais, então o p- valor é uma medida quantitativa para alimentar o processo da tomada de decisão como evidência.
Assim, o p-valor é uma medida de quanta evidência se tem contra a hipótese nula. Quanto menor o p-valor, mais evidência se tem. Deve combinar-se o p-valor com o nível de significância para tomar decisão sobre o teste de hipótese. Em tal caso, se o p-valor for menor que algum corte (usualmente 0,05, algumas vezes um pouco mais como 0,1 ou um pouco menos como 0,01) então a hipótese nula é rejeitada.
6.1.1
Exemplo
A fim de avaliar se houve progressão na aprendizagem, um professor reteve as médias de um grupo de 4 alunos no final de cada trimestre:
Tabela 41: Amostra das notas dos alunos A, B, C e D em 3 trimestres
Alunos A B C D
1o Trimestre 8 15 11 7
2o Trimestre 14 17 13 10
3o Trimestre 15 17 14 12
Considerando um α = 0.05, que conclusão pode-se tirar? Hipóteses:
• H0: Não houve progressão na aprendizagem ao longo do ano escolar;
• H1: Houve progressão ao longo do ano escolar.
Resolução:
Tabela 42: Tabela de ranks
Alunos 1o Trimestre 2o Trimestre 3o Trimestre
A 1 2 3 B 1 2.5 2.5 C 1 2 3 D 1 2 3 Rj 4 8.5 11.5 R2 j 16 72.25 132.25
A Tabela 42 informa que n = 4 e k = 3, então χ2
r = 4×3×412 × [16 + 72.25 + 132.25] −
3 × 4 × (3 + 1) = 7.125
Com o auxílio da Tabela 49 do apêndice B descobre-se que o valor de χ2
α = 5.9915,
com α = 0.05 e (k − 1) = (3 − 1) = 2 graus de liberdade. Como χ2
r ≥ χ2α a hipótese nula
é rejeitada.
Pelos dados da Tabela 49 tem-se 0.05 ≤ p-valor(χ2
r) ≤ 0.025. Assim, com α = 0.05,
a hipótese nula é rejeitada. Então, conclui-se que houve progressão na aprendizagem ao logo do ano escolar.
6.2
Teste de Wilcoxon-Nemenyi-McDonald-Thompson
O teste de Friedman não diz especificamente quais tratamentos são diferentes em casos onde a hipótese nula é rejeitada. Ele só pode dizer que em algum lugar entre seus tratamentos, existem diferenças significativas. Para obter informações adicionais, é preciso realizar um teste post-hoc. Os testes post-hoc são necessários para identificar quais dos pares de tratamento diferem.
Neste trabalho o teste post-hoc utilizado foi o Wilcoxon-Nemenyi-McDonald-Thompson (HOLLANDER, 1999; DEMŠAR, 2006). Este teste é baseado no teste de Friedman, que uti-
liza blocos de ranks, e calcula diferenças entre pares de tratamentos.
Seja R1, ..., Rk o somatório dos ranks de k tratamentos τ, calcula-se as k(k − 1)/2
diferenças absolutas |Ru− Rv|, 1 ≤ u < v ≤ k. Com base em uma taxa de erro α, o teste
Decidir (
τu 6= τv se |Ru− Rv| ≥ rα
τk = τv caso contrário
(6.3) A constante rα é definida como o valor crítico e é calculada pela seguinte fórmula:
rα = qα
r
nk(k + 1) 12
onde qαpara um número de tratamentos k e uma taxa de erro α é definido pela Tabela
50 do Apêndice B. Por exemplo, para encontrar o valor q0.05 para um k = 3 e α = 0.05,
pela tabela 50 temos que q0.05= 3.314.
6.2.1
Exemplo
Considere o exemplo da seção 6.1.1 que usou o teste de Friedman para avaliar se houve progressão na aprendizagem. Para este exemplo o teste de Friedman encontrou diferenças entre os tratamentos avaliados. Agora será utilizado o teste Wilcoxon-Nemenyi-McDonald- Thompson para encontrar as diferenças entre os pares de tratamentos avaliados.
Para este problema tem-se n = 4, k = 3 e α = 0.05. Conferindo a Tabela 50 é encontrado o valor q0.05= 3.314
Calcula-se inicialmente a diferença crítica rα = 3.314
q
4×3×4
12 = 6.628 .
Utilizando o somatório dos ranks Rj da Tabela 42 é possível decidir quais pares
possuem diferença significativa comparando cada par de tratamentos τ, como mostra a Tabela 43:
Tabela 43: Pares de tratamentos
Tratamentos Ru Rv |Ru− Rv| |Ru− Rv| ≥ rα
τ2 e τ1 8.5 4 4.5 Não
τ3 e τ1 11.5 4 7.5 Sim
τ3 e τ2 11.5 8.5 3 Não
Pela Tabela 43 para decidir se há diferença entre os pares τ2e τ1, calcula-se a diferença
entre os dois |R2− R1| = |8.5 − 4| = 4.5 utilizando a Equação 6.3. Como 4.5 < 6.628 então
não há diferenças significativas entre os pares de tratamentos τ2 e τ1. Para os pares τ3 e τ1
entre os pares τ3 e τ1. Por fim para os pares τ3e τ2 tem-se que |R3−R2| = |11.5−7.5| = 3.0,
como 3.0 < 6.628 então não foi encontrada diferença entre os pares τ3 e τ2.
6.3
Experimentos e Resultados da Análise Estatística
O teste de Friedman foi executado para procurar por diferenças significativas entre os algoritmos apresentados neste trabalho. Nos casos onde houve diferença significativa entre os algoritmos de agrupamento, o teste post-hoc Wilcoxon-Nemenyi-McDonald-Thompson foi executado para descobrir quais pares de algoritmos foram significativamente diferentes. Nesta seção, as tabelas de resultados apresentam apenas dados resumidos para os testes de Friedman e post-hoc Wilcoxon-Nemenyi-McDonald-Thompson. As informações completas sobre os resultados destes testes poderão ser encontradas no Apêndice A.
A execução dos testes foi feita utilizando o software R (R Core Team, 2014), versão 3.0.2. O teste de Friedman é disponibilizado pelo R, bem como o teste post-hoc Wilcoxon- Nemenyi-McDonald-Thompson.
6.3.1
Experimentos
Para realização dos testes estatísticos foram utilizadas as bases de dados: Iris, Spam- base, Page Blocks, Moons, Blobs e S4 apresentadas anteriormente. Para cada base foram geradas 50 versões com 90% dos dados originais selecionados em ordem aleatória. Os al- goritmos FCM e ckMeans foram aplicados às 50 versões de cada base. Como o objetivo do teste estatístico foi avaliar os métodos de inicialização, os tratamentos considerados no teste de Friedman foram tais métodos, ou seja, inicialização aleatória para os algoritmos FCM e ckMeans originais, os determinísticos propostos: Método I, Método II e Método II; e a inicialização do algoritmo mrFCM. Aqui usaremos as siglas: M1 para Método I, M2 para Método II, M3 para Método III, R para inicialização aleatória e MR para a inicialização do mrFCM.
Dos resultados da execução dos algoritmos, foram analisados: o índice Davies Bol- ding(DB), o índice Silhueta Fuzzy(SF), o tempo de execução, que compreende o tempo de inicialização mais o tempo de execução do algoritmo de agrupamento(tempo) e o número de iterações que o algoritmo de agrupamento levou para convergir(iter).
Os parâmetro utilizados para os algoritmos de agrupamento foram os mesmos parâ- metros definidos na Seção 5.1.7, com a diferença de que cada versão das bases de dados
foi executada uma única vez.
O teste de Friedman foi executado com o objetivo de encontrar diferenças significativas entre os algoritmos de inicialização que executaram em todas as 6 bases. Consideramos para este teste que os tratamentos serão os 5 métodos de inicialização mencionados no início desta subseção (M1, M2, M3, R, MR) e os blocos serão os valores resultantes da execução dos métodos de agrupamento para as 6 bases de dados apresentadas neste trabalho.
Foram executados 24 testes de Friedman, 6 testes para cada um dos parâmetros anali- sados (DB, FS, tempo e iter). Por exemplo para o parâmetro DB, há 3 testes de Friedman para o algoritmo de agrupamento FCM, com m = {1.5, 1.75, 2.0} e outros 3 testes para o algoritmo de agrupamento ckMeans. Desta forma, analisar um dos testes significa que se estar verificando a existência de diferenças significativas entre os tratamentos para um determinado algoritmo de agrupamento, com dado valor de m, utilizando os resultados de um dos parâmetros em análise (DB, FS, time e iter).
Para cada teste de Friedman, separa-se o conjunto de valores que serão analisados. Por exemplo, para analisar se houve diferenças significativas entre os métodos de inicialização, utilizando o índice DB, no algoritmo de agrupamento FCM, com m = 1.5, tem-se uma tabela com os 5 tratamentos (algoritmos de inicialização), para 6 blocos (bases de dados). Os valores desta tabela são selecionados em cada execução da base de dados. Um exemplo demonstrativo desta tabela é apresentado na Tabela 44.
Tabela 44: Amostra do resultado do índice DB, com m = 1.5 e algoritmo de agrupamento FCM, para os diferentes métodos de inicialização
M1 M2 M3 MR R
Iris vM 1
Iris vM 2Iris vIrisM 3 vM RIris vIrisR
Spambase vM 1
Spambase vM 2Spambase vSpambaseM 3 vSpambaseM R vSpambaseR
Page Blocks vM 1
P ageBlocks vP ageBlocksM 2 vP ageBlocksM 3 vM RP ageBlocks vP ageBlocksR
Moons vM 1
M oons vM oonsM 2 vM 3M oons vM RM oons vM oonsR
Blobs vM 1
Blobs vBlobsM 2 vBlobsM 3 vM RBlobs vBlobsR
S4 vM 1
S4 vM 2S4 vS4M 3 vM RS4 vS4R
onde vM 1
Iris é o valor do índice DB retornado pela execução do método de inicialização
M1 para a base Iris. vM 2
Spambase é o valor de DB retornado pelo método M2 para a base
O teste de Friedman foi executado com: • α = 0.10;
• H0 = todos os algoritmos de inicialização são similares; • H1 = nem todos os algoritmos de inicialização são similares.
No caso do teste de Friedman ter valor menor que α, então H0 é rejeitada, e que portanto existe algum algoritmo significativamente diferente dos demais. Executa-se então o teste post-hoc de Wilcoxon-Nymenyi-McDonald-Thompson para descobrir quais pares de algoritmos tiveram diferenças significativas. A Tabela 45 apresenta o resultado do teste de Friedman.
Tabela 45: Resultado do teste de Friedman (p-value)
FCM ckMeans m 1.5 1.75 2.0 1.5 1.75 2.0 DB 0.253710 0.285563 0.043997 0.227609 0.445325 0.337010 SF 0.065746 0.185438 0.121974 0.112472 0.120942 0.035807 iter 0.323240 0.005774 0.010339 0.046812 0.062788 0.074760 Tempo 0.638677 0.028906 0.032341 0.119287 0.180099 0.180099
Na Tabela 45 é possível observar os valores encontrados no teste de Friedman. Os valores em negrito destacam os resultados em que o teste teve valor menor que α, por- tanto com a hipótese H0 rejeitada, mostrando que existe evidências em 41% dos casos de que algum algoritmo foi significativamente diferente dos demais. Os outros valores na tabela informam que não foram encontradas diferenças significativas entre o algoritmos de inicialização.
O teste de Friedman encontrou diferenças significativas entre os algoritmos analisa- dos em 10 dos 24 casos. A maior quantidade de casos foi no número de iterações, onde para todos os valores de m no algoritmo ckMeans houve diferenças significativas entre os métodos de inicialização. Já no FCM só não houve diferenças significativas para m = 1.5. Em relação ao tempo de execução, os resultados mostraram existir diferenças para o FCM com m = 1.75 e m = 2.0. Já com relação ao ckMeans, não se pode afirmar nada para o α adotado.
O índice SF mostrou diferenças apenas para o FCM com m = 1.5 e para o ckMeans com m = 2.0. Para os demais valores de m não se pode afirmar nada para o valor de α adotado.
Para o índice DB o algoritmo FCM com m = 2.0 mostrou haver diferenças significati- vas entre os algoritmos analisados. Para os demais valores de m não se pode afirmar nada para o valor de α adotado.
Vale ressalvar que na Tabela 45 os valores abaixo de α indicam diferenças signifi- cativas entre os algoritmos de inicialização, porem valores acima de α mas que estejam mais próximos de seu valor, também indicam diferenças, porém menos significativas (me- nos confiáveis). Por fim valores altos indicam não haver diferenças perceptíveis entre os resultados dos algoritmos.
Para encontrar quais algoritmos tiveram esta diferença significativa, foi executado o teste post-hoc Wilcoxon-Nemenyi-McDonald-Thompson. Que informa quais os pares de algoritmos tiveram diferenças mais significativas.
Tabela 46: Resultado do teste post-hoc Wilcoxon-Nemenyi-McDonald-Thompson
FCM ckMeans m 1.5 1.75 2.0 1.5 1.75 2.0 DB (M3,M2);(R,M2) SF (R,M2) (R,M2) iter (M3,M1);(R,M1);(M3,M2) (M3,M1);(M3,M2) (M3,M2);(R,M2) (R,M2) (M3,M2) tempo (M3,M1);(M3,M2) (M3,M1)
Na Tabela 46 foi substituído os valores em negrito da Tabela 45 pelos pares encontra- dos que possuem diferenças significativas pelo teste post-hoc. Os pares encontrados estão delimitados por parênteses e separados por ponto e vírgula. Cada algoritmo dentro de um par está separado por uma vírgula.
Por exemplo, (M3,M2);(R,M2), são dois pares, onde o primeiro par é (M3,M2) e o segundo par é (R,M2). O par (M3,M2) pode ser interpretado como: há uma diferença significativa entre os algoritmos M3 e M2.
Tabela 47: Resultado do teste post-hoc Wilcoxon-Nemenyi-McDonald-Thompson (p- value)
Algoritmo FCM ckMeans
m 1.5 1.75 1.75 1.75 2.0 2.0 1.5 1.75 2.0 2.0 SF DB iter tempo iter tempo iter iter FS iter M2-M1 0.7894 0.3498 0.9962 0.9998 0.9962 0.9822 0.7562 0.8921 0.8875 0.8517 M3-M1 0.8948 0.8891 0.0164 0.0486 0.0165 0.0486 0.5842 0.5882 0.6362 0.5243 MR-M1 0.9994 0.9677 0.7048 0.3586 0.4696 0.1831 0.9997 0.9822 0.9207 0.9909 R-M1 0.5069 0.9677 0.0788 0.4697 0.1831 0.3586 0.6437 0.4696 0.2953 0.7015 M3-M2 0.2477 0.0454 0.0484 0.0789 0.0483 0.1830 0.0603 0.1224 0.1412 0.0767 MR-M2 0.8948 0.7533 0.8921 0.4696 0.7048 0.4697 0.6438 0.5882 0.3993 0.5842 R-M2 0.0517 0.0939 0.1830 0.5882 0.3586 0.7048 0.0767 0.0788 0.0339 0.1475 MR-M3 0.7894 0.5200 0.3586 0.8921 0.5882 0.9822 0.7015 0.8921 0.9814 0.8066 R-M3 0.9609 0.9987 0.9822 0.8090 0.8921 0.8921 1.0000 0.9998 0.9814 0.9987 R-MR 0.3667 0.6982 0.7048 0.9998 0.9822 0.9962 0.7562 0.8090 0.8017 0.9230
Na Tabela 47 são mostrados as diferenças entre os pares de algoritmos de inicialização analisados. Esta tabela resume os resultados presentes no Apêndice A. Estão sendo mos- trados apenas os resultados do teste post-hoc que ficaram abaixo de α = 0.10 da Tabela 45.
Analisando os resultados do teste post-hoc pode-se encontrar pares mais semelhantes e pares menos semelhantes de algoritmos, baseados em suas diferenças. Pares de algorit- mos com um alto valor no teste post-hoc são estatisticamente mais semelhantes do que algoritmos com um baixo valor. Com base nestas observações, na Tabela 48 é exibida a relação entre os algoritmos de inicialização testados.
Tabela 48: Resultado do teste post-hoc: relação entre algoritmos
FCM ckMeans m 1.5 1.75 2.0 1.5 1.75 2.0 DB M2>MR>{M1,R}>M3 SF M2>{MR,M1}>M3>R M2>M1>{MR,M3}>R iter M1>M2>MR>{R,M3} {M1,M2}>MR>R>M3 M2>M1>MR>R>M3 M2>M1>MR>M3>R M2>M1>MR>R>M3 tempo {M1,M2}>{R,MR,M3} M1>M2>R>{MR,M3}
Na Tabela 48 o símbolo > indica que o algoritmo à esquerda mostrou melhores resul- tados que o outro. Por exemplo, a relação M2>MR indica que o algoritmo M2 mostrou melhores resultados que o MR. Já algoritmos entre chaves indicam que estes são estatis- ticamente semelhantes, como por exemplo {M1,R}.
Com base nos resultados apresentados nota-se que os métodos determinísticos de inicialização M1 e M2 apresentam melhores desempenhos, seguidos do algoritmo MR e
por fim, pelos algoritmos M3 e R.
6.3.2
Resultados
Para os conjunto de dados Iris, Spambase, Page Blocks, Moons, Blobs e S4, o teste de Friedman mostrou haver diferenças significativas entre os algoritmos de inicialização Método I, Método II, Método III, mrFCM e inicialização aleatória, para os algoritmos de agrupamento FCM e ckMeans, com os valores de m = {1.5, 1.75, 2.0}.
O teste post-hoc Wilcoxon-Nemenyi-McDonald-Thompson mostrou com 90% de signi- ficância que os algoritmos M1 e M2 tiveram melhores resultados que os demais algoritmos. O algoritmo M3 foi considerado estatisticamente semelhante ao algoritmo R.
Os testes estatísticos indicaram que os métodos de inicialização M1 e M2, trazem o maior ganho de desempenho aos algoritmos FCM e ckMeans, com a redução do número de iterações e do tempo de execução. Estes métodos também encontram melhores valores para os índices SF e DB.
Para o algoritmo de inicialização M3 não foi possível detectar diferenças significativas com relação ao algoritmo de inicialização R.