Modelos da física estatística para agrupamento não supervisionado de dados

Abstract

Nesta dissertação, o problema do agrupamento não-supervisionado de dados ou padrões é investigado, com enfoque em dois recentes métodos fundamentados na Física Estatística. Basicamente, estes métodos associam os elementos do banco de dados aos elementos de um sistema físico, os quais se acoplam através de uma interação de alcance finito. O critério de similaridade entre os dados, necessário para a formação dos agrupamentos, está associado a uma grandeza física do sistema. O primeiro método, chamado agrupamento super-paramagnético, associa cada padrão (matematicamente definido como um ponto no espaço de atributos D-dimensional) a uma variável de spin do modelo de Potts ferromagnético não homogêneo. Neste caso, dois pontos pertencem ao mesmo cluster quando a correlação spin-spin, no equilíbrio termodinâmico a uma temperatura T, está acima de um certo limiar. No segundo método, o conjunto de dados é associado a um sistema de mapas caóticos acoplados e as classificações emergem da sincronia destes mapas. A fundamentação teórica e as implementações computacionais destes dois métodos são apresentadas e comparativamente discutidas. Os métodos são aplicados a três conjuntos de dados sintéticos que, por razões de visualização, são formados por padrões de pontos em um espaço bidimensional limitado. Os padrões são especificamente escolhidos para testar e comparar as potencialidades dos métodos empregados. O agrupamento superparamagnético, por estar fundamentado em um sistema de spins ferromagnético, mostra-se mais robusto com a relação aos ruídos de fundo ou background, evitando a agregação aos clusters de possíveis "trilhas"(de caráter unidimensional) que se formam no background. Em decorrência, o agrupamento super-paramagnético identifica os clusters através de suas densidades e correlações locais com maior precisão, sendo apropriado para identificar e delimitar formas mais compactas eliminando ruídos de fundo nas fronteiras. Por outro lado, o método por associação a mapas caóticos possui maior sensibilidade para identificar estruturas com caráter unidimensional subjacentes aos ruídos de fundo, por conta das conexões locais terem grande influência na transmissão das correlações, sendo, portanto mais eficiente na classificação de clusters com estruturas mais complexas. Computacionalmente, o agrupamento através de mapas caóticos mostrou-se ser é 265 vezes mais rápido que o agrupamento super-paramagnético quando aplicado aos conjuntos de dados aqui selecionados, tendo em vista que o último carece de realizar simulações numéricas através do método Monte Carlo estabilizando termicamente o sistema para cada valor de temperatura considerado