Nesta seção, a melhor variante do ESM-EM, VS-PLL, é comparada com o algoritmo evolu- tivo estado-da-arte Genetic-based Expectation Maximization (GA-EM) (Pernkopf e Bouchaffra, 2005). Por simplicidade, daqui em diante esta variante será referenciada apenas por ESM-EM. Nas comparações, foi utilizado o algoritmo OMR-EM (Seção 2.2) como baseline, devido ao seu amplo uso na prática. Alguns dos parâmetros do GA-EM são comuns aos de outros AEs, como as probabilidades de mutação e crossover. Junto com tais parâmetros, GA-EM possui pa- râmetros adicionais, como o limiar de correlação máxima e o valor mínimo de verossimilhança que um componente gaussiano pode ter. Estes parâmetros são difíceis de serem ajustados na prática, especialmente quando se usa AEs para problemas de agrupamento de dados. Dentro de experimentos controlados, no entanto, pode-se adotar um procedimento de ajuste fino dos parâmetros para se obter bons valores para cada parâmetro e seguir com as comparações. Neste sentido, foi utilizado o framework SPOT (do inglês, Sequential Parameter Optimization Tool- box) (Bartz-Beielstein et al., 2005) para otimizar os parâmetros do GA-EM. Para simplificar a análise de resultados, apenas os melhores resultados do GA-EM obtidos são discutidos na sequência. No entanto, é importante considerar que tais resultados foram obtidos após um es- forço significante na otimização de seus parâmetros, exigindo custo computacional considerável para cada base de dados. Este procedimento (custoso computacionalmente) de otimização de parâmetros dificilmente poderia ser realizado em aplicações práticas.
O algoritmo ESM-EM, por sua vez, não possui parâmetros críticos. Todos os seus parâ- metros (i.e., tamanho da população, número máximo de iterações do EM e K-means, e número máximo de grupos) podem ser definidos de acordo com os recursos computacionais disponíveis. Por exemplo, com populações menores é esperado que o algoritmo necessite de mais tempo para convergir (Naldi et al., 2011). Similarmente, o número de iterações do EM/K-means pode ser
3.4 Avaliação Empírica 55 definido de acordo com o tempo disponível para execução. Em relação ao número máximo de grupos, o usuário pode ter as suas expectativas, e consequentemente, definir tal valor de acordo com as mesmas. Caso este não seja o caso, e assumindo que o menor número de grupos é dois, é esperado que quanto maior o número de grupos, maior o tempo de execução para explorar o espaço de busca. Finalmente, o usuário pode definir uma faixa de valores para K conside- rando a limitação de seus recursos computacionais ou suas expectativas em relação a partição ser induzida. Neste sentido, o ESM-EM pode ser visto como uma melhoria do GA-EM, por não necessitar de otimização de seus parâmetros no processo de aprendizado, mas apenas sobre os recursos computacionais disponíveis. Sob o ponto de vista teórico, devido aos operadores do GA-EM serem guiados e baseados em operadores de divisão/união, ESM-EM pode ser visto como um algoritmo mais principiado em comparação com o GA-EM, que adota uma busca mais aleatória por meio de seus operadores.
Os algoritmos ESM-EM, GA-EM e OMR-EM foram avaliados considerando o compro- misso entre qualidade do modelo obtido e tempo de execução. Para realizar uma comparação justa, todos os algoritmos foram implementados em MATLAB e executados no mesmo compu- tador (Opteron 2GHz, 24Gb de RAM) executando apenas o sistema operacional em paralelo.
Um aspecto prático relevante a ser ilustrado é que o uso de AEs para otimizar parâmetros de um GMM, incluindo a estimação da estrutura do modelo, pode ser computacionalmente mais eficiente e eficaz do que o uso de múltiplas repetições do EM. A literatura não apresenta uma avaliação apropriada de tal aspecto. Para fazer esta análise, OMR-EM foi executado com
np = 10 e o tempo de execução de cada passagem completa sobre o número de grupos foi
guardado, bem como o melhor modelo encontrado até o momento. Na sequência, os AEs (ESM-EM e GA-EM) são executados até o tempo de execução deles seja igual ao necessário pelo OMR-EM (com np = 10) — armazenando as soluções intermediárias. Desta forma, as
melhores soluções de cada algoritmo sob determinada restrição de tempo — considerando o tempo gasto pelo OMR-EM para diferentes valores de np— podem ser comparadas. Em outras
palavras, np é utilizado como unidade de tempo. O tempo gasto na otimização de parâmetros
do GA-EM não é considerado no tempo de execução reportado. Neste sentido, os resultados do GA-EM podem ser considerados otimistas.
A Tabela 3.5 sumariza o desempenho geral de cada algoritmo por meio dos ranking médios — considerando 10 repetições para todas as bases de dados. Por exemplo, o menor valor obtido pelo GA-EM para np = 1 (1,47 na 2ª linha e 4ª coluna) indica que, computando a média sobre
todas as bases de dados, o algoritmo GA-EM foi capaz de obter o menor valor de MDL para cada restrição de tempo. Por meio destes resultados, é possível verificar que existe um ranking consistente dos três algoritmos para np ≤ 7: GA-EM, ESM-EM, e OMR-EM. Para np > 7,
ESM-EM obtém o melhor ranking. Também é possível verificar que os AEs podem ser mais computacionalmente eficientes do que múltiplas repetições do EM. Finalmente, o algoritmo ESM-EM, que não possui parâmetros críticos, é competitivo com o GA-EM mesmo quando os parâmetros do GA-EM foram otimizados a priori. Conforme discutido anteriormente, tal
Tabela 3.5: Ranking médio obtido por cada algoritmo — considerando o valor de MDL obtido pelo melhor modelo para cada valor de np.
np OMR-EM ESM-EM GAEM
1 2,51 2,01 1,47 2 2,51 1,83 1,66 3 2,46 1,89 1,66 4 2,41 1,90 1,69 5 2,30 1,93 1,77 6 2,24 1,94 1,81 7 2,16 1,94 1,90 8 2,14 1,89 1,97 9 2,14 1,87 1,99 10 2,14 1,90 1,96
procedimento de otimização requer algum conhecimento a priori do problema — dificilmente disponível na prática — e recursos computacionais consideráveis. Conforme esperado, quanto mais recursos computacionais estão disponíveis, i.e., conforme se aumenta np, a diferença entre
a performance do OMR-EM e AEs é reduzida, dado que é dado tempo suficiente (ou chances suficientes no caso do OMR-EM) para se alcançar ou chegar perto do ótimo global.
Após tais observações gerais, serão analisados alguns resultados específicos. A Figura 3.9 apresenta alguns resultados representativos para seis bases de dados. Nestes gráficos, o eixo y mostra os valores de MDL (divididos pelo número de objetos), enquanto que o eixo x representa o número de repetições, np, executadas pelo OMR-EM.
Para a base de dados 49Gauss (Figura 3.9(a)), o algoritmo ESM-EM obteve melhores resul- tados do que ambos OMR-EM e GA-EM. Resultados similares foram observados para a base de dados 9Gauss. Considerando np ≥ 2, ESM-EM obteve melhores resultados com menor va-
riância. Como np = 2 pode ser considerado um valor muito pequeno na prática, especialmente
para uma base de dados com 4.900 objetos, a eficiência computacional do ESM-EM é atraente. Na base de dados Pendigits (Figura 3.9(b)), OMR-EM tem maior variância para np ≤ 4 quando
comparado com os AEs. A capacidade dos AEs em gerar boas soluções consistentemente em tão pouco tempo é evidenciada. Além disso, novamente o ESM-EM forneceu soluções melho- res que o (otimizado) GA-EM. Os resultados para a base de dados c0.5-k12M4 (Figura 3.9(c)) e c1.0-k12M8 (Figura 3.9(d)) apresentam uma tendência similar, mas com o GA-EM apresen- tando resultados iguais ou ligeiramente melhores que o ESM-EM. Porém, como o ESM-EM não possui parâmetros críticos, ele pode ser mais interessante que o GA-EM até para estes cenários. Para a base de dados ω0.1-k12M4, ESM-EM foi capaz de obter boas soluções em uma quantidade pequena de tempo (np = 4) e resultados competitivos quando mais tempo
de processamento estava disponível. Resultados similares foram obtidos para a base de dados
ω0.1-k12M8. Os resultados para a base de dados ω0.01-k12M8 são um exemplo de como ine-
ficiente o OMR-EM pode ser quando comparado com busca evolutiva (guiada). Uma tendência similar pode ser observada quando compara-se o ESM-EM e o GA-EM. Especificamente, nova- mente o ESM-EM convergiu rapidamente, mas neste o caso os outros algoritmos não obtiveram soluções melhores.
3.5 Considerações Finais 57 1 2 3 4 5 6 7 8 9 10 5.305 5.317 5.330 OMR−EM GA−EM ESM−EM np MDL value divided by # of objects V al ore s de MDL di vi di dos pe lo núm ero de obj et os (a) 49Gauss 1 2 3 4 5 6 7 8 9 10 3.473 3.479 3.485 OMR−EM GA−EM ESM−EM np MDL value divided by # of objects V al ore s de MDL di vi di dos pe lo núm ero de obj et os (b) Pendigits 1 2 3 4 5 6 7 8 9 10 7.68 7.70 7.72 OMR−EM GA−EM ESM−EM np MDL value divided by # of objects V al ore s de MDL di vi di dos pe lo núm ero de obj et os (c) c0.5-k12M4 1 2 3 4 5 6 7 8 9 10 14.020 14.135 14.250 OMR−EM GA−EM ESM−EM np MDL value divided by # of objects V al ore s de MDL di vi di dos pe lo núm ero de obj et os (d) c1.0-k12M8 1 2 3 4 5 6 7 8 9 10 7.575 7.593 7.610 OMR−EM GA−EM ESM−EM np MDL value divided by # of objects V al ore s de MDL di vi di dos pe lo núm ero de obj et os (e) ω0.1-k12M4 1 2 3 4 5 6 7 8 9 10 13.960 13.985 14.010 OMR−EM GA−EM ESM−EM np MDL value divided by # of objects V al ore s de MDL di vi di dos pe lo núm ero de obj et os (f) ω0.01-k12M8
Figura 3.9: Boxplot dos valores de MDL (divididos pelo número de objetos) obtidos por cada algoritmo. O eixo x indica o número de repetições (np) realizadas pelo OMR-EM.
3.5
Considerações Finais
Neste capítulo, foi apresentada uma contribuição desta tese, o algoritmo Evolutionary Split & Merge Algorithm for Expectation Maximization(ESM-EM) (Covões e Hruschka, 2011). Este algoritmo, desenvolvido com base no Fast Evolutionary Algorithm for Clustering (F-EAC) (Se- ção 2.4.1.1) e na literatura de SM (Seção 2.3), utiliza os operadores de união e divisão de grupos para auxiliar na evolução dos modelos. Além disso, este algoritmo busca ser uma alter- nativa aos algoritmos evolutivos existentes nesta linha de pesquisa (descritos na Seção 2.4.2), e foi projetado de tal forma a fazer melhor uso das informações do modelo durante as gera- ções. Por meio de experimentos com bases de dados sintéticas, foram analisadas diferentes variantes do ESM-EM obtidas alterando alguns de seus componentes. Foi possível demonstrar
que o ESM-EM é uma alternativa viável ao AE estado-da-arte, denominado de GA-EM (Pern- kopf e Bouchaffra, 2005), por ser capaz de prover resultados pelo menos tão bons quanto o GA-EM sem necessitar de otimização de parâmetros e com custo computacional similar. As comparações e análises descritas foram devidamente formalizados em um artigo em revisão em periódico indexado.
CAPÍTULO
4
Agrupamento de Dados com Restrições
4.1
Considerações Iniciais
A área de Agrupamento de Dados com Restrições (ADR) — da terminologia em inglês Constrained Clustering— cresceu pela necessidade de se incorporar informações sobre a par- tição desejada, quando disponíveis, no processo de agrupamento de dados (Basu et al., 2008). O uso de restrições em algoritmos de agrupamento (pela comunidade de Estatísticos) data das décadas de 70 e 80 (Gordon, 1973; Mahajan e Jain, 1978; DeSarbo e Mahajan, 1984). Nas comunidades de aprendizado de máquina e Mineração de Dados (MD) o interesse ocorreu mais recentemente (Wagstaff e Cardie, 2000; Wagstaff et al., 2001) e tem como foco o uso de restri- ções sobre pares de objetos (Basu et al., 2008). As restrições mais comumente encontradas na literatura são:
• Sobre pares de objetos:
– Must-Link (ML) (Wagstaff e Cardie, 2000): Indica que dois objetos devem ser agru- pados no mesmo grupo.
– Cannot-Link (CL) (Wagstaff e Cardie, 2000): Indica que dois objetos devem perten- cer a grupos diferentes.
• Sobre grupos:
– Balanced Clusters (Banerjee e Ghosh, 2006): Indica que todos os grupos da parti- ção devem ter aproximadamente a mesma cardinalidade, i.e., o mesmo número de objetos.
– Minimum Cluster Size (Basu et al., 2008): Indica que cada grupo deve ter uma cardinalidade mínima.
• Sobre partições:
– Non-Redundant Clustering (Gondek e Hofmann, 2004): busca-se partições diferen- tes (não redundantes) em relação a uma determinada partição de referência.
Neste trabalho, tem-se como premissa o uso das restrições ML e CL por serem mais comuns e, portanto, as mais estudadas na literatura. Diversas aplicações podem ter seu conhecimento de domínio representado por meio de restrições ML e CL. Dentre as mencionadas na litera- tura, encontram-se: reconhecimento de pista em uma rodovia via GPS (Wagstaff et al., 2001), segmentação de imagens para a navegação de robôs (Davidson e Ravi, 2005b), agrupamento de genes (Zeng et al., 2007) e análise de imagens de ressonância magnética funcional (Phillips et al., 2013).