Texto completo
| |
| Autor(es): |
Jonathan de Andrade Silva
Número total de Autores: 1
|
| Tipo de documento: | Tese de Doutorado |
| Imprenta: | São Carlos. |
| Instituição: | Universidade de São Paulo (USP). Instituto de Ciências Matemáticas e de Computação (ICMC/SB) |
| Data de defesa: | 2015-03-04 |
| Membros da banca: |
Eduardo Raul Hruschka;
Heloisa de Arruda Camargo;
André Carlos Ponce de Leon Ferreira de Carvalho;
Ricardo Ribeiro Gudwin;
Renato Tinós
|
| Orientador: | Eduardo Raul Hruschka |
| Resumo | |
Técnicas de agrupamento de dados usualmente assumem que o conjunto de dados é de tamanho fixo e pode ser alocado na memória. Neste contexto, um desafio consiste em aplicar técnicas de agrupamento em bases de dados de tamanho ilimitado, com dados gerados continuamente e em ambientes dinâmicos. Dados gerados nessas condições originam o que se convencionou chamar de Fluxo Contínuo de Dados (FCD). Em aplicações de FCD, operações de acesso aos dados são restritas a apenas uma leitura ou a um pequeno número de acessos aos dados, com limitações de memória e de tempo de processamento. Além disso, a distribuição dos dados gerados por essas fontes pode ser não estacionária, ou seja, podem ocorrer mudanças ao longo do tempo, denominadas de mudanças de conceito. Nesse sentido, algumas técnicas de agrupamento em FCD foram propostas na literatura. Muitas dessas técnicas são baseadas no algoritmo das k-Médias. Uma das limitações do algoritmo das k-Médias consiste na definição prévia do número de grupos. Ao se assumir que o número de grupos é desconhecido a priori e que deveria ser estimado a partir dos dados, percorrer o grande espaço de soluções possíveis (tanto em relação ao número de grupos, k, quanto em relação às partições possíveis para um determinado k) torna desafiadora a tarefa de agrupamento de dados - ainda mais sob a limitação de tempo e armazenamento imposta em aplicações de FCD. Neste contexto, essa tese tem como principais contribuições: (i) adaptar algoritmos que têm sido usados com sucesso em aplicações de Fluxo Contínuo de Dados (FCD) nas quais k é conhecido para cenários em que se deseja estimar o número de grupos; (ii) propor novos algoritmos para agrupamento que estimem k automaticamente a partir do FCD; (iii) avaliar sistematicamente, e de maneira quantitativa, os algoritmos propostos de acordo com as características específicas dos cenários de FCD. Foram desenvolvidos 14 algoritmos de agrupamento para FCD capazes de estimar o número de grupos a partir dos dados. Tais algoritmos foram avaliados em seis bases de dados artificiais e duas bases de dados reais amplamente utilizada na literatura. Os algoritmos desenvolvidos podem auxiliar em diversas áreas da Mineração em FCD. Os algoritmos evolutivos desenvolvidos mostraram a melhor relação de custo-benefício entre eficiência computacional e qualidade das partições obtidas. (AU) | |
| Processo FAPESP: | 10/15049-7 - Agrupamento de dados em Fluxos Contínuos com Estimativa Automática do Número de Grupos |
| Beneficiário: | Jonathan de Andrade Silva |
| Modalidade de apoio: | Bolsas no Brasil - Doutorado |