پایان نامه ها

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

هر يك از الگوريتم‌هاي خوشه‌بندي، با توجه به اينكه بر روي جنبه‌هاي متفاوتي از داده‌ها تاكيد مي‌کند، داده‌ها را به صورت‌هاي متفاوتي خوشه‌بندي مي‌نمايد. به همين دليل، نيازمند روش‌هايي هستيم كه بتواند با استفاده از تركيب اين الگوريتم‌ها و گرفتن نقاط قوت هر يك، نتايج بهينه‌تري را توليد كند. در واقع هدف اصلي خوشه‌بندي تركيبي18 جستجوي بهترين خوشه‌ها با استفاده از تركيب نتايج الگوريتم‌هاي ديگر است [1, 8, 9, 54, 56]. به روشي از خوشه‌بندي ترکيبي که زيرمجموعه‌ي منتخب از نتايج اوليه براي ترکيب و ساخت نتايج نهايي استفاده مي‌شود خوشه‌بندي ترکيبي مبتني بر انتخاب19 زيرمجموعه نتايج اوليه مي‌گويند. در اين روش‌ها بر اساس معياري توافقي مجموعه‌اي از مطلوب‌ترين نتايج اوليه را انتخاب كرده و فقط توسط آن‌ها نتيجه نهايي را ايجاد مي‌کنيم [21]. معيارهاي مختلفي جهت انتخاب مطلوب‌ترين روش پيشنهاد شده است كه معيار اطلاعات متقابل نرمال شده20، روش ماكزيموم21 و 22APMM برخي از آن‌ها مي‌باشند [8, 9, 21, 67]. دو مرحله مهم در خوشه‌بندي ترکيبي عبارت‌اند از:
اول، الگوريتم‌هاي ابتدايي خوشه‌بندي که خوشه‌بندي اوليه را انجام مي‌دهد.
دوم، جمع‌بندي نتايج اين الگوريتم‌هاي اوليه (پايه) براي به دست آوردن نتيجه نهايي.
1-3. خرد جمعي
نظريه خرد جمعي23 كه اولين بار توسط سورويکي24 در سال 2004 در كتابي با همان عنوان منتشر شد، استنباطي از مسائل مطرح‌شده توسط گالتون25 و کندورست26 مي‌باشد، و نشان مي‌دهد که قضاوت‌هاي جمعي و دموکراتيک از اعتبار بيشتري نسبت به آنچه که ما انتظار داشتيم برخوردار است، ما تأثيرات اين ايده را در حل مسائل سياسي، اجتماعي در طي سال‌هاي اخير شاهد هستيم. در ادبيات خرد جمعي هر جامعه‌اي را خردمند نمي‌گويند. از ديدگاه سورويكي خردمند بودن جامعه در شرايط چهارگانه پراكندگي27، استقلال28، عدم تمركز29 و روش ترکيب مناسب30 است [55].
1-4. خوشه‌بندي مبتني بر انتخاب بر اساس نظريه خرد جمعي
هدف از اين تحقيق استفاده از نظريه خرد جمعي برای انتخاب زيرمجموعه‌ي مناسب در خوشه‌بندي ترکيبي مي‌باشد. تعاريف سورويکي از خرد جمعي مطابق با مسائل اجتماعي است و در تعاريف آن عناصر سازنده تصميمات رأي افراد مي‌باشد. در اين تحقيق ابتدا مبتني بر تعاريف پايه سورويکي از خرد جمعي و ادبيات مطرح در خوشه‌بندي ترکيبي، تعريف پايه‌اي از ادبيات خرد جمعي در خوشه‌بندي ترکيبي ارائه مي‌دهيم و بر اساس آن الگوريتم پيشنهادي خود را در جهت پياده‌سازي خوشه‌بندي ترکيبي ارائه مي‌دهيم [55]. شرايط چهارگانه خوشه‌بندي خردمند که متناسب با تعاريف سورويکي باز تعريف شده است به شرح زير مي‌باشد:
پراکندگي نتايج اوليه، هر الگوريتم خوشه‌بندي پايه بايد به طور جداگانه و بدون واسطه به داده‌هاي مسئله دسترسي داشته و آن را تحليل و خوشه‌بندي کند حتي اگر نتايج آن غلط باشد.
استقلال الگوريتم، روش تحليل هر يک از خوشه‌بندي‌هاي پايه نبايد تحت تأثير روش‌هاي ساير خوشه‌بندي‌هاي پايه تعيين شود، اين تأثير مي‌تواند در سطح نوع الگوريتم (گروه) يا پارامترهاي اساسي يک الگوريتم خاص (افراد) باشد.
عدم تمرکز، ارتباط بين بخش‌هاي مختلف خوشه‌بندي خرد جمعي بايد به گونه‌اي باشد تا بر روي عملکرد خوشه‌بندي پايه تأثيري ايجاد نکند تا از اين طريق هر خوشه‌بندي پايه شانس اين را داشته باشد تا با شخصي سازي و بر اساس دانش محلي خود بهترين نتيجه ممکن را آشکار سازد.
مکانيزم ترکيب مناسب، بايد مکانيزمي وجود داشته باشد که بتوان توسط آن نتايج اوليه الگوريتم‌هاي پايه را با يکديگر ترکيب کرده و به يک نتيجه نهايي (نظر جمعي) رسيد.
در اين تحقيق دو روش براي ترکيب خوشه‌بندي ترکيبي و خرد جمعي پيشنهاد شده است. با استفاده از تعاريف بالا الگوريتم روش اول مطرح خواهد شد که در آن، جهت رسيدن به نتيجه نهايي از آستانه‌گيري استفاده می‌شود. در اين روش الگوريتم‌هاي خوشه‌بندي اوليه غير هم نام کاملاً مستقل فرض خواهند شد و براي ارزيابي استقلال الگوريتم‌هاي هم نام نياز به آستانه‌گيري مي‌باشد. در روش دوم، سعي شده است تا دو بخش از روش اول بهبود يابد. از اين روي جهت مدل‌سازي الگوريتم‌ها و ارزيابي استقلال آن‌ها نسبت به هم يک روش مبتني بر گراف شبه کد ارائه مي‌شود و ميزان استقلال به دست آمده در اين روش به عنوان وزني براي ارزيابي پراکندگي در تشکيل جواب نهايي مورد استفاده قرار مي‌گيرد. جهت ارزيابي، روش‌هاي پيشنهادي با روش‌هاي پايه، روش‌ ترکيب کامل و چند روش معروف ترکيب مبتني بر انتخاب مقايسه خواهد شد. از اين روي از چهارده داده استاندارد و يا مصنوعي که عموماً از سايت UCI [76] جمع‌آوري شده‌اند استفاده شده است. در انتخاب اين داده‌ها سعي شده، داده‌هايي با مقياس‌ کوچک، متوسط و بزرگ انتخاب شوند تا کارايي روش بدون در نظر گرفتن مقياس داده ارزيابي شود. همچنين جهت اطمينان از صحت نتايج تمامي آزمايش‌هاي تجربي گزارش‌شده حداقل ده بار تکرار شده است.
1-4-1- فرضيات تحقيق
اين تحقيق بر اساس فرضيات زير اقدام به ارائه روشي جديد در خوشه‌بندي ترکيبي مبتني بر انتخاب بر اساس نظريه خرد جمعي مي‌کند.
۱ ) در اين تحقيق تمامي آستانه‌گيري‌ها بر اساس ميزان صحت نتايج نهايي و مدت زمان اجراي الگوريتم به صورت تجربي انتخاب مي‌شوند.
۲ ) در اين تحقيق جهت ارزيابي عملکرد يک الگوريتم، نتايج اجراي آن را
بر روي‌داده‌هاي استاندارد UCI در محيطی با شرايط و پارامترهاي مشابه نسبت به ساير الگوريتم‌ها ارزيابي مي‌کنيم که اين داده‌ها الزاماً حجيم يا خيلي کوچک نيستند.
۳ ) جهت اطمينان از صحت نتايج آزمايش‌ها ارائه‌شده در اين تحقيق، حداقل اجراي هر الگوريتم بر روي هر داده ده بار تکرار شده و نتيجه‌ي نهايي ميانگين نتايج به دست آمده مي‌باشد.
4 ) از آنجايي که روش مطرح‌شده در اين تحقيق يک روش مکاشفه‌اي است سعي خواهد شد بيشتر با روش‌هاي مکاشفه‌اي مطرح در خوشه‌بندي ترکيبي مقايسه و نتايج آن مورد بررسي قرار گيرد.

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

