تعيين ماشين¬هاي بردار پشتيبان بهينه در طبقه¬بندي تصاوير فرا طیفی بر مبناي الگوريتم ژنتيک

محورهای موضوعی : عمومى

فرهاد صمدزادگان ¹ (دانشگاه تهران)
حديثه سادات حسني ² (دانشگاه تهران)

تاریخ دریافت : 1391/04/06 تاریخ پذیرش : 1391/04/06 تاریخ انتشار : 1391/12/20

کلید واژه: ماشین‌های بردار پشتيبان, تصاوير فرا طیفی, طبقه بندي, انتخاب مدل, انتخاب ويژگي, الگوريتم ژنتيک,

چکیده مقاله :

امروزه تصاوير فرا طیفی به علت غناي اطلاعات طيفي يک ابزار قوي و کارامد در سنجش از دور به حساب مي¬آيند و امکان تمايز بين عوارض مشابه را فراهم مي¬آورند. با توجه به پايداري ماشین‌های بردار پشتیبان در فضاهايي با ابعاد بالا، یک گزينه مناسب در طبقه¬بندي تصاوير فرا طیفی محسوب مي¬شوند. با اين وجود، عملکرد این طبقه¬بندي کننده¬ها تحت تأثیر پارامترها و فضاي ويژگي ورودي آن¬ها مي¬باشد. به منظور استفاده از ماشين¬هاي بردار پشتيبان با بيشترين کارایی، مي¬بايست مقادير بهينه¬ي پارامترها و همچنين زير مجموعه بهينه از ويژگي¬هاي ورودي تعيين گردند. در اين تحقيق از توانايي الگوريتم ژنتيک به عنوان يک تکنيک بهينه¬سازي فرا ابتکاري، در تعيين مقادير بهينه پارامترهاي ماشين¬هاي بردار پشتيبان و همچنين انتخاب زيرمجموعه ويژگي¬هاي بهينه در طبقه¬بندي تصاوير فرا طیفی استفاده شده است. نتايج عملي از به‌کارگیری روش فوق در خصوص داده¬هاي فرا طیفی سنجنده AVIRISنشان مي¬دهند، ويژگي¬هاي ورودي و پارامترها هر کدام جداگانه تأثیر بسزايي بر عملکرد ماشين¬هاي بردار پشتيبان دارند ولي بهترين عملکرد طبقه-بندي کننده با حل همزمان آن دو بدست مي¬آيد. در حل همزمان تعيين پارامتر و انتخاب ويژگي، براي کرنل گوسين و پلي¬نوميال به ترتيب 5% و 15% افزايش دقت با حذف بيش از نيمي از باندهاي تصوير حاصل شد. همچنين الگوريتم بهينه¬سازي شبيه¬سازي تبريد تدريجي به منظور مقايسه با الگوريتم ژنتيک پياده¬سازي شد که نتايج حاکي از برتري الگوريتم ژنتيک به ويژه با بزرگ و پيچيده شدن فضاي جستجو در رويکرد حل همزمان تعيين پارامتر و انتخاب ويژگي مي¬باشد.

چکیده انگلیسی:

منابع و مأخذ:

[1]. C. Chang, Hyperspectral data exploitation: theory and applications: Wiley-Blackwell, 2007.
[2]. G. Hughes, "On the mean accuracy of statistical pattern recognizers," IEEE Transactions on Information Theory, vol. 14, pp. 55-63, 2002.
[3]. G. Camps-Vallsand L. Bruzzone, "Kernel-based methods for hyperspectral image classification," IEEE Transactions on Geoscience and Remote Sensing, vol. 43, pp. 1351-1362, 2005.
[4]. P. Du, K. Tan, W. Zhang, and Z. Yan, "ANN Classification of OMIS Hyperspectral RemotelySensed Imagery: Experiments and Analysis," Congress on Image and Signal Processing, pp. 692-696, 2008.
[5]. T. Waheed, R. Bonnell, S. Prasher, and E. Paulet, "Measuring performance in precision agriculture: CART--A decision tree approach," Agricultural water management, vol. 84, pp. 173-185, 2006.
[6]. J. Ham, Y. Chen, M. Crawford, and J. Ghosh, "Investigation of the random forest framework for classification of hyperspectral data," IEEE Transactions on Geoscience and Remote Sensing, vol. 43, pp. 492-501, 2005.
[7]. F. Melgani and L. Bruzzone, "Classification of hyperspectral remote sensing images with support vector machines," IEEE Transactions on Geoscience and Remote Sensing, vol. 42, pp. 1778-1790, 2004.

