روش‌های پیشنهادی این تحقیق در اکثر موارد نسبت به سایر روش‌های مطرح شده را نشان می‌دهد. همچنین در بخش نتیجه‌گیری چندین روش توسعه جهت كارهای آتی‌ پیشنهاد می‌شود.

فصل اول: مقدمه

1- مقدمه

1-1- خوشه بندی

به عنوان یکی از شاخه‌های وسیع و پرکاربرد هوش مصنوعی[1]، یادگیری ماشین[2] به تنظیم و اکتشاف شیوه‌ها و الگوریتم‌هایی می‌پردازد که بر اساس آن‌ها رایانه‌ها و سامانه‌های اطلاعاتی توانایی تعلم و یادگیری پیدا می‌کنند. طیف پژوهش‌هایی که در مورد یادگیری ماشینی صورت می‌گیرد گسترده ‌است. در سوی نظر‌ی آن پژوهش‌گران بر آن‌اند که روش‌های یادگیری تازه‌ای به وجود بیاورند و امکان‌پذیری و کیفیت یادگیری را برای روش‌هایشان مطالعه کنند و در سوی دیگر عده‌ای از پژوهش‌گران سعی می‌کنند روش‌های یادگیری ماشینی را بر مسائل تازه‌ای اعمال کنند. البته این طیف گسسته نیست و پژوهش‌های انجام‌شده دارای مؤلفه‌هایی از هر دو رو‌یكرد هستند. امروزه، داده‌كاوی[3] به عنوان یك ابزار قوی برای تولید اطلاعات و دانش از داده‌های خام، در یادگیری ماشین شناخته‌شده و همچنان با سرعت در حال رشد و تكامل است. به طور كلی می‌توان تکنیک‌های داده‌كاوی را به دو دسته بانظارت[4] و بدون نظارت[5] تقسیم كرد [29, 46].

در روش بانظارت ما ورودی (داده یادگیری[6]) و خروجی (كلاس[7] داده) یك مجموعه داده را به الگوریتم هوشمند می‌دهیم تا آن الگوی[8] بین ورودی و خروجی را تشخیص دهد در این روش خروجی كار ما مدلی[9] است كه می‌تواند برای ورودی‌های جدید خروجی درست را پیش‌بینی[10] كند. روش‌های طبقه‌بندی[11] و قوانین انجمنی[12] از این جمله تكنیك‌ها می‌باشد. روش‌های با نظارت كاربرد فراوانی دارند اما مشكل عمده این روش‌ها این است كه همواره باید داده‌ای برای یادگیری وجود داشته باشد كه در آن به ازای ورودی مشخص خروجی درست آن مشخص شده باشد. حال آنكه اگر در زمینه‌ای خاص داده‌ای با این فرمت وجود نداشته باشد این روش‌ها قادر به حل این‌گونه مسائل نخواهند بود [29, 68]. در روش بدون نظارت برخلاف یادگیری بانظارت هدف ارتباط ورودی و خروجی نیست، بلکه تنها دسته‌بندی ورودی‌ها است. این نوع یادگیری بسیار مهم است چون خیلی از مسائل (همانند دنیای ربات‌ها) پر از ورودی‌هایی است که هیچ برچسبی[13] (كلاس) به آن‌ها اختصاص داده نشده است اما به وضوح جزئی از یک دسته هستند [46, 68]. خوشه‌بندی[14] شاخص‌ترین روش در داده‌كاوی جهت حل مسائل به صورت بدون ناظر است. ایده اصلی خوشه‌بندی اطلاعات، جدا کردن نمونه‌ها از یكدیگر و قرار دادن آن‌ها در گروه‌های شبیه به هم می‌باشد. به این معنی كه نمونه‌های شبیه به هم باید در یك گروه قرار بگیرند و با نمونه‌های گروه‌های دیگر حداكثر متفاوت را دارا باشند [20, 26]. دلایل اصلی برای اهمیت خوشه‌بندی عبارت‌اند از:

اول، جمع‌آوری و برچسب‌گذاری یك مجموعه بزرگ از الگوهای نمونه می‌تواند بسیار پركاربرد و باارزش باشد.

 

دوم، می‌توانیم از روش‌های خوشه‌بندی برای پیدا کردن و استخراج ویژگی‌ها[15] و الگوهای جدید استفاده كنیم. این كار می‌تواند كمك به سزایی در كشف دانش ضمنی[16] داده‌ها انجام دهد.

سوم، با خوشه‌بندی می‌توانیم یك دید و بینشی از طبیعت و ساختار داده به دست آوریم كه این می‌تواند برای ما باارزش باشد.

چهارم، خوشه‌بندی می‌تواند منجر به كشف زیر رده‌های[17] مجزا یا شباهت‌های بین الگوها ممكن شود كه به طور چشمگیری در روش طراحی طبقه‌بندی قابل استفاده باشد.

1-2. خوشه‌بندی تركیبی

