Abordagens Evolutivas para Agrupamento Relacional de Dados

• Processo: 08/00932-2
• Modalidade de apoio: Bolsas no Brasil - Mestrado
• Data de Início da vigência: 01 de março de 2009
• Data de Término da vigência: 28 de fevereiro de 2010
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação
• Pesquisador responsável: Ricardo José Gabrielli Barreto Campello
• Beneficiário: Danilo Horta
• Instituição Sede: Instituto de Ciências Matemáticas e de Computação (ICMC). Universidade de São Paulo (USP). São Carlos , SP, Brasil
• Vinculado ao auxílio: 06/50231-5 - Inteligência computacional em mineração de dados e suas aplicações, AP.JP
• Assunto(s): Mineração de dados Computação evolutiva
• Palavra(s)-Chave do Pesquisador: Agrupamento de Dados (clustering) | computação evolutiva | Mineração de Dados

Resumo

Agrupamento não supervisionado (clustering) é um dos problemas centrais na área de mineração de dados. A solução deste problema muitas vezes constitui o objetivo final da tarefa de mineração em si, mas em muitos casos pode também ser parte da solução de outros problemas relacionados, como classificação e extração de regras. O objetivo do agrupamento de dados é particionar os dados em grupos de objetos mais similares entre si do que com relação aos objetos dos demais grupos, segundo alguma medida de similaridade ou dissimilaridade. A literatura sobre o problema de agrupamento de dados é extensa, sendo que por várias décadas diversos algoritmos de natureza, características e propósitos distintos têm sido propostos e investigados. Um problema ainda hoje crítico no que tange à tarefa de agrupamento diz respeito à estimação do número mais natural de grupos contidos em um determinado conjunto de dados. A maioria dos algoritmos requer, a priori ou a posteriori, que o número de grupos seja definido pelo usuário. Exemplos são os populares algoritmos das k-médias (k-means) e EM (Expectation Maximization), bem como os diferentes métodos de agrupamento hierárquico. Uma abordagem para esse problema, que tem ganho crescente importância nos últimos anos, é a utilização de algoritmos evolutivos dedicados exclusivamente ao problema de agrupamento de dados. O orientador da presente proposta de mestrado tem trabalhado ativamente no estudo e desenvolvimento de algoritmos evolutivos para agrupamento de dados. Todos os algoritmos desenvolvidos até o momento, no entanto, são apropriados para bases de dados descritas por atributos numéricos, uma vez que os algoritmos e seus operadores se sustentam fortemente no conceito de centróides como protótipos de grupos. No sentido de ampliar a aplicabilidade desses algoritmos também para bases de dados envolvendo atributos categóricos, pretende-se inicialmente desenvolver novas versões de operadores evolutivos para agrupamento de dados que sejam baseados no conceito de medóides (objetos representativos) como protótipos de grupos, permitindo assim a utilização dos algoritmos evolutivos resultantes em um espectro mais amplo de cenários de aplicação. Sabe-se que o uso de medóides, além de permitir a manipulação de atributos categóricos, pode também aumentar a robustez dos algoritmos de agrupamento a ruído e outliers. Uma alternativa ao uso de medóides para o tratamento de atributos categóricos é o uso de operadores relacionais, ou seja, que operem apenas sobre uma matriz de similaridade ou dissimilaridade entre os objetos da base de dados, não sobre os objetos em si. Algoritmos relacionais apresentam várias propriedades importantes que vão além da capacidade de manipular atributos categóricos. Por exemplo, são muito úteis quando não se dispõe da base de dados propriamente dita, mas apenas da matriz de similaridades ou dissimilaridades entre seus objetos (e.g., por questões de sigilo). Por esta razão, pretende-se também neste projeto investigar a possibilidade de desenvolver operadores evolutivos para agrupamento de dados que sejam relacionais.

Publicações acadêmicas

(Referências obtidas automaticamente das Instituições de Ensino e Pesquisa do Estado de São Paulo)

HORTA, Danilo. Abordagens evolutivas para agrupamento relacional de dados. 2010. Dissertação de Mestrado - Universidade de São Paulo (USP). Instituto de Ciências Matemáticas e de Computação (ICMC/SB) São Carlos.