بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
ررسي عملکرد الگوريتم هاي بهينه سازي در طبقه بندي ماشين بردار پشتيبان در تصاويرسنجش ازدور
چکيده
تمايل به داشتن اطلاعات مکاني دقيق ، صحيح و بهنگام از منابع کشور در يک پايگاه داده جامع مکان مرجع همواره رو به رشد است . با گسترش علوم فتوگرامتري و سنجش ازدور، طيف وسيعي از اطلاعات مکاني در دسترس علوم مختلف قرارگرفته است . طبقه بندي يکي از پرکاربردترين روش هاي استخراج اطلاعات از تصاوير سنجش ازدور ميباشد. تعيين روش مناسب طبقه بندي امري مهم و چالش برانگيز است که منجر به بهبود نتايج نهايي ميشود. هدف اصلي اين مقاله ، بهينه سازي طبقه بندي ماشين بردار پشتيبان در تصاوير ابرطيفي سنجش ازدور ميباشد. در طبقه بندي ماشين بردار پشتيبان در مسائل غيرخطي، پارامترهايي براي توابع کرنل و ترم تنظيم کننده خطا مشخص ميشود که به منظور افزايش دقت طبقه بندي و افزايش اعتمادپذيري به نتايج ، ميتوان از الگوريتم هاي بهينه سازي براي تعيين اين پارامترها استفاده نمود. از طرفي انتخاب باندهاي مناسب تأثير بسزايي در بهبود نتايج طبقه بندي دارد. اين دو عامل سبب شده است که از الگوريتم هاي بهينه سازي در اين مقاله به منظور تعيين مقادير بهينه اين پارامترها و تعيين ويژگيهاي بهينه استفاده شود که منجر به اتوماتيک سازي روند حل مسئله و افزايش ٥ درصدي دقت کلي طبقه بندي و افزايش ١٥ درصدي ضريب کاپا شده است .
کلمات کليدي: طبقه بندي ماشين بردار پشتيبان، انتخاب ويژگي، تعيين پارامترها، الگوريتم بهينه سازي ژنتيک ، الگوريتم بهينه سازي ازدحام ذرات.
١. مقدمه
با گسترش علوم فتوگرامتري و سنجش ازدور، اطلاعات مکاني با سرعت آمادهسازي و به روزرساني بيشتري در دسترس مديران و برنامه ريزان شهري به منظور اخذ تصميمات کلان و راهبردي و مديريت منابع کشور قرارگرفته است . طبقه بندي يکي از پرکاربردترين روشها در استخراج اطلاعات از تصاوير سنجش ازدور ميباشد که تعيين روش مناسب آن، امري مهم و چالش برانگيز است که منجر به بهبود نتايج نهايي ميشود. طبقه بندي کلاس هاي مختلف عوارض شهري مانند ساختمان ها، راهها، پوشش گياهي و ... با قرار دادن پيکسل هايي با مشخصات طيفي يکسان در يک کلاس فراهم ميشود.
اين امر به منظور توليد نقشه هاي پوشش اراضي از عکس هاي هوايي يا تصاوير ماهوارهاي انجام ميشود [١]. رضا خاتمي در 1 سال ٢٠١٦ از بررسي نتايج ٢٦٦ مقاله چاپشده در مجلات معتبر سنجش ازدور، کارايي طبقه بندي ماشين بردار پشتيبان را نسبت به ساير روشهاي طبقه بندي به اثبات رسانده است [٢]. ازجمله مزاياي طبقه بندي SVM نسبت به ساير روشها ميتوان به آموزش نسبتا ساده، کارايي مناسب براي مسائل غيرخطي با تعداد نمونه کم و ابعاد بالا، قابليت تعميم پذيري مناسب [٣-٦] و حساسيت کمتر اين روش به چالش کار با داده هاي با ابعاد بالا٢[٧] اشاره نمود. در اين مقاله به دلايل فوق، از طبقه بندي SVM استفاده شده است . در طبقه بندي SVM در مواجه با مسائل غيرخطي، علاوه بر در نظر گرفتن ترم تنظيم کننده خطا، از توابع کرنل به منظور نگاشت از فضاي ويژگي با ابعاد پايين به فضاي ويژگي با ابعاد بالا استفاده ميشود؛ بنابراين در فضاي ويژگي با ابعاد بالا، مسئله خطي ميشود و امکان تفکيک پيکسل هاي تصويري در فضاي خطي فراهم ميشود. تعيين پارامترهاي کرنل مناسب اغلب به صورت سعي و خطا صورت مي رد که اين روش، زمان بر و هزينه بر ميباشد و در برخي موارد عدم اطمينان به نتايج به دست آمده را در بردارد.
تصاوير ابرطيفي يکي از محصولات سنجش ازدور است که محدوده طيفي فراواني از طول موجهاي مرئي تا مادون قرمز- طول موج کوتاه را در تعداد زيادي باندهاي طيفي باريک پوشش ميدهند. در طبقه بندي پوشش زمين ، اين حجم بالاي اطلاعات ميتواند باعث افزايش دقت تفکيک کلاس ها شود. عليرغم وجود تعداد زياد باندهاي طيفي، در صورت ناکافي بودن نمونه هاي آموزشي، طبقه بندي با چالش کار با داده هاي با ابعاد بالا مواجه ميشود [٨]. در اين حالت ، روش هاي آماري قديمي طبقه بندي نميتوانند نتايج مناسبي فراهم نمايند. در چند دهه اخير، الگوريتم هاي يادگيري ماشين به منظور بهبود فرآيند يادگيري اطلاعات توسعه دادهشدهاند [٩]. ازجمله اين الگوريتم ها ميتوان به شبکه عصبي مصنوعي [١٠]، درخت تصميم ي [١١, ١٢]، ماشين بردار پشتيبان [١٣-١٥] و الگوريتم هاي ژنتيک [١٦, ١٧] اشاره نمود. همچنين در تصاوير ابرطيفي، وابستگي باندهاي طيفي به يکديگر منجر به کاهش دقت طبقه بندي خواهد شد. يکي از پرکاربردترين روشها در زمينه ي شناسايي باندهاي مستقل ، استفاده از الگوريتم هاي بهينه سازي ميباشد [٣, ١٨-٢٠].
در اين مقاله با توجه به اهميت تصاوير ابرطيفي به دليل دارا بودن اطلاعات طيفي بالا و ضرورت بهينه سازي طبقه بندي SVM، بهينه سازي طبقه بندي SVM بر روي دو تصوير ابرطيفي هم در زمينه ي انتخاب باندهاي طيفي مستقل و هم در زمينه ي انتخاب پارامترهاي تابع کرنل و ترم تنظيم کننده خطا انجامشده است . سپس نتايج به دست آمده از طبقه بندي تصوير ابرطيفي با دادههاي چک مورد ارزيابي قرار مي رند.
٢. تئوري روش
طبقه بندي روشي پرکاربرد در استخراج اطلاعات از تصاوير سنجش ازدور ميباشد. به طورکلي روشهاي طبقه بندي در سنجش ازدور به دو گروه: نظارتشده و نظارتنشده تقسيم ميشوند [٢١]. در طبقه بندي نظارتنشده، تصوير سنجش ازدور به خوشه هايي بر اساس مقادير درجات خاکستري تصوير، بدون داده آموزشي يا دانش قبلي از تصوير، تقسيم ميشود [٢٢, ٢٣]. ازجمله روشهاي طبقه بندي نظارتنشده ميتوان به K-means [٢٤, ٢٥] و ISODATA٣ [٢٦] اشاره نمود. در طبقه بندي نظارتشده فرد خبره نمونه هاي آموزشي٤ با کلاس مشخص را براي هر کلاس تصويري انتخاب مينمايد و سپس ويژگيهاي طيفي هر پيکسل تصويري را با ويژگيهاي طيفي نمونه هاي آموزشي اخذشده مقايسه ميشود و سپس به پيکسل هاي تصويري برچسب اختصاص داده ميشود [٢٢]. ازجمله روشهاي طبقه بندي نظارتشده ميتوان به طبقه بندي بي يشنه شباهت ٥ [٢٧]، طبقه بندي کمترين فاصله از ميانگين ٦ [٢٨, ٢٩]، طبقه بندي فاصله ماهولونوبيس [٢٩, ٣٠] و طبقه بندي نزديک ترين همسايگي ٨ [٣١, ٣٢] و طبقه بندي SVM اشاره نمود.
٢-١. طبقه بندي ماشين بردار پشتيبان
طبقه بندي ماشين بردار پشتيبان اولين بار در سال ١٩٦٣ ميلادي توسط وپنيک ٩ به عنوان طبقه بنديکنندهي خطي ارائه گرديد [٣٣]. اين روش از پارامترهاي هندسي کلاسها به جاي پارامترهاي آماري، استفاده ميکند؛ بنابراين طبقه بندي SVM جزء دسته طبقه بندي غير پارامتريک ميباشد. ايده اصلي SVM يافتن فراصفحه بهينه براي جدا کردن دو کلاس با برچسب ١ و -١ با بيشترين حاشيه ١٠ جداسازي آن ميباشد. فرض کنيد n نمونه آموزشي موجود باشد که هر يک با (xb,yb) نشان داده ميشود،xi بردار ويژگي n بعدي و برچسب آن ميباشد. درصورتيکه دادهها به صورت خطي جدا پذير نباشند، دادهها با کرنلي به فضاي با ابعاد بالاتر منتقل ميشوند و فرا صفحه بهينه در آن فضا تعيين ميشود. بيشينه نمودن حاشيه بين دو کلاس معادل کمينه سازي اندازه w ميباشد که منجر به حل مسئله کمينه سازي مقيد ميشود که از رابطه (١) محاسبه ميگردد [٣٤].
که در رابطه فوق C ترم تنظيم کننده و ضريبي براي ايجاد تعادل بين نقاط خطادار از نمونه آموزشي و ساير نقاط است و به منظور در نظر گرفتن نويز موجود در داده و تداخل بين نمونه هاي آموزشي، از متغير استفاده ميشود که درجه طبقه بندي اشتباه داده Xi را اندازهگيري ميکند؛ بنابراين تابع تصميم ي بهينه طبق رابطه (٢) محاسبه ميشود.
در اين رابطه α ضرايب لاگرانژ ميباشد که در پروسه بهينه سازي محاسبه ميشود، nSV بردارهاي پشتيبان هستند که ضرايب لاگرانژ متناظر آنها بزرگتر از صفر است . اين دادههاي آموزشي، نزديک ترين نمونه ها به فرا صفحه هستند.
کرنل هاي متفاوتي به منظور نگاشت از فضايي با ابعاد پائين به ابعاد بالا وجود دارد[٤, ٣٤]. در اين مقاله از کرنل تابع پايه شعاعي به دليل مناسب بودن اين کرنل در مسائل ساده و غيرخطي و تقارن شعاعي [٥, ٣٥]، ارائه نتايج بهتر [٣٦, ٣٧] و تعداد پارامتر کم استفادهشده است (رابطه (٣)).
٢-٢. بهينه سازي
بهينه سازي بدين مفهوم است که در بين پارامترهاي يک تابع به دنبال مقاديري باشيم که تابع را کمينه يا بيشينه 12 مينمايند. کليه مقادير مناسب جهت اين امر را، راهحل هاي ممکن ١١ و بهترين مقدار از اين مقادير را راهحل بهينه مينامند. در اين مقاله ، با توجه به اينکه تابع هدف موردنظر براي بهينه سازي، خطاي طبقه بندي به ازاي داده هاي آموزشي و آزمايشي ميباشد؛ بنابراين مسئله بهينه سازي از نوع کمينه سازي تابع هدف ميباشد. الگوريتم هاي متعدد بهينه سازي توسط محققين ارائه شده است . در اين مقاله بنا بر دلايل ذکرشده در بخش (٢-٢-١) و (٢-٢-٢)، از الگوريتم هاي بهينه سازي ژنتيک ١٣ و ازدحام ذرات١٤ به منظور بهينه سازي طبقه بندي SVM استفاده شده است .
٢-٢-١. الگوريتم بهينه سازي ژنتيک
جان هالاند و دانشجويانش در اواخر دهه ي ١٩٦٠ با الهام گرفتن از ايدههاي بنيادين داروين و اصل تکامل طبيعي، الگوريتم ژنتيک را معرفي نمودند [٣٨, ٣٩]. اين الگوريتم با مجموعه اي (n) عضوي از راهحل هاي اوليه که معادل جمعيت اوليه است ، شروع ميشود. هر عضو از جمعيت کروموزوم ناميده ميشود که بيانگر يک راهحل مسئله است که به صورت تصادفي مقداردهي ميشوند و در تکرارهاي مختلف مطابق تابع هزينه ١٥ ارزيابي ميشوند. سپس از ميان کروموزوم هاي موجود، اعضائي از جمعيت به عنوان والد انتخاب ميشوند و فرزندهايي توليد ميکنند. همچنين به منظور جست وجوي 16 تصادفي در فضاي مسئله ، برخي از کروموزومها دچار جهش ميشوند؛ بنابراين کروموزومهاي جديدي با دو عمل ادغام و جهش ژني ١٧ به وجود مييند. کروموزوم هاي جديد با کروموزوم هاي قديمي ادغام ميشود و جمعيت بر اساس مقدار تابع هزينه مرتب سازي ميشود و کروموزوم ضعيف (کروموزومي که مقدار تابع هزينه آن زياد باشد) حذف ميشود و (n) کروموزوم اول از اين جمعيت ، به عنوان جمعيت نسل بعدي انتخاب ميشود. بعد از چندين تکرار، الگوريتم به سمت بهترين کروموزوم (بهترين راهحل ) هدايت ميشود که پاسخي بهينه از مسئله است و درواقع اولين کروموزوم از جمعيت مرتب شده بر اساس تابع هدف در آخرين تکرار، همان پاسخ بهينه مسئله ميباشد. فلوچارت الگوريتم ژنتيک در بخش (٣-٢) ارائه شده است .
از مزاياي اين الگوريتم ميتوان به ارائه يک راهحل بهينه با جست وجو در ميان تمام راهحل هاي ممکن ، مناسب براي مسائل با ابعاد بالا و عدم نياز به اطلاعات زياد در مورد مسئله اشاره نمود. همچنين اين الگوريتم از يک نقطه براي جست وجو استفاده نميکند بلکه از يک جمعيت از نقاط در يک زمان مشابه استفاده ميکند. به عبارتديگر الگوريتم ژنتيک يک روش جست وجوي عمومي است زيرا که به طور موازي نقاط زيادي را در فضاي جستجو (تمام راهحل هاي ممکن ) کاوش ميکند به همين دليل است که در اين روش از بهينه محلي جلوگيري ميشود [٤٠].
٢-٢-٢. الگوريتم ازدحام ذرات
الگوريتم ازدحام ذرات اولين بار توسط کندي ١٨ و ابرهارت١٩ از شبيه سازي رفتار اجتماعي پرندگان ارائه شد [٤١]. از مزاياي الگوريتم PSO ميتوان به قابليت فهم و پيادهسازي آسان [٤٢, ٤٣]، کارايي PSO در مقايسه با ساير الگوريتم هاي هوش مصنوعي [٤٤-٤٨]، تعداد کم پارامترهاي خود الگوريتم PSO [٦] اشاره نمود. اين الگوريتم از مجموعه اي از راه حل هاي ممکن تشکيل شده است که به آنها جمعيت گفته ميشود. هر راهحل (ذره) از مجموعه اي از پارامترها تشکيل شده است و معرف يک نقطه در فضاي چندبعدي مسئله است و به ازاي موقعيت ذره، تابع هدف محاسبه ميشود.
در اين الگوريتم هر ذره داراي حافظه اي به منظور ذخيرهسازي بهترين موقعيتي که در آن قرارگرفته است (بهترين موقعيت محلي ٢٠)، ميباشد. همچنين در هر بار تکرار الگوريتم ، حافظه اي به منظور ذخيره سازي بهترين موقعيت موجود در يک توده ذرات وجود دارد (بهترين موقعيت عمومي ٢١). هر ذره در فضاي جست وجو با سرعت تعيين شده با در نظر گرفتن موقعيت فعلياش، بهترين موقعيت محلي و بهترين موقعيت عمومي به سمت راه حل بهينه مسئله حرکت ميکند و موقعيت جديدي براي هر ذره محاسبه ميشود. به منظور محاسبه موقعيت جديد ذرات از رابطه (٤) و رابطه (٥) استفاده ميشود. اين روابط به ترتيب مربوط به به روزرساني سرعت و به روزرساني پيوسته موقعيت ميباشد. پس از حرکت تمام ذرات به سمت راهحل بهينه مسئله ، يک تکرار از مسئله به پايان ميرسد. مراحل فوق تا رسيدن به شرط توقف (تعداد تکرار معين ) انجام ميشود.
بهترين موقعيت عمومي به دست آمده در صورت تحقق شرط توقف مسئله ، همان راهحل بهينه مسئله ميباشد.
در روابط فوق، به ترتيب مربوط به بردار سرعت ذره i ام در تکرارt ام، موقعيت ذره i ام در تکرار t ام، بهترين موقعيت محلي ذره i ام و بهترين موقعيت عمومي در تکرار t ام ميباشند. فلوچارت الگوريتم ازدحام ذرات در بخش (٣-٢) ارائه شده است .
٣. روش پيشنهادي
٣-١. داده مورد استفاده
با توجه به اهميت تصاوير ابرطيفي به دليل اطلاعات طيفي وسيع و افزايش دقت استخراج اطلاعات در اين تصاوير، روش پيشنهادي در اين مقاله بر روي دو مجموعه تصوير ابرطيفي پيادهسازي شده است . مشخصات تصاوير ابرطيفي مورد استفاده در اين تحقيق در جدول (١) ارائه شده است .
٣-٢. بهينه سازي طبقه بندي SVM
همانطور که گفته شد، تابع کرنل در طبقه بندي SVM به منظور انتقال دادهها از فضايي با ابعاد پايين (حالت غيرخطي) به فضايي با ابعاد بالا (حالت خطي) مورد نياز است . در اين مقاله بنا به دلايل ذکرشده در بخش (٢-١)، از تابع کرنل پايه شعاعي استفادهشده است ؛ بنابراين دو پارامتر ترم تنظيم کننده خطا (C) و پارامتر کرنل (γ) در طبقه بندي SVM براي تنظيمات دقيق مورد نياز است ؛ زيرا اين دو پارامتر مستقيما بر عملکرد طبقه بندي تأثير ميگذارند. تعيين مقادير دقيق اين پارامترها اغلب به صورت سعي و خطا انجام ميشود که امري دشوار و هزينه بر ميباشد. به طورکلي، به منظور يافتن بهترين مقدار C وγ، يک پارامتر ثابت در نظر گرفته ميشود و پارامتر ديگر در يک محدوده تغيير ميکند. اين روش از انتخاب و مقايسه يک مجموعه اي از اعداد نتيجه ميشود که اين روش کارايي و دقت پايين در فضاي جست وجوي بزرگ دارد.
به منظور رفع مشکلات فوق، از الگوريتم هاي GA و PSO جهت يافتن مقادير بهينه اين دو پارامتر استفادهشده است . روند کلي بهينه سازي طبقه بندي SVM با الگوريتم GA و PSO در ادامه ارائه شده است . روند کلي روش پيشنهادي در اين مقاله ، شکل (١) و (٢) ارائه شده است .
ازدحام ذرات
در اين مقاله به منظور ارزيابي هرکدام از راهحل هاي ممکن در الگوريتم بهينه سازي، از خطاي طبقه بندي SVM به عنوان تابع هزينه استفاده ميشود. الگوريتم بهينه سازي GA و PSO به ترتيب مطابق با زير بخش (٢-٢-١) و (٢-٢-٢) موردبررسي قرارگرفته است . روند کلي بهينه سازي طبقه بندي SVM با الگوريتم GA و PSOدر شکل (٣) ارائه شده است .