فصل دوم
مروري بر ادبيات تحقيق

2. مروري بر ادبيات تحقيق
2-1. مقدمه
در اين بخش، کارهاي انجام‌شده در خوشه‌بندي و خوشه‌بندي ترکيبي را مورد مطالعه قرار مي‌دهيم. ابتدا چند الگوريتم‌ پايه خوشه‌بندي معروف را معرفي خواهيم کرد. سپس چند روش کاربردي جهت ارزيابي خوشه، خوشه‌بندي و افرازبندي را مورد مطالعه قرار مي‌دهيم. در ادامه به بررسي ادبيات خوشه‌بندي ترکيبي خواهيم پرداخت و روش‌هاي ترکيب متداول را بررسي خواهيم کرد. از روش‌هاي خوشه‌بندي ترکيبي، روش ترکيب کامل و چند روش معروف مبتني بر انتخاب را به صورت مفصل شرح خواهيم داد.
2-2. خوشه‌بندي
در اين بخش ابتدا انواع الگوريتم‌هاي خوشه‌بندي پايه را معرفي مي‌کنيم و سپس برخي از آن‌ها را مورد مطالعه قرار مي‌دهيم سپس براي ارزيابي نتايج به دست آمده چند متريک معرفي خواهيم کرد.
2-2-1. الگوريتم‌هاي خوشه‌بندي پايه
به طور كلي، الگوريتم‌هاي خوشه‌بندي را مي‌توان به دو دسته كلي تقسيم كرد:
1- الگوريتم‌هاي سلسله مراتبي33
2- الگوريتم‌هاي افرازبندي34
الگوريتم‌هاي سلسله مراتبي، يك روال براي تبديل يك ماتريس مجاورت به يك دنباله از افرازهاي تو در تو، به صورت يك درخت است. در اين روش‌ها، مستقيماً با داده‌ها سروكار داريم و از روابط بين آن‌ها براي به دست آوردن خوشه‌ها استفاده مي‌کنيم. يكي از ويژگي‌هاي اين روش قابليت تعيين تعداد خوشه‌ها به صورت بهينه مي‌باشد. در نقطه مقابل الگوريتم‌هاي سلسله مراتبي، الگوريتم‌هاي افرازبندي قرار دارند. هدف اين الگوريتم‌ها، تقسيم داده‌ها در خوشه‌ها، به گونه‌اي است كه داده‌هاي درون يك خوشه بيش‌ترين شباهت را به همديگر داشته باشند؛ و درعين‌حال، بيش‌ترين فاصله و اختلاف را با داده‌هاي خوشه‌هاي ديگر داشته باشند. در اين فصل تعدادي از متداول‌ترين الگوريتم‌هاي خوشه‌بندي، در دو دسته سلسله مراتبي و افرازبندي، مورد بررسي قرار مي‌گيرند. از روش سلسله‌ مراتبي چهار الگوريتم‌ از سري الگوريتم‌هاي پيوندي35 را مورد بررسي قرار مي‌دهيم. و از الگوريتم‌هاي افرازبندي K-means، FCM و الگوريتم طيفي را مورد بررسي خواهيم داد.
2-2-1-1. الگوريتم‌هاي سلسله مراتبي
همان‌گونه كه در شكل 2-1 مشاهده مي‌شود، روال الگوريتم‌هاي خوشه‌بندي سلسله مراتبي را مي‌تواند به صورت يك دندوگرام36 نمايش داد. اين نوع نمايش تصويري از خوشه‌بندي سلسله مراتبي، براي انسان، بيشتر از يك ليست از نمادها قابل‌درک است. در واقع دندوگرام، يك نوع خاص از ساختار درخت است كه يك تصوير قابل‌فهم از خوشه‌بندي سلسله مراتبي را ارائه مي‌کند. هر دندوگرام شامل چند لايه از گره‌هاست، به طوري كه هر لايه يك خوشه را نمايش مي‌دهد. خطوط متصل‌کننده گره‌ها، بيانگر خوشه‌هايي هستند كه به صورت آشيانه‌اي37 داخل يكديگر قرار دارند. برش افقي يك دندوگرام، يك خوشه‌بندي را توليد مي‌کند [33]. شكل 2-1 يك مثال ساده از خوشه‌بندي و دندوگرام مربوطه را نشان مي‌دهد.