[8]. C. Dai, X. Huang, and G. Dong, "Support Vector Machine for Classification of Hyperspectral Remote Sensing Imagery,"Fourth International Conference on Fuzzy System and Knowledge Discovery, pp. 77-80, 2007.
[9]. B. Guo, S. Gunn, R. Damper, and J. Nelson, "Customizing kernel functions for SVM-based hyperspectral image classification," IEEE Transactions onImage Processing, vol. 17, pp. 622-629, 2008.
[10]. P. Watanachaturaporn, M. Arora, and P. Varshney, "Hyperspectral image classification using support vector machines: A comparison with decision tree and neural network classifiers," 2006.
[11]. S. Arlot and A. Celisse, "A survey of cross-validation procedures for model selection," Statistics Surveys, vol. 4, pp. 40-79, 2010.
[12]. X. Zhang, X. Chen, and Z. He, "An ACO-based algorithm for parameter optimization of support vector machines," Expert systems with applications, 2010.
[13]. C. Wu, G. Tzeng, Y. Goo, and W. Fang, "A real-valued genetic algorithm to optimize the parameters of support vector machine for predicting bankruptcy," Expert systems with applications, vol. 32, pp. 397-408, 2007.
[14]. E. Huerta, B. Duval, and J. Hao, "A hybrid GA/SVM approach for gene selection and classification of microarray data," Applications of Evolutionary Computing, pp. 34-44, 2006.
[15]. L. Zhuo, J. Zheng, F. Wang, X. Li, B. Ai, and J. Qian, "A genetic algorithm based wrapper feature selection method for classification of hyperspectral images using support vector machine," The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, vol. 37, pp. 397-402, 2008.
[16]. T. Zhang, X. Fu, R. Goh, C. Kwoh, and G. Lee, "A GA-SVM feature selection model based on high performance computing techniques," IEEE International Conference on System, Man and Cybernetics, pp. 2653-2658, 2009.
[17]. C. Huang, "ACO-based hybrid classification system with feature subset selection and model parameters optimization," Neurocomputing, vol. 73, pp. 438-448, 2009.
[18]. S. Lin, Z. Lee, S. Chen, and T. Tseng, "Parameter determination of support vector machine and feature selection using simulated annealing approach," Applied soft computing, vol. 8, pp. 1505-1512, 2008.
[19]. S. Lin, K. Ying, S. Chen, and Z. Lee, "Particle swarm optimization for parameter determination and feature selection of support vector machines," Expert systems with applications, vol. 35, pp. 1817-1824, 2008.
[20]. C. Huang and C. Wang, "A GA-based feature selection and parameters optimizationfor support vectormachines," Expert systems with applications, vol. 31, pp. 231-240, 2006.
[21]. R. Haupt, S. Haupt, and J. Wiley, Practical genetic algorithms: Wiley Online Library, 1998.
[22]. V. Vapnik, The nature of statistical learning theory: Springer Verlag, 2000.
[23]. A. Lorena and A. de Carvalho, "Evolutionary tuning of SVM parameter values in multiclass problems," Neurocomputing, vol. 71, pp. 3326-3334, 2008.
[24]. T. Weise, "Global Optimization Algorithms–Theory and Application,", Abrufdatum, vol. 1, 2008.
[25]. U. Maulik, "Medical image segmentation using genetic algorithms," IEEE Transactions onInformation Technology in Biomedicine, vol. 13, pp. 166-173, 2009.
[26]. E. Pourbasheer, S. Riahi, M. Ganjali, and P. Norouzi, "Application of genetic algorithm-support vector machine (GA-SVM) for prediction of BK-channels activity," European journal of medicinal chemistry, vol. 44, pp. 5023-5028, 2009.
[27]. B. de Souza, A. de Carvalho, R. Calvo, and R. Ishii, "Multiclass SVM model selection using particle swarm optimization," 2006, p. 31.
[28]. C. Hsu, C. Chang, and C. Lin, "A practical guide to support vector classification," Citeseer, 2003.
[29]. I. Guyon and A. Elisseeff, "An introduction to variable and feature selection," The Journal of Machine Learning Research, vol. 3, pp. 1157-1182, 2003.
[30]. M. Tahir, A. Bouridane, F. Kurugollu, and A. Amira, "Feature selection using tabu search for improving the classification rate of prostate needle biopsies," Pattern Recognition, vol. 2, pp. 335-33, 2004.
[31]. C. Tu, L. Chuang, J. Chang, and C. Yang, "Feature selection using PSO-SVM," IAENG International journal of computer science, vol. 33, pp. 111-116, 2007.
[32]. D. Niu, Y. Wang, and D. Wu, "Power load forecasting using support vector machine and ant colony optimization," Expert systems with applications, vol. 37, pp. 2531-2539, 2010.
[33]. H. Frohlich, O. Chapelle, and B. Scholkopf, "Feature selection for support vector machines by means of genetic algorithm," 2003, pp. 142-148.
[34]. S. Bhatia, P. Prakash, and G. Pillai, "SVM Based Decision Support System for Heart Disease Classification with Integer-Coded Genetic Algorithm to Select Critical Features," 2008.
[35]. A.B. Santos, C.S.F. de S. Celes, A. de A. Araŭjo, D. Menotti, "Feature selection for classification of remote sensed hyperspectral images: A filter approach using genetic algorithm and cluster validity,"The 2012 International Conference on Image Processing, Computer Vision, and Pattern Recognition (IPCV’12), 2012.
[36]. Y. Bazi and F. Melgani, "Toward an optimal SVM classification system for hyperspectral remote sensing images," IEEE Transactions onGeoscience and Remote Sensing, vol. 44, pp. 3374-3385, 2006.
[37]. I. Mejía-Guevara and Ákuri-Morales, "Evolutionary feature and parameter selection in support vector regression," MICAI 2007: Advances inArtificial Intelligence, pp. 399-408, 2007.
[38]. E. Avci, "Selecting of the optimal feature subset and kernel parameters in digital modulation classification by using hybrid genetic algorithm-support vector machines: HGASVM," Expert systems with applications, vol. 36, pp. 1391-1402, 2009.
[39]. B. F. de Souza and A. P. d. L. F. de Carvalho, "Gene selection based on multi-class support vector machines and genetic algorithms," Genetics and Molecular Research, pp. 599-607, 2005.
[40]. M. Zhao, C. Fu, L. Ji, K. Tang, and M. Zhou, "Feature selection and parameter determination for support vector machines: A new approach based on genetic algorithm with feature chromosomes," Expert System with Applications, Vol. 38, No. 5, pp. 5197-5204, 2011.
[41]. N. Chen, B. Ribeiro, A. S. Vieira, J. Duarte, J. C. Neves, "A genetic algorithm-based approach to cost-sensitive bankruptcy prediction," Expert System with Application, Vol. 38, No. 10, pp. 12939-12945, 2011.

