شکل ۲-۷. الگوریتم خوشه‌بندی سلسله مراتبی تراکمی پیوندی کامل
شکل ۲-۸. دندوگرام پیوندی کامل برای ماتریس
پایان نامه - مقاله - پروژه
۲-۲-۱-۱-۴. الگوریتم پیوندی میانگین
الگوریتم پیوندی منفرد اجازه می‌دهد تا خوشه‌ها به صورت دراز و نازک رشد کنند. این در شرایطی است که الگوریتم پیوندی کامل خوشه‌های فشرده‌تری تولید می‌کند. هر دو الگوریتم مستعد خطا با داده‌های خارج از محدوده[۴۶] هستند. الگوریتم خوشه‌بندی پیوندی میانگین، یک تعادلی بین مقادیر حدی الگوریتم‌های پیوندی منفرد و کامل است. الگوریتم پیوندی میانگین همچنین، روش جفت-گروه بدون وزن با بهره گرفتن از میانگین حسابی[۴۷] نامیده می‌شود. این الگوریتم، یکی از پرکاربردترین الگوریتم‌های خوشه‌بندی سلسله مراتبی می‌باشد [۲۶]. اگر  یک خوشه با تعداد  تا عضو، و  یک خوشه دیگر با تعداد  تا عضو باشند، در روش پیوندی میانگین، فاصله آن‌ها برابر خواهد بود با:
(۲-۴)
که  نشان‌دهنده فاصله(عدم شباهت) بین نقاط a و  در ماتریس مجاورت است.
۲-۲-۱-۱-۵. الگوریتم پیوندی بخشی
روش پیوندی بخشی که از مربع مجموع خطا‌های (SSE) خوشه‌های یک افراز برای ارزیابی استفاده می‌کند، یکی دیگر از روش‌های سلسله مراتبی می‌باشد [۶۰]. اگر  یک خوشه با تعداد  تا عضو، و  یک خوشه دیگر با تعداد  تا عضو باشند و نماد  به معنای فاصله اقلیدسی و  و  مراکز خوشه‌های  و  باشد آنگاه در روش پیوندی بخشی، فاصله آن‌ها برابر خواهد بود با:
(۲-۵)
۲-۲-۱-۲. الگوریتم‌های افرازبندی
یک خاصیت مهم روش‌های خوشه‌بندی سلسله مراتبی، قابلیت نمایش دندوگرام است که تحلیل‌گر را قادر می‌سازد تا ببیند که چگونه اشیاء در سطوح متوالی مجاورت، در خوشه‌ها به هم پیوند می‌خورند یا تفکیک می‌شوند. همان طور که اشاره شد، هدف الگوریتم‌های افرازبندی، تقسیم داده‌ها در خوشه‌ها، به گونه‌ای است که داده‌های درون یک خوشه بیش‌ترین شباهت را به همدیگر داشته باشند؛ و درعین‌حال، بیش‌ترین فاصله و اختلاف را با داده‌های خوشه‌های دیگر داشته باشند. آن‌ها یک افراز منفرد از داده را تولید می‌کنند و سعی می‌کنند تا گروه‌های طبیعی حاضر در داده را کشف کنند. هر دو رویکرد خوشه‌بندی، دامنه‌های مناسب کاربرد خودشان را دارند. معمولاً روش‌های خوشه‌بندی سلسله مراتبی، نیاز به ماتریس مجاورت بین اشیاء دارند؛ درحالی‌که روش‌های افرازبندی، به داده‌ها در قالب ماتریس الگو نیاز دارند. نمایش رسمی مسئله خوشه‌بندی افرازبندی می‌تواند به صورت زیر باشد:
تعیین یک افراز از الگوها در  گروه، یا خوشه، با داشتن  الگو در یک فضای d-بعدی؛ به طوری که الگوها در یک خوشه بیش‌ترین شباهت را به هم داشته و با الگوهای خوشه‌های دیگر بیش‌ترین، تفاوت را داشته باشند. تعداد خوشه‌ها،  ، ممکن است که از قبل مشخص‌شده نباشد، اما در بسیاری از الگوریتم‌های خوشه‌بندی افرازبندی، تعداد خوشه‌ها باید از قبل معلوم باشند. در ادامه برخی از معروف‌ترین و پرکاربردترین الگوریتم‌های افرازبندی مورد بررسی قرار خواهند گرفت.
۲-۲-۱-۲-۱. الگوریتم K-means
در الگوریتم  مراکز خوشه‌ها بلافاصله بعد از اینکه یک نمونه به یک خوشه می‌پیوندد محاسبه می‌شوند. به طور معمول بیشتر روش‌های خوشه‌بندی ترکیبی از الگوریتم  جهت خوشه‌بندی اولیه خود استفاده می‌کنند [۳۷, ۴۷, ۵۷]. اما مطالعات اخیر نشان داده‌اند که با توجه به رفتار هر مجموعه داده، گاهی اوقات یک روش خوشه‌بندی خاص پیدا می‌شود که دقت بهتری از  برای بعضی از مجموعه داده‌ها می‌دهد [۱, ۵۴]. اما الگوریتم  به دلیل سادگی و توانایی مناسب در خوشه‌بندی همواره به عنوان انتخاب اول مطالعات خوشه‌بندی ترکیبی مورد مطالعه قرار گرفته است. در شکل ۲-۱۰ شبه کد الگوریتم  را مشاهده می‌کنید:

 

