Procedura wyboru eps i minPts dla DBSCAN

14

DBSCAN jest najczęściej cytowanym algorytmem klastrowania według literatury i może znaleźć klastry o dowolnym kształcie na podstawie gęstości. Ma dwa parametry eps (jako promień sąsiedztwa) i minPts (jako minimalni sąsiedzi, aby uznać punkt za punkt centralny), co moim zdaniem w dużym stopniu zależy od nich.

Czy istnieje jakaś rutynowa lub powszechnie stosowana metoda wyboru tych parametrów?

clustering dbscan Mehraban
źródło
1
Zauważ, że podobne pytanie dotyczy przepełnienia stosu : wybranie eps i minpt dla DBSCAN (R)?
gung - Przywróć Monikę

Odpowiedzi:

11

Istnieje wiele publikacji, które proponują metody wyboru tych parametrów.

Najbardziej godna uwagi jest OPTICS, odmiana DBSCAN, która eliminuje parametr epsilon; daje wynik hierarchiczny, który można z grubsza postrzegać jako „uruchamianie DBSCAN z każdym możliwym epsilon”.

W przypadku MinPts sugeruję, aby nie polegać na automatycznej metodzie, ale na wiedzy o Twojej domenie .

Dobry algorytm grupowania ma parametry, które pozwalają dostosować go do własnych potrzeb.

Parametrem, który przeoczyłeś, jest funkcja odległości. Pierwszą rzeczą do zrobienia dla DBSCAN jest znalezienie dobrej funkcji odległości dla twojej aplikacji . Nie polegaj na tym, że odległość euklidesowa jest najlepsza dla każdego zastosowania!

Ma ZAKOŃCZENIE - Anony-Mus
źródło
Chociaż użytkownik może wybrać funkcję odległości, wątpię, że jest to parametr.
Mehraban
1
Oczywiście, że jest. Jest to tak samo parametr jak funkcja jądra dla każdej innej metody jądra (w rzeczywistości można w ten sposób kernelizować DBSCAN w ten sposób), a z mojego doświadczenia wynika, że ​​inne odległości, takie jak Canberra lub Clark, mogą znacznie poprawić wyniki .
Ma ZAKOŃCZENIE - Anony-Mousse
Nie doceniam wpływu funkcji odległości na klastrowanie, ale myślę, że jest ona w jakiś sposób ogólna, nie jest specyficzna dla dbscan ani żadnego innego algorytmu klastrowania; podczas gdy eps i minPts są wyraźnie parametrami dbscan.
Mehraban
1
Istnieje również wiele algorytmów nie opartych na odległości. A jeśli uważasz, że minPts są takie same jak np. kDla klasyfikacji najbliższego sąsiada, możesz powiedzieć to samo dla parametru minPts. Myślę, że główna różnica polega na tym, że w przypadku odległości istnieje „często” rozsądna wartość domyślna: odległość euklidesowa; podczas gdy dla MinPts wartość będzie zależała od danych.
Ma ZAKOŃCZENIE - Anony-Mousse
1
Sama optyka nie da ci partycji, ale porządek klastra. Aby uzyskać partycje, użyj ekstrakcji XI opisanej w dokumencie OPTICS. Zobacz papier każdego wariantu, aby zrozumieć różnice.
Ma ZAKOŃCZENIE - Anony-Mousse