Piotr Lasek

W dniu  15 maja 2012 roku Piotr Lasek obronił rozprawę doktorską pt. "Efficient Density-Based Clustering" (Efektywne gęstościowe grupowanie danych). Promotorem rozprawy była prof. nzw. dr hab. Marzena Kryszkiewicz.

Niniejsza praca poświęcona jest efektywnemu gęstościowemu grupowaniu danych przy użyciu algorytmów takich jak DBSCAN oraz NBC oraz zastosowaniu indeksów i własności nierówności trójkąta w celu polepszenia ich wydajności. W pracy zaproponowano nowy indeks LVA oraz metody budowania i wyszukiwania najbliższych sąsiadów z jego użyciem. Indeks LVA łączy w sobie niektóre cechy indeksu VA-File oraz algorytmu NBC, a mianowicie wykorzystuje koncepcję wektorów aproksymacyjnych oraz warstwowe podejście do wyszukiwania najbliższych sąsiadów. Cechą charakterystyczną indeksu LVA jest brak konieczności odwoływania się do wszystkich komórek przestrzeni w celu znalezienia najbliższych sąsiadów. Ponadto, w przeciwieństwie do rozwiązania zaproponowanego w algorytmie NBC, indeks LVA został przystosowany do wyszukiwania sąsiadów w warstwach o numerach większych od 1. Inną istotną cechą indeksu LVA jest to, że w trakcie budowy indeksu, dla każdej komórki zapamiętywane są reprezentacje l najbliższych warstw zawierających niepuste komórki. Cecha ta znacząco przyspiesza wyszukiwanie najbliższych sąsiadów danego punktu, ponieważ w celu ich znalezienia, przeszukiwane są jedynie najbliższe warstwy komórki, do której ten punkt należy. Z uwagi na przechowywanie warstw w pamięci, dostęp do nich jest bardzo szybki.
W pracy przedstawiono także propozycję wykorzystania własności nierówności trójkąta w celu zwiększenia efektywności algorytmów gęstościowego grupowania danych. Przedstawiono wyniki eksperymentów, których celem było zbadanie efektywności nowego rozwiązania w zależności od liczby wymiarów danych, ilości danych oraz liczby użytych punktów referencyjnych wykorzystywanych do wnioskowania o odległościach pomiędzy punktami na podstawie własności nierówności trójkąta. Eksperymentalnie wykazano, ze w porównaniu do algorytmów gęstościowego grupowania danych wykorzystujących indeksy przestrzenne typu R-drzewo, czy plik VA, zaproponowane algorytmy gęstościowego grupowania danych, które wykorzystują własności nierówności trójkata, są w stanie efektywnie grupować dane także o dużej liczbie wymiarów.