خوشه‌بندي بر اساس چگالي!
 

خوشه‌بندي بر اساس چگالي

اين روشهاي خوشه‌بندي بر اين اصل استوارند که خوشه‌ها‌، ناحيه‌هايي از فضاي داده با چگالي زيادي هستند که توسط نواحي با چگالي کمتر از همديگر جدا شده‌اند. براي پياده‌سازي اين روشهاي خوشه‌بندي لازم است تا ابتدا اصطلاحاتي تعريف شوند:[3]
چگالي نقاط محلي در نقطة P (Local Point Density) : اگر P را نقطة هستة يک همسايگي و ε شعاع همسايگي براي نقطة P در نظر گرفته شود آنگاه همسايگي به شعاع ε براي نقطة P به صورت زير تعريف مي‌شود:
(7)

به تعداد نقاط قرار گرفته شده درون يک همسايگيِ داده شده چگالي نقاط آن همسايگي گفته مي‌شود.

http://ceit.aut.ac.ir/~shiry/lecture...s/image004.jpg
شکل 12: يک همسايگي براي P داراي چگالي نقاط 5

º در دسترسِ مستقيمِ چگالي (Directly Density-Reachable): دادة p را در دسترسِ مستقيمِ چگاليِ q گويند اگر p درون يک همسايگي به شعاع ε با هستة q باشد. در شکل زير بهتر مي‌توان اين مفهوم را درک کرد.

http://ceit.aut.ac.ir/~shiry/lecture...s/image004.jpg
شکل 13: p در دسترسِ مستقيمِ چگاليِ q قرار دارد.

º در دسترسِ چگالي (Density-Reachable): دادة p را در دسترسِ چگاليِ q گويند اگر داده‌اي وجود داشته باشد که هم درون يک همسايگي به شعاع ε با هستة p و هم درون يک همسايگي به شعاع ε با هستة q باشد. در شکل زير بهتر مي‌توان اين مفهوم را درک کرد.

http://ceit.aut.ac.ir/~shiry/lecture...s/image008.gif
شکل 14: p در دسترسِ چگاليِ q قرار دارد.


º متصلِ چگالي (Density-Connected): دادة p را متصلِ چگاليِ q گويند اگر داده‌اي مانند o وجود داشته باشد که هم در دسترسِ چگاليِ p و هم در دسترسِ چگاليِ q باشد. در شکل زير بهتر مي‌توان اين مفهوم را درک کرد.

http://ceit.aut.ac.ir/~shiry/lecture...s/image010.gif
شکل 15: p متصلِ چگاليِ q است.

º خوشة مبتني بر چگالي (Density-Based Cluster): زير مجموعه‌اي غيرتهي(S) از مجموعة داده‌ها (D) که داراي دو شرط زير باشد:
§ حداکثر: اگر p درون S باشد و q در دسترسِ چگاليِ p باشد آنگاه q نيز متعلق به S باشد.
§ اتصال: هر دادة درون S متصلِ چگاليِ ساير داده‌هاي درون S باشد.

o خوشه‌بندي بر اساس چگالي (Density-Based Clustering): خوشه‌بندي بر اساس چگالي بر روي مجموعة دادة D مجموعه‌اي به صورت {S1, …, Sn, N} است که :
§ S1, …, Sn تمام خوشه‌هاي مبتني چگاليِ درون D است.
§ N=D\{ S1, …, Sn } مجموعة نويز خوانده مي‌شود.

http://ceit.aut.ac.ir/~shiry/lecture...s/image012.jpg
شکل 16: خوشه‌بندي بر اساس چگالي

الگوريتم خوشه‌بندي براساس چگالي DBSCAN: در اين روش خوشه‌بندي هر دادة متعلق به خوشة C در دسترس چگالي ساير داده‌هاي متعلق به آن خوشه‌ است و در دسترس چگالي هيچ دادة ديگري قرار ندارد. شبه کد اين الگوريتم را زير مشاهده مي‌کنيد.


http://ceit.aut.ac.ir/~shiry/lecture...s/image014.gif
1-1-1- مثالي از الگوريتم خوشه‌بندي براساس چگالي DBSCAN: در شکل زير سعي شده است تا نحوة اعمال الگوريتم خوشه‌بندي DBSCAN را بر روي يک مجموعه داده نشان داده شود. همان‌گونه که مشاهده مي‌شود، اين الگوريتم نوانسته ‌است به خوبي داده‌ها را خوشه‌بندي کند.


http://ceit.aut.ac.ir/~shiry/lecture...s/image016.gif
(b)
http://ceit.aut.ac.ir/~shiry/lecture...s/image018.jpg
(a)

http://ceit.aut.ac.ir/~shiry/lecture...s/image020.jpg
(d)

http://ceit.aut.ac.ir/~shiry/lecture...s/image022.jpg
(c)

http://ceit.aut.ac.ir/~shiry/lecture...s/image024.jpg
(f)

شکل 17: مثالي از روش خوشه‌بندي DBSCAN

الگوريتم سلسله مراتبي خوشه‌بندي براساس چگالي OPTICS:
در اين روش سعي مي‌شود تا با تکنيکي سلسله مراتبي خوشه‌هاي بزرگتري را از ترکيب خوشه‌اي داراي چگالي زياد ولي کوچک‌تر محاسبه کرد. در شکل زير با يک بار اعمال الگوريتم خوشه‌بندي DBSCAN خوشه‌هاي C1 و C2 حاصل گشته‌اند که در مرحلة ديگري با هم ترکيب شده و خوشة بزرگتر C را ساخته‌اند. در اين روش با افزايش تعداد تکرار مقدار پارامتر ε افزايش مي‌يابد.

http://ceit.aut.ac.ir/~shiry/lecture...s/image026.gif
شکل 18: در روش سلسله مراتبي خوشه‌بندي براساس چگالي OPTICS از ترکيب خوشه‌هاي با چگالي زياد و کوچک خوشه‌هاي بزرگتري حاصل مي‌شود.

مزاياي خوشه‌بندي بر اساس چگالي
a. خوشه‌ها مي‌توانند داراي اشکال دلخواه باشند.
b. تعداد خوشه‌ها به صورت اتوماتيک همزمان با عمل خوشه‌بندي تعيين مي‌شود.
c. در تشخيص نويزها بسيار کارا هستند