شكل 2-1. يك خوشه‌بندي سلسله مراتبي و درخت متناظر
اگر الگوريتم‌هاي خوشه‌بندي سلسله مراتبي، دندوگرام را به صورت پايين به بالا بسازند، الگوريتم‌هاي خوشه‌بندي سلسله مراتبي تراكمي38 ناميده مي‌شوند. همچنين، اگر آن‌ها دندوگرام را به صورت بالا به پايين بسازند، الگوريتم‌هاي خوشه‌بندي سلسله مراتبي تقسيم‌کننده39 ناميده مي‌شوند [26]. مهم‌ترين روش‌هاي خوشه‌بندي سلسله مراتبي الگوريتم‌هاي سري پيوندي مي‌باشد كه در اين بخش تعدادي از کاراترين آن‌ها مورد بررسي قرار خواهند گرفت که عبارت‌اند از:
1- الگوريتم پيوندي منفرد40
2- الگوريتم پيوندي كامل41
3- الگوريتم پيوندي ميانگين42
4- الگوريتم پيوندي بخشي43
2-2-1-1-1. تعاريف و نماد‌ها

شكل 2-2. ماتريس مجاورت
قبل از معرفي اين الگوريتم‌ها، در ابتدا نمادها و نحوه نمايش مسئله نمايش داده خواهد شد. فرض كنيد كه يك ماتريس مجاورت متقارن داريم. وارده در هر سمت قطر اصلي قرار دارد كه شامل يك جاي گشت اعداد صحيح بين 1 تا است. ما مجاورت‌ها را عدم شباهت در نظر مي‌گيريم. به اين معني است كه اشياء 1 و 3 بيشتر از اشياء 1 و 2 به هم
شبيه‌اند. يك مثال از ماتريس مجاورت معمول براي است كه در شكل 2-2 نشان داده شده است. يك گراف آستانه44، يك گراف غير جهت‌دار و غير وزن‌دار، روي گره، بدون حلقه بازگشت به خود45 يا چند لبه است. هر نود يك شيء را نمايش مي‌دهد. يك گراف آستانه براي هر سطح عدم شباهت به اين صورت تعريف مي‌شود: اگر عدم شباهت اشياء و از حد آستانه کوچک‌تر باشد، با واردکردن يك لبه بين نودهاي ويك گراف آستانه تعريف مي‌کنيم.
(2-1)if and only if
شكل 2-3 يك رابطه دودويي به دست آمده از ماتريس مربوط به شكل 2-2 را براي مقدار آستانه 5 نشان مي‌دهد. نماد “*” در موقعيت ماتريس، نشان مي‌دهد كه جفت متعلق به رابطه دودويي مي‌باشد. شكل 2-4، گراف‌هاي آستانه براي ماتريس را نمايش مي‌دهد.

شكل 2-3. رابطه دودويي و گراف آستانه براي مقدار آستانه 5.

شكل 2-4. گراف‌هاي آستانه براي ماتريس
2-2-1-1-2. الگوريتم پيوندي منفرد
اين الگوريتم روش کمينه و روش نزديک‌ترين همسايه نيز ناميده مي‌شود [26]. اگر و خوشه‌ها باشند، در روش پيوندي منفرد، فاصله آن‌ها برابر خواهد بود با:
(2-2)
كه نشان‌دهنده فاصله (عدم شباهت) بين

متن کامل پایان نامه ها در 40y.ir

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *