Artificial Intelligence - هوش مصنوعی - نمايش پست تنها

**Astaraki** · ۱۲-۴-۱۳۸۸, ۱۱:۴۳ بعد از ظهر

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

اين روشهاي خوشه‌بندي بر اين اصل استوارند که خوشه‌ها‌، ناحيه‌هايي از فضاي داده با چگالي زيادي هستند که توسط نواحي با چگالي کمتر از همديگر جدا شده‌اند. براي پياده‌سازي اين روشهاي خوشه‌بندي لازم است تا ابتدا اصطلاحاتي تعريف شوند:

چگالي نقاط محلي در نقطة P (Local Point Density) : اگر P را نقطة هستة يک همسايگي و ε شعاع همسايگي براي نقطة P در نظر گرفته شود آنگاه همسايگي به شعاع ε براي نقطة P به صورت زير تعريف مي‌شود:

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

شکل 12: يک همسايگي براي P داراي چگالي نقاط 5

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

شکل 13: p در دسترسِ مستقيمِ چگاليِ q قرار دارد.

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

شکل 14: p در دسترسِ چگاليِ q قرار دارد.

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

شکل 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 } مجموعة نويز خوانده مي‌شود.

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

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

1-1-1- مثالي از الگوريتم خوشه‌بندي براساس چگالي DBSCAN: در شکل زير سعي شده است تا نحوة اعمال الگوريتم خوشه‌بندي DBSCAN را بر روي يک مجموعه داده نشان داده شود. همان‌گونه که مشاهده مي‌شود، اين الگوريتم نوانسته ‌است به خوبي داده‌ها را خوشه‌بندي کند.
a

b

c:

d:

f :

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

الگوريتم سلسله مراتبي خوشه‌بندي براساس چگالي OPTICS:

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

شکل 18: در روش سلسله مراتبي خوشه‌بندي براساس چگالي OPTICS از ترکيب خوشه‌هاي با چگالي زياد و کوچک خوشه‌هاي بزرگتري حاصل مي‌شود.

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

a. خوشه‌ها مي‌توانند داراي اشکال دلخواه باشند.

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

c. در تشخيص نويزها بسيار کارا هستند.

۱۲-۴-۱۳۸۸, ۱۱:۴۳ بعد از ظهر	#12 (لینک دائم)
Astaraki Administrator تاريخ عضويت: خرداد ۱۳۸۷ محل سكونت: تهران-کرج! پست ها: 3,465 تشكرها: 754 16,337 تشكر در 3,127 پست My Mood:	خوشه‌بندي بر اساس چگالي اين روشهاي خوشه‌بندي بر اين اصل استوارند که خوشه‌ها‌، ناحيه‌هايي از فضاي داده با چگالي زيادي هستند که توسط نواحي با چگالي کمتر از همديگر جدا شده‌اند. براي پياده‌سازي اين روشهاي خوشه‌بندي لازم است تا ابتدا اصطلاحاتي تعريف شوند: چگالي نقاط محلي در نقطة P (Local Point Density) : اگر P را نقطة هستة يک همسايگي و ε شعاع همسايگي براي نقطة P در نظر گرفته شود آنگاه همسايگي به شعاع ε براي نقطة P به صورت زير تعريف مي‌شود: به تعداد نقاط قرار گرفته شده درون يک همسايگيِ داده شده چگالي نقاط آن همسايگي گفته مي‌شود. شکل 12: يک همسايگي براي P داراي چگالي نقاط 5 در دسترسِ مستقيمِ چگالي (Directly Density-Reachable): دادة p را در دسترسِ مستقيمِ چگاليِ q گويند اگر p درون يک همسايگي به شعاع ε با هستة q باشد. در شکل زير بهتر مي‌توان اين مفهوم را درک کرد. شکل 13: p در دسترسِ مستقيمِ چگاليِ q قرار دارد. در دسترسِ چگالي (Density-Reachable): دادة p را در دسترسِ چگاليِ q گويند اگر داده‌اي وجود داشته باشد که هم درون يک همسايگي به شعاع ε با هستة p و هم درون يک همسايگي به شعاع ε با هستة q باشد. در شکل زير بهتر مي‌توان اين مفهوم را درک کرد شکل 14: p در دسترسِ چگاليِ q قرار دارد. متصلِ چگالي (Density-Connected): دادة p را متصلِ چگاليِ q گويند اگر داده‌اي مانند o وجود داشته باشد که هم در دسترسِ چگاليِ p و هم در دسترسِ چگاليِ q باشد. در شکل زير بهتر مي‌توان اين مفهوم را درک کرد. شکل 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 } مجموعة نويز خوانده مي‌شود. شکل 16: خوشه‌بندي بر اساس چگالي الگوريتم خوشه‌بندي براساس چگالي DBSCAN: در اين روش خوشه‌بندي هر دادة متعلق به خوشة C در دسترس چگالي ساير داده‌هاي متعلق به آن خوشه‌ است و در دسترس چگالي هيچ دادة ديگري قرار ندارد. شبه کد اين الگوريتم را زير مشاهده مي‌کنيد. 1-1-1- مثالي از الگوريتم خوشه‌بندي براساس چگالي DBSCAN: در شکل زير سعي شده است تا نحوة اعمال الگوريتم خوشه‌بندي DBSCAN را بر روي يک مجموعه داده نشان داده شود. همان‌گونه که مشاهده مي‌شود، اين الگوريتم نوانسته ‌است به خوبي داده‌ها را خوشه‌بندي کند. a b c: d: f : شکل 17: مثالي از روش خوشه‌بندي DBSCAN الگوريتم سلسله مراتبي خوشه‌بندي براساس چگالي OPTICS: در اين روش سعي مي‌شود تا با تکنيکي سلسله مراتبي خوشه‌هاي بزرگتري را از ترکيب خوشه‌اي داراي چگالي زياد ولي کوچک‌تر محاسبه کرد. در شکل زير با يک بار اعمال الگوريتم خوشه‌بندي DBSCAN خوشه‌هاي C1 و C2 حاصل گشته‌اند که در مرحلة ديگري با هم ترکيب شده و خوشة بزرگتر C را ساخته‌اند. در اين روش با افزايش تعداد تکرار مقدار پارامتر ε افزايش مي‌يابد. شکل 18: در روش سلسله مراتبي خوشه‌بندي براساس چگالي OPTICS از ترکيب خوشه‌هاي با چگالي زياد و کوچک خوشه‌هاي بزرگتري حاصل مي‌شود. مزاياي خوشه‌بندي بر اساس چگالي a. خوشه‌ها مي‌توانند داراي اشکال دلخواه باشند. b. تعداد خوشه‌ها به صورت اتوماتيک همزمان با عمل خوشه‌بندي تعيين مي‌شود. c. در تشخيص نويزها بسيار کارا هستند. __________________ تعرفه ارزان تبلیغات در اولین و بزرگترین سایت هوش مصنوعی ایران ! با بیش از صد و چهل هزار کاربر!