متن کامل:

ICeLeT2010 Persian Template

تعيين ماشينهاي بردار پشتيبان بهينه در طبقهبندي تصاوير فرا طیفی بر مبناي الگوريتم ژنتيک

فصلنامه علمي- پژوهشي

فناوري اطلاعات و ارتباطات ایران

سال چهارم، شماره‌هاي 13 و 14، پاییز و زمستان 1391

صص: 9- 24

$E:\E Drive\logo\iicta Logo0.JPG$

تعيين ماشينهاي بردار پشتيبان بهينه در طبقهبندي تصاوير فرا طیفی بر مبناي الگوريتم ژنتيک

فرهاد صمدزادگان* حديثه سادات حسني **1

* استاد، دانشکده مهندسي نقشهبرداري، دانشگاه تهران، تهران

** دانشجوي دکتري فتوگرامتري، دانشکده مهندسي نقشهبرداري، دانشگاه تهران، تهران

تاريخ دريافت: 06/04/1391 تاريخ پذيرش: 09/11/1391

چكيده

امروزه تصاوير فرا طیفی به علت غناي اطلاعات طيفي يک ابزار قوي و کارامد در سنجش از دور به حساب ميآيند و امکان تمايز بين عوارض مشابه را فراهم ميآورند. با توجه به پايداري ماشین‌های بردار پشتیبان در فضاهايي با ابعاد بالا، یک گزينه مناسب در طبقهبندي تصاوير فرا طیفی محسوب ميشوند. با اين وجود، عملکرد این طبقهبندي کنندهها تحت تأثیر پارامترها و فضاي ويژگي ورودي آنها ميباشد. به منظور استفاده از ماشينهاي بردار پشتيبان با بيشترين کارایی، ميبايست مقادير بهينهي پارامترها و همچنين زير مجموعه بهينه از ويژگيهاي ورودي تعيين گردند. در اين تحقيق از توانايي الگوريتم ژنتيک به عنوان يک تکنيک بهينهسازي فرا ابتکاري، در تعيين مقادير بهينه پارامترهاي ماشينهاي بردار پشتيبان و همچنين انتخاب زيرمجموعه ويژگيهاي بهينه در طبقهبندي تصاوير فرا طیفی استفاده شده است. نتايج عملي از به‌کارگیری روش فوق در خصوص دادههاي فرا طیفی سنجنده AVIRISنشان ميدهند، ويژگيهاي ورودي و پارامترها هر کدام جداگانه تأثیر بسزايي بر عملکرد ماشينهاي بردار پشتيبان دارند ولي بهترين عملکرد طبقهبندي کننده با حل همزمان آن دو بدست ميآيد. در حل همزمان تعيين پارامتر و انتخاب ويژگي، براي کرنل گوسين و پلينوميال به ترتيب 5% و 15% افزايش دقت با حذف بيش از نيمي از باندهاي تصوير حاصل شد. همچنين الگوريتم بهينهسازي شبيهسازي تبريد تدريجي به منظور مقايسه با الگوريتم ژنتيک پيادهسازي شد که نتايج حاکي از برتري الگوريتم ژنتيک به ويژه با بزرگ و پيچيده شدن فضاي جستجو در رويکرد حل همزمان تعيين پارامتر و انتخاب ويژگي ميباشد.