۱. Place K points into the space represented by the objects that are being clustered.
These points represent initial group centroids.
۲. Assign each object to the group that has the closest centroid.
۳. When all objects have been assigned, recalculate the positions of the K centroids.
۴. Repeat Steps 2 and 3 until the centroids no longer move. This produces a separation
of the objects into groups from which the metric to be minimized can be calculated

شکل ۲-۹. الگوریتم خوشه‌بندی افرازبندی
مقادیر مراکز اولیه‌ی‌ متفاوت برای الگوریتم  می‌تواند منجر به خوشه‌بندی‌های مختلفی شود. به خاطر اینکه این الگوریتم مبتنی بر مربع خطا است، می‌تواند به کمینه محلی همگرا شود، مخصوصاً برای خوشه‌هایی که به طور خیلی خوبی از هم تفکیک نمی‌شوند، این امر صادق است. نشان داده شده است که هیچ تضمینی برای همگرایی یک الگوریتم تکراری به یک بهینه سراسری نیست [۳۳]. به طور خلاصه می‌توان ویژگی‌های الگوریتم  را به صورت زیر برشمرد:
۱- بر اساس فاصله اقلیدسی تمامی ویژگی‌ها می‌باشد.
۲- منجر به تولید خوشه‌هایی به صورت دایره، کره و یا ابر کره می‌شود.
۳- نسبت به روش‌های دیگر خوشه‌بندی، ساده و سریع است.
۴- همگرایی آن به یک بهینه محلی اثبات شده است، اما تضمینی برای همگرایی به بهینه سراسری وجود ندارد.
۵- نسبت به مقداردهی اولیه مراکز خوشه‌ها خیلی حساس است.
۲-۲-۱-۲-۲. الگوریتم FCM
الگوریتم FCM[48] اولین بار توسط دون [۱۳] ارائه شد. سپس توسط بزدک [۶۶] بهبود یافت. این متد دیدگاه جدیدی را در خوشه‌بندی بر اساس منطق فازی [۶۲] ارائه می‌دهد. در این دیدگاه جدید، به جای اینکه داده‌ها در یک خوشه عضو باشند، در تمامی خوشه‌ها با یک ضریب عضویت که بین صفر و یک است، عضو هستند و ما در این نوع خوشه‌بندی، دنبال این ضرایب هستیم. در روش‌های معمول در جایی که ما  داده داشته باشیم، جواب نهایی ماتریس  خواهد بود که هر خانه شامل برچسب خوشه‌ی داده‌ی نظیر آن می‌باشد. ولی در این روش در صورت داشتن  خوشه، جواب نهایی یک ماتریس  خواهد بود که در آن هر ردیف شامل ضرایب عضویت داده‌ی نظیر به آن خوشه است. بدیهی است که جمع افقی هر ردیف (ضرایب عضویت یک داده خاص) برابر با یک خواهد بود. یک روش معمول جهت رسیدن به جواب‌هایی غیر فازی بر اساس نتایج نهایی الگوریتم فازی، برچسب‌زنی داده بر اساس آن ضریبی که مقدار حداکثر را در این داده دارد، می‌باشد. رابطه ۲-۶ معادله پایه در روش فازی است: [۶۶]
(۲-۶) ,
در رابطه ۲-۶ متغیرm یک عدد حقیقی بزرگ‌تر از یک و  درجه عضویت داده  در خوشه j-ام می‌باشد، که خود  ، i-امین داده d-بُعدی از داده‌ی مورد مطالعه می‌باشد و  مرکز d-بعدی خوشه j-ام‌ است و  هر روش معمول جهت اندازه‌گیری شباهت میان داده  و مرکز خوشه  می‌باشد. در روش خوشه‌بندی فازی مراکز خوشه (  ) و درجه عضویت (  ) با تکرار مکرر به ترتیب بر اساس رابطه‌های ۲-۷ و ۲-۸ به‌روزرسانی می‌شوند، تا زمانی که شرط توقف درست در آید. در این شرط مقدار  یک مقدار توافقی بسیار کوچک‌تر از یک می‌باشد که مطابق با نوع داده و دقت خوشه‌بندی قابل جایگذاری خواهد بود. بدیهی است که هر چقدر این مقدار به سمت صفر میل کند درجه عضویت دقیق‌تر و مقدار زمان اجرا بیشتر خواهد بود [۶۶].
(۲-۷)
(۲-۸)
مراحل اجرای الگوریتم  در شبه کد شکل ۲-۱۱ شرح داده شده است:

۱.Initialize  matrix,
۲.At k-step: calculate the centers vectors  with

۳.Update  ,
موضوعات: بدون موضوع  لینک ثابت


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