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

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

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

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

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

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

عنوان:

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

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

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

استاد مشاور:

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

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

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

چکیده:

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

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

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

قیمت : 14700 تومان

 

***

—-

:       

****         serderehi@gmail.com

جستجو در سایت : کلمه کلیدی خود را وارد نمایید :
 

 

برچسب ها :