Ok, zacznijmy mówić o DBSCAN.
Density-based spatial clustering of applications with noise (DBSCAN) jest dobrze znanym algorytmem grupowania danych, który jest powszechnie stosowany w eksploracji danych i uczeniu maszynowym.
Bazując na zbiorze punktów (pomyślmy w przestrzeni dwuwymiarowej, jak pokazano na rysunku), DBSCAN grupuje punkty, które są blisko siebie w oparciu o miarę odległości (zwykle odległość euklidesowa) i minimalną liczbę punktów. Zaznacza również jako odstające punkty, które znajdują się w regionach o niskiej gęstości.
Parametry:
Algorytm DBSCAN wymaga w zasadzie 2 parametrów:
Peps: określa, jak blisko siebie powinny znajdować się punkty, aby można je było uznać za część klastra. Oznacza to, że jeśli odległość między dwoma punktami jest mniejsza lub równa tej wartości (eps), to punkty te są uznawane za sąsiadów.
minPoints: minimalna liczba punktów, które mają tworzyć zwarty region. Na przykład, jeśli ustawimy parametr minPoints jako 5, to potrzebujemy co najmniej 5 punktów, aby utworzyć gęsty region.
Oszacowanie parametrów:
Oszacowanie parametrów jest problemem dla każdego zadania eksploracji danych. Aby wybrać dobre parametry, musimy zrozumieć, jak są one używane i mieć przynajmniej podstawową wiedzę na temat zbioru danych, który będzie używany.
eps: jeśli wybrana wartość eps jest zbyt mała, duża część danych nie będzie grupowana. Będą one uważane za wartości odstające, ponieważ nie spełniają liczby punktów, aby utworzyć gęsty region. Z drugiej strony, jeśli wybrana wartość jest zbyt wysoka, klastry będą się łączyć i większość obiektów znajdzie się w tym samym klastrze. Wartość eps powinna być wybrana na podstawie odległości zbioru danych (możemy użyć wykresu k-odległości, aby ją znaleźć), ale generalnie małe wartości eps są preferowane.
minPoints: Jako ogólną zasadę, minimalne minPoints może być wyprowadzone z liczby wymiarów (D) w zbiorze danych, jako minPoints ≥ D + 1. Większe wartości są zazwyczaj lepsze dla zestawów danych z szumem i będą tworzyć bardziej znaczące klastry. Minimalna wartość minPoints musi wynosić 3, ale im większy zbiór danych, tym większa wartość minPoints powinna być wybrana.
Możesz znaleźć więcej o estymacji parametrów tutaj.
Dlaczego powinniśmy używać DBSCAN?
Algorytm DBSCAN powinien być używany do znajdowania związków i struktur w danych, które są trudne do znalezienia ręcznie, ale które mogą być istotne i użyteczne do znalezienia wzorców i przewidywania trendów.
Metody klasteryzacji są zwykle używane w biologii, medycynie, naukach społecznych, archeologii, marketingu, rozpoznawaniu znaków, systemach zarządzania i tak dalej.
Pomyślmy w praktycznym zastosowaniu DBSCAN. Załóżmy, że mamy e-commerce i chcemy poprawić naszą sprzedaż poprzez polecanie odpowiednich produktów naszym klientom. Nie wiemy dokładnie czego szukają nasi klienci, ale na podstawie zbioru danych możemy przewidzieć i polecić odpowiedni produkt dla konkretnego klienta. Możemy zastosować DBSCAN do naszego zbioru danych (opartego na bazie danych e-commerce) i znaleźć klastry oparte na produktach, które użytkownicy kupili. Używając tych klastrów możemy znaleźć podobieństwa między klientami, na przykład, klient A kupił 1 długopis, 1 książkę i 1 nożyczki, a klient B kupił 1 książkę i 1 nożyczki, wtedy możemy polecić 1 długopis klientowi B. To jest tylko mały przykład użycia DBSCAN, ale może on być użyty w wielu aplikacjach w wielu dziedzinach.
Jak możemy go łatwo zaimplementować?
Jak już pisałem (rada: nie wierz we wszystko co piszę) DBSCAN jest dobrze znanym algorytmem, dlatego nie musisz się martwić o jego samodzielną implementację. Możesz użyć jednej z bibliotek/pakietów, które można znaleźć w Internecie. Poniżej znajduje się lista linków, pod którymi można znaleźć implementację DBSCAN: Matlab, R, R, Python, Python.
Pracowałem również nad aplikacją (w języku portugalskim), aby wyjaśnić jak działa DBSCAN w sposób dydaktyczny. Aplikacja została napisana w C++ i można ją znaleźć na Github.