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. / Several algorithms for clustering data streams based on k-Means have been proposed in the literature. However, most of them assume that the number of clusters, k, is known a priori by the user and can be kept fixed throughout the data analysis process. Besides the dificulty in choosing k, data stream clustering imposes several challenges to be dealt with, such as addressing non-stationary, unbounded data that arrives in an online fashion. In data stream applications, the dataset must be accessed in order and that can be read only once or a small number of times. In this context, the main contributions of this thesis are: (i) adapt algorithms that have been used successfully in data stream applications where k is known to be able to estimate the number of clusters from data; (ii) propose new algorithms for clustering to estimate k automatically from the data stream; (iii) evaluate the proposed algorithms according to diferent scenarios. Fourteen clustering data stream algorithms were developed which are able to estimate the number of clusters from data. They were evaluated in six artificial datasets and two real-world datasets widely used in the literature. The developed algorithms are useful for several data mining tasks. The developed evolutionary algorithms have shown the best trade-off between computational efficiency and data partition quality.

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. / Several algorithms for clustering data streams based on k-Means have been proposed in the literature. However, most of them assume that the number of clusters, k, is known a priori by the user and can be kept fixed throughout the data analysis process. Besides the dificulty in choosing k, data stream clustering imposes several challenges to be dealt with, such as addressing non-stationary, unbounded data that arrives in an online fashion. In data stream applications, the dataset must be accessed in order and that can be read only once or a small number of times. In this context, the main contributions of this thesis are: (i) adapt algorithms that have been used successfully in data stream applications where k is known to be able to estimate the number of clusters from data; (ii) propose new algorithms for clustering to estimate k automatically from the data stream; (iii) evaluate the proposed algorithms according to diferent scenarios. Fourteen clustering data stream algorithms were developed which are able to estimate the number of clusters from data. They were evaluated in six artificial datasets and two real-world datasets widely used in the literature. The developed algorithms are useful for several data mining tasks. The developed evolutionary algorithms have shown the best trade-off between computational efficiency and data partition quality.

Submitted by Milena Rubi (milenarubi@ufscar.br) on 2016-10-17T14:50:55Z No. of bitstreams: 1 LUZ_Thamires_2015.pdf: 4921213 bytes, checksum: 9d05f0a134378657db3994e8496ed5bf (MD5) / Approved for entry into archive by Milena Rubi (milenarubi@ufscar.br) on 2016-10-17T14:51:09Z (GMT) No. of bitstreams: 1 LUZ_Thamires_2015.pdf: 4921213 bytes, checksum: 9d05f0a134378657db3994e8496ed5bf (MD5) / Approved for entry into archive by Milena Rubi (milenarubi@ufscar.br) on 2016-10-17T14:51:18Z (GMT) No. of bitstreams: 1 LUZ_Thamires_2015.pdf: 4921213 bytes, checksum: 9d05f0a134378657db3994e8496ed5bf (MD5) / Made available in DSpace on 2016-10-17T14:51:33Z (GMT). No. of bitstreams: 1 LUZ_Thamires_2015.pdf: 4921213 bytes, checksum: 9d05f0a134378657db3994e8496ed5bf (MD5) Previous issue date: 2015-11-19 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / Electricity in Brazil is mostly generated by hydroelectric plants that depend on the volume of water in their reservoirs. Due to the fact that rainfall is decreasing, other methods with higher costs to generate energy are required. These costs are passed to users, increasing the energy bill. Futhermore, the wasting of energy and overconsumption also contribute to increase the energy bill. At the same time, the wasting of energy are not noticed by the user. To avoid such wasting, an alert could be sent as soon as an anomalous event is detected. In this way, we propose a system that sends an alert of any novelty detection in energy consumption through the analysis of the methods Sliding Window, Exponentially Weighted Moving Averages, Clustering, Average per Circle, Average per Stage, Gauss Distribution and Self-Organizing Novelty Detection. Results demonstrate that the methods evaluated are efficient in real time detection of novelties, presenting 90% of accuracy and 10% of recall, besides a low delay to send the alert. / A energia elétrica no Brasil é gerada em sua maioria pelas usinas hidrelétricas. Essas hidrelétricas dependem do volume de água dos reservatórios para a geração de energia e, devido à diminuição dos índices pluviométricos, métodos alternativos de geração com custos mais altos são necessários. Esses custos são repassados para os usuários, encarecendo a conta de energia elétrica. Além disso, podemos atribuir o aumento da conta de energia elétrica também ao consumo exagerado e ao desperdício de energia, que muitas vezes pode não ser notado devido ao aumento ser gerado por falha elétrica ou humana, como o esquecimento da porta da geladeira aberta, por exemplo. Partindo da hipótese de que cada equipamento eletrônico apresenta um padrão no consumo energético, um alerta poderia ser enviado ao usuário caso o comportamento padrão fosse alterado. Sendo assim, neste trabalho é proposto um sistema que realiza detecções nas alterações no comportamento do consumo de energia elétrica dos aparelhos eletrônicos, de forma que alertas sejam enviados para o usuário. Para detectar a alteração de comportamento do consumo de energia elétrica dos aparelhos eletrônicos foram implementados sete métodos consolidados na literatura: Janela Deslizante, Exponentially Weighted Moving Averages (EWMA), Agrupamento, Média por Ciclo, Média por Estágio, Distribuição Gaussiana e Self-Organizing Novelty Detection (SONDE). Os experimentos demonstraram que os métodos foram eficientes na detecção de novidade em tempo real apresentando taxa de detecção das alterações comportamentais acima de 90% e falso-positivo abaixo de 10%, além de um tempo médio de resposta baixo.

