پایان نامه مقطع کارشناسی ارشد رشته فناوری اطلاعات

وزارت علوم، تحقيقات و فناوري

دانشگاه علوم و فنون مازندران

پايان نامه مقطع كارشناسي ارشد

رشته: فناوري اطلاعات – مديريت سيستم‌هاي اطلاعاتي

عنوان:

خوشه‌بندي مبتني بر انتخاب بر اساس نظريه خرد جمعي

استاد راهنما:

جناب آقاي دکتر بهروز مينايي

استاد مشاور:

جناب آقاي دکتر حسين عليزاده

برای رعایت حریم خصوصی نام نگارنده درج نمی گردد

تکه هایی از متن به عنوان نمونه :

چکیده:

خوشه‌بندي وظيفه کاوش الگوهاي پنهان در داده‌هاي بدون برچسب را بر عهده دارد. به خاطر پيچيدگي مسئله و ضعف روش‌هاي خوشه‌بندي پايه، امروزه روش‌هاي خوشه‌بندي ترکيبي مورد بهره گیری قرار مي‌گيرند. به روشي از خوشه‌بندي ترکيبي که در آن از زيرمجموعه‌اي منتخب از نتايج اوليه براي ترکيب و ساخت نتيجه نهايي بهره گیری مي‌گردد خوشه‌بندي ترکيبي مبتني بر انتخاب زيرمجموعه نتايج اوليه مي‌گويند. در سال‌هاي اخير تمرکز بر روي ارزيابي نتايج اوليه براي انتخاب خوشه در خوشه‌بندي ترکيبي مورد توجه محققين زيادي قرار گرفته می باشد. اما پاسخ به بعضي از سؤالات در اين زمينه همچنان با ابهامات زيادي روبروست. از طرفي ديگر، نظريه خرد جمعي که اولين بار توسط سورويکي چاپ گردیده می باشد، نشان مي‌دهد که قضاوت‌هاي جمعي و دموکراتيک از اعتبار بيشتري نسبت به آن چیز که که ما انتظار داشتيم برخوردار هستند. اين نظريه چهار شرط پراکندگي، استقلال، عدم تمرکز و روش ترکيب مناسب آراء را براي هر جمعيت خردمند لازم و کافي مي‌داند. هدف اين تحقيق پيشنهاد فرآيندي جهت نگاشت و به‌کارگيري نظريه خرد جمعي در انتخاب زيرمجموعه مناسب در خوشه‌بندي ترکيبي مبتني بر انتخاب مي‌باشد. از اين روي در اين تحقيق آغاز با بهره گیری از تعاريف مطرح‌شده در نظريه خرد جمعي باز تعريفي متناسب با خوشه‌بندي ترکيبي مبتني بر انتخاب ارائه مي‌گردد و بر اساس آن دو روش براي ترکيب اين دو مفهوم پيشنهاد مي‌گردد. در روش پيشنهادي اول الگوريتم‌هاي خوشه‌بندي اوليه غير هم نام کاملاً مستقل فرض خواهند گردید و براي ارزيابي استقلال الگوريتم‌هاي هم نام نياز به آستانه‌گيري مي‌باشد. در روش دوم، سعي شده می باشد تا دو بخش از روش اول بهبود يابد. از اين روي جهت مدل‌سازي الگوريتم‌ها و ارزيابي استقلال آن‌ها نسبت به هم يک روش مبتني بر گراف کد الگوريتم ارائه مي‌گردد و ميزان استقلال به دست آمده در اين روش به عنوان وزني براي ارزيابي پراکندگي در تشکيل جواب نهايي مورد بهره گیری قرار مي‌گيرد. جهت بررسي ادعاهاي اين تحقيق در بخش ارزيابي دقت و اطلاعات متقابل نرمال شده‌ي روش‌هاي پيشنهادي بر روي داده‌ّهاي استاندارد با روش‌هاي پايه، روش‌ ترکيب کامل و چند روش معروف خوشه‌بندي ترکيبي مبتني بر انتخاب مقايسه مي‌شوند که اين مقايسه کاراريي بالاي روش‌هاي پيشنهادي اين تحقيق در اکثر موارد نسبت به ساير روش‌هاي مطرح شده را نشان مي‌دهد. همچنين در بخش نتيجه‌گيري چندين روش توسعه جهت كارهاي آتي‌ پيشنهاد مي‌گردد.

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

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

شما می توانید مطالب مشابه این مطلب را با جستجو در همین سایت بخوانید                     

[29] Decentralization

[30] Aggregation Mechanism

[31] Cluster

[32] Partition

***ممکن می باشد هنگام انتقال از فایل اصلی به داخل سایت بعضی متون به هم بریزد یا بعضی نمادها و اشکال درج نشود اما در فایل دانلودی همه چیز مرتب و کامل و با فرمت ورد موجود می باشد***

متن کامل را می توانید دانلود نمائید

زیرا فقط تکه هایی از متن پایان نامه در این صفحه درج شده (به گونه نمونه)

اما در فایل دانلودی متن کامل پایان نامه

 با فرمت ورد word که قابل ویرایش و کپی کردن می باشند

موجود می باشد

تعداد صفحه : 167

قیمت : چهارده هزار و هفتصد تومان