DBSCAN - DBSCAN

Ilovalarning shovqin bilan zichligiga asoslangan fazoviy klasteri (DBSCAN) a ma'lumotlar klasteri tomonidan taklif qilingan algoritm Martin Ester, Xans-Piter Krigel, Yorg Sander va Xiaowei Xu 1996 yilda.^[1]Bu zichlikka asoslangan klasterlash parametrik bo'lmagan algoritm: ba'zi bir bo'shliqdagi bir qator berilgan holda, u bir-biriga chambarchas bog'langan nuqtalarni birlashtiradi (ko'plari bo'lgan nuqtalar yaqin qo'shnilar ), zichligi past bo'lgan mintaqalarda (ularning yaqin qo'shnilari juda uzoq) yolg'iz yotadigan fikrlarni ustun deb belgilash .DBSCAN klasterlashning eng keng tarqalgan algoritmlaridan biri bo'lib, shuningdek, ilmiy adabiyotlarda eng ko'p keltirilgan.^[2]

2014 yilda algoritm vaqt sinovi mukofotiga sazovor bo'ldi (nazariya va amaliyotda katta e'tiborga ega bo'lgan algoritmlarga berilgan mukofot) ma'lumotlar uzatish bo'yicha etakchi konferentsiyada ACM SIGKDD.^[3] 2020 yil iyul oyidan boshlab^[yangilash], "DBSCAN qayta ko'rib chiqildi, qayta ko'rib chiqildi: nima uchun va qanday qilib DBSCAN dan foydalanishingiz kerak (hanuzgacha)"^[4] obro'li eng ko'p yuklab olingan 8 ta maqola ro'yxatida paydo bo'ladi Ma'lumotlar bazalari tizimlarida ACM operatsiyalari (TODS) jurnal.^[5]

Tarix

1972 yilda Robert F. Ling "k-klasterlar nazariyasi va qurilishi" da yaqin algoritmni nashr etdi.^[6] yilda Kompyuter jurnali taxminiy ish vaqti murakkabligi bilan O (n³).^[6] DBSCAN O (n²) ning eng yomon holatiga ega va DBSCAN ma'lumotlar bazasiga yo'naltirilgan intervalli so'rov formulasi indeksni tezlashtirishga imkon beradi. Algoritmlar chegara nuqtalari bilan ishlashda bir oz farq qiladi.

Dastlabki

Klasterlangan ba'zi bir bo'shliqdagi bir qator fikrlarni ko'rib chiqing. Ruxsat bering ε bir nuqtaga nisbatan mahalla radiusini belgilaydigan parametr bo'ling. DBSCAN klasteri uchun ballar quyidagicha tasniflanadi asosiy fikrlar, (zichlik-)erishish mumkin bo'lgan fikrlar va chetga chiquvchilar, quyidagicha:

• Bir nuqta p a asosiy nuqta hech bo'lmaganda minPts nuqtalar masofada joylashgan ε uning (shu jumladan p).
• Bir nuqta q bu to'g'ridan-to'g'ri erishish mumkin dan p agar nuqta q masofada joylashgan ε asosiy nuqtadan p. Ballarga faqat asosiy nuqtalardan to'g'ridan-to'g'ri erishish mumkinligi aytiladi.
• Bir nuqta q bu erishish mumkin dan p agar yo'l bo'lsa p₁, ..., p_n bilan p₁ = p va p_n = q, har birida p_men+1 to'g'ridan-to'g'ri erishish mumkin p_men. Shuni esda tutingki, bu boshlang'ich nuqta va yo'lning barcha nuqtalari, ehtimol istisnolardan tashqari, asosiy nuqtalar bo'lishi kerak q.
• Boshqa nuqtalardan erishish mumkin bo'lmagan barcha fikrlar chetga chiquvchilar yoki shovqin nuqtalari.

Endi agar p asosiy nuqta, keyin u hosil qiladi klaster undan erishish mumkin bo'lgan barcha nuqtalar (yadroli yoki yadrosiz) bilan birgalikda. Har bir klaster kamida bitta asosiy nuqtani o'z ichiga oladi; yadro bo'lmagan nuqtalar klasterning bir qismi bo'lishi mumkin, ammo ular uning "chekkasini" tashkil qiladi, chunki ularni ko'proq nuqtalarga erishish uchun ishlatish mumkin emas.

