اغلب الگوريتمهاي خوشه‌بندي سلسله مراتبي را به نحوي مي‌توان گسترش يافتة الگوريتم خوشه‌بندي Single-Link در نظر گرفت. تفاوت روشهاي مختلف در نحوة محاسبة ماتريس تشابه يا عدم تشابه (Dissimilaritye) آنها است. فرمولي بازگشتي به نام فرمول Lance-Williams تعريف شده است که عدم‌تشابه بين خوشة k و خوشة حاصل از پيوند خوشه‌هاي i و j را بيان مي‌کند:[7]

که پارامترهاي ai، b و c بيان کنندة نوع روش خوشه‌بندي هستند.
1-8-3 روش مبتنی بر چگالی
بسیاری از روش های افرازبندی اشیاء را بر اساس فاصله آنها نسبت به یکدیگر خوشه­بندی می­ کنند. این روشها تنها خوشه­های کروی شکل را پیدا می­ کنند. و در برابر خوشه­های با شکل­های دلخواه به مشکل بر می­خورند. در مقابل برخی روش های دیگر خوشه­بندی بر پایه چگالی توسعه یافته­اند. ایده عمومی این روشها رشد دادن خوشه ­ها بر پایه چگالی در همسایه هاست. به این معنی که برای هر نقطه داده در یک خوشه معلوم همسایگی با شعاع معلوم باید شامل حداقل تعداد مینیمم نقاط باشد. این روشها برای صاف کردن نویزها و کشف خوشه­های با اشکال دلخواه بکار می­روند. روش های مبتنی بر چگالی که می توانند خوشه­هایی نامتقارن را نیز تشکیل دهند، داده­هایی را که در فضا متراکم­تر هستند شناسایی کرده و آنها با داده ­های متراکم نزدیک آنها در فضا در یک خوشه قرار می­ دهند. اساس این تراکم را تابعی تشکیل می­دهد که تاثیری برای هر­داده بر فضای اطراف آن نقطه در نظر می­گیرد. حال اگر چند داده مختلف در نزدیکی یکدیگر باشند مجموع این تاثیر­ها بر فضا زیاد خواهد بود . بعنوان مثال فرض کنید که چند لامپ روشن در فضایی قرار داشته باشد. هر لامپ فضای اطراف خود را روشن می­ کند و این تاثیر هر چه از آن فضا دور شویم کمتر می­ شود. حال اگر چند لامپ در کنار هم روشن باشد فضایی روشن و با تراکم بالا از نور بوجود میآید­. در روشی ساده می­توان نقاطی را که در همسایگی آنها یک تعداد حداقلی نقطه دیگر وجود دارد را روشن کرد و نقاط موجود در همسایگی آنها در خوشه­های یکسان قرار دارد و همینطور جلو رفت تا به تعداد خوشه­های مورد نظر دست یافت. [12]
دانلود پایان نامه
خوشه‌بندي بر اساس چگالي بر اين اصل استوارند که خوشه‌ها‌، ناحيه‌هايي از فضاي داده با چگالي زيادي هستند که توسط نواحي با چگالي کمتر از همديگر جدا شده‌اند. براي پياده‌سازي اين روشهاي خوشه‌بندي لازم است تا ابتدا اصطلاحاتي تعريف شوند:[9]

 

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

 

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

 

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

 

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

 

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

 

شکل 1-10 : p در دسترسِ چگاليِ q قرار دارد

 

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

 

شکل 1-11 : p متصلِ چگاليِ q است

 

    • خوشة مبتني بر چگالي (Density-Based Cluster): زير مجموعه‌اي غيرتهي(S) از مجموعة داده‌ها (D) که داراي دو شرط زير باشد:

 

    • حداکثر: اگر p درون S باشد و q در دسترسِ چگاليِ p باشد آنگاه q نيز متعلق به S باشد.

 

    • اتصال: هر دادة درون S متصلِ چگاليِ ساير داده‌هاي درون S باشد.

 

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

 

    • S1, …, Sn تمام خوشه‌هاي مبتني چگاليِ درون D است.

 

    • N=D{ S1, …, Sn } مجموعة نويز خوانده مي‌شود.

 

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

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

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

 

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

 

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

 

  1. در تشخيص نويزها بسيار کارا هستند.
موضوعات: بدون موضوع  لینک ثابت


فرم در حال بارگذاری ...