بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
بهبود عملکرد طبقه بندي KNN با استفاده از روش وزندهي ويژگيها
چکيده
روش KNN يک روش ساده و پرکاربرد در تشخيص الگو است که جهت طبقه بندي داده ها بر اساس نمونه هاي نزديک به هم در فضاي ويژگي به کار ميرود. عملکرد طبقه بندي KNN، شديدا به نحوه محاسبه فاصله بين نمونه ها وابسته است . در همين راستا روش هاي مختلفي جهت اندازه گيري فاصله ارائه شده است که ميتوان از موفق ترين آنها به روش هاي مبتني بر يادگيري معيار فاصله با استفاده از بهينه سـازي اشـاره کرد. در اين مقاله يک الگوريتم سريع جهت وزندهي ويژگيها ارائه ميشود که هدف آن کاهش فاصله درون کلاسـي و افزايش فاصـله بين کلاسـي محلي اسـت و برخلاف روش هاي مبتني بر بهينه سازي، محاسبات بسيار کمتري دارد. نتايج پياده سازي و مقايسه روش پيشنهادي با روش هاي موفق گذشته بيانگر بهبود چشمگير عملکرد طبقه بندي است .
کلمات کليدي
طبقه بندي K نزديک ترين همسايگي، وزندهي ويژگيها، يادگيري معيار فاصله ، برنامه ريزي خطي .
١- مقدمه
يکي از قـديميترين و ســـاده ترين روش هـاي طبقـه بنـدي، روش K نزديـک ترين همســـايگي (KNN)1 اســـت [١]. اين روش هر نمونـه آزمايشــي را بر اســاس برچســب اکثريت K نزديک ترين همســايه آن طبقه بندي مي کند. روش KNN نه تنها ســـاده ترين طبقه بندي کننده غيرخطي اسـت بلکه تصميم گيري آن با بررسي نزديک ترين همسايه ها قابل تفسير است [٢]. روش KNN، اغلب به نتايج قابل قبولي مي رسد و از ترکيب مناسـب آن با دانسـته هاي پيشـين ، پيشـرفت چشمگيري حاصــل مي شــود [٣، ٤ و ٥]. عملکرد طبقه بندي KNN، به دليل نوع تصـميم گيري آن ، بستگي زيادي به نحوه محاسبه فاصله بين نمونه هاي مختلف دارد. اغلب پياده سازيهاي KNN، هنگامي که در مورد داده ها دانش پيشـيني موجود نباشــد، از فاصـله اقليدســي اســتفاده مي کنند. متاسفانه فاصله اقليدسي نه تنها بر اساس اهميت ابعاد داده نيست بلکه کاملا به مقياس بندي دلخواه ابعاد بســتگي دارد. همچنين از هر نتيجه آماري که مي توان از داده هاي آموزشي تخمين زد، چشم پوشي مي کند.
در نتيجـه پژوهش هاي فراواني با ارائه روش هاي مناســـب اندازه گيري فاصـله نمونه هاي آموزشي ، سعي در بهبود طبقه بندي KNN داشته اند [٢، ٦، ٧ و ٨]. اين مسـاله ، يادگيري معيار فاصله ٢ نام دارد. در [٨ و ٩] نشـان داده شده است که حتي يک تبديل ساده خطي هم ممکن است به بهبود چشـمگير در طبقه بندي KNN منجر شود. در اين مقاله ، يک روش جـديـد وزندهي ويژگيها جهت بهبود عملکرد روش KNN ارائه مي شــود که در مقايســه با روش هاي ديگر از دقت و ســرعت بالاتر و پياده سـازي سـاده تري برخوردار است . اين روش پس از نرماليزه کردن داده ها، به ازاي هر بعد و براي هر داده آموزشــي يک بازه هدف تعيين نموده و بر اسـاس تعداد نمونه هاي با برچسـب يکسان و متفاوت در آن بازه ها به هر بعد يک وزن نســبت مي دهد. نتايج پياده ســازي الگوريتم پيشـنهادي و مقايسـه آن با ساير روش ها، بهبود عملکرد طبقه بندي را نشان ميدهد.
٢- يادگيري معيار فاصله
مســـاله یادگیری معیار فاصـــله با یافتن ماتریس تبدیل W ســـعی در بـهـیـنــهســــازی فــاصـــلــه مــاهــالانـوبیس برای داده آموزشـــی جهت کاهش خطاي طبقه بندي دارد:
مســاله وزندهي ويژگيها حالت خاصــي از مســاله يادگيري معيار فاصـله اسـت که ماتريس W قطري فرض ميشود. در اين حالت فاصله بين دو داده نمونه X و ′X به فاصله وزن دار اقليدسي تبديل ميشود:
اگر داده داراي ويژگيهاي نامربوط به طبقه بندي باشــد، وزن اين ابعاد به صفر ميل ميکند و درنتيجه ابعاد داده کاهش مييابد. اخيرا دو الگوريتم LMNN و MDM بـه عنوان دو روش موفق بهبود عملکرد
KNN مطرح شده اند که با تغيير بهينه مقياس ابعاد، خطاي طبقه بندي الگوريتم KNN را کـاهش ميدهنـد [٢]. روش LMNN يـک روش شناخته شده در يادگيري معيار فاصله و روش MDM يک روش موفق در وزندهي ويژگيها است . در اين مقاله به منظور ارزيابي عملکرد روش پيشنهادي، اين دو روش نيز تشريح و به کار گرفته ميشوند.
٢-١- روش LMNN
روش نزديـک ترين همســـايه با حاشـــيه بزرگ (LMNN)3 به منظور افزايش عملکرد طبقـه بنـدي، نقاط مربوط به کلاس مشـــابه را به هم نزديـک و نقـاط مربوط به کلاس هاي متفاوت را از هم دور ميکند. به عبارت دقيق تر K نقطه نزديک تر به هر نقطه داده بايد برچسب يکسان داشته باشند. اگر K نقطه نزديک تر به نقطه � که داراي کلاس مشابه
�
با آن باشند را همسايه هاي هدف بناميم و با � نشان دهيم و هر نقطه
�
با برچسـب متفاوت که از دورترين نقطه هدف (بعلاوه مقداري حاشيه ) نزديک تر باشــد را نقطه فريب بناميم و با نشــان دهيم ، آنگاه به بايد يک بهينه ســازي همزمان روي نقاط داده ، همســايگيهاي هدف و نقاط فريب صورت گيرد و فاصله بين تمام نقاط مربوط به هر کلاس نيز کمينه گردد. اين بهينه سازي توسط برنامه ريزي زير انجام مي شود:
است و
نماد به اين معني اسـت که همسايگي هدف تابعي اسـت که در صورت يکسان بودن برچسب برابر يک و در غير اينصـورت برابر صفر است . پارامتر μ براي وزندهي دو جمله و متغير کمکي اســت . با محدود کردن ماتريس به يک ماتريس قطري مســاله بهينه ســازي به يک برنامه ريزي خطي ٤ تبديل ميشــود.
مساله برنامه ريزي خطي سعي در يافتن مقدار کمينه يک تابع با در نظر گرفتن شرايط زير را دارد [٦ و ١٢-١٠]:
که بردار و ماتريس هستند.
٢-٢- روش MDM
روش کمينه ســازي بيشــترين فاصــله (MDM)٥ يک روش وزندهي ويژگي اســـت کـه بر خلاف روش LMNN بـا هدف ترکيب با KNN طراحي نشـده اسـت و پارامترهاي کمتري جهت بهينه سازي دارد. اين روش بــه دلـيــل عمومي بودن هــدف ، براي مرحلــه پيش پردازش طبقـه بنـديکننـده هـاي ديگر نيز مناســـب اســـت . اين روش همانند LMNN سـعي در کمينه سازي فاصله نقاط با کلاس يکسان دارد ولي فقط همسـايگيهاي محلي در نظر گرفته نميشـوند و بيشترين فاصله بين تمام جفت هاي نقاط داده با کلاس يکسان کمينه ميشود در حالي که فاصـله بين جفت هاي نقاط داده با کلاس متفاوت ، بزرگ تر ميشود.
اين بهينه سازيها را ميتوان در مساله برنامه ريزي خطي زير بيان کرد:
که برچسب داده هاي هستند. در مقايسه با LMNN عليرغم افزايش تعداد شـرط ها متناسب با مربع تعداد نقاط داده در اين مساله برنامه ريزي خطي، تعداد پارامترهاي بهينه سازي که همان وزن هاي �� هســـتند، به شـــدت کاهش مييابد. همچنين اين مساله بهينه سازي بدون نياز به متغير کمکي، همواره جواب دارد [٢].
٣- روش وزندهي ويژگيها براساس فواصل محلي
روش پيشـنهاد شده در اين مقاله يک روش وزندهي ويژگيها است که هدف آن کاهش فاصــله درون کلاســي و افزايش فاصــله بين کلاســي محلي اســـت . برخلاف روش هـاي LMNN و MDM اين روش يـک مساله بهينه سازي نيست و در نتيجه بار محاسباتي بسيار کمتري دارد.
الگوريتم زير مراحل کار را نشان ميدهد:
١- نرماليزه کردن ابعاد داده : محاسـبه مقدار کمينه و بيشينه هر بعد و تغيير مقياس به بازه [١ و ٠].
