• اتصال میانگین

از آن­جا که هر دو روش خوشه‌بندی اتصال منفرد و اتصال کامل به شدت به نویز حساس می‌باشد، این روش که محاسبات بیشتری دارد، پیشنهاد شد. در این الگوریتم، فاصله­ی ‌بین دو خوشه به صورت میانگین فاصله ‌بین همه ‌جفت‌هایـــی است که یکی از آن­ها در خوشــه­ی ‌نخست و دیگری در خوشه­ی ‌دوم باشد (شکل ۲-۳، قسمت ب). به بیان دیگر:

که و دو خوشه هستند، و تعداد اشیای متعلق به دو خوشه‌­ی و هستند و فاصله­ی ‌بین دو عضو و است. خوشه‌هایی که اتصال میانگین تولید می‌کند، فشرده‌تر از خوشه‌هایی است که در اتصال منفرد تولید می‌شوند.

• اتصال کامل

به این روش خوشه‌بندی، تکنیک دورترین همسایه^[۳۰] نیز گفته می‌شود. در این الگوریتم ، فاصله­ی‌ بین دو خوشه به صورت بیشینه­ی فاصله ‌بین همه‌ جفت‌هایی است که یکی از آن­ها در خوشـه­ی ‌نخـست و دیگری در خوشه­ی‌ دوم باشد (شکل ۲-۳، قسمت ج).
به بیان دیگر:

که و دو خوشه هستند و فاصله­ی ‌بین دو عضو و است.
این الگوریتم بیشتر مایل است که کلاسترهائی متراکم تولید کند، در حالی که کلاسترهای خروجی الگوریتم اتصال منفرد پراکنده و کشیده می باشد. نکته دیگر این که، تنها الگوریتم اتصال منفرد است که می تواند کلاسترهای هم مرکز استخراج کند، اما از نقطه نظر عملی، الگوریتم­های اتصال کامل محبوبیت بیشتری دارند .
۲-۲-۷- خوشه‌بندی افرازبندی یا پارتیشنی
آن­چه که از یک الگوریتم خوشه­بندی پارتیشنی به­دست می ­آید[۲۲]،[۲۳]، یک پارتیشن واحد از داده به ­جای یک ساختار کلاستری (چیزی شبیه دندوگرامی که در تکنیک­های سلسله مراتبی حاصل می شد) می­باشد. متدهای پارتیشنی از این مزیت برخوردارند که می­توانند با مجموعه­ وسیعی از داده ­ها کار کنند و می­دانیم که ساختن یک دندوگرام از نظر محاسباتی مقرون به صرفه نخواهد بود. اما مشکلی که الگوریتم­های پارتیشنی را دنبال می­ کند، این است که تعداد کلاسترهای خروجی چگونه انتخاب شود. روند تولید کلاسترها در تکنیک­های پارتیشنی بر این اساس است که یک تابع سنجش^[۳۱] از قبل تعریف شده را بهینه کند. که این تابع ممکن است محلی باشد (بر روی زیرمجموعه ای از نمونه ها تعریف می­ شود) و یا سراسری (بر روی تمام نمونه ها) [۲۴]. محاسبه­ی مقدار بهینه واضح است که پر هزینه می­باشد. بنابراین، در عمل معمولاً این الگوریتم­ها را چندین بار با حالات شروع مختلف بر روی نمونه­ها اجرا می­ کنند و بهترین ترکیب به­دست آمده برای خروجی کلاسترینگ استفاده می­گردد .

( اینجا فقط تکه ای از متن فایل پایان نامه درج شده است. برای خرید متن کامل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. )

معیار خطای مربعی^[۳۲]، یکی از پرکاربردترین و مستقیم­ترین توابع سنجش در تکنیک­های خوشه­بندی افرازبندی می­باشد که بر روی خوشـه­های متراکـم و ایزولــه بسیار خوب جواب می­دهد. خطای مربعی روی یک عملیات خوشه­بندی چون از یک مجموعه نمونه­هایی چون (شامل خوشه) به­ صورت زیر تعریف می­ شود :
(۲-۴)
در عبارت فوق امین نمونه متعلق به امین خوشه را با نشان داده است و مقدار عنصر مرکزی^[۳۳] از امین خوشه می­باشد. الگوریتم k-means، جز این دسته­بندی قرار داردکه در ادامه به­تفصیل شرح داده خواهد شد.
۲-۲-۷-۱-الگوریتم k-means
این روش علی‌رغم سادگی به عنوان یک روش پایه برای بسیاری از روش‌های خوشه‌بندی (مانند خوشه‌بندی فازی) محسوب می‌شود[۲۵]،[۲۶]. این روش، روشی انحصاری و مسطح است. برای این الگوریتم شکل­های مختلفی بیان شده است ولی همه آنها دارای روالی تکراری هستند که برای تعدادی ثابت از خوشه‌ها سعی در تخمین موارد زیر دارند:

