Knowledge base: Warsaw University of Technology

Settings and your account

Back

Density-based Clustering By Means of the Triangle Inequality

Jarosław Wawer

Abstract

The Master’s Thesis begins with a introduction to a density-based clustering domain, including the description of selected algorithms: DBSCAN, NBC and PreDeCon. Following the explanation of accelerating density-based clustering by means of the Triangle Inequality, ąirthcr chapters concentrate on the algorithms using this property, TI-DBSCAN and TI-NBC, and new algorithm TI-PreDeCon. The description of these algorithms’ parameters focuses on strategies for selecting a reference point, used for efficient clustering by means of the Triangle Inequality. Furthermore, variants with many reference points and more complex strategies for their selection were taken into account. The main part of the dissertation — the results of my research — follows the description of the most crucial implementation issues, data sets used in the experiments. The use of diversified data sets allowed analyzing the influence of number and strategy of reference points’ selection on efficiency of searching c-neighborhood or k-neighborhood. In the concluding part of the thesis, the original algorithms that use spatial indices (such as R*tree or VA-File) are compared with the versions using the Triangle Inequality in favour of the latter. Apart from pointing out strengths of the algorithms using the Triangle Inequality, the conclusions also provide the list of issues for further consideration.
Record ID
WUT8bbabe89ae264fcbbf0575649f18fac3
Diploma type
Master of Science
Author
Jarosław Wawer (FEIT/ICS) Jarosław Wawer,, The Institute of Computer Science (FEIT/ICS)Faculty of Electronics and Information Technology (FEIT)
Title in Polish
Gęstościowe grupowanie danych z użyciem nierówności trójkąta
Supervisor
Marzena Kryszkiewicz (FEIT/ICS) Marzena Kryszkiewicz,, The Institute of Computer Science (FEIT/ICS)Faculty of Electronics and Information Technology (FEIT)
Certifying unit
Faculty of Electronics and Information Technology (FEIT)
Affiliation unit
The Institute of Computer Science (FEIT/ICS)
Language
(pl) Polish
Status
Finished
Issue date (year)
2012
Internal identifier
ENII-PM.001551
Keywords in Polish
gęstościowe grupowanie danych, DBSCAN, NBC, PreDeCon, nierówność trójkąta, TI-DBSCAN, TI-NBC, TI-PreDeCon, R*tree, VA-File
Keywords in English
density-based clustering, DBSCAN, NBC, PreDeCon, Triangle Inequality, TI-DBSCAN, TI-NBC, TI-PreDeCon, R*tree, VA-File
Abstract in Polish
Praca magisterska rozpoczyna się od wprowadzenia w dziedzinę gęstościowego grupowania danych, w tym przedstawienia trzech wybranych algorytmów: DBSCAN, NBC i PreDeCon. Po opisaniu teoretycznych podstaw wykorzystania nierówności trójkąta w gęstościowym grupowaniu danych, przedstawione zostały oparte na tej własności algorytmy TI-DBSCAN i TI-NBC oraz nowy algorytm TI-PreDeCon. Opis ich parametrów skoncentrowany jest na strategiach wyboru punktu referencyjnego, wykorzystywanego do efektywnego grupowania danych z zastosowaniem nierówności trójkąta. Uwzględnione zostały także wersje wykorzystujące wiele punktów referencyjnych oraz bardziej złożone strategie ich wyboru. Po opisie najistotniejszych aspektów implementacji i testowych zbiorów danych, znalazła się najważniejsza część pracy, czyli omówienie wyników przeprowadzonych badań eksperymentalnych. Na testowych zbiorach danych, o różnej charakterystyce, przeanalizowany został wpływ liczby i strategii wyboru punktów referencyjnych na wydajność algorytmów wykorzystujących nierówność trójkąta do wyszukiwania epsilonowego sąsiedztwa i k-sąsiedztwa. Wnioski w podsumowaniu obcjmują porównanie wydajności algorytmów opartych na nierówności trójkąta z wersjami wykorzystującymi indeksy przestrzenne, takie jak R*drzewo czy VA-File. Poza podsumowaniem mocnych stron algorytmów wykorzystujących nierówność trójkąta, wskazałem możliwości rozwoju.

Uniform Resource Identifier
https://repo.pw.edu.pl/info/master/WUT8bbabe89ae264fcbbf0575649f18fac3/
URN
urn:pw-repo:WUT8bbabe89ae264fcbbf0575649f18fac3

Confirmation
Are you sure?
Report incorrect data on this page