كليد واژگان: ماشین‌های بردار پشتيبان، تصاوير فرا طیفی، طبقه بندي، انتخاب مدل، انتخاب ويژگي، الگوريتم ژنتيک.

1. مقدمه

امروزه با پيشرفتهاي اخير در زمينه تکنولوژي ساخت سنجیده‌های فرا طیفی در سنجش از دور، امکان اخذ تصاوير با صدها باند با قدرت تفکيک طيفي بالا فراهم است [1]. افزايش تعداد باندها و در نتيجه افزايش اطلاعات طيفي، امکان استخراج اطلاعات بيشتر در مورد عوارض موجود در تصوير و همچنين تمايز بين عوارض مشابه را فراهم ميکند. از سوي ديگر با بالا رفتن ابعاد فضاي ورودي، نياز به پردازشهاي خاصي به منظور به‌کارگیری اين تصاوير در بسياري از کاربردهاي مطرح ميباشد [1].

يک مرحله مهم در پردازش تصاوير فرا طیفی به منظور استخراج اطلاعات، طبقهبندي آنها با يکسري کلاسهاي از پيش تعيين شده ميباشد. در تصاوير فرا طیفی، طبقهبندي کنندههاي پارامتريک به علت نياز به تخمين توزيع آماري کلاسها و عدم توازن بين تعداد باندها و تعداد نمونههاي آموزشي، با پديده هيوز¹ مواجه ميشوند [2]. در اين شرايط به علت بزرگ شدن فضاي فرضيه و محدوديت تعداد نمونههاي آموزشي، احتمال بيش تطابق نمودن² مدل به دادههاي آموزشي وجود دارد [3]. به منظور رفع مشکلات روشهاي پارامتريک در سالهاي اخير طبقهبندي کنندههاي غير پارامتريک مختلفي به منظور طبقهبندي تصاوير فرا طیفی ارائه شدهاند، از جمله: شبکه عصبي [4]، درخت تصميمگيري [5]، Random Forest [6] و روشهاي کرنل مبنا [3].

