نتایج آزمایشات نشان داده است که ترکیب چندین دستهبند[1] میتواند کارایی الگوریتمهای متنوع را بالا ببرد. روشهای تصمیمگیری دستهجمعی[2] بسیاری ارائه شدهاند که با استفاده از آنها، خطای روشهای مختلف دستهبندی[3] کاهش یافته است. با این حال، این گونه روشها نتوانستهاند کارایی الگوریتم نزدیکترین همسایه[4] را افزایش دهند. در این پایاننامه یک روش تصمیمگیری دستهجمعی ارائه شده است تا با استفاده از ترکیب وزندار چندین دستهبند، کارایی را بهبود بدهد. در این روش هر کدام از این دستهبندها یک دستهبند نزدیکترین همسایه است که تنها از زیر مجموعهای از مجموعه ویژگیها[5] نمونهها استفاده میکند. در ادامه، الگوریتم به هر کدام از آنها یک وزن اختصاص میدهد و در نهایت از یک مکانیسم رایگیری وزنی[6] برای تعیین خروجی مدل دستهجمعی استفاده می کند. فهرست مطالب عنوان صفحهفصل اول1مقدمه11-1- مقدمه21-2- روشهای دستهبندی31-3- ارزيابي دستهبند41-4- تصدیق متقابل61-5- الگوریتم نزدیکترین همسایه71-7- سر فصلها9فصل دوم10الگوریتم نزدیکترن همسایه و روشهای موجود برای بهبود آن102-1-الگوریتم نزدیکترین همسایه112-2- محدودیتهای روش نزدیکترین همسایه142-3- مروری بر راهکارهای ارائه شده در گذشته برای بهبود الگوریتم نزدیکترین همسایه15فصل سوم18روشهای تصمیمگیری دستهجمعی183-1- مقدمه193-2- روشهای متفاوت برای ایجاد یک تصمیمگیر دستهجمعی213-3- ساختارهای مختلف در روش تصمیمگیری دستهجمعی223-4- رایگیری بین دستهبندها233-5- معرفی چند روش تصمیمگیری دستهجمعی پرکاربرد24فصل چهارم28روش پیشنهادی برای دستهجمعی کردن الگوریتم نزدیکترین همسایه284-1- مقدمه294-2- ایدهی اصلی304-3- دستهجمعی کردن مجموعه دستهبندهای وزندار نزدیکترین همسایه31فصل پنجم39نتايج آزمایشات پياده سازي و نتیجهگیری395-1- نتایج40فصل ششم45نتیجهگیری45فهرست منابع48Abstract1 فهرست جدولها عنوان صفحه جدول 134جدول 238جدول 341جدول 442جدول 543جدول 644 فهرست شکلها عنوان صفحه شکل 1.8شکل 2.20شکل 3.22شکل 4.23شکل 5.32 فصل اول 1-1- مقدمهدر دنیای امروزی حجم اطلاعات دیجیتالی به صورت روز افزونی در حال افزایش است. در همین راستا، به جهت مدیریت و بررسی علمی این اطلاعات، نیاز به پردازش هوشمندانه و خودکار این اطلاعات بیش از پیش احساس می شود.یکی از مهم ترین این پردازش ها که در فناوری اطلاعات و ارتباطات مورد نیاز است، دستهبندی خودکار این اطلاعات می باشد. دسته بندی در مسائل متنوعی در فناوری اطلاعات به کار گرفته می شود، در مسائلی مانند امنیت اطلاعات، شناسایی نفوزگری در شبکه، دسته بندی کاربران بر اساس اطلاعات شخصی، پردازش تصویر و در واقع شناسایی هر گونه الگو بر اساس نمونهها و اطلاعات پیشین. این پردازش می تواند دسته[7]ی نمونههای جدید که به مجموعه اطلاعات اضافه می شود را پیش بینی نماید. از این رو در هوش مصنوعی توجه خاصی به توسعه انواع روشهای دستهبندی هوشمند و خودکار شده است. 1-2- روشهای دستهبندیدستهبندی یکی از مهمترین شاخههاي يادگيري ماشين[8] است. دستهبندی به پیشبینی برچسب دسته[9] نمونه[10] بدون برچسب، بر اساس مجموعه نمونههای آموزشی برچسبدار (که قبلا به با کمک يک کارشناس دستهبندي شدهاند) گفته میشود. درواقع دستهبندی روشي است که هدف آن، گروهبندي اشيا به تعدادي دسته یا گروه ميباشد. در روشهاي دستهبندی، با استفاده از اطلاعات بدست آمده از مجموعه نمونههاي آموزشی، از فضای ویژگیها[11] به مجموعه برچسب دستهها نگاشتی بدست می آید که بر اساس آن، نمونههای بدون برچسب به یکی از دستهها نسبت داده میشود.در مسائل دستهبندی، هر نمونه توسط یک بردار ویژگی[12] به صورت X=<x1 , x2 ,… xm> معرفی میشود که نشان دهندهی مجموعه مقادیر ویژگیهای نمونهی مربوطه است. بر اساس این بردار، نمونهی X دارای m خصوصیت یا ویژگی است. این ویژگیها میتوانند مقادیر عدد صحیح، اعشاری ویا مقادیر نامی[13] به خود اختصاص بدهند. همچنین این نمونه دارای یک برچسب C است که معرف دستهای است که نمونهی X به آن تعلق دارد.تفاوت روشها دستهبندی در چگونگی طراحی نگاشت است. در بعضی از آنها با استفاده از دادههای آموزشی مدلی ایجاد میشود که بر اساس آن فضای ویژگیها به قسمتهای مختلف تقسیم میشود که در آن، هر قسمت نشان دهندهی یک دسته است. در این گونه روشهای دستهبندی از مدل برای پیشبینی دستهی نمونه بدون برچسب استفاده شده و از نمونههای آموزشی به طور مستقیم استفاده نمی شود. يک نمونه از این دستهبندها، دستهبندهاي احتمالي[14] ميباشد. این گونه الگوريتمها، از استنتاج آماري براي پيدا کردن بهترين دسته استفاده ميکنند؛ برخلاف ساير دستهبندها که فقط بهترين کلاس را مشخص ميکنند الگوريتمهاي احتمالي به ازاي هر دسته موجود يک احتمال را به عنوان تعلق نمونه به آن مشخص ميکنند و کلاس برنده، بر اساس بيشترين احتمال انتخاب ميشود. روشهاي احتمالي در يادگيري ماشين معمولا با نام الگوريتمهاي آماري نيز شناخته ميشوند. در گروهی دیگر از روشهای دسته بندی، نمونه براساس خود مجموعه نمونهها و بدون ساختن مدل، به پیشبینی دستهی نمونه مورد نظر میپردازد. به این گونه الگوریتم های دستهبندی، نمونه- بنیاد[15] گفته میشود.تاکنون الگوريتمهاي متفاوتی به عنوان دستهبند ارائه شدهاند. از جملهی آنها ميتوان به الگوریتم نزدیک ترین همسایهها[16] [1] ، دستهبند بیز[17][2]، ماشین بردار پشتیبان[3] و شبکه عصبی[18][4] اشاره کرد.
روش تصمیم گیری دسته جمعی جهت بهبود عملکرد الگوریتم نزدیک ترین همسایه WORD
نتایج آزمایشات نشان داده است که ترکیب چندین دستهبند[1] میتواند کارایی الگوریتمهای متنوع را بالا ببرد. روشهای تصمیمگیری دستهجمعی[2] بسیاری ارائه شدهاند که با استفاده از آنها، خطای روشهای مختلف دستهبندی[3] کاهش یافته است. با این حال، این گونه روشها نتوانستهاند کارایی الگوریتم نزدیکترین همسایه[4] را افزایش دهند. در این پایاننامه یک روش تصمیمگیری دستهجمعی ارائه شده است تا با استفاده از ترکیب وزندار چندین دستهبند، کارایی را بهبود بدهد. در این روش هر کدام از این دستهبندها یک دستهبند نزدیکترین همسایه است که تنها از زیر مجموعهای از مجموعه ویژگیها[5] نمونهها استفاده میکند. در ادامه، الگوریتم به هر کدام از آنها یک وزن اختصاص میدهد و در نهایت از یک مکانیسم رایگیری وزنی[6] برای تعیین خروجی مدل دستهجمعی استفاده می کند. فهرست مطالب عنوان صفحهفصل اول1مقدمه11-1- مقدمه21-2- روشهای دستهبندی31-3- ارزيابي دستهبند41-4- تصدیق متقابل61-5- الگوریتم نزدیکترین همسایه71-7- سر فصلها9فصل دوم10الگوریتم نزدیکترن همسایه و روشهای موجود برای بهبود آن102-1-الگوریتم نزدیکترین همسایه112-2- محدودیتهای روش نزدیکترین همسایه142-3- مروری بر راهکارهای ارائه شده در گذشته برای بهبود الگوریتم نزدیکترین همسایه15فصل سوم18روشهای تصمیمگیری دستهجمعی183-1- مقدمه193-2- روشهای متفاوت برای ایجاد یک تصمیمگیر دستهجمعی213-3- ساختارهای مختلف در روش تصمیمگیری دستهجمعی223-4- رایگیری بین دستهبندها233-5- معرفی چند روش تصمیمگیری دستهجمعی پرکاربرد24فصل چهارم28روش پیشنهادی برای دستهجمعی کردن الگوریتم نزدیکترین همسایه284-1- مقدمه294-2- ایدهی اصلی304-3- دستهجمعی کردن مجموعه دستهبندهای وزندار نزدیکترین همسایه31فصل پنجم39نتايج آزمایشات پياده سازي و نتیجهگیری395-1- نتایج40فصل ششم45نتیجهگیری45فهرست منابع48Abstract1 فهرست جدولها عنوان صفحه جدول 134جدول 238جدول 341جدول 442جدول 543جدول 644 فهرست شکلها عنوان صفحه شکل 1.8شکل 2.20شکل 3.22شکل 4.23شکل 5.32 فصل اول 1-1- مقدمهدر دنیای امروزی حجم اطلاعات دیجیتالی به صورت روز افزونی در حال افزایش است. در همین راستا، به جهت مدیریت و بررسی علمی این اطلاعات، نیاز به پردازش هوشمندانه و خودکار این اطلاعات بیش از پیش احساس می شود.یکی از مهم ترین این پردازش ها که در فناوری اطلاعات و ارتباطات مورد نیاز است، دستهبندی خودکار این اطلاعات می باشد. دسته بندی در مسائل متنوعی در فناوری اطلاعات به کار گرفته می شود، در مسائلی مانند امنیت اطلاعات، شناسایی نفوزگری در شبکه، دسته بندی کاربران بر اساس اطلاعات شخصی، پردازش تصویر و در واقع شناسایی هر گونه الگو بر اساس نمونهها و اطلاعات پیشین. این پردازش می تواند دسته[7]ی نمونههای جدید که به مجموعه اطلاعات اضافه می شود را پیش بینی نماید. از این رو در هوش مصنوعی توجه خاصی به توسعه انواع روشهای دستهبندی هوشمند و خودکار شده است. 1-2- روشهای دستهبندیدستهبندی یکی از مهمترین شاخههاي يادگيري ماشين[8] است. دستهبندی به پیشبینی برچسب دسته[9] نمونه[10] بدون برچسب، بر اساس مجموعه نمونههای آموزشی برچسبدار (که قبلا به با کمک يک کارشناس دستهبندي شدهاند) گفته میشود. درواقع دستهبندی روشي است که هدف آن، گروهبندي اشيا به تعدادي دسته یا گروه ميباشد. در روشهاي دستهبندی، با استفاده از اطلاعات بدست آمده از مجموعه نمونههاي آموزشی، از فضای ویژگیها[11] به مجموعه برچسب دستهها نگاشتی بدست می آید که بر اساس آن، نمونههای بدون برچسب به یکی از دستهها نسبت داده میشود.در مسائل دستهبندی، هر نمونه توسط یک بردار ویژگی[12] به صورت X=<x1 , x2 ,… xm> معرفی میشود که نشان دهندهی مجموعه مقادیر ویژگیهای نمونهی مربوطه است. بر اساس این بردار، نمونهی X دارای m خصوصیت یا ویژگی است. این ویژگیها میتوانند مقادیر عدد صحیح، اعشاری ویا مقادیر نامی[13] به خود اختصاص بدهند. همچنین این نمونه دارای یک برچسب C است که معرف دستهای است که نمونهی X به آن تعلق دارد.تفاوت روشها دستهبندی در چگونگی طراحی نگاشت است. در بعضی از آنها با استفاده از دادههای آموزشی مدلی ایجاد میشود که بر اساس آن فضای ویژگیها به قسمتهای مختلف تقسیم میشود که در آن، هر قسمت نشان دهندهی یک دسته است. در این گونه روشهای دستهبندی از مدل برای پیشبینی دستهی نمونه بدون برچسب استفاده شده و از نمونههای آموزشی به طور مستقیم استفاده نمی شود. يک نمونه از این دستهبندها، دستهبندهاي احتمالي[14] ميباشد. این گونه الگوريتمها، از استنتاج آماري براي پيدا کردن بهترين دسته استفاده ميکنند؛ برخلاف ساير دستهبندها که فقط بهترين کلاس را مشخص ميکنند الگوريتمهاي احتمالي به ازاي هر دسته موجود يک احتمال را به عنوان تعلق نمونه به آن مشخص ميکنند و کلاس برنده، بر اساس بيشترين احتمال انتخاب ميشود. روشهاي احتمالي در يادگيري ماشين معمولا با نام الگوريتمهاي آماري نيز شناخته ميشوند. در گروهی دیگر از روشهای دسته بندی، نمونه براساس خود مجموعه نمونهها و بدون ساختن مدل، به پیشبینی دستهی نمونه مورد نظر میپردازد. به این گونه الگوریتم های دستهبندی، نمونه- بنیاد[15] گفته میشود.تاکنون الگوريتمهاي متفاوتی به عنوان دستهبند ارائه شدهاند. از جملهی آنها ميتوان به الگوریتم نزدیک ترین همسایهها[16] [1] ، دستهبند بیز[17][2]، ماشین بردار پشتیبان[3] و شبکه عصبی[18][4] اشاره کرد.