DENSITY-BASED CLUSTERING AND NEAREST NEIGHBOROOD SEARCH BY MEANS OF THE TRIANGLE INEQUALITY

Bartłomiej Jańczak

Abstract

The thesis begins with a brief introduction to a density-based clustering domain, including the description of the DBSCAN algorithm and k neighborhood search. Next, density-based clustering algorithms and k neighborhood search by means of the triangle inequality were explained. Also, distance metrics and the cosine measure were recalled, as well as the determination of cosine neighborhood by means of the Euclidean distance was described. Then, TI-DBSCAN and TI-k-Neighborhood-Index algorithms were presented. In addition, their modifications DBSCAN-PROJECTION and k-Neighborhood-Index-Projection were proposed. The description of the algorithms using the triangle inequality mainly focused on methods of selecting reference points to enable efficient clustering by means of the triangle inequality, while in the case of algorithms which use projection their description mainly focused on methods of selecting projection dimensions to enable efficient clustering by means of projection. There were proposed also two variants of k nearest neighbors search in a VP-Tree, which are enhancements of the algorithm for nearest neighbor search in the VP-Tree that is available in the literature. All these algorithms and indexes were implemented. The main part of the dissertation are research results and conclusions drawn from the experiments carried out by means of the implemented algorithms and indexes on diverse datasets. In the concluding part of the thesis, the performance of the examined algorithms and indexes was compared both for the Euclidean distance metric and the cosine similarity measure.
Diploma typeMaster of Science
Author Bartłomiej Jańczak II
Bartłomiej Jańczak,,
- The Institute of Computer Science
Title in PolishGęstościowe grupowanie danych i wyznaczanie najbliższego sąsiedztwa z użyciem nierówności trójkąta
Supervisor Marzena Kryszkiewicz II
Marzena Kryszkiewicz,,
- The Institute of Computer Science
Certifying unitFaculty of Electronics and Information Technology (FEIT)
Affiliation unitThe Institute of Computer Science (IN)
Languagepl polski
StatusFinished
Issue date (year)2013
Internal identifierENII-PM.001769
Keywords in Polishgęstościowe grupowanie danych, wyznaczanie najbliższego sąsiedztwa, nierówność trójkąta, VP-Tree, DBSCAN, TI-DBSCAN
Keywords in Englishdensity-based clustering, nearest neighborhood search, triangle inequality, VP-Tree, DBSCAN, TI-DBSCAN
Abstract in PolishNiniejsza praca rozpoczyna się od wprowadzenia w dziedzinę gęstościowego grupowania danych, w tym przedstawienia algorytmu DBSCAN i wyszukiwania k sąsiedztwa. Następnie opisano teoretyczne podstawy wykorzystania nierówności trójkąta w gęstościowym grupowaniu danych i wyszukiwaniu k sąsiedztwa. Przypomniano metryki odległości i miarę kosinusową oraz opisano metodę wyznaczania kosinusowego sąsiedztwa za pomocą sąsiedztwa opartego na odległości euklidesowej. W dalszej części zaprezentowano algorytmy TI-DBSCAN i TI-k-Neighborhood-Index wykorzystujące nierówność trójkąta oraz zaproponowano ich modyfikacje DBSCAN-PROJECTION i k-Neighborhood-Index-Projection wykorzystujące rzutowanie. W opisie algorytmów korzystających z nierówności trójkąta skupiono się na możliwych metodach doboru punktów referencyjnych pozwalających na efektywne grupowanie danych z zastosowaniem nierówności trójkąta, natomiast w przypadku algorytmów stosujących rzutowanie skoncentrowano się na metodach doboru wymiarów rzutowania umożliwiających efektywne grupowanie z wykorzystaniem rzutowania. Zaproponowano także dwa warianty wyszukiwania k sąsiadów w drzewie metrycznym VP-Tree, które stanowią rozwinięcie algorytmu wyszukiwania najbliższego sąsiada w drzewie VP-Tree dostępnego w literaturze. Wszystkie te algorytmy i indeksy zostały zaimplementowane. Następnie znajduje się najistotniejsza część pracy, czyli prezentacja i omówienie wyników badań eksperymentalnych przeprowadzonych z użyciem tychże algorytmów i indeksów na testowych zbiorach danych o różnej liczbie wymiarów i charakterystyce. W podsumowaniu zawarto wnioski obejmujące porównanie ze sobą wydajności badanych algorytmów oraz indeksów z użyciem metryki odległości euklidesowej i kosinusowej miary podobieństwa.
File
Praca_Magisterska_2.pdf 5.62 MB

Get link to the record
msginfo.png

Back