DBSCAN

همچنین ارتباط نقاط بر اساس وضعیتشان (مرکزی بودن یا نبودن) در هر خوشه، به سه دسته تقسیم می‌شوند:

1. نقاط متصل: نقطه به یک خوشه متصل است که اولاً نقطه مرکزی باشد. ثانیاً با یکی از نقاط داخل خوشه همسایه باشند.
2. نقاط دسترسی پذیر: نقطه به خوشه دسترسی پذیر است که نقطه مرکزی نباشد ولی با یکی از نقاط داخل خوشه همسایه باشد.
3. اگر نقطه هیچ‌یک از وضعیت‌های بالا را نداشته باشد، نویز برای آن خوشه محسوب می‌شود. همچنین اگر نقطه نسبت به تمام خوشه‌ها نویز باشد، در خوشه نویز قرار می‌گیرد.

در شکل زیر نقاط قرمز رنگ نقاط مرکزی هستند. نقاط زرد به خوشه مشخص شده دسترسی دارند. نقطه آبی، نویز است. برای شکل زیر μ برابر با ۳ در نظر گرفته شده‌است.

DBSCNA

روند الگوریتم در شبه کد زیر آورده شده‌است. در ابتدا نقطه به صورت اختیاری انتخاب می‌شود که قبلاً بازدید نشده‌است. همسایگی این نقطه به شعاع ε بررسی می‌شود و در صورتی که حداقل تعداد نقاط همسایگی لازم را داشت. خوشه ایجاد می‌شود وگرنه نقطه نویزی برچسب می‌خورد. نکته قابل این است که در ادامه ممکن است این نقطه در همسایگی دیگر نقاط قرار گیردو قسمتی از خوشه دیگر شود.

DBSCAN(D, eps, MinPts) {
 C = ۰
 for each point P in dataset D {
 if P is visited
 continue next point
 mark P as visited
 NeighborPts = regionQuery(P, eps)
 if sizeof(NeighborPts) <MinPts
 mark P as NOISE
 else {
 C = next cluster
 expandCluster(P, NeighborPts, C, eps, MinPts)
 }
 }
}

expandCluster(P, NeighborPts, C, eps, MinPts) {
 add P to cluster C
 for each point P' in NeighborPts {
 if P' is not visited {
 mark P' as visited
 NeighborPts' = regionQuery(P', eps)
 if sizeof(NeighborPts')>= MinPts
 NeighborPts = NeighborPts joined with NeighborPts'
 }
 if P' is not yet member of any cluster
 add P' to cluster C
 }
}
 regionQuery(P, eps)
 return all points within P's eps-neighborhood (including P)