در اين خصوص ماشينهاي بردار پشتيبان³ به عنوان يک روش کرنل مبنا، توانستهاند به با توجه به عملکردشان بر مبناي ويژگيهاي هندسي و عدم نياز به تخمين ويژگيهاي آماري، ابزاري بسيار کارا و قدرتمند براي طبقهبندي تصاوير فرا طیفی به حساب آيند [7-9]. ايده ماشينهاي بردار پشتيبان يافتن يک صفحه تصميمگيري بهينه براي جداسازي دو کلاس می‌باشد به صورتي که دو کلاس بيشترين حاشيه جداسازي را در یک طبقه‌بندی باينري داشته باشند. در صورتی که نمونهها به صورت خطي جدا پذیر نباشند، ابتدا با يک کرنل به فضايي با ابعاد بالاتر منتقل ميشود و صفحه جداکننده در آن فضا تعريف ميشود [10].

هر چند در سالهاي اخير ماشينهاي بردار پشتيبان با موفقيت در طبقهبندي بسياري از تصاوير فرا طیفی به کار گرفته شدهاند، با اين حال ميبايست به تأثیر دو عامل که بر عملکرد آنها تأثیرگذار هستند، توجه داشت: پارامترهاي ماشينهاي بردار پشتيبان و فضاي ويژگي ورودي (باندهاي ورودي طبقهبندي). به منظور طراحي يک سيستم بهينه طبقهبندي براي تصاوير فرا طیفی بر مبناي ماشينهاي بردار پشتيبان، انتخاب مقادير بهينه پارامترهاي مدل و انتخاب زير مجموعهاي از باندهاي بهينه چالشهايي است که در اين زمينه وجود دارند. به علت اهميت موضوع، مطالعات زيادي در سالهاي اخير در اين زمينه انجام شده است که می‌توان آنها را به سه دسته تقسيم کرد. در دسته اول، از همه ويژگيهاي ورودي داده استفاده ميشود و پارامترهاي مدل بهينه ميگردد تا کارایی ماشينهاي بردار پشتيبان بالا رود [11-13]. انتخاب ويژگيهاي بهينه با ثابت درنظر گرفتن پارامترها گروه دوم تحقيقات ميباشد [14-16] که با حذف ويژگيهاي اضافي و وابسته، دقت و سرعت طبقهبندي را بهبود ميبخشند. در اين دسته از مطالعات، در ابتدا مقادير پارامترهاي مدل با استفاده از يک روش کلاسيک محاسبه شده و يا از مقادير پيش فرض استفاده ميکنند. سپس در پروسه انتخاب ويژگي آن مقادير ثابت در نظر گرفته ميشوند. با توجه به تأثیر فضاي ورودي بر مقدار بهينه پارامترها و بالعکس، دسته سوم الگوریتم‌ها به حل همزمان تعيين پارامترها و انتخاب زير مجموعه ويژگيهاي بهينه ميپردازند [17-20].

به منظور حل اين مسائل، با توجه به بزرگ بودن فضاي مجهولات نياز به يک الگوريتم بهينهسازي قوي و کارا می‌باشد تا بتواند جواب بهينه سراسري را بدست آورد. از آنجایي که الگوريتمهاي بهينه سازي مرسوم معمولاً در فضاي جستجوي بزرگ با مشکل مواجه ميشوند و به جواب زير بهينه ميرسند، در اين تحقيق از الگوريتم فرا ابتکاری⁴ ژنتيک استفاده گرديده است. الگوريتم ژنتيک به علت جمعيت مبنا بودن و اجراي همزمان جستجوي سراسري⁵ و جستجوي محلي⁶ پتانسيل بالايي در حل مسائل پيچيده بهينهسازي دارد [21].

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

2. ماشينهاي بردار پشتيبان

