Data Classification in Complex Networks

• Grant number: 09/02985-9
• Support Opportunities: Scholarships in Brazil - Master
• Start date: August 01, 2009
• End date: April 30, 2011
• Field of knowledge: Physical Sciences and Mathematics - Computer Science
• Principal Investigator: Zhao Liang
• Grantee: Lilian Berton
• Host Institution: Instituto de Ciências Matemáticas e de Computação (ICMC). Universidade de São Paulo (USP). São Carlos , SP, Brazil

Abstract

Recentemente, com o aumento do poder computacional e a disponibilidade de dados sobre redes reais, as redes complexas surgiram como uma nova e poderosa maneira de representação e abstração de dados capaz de capturar as relações espaciais, topológicas, funcionais, entre outras características presentes em muitas bases de dados. Dentre as várias abordagens para a análise de dados, destacam-se a classificação e a clusterização. A classificação de dados permite atribuir uma qualidade (classe) aos dados, baseado nas características de seus atributos. Já a clusterização é indicada para explorar a estrutura dos dados, como grupos ou hierarquias entre grupos, cujas classes não são previamente conhecidas. Métodos de clusterização baseados em redes complexas, também conhecidos como detecção de comunidades, têm sido extensivamente explorados na literatura. Por outro lado, a classificação de dados baseada em redes complexas ainda é pouco estudada. Tendo em vista os benefícios da representação de grandes bases de dados e a revelação de estruturas topológicas por meio de redes complexas, o presente projeto prevê o desenvolvimento de métodos de classificação de dados baseados em redes complexas. A abordagem que será considerada é inspirada em um classificador que usa uma rede K-associada, a qual é capaz de representar relações de similaridade entre classes de dados via extração da medida de pureza de cada componente da rede construída. Na nova técnica de classificação de dados a ser desenvolvida, considera-se não apenas o fator de pureza de cada classe, mas também extensões de classes formadas. Observe que os dois fatores são contraditórios, pois o aumento da pureza tende a diminuir a extensão da classe e vice-versa. Uma boa classificação sobre um conjunto de dados de entrada busca o equilíbrio entre pureza e extensão, ou seja, procura otimizar uma função que reúne ambos. Espera-se que a técnica a ser desenvolvida tenha um bom desempenho de generalização e ao mesmo tempo possua boa precisão de classificação. Por fim a nova abordagem será aplicada em bioinformática para identificação de splice junctions.