• به دست آوردن نقاطی به عنوان مراکز خوشه‌ها: این نقاط در واقع همان میانگین نقاط متعلق به هر خوشه هستند.

• نسبت دادن هر نمونه داده به یک خوشه: آن داده باید کمترین فاصله تا مرکز آن خوشه را دارا باشد.

در نوع ساده‌ای از این روش، ابتدا به تعداد خوشه‌‌های مورد نیاز، نقاطی به صورت تصادفی انتخاب می‌شود. سپس داده‌ها با توجه با میزان نزدیکی (شباهت) به یکی از این خوشه‌ها نسبت داده‌ می‌شوند و بدین ترتیب، خوشه‌های جدیدی حاصل می‌شود. با تکرار همین روال می‌توان در هر تکرار با میانگین‌گیری از داده‌ها، مراکز جدیدی برای آن­ها محاسبه کرد و مجدادأ داده‌ها را به خوشه‌های جدید نسبت داد. این روند تا زمانی ادامه پیدا می‌کند که دیگر تغییری در داده‌ها حاصل نشود. به بیان دقیق­تر:
قدم اول: در ابتدا K نقطه­ به صورت تصادفی به عنوان مراکز خوشه ها انتخاب می شوند. این مراکز بایستی با دقت زیاد انتخاب شوند، زیرا مراکز مختلف، نتایج مختلف را به وجود می­آورند. بنابراین، بهترین انتخاب، قرار دادن مراکز در فاصله هر چه بیشتر از یکدیگر می باشد.
قدم دوم: هر نمونه داده به خوشه‌ای که مرکز آن خوشه کمترین فاصله تا آن داده را داراست، نسبت داده‌ می شود.
قدم سوم: پس از تعلق تمام داده ­ها به یکی از خوشه ­ها، برای هر خوشه یک نقطه­ی جدید به عنوان مرکز آن تعریف می شود که این نقطه میانگین نقاط متعلق به هر خوشه است. مراحل دو و سه تا زمانی که هیچ تغییری در مراکز خوشه ها ایجاد نشود، تکرار می­گردد.
علی‌رغم این­که خاتمه‌پذیری الگوریتم بالا تضمین شده است ولی جواب نهایی آن واحد نبوده و همواره جوابی بهینه نمی‌باشد. به طور کلی روش ساده بالا دارای مشکلات زیر است:

• جواب نهایی به انتخاب خوشه‌های اولیه وابستگی دارد.

• روالی مشخص برای محاسبه­ی اولیه­ مراکز خوشه‌ها وجود ندارد.

• اگر در تکراری از الگوریتم تعداد داده‌های متعلق به خوشه‌ای صفر شد راهی برای تغییر و بهبود ادامه­ روش وجود ندارد.

• در این روش فرض شده است که تعداد خوشه‌ها از ابتدا مشخص است اما معمولاً در کاربردهای زیادی تعداد خوشه‌ها مشخص نمی‌باشد.

• علت محبوبیت این الگوریتم در این است که به­سادگی قابل پیاده­سازی است. اما مشکل بزرگی که این روش را تهدید می­ کند این است که احتمال توقف در کمینه محلی وجود دارد.

انواع مختلفی از الگوریتم k-means در تحقیقات متعدد ذکر شده است[۲۷]، [۲۸]. بعضی از آنها تلاش کرده ­اند که یک تقسیم ­بندی اولیه خوب، انتخاب کنند تا الگوریتم بتواند به سوی پیدا کردن مقدار کمینه سراسری متمایل شود[۲۹].
مراحل پیاده سازی الگوریتم k-means به تفصیل عبارت است از:
گام اول:ایجاد مراکز اولیه­ خوشه ­ها ، با انتخاب تصادفی نقطه از بین کلیه نقاط داده.
گام دوم: محاسبه­ی ماتریس عضویت با بهره گرفتن از رابطه­ زیر:
(۲-۵)
گام سوم: محاسبه­ی تابع عضویت (عدم تشابه) با بهره گرفتن از معادله­ زیر:
(۲-۶)
توقف تکرار در صورتی که تغییرات آن نسبت به تکرار قبل، کمتر از حد آستانه تعریف شده باشد.
گام چهارم: محاسبه­ی مراکز جدید خوشه ­ها با بهره گرفتن از معادله­ ۲- ۷٫