ماشينهاي بردار پشتيبان يک روش طبقه بندي با نظارت بر مبنای نظريه يادگيري آماري ميباشند [22]. ايده اساسي اين طبقهبندي کننده، يافتن يک ابر صفحه بهينه به عنوان سطح تصميمگيري به گونهاي ميباشد که حاشيه بين دو کلاس را بيشينه کند. در صورتی که دادهها به صورت خطي جدا پذیر نباشد، داده‌ها با کرنلي غيرخطي به فضاي با ابعاد بالاتر منتقل ميشود و ابر صفحه بهينه در آن فضا تعيين ميشود.

فرض کنيد l دادههاي آموزشي موجود ميباشد که هر يک با (xi,yi) نشان داده ميشود، xi بردار ويژگي n بعدي و برچسب آن می‌باشد. هدف يافتن ابر صفحه است که دو کلاس با برچسب 1 و 1- را با بيشترين حاشيه از هم جدا کند. اين ابر صفحه را می‌توان با معادله (1) بيان کرد.

(1)

در اين رابطه، بردار وزن w، برداري عمود بر ابر صفحه، b بردار باياس می‌باشد که به منظور اندازهگيري فاصله ابر صفحه تا مبدأ استفاده می‌شود و کرنلي براي انتقال داده به فضاي با ابعاد بالاتر ميباشد (شکل 1).

شکل 1- طبقهبندي دادههايي که به صورت خطي جدا پذیر نيستند، توسط ماشينهاي بردار پشتيبان

بيشينه نمودن حاشيه بين دو کلاس معادل کمينه کردن اندازه w ميباشد که منجر به حل مسئله کمينهسازي مقيد (2) ميشود.

(2)

که پارامتر C، پارامتر تنظيم در ماشينهاي بردار پشتیبان می‌باشد. به منظور در نظر گرفتن نويز موجود در داده و تداخل بين دادههاي آموزشي، از متغير استفاده ميشود. وجود قيد ضمانت ميکند که دادهاي در حاشيه قرار نميگيرد. هرچند براي جلوگيري از بيش تطابق نمودن به دادههاي نويزي، اين قيد با متغيرهاي نرم شده است.

سطح تصميمگيري بهينه با حل مسئله مقيد (2) بر مبناي روش لاگرانژ طبق معادله (3) محاسبه ميشود.

(3)

در اين رابطه ضرايب لاگرانژ ميباشد که در پروسه بهينهسازي محاسبه می‌شود، SV بردارهاي پشتيبان هستند که ضريب لاگرانژ متناظر آنها بزرگ‌تر از صفر است. اين داده هاي آموزشي، نزديکترين نمونهها به ابر صفحه هستند. همان طور که رابطه (3) نشان ميدهد، تنها بردارهاي پشتيبان هستند که در مرحله آموزش شرکت ميکنند. در نتيجه ماشينهاي بردار پشتيبان نياز به تعداد نمونه آموزشي زياد ندارند. در رابطه (3)، ضرب داخلي بين دو کرنل نگاشت شده، ميتواند با کرنل آن دو نمونه محاسبه گردد. از پرکاربردترين کرنلها، کرنل گوسين و پلي نوميال هستند که به ترتيب با روابط (4) و (5) تعريف می‌شوند.

(4)

(5)

در اين روابط،پارامتر کرنل گوسين و d متغير کرنل پلي نوميال می‌باشد [23].

الگوريتم پايه ماشينهاي بردار پشتيبان براي طبقهبندي باينري توسعه داده شده است. از آنجایي که در بيشتر کاربردها، بيش از دو کلاس وجود دارد، الگوريتمهاي مختلفي براي حل مسئله چند کلاسه به کار گرفته شده است [10]. يک روش مرسوم در اين زمينه تجزيه مسئله چند کلاسه به مسئله اي با چندين طبقه بندي کننده باينري ميباشد. الگوریتم‌های «يک در مقابل يک» و «يک در مقابل مابقي»، دو الگوريتم پرکاربرد در اين زمينه ميباشد.

در روش «يک در مقابل يک»، براي هر زوج کلاس ممکن از يک ماشين بردار پشتيبان باينري استفاده می‌شود. به اين ترتيب براي M کلاس،

اشتراک گذاری

آدرس مقاله

تعيين ماشين¬هاي بردار پشتيبان بهينه در طبقه¬بندي تصاوير فرا طیفی بر مبناي الگوريتم ژنتيک