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

گرایش : هوش مصنوعي

عنوان : روش تصمیم­ گیری دسته ­جمعی جهت بهبود عملکرد الگوریتم نزدیک­ترین همسایه

دانشگاه شیراز

دانشكده ­ي مهندسـي

پايان‌نامه كارشناسي ارشد در رشته مهندسي کامپيوتر (هوش مصنوعي)

روش تصمیم­ گیری دسته ­جمعی جهت بهبود عملکرد الگوریتم نزدیک­ترین همسایه

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

دكتر منصور ذوالقدری جهرمی

دکتر اقبال منصوری

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

(در فایل دانلودی نام نویسنده موجود است)

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

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

چکيده

نتایج آزمایشات نشان داده است که ترکیب چندین دسته­بند[1] می­تواند کارایی الگوریتم­های متنوع را بالا ببرد. روش­های تصمیم­گیری دسته­جمعی[2] بسیاری ارائه شده­اند که با بهره گرفتن از آن­ها، خطای روش­های مختلف دسته­بندی[3] کاهش یافته است. با این حال، این گونه روش­ها نتوانسته­اند کارایی الگوریتم نزدیک­ترین همسایه[4] را افزایش دهند. در این پایان نامه یک روش تصمیم­گیری دسته­جمعی ارائه شده است تا با بهره گرفتن از ترکیب وزن­دار چندین دسته­بند، کارایی را بهبود بدهد. در این روش هر کدام از این دسته­بند­ها یک دسته­بند نزدیک­ترین همسایه است که تنها از زیر مجموعه­ای از مجموعه ویژگی­ها[5] نمونه­ها استفاده می­کند. در ادامه، الگوریتم به هر کدام از آن­ها یک وزن اختصاص می­دهد و در نهایت از یک مکانیسم رای­گیری وزنی[6] برای تعیین خروجی مدل دسته­جمعی استفاده می کند.

فهرست مطالب

  عنوان                               صفحه

فصل اول   1

مقدمه  1

1-1- مقدمه. 2

1-2- روش­های دسته­بندی.. 3

1-3- ارزيابي دسته­بند. 4

1-4- تصدیق متقابل.. 6

1-5- الگوریتم نزدیک­ترین همسایه. 7

1-7- سر فصل­ها 9

فصل دوم  10

الگوریتم نزدیک­ترن همسایه و روش­های موجود برای بهبود آن.. 10

2-1-الگوریتم نزدیک­ترین همسایه. 11

2-2- محدودیت­های روش نزدیک­ترین همسایه. 14

2-3- مروری بر راه­کارهای ارائه شده در گذشته برای بهبود الگوریتم نزدیکترین همسایه. 15

فصل سوم  18

روش­های تصمیم­گیری دسته­جمعی.. 18

3-1- مقدمه. 19

3-2- روش­های متفاوت برای ایجاد یک تصمیم­گیر دسته­جمعی.. 21

3-3- ساختارهای مختلف در روش تصمیم­گیری دسته­جمعی.. 22

3-4- رای­گیری بین دسته­بندها 23

3-5- معرفی چند روش تصمیم­گیری دسته­جمعی پرکاربرد. 24

فصل چهارم  28

روش پیشنهادی برای دسته­جمعی کردن الگوریتم نزدیک­ترین همسایه. 28

4-1- مقدمه. 29

4-2- ایده­ی اصلی.. 30

4-3- دسته­جمعی کردن مجموعه دسته­بندهای وزن­دار نزدیک­ترین همسایه. 31

فصل پنجم   39

نتايج آزمایشات پياده سازي و نتیجه­گیری.. 39

5-1- نتایج.. 40

فصل ششم   45

نتیجه­گیری   45

فهرست منابع.. 48

  • مقدمه

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

