Para determinar a quantidade de regiões que devemos dividir os dados é importante ter em mente que a quantização vetorial objetiva duas coisas: diminuir o número de pontos usando os centros de cada região auxiliar; e capturar a informação estatística embutida nos dados dessas regiões.
Sendo assim, a ideia mais intuitiva é escolher um valor alto para a quantidade de RA de modo que a quantidade de pontos em cada uma decresça e, por consequência, elas se tornem mais homogêneas. Com as regiões menores e mais homogêneas, os centros se tor- nam elementos mais simbólicos daquelas regiões. Por outro lado, quanto menos pontos houver, menor vai ser a amostra daquela parte do espaço de características e menor a sig- nificância estatísticas das RA. O desafio se torna encontrar uma quantidade que relacione a homogeneidade e a representatividade dos dados.
Existem ainda algumas outras questões relacionadas ao aumento indiscriminado na quantidade de RA. Uma delas é que dependendo da distribuição dos dados, com uma quantidade grande de RA, o montante de pontos pode ficar pequeno o suficiente para tornar difícil encontrar relações estatísticas entre eles. Ou ainda, o formato das RA pode distorcer a relação que existe entre regiões vizinhas.
Para ilustrar isso, considere os dois grupos mostrados na Figura5.6(a). Pela natureza alongada dos grupos e proximidade entre eles, para separá-los corretamente, a quantidade de AR tem que ser suficiente para que o formato delas faça com que os pontos do mesmo
grupo tenham uma influência maior que os pontos de outro grupo (Figura5.6(c)). Caso contrário, pode ser que relações falsas sejam criadas entre elementos de grupos diferentes (Figura5.6(e)). −8 −6 −4 −2 0 2 4 −5 −4 −3 −2 −1 0 1 2 3 4 5 off (a) 3 4 1 2 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 1.1 (b) −10 −8 −6 −4 −2 0 2 4 6 −6 −4 −2 0 2 4 6 off 1 2 3 4 (c) 1 4 2 6 3 5 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 1.1 (d) −10 −5 0 5 −6 −4 −2 0 2 4 6 off 1 2 3 4 5 6 (e)
Figura 5.6: Efeitos da escolha errada do número de RA.
Para tentar determinar qual o número de regiões auxiliares mais indicada para cada conjunto de dados foi desenvolvida uma estratégia baseada no comportamento da FCA1
quando a quantidade de RA é alterada. Mais precisamente, se executarmos o algoritmo utilizando um determinado intervalo de valores referente a quantidade de regiões auxili- ares e observarmos o comportamento da FCA1notamos que o seu valor se estabiliza em
Em muitas situações, essas regiões de estabilidade indicam que o aumento na quanti- dade de RA não provoca uma melhora substancial na função custo. Assim, usar um valor demasiadamente alto de RA sem necessidade só aumenta o tempo de execução e a proba- bilidade de erros. A Figura5.7ilustra a análise em questão, mostrando que ao dividir o conjunto de dados a esquerda em dois grupos, a FCA1 se estabiliza em um determinado
ponto. −1.5 −1 −0.5 0 0.5 1 1.5 2 −0.5 0 0.5 1 1.5 2 0 5 10 15 20 25 30 35 40 45 50 0 0.002 0.004 0.006 0.008 0.01 0.012 0.014 0.016 0.018 ak CEF RA FCA 1
Figura 5.7: Análise sobre o número de regiões auxiliares.
A partir disso, é possível determinar um intervalo experimental para escolher a me- lhor quantidade de RAs. Nesse sentido, um intervalo definido a partir do ponto onde a FCA se estabiliza até dez unidades para frente é usado para realizar experimentos prévios. A quantidade final de RAs é determinada pelo valor que produzir a menor FCA1 dentro
daquele intervalo. Por exemplo, na Figura5.7, o intervalo usado é de 18 (início da esta- bilização) a 28 (dez unidades posteriores). A quantidade de RAs que seria usada durante os experimentos finais é de 26 (menor valor da FCA1).
É importante ressaltar que o procedimento descrito anteriormente só é válido quando existe uma estabilização no comportamento da FCA1quando a quantidade de RAs é au-
mentada. No demais casos, onde essa estabilização não ocorre, o gráfico da análise ainda é utilizado, mas para identificar intervalos maiores onde a FCA1 apresenta platôs. Da
mesma maneira, dentro desses intervalos, a quantidade final é aquela que apresenta me- nor valor da FCA1.
Note que esse é um procedimento de validação e pode ser realizado para qualquer dos algoritmo propostos, mesmo que eles usem durante o agrupamento a FCA2(AHTI e
AGTI). Isso é possível, por que depois de gerar um agrupamento usando a FCA2 ainda
é possível calcular qual o custo da partição perante a FCA1. É interessante usar a FCA1,
existentes, enquanto que a FCA2é uma medida mais local.
5.3
Considerações Finais
Neste capítulo foram destacados os dados utilizados na parte experimental da pro- posta de trabalho. Foram descritos os conjuntos de dados em dois tipos: artificiais e reais. A primeira categoria foi representada por conjuntos de dados que simulam situações do mundo real onde a complexidade espacial, muitas vezes, apresenta comportamento mul- tivariado. A última categoria possui dados de alguns domínios como reconhecimento de padrões, análise especialista e segmentação de imagens.
Todos os parâmetros utilizados pelos algoritmos testados são definidos. Além disso, são definidos os critérios para análise dos agrupamentos gerados, sendo o índice corrected Rand para os dados que possuem informação prévia sobre sua rotulagem e a exposição das imagens construídas para a segmentação de imagens.
A escolha do número de regiões auxiliares é uma necessidade básica nos algoritmos TI, mas a escolha não precisa ser feita de maneira arbitrária. Neste capítulo foi mostrada uma metodologia para guiar a escolha desse parâmetro.
No próximo capítulo serão discutidos os resultados obtidos a partir dos experimentos descritos aqui.
Resultados
Como descrito no capítulo anterior, experimentos foram realizados com o objetivo de testar e comparar os métodos de agrupamento propostos. Os resultados serão expostos separadamente para os dados sintéticos e reais, uma vez que cada aplicação possui suas próprias particularidades a serem analisadas.
Existem algumas maneiras de realizar a análise de agrupamentos sobre os dados. Neste trabalho, o intuito é verificar a eficiência do método proposto em agrupar os dados. Mais precisamente, em recuperar a estrutura real dos conjuntos de dados. Desse modo, são analisadas as partições obtidas por cada algoritmo utilizando o índice corrected Rand (cR - Seção3.4), em que os valores indicam quão próximos estão os agrupamentos obtidos aos dados reais.
O valores de cR referentes às partições obtidas por todos os algoritmos são exibidos em tabelas para que seja possível comparar os seus desempenhos. Adicionalmente, foram construídas visualizações das partições analisadas e inseridas no ApêndiceC.
Para fins de esclarecimentos, durante a análise dos resultados, o termo “classe” é utilizado para referenciar os grupos já definidos previamente através de rótulos que iden- tificam cada objeto. O termo “grupo” é usado para fazer referência aos grupos gerados pelos algoritmos durante o processo de agrupamento.
6.1
Análise dos Conjuntos de Dados Sintéticos
Com o objetivo de criar uma referencial de desempenho, primeiro, serão mostrados os resultados referentes aos algoritmos clássicos de agrupamento. A Tabela6.1exibe os valores de cR relativos às partições produzidas pelos algoritmos mistura finita de Gaussi-
Conjunto de dados MFG KM LS SPC aggregation 0,83 0,76 0,80 0,99 atom 0,01 0,20 1,00 0,23 circles 0,51 0,40 1,00 0,52 compound 0,63 0,54 0,74 0,83 ee 0,37 0,40 1,00 1,00 eee 0,03 0,03 1,00 0,01 md 0,07 0,00 0,01 -0,06 oa -0,01 0,00 0,00 -0,01 proximity 0,26 0,07 0,03 0,03 spirals 0,04 0,02 1,00 1,00 springs 0,00 0,00 0,00 0,00 twodiamonds 0,00 1,00 0,00 1,00 wingnut 0,89 0,86 1,00 0,95 xp 0,01 0,86 1,00 1,00
Tabela 6.1: Desempenho dos algoritmos clássicos de agrupamento.
anas (MFG), k-means (KM), hierárquico com ligação simples (LS) e algoritmo espectral (SPC) para todas as bases de dados artificiais.
Nesse contexto, o algoritmo LS foi escolhido por possuir a mesma natureza hierár- quica do algoritmo proposto HTI. O SPC e MFG utilizam o princípio de modelos (kernels) estatísticos para realizar o agrupamento, sendo completamente indicados para compara- ção já que todos os métodos propostos são também baseados em modelos estatísticos. Por fim, o KM é um método que usa centros como guia de funcionamento, o que tam- bém acontece com todos os métodos propostos. Além disso, essas técnicas representam diferentes critérios de agrupamento amplamente utilizados na literatura, que os levam a serem nomeados de “clássicos”.
Na Tabela6.1, para cada conjunto de dados é destacado em negrito o índice da técnica que atingiu o melhor desempenho para aquela base. Em casos de empate, são destacados todos os valores iguais.
Em princípio, podemos notar que para tais algoritmos, os resultados só são satisfa- tórios nos casos em que a função critério de agrupamento é adequada aos dados. Mais especificamente, o KM conseguiu bons resultados somente em alguns conjuntos de dados (aggregation, twodiamonds, wingnut e xp). Três dessas bases possuem uma mesma característica em comum: serem totalmente balanceadas na distribuição de pontos por classe. No caso da base aggregation, o algoritmo só consegue agrupar corretamente os dados das classes que possuem distribuição elíptica e compacta (isso pode ser constatado
na partição referente a essa base mostrada no ApêndiceC).
Esse comportamento é previsível para o KM, uma vez que o algoritmo minimiza o erro quadrático médio como critério de agrupamento, favorecendo grupos com pouca dispersão e com formato elíptico. Nos demais conjuntos, onde a dispersão é maior, a separação entre grupos não é tão evidente ou a complexidade espacial é maior, o KM não consegue atingir bons resultados. De fato, o KM só conseguiu recuperar a estrutura completa (cR = 1) de uma das bases de dados.
Na prática, para conjuntos de dados que possuem grupos que não podem ser linear- mente separados, a utilização do KM é inapropriada. Apesar de sua baixa complexidade computacional, essa técnica não consegue separar os grupos quando eles estão, por exem- plo, inseridos um dentro do outro (atom e spirals, por exemplo). Isso acontece mesmo quando a separação entre os grupos é bem clara.
Pela natureza da maior parte dos dados, o algoritmo LS atingiu bons resultados em boa parte das bases (7 de 14). Uma característica comum entre todas essas bases é que as classes são completamente separadas umas das outras (possuem um grande vale entre elas) e os dados possuem formato alongado, criando “correntes”. No entanto, é importante notar que quando existe qualquer pertubação na separação das classes ou, simplesmente, quando um ponto de uma classe está mais próximo de qualquer ponto de outra classe, o desempenho cai drasticamente. Esse comportamento é melhor visto nas bases md, oa, proximitye twodiamonds onde a região inter-grupos é muito estreita. Nesses casos, a tendência é que os grupos se aglomerem em um só, deixando poucos pontos formarem outro grupo. A sensibilidade a ruídos ou outliers do LS já foi reportada por trabalhos científicos anteriormente (JAIN; DUBES,1988;SOUTO et al.,2008).
A MFG vem mostrando bons resultados no contexto de agrupamento em diferentes áreas como reportado na Seção 3.3.3. No entanto, por ser uma técnica paramétrica, a suposição levantada para agrupar os dados, muitas vezes, não é suficiente para gerar boas partições. De fato, quando a complexidade espacial dos dados é elevada, a suposição de Gaussianidade faz com que os agrupamentos não estejam de acordo com a realidade. Nesse contexto, nos conjuntos de dados que possuem somente parte dos seus grupos com natureza Gaussiana, a MFG tem seu desempenho deteriorado devido a falhas no agrupa- mento das classes com distribuição não-normal. Por esse motivo, a MFG só conseguiu resultados satisfatórios em poucas bases de dados. De fato, a técnica não conseguiu atingir uma partição perfeita (cR = 1,00) em nenhuma das bases de dados.
lhante ao LS atingindo bons resultados para algumas bases de dados (6 de 14). O SPC leva em consideração algumas estatísticas dos dados e, por isso, consegue realizar bons agrupamentos, mesmo quando os dados possuem distribuição espacial mais complexa, como no caso de aggregation e spirals. No entanto, como é limitada a estatísticas de primeira e segunda ordem (média e variância), não atinge bons resultados em bases como atom, onde os grupos distintos possuem mesma média, mas variâncias diferentes, e proximity que possui grupos com diferentes densidades, o que distorce o cálculo de médias individuais de cada grupo (dificuldade também encontrada pelo KM e mostrada na Seção3.3.2).
Dentre esses algoritmos, o LS obteve o melhor desempenho, atingindo o maior nú- mero de partições com boa qualidade. Em seguida, o algoritmo SPC mostrou desempenho regular sendo indicado para metade das bases de dados. Por último, o KM e MFG ficaram com os piores resultados. Como mencionado, a suposição de Gaussianidade prejudica o funcionamento desses dois métodos em situações mais complexas.
Constata-se, então, que cada um desses algoritmos só são indicados para tipos de dados específicos. Ou seja, quando os dados possuem natureza homogênea de distribuição estatística e se encaixam no seus respectivos critérios de agrupamento. Nos demais casos, onde esse comportamento pode variar dependendo da região do espaço de características, o uso de técnicas que avaliam a estatística completa dos dados é mais indicado.
Para isso, foram desenvolvidas técnicas e medidas de agrupamento baseadas em des- critores teóricos da informação que buscam usar toda a estatística embutida nos dados para produzir agrupamentos que estejam de acordo com a realidade dos dados. Nesse contexto, para avaliar a proposta de trabalho, os resultados (em termos de CR) dos al- goritmos utilizando TI podem ser visualizados na Tabela 6.2. Da mesma maneira que os resultados referentes aos algoritmos clássicos, os melhores índices para cada base de dados está destacada em negrito. Adicionalmente, ao lado de cada resultado, o número de regiões auxiliares que cada algoritmo usou para gerar a partição é informado ao lado.
Em linhas gerais, está claro que, usando o número apropriado de regiões auxiliares, foi possível resgatar a estrutura real dos dados na sua perfeição em pelo menos 11 dos 14 conjuntos de dados. Nas bases onde não foi possível atingir uma total concordância entre a partição gerada e os dados reais, o valor CR foi muito próximo do máximo desejado.
Isso é válido para qualquer nível de dificuldade imposta, desde as consideradas mais simples (bases com dados balanceados e com clara separação entre os dados) até para os casos mais complexos, onde existe a presença de dados ruidosos e dispersões distintas
Conjunto de dados AHTI AHcTI APLTI AGTI cR RA cR RA cR RA cR RA aggregation 1,00 30 1,00 30 0,99 30 0,99 20 atom 1,00 15 1,00 12 1,00 17 1,00 12 circles 1,00 80 1,00 80 1,00 85 1,00 70 compound 0,88 28 0,85 35 0,88 35 0,92 25 ee 1,00 30 1,00 25 1,00 35 1,00 25 eee 1,00 25 1,00 25 1,00 30 1,00 25 md 0,98 54 0,98 55 0,95 21 0,96 20 oa 1,00 65 1,00 55 1,00 55 1,00 55 proximity 0,97 30 0,97 20 0,94 30 0,98 20 spirals 1,00 37 1,00 40 1,00 35 1,00 32 springs 1,00 60 1,00 70 1,00 80 1,00 70 twodiamonds 1,00 41 1,00 20 1,00 20 1,00 30 wingnut 1,00 50 1,00 30 1,00 16 1,00 30 xp 1,00 30 1,00 30 1,00 25 1,00 20
Tabela 6.2: Desempenho dos algoritmos propostos.
nos grupos. Ou seja, os resultados mostram que os algoritmos propostos funcionam nos casos em que LS, MFG, SPC e KM são indicados, mas também são uma melhor opção para os demais casos, onde eles falham. Com isso, fica claro que os algoritmos basea- dos em TI são genericamente mais robustos, principalmente, pelo fato de conseguirem capturar a estatística embutida nos dados e agrupar cada parte dos dados de acordo com suas características específicas. Isso pode ser visto mais claramente em bases como md e proximityque possuem grupos multi-densidade.
Note que, de acordo com a visualização das imagens sintéticas mostradas nas Figuras
5.1,5.2e5.3, as bases onde o índice cR não atingiu o valor máximo, possuem pontos que poderiam pertencer a mais de uma classe. Desse modo, o que causa a divergência entre a estrutura encontrada e a partição real foi a escolha do rótulo atribuído ao dado em questão. Por outro lado, para a maior parte dos pontos, onde existe uma clara caracterização da classe, o algoritmo os atribuiu aos grupos devidos.
Quando comparados aos métodos clássicos, o desempenho dos algoritmos propostos sempre foi igual ou superior. Os casos onde o desempenho é equivalente estão relaciona- dos aquelas bases onde o índice cR teve valor máximo. Além disso, a robustez perante a variabilidade de características nos dados fica comprovada pelo alto desempenho em todos os casos. Situação que não ocorre para os demais algoritmos que, apesar de terem bons desempenhos em algumas bases, falham completamente em outras.
Essa robustez pode ser melhor visualizada na Figura 6.1, onde um gráfico com a média de desempenho de cada algoritmo para todas as bases é mostrada juntamente com o desvio padrão, que indica a variabilidade nos resultados.
0 0.2 0.4 0.6 0.8 1 MFG KM LS SPC AHTI
AHcTI APLTI AGTI
Figura 6.1: Índices médios de cR com os respectivos desvios-padrões.
O gráfico mostra que, além de melhores resultados, os algoritmos TI são mais con- sistentes para as várias possibilidades de situações referentes à caracterização do espaço amostral de entrada. Note que os algoritmos clássicos possuem média bem inferior e com altos desvios-padrões mostrando a instabilidade desses métodos quando submetidos a di- ferentes situações. Se tomarmos o LS como exemplo, o algoritmo apresentou na maioria dos conjuntos de dados desempenhos extremos, ou seja, partições perfeitas ou partições com grupos gerados ao acaso, reforçando a ideia que os algoritmos existentes são indica- dos para dados com distribuições específicas.
Entre os algoritmos propostos, todos mostraram desempenhos equivalentes para to- das as bases de dados. Nas situações onde houve diferença, ela foi mínima e provocada por particularidades do algoritmo. Mais especificamente, o APLTI não requer o número de grupos que deve estar presente na partição produzida e, por isso, em algumas situa- ções em que uma classe pode conter pequenas diferenças internas na sua caracterização (indicando subclasses), esses métodos acabam por produzir partições que refletem essa realidade. Nesses casos, a FCA referente aos desmembramento de uma classe, em geral, é mais próxima do ponto ótimo. Note que isso, muitas vezes, não pode ser visto como uma desvantagem, uma vez que isso não reflete um agrupamento errado mas, apenas,
divergente da rotulagem adotada.
Além do bom desempenho em recuperar a estrutura real dos dados, os algoritmos propostos também mostraram um ganho significativo de custo computacional relativo ao tempo de execução. Se considerarmos a base circles como exemplo, o tempo de execu- ção utilizando o PIC original (PICp) para conseguir agrupar os dados seria muito superior ao atingido com o PICr, uma vez que para o primeiro caso, o potencial teria que ser calcu- lado entre todos os 5032 pontos existentes. Na situação proposta, foram usadas 80 regiões auxiliares, o que reduziu o tempo de execução drasticamente.
Os métodos propostos conseguiram atingir bons resultados, principalmente, pelos fatos mencionados na Seção4.1, em que o potencial de informação cruzado está altamente relacionado com entropia e informação mútua. Isso significa que quando maximizamos o PICr entre as regiões auxiliares, estamos minimizando a entropia interna de cada grupo e, por sua vez, maximizando a divergência Cauchy-Schwartz (CS) entre os grupos. Assim, as partições criadas pelos algoritmos propostos possuem entropia mínima intra-grupo e divergência máxima inter-grupos.
Por entropia mínima intra-grupo, devemos entender que a aleatoriedade interna dos grupos é baixa, implicando em grupos estatisticamente relacionados e compactados ao extremo. Se considerarmos que divergência CS está relacionada à informação mútua, cada grupo possui o mínimo de informação sobre os demais, significando que eles possuem pouca relação estatística e deveriam, de fato, estar separados.
Com o objetivo de deixar mais claros os argumentos apontados, dois estudos de caso foram usados para ilustrar o bom desempenho dos métodos baseados em TI quando com- parados com os demais métodos.