هر یك از الگوریتم‌های خوشه‌بندی، با توجه به اینكه بر روی جنبه‌های متفاوتی از داده‌ها تاكید می‌کند، داده‌ها را به صورت‌های متفاوتی خوشه‌بندی می‌نماید. به همین دلیل، نیازمند روش‌هایی هستیم كه بتواند با استفاده از تركیب این الگوریتم‌ها و گرفتن نقاط قوت هر یك، نتایج بهینه‌تری را تولید كند. در واقع هدف اصلی خوشه‌بندی تركیبی[18] جستجوی بهترین خوشه‌ها با استفاده از تركیب نتایج الگوریتم‌های دیگر است [1, 8, 9, 54, 56]. به روشی از خوشه‌بندی ترکیبی که زیرمجموعه‌ی منتخب از نتایج اولیه برای ترکیب و ساخت نتایج نهایی استفاده می‌شود خوشه‌بندی ترکیبی مبتنی بر انتخاب[19] زیرمجموعه نتایج اولیه می‌گویند. در این روش‌ها بر اساس معیاری توافقی مجموعه‌ای از مطلوب‌ترین نتایج اولیه را انتخاب كرده و فقط توسط آن‌ها نتیجه نهایی را ایجاد می‌کنیم [21]. معیارهای مختلفی جهت انتخاب مطلوب‌ترین روش پیشنهاد شده است كه معیار اطلاعات متقابل نرمال شده[20]، روش ماكزیموم[21] و [22]APMM برخی از آن‌ها می‌باشند [8, 9, 21, 67]. دو مرحله مهم در خوشه‌بندی ترکیبی عبارت‌اند از:

اول، الگوریتم‌های ابتدایی خوشه‌بندی که خوشه‌بندی اولیه را انجام می‌دهد.

دوم، جمع‌بندی نتایج این الگوریتم‌های اولیه (پایه) برای به دست آوردن نتیجه نهایی.

1-3. خرد جمعی

نظریه خرد جمعی[23] كه اولین بار توسط سورویکی[24] در سال 2004 در كتابی با همان عنوان منتشر شد، استنباطی از مسائل مطرح‌شده توسط گالتون[25] و کندورست[26] می‌باشد، و نشان می‌دهد که قضاوت‌های جمعی و دموکراتیک از اعتبار بیشتری نسبت به آنچه که ما انتظار داشتیم برخوردار است، ما تأثیرات این ایده را در حل مسائل سیاسی، اجتماعی در طی سال‌های اخیر شاهد هستیم. در ادبیات خرد جمعی هر جامعه‌ای را خردمند نمی‌گویند. از دیدگاه سورویكی خردمند بودن جامعه در شرایط چهارگانه پراكندگی[27]، استقلال[28]، عدم تمركز[29] و روش ترکیب مناسب[30] است [55].

1-4. خوشه‌بندی مبتنی بر انتخاب بر اساس نظریه خرد جمعی

هدف از این تحقیق استفاده از نظریه خرد جمعی برای انتخاب زیرمجموعه‌ی مناسب در خوشه‌بندی ترکیبی می‌باشد. تعاریف سورویکی از خرد جمعی مطابق با مسائل اجتماعی است و در تعاریف آن عناصر سازنده تصمیمات رأی افراد می‌باشد. در این تحقیق ابتدا مبتنی بر تعاریف پایه سورویکی از خرد جمعی و ادبیات مطرح در خوشه‌بندی ترکیبی، تعریف پایه‌ای از ادبیات خرد جمعی در خوشه‌بندی ترکیبی ارائه می‌دهیم و بر اساس آن الگوریتم پیشنهادی خود را در جهت پیاده‌سازی خوشه‌بندی ترکیبی ارائه می‌دهیم [55]. شرایط چهارگانه خوشه‌بندی خردمند که متناسب با تعاریف سورویکی باز تعریف شده است به شرح زیر می‌باشد:

پراکندگی نتایج اولیه، هر الگوریتم خوشه‌بندی پایه باید به طور جداگانه و بدون واسطه به داده‌های مسئله دسترسی داشته و آن را تحلیل و خوشه‌بندی کند حتی اگر نتایج آن غلط باشد.

استقلال الگوریتم، روش تحلیل هر یک از خوشه‌بندی‌های پایه نباید تحت تأثیر روش‌های سایر خوشه‌بندی‌های پایه تعیین شود، این تأثیر می‌تواند در سطح نوع الگوریتم (گروه) یا پارامترهای اساسی یک الگوریتم خاص (افراد) باشد.

عدم تمرکز، ارتباط بین بخش‌های مختلف خوشه‌بندی خرد جمعی باید به گونه‌ای باشد تا بر روی عملکرد خوشه‌بندی پایه تأثیری ایجاد نکند تا از این طریق هر خوشه‌بندی پایه شانس این را داشته باشد تا با شخصی سازی و بر اساس دانش محلی خود بهترین نتیجه ممکن را آشکار سازد.

