کافه دانایی

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

ابتدا تمام دادهها به عنوان یک خوشه در نظر گرفته می شوند و سپس طی یک فرآیند تکراری، دادههایی که شباهت کمتری به هم دارند به خوشههای مجزایی شکسته میشوند. این روال تا رسیدن به خوشههایی که دارای یک عضو هستند؛ ادامه پیدا میکند.
2-2-6-2- خوشه بندی سلسله مراتبی متراکم شونده
ابتدا هر داده به عنوان خوشهای مجزا در نظر گرفته می شود و در طی یک فرآیند تکراری در هر مرحله خوشههایی که شباهت بیشتری با هم دارند با یکدیگر ترکیب شده تا در نهایت یک یا تعداد مشخصی خوشه حاصل شود. از انواع الگوریتمهای خوشهبندی سلسله مراتبی متراکم شونده می توان اتصال منفرد، اتصال کامل و اتصال میانگین را نام برد. تفاوت اصلی بین این روشها به نحوهی محاسبهی شباهت بین خوشه ها مربوط می شود.
شکل2 3 محاسبه فاصله در اتصال منفرد، اتصال میانگین و اتصال کامل
• اتصال منفرد
به این روش خوشه‌بندی، تکنیک نزدیکترین همسایه27 نیز گفته می‌شود. این الگوریتم برای دادههائی که خواص مشترکی ندارند28 (پراکندگی خوب، زنجیرهای مانند و یا هم مرکز ) بسیار خوب عمل میکند. این در حالی است که الگوریتم پارتیشنی چون K-means بر روی مجموعه دادههائی که همسانگرد29 هستند، کارا میباشد. در اتصال منفرد، فاصله‌ی بین دو خوشه برابر با کمترین فاصله بین جفت اشیایی است که هر کدام متعلق به یکی از دو خوشه است (شکل 2-3، قسمت الف). به بیان دیگر، ودو خوشه هستند و فاصله‌ی بین دو عضو و است. بهکارگیری الگوریتم اتصال منفرد هنگامی مفید است که خوشه‌ها دارای اشیای نزدیک به هم باشند؛ بهعبارت دیگر، خوشه پیوسته باشد.
• اتصال میانگین
 از آنجا که هر دو روش خوشه‌بندی اتصال منفرد و اتصال کامل به شدت به نویز حساس می‌باشد، این روش که محاسبات بیشتری دارد، پیشنهاد شد. در این الگوریتم، فاصلهی ‌بین دو خوشه به صورت میانگین فاصله ‌بین همهی ‌جفت‌هایـــی است که یکی از آنها در خوشــهی ‌نخست و دیگری در خوشهی ‌دوم باشد (شکل 2-3، قسمت ب). به بیان دیگر:
که و دو خوشه هستند، و تعداد اشیای متعلق به دو خوشه‌ی و هستند و فاصلهی ‌بین دو عضو و است. خوشه‌هایی که اتصال میانگین تولید می‌کند، فشرده‌تر از خوشه‌هایی است که در اتصال منفرد تولید می‌شوند.
• اتصال کامل
به این روش خوشه‌بندی، تکنیک دورترین همسایه30 نیز گفته می‌شود. در این الگوریتم ، فاصلهی‌ بین دو خوشه به صورت بیشینهی فاصله ‌بین همه‌ جفت‌هایی است که یکی از آنها در خوشـهی ‌نخـست و دیگری در خوشهی‌ دوم باشد (شکل 2-3، قسمت ج).
به بیان دیگر:
که ودو خوشه هستند و فاصلهی ‌بین دو عضو و است.
این الگوریتم بیشتر مایل است که کلاسترهائی متراکم تولید کند، در حالی که کلاسترهای خروجی الگوریتم اتصال منفرد پراکنده و کشیده می باشد. نکته دیگر این که، تنها الگوریتم اتصال منفرد است که می تواند کلاسترهای هم مرکز استخراج کند، اما از نقطه نظر عملی، الگوریتمهای اتصال کامل محبوبیت بیشتری دارند .
2-2-7- خوشه‌بندی افرازبندی یا پارتیشنی
آنچه که از یک الگوریتم خوشهبندی پارتیشنی بهدست میآید[22]،[23]، یک پارتیشن واحد از داده به جای یک ساختار کلاستری (چیزی شبیه دندوگرامی که در تکنیکهای سلسله مراتبی حاصل می شد) میباشد. متدهای پارتیشنی از این مزیت برخوردارند که میتوانند با مجموعهی وسیعی از دادهها کار کنند و میدانیم که ساختن یک دندوگرام از نظر محاسباتی مقرون به صرفه نخواهد بود. اما مشکلی که الگوریتمهای پارتیشنی را دنبال میکند، این است که تعداد کلاسترهای خروجی چگونه انتخاب شود. روند تولید کلاسترها در تکنیکهای پارتیشنی بر این اساس است که یک تابع سنجش31 از قبل تعریف شده را بهینه کند. که این تابع ممکن است محلی باشد (بر روی زیرمجموعه ای از نمونه ها تعریف میشود) و یا سراسری (بر روی تمام نمونه ها) [24]. محاسبهی مقدار بهینه واضح است که پر هزینه میباشد. بنابراین، در عمل معمولاً این الگوریتمها را چندین بار با حالات شروع مختلف بر روی نمونهها اجرا میکنند و بهترین ترکیب بهدست آمده برای خروجی کلاسترینگ استفاده میگردد .
معیار خطای مربعی32، یکی از پرکاربردترین و مستقیمترین توابع سنجش در تکنیکهای خوشهبندی افرازبندی میباشد که بر روی خوشـههای متراکـم و ایزولــه بسیار خوب جواب میدهد. خطای مربعی روی یک عملیات خوشهبندی چون از یک مجموعه نمونههایی چون(شاملخوشه) بهصورت زیر تعریف میشود :
(2-4)
در عبارت فوقامین نمونه متعلق بهامین خوشه را با نشان داده است و مقدار عنصر مرکزی33 ازامین خوشه میباشد. الگوریتم k-means، جز این دستهبندی قرار داردکه در ادامه بهتفصیل شرح داده خواهد شد.
2-2-7-1-الگوریتم k-means
  این روش علی‌رغم سادگی به عنوان یک روش پایه برای بسیاری از روش‌های خوشه‌بندی (مانند خوشه‌بندی فازی) محسوب می‌شود[25]،[26]. این روش، روشی انحصاری و مسطح است. برای این الگوریتم شکلهای مختلفی بیان شده است ولی همهی آنها دارای روالی تکراری هستند که برای تعدادی ثابت از خوشه‌ها سعی در تخمین موارد زیر دارند:
•        به دست آوردن نقاطی به عنوان مراکز خوشه‌ها: این نقاط در واقع همان میانگین نقاط متعلق به هر خوشه هستند.
•        نسبت دادن هر نمونه داده به یک خوشه: آن داده باید کمترین فاصله تا مرکز آن خوشه را دارا باشد.
در نوع ساده‌ای از این روش، ابتدا به تعداد خوشه‌‌های مورد نیاز، نقاطی به صورت تصادفی انتخاب می‌شود. سپس داده‌ها با توجه با میزان نزدیکی (شباهت) به یکی از این خوشه‌ها نسبت داده‌ می‌شوند و بدین ترتیب، خوشه‌های جدیدی حاصل می‌شود. با تکرار همین روال می‌توان در هر تکرار با میانگین‌گیری از داده‌ها، مراکز جدیدی برای آنها محاسبه کرد و مجدادأ داده‌ها را به خوشه‌های جدید نسبت داد. این روند تا زمانی ادامه پیدا می‌کند که دیگر تغییری در داده‌ها حاصل نشود. به بیان دقیقتر:
قدم اول: در ابتدا K نقطه به صورت تصادفی به عنوان مراکز خوشه ها انتخاب می شوند. این مراکز بایستی با دقت زیاد انتخاب شوند، زیرا مراکز مختلف، نتایج مختلف را به وجود میآورند. بنابراین، بهترین انتخاب، قرار دادن مراکز در فاصله هر چه بیشتر از یکدیگر می باشد.
قدم دوم: هر نمونه داده به خوشه‌ای که مرکز آن خوشه کمترین فاصله تا آن داده را داراست، نسبت داده‌ می شود.
قدم سوم: پس از تعلق تمام دادهها به یکی از خوشهها، برای هر خوشه یک نقطهی جدید به عنوان مرکز آن تعریف می شود که این نقطه میانگین نقاط متعلق به هر خوشه است. مراحل دو و سه تا زمانی که هیچ تغییری در مراکز خوشه ها ایجاد نشود، تکرار میگردد.
علی‌رغم اینکه خاتمه‌پذیری الگوریتم بالا تضمین شده است ولی جواب نهایی آن واحد نبوده و همواره جوابی بهینه نمی‌باشد. به طور کلی روش ساده بالا دارای مشکلات زیر است:
•  جواب نهایی به انتخاب خوشه‌های اولیه وابستگی دارد.
•  روالی مشخص برای محاسبهی اولیهی مراکز خوشه‌ها وجود ندارد.
• اگر در تکراری از الگوریتم تعداد داده‌های متعلق به خوشه‌ای صفر شد راهی برای تغییر و بهبود ادامهی روش وجود ندارد.
• در این روش فرض شده است که تعداد خوشه‌ها از ابتدا مشخص است اما معمولاً در کاربردهای زیادی تعداد خوشه‌ها مشخص نمی‌باشد.
• علت محبوبیت این الگوریتم در این است که بهسادگی قابل پیادهسازی است. اما مشکل بزرگی که این روش را تهدید میکند این است که احتمال توقف در کمینه محلی وجود دارد.
انواع مختلفی از الگوریتم k-means در تحقیقات متعدد ذکر شده است[27]، [28]. بعضی از آنها تلاش کردهاند که یک تقسیمبندی اولیه خوب، انتخاب کنند تا الگوریتم بتواند به سوی پیدا کردن مقدار کمینه سراسری متمایل شود[29].
 مراحل پیاده سازی الگوریتم k-means به تفصیل عبارت است از:
گام اول:ایجاد مراکز اولیهی خوشهها، با انتخاب تصادفی نقطه از بین کلیه نقاط داده.
گام دوم: محاسبهی ماتریس عضویت با استفاده از رابطهی زیر:
(2-5)
گام سوم: محاسبهی تابع عضویت (عدم تشابه) با استفاده از معادلهی زیر:
(2-6)
توقف تکرار در صورتی که تغییرات آن نسبت به تکرار قبل، کمتر از حد آستانه تعریف شده باشد.
گام چهارم: محاسبهی مراکز جدید خوشهها با استفاده از معادلهی 2- 7.
(2-7)
و سپس بازگشت به گام دوم.
متأسفانه نحوه عملکرد الگوریتم K-means به مقادیر اولیه وابستگی دارد[30]، [31]. لذا تضمینی برای رسیدن به جواب مورد انتظار وجود نخواهد داشت. در جدول2-3مزایا و معایب این روش لیست شده است.
جدول 2-1 مزایا و معایب الگوریتم k-means.
مزایایالگوریتمk-means
معایب الگوریتم k-means
سرعت بالای محاسبات
عدم توانایی مقایسه کیفی خوشههای تولید شده
تراکم خوشههای تولیدی
ثابت بودن تعداد خوشهها
همگرا به کمینه های محلی
حساس به نویز
وابستگی به مقادیر اولیه
الزام کروی بودن خوشهها
عدم دستیابی به بهینه سراسری
2-2-8- خوشهبندی همپوشانی
مسائل خوشهبندی از یک دیدگاه میتواند به دو گروه تقسیم شود: خوشه بندی سخت (خوشه بندی پیچیده) و خوشه بندی فازی (خوشه بندی  نرم یا همپوشی ). در خوشهبندی سخت یک داده به یک و فقط یک خوشه تعلق میگیرد. درحالیکه در خوشه بندی فازی یک نقطه داده ممکن است به دو خوشه یا بیشتر تعلق داشته باشد. الگوریتم Fuzzy c-means نمونه ای از الگوریتم همپوشی است که در ادامه بیان می شود.
2-2-8-1- خوشهبندی فازی
در خوشهبندی کلاسـیک هر نمونه ورودی متعلق به یـک و فقط یک خوشه میباشد و نمیتواند عضو دو خوشه و یا بیشتر باشد. بهعبارت دیگر، خوشهها همپوشانی ندارند[32]،[33]،[34]. حال حالتی را در نظر بگیرید که میزان تشابه یک نمونه با دو خوشه و یا بیشتر یکسان باشد. در چنین حالتی، در خوشهبندی کلاسیک بهدلیل آنکه هر نمونه باید به یک و فقط یک خوشه متعلق باشد، باید تصمیمگیری شود که این نمونه متعلق به کدام خوشه است. تفاوت اصلی خوشهبندی کلاسیک و خوشهبندی فازی در همین جا است که در خوشه بندی فازی یک نمونه می تواند متعلق به بیش از یک خوشه باشد. برای روشن شدن مطلب شکل زیر را در نظر بگیرید:
اگر نمونههای ورودی مطابق شکل فوق باشند مشخص است که می توان دادهها را به دو خوشه تقسیم کرد. اما مشکلی که پیش میآید این است که دادهی مشخص شده در وسط میتواند عضو هر دو خوشه باشد. بنابراین، باید تصمیم گرفت که دادهی مورد نظر متعلق به کدام خوشه است؛ خوشهی سمت راست یا خوشهی سمت چپ. اما اگر از خوشه بندی فازی استفاده کنیم، دادهی مورد نظر با تعلق 0.5 عضو خوشهی سمت راست و با تعلق مشابه عضو خوشهی سمت چپ است. تفاوت دیگر در این است که مثلاً نمونه های ورودی در سمت راست شکل می توانند با یک درجه تعلق خیلی کم عضو خوشهی سمت چپ نیز باشند که همین موضوع برای نمونه های سمت چپ نیز صادق است.
زمانی که در سال 1965 پروفسور لطفی‌زاده، استاد ایرانی‌الاصل دانشگاه برکلی، اولین مقاله خود را در زمینهی فازی تحت عنوان مجموعه‌های فازی منتشر کرد، هیچ کس باور نداشت که این جرقه‌ای خواهد بود که دنیای ریاضیات را به طور کلی تغییر دهد.
یکی از مهمترین و پرکاربردترین الگوریتمهای خوشهبندی فازی، الگوریتم c میانگین میباشد[35]. در این الگوریتم نمونهها به c خوشه تقسیم میشوند به گونهای که تعداد c از قبل مشخص شده باشد. در نسخه فازی این الگوریتم نیز تعداد خوشهها (c) از قبل مشخص شده است. در الگوریتم خوشه بندی c میانگین فازی تابع هدف بصورت زیر می باشد:
(2-8)
در فرمول فوق m یک عدد حقیقی بزرگتر از 1 است