Ushbu diagrammada, minPts = 4. A nuqta va boshqa qizil nuqtalar yadro nuqtalaridir, chunki bu nuqtalarni an ichida o'rab turgan maydon ε radiusi kamida 4 nuqtani o'z ichiga oladi (shu nuqtaning o'zi ham). Ularning barchasi bir-biridan foydalanish imkoniyatiga ega bo'lganligi sababli, ular bitta klasterni tashkil qiladi. B va C nuqtalari asosiy nuqtalar emas, balki A dan (boshqa yadro nuqtalari orqali) o'tish mumkin va shu bilan klasterga tegishli. N nuqta - bu shovqin nuqtasi, u na asosiy nuqta, na to'g'ridan-to'g'ri erishib bo'lmaydi.

Reachability nosimmetrik munosabat emas: ta'rifi bo'yicha faqat yadro nuqtalari yadro bo'lmagan nuqtalarga etib borishi mumkin. Buning aksi to'g'ri emas, shuning uchun yadro bo'lmagan nuqtaga erishish mumkin, ammo undan hech narsaga erishib bo'lmaydi. Shuning uchun, keyingi tushuncha ulanish DBSCAN tomonidan topilgan klasterlar hajmini rasmiy ravishda aniqlash uchun kerak. Ikki nuqta p va q nuqta bo'lsa zichlikka bog'langan o ikkalasi ham shunday p va q dan foydalanish mumkin o. Zichlik bilan bog'liqlik bu nosimmetrik.

Keyin klaster ikkita xususiyatni qondiradi:

1. Klaster ichidagi barcha nuqtalar o'zaro zichlik bilan bog'langan.
2. Agar nuqta klasterning biron bir nuqtasidan zichlikka ega bo'lsa, u klasterning bir qismidir.

Algoritm

Asl so'rovlarga asoslangan algoritm

DBSCAN ikkita parametrni talab qiladi: ε (eps) va zich mintaqani hosil qilish uchun zarur bo'lgan minimal ball^[a] (minPts). U tashrif buyurmagan o'zboshimchalik bilan boshlang'ich nuqtadan boshlanadi. Ushbu nuqtaning ε-mahallasi olinadi va agar u etarlicha ko'p nuqtalarni o'z ichiga olsa, klaster boshlanadi. Aks holda, nuqta shovqin sifatida belgilanadi. Shuni esda tutingki, keyinchalik bu nuqta boshqa nuqtaning etarlicha o'lchamdagi ε-muhitida topilishi va shu sababli klasterning bir qismiga aylanishi mumkin.

Agar nuqta klasterning zich qismi ekanligi aniqlansa, uning ε-mahallasi ham shu klasterning bir qismidir. Demak, ε-mahalla ichida topilgan barcha fikrlar, shuningdek, ularning zichligi bo'lganida o'zlarining ε-mahallalari qo'shiladi. Ushbu jarayon zichlikka bog'langan klaster to'liq topilmaguncha davom etadi. Keyinchalik, yangi kutilmagan nuqta olinadi va qayta ishlanadi, bu esa qo'shimcha klaster yoki shovqinni topishga olib keladi.

DBSCAN dan har qanday masofaviy funktsiya bilan foydalanish mumkin^[1][4] (shuningdek, o'xshashlik funktsiyalari yoki boshqa predikatlar).^[7] Masofa funktsiyasi (dist) shuning uchun qo'shimcha parametr sifatida qaralishi mumkin.

Algoritmni quyidagicha ifodalash mumkin psevdokod quyidagicha:^[4]

DBSCAN (JB, distFunc, eps, minPts) {C: = 0 / * Klaster hisoblagichi * /    har biriga nuqta P yilda ma'lumotlar bazasi JB { agar yorliq (P) ≠ aniqlanmagan keyin davom eting               / * Ilgari ichki tsiklda qayta ishlangan * /        Qo'shnilar N: = RangeQuery (DB, distFunc, P, eps) / * Qo'shnilarni topish * /        agar | N | keyin {                              / * Zichlikni tekshirish * /            yorliq (P): = Shovqin / * Shovqin sifatida yorliq * /            davom eting        } C: = C + 1 / * keyingi klaster yorlig'i * /        yorliq (P): = C / * Yorliqning dastlabki nuqtasi * /        SeedSet S: = N {P} / * Kengayadigan qo'shnilar * /        har biriga nuqta Q yilda S { / * Har bir urug 'nuqtasini qayta ishlash Q * /            agar yorliq (Q) = shovqin keyin yorliq (Q): = C / * Shovqinni chegara nuqtasiga o'zgartiring * /            agar yorliq (Q) ≠ aniqlanmagan keyin davom eting           / * Ilgari qayta ishlangan (masalan, chegara punkti) * /            yorliq (Q): = C / * Yorliq qo'shni * /            Qo'shnilar N: = RangeQuery (JB, distFunc, Q, eps) / * Qo'shnilarni topish * /            agar | N | ≥ minPts keyin {                          / * Zichlikni tekshirish (agar Q asosiy nuqta bo'lsa) * /                S: = S ∪ N / * Urug'lar to'plamiga yangi qo'shnilarni qo'shish * /            }        }    }}

bu erda RangeQuery yaxshiroq ishlash uchun ma'lumotlar bazasi indeksidan foydalangan holda yoki sekin chiziqli skanerlash yordamida amalga oshirilishi mumkin:

RangeQuery (JB, distFunc, Q, eps) {Qo'shnilar N: = bo'sh ro'yxat har biriga nuqta P yilda ma'lumotlar bazasi JB { / * Ma'lumotlar bazasidagi barcha nuqtalarni skanerlash * /        agar distFunc (Q, P) ≤ eps keyin {                     / * Masofani hisoblang va epsilonni tekshiring * /            N: = N ∪ {P} / * Natijaga qo'shish * /        }    }    qaytish N}

Abstrakt algoritm

DBSCAN algoritmi quyidagi bosqichlarda qisqartirilishi mumkin:^[4]

1. Har bir nuqtaning ε (eps) atrofidagi nuqtalarni toping va minPts dan ko'proq qo'shnilar bilan asosiy nuqtalarni aniqlang.
2. Toping ulangan komponentlar ning yadro barcha yadro bo'lmagan fikrlarni e'tiborsiz qoldirib, qo'shni grafadagi nuqtalarni.
3. Yadro klasteriga yadro bo'lmagan har bir nuqtani tayinlang, agar klaster ε (eps) qo'shni bo'lsa, aks holda uni shovqinga tayinlang.

Buning sodda amalga oshirilishi uchun mahallalarni 1-bosqichda saqlash kerak, shu bilan katta xotira talab etiladi. Dastlabki DBSCAN algoritmi ushbu amallarni bir vaqtning o'zida bir nuqtada bajarish orqali talab qilmaydi.

Murakkablik

DBSCAN ma'lumotlar bazasining har bir nuqtasiga, ehtimol bir necha marta tashrif buyuradi (masalan, turli guruhlarga nomzod sifatida). Amaliy mulohazalar uchun vaqtning murakkabligi asosan mintaqalar soni bo'yicha boshqariladi So'rovnomalar. DBSCAN har bir nuqta uchun aynan bitta shunday so'rovni bajaradi va agar shunday bo'lsa indeksatsiya tuzilishi ni bajaradigan foydalaniladi mahalla so'rovi yilda O (log n), ishning umumiy o'rtacha murakkabligi O (n jurnal n) olinadi (agar parametr bo'lsa ε mazmunli tarzda tanlanadi, ya'ni faqat o'rtacha O (log n) ballar qaytariladi). Tezlashtiruvchi indeks tuzilmasidan yoki buzilgan ma'lumotlardan foydalanmasdan (masalan, masofadan past bo'lgan barcha nuqtalar ε), eng yomon ish vaqti murakkabligi saqlanib qoladi O (n²). O'lchamning masofa matritsasi (n²-n)/2 masofani hisoblashdan qochish uchun moddiylashtirilishi mumkin, ammo bunga ehtiyoj bor O (n²) matritsasiz dastur DBSCAN dasturini faqat talab qiladi O (n) xotira.

DBSCAN chiziqli bo'linmaydigan klasterlarni topishi mumkin. Ushbu ma'lumotlar bazasini k-vositalari yoki Gaussian Mixture EM klasteri bilan etarli darajada klasterlash mumkin emas.

Afzalliklari

1. DBSCAN dan farqli o'laroq, ma'lumotdagi klasterlar sonini oldindan belgilashni talab qilmaydi k-degani.
2. DBSCAN o'zboshimchalik shaklidagi klasterlarni topishi mumkin. Hatto boshqa klaster bilan to'liq o'ralgan (lekin unga ulanmagan) klasterni ham topishi mumkin. MinPts parametri tufayli bitta bog'lanish effekti deb ataladigan narsa (turli klasterlar ingichka chiziqlar bilan bog'langan) kamayadi.
3. DBSCAN-da shovqin tushunchasi bor va u baquvvatdir chetga chiquvchilar.
4. DBSCAN faqat ikkita parametrni talab qiladi va ma'lumotlar bazasidagi punktlarning tartibiga asosan befarq. (Biroq, ikki xil klasterning chetida o'tirgan punktlar, agar ballarning tartibi o'zgartirilsa, klasterga a'zolikni almashtirishi mumkin va klasterni tayinlash faqat izomorfizmgacha noyobdir.)
5. DBSCAN mintaqaviy so'rovlarni tezlashtiradigan ma'lumotlar bazalari bilan ishlash uchun mo'ljallangan, masalan. yordamida R * daraxti.
6. Agar ma'lumotlar yaxshi tushunilgan bo'lsa, minPts va ε parametrlarini domen mutaxassisi o'rnatishi mumkin.

Kamchiliklari

1. DBSCAN butunlay deterministik emas: bir nechta klasterlardan foydalanish mumkin bo'lgan chegara nuqtalari, ma'lumotlar qayta ishlash tartibiga qarab har ikkala klasterning bir qismi bo'lishi mumkin. Ko'pgina ma'lumotlar to'plamlari va domenlari uchun bu holat tez-tez uchramaydi va klasterlash natijasiga unchalik ta'sir qilmaydi:^[4] ham asosiy nuqtalarda, ham shovqin nuqtalarida DBSCAN deterministikdir. DBSCAN *^[8] chegara punktlarini shovqin sifatida qabul qiladigan o'zgarishdir va shu bilan zichlik bilan bog'liq komponentlarning statistik izohlanishi bilan bir qatorda to'liq deterministik natijaga erishiladi.
2. DBSCAN-ning sifati quyidagilarga bog'liq masofa o'lchovi regionQuery (P, ε) funktsiyasida ishlatiladi. Amaldagi eng keng tarqalgan metrik Evklid masofasi. Ayniqsa uchun yuqori o'lchovli ma'lumotlar, ushbu metrik "deb nomlangan narsa tufayli deyarli foydasiz bo'lishi mumkinO'lchovlilikning la'nati "uchun mos qiymatni topishni qiyinlashtirmoqda. Biroq, bu effekt Evklid masofasiga asoslangan boshqa har qanday algoritmda ham mavjud.
3. DBSCAN ma'lumotlar zichligini zichlikdagi katta farqlar bilan yaxshi klasterlay olmaydi, chunki minPts-ε kombinatsiyasini keyinchalik barcha klasterlar uchun to'g'ri tanlab bo'lmaydi.^[9]
4. Agar ma'lumotlar va o'lchov yaxshi tushunilmagan bo'lsa, mazmunli masofa chegarasini tanlash qiyin bo'lishi mumkin.

Ushbu masalalarni hal qilish uchun algoritmik o'zgartirishlar uchun kengaytmalar haqidagi quyidagi bo'limga qarang.

Parametrlarni baholash

Ma'lumotlarni qazib olish bo'yicha har qanday vazifada parametrlar muammosi mavjud. Har qanday parametr algoritmga ma'lum usullar bilan ta'sir qiladi. DBSCAN uchun parameters va parametrlari minPts kerak. Parametrlar foydalanuvchi tomonidan ko'rsatilishi kerak. Ideal holda, ε ning qiymati echilishi kerak bo'lgan muammo bilan beriladi (masalan, jismoniy masofa) va minPts keyin kerakli minimal klaster hajmi.^[a]

• MinPts: Bosh qoida bo'yicha, minimal minPts o'lchovlar sonidan kelib chiqishi mumkin D. ma'lumotlar to'plamida, kabi minPts ≥ D. + 1. ning past qiymati minPts = 1 mantiqqa to'g'ri kelmaydi, chunki har bir nuqta o'zi allaqachon klaster bo'ladi.^{[shubhali – muhokama qilish]} Bilan minPts ≤ 2, natija bilan bir xil bo'ladi ierarxik klasterlash dendrogram bilan link balandlikda kesilgan holda, bitta bog'lanish metrikasi bilan. Shuning uchun, minPts kamida 3. Tanlangan bo'lishi kerak. Ammo, shovqinli ma'lumotlar to'plamlari uchun kattaroq qiymatlar odatda yaxshiroqdir va muhim klasterlarni keltirib chiqaradi. Qoida tariqasida, minPts = 2·xira foydalanish mumkin,^[7] ammo juda katta ma'lumotlar uchun, shovqinli ma'lumotlar uchun yoki ko'plab takroriy ma'lumotlarni o'z ichiga olgan kattaroq qiymatlarni tanlash kerak bo'lishi mumkin.^[4]
• ε: keyin ε uchun qiymatni a yordamida tanlash mumkin k masofa grafigi, gacha bo'lgan masofani chizish k = minPts-1 eng yaqin qo'shnisi eng kattasidan eng kichigigacha buyurtma bergan.^[4] $ Delta $ ning yaxshi qiymatlari, bu erda "tirsak" ko'rsatilgan:^[1][7][4] agar ε juda kichik tanlangan bo'lsa, ma'lumotlarning katta qismi klaster qilinmaydi; $ Delta $ ning juda yuqori qiymati uchun klasterlar birlashadi va ob'ektlarning aksariyati bir xil klasterda bo'ladi. Umuman olganda, ε ning kichik qiymatlari afzalroq,^[4] va qoidalar bo'yicha ballarning faqat kichik qismi bir-biridan shu masofada bo'lishi kerak. Shu bilan bir qatorda, an OPTIKA uchastkadan ε ni tanlash uchun foydalanish mumkin,^[4] ammo keyin OPTICS algoritmining o'zi ma'lumotlarni klasterlash uchun ishlatilishi mumkin.
• Masofa funktsiyasi: masofa funktsiyasini tanlash ε ni tanlash bilan chambarchas bog'langan va natijalarga katta ta'sir ko'rsatadi. Umuman olganda, parametr parametrini tanlashdan oldin, avval ma'lumotlar to'plami uchun oqilona o'xshashlik o'lchovini aniqlash kerak bo'ladi. Ushbu parametr uchun taxmin yo'q, ammo masofa funktsiyalari ma'lumotlar to'plamiga mos ravishda tanlanishi kerak. Masalan, geografik ma'lumotlarda katta doiradagi masofa ko'pincha yaxshi tanlovdir.

OPTIKA parametrini asosan ishlashga ta'sir qiladigan maksimal qiymat bilan almashtiradigan DBSCAN-ning umumlashtirilishi sifatida qarash mumkin. MinPts u holda aslida topish uchun minimal klaster hajmi bo'ladi. Algoritmni parametrlash DBSCANga qaraganda ancha osonroq bo'lsa-da, natijalarni ishlatish biroz qiyinroq, chunki odatda DBSCAN ishlab chiqaradigan oddiy ma'lumotlar bo'limi o'rniga ierarxik klaster hosil qiladi.

Yaqinda DBSCAN-ning asl mualliflaridan biri DBSCAN va OPTICS-ni qayta ko'rib chiqdi va DBSCAN-ning (HDBSCAN *) ierarxikali versiyasini nashr etdi,^[8] endi chegara punktlari tushunchasi yo'q. Buning o'rniga faqat asosiy nuqtalar klasterni tashkil qiladi.

Spektral klasterlash bilan bog'liqlik

DBSCAN ni maxsus (samarali) variant sifatida ko'rish mumkin spektral klasterlash: Bog'langan komponentlar optimal spektral klasterlarga mos keladi (qirralarning kesilishi yo'q - spektral klasterlash ma'lumotni a bilan ajratishga harakat qiladi minimal kesish ); DBSCAN ulangan komponentlarni (assimetrik) erishish grafigidan topadi.^[10] Biroq, spektral klasterlash hisoblash intensiv bo'lishi mumkin (gacha ${displaystyle O (n ^ {3})}$ yaqinlashmasdan va qo'shimcha taxminlarsiz) va klasterlar sonini tanlash kerak ${displaystyle k}$ tanlanadigan xususiy vektorlar soni uchun ham, spektral ko'mishda k-vositalar bilan ishlab chiqariladigan klasterlar soni uchun ham. Shunday qilib, ishlash sabablari bo'yicha asl DBSCAN algoritmi spektrli dasturdan afzalroq bo'lib qolmoqda va bu munosabatlar hozircha faqat nazariy jihatdan qiziqish uyg'otmoqda.

Kengaytmalar

Umumlashtirilgan DBSCAN (GDBSCAN)^[7][11] bir xil mualliflar tomonidan o'zboshimchalik bilan "mahalla" va "zich" predikatlar uchun umumlashtirishdir. Ε va minPts parametrlar dastlabki algoritmdan olib tashlanadi va predikatlarga o'tkaziladi. Masalan, ko'pburchak ma'lumotlarida "mahalla" har qanday kesishgan ko'pburchak bo'lishi mumkin, zichlik predikati esa ob'ektlar soni o'rniga ko'pburchak maydonlardan foydalanadi.

DBSCAN algoritmiga turli xil kengaytmalar, jumladan, parallellashtirish, parametrlarni baholash va noaniq ma'lumotlarni qo'llab-quvvatlash usullari taklif qilingan. Asosiy g'oya ierarxik klasterlash uchun kengaytirilgan OPTICS algoritmi. DBSCAN shuningdek, PreDeCon va kabi subspace klaster algoritmlarining bir qismi sifatida ishlatiladi SUBCLU. HDBSCAN^[8] bu DBSCAN-ning ierarxik versiyasi bo'lib, u ham OPTICS-ga qaraganda tezroq bo'lib, undan eng taniqli klasterlardan tashkil topgan tekis bo'linishni ierarxiyadan olish mumkin.^[12]

Mavjudligi

Xuddi shu algoritmning turli xil tatbiq etilishi juda katta farqlarni ko'rsatdi, natijada test ma'lumotlarining tezligi 1,4 soniyada tugadi, eng sekini 13803 soniyani oladi.^[13] Farqlarni amalga oshirish sifati, til va kompilyator farqlari va tezlashtirish uchun indekslardan foydalanish bilan bog'lash mumkin.

• Apache Commons Matematika kvadratik vaqt ichida ishlaydigan algoritmning Java dasturini o'z ichiga oladi.
• ELKI DBSCAN dasturini, shuningdek GDBSCAN va boshqa variantlarini taklif qiladi. Ushbu dastur subkvadratik ish vaqti uchun turli xil indeks tuzilmalaridan foydalanishi mumkin va o'zboshimchalik bilan masofaviy funktsiyalarni va o'zboshimchalik bilan ma'lumotlar turlarini qo'llab-quvvatlaydi, ammo u kichik ma'lumotlar to'plamlarida past darajadagi optimallashtirilgan (va ixtisoslashgan) dasturlar bilan ustun bo'lishi mumkin.
• mlpack ikki qatorli qidiruv texnikasi bilan tezlashtirilgan DBSCAN dasturini o'z ichiga oladi.
• PostGIS ST_ClusterDBSCAN-ni o'z ichiga oladi - DBSCAN-ning 2-darajali bajarilishi, bu R-daraxt indeksidan foydalanadi. Har qanday geometriya turi qo'llab-quvvatlanadi, masalan. Point, LineString, Polygon va boshqalar.
• R paketlarda DBSCAN dasturlarini o'z ichiga oladi dbscan va kompyuter. Ikkala paket masofaviy matritsalar orqali o'zboshimchalik bilan masofaviy funktsiyalarni qo'llab-quvvatlaydi. Fpc to'plami indeksni qo'llab-quvvatlamaydi (va shuning uchun kvadratik ish vaqti va xotira murakkabligi) va R tarjimoni tufayli juda sekin. Dbscan to'plami yordamida tezkor C ++ dasturini taqdim etadi k-d daraxtlari (faqat Evklid masofasi uchun) va DBSCAN *, HDBSCAN *, OPTICS, OPTICSXi va shunga o'xshash boshqa usullarning dasturlarini o'z ichiga oladi.
• skikit o'rganish o'zboshimchalik uchun DBSCAN ning Python dasturini o'z ichiga oladi Minkovskiy ko'rsatkichlari yordamida tezlashtirilishi mumkin k-d daraxtlari va shar daraxtlari ammo bu eng yomon kvadratik xotiradan foydalanadi. A scikit-learn-ga hissa qo'shish HDBSCAN * algoritmini amalga oshirishni ta'minlaydi.
• pyclustering kutubxonada Python va C ++ dasturlari faqat Evklid masofasi uchun DBSCAN dasturini hamda OPTICS algoritmini o'z ichiga oladi.
• SPMF faqat evklid masofasi uchun k-d daraxtlarni qo'llab-quvvatlashi bilan DBSCAN algoritmini amalga oshirishni o'z ichiga oladi.
• Weka o'z ichiga oladi (so'nggi versiyalarida ixtiyoriy to'plam sifatida) kvadratik vaqt va chiziqli xotirada ishlaydigan DBSCAN ning asosiy dasturini o'z ichiga oladi.

Izohlar

Adabiyotlar