منبع پایان نامه ارشد با موضوع سلسله مراتبی و سلسله مراتب

اتصال کامل
Widget not in any sidebars

به این روش خوشه‌بندی، تکنیک دورترین همسایه نیز گفته می‌شود. در این الگوریتم ، فاصلهی‌ بین دو خوشه به صورت بیشینهی فاصله ‌بین همه‌ جفت‌هایی است که یکی از آنها در خوشـهی ‌نخـست و دیگری در خوشهی‌ دوم باشد (شکل 2-3، قسمت ج).
به بیان دیگر:
که ودو خوشه هستند و فاصلهی ‌بین دو عضو و است.
این الگوریتم بیشتر مایل است که کلاسترهائی متراکم تولید کند، در حالی که کلاسترهای خروجی الگوریتم اتصال منفرد پراکنده و کشیده می باشد. نکته دیگر این که، تنها الگوریتم اتصال منفرد است که می تواند کلاسترهای هم مرکز استخراج کند، اما از نقطه نظر عملی، الگوریتمهای اتصال کامل محبوبیت بیشتری دارند .
2-2-7- خوشه‌بندی افرازبندی یا پارتیشنی
آنچه که از یک الگوریتم خوشهبندی پارتیشنی بهدست میآید[22]،[23]، یک پارتیشن واحد از داده به جای یک ساختار کلاستری (چیزی شبیه دندوگرامی که در تکنیکهای سلسله مراتبی حاصل می شد) میباشد. متدهای پارتیشنی از این مزیت برخوردارند که میتوانند با مجموعهی وسیعی از دادهها کار کنند و میدانیم که ساختن یک دندوگرام از نظر محاسباتی مقرون به صرفه نخواهد بود. اما مشکلی که الگوریتمهای پارتیشنی را دنبال میکند، این است که تعداد کلاسترهای خروجی چگونه انتخاب شود. روند تولید کلاسترها در تکنیکهای پارتیشنی بر این اساس است که یک تابع سنجش از قبل تعریف شده را بهینه کند. که این تابع ممکن است محلی باشد (بر روی زیرمجموعه ای از نمونه ها تعریف میشود) و یا سراسری (بر روی تمام نمونه ها) [24]. محاسبهی مقدار بهینه واضح است که پر هزینه میباشد. بنابراین، در عمل معمولاً این الگوریتمها را چندین بار با حالات شروع مختلف بر روی نمونهها اجرا میکنند و بهترین ترکیب بهدست آمده برای خروجی کلاسترینگ استفاده میگردد .
معیار خطای مربعی، یکی از پرکاربردترین و مستقیمترین توابع سنجش در تکنیکهای خوشهبندی افرازبندی میباشد که بر روی خوشـههای متراکـم و ایزولــه بسیار خوب جواب میدهد. خطای مربعی روی یک عملیات خوشهبندی چون از یک مجموعه نمونههایی چون(شاملخوشه) بهصورت زیر تعریف میشود :
(2-4)
در عبارت فوقامین نمونه متعلق بهامین خوشه را با نشان داده است و مقدار عنصر مرکزی ازامین خوشه میباشد. الگوریتم k-means، جز این دستهبندی قرار داردکه در ادامه بهتفصیل شرح داده خواهد شد.
2-2-7-1-الگوریتم k-means
  این روش علی‌رغم سادگی به عنوان یک روش پایه برای بسیاری از روش‌های خوشه‌بندی (مانند خوشه‌بندی فازی) محسوب می‌شود[25]،[26]. این روش، روشی انحصاری و مسطح است. برای این الگوریتم شکلهای مختلفی بیان شده است ولی همهی آنها دارای روالی تکراری هستند که برای تعدادی ثابت از خوشه‌ها سعی در تخمین موارد زیر دارند:
        به دست آوردن نقاطی به عنوان مراکز خوشه‌ها: این نقاط در واقع همان میانگین نقاط متعلق به هر خوشه هستند.
        نسبت دادن هر نمونه داده به یک خوشه: آن داده باید کمترین فاصله تا مرکز آن خوشه را دارا باشد.
در نوع ساده‌ای از این روش، ابتدا به تعداد خوشه‌‌های مورد نیاز، نقاطی به صورت تصادفی انتخاب می‌شود. سپس داده‌ها با توجه با میزان نزدیکی (شباهت) به یکی از این خوشه‌ها نسبت داده‌ می‌شوند و بدین ترتیب، خوشه‌های جدیدی حاصل می‌شود. با تکرار همین روال می‌توان در هر تکرار با میانگین‌گیری از داده‌ها، مراکز جدیدی برای آنها محاسبه کرد و مجدادأ داده‌ها را به خوشه‌های جدید نسبت داد. این روند تا زمانی ادامه پیدا می‌کند که دیگر تغییری در داده‌ها حاصل نشود. به بیان دقیقتر:
قدم اول: در ابتدا K نقطه به صورت تصادفی به عنوان مراکز خوشه ها انتخاب می شوند. این مراکز بایستی با دقت زیاد انتخاب شوند، زیرا مراکز مختلف، نتایج مختلف را به وجود میآورند. بنابراین، بهترین انتخاب، قرار دادن مراکز در فاصله هر چه بیشتر از یکدیگر می باشد.
قدم دوم: هر نمونه داده به خوشه‌ای که مرکز آن خوشه کمترین فاصله تا آن داده را داراست، نسبت داده‌ می شود.
قدم سوم: پس از تعلق تمام دادهها به یکی از خوشهها، برای هر خوشه یک نقطهی جدید به عنوان مرکز آن تعریف می شود که این نقطه میانگین نقاط متعلق به هر خوشه است. مراحل دو و سه تا زمانی که هیچ تغییری در مراکز خوشه ها ایجاد نشود، تکرار میگردد.
علی‌رغم اینکه خاتمه‌پذیری الگوریتم بالا تضمین شده است ولی جواب نهایی آن واحد نبوده و همواره جوابی بهینه نمی‌باشد. به طور کلی روش ساده بالا دارای مشکلات زیر است:
 جواب نهایی به انتخاب خوشه‌های اولیه وابستگی دارد.
 روالی مشخص برای محاسبهی اولیهی مراکز خوشه‌ها وجود ندارد.
اگر در تکراری از الگوریتم تعداد داده‌های متعلق به خوشه‌ای صفر شد راهی برای تغییر و بهبود ادامهی روش وجود ندارد.
در این روش فرض شده است که تعداد خوشه‌ها از ابتدا مشخص است اما معمولاً در کاربردهای زیادی تعداد خوشه‌ها مشخص نمی‌باشد.
علت محبوبیت این الگوریتم در این است که بهسادگی قابل پیادهسازی است. اما مشکل بزرگی که این روش را تهدید میکند این است که احتمال توقف در کمینه محلی وجود دارد.