یکی از مهم ترین این پردازش ها که در فناوری اطلاعات و ارتباطات مورد نیاز است، دسته­بندی خودکار این اطلاعات می باشد. دسته بندی در مسائل متنوعی در فناوری اطلاعات به کار گرفته می شود، در مسائلی مانند امنیت اطلاعات، شناسایی نفوزگری در شبکه، دسته بندی کاربران بر اساس اطلاعات شخصی، پردازش تصویر و در واقع شناسایی هر گونه الگو بر اساس نمونه­ها و اطلاعات پیشین. این پردازش می تواند دسته[1]­ی نمونه­های جدید که به مجموعه اطلاعات اضافه می شود را پیش بینی نماید. از این رو در هوش مصنوعی توجه خاصی به توسعه انواع روش­های دسته­بندی هوشمند و خودکار شده است.

 روش­های دسته­بندی

دسته­بندی یکی از مهم­ترین شاخه‌هاي يادگيري ماشين[2] است. دسته­بندی به پیش­بینی برچسب دسته[3] نمونه[4] بدون برچسب، بر اساس مجموعه نمونه­های آموزشی برچسب­دار (که قبلا به با کمک يک کارشناس دسته­بندي  شده­اند) گفته می­شود. درواقع دسته­بندی روشي است که هدف آن، گروه­بندي اشيا به تعدادي دسته یا گروه مي­باشد. در روش‌هاي دسته­بندی، با بهره گرفتن از اطلاعات بدست آمده از مجموعه نمونه­هاي آموزشی، از فضای ویژگی­ها[5] به مجموعه برچسب دسته­ها نگاشتی بدست می آید که بر اساس آن، نمونه­های بدون برچسب به یکی از دسته­ها نسبت داده می­شود.

در مسائل دسته­بندی، هر نمونه توسط یک بردار ویژگی[6] به صورت X=<x1 , x2 ,… xm> معرفی می­شود که نشان دهنده­ی مجموعه مقادیر ویژگی­های نمونه­ی­ مربوطه است. بر اساس این بردار، نمونه­ی ­ X دارای m خصوصیت یا ویژگی است. این ویژگی­ها می­توانند مقادیر عدد صحیح، اعشاری ویا مقادیر نامی[7] به خود اختصاص بدهند. همچنین این نمونه دارای یک برچسب C است که معرف دسته­ای­ است که نمونه­ی­ X به آن تعلق دارد.

تفاوت روش­ها دسته­بندی در چگونگی طراحی نگاشت است. در بعضی از آن­ها با بهره گرفتن از داده­های آموزشی مدلی ایجاد می­شود که بر اساس آن فضای ویژگی­ها به قسمت­های مختلف تقسیم می­شود که در آن، هر قسمت نشان دهنده­ی یک دسته است. در این گونه روش­های دسته­بندی از مدل برای پیش­بینی دسته­ی­ نمونه بدون برچسب استفاده شده و از نمونه­­های آموزشی به طور مستقیم استفاده نمی شود. يک نمونه از این دسته­بندها، دسته­بندهاي احتمالي[8] مي­باشد. این گونه الگوريتم­ها، از استنتاج آماري براي پيدا کردن بهترين دسته استفاده مي­کنند؛ برخلاف ساير دسته­بند­ها که فقط بهترين کلاس را مشخص مي­کنند الگوريتم­هاي احتمالي به ازاي هر دسته موجود يک احتمال را به عنوان تعلق نمونه به آن مشخص مي­کنند و کلاس برنده، بر اساس بيشترين احتمال انتخاب مي­شود. روش­هاي احتمالي در يادگيري ماشين معمولا با نام الگوريتم­هاي آماري نيز شناخته مي­شوند. در گروهی دیگر از روش­های دسته بندی، نمونه براساس خود مجموعه نمونه­ها و بدون ساختن مدل، به پیش­بینی دسته­ی نمونه مورد نظر می­پردازد. به این گونه الگوریتم های دسته­بندی، نمونه- بنیاد[9] گفته می­شود.

تاکنون الگوريتم­هاي متفاوتی به عنوان دسته­بند ارائه شده­اند. از جمله­ی­ آن­ها مي­توان به الگوریتم نزدیک ترین همسایه­ها[10] [1] ، دسته­بند بیز[11][2]، ماشین بردار پشتیبان[3] و شبکه عصبی[12][4] اشاره کرد.

  • ارزيابي دسته­بند

