Para a an´alise dos experimentos, inicialmente foi realizada uma an´alise da qualidade geral das solu¸c˜oes, seguida de uma an´alise mais detalhada. Nos dois casos, todas as configura¸c˜oes do MOCLE (MUH, MUM, MSH e MSM) foram comparadas com os algo- ritmos individuais (KM, LM, LS e SNN) e com o algoritmo de agrupamento multi-objetivo MOCK e o ensemble ES.
Como os algoritmos MOCLE e MOCK n˜ao s˜ao determin´ısticos, foram realizadas 30 execu¸c˜oes, com as mesmas configura¸c˜oes iniciais. O ES depende da ordem de apresenta¸c˜ao das parti¸c˜oes iniciais. Assim, para o ES, tamb´em foram realizadas 30 execu¸c˜oes, cada uma
7.4 Metodologia de Avalia¸c˜ao dos Experimentos
apresentando as parti¸c˜oes em uma ordem aleat´oria. Para o KM, na an´alise geral tamb´em foram consideradas todas as 30 execu¸c˜oes realizadas. Na an´alise detalhada, foi empregado o conjunto de parti¸c˜oes do KM que foi considerado na popula¸c˜ao inicial do MOCLE.
A qualidade geral das solu¸c˜oes foi avaliada com o ´ındice CR, descrito na Se¸c˜ao 3.4 (Equa¸c˜ao 3.5), pois, como j´a mencionado, esse ´e um dos ´ındices de valida¸c˜ao externa mais utilizados, n˜ao sendo sens´ıvel ao n´umero de clusters, como outros ´ındices.
A primeira quest˜ao a ser avaliada ´e a habilidade dos algoritmos em gerar solu¸c˜oes de alta qualidade. Para isso, foi considerado o conhecimento do conjunto de estruturas ΠE = {πE1, πE2, ..., πEnE
} sabidamente existentes em cada conjunto de dados. Esse co- nhecimento externo ´e usado para selecionar a melhor solu¸c˜ao de cada conjunto em rela¸c˜ao a cada estrutura conhecida. Deve-se considerar que tal conhecimento n˜ao foi empre- gado pelos algoritmos na determina¸c˜ao das solu¸c˜oes, com exce¸c˜ao das configura¸c˜oes semi- supervisionadas do MOCLE, que utilizaram apenas parte desse conhecimento. Para a obten¸c˜ao dos valores do CR a serem comparados foram seguidos os seguintes procedimen- tos.
Para os algoritmos LM, LS e SNN, que s˜ao determin´ısticos, foi calculado o CR entre cada parti¸c˜ao πSi do conjunto de solu¸c˜oes, ΠS =
{πS1, πS2, ..., πSnS
} e cada estrutura πEj do conjunto de estruturas conhecidas ΠE. Para cada estrutura conhecida, πEj, foi selecionada a melhor parti¸c˜ao do conjunto de solu¸c˜oes em rela¸c˜ao a essa estrutura, ou seja, a parti¸c˜ao πSi que apresenta o maior CR quando comparada com πEj.
Para as demais t´ecnicas (KM, MOCK, ES e MOCLE), o mesmo foi feito para cada execu¸c˜ao. Assim, para cada estrutura conhecida, πEj, foi selecionada uma parti¸c˜ao πSi mais pr´oxima de πEj para cada uma das 30 execu¸c˜oes. Em seguida, para cada πEj, foram calculados a m´edia e o desvio padr˜ao do CR dessas 30 parti¸c˜oes πSi selecionadas. Esse procedimento ´e o mesmo seguido em (Handl and Knowles 2006a). A ´unica diferen¸ca ´e que neste trabalho est˜ao sendo consideradas v´arias estruturas para cada conjunto de dados e em (Handl and Knowles 2006a), uma ´unica estrutura.
Al´em do conjunto de solu¸c˜oes completo, o MOCK retorna um n´umero reduzido (1 a 4) de solu¸c˜oes recomendadas como as melhores do fronte de Pareto. Para esse conjunto de recomenda¸c˜oes, tamb´em foram selecionadas as parti¸c˜oes que mais se aproximam de cada uma das estruturas conhecidas em cada execu¸c˜ao e calculados a m´edia e desvio padr˜ao para as 30 execu¸c˜oes. A recomenda¸c˜ao do MOCK ser´a denominada MKR, enquanto que o MOCK considerando todas as solu¸c˜oes ser´a denominado apenas por MK.
Com isso, as referˆencias futuras ao CR dizem respeito tanto ao CR calculado para uma parti¸c˜ao, quanto a m´edia do CR das parti¸c˜oes de v´arias execu¸c˜oes, dependendo se as t´ecnicas s˜ao as determin´ısticas ou n˜ao determin´ısticas.
algoritmos foi empregado o teste Friedman e o p´os teste de Nemenyi, apropriado para comparar v´arios algoritmos aplicados em m´ultiplos conjuntos de dados (Hollander and Wolfe 1999; Demˇsar 2006). Segundo Demˇsar (2006), esse teste ´e mais apropriado para analisar algoritmos de aprendizado de m´aquina do que o teste ANOVA, pois n˜ao se pode garantir que as suposi¸c˜oes necess´arias para o ANOVA n˜ao sejam violadas.
Para aplicar esse teste, inicialmente s˜ao ordenados os algoritmos para cada conjunto de dados, separadamente. O melhor algoritmo recebe o rank 1, o segundo melhor,rank 2, e assim por diante. Para os casos de empate, a m´edia dos ranks ´e associada a todos os algoritmos que tˆem desempenho igual.
Dados nA algoritmos e nD conjuntos de dados, rj
i ´e o rank do j-´esimo algoritmo no i-´esimo conjunto de dados. No teste Friedman, a hip´otese nula ´e a de que todos os algoritmos s˜ao equivalentes e, portanto, a m´edia dos ranks, Rj = 1
nD
nD
P i=1
rji deve ser igual. A estat´ıstica Friedman ´e dada pela Equa¸c˜ao 7.1. Como χ2
F ´e indesejavelmente conservadora, Iman and Davenport (1980) derivaram uma estat´ıstica melhor, dada pela Equa¸c˜ao 7.2, que ´e distribu´ıda de acordo com a distribui¸c˜ao F com (nA
− 1) e (nA − 1)(nD − 1) graus de liberdade. χ2 F = 12nD nA(nA+ 1) nA X j=1 R2 j − nA(nA+ 1)2 4 (7.1) FF = (n D − 1)χ2 F nD(nA− 1) − χ2 F (7.2) Se a hip´otese nula for rejeitada, ser´a aplicado o p´os teste de Nemenyi, apropriado para comparar cada algoritmo com todos os outros. Segundo esse teste, dois algoritmos s˜ao significativamente diferentes se a m´edia dos ranks, Rj, difere de pelo menos uma diferen¸ca cr´ıtica, CD, dada pela Equa¸c˜ao 7.3, em que os valores cr´ıticos, qα, s˜ao baseados na Studentized range statistic, dividido por √2 (Demˇsar 2006).
CD = qα r
nA(nA+ 1)
6nD (7.3)
Neste trabalho, ser˜ao considerados como algoritmos a serem comparados, as quatro configura¸c˜oes do MOCLE (MUH, MUM, MSH e MSM), o ensemble ES, o MOCK, con- siderando todas as solu¸c˜oes (MK) e somente as recomenda¸c˜oes (MKR), e os algoritmos individuais (KM, LM, LS e SNN), perfazendo um total de 11 t´ecnicas (nA = 11). Como conjuntos de dados, foram considerados os 10 conjuntos descritos na Se¸c˜ao 7.2 e cada uma de suas estruturas conhecidas. Assim, o conjunto de dados glass, por exemplo, ser´a considerado como trˆes casos diferentes, uma vez que, para cada estrutura conhecida, ser´a obtida uma solu¸c˜ao diferente. Considerando os 10 conjuntos de dados e suas respectivas
7.5 Considera¸c˜oes Finais
estruturas, ser˜ao analisadas um total de nD= 22 estruturas.
Ainda na an´alise geral, al´em da habilidade das t´ecnicas em encontrar as estruturas conhecidas, foram avaliadas a concis˜ao e a estabilidade das t´ecnicas que geram um con- junto de solu¸c˜oes. Para a concis˜ao, ser´a analisado o n´umero m´edio de solu¸c˜oes obtidos nas 30 execu¸c˜oes. Para a estabilidade, ser˜ao observados os desvios padr˜ao do CR calculados como j´a descrito.
A an´alise detalhada ilustra outros aspectos importantes do MOCLE que n˜ao podem ser observados na an´alise geral. Para isso, foi selecionada uma execu¸c˜ao de cada t´ecnica em que foram realizadas 30 execu¸c˜oes. A execu¸c˜ao selecionada foi aquela que possuia a parti¸c˜ao com maior CR em rela¸c˜ao a estrutura mais refinada. Assim, para cada t´ecnica, foi analisado um conjunto de solu¸c˜oes, ΠS, por meio de gr´aficos empregando o CR e os valores de var e con de cada parti¸c˜ao πSi, e tamb´em o m´etodo de visualiza¸c˜ao proposto no Cap´ıtulo 6. Al´em disso, para as solu¸c˜oes do MOCLE, ser´a avaliado se cada solu¸c˜ao j´a fazia parte da popula¸c˜ao inicial, ou se foi gerada durante o processo de evolu¸c˜ao, por meio da combina¸c˜ao de outras parti¸c˜oes. Para a an´alise com o m´etodo de visualiza¸c˜ao, foi selecionado apenas um conjunto de dados, pois sua aplica¸c˜ao a todos os conjuntos geraria um grande volume de tabelas e apenas um conjunto j´a serve para ilustrar bem a utiliza¸c˜ao do m´etodo.
7.5
Considera¸c˜oes Finais
Neste cap´ıtulo foi apresentada a metodologia empregada para a realiza¸c˜ao dos ex- perimentos. Em resumo, foram empregados 10 conjuntos de dados com caracter´ısticas bastante distintas. Quatro configura¸c˜oes diferentes do MOCLE foram investigadas, duas no contexto n˜ao supervisionado e duas no semi-supervisionado. As parti¸c˜oes iniciais para o MOCLE foram geradas com quatro algoritmos de agrupamento distintos e com di- ferentes n´umeros de clusters. Al´em dos algoritmos individuais, o MOCLE tamb´em foi comparado com o ensemble de agrupamentos ES e o algoritmo de agrupamento multi- objetivo MOCK, cujos princ´ıpios foram combinados para a proposi¸c˜ao do MOCLE. As avalia¸c˜oes dos resultados ser˜ao feitas com um ´ındice de valida¸c˜ao bastante tradicional, o CR, sendo tamb´em aplicado um teste estat´ıstico para avaliar a significˆancia estat´ıstica das diferen¸cas de desempenho entre as t´ecnicas.
No Cap´ıtulo 8 ser˜ao apresentados os resultados obtidos com os experimentos. Ser´a ainda discutido como cada meta foi atingida.