DBSCAN শব্দের সাথে অ্যাপ্লিকেশনের ঘনত্ব-ভিত্তিক স্থানিক ক্লাস্টারিং বোঝায়। এটি একটি ঘনত্ব ভিত্তিক ক্লাস্টারিং অ্যালগরিদম। অ্যালগরিদম যথেষ্ট উচ্চ ঘনত্ব সহ অঞ্চলগুলিকে ক্লাস্টারে পরিণত করে এবং শব্দের সাথে স্থানিক ডাটাবেসে নির্বিচারে আর্কিটেকচারের ক্লাস্টারগুলি খুঁজে পায়। এটি ঘনত্ব-সংযুক্ত পয়েন্টগুলির সর্বাধিক গোষ্ঠী হিসাবে একটি ক্লাস্টারকে প্রতিনিধিত্ব করে৷
ঘনত্ব-ভিত্তিক ক্লাস্টারিংয়ের ধারণাটি নিম্নরূপ অনেকগুলি নতুন সংজ্ঞা অন্তর্ভুক্ত করে -
-
প্রদত্ত বস্তুর ε ব্যাসার্ধের মধ্যে অবস্থিত আশেপাশের এলাকাটিকে বস্তুর প্রতিবেশী বলা হয়।
-
যদি কোনো বস্তুর ε-আশেপাশে বস্তুর অন্ততপক্ষে একটি ন্যূনতম সংখ্যা, MinPts, অবজেক্ট থাকে, তাহলে অবজেক্টটিকে কোর অবজেক্ট বলা হয়।
-
বস্তুর একটি সেট দেওয়া হলে, D, এটি বলতে পারে যে একটি বস্তু p বস্তু q থেকে সরাসরি ঘনত্ব-পৌছানো যায় যদি p q এর ε-প্রতিবেশীর ভিতরে থাকে এবং q একটি মূল বস্তু।
-
বস্তুর p1 বস্তুর একটি শৃঙ্খল থাকলে, D বস্তুর একটি গোষ্ঠীতে ε এবং MinPts সম্পর্কিত বস্তু q থেকে একটি বস্তুর ঘনত্ব-পৌছানো যায়। ,..., pn , যেখানে p1 =q এবং pn =p সহ pi +1 pi থেকে সরাসরি ঘনত্বে পৌঁছানো যায় ε এবং MinPts সম্পর্কিত, 1 ≤ i ≤ n, pi এর জন্য ε ডি.
-
একটি বস্তু p হল বস্তুর একটি গোষ্ঠীতে ε এবং MinPts সম্পর্কিত বস্তু q-এর সাথে ঘনত্ব-লিঙ্কযুক্ত>
ঘনত্বের প্রাপ্যতা হল প্রত্যক্ষ ঘনত্বের পৌঁছানোর ট্রানজিটিভ ক্লোজার, এবং এই সংযোগটি অপ্রতিসম। শুধুমাত্র মূল বস্তু আছে পারস্পরিক ঘনত্ব পৌঁছানো যায়. ঘনত্ব সংযোগ একটি প্রতিসম সম্পর্ক।
একটি ঘনত্ব-ভিত্তিক ক্লাস্টার হল ঘনত্ব-সংযুক্ত বস্তুর একটি গোষ্ঠী যা ঘনত্ব-নাগালের ক্ষেত্রে সর্বাধিক। কোনো ক্লাস্টারে অন্তর্ভুক্ত নয় এমন প্রতিটি বস্তুকে শব্দ বলে গণ্য করা হয়।
DBSCAN ডাটাবেসের প্রতিটি পয়েন্টের ε-প্রতিবেশী পরীক্ষা করে ক্লাস্টার অনুসন্ধান করে। যদি একটি বিন্দু p-এর ε-প্রতিবেশীতে MinPts-এর চেয়ে বেশি অন্তর্ভুক্ত থাকে, তাহলে একটি মূল বস্তু হিসাবে p সহ একটি নতুন ক্লাস্টার তৈরি করা হয়। DBSCAN পুনরাবৃত্তভাবে এই মূল বস্তুগুলি থেকে সরাসরি ঘনত্ব-নাগালযোগ্য বস্তু সংগ্রহ করে, যেটিতে কয়েকটি ঘনত্ব-পৌঁছানো ক্লাস্টারের একত্রীকরণ থাকতে পারে। যখন কোনো ক্লাস্টারে কোনো নতুন পয়েন্ট ঢোকানো যায় না তখন প্রক্রিয়াটি সরিয়ে দেয়।
যদি একটি স্থানিক সূচক ব্যবহার করা হয়, DBSCAN-এর গণনাগত জটিলতা হল O(nlogn), যেখানে n হল ডাটাবেস বস্তুর সংখ্যা। অতএব, এটি O (n 2 ) ) ব্যবহারকারী-উপস্থিত পরামিতি ε এবং MinPts এর উপযুক্ত সেটিংসের সাথে, অ্যালগরিদম নির্বিচারে-আকৃতির ক্লাস্টারগুলি আবিষ্কার করতে দক্ষ৷