اولین موضوعی که در مورد هر الگوریتم مورد توجه قرار می­گیرد، کارایی و دقت آن الگوریتم است. در هوش مصنوعی، معیار­های متفاوتی وجود دارند که در مسائل مختلف و زیر شاخه­های این علم استفاده می­شود. در مورد کارایی یک دسته­بند­، به عنوان یکی از مسائل اصلی هوش مصنوعی، روش­های متنوعی وجود دارد که در این قسمت بررسی شده­اند.

معیار کارايي نظر­گرفته شده برای یک دسته­بند، ارتباط مستقيمي با کاربرد و ضمینه کار خاص آن دسته­بند دارد. بنابراين در مسائل متفاوت، ممکن است معیار­های مختلفی برای اندازه­گیری کارایی الگوریتم در نظر­گرفته شود. همچنین همان طور که مشخص است، يک دسته­بند که بتواند براي همه مسائل موجود بهترين جواب را ارائه دهد، وجود ندارد.

در بررسی آماری کارایی یک دسته­بند، از یک مجموعه که شامل تعداد مشخصی نمونه­ی­ آموزشی دارای برچسب است استفاده می­شود. برای این کار، قسمتی از این نمونه­ها و یا تمام مجموعه،­ به عنوان مجموعه آموزشی[13]، در اختیار دسته­بند برای آموزش قرار می­گیرد. پس از آموزش، دسته بند به وسیله­ی­ زیر­مجموعه­ای­ از نمونه­ها، به عنوان نمونه­های­ آزمایشی، محک زده می­شود. نمونه­ها­ی موجود در مجموعه­ی­ آزمایشی، بسته به نوع آزمون کارایی، می­تواند عضو مجموعه آموزشی بوده و یا متفاوت با آن باشند.

نرخ دسته­بندی[14] یا صحت[15] پرکاربردترین و ساده­ترین معیار اندازه­گیری کارایی هر دسته­بند است. این معیار برابر است با نسبت تعداد نمونه­های درست دسته­بندی شده به تعداد کل نمونه­ها. براساس این تعریف، نرخ خطای دسته­بندی از ارتباط زیر بدست می­آید:

 مقادير دقت[16] و بازخواني[17] نیز معيارهاي مناسبي براي ارزيابي دسته­بندها مي­باشند. که اخيرا براي ارزيابي رقابت[18] بين اشتباه-مثبت[19] و درست-مثبت[20] استفاده مي­شود. در ادامه اين معيار­ها معرفي مي­شود.

  • معياردقت : احتمال مثبت بودن نمونه­هايي که مثبت اعلام شده­اند.

                  معيار بازخواني : احتمال مثبت اعلام کردن نمونه­هاي دسته مثبت.

   معيار اختصاص[21]: احتمال منفي اعلام کردن  نمونه­هاي دسته منفي.

که در این معیارها، دسته مثبت، دسته مورد بررسی است و دسته منفی به سایر دسته­ها گفته می­شود.

  • تصدیق متقابل[22]

يک روش براي ارزيابي آماري دسته­بند، تصدق متقابل[5] مي­باشد. در اين تکنيک براي ارزيابي کارايي دسته­بند، نمونه­ها را به صورت تصادفي به دو گروه که مکمل يکديگر هستند، تقسيم مي­کنند. با يک گروه سيستم را آموزش داده و با گروه ديگر سيستم آموزش ديده را مورد آزمايش قرار مي­دهند. با این کار از تطبیق بیش از حد[23] مدل بر روي داده­هاي آموزشي جلوگيري می­شود و نتایج بدست آمده از ارزیابی، دارای درجه اطمینان بیشتر خواهد بود. براي اطمینان بیشتر از نتایج، تصديق متقابل در چندين مرحله صورت تکرار شده و در هر مرحله، از تقسیم­بندي متفاوتي براي نمونه­ها استفاده مي­شود. در پایان از نتایج تمامی تکرار آزمایش­ها میانگین­گیری صورت می­گیرد.

