Please use this identifier to cite or link to this item: http://hdl.handle.net/10348/365
Title: Optimização da Combinação de Agrupamentos baseado na Acumulação de Provas pesadas por Índices de Validação e com uso de Amostragem
Authors: Duarte, Fernando Jorge Ferreira
Advisor: Rodrigues, Maria de Fátima Coutinho
Cordeiro, Manuel da Ressurreição
Issue Date: 2008
Abstract: O objectivo do agrupamento de dados consiste em organizar os objectos de um conjunto de dados em grupos homogéneos, de forma que exista similaridade entre objectos do mesmo grupo e dissimilaridade entre objectos de grupos diferentes. Apesar do vasto número de algoritmos de agrupamento de dados existentes, nenhum é aplicável com êxito a todas as possíveis estruturas presentes nos conjuntos de dados multidimensionais. Nos últimos anos, a combinação de agrupamentos de dados tem sido foco de grande actividade de investigação com o intuito de, nomeadamente: minimizar os problemas inerentes ao processo de agrupamento de dados e obter um agrupamento de dados final de melhor qualidade do que aqueles que lhe deram origem, reutilizar agrupamentos de dados já existentes e usar agrupamentos de dados que se encontrem fisicamente distribuídos (eventualmente com diferentes objectos e/ou atributos), sem que para tal seja necessário realizar a centralização dos objectos de dados. A validação de agrupamentos de dados e a descoberta do número de grupos existente nos dados têm sido também motivo de intensa investigação. O objectivo da validação de agrupamentos de dados consiste em seleccionar entre os agrupamentos de dados existentes, o que melhor se ajusta aos dados. Mais uma vez, apesar de existirem várias medidas de validação de agrupamentos de dados, nenhuma captura todas as propriedades de um qualquer bom agrupamento de dados. Estas medidas podem ser classificadas em medidas baseadas em critérios externos e internos. As medidas de validação de agrupamentos de dados baseadas em critérios internos podem ainda ser subdivididas em medidas que avaliam o ajuste ou correspondência entre os dados e o agrupamento de dados obtido e em métodos de determinação do número K de grupos existente nos dados. Neste trabalho de dissertação são apresentados vários conteúdos relacionados com o agrupamento de dados, nomeadamente, os conceitos e aspectos formais a ele relacionados, os algoritmos de agrupamento de dados mais referenciados, as principais medidas de validação de agrupamentos de dados e as abordagens de combinação de agrupamento de dados mais importantes. Duas das mais valias deste trabalho consistem no desenvolvimento do método de combinação ponderada de agrupamentos de dados com amostragem, WEACS, e da medida de consistência dos grupos do conjunto de agrupamentos de dados, MCG. De forma a possibilitar a análise do comportamento de diversos algoritmos de agrupamento, de diversas medidas de validação de agrupamentos de dados e de diversos métodos de combinação de agrupamentos de dados, procedeu-se à sua implementação. Outra das contribuições deste trabalho consiste na disponibilização de uma toolbox com interface gráfica, que permite obter resultados pela aplicação de vários algoritmos de agrupamento, de várias medidas de validação de agrupamentos e de várias abordagens de combinação de agrupamentos de dados. Nesta dissertação foram realizados vários estudos comparativos com vários conjuntos de dados reais e sintéticos: para avaliar o desempenho de vários algoritmos de agrupamento de dados; para avaliar o desempenho de várias medidas de validação de agrupamentos de dados baseadas em critérios externos e em critérios internos; para avaliar o desempenho de vários métodos de combinação de agrupamentos de dados, incluindo o método WEACS proposto nesta dissertação; para avaliar o desempenho de medidas para a selecção do melhor agrupamento de dados final combinado com base nos agrupamentos do conjunto de agrupamentos, incluindo a medida MCG proposta nesta dissertação. Os resultados obtidos nos estudos realizados para avaliar o desempenho dos vários algoritmos de agrupamento de dados e dos vários métodos de combinação de agrupamentos de dados, mostraram que apesar da configuração TODOS5+WR do passo complementar do método WEACS não obter sempre os melhores resultados, o seu desempenho em quase todas as situações é claramente superior ao desempenho médio dos restantes métodos de combinação de agrupamentos de dados, aproximando-se sempre dos melhores resultados nas situações em que isso não acontece. Por esse facto, o método WEACS constitui uma opção robusta e recomendável para a combinação de agrupamentos de dados. O estudo comparativo para a avaliação do desempenho das medidas para a selecção do melhor agrupamento de dados, obtido pela combinação de agrupamentos de um determinado conjunto de agrupamentos de dados, apresentou resultados que mostram que existe uma relação directa entre os resultados obtidos pela medida MCG e a qualidade dos agrupamentos de dados finais obtidos, já que o aumento ou a diminuição dos valores da medida MCG são acompanhados pelo aumento ou diminuição da qualidade dos agrupamentos de dados finais. As restantes medidas usadas no estudo, não apresentaram esta correlação ou só apresentaram em alguns conjuntos de dados. Estes resultados demonstram que a medida MCG constitui uma opção aconselhável como medida para a selecção de agrupamentos de dados finais resultantes da combinação de agrupamentos de dados. Outra vertente desta dissertação está ligada à liberalização do mercado de energia eléctrica. Esta liberalização provocou a necessidade das empresas produtoras, distribuidoras e comercializadoras de energia eléctrica terem disponíveis ferramentas de previsão do comportamento de consumo de energia eléctrica dos seus clientes, de forma a poderem reduzir e atenuar os riscos. A caracterização de consumidores de energia eléctrica constitui uma ajuda indispensável na obtenção desses objectivos. Esta necessidade de ferramentas de previsão do comportamento de consumo de energia eléctrica levou à inclusão neste trabalho de uma metodologia para a caracterização de consumidores de energia eléctrica. Neste trabalho de dissertação é apresentado um caso de estudo sobre a caracterização de perfis de consumo de clientes de média tensão sendo assim realizada uma aplicação da metodologia para a caracterização de consumidores de energia eléctrica proposta. Na fase de determinação dos perfis de consumo pôde-se constatar que a configuração TODOS5+WR do passo complementar do método WEACS alcançou os melhores resultados, isto é, obteve os grupos melhor divididos do que qualquer um dos outros algoritmos de agrupamento usados no estudo.
The purpose of data clustering is to organize the objects of a data set in homogeneous groups, in such a way that there is similarity between the objects in the same group, and dissimilarity between objects of different groups. Despite the existing wide number of data clustering algorithms, none is successfully applicable in all the possible structures present in multidimensional data sets. Lately, the combination of clustering ensembles has been extensively focused on by investigation activities. This focus aims at minimizing the problems inherent to the data clustering process, at getting a final data partition better in quality than their predecessors, at reusing already existent data partitions, and at using physically distributed data partitions (eventually with different objects and/or attributes), without the need for data objects centralization. Data clustering validation and the determination of the number of groups existent in data have also been the target of thorough investigation. The objective of data clustering validation is to select, among the existent data partitions, the one that fits data the best. Once again, although there are several data clustering validation measures, none captures all the properties of any good data partition. These measures may be classified in external and internal criteria based measures. Clustering validation measures based on internal criteria may still be subdivided into measures that evaluate the adjustment or the correspondence between the data and the obtained data partition, and methods of determining the existent K number of groups in the data. In this dissertation several contents related to data clustering are presented, namely its related formal concepts and aspects, the most referenced data clustering algorithms, the main data clustering validation measures, and the most important clustering ensemble combination approaches. Two of the most valuable aspects of this research work consist in the development of the weighed clustering ensemble combination method with sampling, WEACS, and in the development of the clustering ensemble consistency measure of groups, MCG. Several clustering algorithms, diverse data clustering validation measures, and diverse clustering ensemble combination methods were implemented so that their behavior could be analyzed. Another contribution of the present research work consists in the availability of a toolbox with graphical interface, which enables getting the results by applying various clustering algorithms, various clustering validation measures, and various clustering ensemble combination approaches. In this dissertation various comparative studies were performed with various real and synthetic data sets: to evaluate the performance of several data clustering algorithms; to evaluate the performance of several data clustering validation measures based on external and on internal criteria; to evaluate the performance of several clustering ensemble combination methods, including the WEACS method proposed in this dissertation; to evaluate the performance of measures to select the best final combined data partition based on the clustering ensemble data partitions, including the MCG measure proposed in this dissertation. The results obtained in the studies to evaluate the performance of the several data clustering algorithms and of the several clustering ensemble combination methods showed that although the TODOS5+WR configuration of the WEACS method’s complementary step has not always obtained the best results, its performance in almost every situation is clearly superior to the average performance of the rest of the clustering ensemble combination methods, always being close to the best results even in the situations in which that does not happen. Therefore, the WEACS method is a robust and recommendable option for clustering ensemble combination. The comparative study to evaluate the performance of the measures for the selection of the best data partition, obtained by the combination of partitions of a determined clustering ensemble, presented results that show that there is a direct relation between the results obtained through the MCG measure and the quality of the final data partitions, once the raising or lowering of the MCG measure values are accompanied by the raising and lowering of the quality of the final data partitions. The other measures used in the study did not present this correlation, or only presented it in some sets of data. These results reveal that the MCG measure constitutes an advisable option as a measure for the selection of final data partitions resulting from the clustering ensemble combination. Another aspect of this dissertation is connected to the liberalization of the electrical power market. This liberalization has raised the need for companies that produce, distribute and commercialize electrical power to have at their disposal tools able to predict their clients’ electrical energy consumption behavior, so that they can reduce and minimize risks. The characterization of the electrical power consumers constitutes an invaluable help in reaching those objectives. This need for electrical power consumption behavior predicting tools has led to include in this work a methodology for characterizing electrical power consumers. In this dissertation a case study about the characterization of medium power clients’ consumption profiles is presented. This way, the proposed methodology for characterizing the electrical power consumers was applied. In the consumption profiles determination phase, it was possible to observe that the configuration TODOS5+WR of the WEACS method’s complementary step reached the best results, i.e. obtained better divided groups than any of the other clustering algorithms used in the study.
Description: Tese de Doutoramento em Engenharia Electrotécnica e de Computadores
URI: http://hdl.handle.net/10348/365
Document Type: Doctoral Thesis
Appears in Collections:OLD - Teses de Doutoramento

Files in This Item:
File Description SizeFormat 
phd_fjfduarte.pdf12,19 MBAdobe PDFThumbnail
View/Open


FacebookTwitterDeliciousLinkedInDiggGoogle BookmarksMySpace
Formato BibTex mendeley Endnote Logotipo do DeGóis Logotipo do Orcid 

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.