Rutin untuk memilih eps dan minPts untuk DBSCAN

13

DBSCAN adalah algoritma pengelompokan yang paling banyak dikutip menurut beberapa literatur dan dapat menemukan bentuk cluster berdasarkan kepadatan. Ini memiliki dua parameter eps (sebagai radius lingkungan) dan minPts (sebagai tetangga minimum untuk mempertimbangkan titik sebagai titik inti) yang saya percaya sangat tergantung pada mereka.

Apakah ada metode rutin atau umum digunakan untuk memilih parameter ini?

clustering dbscan Mehraban
sumber
1
Perhatikan bahwa ada pertanyaan serupa tentang Stack Overflow : Memilih eps dan minpts untuk DBSCAN (R)?
gung - Reinstate Monica

Jawaban:

11

Ada banyak publikasi yang mengusulkan metode untuk memilih parameter ini.

Yang paling penting adalah OPTICS, variasi DBSCAN yang menghilangkan parameter epsilon; itu menghasilkan hasil hierarkis yang secara kasar dapat dilihat sebagai "menjalankan DBSCAN dengan setiap epsilon yang mungkin".

Untuk minPts, saya sarankan untuk tidak mengandalkan metode otomatis, tetapi pada pengetahuan domain Anda .

Algoritma pengelompokan yang baik memiliki parameter, yang memungkinkan Anda untuk menyesuaikannya dengan kebutuhan Anda.

Parameter yang Anda abaikan adalah fungsi jarak. Hal pertama yang harus dilakukan untuk DBSCAN adalah menemukan fungsi jarak yang baik untuk aplikasi Anda . Jangan mengandalkan jarak Euclidean menjadi yang terbaik untuk setiap aplikasi!

Memiliki QUIT - Anony-Mousse
sumber
Meskipun pengguna dapat memilih fungsi jarak, saya ragu itu adalah parameter.
Mehraban
1
Tentu saja. Ini adalah parameter sebanyak fungsi kernel untuk metode kernel lainnya (Anda sebenarnya dapat melakukan kernelisasi DBSCAN secara sepele dengan cara ini), dan menurut pengalaman saya, jarak lain seperti Canberra atau Clark dapat secara signifikan meningkatkan hasil .
Memiliki QUIT - Anony-Mousse
Saya tidak meremehkan pengaruh fungsi jarak pada pengelompokan, Tapi saya pikir itu agak umum, tidak spesifik untuk dbscan atau setiap algoritma pengelompokan lainnya; sedangkan eps dan minPts secara eksplisit adalah parameter dbscan.
Mehraban
1
Ada banyak algoritma berbasis non-jarak juga. Dan ketika Anda menganggap minPts sama dengan misalnya kuntuk klasifikasi tetangga terdekat, maka Anda bisa mengatakan hal yang sama untuk parameter minPts. Saya kira perbedaan utama adalah bahwa untuk jarak, ada "sering" default yang masuk akal: jarak Euclidean; sedangkan untuk minPts nilainya akan menjadi data spesifik.
Memiliki QUIT - Anony-Mousse
1
OPTICS sendiri tidak akan memberi Anda partisi, tetapi urutan cluster. Untuk mendapatkan partisi, gunakan ekstraksi xi yang dijelaskan dalam kertas OPTICS. Lihat setiap varian kertas untuk memahami perbedaannya.
Memiliki QUIT - Anony-Mousse