Baza wiedzy: Politechnika Warszawska

Ustawienia i Twoje konto

Powrót

Gęstościowe grupowanie danych z użyciem nierówności trójkąta

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.
Identyfikator pozycji
WUT8bbabe89ae264fcbbf0575649f18fac3
Rodzaj dyplomu
Praca magisterska
Autor
Jarosław Wawer (WEiTI/II) Jarosław Wawer Instytut Informatyki (WEiTI/II)Wydział Elektroniki i Technik Informacyjnych (WEiTI)
Tytuł w języku polskim
Gęstościowe grupowanie danych z użyciem nierówności trójkąta
Promotor
Marzena Kryszkiewicz (WEiTI/II) Marzena Kryszkiewicz Instytut Informatyki (WEiTI/II)Wydział Elektroniki i Technik Informacyjnych (WEiTI)
Jednostka dyplomująca
Wydział Elektroniki i Technik Informacyjnych (WEiTI)
Jednostka prowadząca
Instytut Informatyki (WEiTI/II)
Język
(pl) polski
Status pracy
Obroniona
Data (rok) wydania
2012
Identyfikator wewnętrzny
ENII-PM.001551
Słowa kluczowe w języku polskim
gęstościowe grupowanie danych, DBSCAN, NBC, PreDeCon, nierówność trójkąta, TI-DBSCAN, TI-NBC, TI-PreDeCon, R*tree, VA-File
Słowa kluczowe w języku angielskim
density-based clustering, DBSCAN, NBC, PreDeCon, Triangle Inequality, TI-DBSCAN, TI-NBC, TI-PreDeCon, R*tree, VA-File
Streszczenie w języku polskim
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.

Jednolity identyfikator zasobu
https://repo.pw.edu.pl/info/master/WUT8bbabe89ae264fcbbf0575649f18fac3/
URN
urn:pw-repo:WUT8bbabe89ae264fcbbf0575649f18fac3

Potwierdzenie
Czy jesteś pewien?
Zgłoszenie uwag dotyczących tej strony