مکانیزم ترکیب مناسب، باید مکانیزمی وجود داشته باشد که بتوان توسط آن نتایج اولیه الگوریتم‌های پایه را با یکدیگر ترکیب کرده و به یک نتیجه نهایی (نظر جمعی) رسید.

در این تحقیق دو روش برای ترکیب خوشه‌بندی ترکیبی و خرد جمعی پیشنهاد شده است. با استفاده از تعاریف بالا الگوریتم روش اول مطرح خواهد شد که در آن، جهت رسیدن به نتیجه نهایی از آستانه‌گیری استفاده می‌شود. در این روش الگوریتم‌های خوشه‌بندی اولیه غیر هم نام کاملاً مستقل فرض خواهند شد و برای ارزیابی استقلال الگوریتم‌های هم نام نیاز به آستانه‌گیری می‌باشد. در روش دوم، سعی شده است تا دو بخش از روش اول بهبود یابد. از این روی جهت مدل‌سازی الگوریتم‌ها و ارزیابی استقلال آن‌ها نسبت به هم یک روش مبتنی بر گراف شبه کد ارائه می‌شود و میزان استقلال به دست آمده در این روش به عنوان وزنی برای ارزیابی پراکندگی در تشکیل جواب نهایی مورد استفاده قرار می‌گیرد. جهت ارزیابی، روش‌های پیشنهادی با روش‌های پایه، روش‌ ترکیب کامل و چند روش معروف ترکیب مبتنی بر انتخاب مقایسه خواهد شد. از این روی از چهارده داده استاندارد و یا مصنوعی که عموماً از سایت UCI [76] جمع‌آوری شده‌اند استفاده شده است. در انتخاب این داده‌ها سعی شده، داده‌هایی با مقیاس‌ کوچک، متوسط و بزرگ انتخاب شوند تا کارایی روش بدون در نظر گرفتن مقیاس داده ارزیابی شود. همچنین جهت اطمینان از صحت نتایج تمامی آزمایش‌های تجربی گزارش‌شده حداقل ده بار تکرار شده است.

1-4-1- فرضیات تحقیق

این تحقیق بر اساس فرضیات زیر اقدام به ارائه روشی جدید در خوشه‌بندی ترکیبی مبتنی بر انتخاب بر اساس نظریه خرد جمعی می‌کند.

1) در این تحقیق تمامی آستانه‌گیری‌ها بر اساس میزان صحت نتایج نهایی و مدت زمان اجرای الگوریتم به صورت تجربی انتخاب می‌شوند.

2) در این تحقیق جهت ارزیابی عملکرد یک الگوریتم، نتایج اجرای آن را بر روی‌داده‌های استاندارد UCI در محیطی با شرایط و پارامترهای مشابه نسبت به سایر الگوریتم‌ها ارزیابی می‌کنیم که این داده‌ها الزاماً حجیم یا خیلی کوچک نیستند.

3) جهت اطمینان از صحت نتایج آزمایش‌ها ارائه‌شده در این تحقیق، حداقل اجرای هر الگوریتم بر روی هر داده ده بار تکرار شده و نتیجه‌ نهایی میانگین نتایج به دست آمده می‌باشد.

4) از آنجایی که روش مطرح‌شده در این تحقیق یک روش مکاشفه‌ای است سعی خواهد شد بیشتر با روش‌های مکاشفه‌ای مطرح در خوشه‌بندی ترکیبی مقایسه و نتایج آن مورد بررسی قرار گیرد.

در این فصل اهداف، مفاهیم و چالش‌های این تحقیق به صورت خلاصه ارائه شد. در ادامه این تحقیق، در فصل دوم، الگوریتم‌های خوشه‌بندی پایه و روش‌های خوشه‌بندی‌ تركیبی مورد بررسی قرار می‌گیرد. همچنین به مرور روش‌های انتخاب خوشه[31] و یا افراز[32] در خوشه‌بندی ترکیبی مبتنی بر انتخاب خواهیم پرداخت. در فصل سوم، نظریه خرد جمعی و دو روش پیشنهادی خوشه‌بندی خردمند ارائه می‌شود. در فصل چهارم، به ارائه نتایج آزمایش‌های تجربی این تحقیق و ارزیابی آن‌ها می‌پردازیم و در فصل پنجم، به ارائه‌ی نتایج و کار‌های آتی خواهیم پرداخت.

[1] Artificial Intelligent (AI)

[2] Machine Learning

[3] Data Mining

[4] Supervised

[5] Unsupervised

[6] Train Set

[7] Class

[8] Pattern

[9] Learning Model

[10] Predictive

[11] Classification

[12] Association rule mining

[13] Label

[14] Clustering

[15] Features

[16] Tacit knowledge

[17] Sub-Class

[18] Cluster Ensemble

[19] Cluster Ensemble Selection

[20] Normalized Mutual Information

[21] Maximum

[22] Alizadeh-Parvin-Moshki-Minaei

[23] The wisdom of crowds

[24] Surowiecki

[25] Francis Galton (1822-1911)

[26] Condorcet

[27] Diversity

[28] Independency