Utilize este identificador para referenciar este registo: https://hdl.handle.net/1822/34194

TítuloSegmentação de vastos volumes de dados com o SNNagg
Outro(s) título(s)Clustering large datasets with SNNagg
Autor(es)Galvão, João Rui Magalhães Velho Cunha
Orientador(es)Santos, Maribel Yasmina
Data2014
Resumo(s)Devido aos constantes avanços tecnológicos e à utilização massiva de dispositivos eletrónicos, a quantidade de dados gerados tem aumentado a um ritmo muito elevado. Consequentemente, a necessidade urgente de conseguir processar maiores quantidades de dados num menor espaço de tempo está cada vez mais presente. De forma a poder tratar estas grandes quantidades de dados, recorre-se ao processo Knowledge Discovery in Databases. Este processo é composto por várias etapas, sendo uma delas o data mining. Os algoritmos data mining permitem analisar vastas quantidades de dados, identificando padrões ou tendências nos mesmos. Existem diversas tarefas e técnicas de data mining, focando-se este trabalho apenas na técnica de data mining de segmentação ou clustering e, dentro desta, no algoritmo SNN (Shared Nearest Neighbour). Os algoritmos de clustering têm, habitualmente, tempo de execução elevados, devido à complexidade quadrática que a maioria apresentam. Neste trabalho, o algoritmo SNN é utilizado para analisar dados espaciais, devido às vantagens que apresenta na análise deste tipo de dados, nomeadamente, ser capaz de identificar segmentos de diferentes densidades, tamanhos ou formas, e ser ainda capaz de identificar ruído nos dados. Apesar das vantagens em termos da qualidade dos resultados obtidos, o tempo de execução aumenta de forma drástica, quando este algoritmo é aplicado a vastos volumes de dados, tornando sua a utilização em tempo útil, quase impraticável. Como objetivo principal, este trabalho visa propor e avaliar soluções capazes de reduzir o tempo de processamento do algoritmo SNN quando este encontra objetos repetidos, uma vez que a quantidade de dados repetidos que é possível encontrar num conjunto de dados com características espaciais pode ser bastante significativa. Para tal, seguindo a metodologia Designe Science Research, o trabalho apresenta três abordagens diferentes com base no algoritmo SNN. As abordagens apresentadas excluem os pontos repetidos da etapa de cálculo dos vizinhos mais próximos, responsável pela complexidade quadrática do algoritmo, voltando a incorporar tais pontos em etapas posteriores. Os resultados obtidos para as diversas abordagens propostas mostram que é possível reduzir o tempo de processamento sem comprometer a qualidade dos agrupamentos que são identificados.
Nowadays, and motivated by the recent advances in information technologies and in the massive use of electronic devices, the amount of generated data has increased at a very high rate. Thus, there is an urgent need to process larger amounts of data to support the decision making process. However, this processing needs to be more efficient than ever. In order to be able to handle these large amounts of data, the process of Knowledge Discovery in Databases is used. This process integrates several stages, one of which is data mining step. Data mining algorithms allow the analysis of huge amounts of data, identifying patterns or trends. Although there are several data mining techniques and tasks, this work is focused in the use of clustering and, namely, in the SNN (Shared Nearest Neighbour) algorithm, a density-based clustering algorithm. Clustering algorithms usually present high runtimes due to the quadratic complexity. In this work, the SNN algorithm is used to analyse spatial data. This algorithm presents several advantages in the analysis of this kind of data, namely the capability of identifying clusters of variable densities, different shapes and sizes, and the ability to identify noise. Despite all these advantages, the algorithm runtime increases drastically when applied to vast amounts of data, making almost impossible the use of it in due time. The main objective of this work is to propose and evaluate solutions capable of reducing the processing time of the algorithm taking into consideration that repeated objects can be excluded from the most demanding task in terms of processing time, which is the identification of the k-nearest neighbours of a point. This is a key point as the number of repeated objects that can be found in a spatial data set is usually high. Following the Design Science Research methodology, this work presents three different approaches that can reduce the processing time by excluding the repeated points of the process of identifying the nearest neighbours, task responsible for the quadratic complexity of the algorithm. The excluded points are added laterto the identified clusters. For the three proposed approaches, the obtained results show that it is possible to reduce the processing time without compromising the quality of the identified clusters.
TipoDissertação de mestrado
DescriçãoDissertação de mestrado integrado em Engenharia de Comunicações
URIhttps://hdl.handle.net/1822/34194
AcessoAcesso aberto
Aparece nas coleções:BUM - Dissertações de Mestrado
CAlg - Dissertações de mestrado/MSc dissertations
DSI - Sistemas de Computação e Comunicações

Ficheiros deste registo:
Ficheiro Descrição TamanhoFormato 
Tese_João Galvão_2014.pdf5,31 MBAdobe PDFVer/Abrir

Partilhe no FacebookPartilhe no TwitterPartilhe no DeliciousPartilhe no LinkedInPartilhe no DiggAdicionar ao Google BookmarksPartilhe no MySpacePartilhe no Orkut
Exporte no formato BibTex mendeley Exporte no formato Endnote Adicione ao seu ORCID