Submitted by Fabio Sobreira Campos da Costa (fabio.sobreira@ufpe.br) on 2016-07-11T12:33:28Z No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) silas-dissertacao-versao-final-2016.pdf: 1708159 bytes, checksum: 6c0efc5f2f0b27c79306418c9de516f1 (MD5) / Made available in DSpace on 2016-07-11T12:33:28Z (GMT). No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) silas-dissertacao-versao-final-2016.pdf: 1708159 bytes, checksum: 6c0efc5f2f0b27c79306418c9de516f1 (MD5) Previous issue date: 2015-02-27 / FACEPE / A extração de conhecimento em ambientes com fluxo contínuo de dados é uma atividade que vem crescendo progressivamente. Diversas são as situações que necessitam desse mecanismo, como o monitoramento do histórico de compras de clientes; a detecção de presença por meio de sensores; ou o monitoramento da temperatura da água. Desta maneira, os algoritmos utilizados para esse fim devem ser atualizados constantemente, buscando adaptar-se às novas instâncias e levando em consideração as restrições computacionais. Quando se trabalha em ambientes com fluxo contínuo de dados, em geral não é recomendável supor que sua distribuição permanecerá estacionária. Diversas mudanças podem ocorrer ao longo do tempo, desencadeando uma situação geralmente conhecida como mudança de conceito (concept drift). Neste trabalho foi realizado um estudo comparativo entre alguns dos principais métodos de detecção de mudanças: ADWIN, DDM, DOF, ECDD, EDDM, PL e STEPD. Para execução dos experimentos foram utilizadas bases artificiais – simulando mudanças abruptas, graduais rápidas, e graduais lentas – e também bases com problemas reais. Os resultados foram analisados baseando-se na precisão, tempo de execução, uso de memória, tempo médio de detecção das mudanças, e quantidade de falsos positivos e negativos. Já os parâmetros dos métodos foram definidos utilizando uma versão adaptada de um algoritmo genético. De acordo com os resultados do teste de Friedman juntamente com Nemenyi, em termos de precisão, DDM se mostrou o método mais eficiente com as bases utilizadas, sendo estatisticamente superior ao DOF e ECDD. Já EDDM foi o método mais rápido e também o mais econômico no uso da memória, sendo superior ao DOF, ECDD, PL e STEPD, em ambos os casos. Conclui-se então que métodos mais sensíveis às detecções de mudanças, e consequentemente mais propensos a alarmes falsos, obtêm melhores resultados quando comparados a métodos menos sensíveis e menos suscetíveis a alarmes falsos. / Knowledge extraction from data streams is an activity that has been progressively receiving an increased demand. Examples of such applications include monitoring purchase history of customers, movement data from sensors, or water temperatures. Thus, algorithms used for this purpose must be constantly updated, trying to adapt to new instances and taking into account computational constraints. When working in environments with a continuous flow of data, there is no guarantee that the distribution of the data will remain stationary. On the contrary, several changes may occur over time, triggering situations commonly known as concept drift. In this work we present a comparative study of some of the main drift detection methods: ADWIN, DDM, DOF, ECDD, EDDM, PL and STEPD. For the execution of the experiments, artificial datasets were used – simulating abrupt, fast gradual, and slow gradual changes – and also datasets with real problems. The results were analyzed based on the accuracy, runtime, memory usage, average time to change detection, and number of false positives and negatives. The parameters of methods were defined using an adapted version of a genetic algorithm. According to the Friedman test with Nemenyi results, in terms of accuracy, DDM was the most efficient method with the datasets used, and statistically superior to DOF and ECDD. EDDM was the fastest method and also the most economical in memory usage, being statistically superior to DOF, ECDD, PL and STEPD, in both cases. It was concluded that more sensitive change detection methods, and therefore more prone to false alarms, achieve better results when compared to less sensitive and less susceptible to false alarms methods.