در ادامه روش­هاي مختلف تطبيق متقابل توضيح داده مي­شود.

  • تصدیق زیر گروه تصادفی[24]: در اين روش، نمونه­ها به صورت تصادفي به دو گروه آموزشي[25] و آزمايشي[26] تقسيم مي­شوند. سپس دسته­بند به وسیله­ی­ نمونه­هاي آموزشي، آموزش داده مي­شود و با بهره گرفتن از مجموعه دیگر آزمايش شده و کارایی محاسبه مي­شود. اين عمليات چندين بار انجام مي­گیرد و در نهايت ميانگين آن­ها به عنوان کارايي دسته­بند ارائه مي­شود. با توجه به تصادفي انتخاب شدن مجموعه­هاي آموزشي و آزمايشي، مهم­ترين مشکل اين روش امکان عدم انتخاب بعضي از نمونه­ها به عنوان عضو یکی از دو گروه و یا انتخاب بيش از يک بار بعضي از نمونه­ها مي­باشد.
  • تصدیق متقابل k قسمت[27]: در روش ابتدا مجموعه نمونه­ها به K دسته تقسيم مي­شوند. در هر مرحله نمونه­های k-1 دسته به عنوان مجموعه آموزشی در نظر گرفته مي­شود و با بهره گرفتن از يک دسته دیگر کارايي سيستم دسته­بند ارزيابي مي­شود. در نهايت کارايي سيستم برابر با ميانگين کارايي در همه مراحل مي­شود. در اين روش از همه نمونه­ها برای آموزش و آزمایش استفاده مي­شود.
  • تصدیق یکی در مقابل بقیه[28]: یک روش دیگر، تصدیق یکی در مقابل بقیه است. در اين روش، هر نمونه يک بار به عنوان نمونه آزمايشي انتخاب مي­شود و از ساير نمونه­­ها برای آموزش استفاده مي­شوند. این روش بر روی تمامی نمونه­ها انجام می­شود. در پایان، کارایی الگوریتم برابر نسبت تعداد نمونه­های درست دسته­بندی شده به کل است.
    • الگوریتم نزدیک­ترین همسایه

يکي از الگوریتم­هاي معروف دسته­بندي، الگوریتم نزدیک همسایه است؛ با این که از معرفی آن چندین دهه می­گذرد، این روش همچنان محبوب بوده و کاربرد بسیاری در مسائل مختلف دارد. دلیل این موضوع سادگی پیاده­سازی و کارایی بالا این روش است. به علاوه، این الگوریتم را به سادگی می­توان در مسائل مختلف به کار برد. الگوریتم نزدیک­ترین همسایه از یک قانون بسیار ساده در عمل دسته­بندی استفاده می­کند. نمونه­هایی که شباهت بیشتری با یکدیگر دارند(در فضای ویژگی­ها در نزدیکی یکدیگر قرار گرفته­اند)، به احتمال بالا در یک دسته قرار دارند. بر طبق این، در الگوریتم نزدیک­ترین­ همسایه، برای بدست آوردن دسته­ی­ نمونه­ی­ پرس­و­جو شده[29]، بر اساس یک معیار شباهت(تفاوت)[30]، نزدیک­ترین­ نمونه، از مجموعه­ی­ نمونه­های آموزشی تعیین می­شود. سپس الگوریتم دسته­ی­ این نمونه را به عنوان دسته­ی­ نمونه­ی پرس­و­جو شده اعلام می­کند.

به عنوان مثال، شکل 1 نحوه بدست آوردن دسته­ی نمونه­ی­ پرس­وجو شده را توسط الگوریتم نزدیک­ترین­ همسایه، در یک فضای ویژگی دو بعدی و در مسئله­ای­ با سه دسته نمایش می­دهد. در این مثال، از معیار فاصله اقلیدسی برای بدست آوردن نزدیک­ترین همسایه استفاده شده است.

تعداد صفحه :63

قیمت :14700 تومان

بلافاصله پس از پرداخت لینک دانلود فایل در اختیار شما قرار می گیرد

و در ضمن فایل خریداری شده به ایمیل شما ارسال می شود.

:        ****       serderehi@gmail.com

در صورتی که مشکلی با پرداخت آنلاین دارید می توانید مبلغ مورد نظر برای هر فایل را کارت به کارت کرده و فایل درخواستی و اطلاعات واریز را به ایمیل ما ارسال کنید تا فایل را از طریق ایمیل دریافت کنید.

***  **** ***

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