شکل۴-۲۸. رابطه میان آستانه پراکندگی و دقت نتیجه نهایی در روش پیشنهادی اول …………………………………….. ۱۳۴
شکل۴-۲۹. رابطه میان آستانه عدم تمرکز و دقت نتیجه نهایی در روش پیشنهادی اول ………………………………….. ۱۳۵
شکل۴-۳۰. رابطه میان آستانه پراکندگی و زمان اجرای الگوریتم در روش پیشنهادی دوم ………………………………. ۱۳۵
شکل۴-۳۱. رابطه میان آستانه پراکندگی و دقت نتایج نهایی در روش پیشنهادی دوم …………………………………….. ۱۳۶
شکل۴-۳۲. رابطه میان آستانه عدم تمرکز و دقت نتایج نهایی در روش پیشنهادی دوم ………………………………….. ۱۳۷
شکل۴-۳۳. مقایسه زمان اجرای الگوریتم ………………………………………………………………………………………………… ۱۳۸
فصل اول
مقدمه
-
- مقدمه
۱-۱. خوشه‌بندی
به عنوان یکی از شاخه‌های وسیع و پرکاربرد هوش مصنوعی[۱]، یادگیری ماشین[۲] به تنظیم و اکتشاف شیوه‌ها و الگوریتم‌هایی می‌پردازد که بر اساس آن‌ها رایانه‌ها و سامانه‌های اطلاعاتی توانایی تعلم و یادگیری پیدا می‌کنند. طیف پژوهش‌هایی که در مورد یادگیری ماشینی صورت می‌گیرد گسترده است. در سوی نظر‌ی آن پژوهش‌گران بر آن‌اند که روش‌های یادگیری تازه‌ای به وجود بیاورند و امکان‌پذیری و کیفیت یادگیری را برای روش‌هایشان مطالعه کنند و در سوی دیگر عده‌ای از پژوهش‌گران سعی می‌کنند روش‌های یادگیری ماشینی را بر مسائل تازه‌ای اعمال کنند. البته این طیف گسسته نیست و پژوهش‌های انجام‌شده دارای مؤلفه‌هایی از هر دو رو‌یکرد هستند. امروزه، داده‌کاوی[۳] به عنوان یک ابزار قوی برای تولید اطلاعات و دانش از داده‌های خام، در یادگیری ماشین شناخته‌شده و همچنان با سرعت در حال رشد و تکامل است. به طور کلی می‌توان تکنیک‌های داده‌کاوی را به دو دسته بانظارت[۴] و بدون نظارت[۵] تقسیم کرد [۲۹, ۴۶].
(( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت nefo.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. ))
در روش بانظارت ما ورودی (داده یادگیری[۶]) و خروجی (کلاس[۷] داده) یک مجموعه داده را به الگوریتم هوشمند می‌دهیم تا آن الگوی[۸] بین ورودی و خروجی را تشخیص دهد در این روش خروجی کار ما مدلی[۹] است که می‌تواند برای ورودی‌های جدید خروجی درست را پیش‌بینی[۱۰] کند. روش‌های طبقه‌بندی[۱۱] و قوانین انجمنی[۱۲] از این جمله تکنیک‌ها می‌باشد. روش‌های با نظارت کاربرد فراوانی دارند اما مشکل عمده این روش‌ها این است که همواره باید داده‌ای برای یادگیری وجود داشته باشد که در آن به ازای ورودی مشخص خروجی درست آن مشخص شده باشد. حال آنکه اگر در زمینه‌ای خاص داده‌ای با این فرمت وجود نداشته باشد این روش‌ها قادر به حل این‌گونه مسائل نخواهند بود [۲۹, ۶۸]. در روش بدون نظارت برخلاف یادگیری بانظارت هدف ارتباط ورودی و خروجی نیست، بلکه تنها دسته‌بندی ورودی‌ها است. این نوع یادگیری بسیار مهم است چون خیلی از مسائل (همانند دنیای ربات‌ها) پر از ورودی‌هایی است که هیچ برچسبی[۱۳] (کلاس) به آن‌ها اختصاص داده نشده است اما به وضوح جزئی از یک دسته هستند [۴۶, ۶۸]. خوشه‌بندی[۱۴] شاخص‌ترین روش در داده‌کاوی جهت حل مسائل به صورت بدون ناظر است. ایده اصلی خوشه‌بندی اطلاعات، جدا کردن نمونه‌ها از یکدیگر و قرار دادن آن‌ها در گروه‌های شبیه به هم می‌باشد. به این معنی که نمونه‌های شبیه به هم باید در یک گروه قرار بگیرند و با نمونه‌های گروه‌های دیگر حداکثر متفاوت را دارا باشند [۲۰, ۲۶]. دلایل اصلی برای اهمیت خوشه‌بندی عبارت‌اند از:
اول، جمع آوری و برچسب‌گذاری یک مجموعه بزرگ از الگوهای نمونه می‌تواند بسیار پرکاربرد و باارزش باشد.
دوم، می‌توانیم از روش‌های خوشه‌بندی برای پیدا کردن و استخراج ویژگی‌ها[۱۵] و الگوهای جدید استفاده کنیم. این کار می‌تواند کمک به سزایی در کشف دانش ضمنی[۱۶] داده‌ها انجام دهد.
سوم، با خوشه‌بندی می‌توانیم یک دید و بینشی از طبیعت و ساختار داده به دست آوریم که این می‌تواند برای ما باارزش باشد.
چهارم، خوشه‌بندی می‌تواند منجر به کشف زیر رده‌های[۱۷] مجزا یا شباهت‌های بین الگوها ممکن شود که به طور چشمگیری در روش طراحی طبقه‌بندی قابل استفاده باشد.
۱-۲. خوشه‌بندی ترکیبی
هر یک از الگوریتم‌های خوشه‌بندی، با توجه به اینکه بر روی جنبه‌های متفاوتی از داده‌ها تاکید می‌کند، داده‌ها را به صورت‌های متفاوتی خوشه‌بندی می کند. به همین دلیل، نیازمند روش‌هایی هستیم که بتواند با بهره گرفتن از ترکیب این الگوریتم‌ها و گرفتن نقاط قوت هر یک، نتایج بهینه‌تری را تولید کند. در واقع هدف اصلی خوشه‌بندی ترکیبی[۱۸] جستجوی بهترین خوشه‌ها با بهره گرفتن از ترکیب نتایج الگوریتم‌های دیگر است [۱, ۸, ۹, ۵۴, ۵۶]. به روشی از خوشه‌بندی ترکیبی که زیرمجموعه‌ی منتخب از نتایج اولیه برای ترکیب و ساخت نتایج نهایی استفاده می‌شود خوشه‌بندی ترکیبی مبتنی بر انتخاب[۱۹] زیرمجموعه نتایج اولیه می‌گویند. در این روش‌ها بر اساس معیاری توافقی مجموعه‌ای از مطلوب‌ترین نتایج اولیه را انتخاب کرده و فقط توسط آن‌ها نتیجه نهایی را ایجاد می‌کنیم [۲۱]. معیارهای مختلفی جهت انتخاب مطلوب‌ترین روش پیشنهاد شده است که معیار اطلاعات متقابل نرمال شده[۲۰]، روش ماکزیموم[۲۱] و [۲۲]APMM برخی از آن‌ها می‌باشند [۸, ۹, ۲۱, ۶۷]. دو مرحله مهم در خوشه‌بندی ترکیبی عبارت‌اند از:
اول، الگوریتم‌های ابتدایی خوشه‌بندی که خوشه‌بندی اولیه را انجام می‌دهد.
دوم، جمع‌بندی نتایج این الگوریتم‌های اولیه (پایه) برای به دست آوردن نتیجه نهایی.
۱-۳. خرد جمعی
نظریه خرد جمعی[۲۳] که اولین بار توسط سورویکی[۲۴] در سال ۲۰۰۴ در کتابی با همان عنوان منتشر شد، استنباطی از مسائل مطرح‌شده توسط گالتون[۲۵] و کندورست[۲۶] می‌باشد، و نشان می‌دهد که قضاوت‌های جمعی و دموکراتیک از اعتبار بیشتری نسبت به آنچه که ما انتظار داشتیم برخوردار است، ما تأثیرات این ایده را در حل مسائل سیاسی، اجتماعی در طی سال‌های اخیر شاهد هستیم. در ادبیات خرد جمعی هر جامعه‌ای را خردمند نمی‌گویند. از دیدگاه سورویکی خردمند بودن جامعه در شرایط چهارگانه پراکندگی[۲۷]، استقلال[۲۸]، عدم تمرکز[۲۹] و روش ترکیب مناسب[۳۰] است [۵۵].
۱-۴. خوشه‌بندی مبتنی بر انتخاب بر اساس نظریه خرد جمعی
هدف از این تحقیق استفاده از نظریه خرد جمعی برای انتخاب زیرمجموعه‌ی مناسب در خوشه‌بندی ترکیبی می‌باشد. تعاریف سورویکی از خرد جمعی مطابق با مسائل اجتماعی است و در تعاریف آن عناصر سازنده تصمیمات رأی افراد می‌باشد. در این تحقیق ابتدا مبتنی بر تعاریف پایه سورویکی از خرد جمعی و ادبیات مطرح در خوشه‌بندی ترکیبی، تعریف پایه‌ای از ادبیات خرد جمعی در خوشه‌بندی ترکیبی ارائه می‌دهیم و بر اساس آن الگوریتم پیشنهادی خود را در جهت پیاده‌سازی خوشه‌بندی ترکیبی ارائه می‌دهیم [۵۵]. شرایط چهارگانه خوشه‌بندی خردمند که متناسب با تعاریف سورویکی باز تعریف شده است به شرح زیر می‌باشد:
پراکندگی نتایج اولیه، هر الگوریتم خوشه‌بندی پایه باید به طور جداگانه و بدون واسطه به داده‌های مسئله دسترسی داشته و آن را تحلیل و خوشه‌بندی کند حتی اگر نتایج آن غلط باشد.
استقلال الگوریتم، روش تحلیل هر یک از خوشه‌بندی‌های پایه نباید تحت تأثیر روش‌های سایر خوشه‌بندی‌های پایه تعیین شود، این تأثیر می‌تواند در سطح نوع الگوریتم (گروه) یا پارامترهای اساسی یک الگوریتم خاص (افراد) باشد.
عدم تمرکز، ارتباط بین بخش‌های مختلف خوشه‌بندی خرد جمعی باید به گونه‌ای باشد تا بر روی عملکرد خوشه‌بندی پایه تأثیری ایجاد نکند تا از این طریق هر خوشه‌بندی پایه شانس این را داشته باشد تا با شخصی سازی و بر اساس دانش محلی خود بهترین نتیجه ممکن را آشکار سازد.
مکانیزم ترکیب مناسب، باید مکانیزمی وجود داشته باشد که بتوان توسط آن نتایج اولیه الگوریتم‌های پایه را با یکدیگر ترکیب کرده و به یک نتیجه نهایی (نظر جمعی) رسید.
در این تحقیق دو روش برای ترکیب خوشه‌بندی ترکیبی و خرد جمعی پیشنهاد شده است. با بهره گرفتن از تعاریف بالا الگوریتم روش اول مطرح خواهد شد که در آن، جهت رسیدن به نتیجه نهایی از آستانه‌گیری استفاده می‌شود. در این روش الگوریتم‌های خوشه‌بندی اولیه غیر هم نام کاملاً مستقل فرض خواهند شد و برای ارزیابی استقلال الگوریتم‌های هم نام نیاز به آستانه‌گیری می‌باشد. در روش دوم، سعی شده است تا دو بخش از روش اول بهبود یابد. از این روی جهت مدل‌سازی الگوریتم‌ها و ارزیابی استقلال آن‌ها نسبت به هم یک روش مبتنی بر گراف شبه کد ارائه می‌شود و میزان استقلال به دست آمده در این روش به عنوان وزنی برای ارزیابی پراکندگی در تشکیل جواب نهایی مورد استفاده قرار می‌گیرد. جهت ارزیابی، روش‌های پیشنهادی با روش‌های پایه، روش ترکیب کامل و چند روش معروف ترکیب مبتنی بر انتخاب مقایسه خواهد شد. از این روی از چهارده داده استاندارد و یا مصنوعی که عموماً از سایت UCI [76] جمع آوری شده‌اند استفاده شده است. در انتخاب این داده‌ها سعی شده، داده‌هایی با مقیاس کوچک، متوسط و بزرگ انتخاب شوند تا کارایی روش بدون در نظر گرفتن مقیاس داده ارزیابی شود. همچنین جهت اطمینان از صحت نتایج تمامی آزمایش‌های تجربی گزارش‌شده حداقل ده بار تکرار شده است.
۱-۴-۱- فرضیات تحقیق
این تحقیق بر اساس فرضیات زیر اقدام به ارائه روشی جدید در خوشه‌بندی ترکیبی مبتنی بر انتخاب بر اساس نظریه خرد جمعی می‌کند.
۱ ) در این تحقیق تمامی آستانه‌گیری‌ها بر اساس میزان صحت نتایج نهایی و مدت زمان اجرای الگوریتم به صورت تجربی انتخاب می‌شوند.
۲ ) در این تحقیق جهت ارزیابی عملکرد یک الگوریتم، نتایج اجرای آن را بر روی‌داده‌های استاندارد UCI در محیطی با شرایط و پارامترهای مشابه نسبت به سایر الگوریتم‌ها ارزیابی می‌کنیم که این داده‌ها الزاماً حجیم یا خیلی کوچک نیستند.
۳ ) جهت اطمینان از صحت نتایج آزمایش‌ها ارائه‌شده در این تحقیق، حداقل اجرای هر الگوریتم بر روی هر داده ده بار تکرار شده و نتیجه‌ی نهایی میانگین نتایج به دست آمده می‌باشد.
۴ ) از آنجایی که روش مطرح‌شده در این تحقیق یک روش مکاشفه‌ای است سعی خواهد شد بیشتر با روش‌های مکاشفه‌ای مطرح در خوشه‌بندی ترکیبی مقایسه و نتایج آن مورد بررسی قرار گیرد.
در این فصل اهداف، مفاهیم و چالش‌های این تحقیق به صورت خلاصه ارائه شد. در ادامه این تحقیق، در فصل دوم، الگوریتم‌های خوشه‌بندی پایه و روش‌های خوشه‌بندی ترکیبی مورد بررسی قرار می‌گیرد. همچنین به مرور روش‌های انتخاب خوشه[۳۱] و یا افراز[۳۲] در خوشه‌بندی ترکیبی مبتنی بر انتخاب خواهیم پرداخت. در فصل سوم، نظریه خرد جمعی و دو روش پیشنهادی خوشه‌بندی خردمند ارائه می‌شود. در فصل چهارم، به ارائه نتایج آزمایش‌های تجربی این تحقیق و ارزیابی آن‌ها می‌پردازیم و در فصل پنجم، به ارائه نتایج و کارهای آتی خواهیم پرداخت.
فصل دوم
مروری بر ادبیات تحقیق
-
- مروری بر ادبیات تحقیق
۲-۱. مقدمه
در این بخش، کارهای انجام‌شده در خوشه‌بندی و خوشه‌بندی ترکیبی را مورد مطالعه قرار می‌دهیم. ابتدا چند الگوریتم پایه خوشه‌بندی معروف را معرفی خواهیم کرد. سپس چند روش کاربردی جهت ارزیابی خوشه، خوشه‌بندی و افرازبندی را مورد مطالعه قرار می‌دهیم. در ادامه به بررسی ادبیات خوشه‌بندی ترکیبی خواهیم پرداخت و روش‌های ترکیب متداول را بررسی خواهیم کرد. از روش‌های خوشه‌بندی ترکیبی، روش ترکیب کامل و چند روش معروف مبتنی بر انتخاب را به صورت مفصل شرح خواهیم داد.
۲-۲. خوشه‌بندی
در این بخش ابتدا انواع الگوریتم‌های خوشه‌بندی پایه را معرفی می‌کنیم و سپس برخی از آن‌ها را مورد مطالعه قرار می‌دهیم سپس برای ارزیابی نتایج به دست آمده چند متریک معرفی خواهیم کرد.
۲-۲-۱. الگوریتم‌های خوشه‌بندی پایه
به طور کلی، الگوریتم‌های خوشه‌بندی را می‌توان به دو دسته کلی تقسیم کرد:
فرم در حال بارگذاری ...
