تعيين ماشين¬هاي بردار پشتيبان بهينه در طبقه¬بندي تصاوير فرا طیفی بر مبناي الگوريتم ژنتيک
محورهای موضوعی : عمومىفرهاد صمدزادگان 1 , حديثه سادات حسني 2 *
1 - دانشگاه تهران
2 - دانشگاه تهران
کلید واژه: ماشین‌های بردار پشتيبان, تصاوير فرا طیفی, طبقه بندي, انتخاب مدل, انتخاب ويژگي, الگوريتم ژنتيک,
چکیده مقاله :
امروزه تصاوير فرا طیفی به علت غناي اطلاعات طيفي يک ابزار قوي و کارامد در سنجش از دور به حساب مي آيند و امکان تمايز بين عوارض مشابه را فراهم مي آورند. با توجه به پايداري ماشین‌های بردار پشتیبان در فضاهايي با ابعاد بالا، یک گزينه مناسب در طبقه بندي تصاوير فرا طیفی محسوب مي شوند. با اين وجود، عملکرد این طبقه بندي کننده ها تحت تأثیر پارامترها و فضاي ويژگي ورودي آن ها مي باشد. به منظور استفاده از ماشين هاي بردار پشتيبان با بيشترين کارایی، مي بايست مقادير بهينه ي پارامترها و همچنين زير مجموعه بهينه از ويژگي هاي ورودي تعيين گردند. در اين تحقيق از توانايي الگوريتم ژنتيک به عنوان يک تکنيک بهينه سازي فرا ابتکاري، در تعيين مقادير بهينه پارامترهاي ماشين هاي بردار پشتيبان و همچنين انتخاب زيرمجموعه ويژگي هاي بهينه در طبقه بندي تصاوير فرا طیفی استفاده شده است. نتايج عملي از به‌کارگیری روش فوق در خصوص داده هاي فرا طیفی سنجنده AVIRISنشان مي دهند، ويژگي هاي ورودي و پارامترها هر کدام جداگانه تأثیر بسزايي بر عملکرد ماشين هاي بردار پشتيبان دارند ولي بهترين عملکرد طبقه-بندي کننده با حل همزمان آن دو بدست مي آيد. در حل همزمان تعيين پارامتر و انتخاب ويژگي، براي کرنل گوسين و پلي نوميال به ترتيب 5% و 15% افزايش دقت با حذف بيش از نيمي از باندهاي تصوير حاصل شد. همچنين الگوريتم بهينه سازي شبيه سازي تبريد تدريجي به منظور مقايسه با الگوريتم ژنتيک پياده سازي شد که نتايج حاکي از برتري الگوريتم ژنتيک به ويژه با بزرگ و پيچيده شدن فضاي جستجو در رويکرد حل همزمان تعيين پارامتر و انتخاب ويژگي مي باشد.
۱٬۳۸۵ / ۵٬۰۰۰ Today, hyperspectral images are considered a powerful and efficient tool in remote sensing due to the wealth of spectral information and provide the possibility of distinguishing between similar complications. Considering the stability of support vector machines in spaces with high dimensions, they are considered a suitable option in the classification of hyperspectral images. Nevertheless, the performance of these classifiers is influenced by their input parameters and feature space. In order to use support vector machines with the highest efficiency, the optimal values of the parameters and also the optimal subset of the input features should be determined. In this research, the ability of the genetic algorithm as a meta-heuristic optimization technique has been used in determining the optimal values of support vector machine parameters and also selecting the subset of optimal features in the classification of hyperspectral images. The practical results of applying the above method on the hyperspectral data of AVIRIS sensor show that the input features and parameters each have a great effect on the performance of support vector machines, but the best performance of the classifier is obtained by solving them simultaneously. In the simultaneous solution of parameter determination and feature selection, for Gaussian kernel and polynomial, 5% and 15% increase in accuracy was achieved by removing more than half of the image bands. Also, the gradual cooling simulation optimization algorithm was implemented in order to compare with the genetic algorithm, and the results indicate the superiority of the genetic algorithm, especially with the large and complicated search space in the simultaneous solution approach of parameter determination and feature selection.
[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.
تعيين ماشينهاي بردار پشتيبان بهينه در طبقهبندي تصاوير فرا طیفی بر مبناي الگوريتم ژنتيک
فصلنامه علمي- پژوهشي فناوري اطلاعات و ارتباطات ایران | سال چهارم، شمارههاي 13 و 14، پاییز و زمستان 1391 صص: 9- 24 |
|
تعيين ماشينهاي بردار پشتيبان بهينه در طبقهبندي تصاوير فرا طیفی بر مبناي الگوريتم ژنتيک
فرهاد صمدزادگان* حديثه سادات حسني **1
* استاد، دانشکده مهندسي نقشهبرداري، دانشگاه تهران، تهران
** دانشجوي دکتري فتوگرامتري، دانشکده مهندسي نقشهبرداري، دانشگاه تهران، تهران
تاريخ دريافت: 06/04/1391 تاريخ پذيرش: 09/11/1391
چكيده
امروزه تصاوير فرا طیفی به علت غناي اطلاعات طيفي يک ابزار قوي و کارامد در سنجش از دور به حساب ميآيند و امکان تمايز بين عوارض مشابه را فراهم ميآورند. با توجه به پايداري ماشین‌های بردار پشتیبان در فضاهايي با ابعاد بالا، یک گزينه مناسب در طبقهبندي تصاوير فرا طیفی محسوب ميشوند. با اين وجود، عملکرد این طبقهبندي کنندهها تحت تأثیر پارامترها و فضاي ويژگي ورودي آنها ميباشد. به منظور استفاده از ماشينهاي بردار پشتيبان با بيشترين کارایی، ميبايست مقادير بهينهي پارامترها و همچنين زير مجموعه بهينه از ويژگيهاي ورودي تعيين گردند. در اين تحقيق از توانايي الگوريتم ژنتيک به عنوان يک تکنيک بهينهسازي فرا ابتکاري، در تعيين مقادير بهينه پارامترهاي ماشينهاي بردار پشتيبان و همچنين انتخاب زيرمجموعه ويژگيهاي بهينه در طبقهبندي تصاوير فرا طیفی استفاده شده است. نتايج عملي از به‌کارگیری روش فوق در خصوص دادههاي فرا طیفی سنجنده AVIRISنشان ميدهند، ويژگيهاي ورودي و پارامترها هر کدام جداگانه تأثیر بسزايي بر عملکرد ماشينهاي بردار پشتيبان دارند ولي بهترين عملکرد طبقهبندي کننده با حل همزمان آن دو بدست ميآيد. در حل همزمان تعيين پارامتر و انتخاب ويژگي، براي کرنل گوسين و پلينوميال به ترتيب 5% و 15% افزايش دقت با حذف بيش از نيمي از باندهاي تصوير حاصل شد. همچنين الگوريتم بهينهسازي شبيهسازي تبريد تدريجي به منظور مقايسه با الگوريتم ژنتيک پيادهسازي شد که نتايج حاکي از برتري الگوريتم ژنتيک به ويژه با بزرگ و پيچيده شدن فضاي جستجو در رويکرد حل همزمان تعيين پارامتر و انتخاب ويژگي ميباشد.
كليد واژگان: ماشین‌های بردار پشتيبان، تصاوير فرا طیفی، طبقه بندي، انتخاب مدل، انتخاب ويژگي، الگوريتم ژنتيک.
1. مقدمه
امروزه با پيشرفتهاي اخير در زمينه تکنولوژي ساخت سنجیده‌های فرا طیفی در سنجش از دور، امکان اخذ تصاوير با صدها باند با قدرت تفکيک طيفي بالا فراهم است [1]. افزايش تعداد باندها و در نتيجه افزايش اطلاعات طيفي، امکان استخراج اطلاعات بيشتر در مورد عوارض موجود در تصوير و همچنين تمايز بين عوارض مشابه را فراهم ميکند. از سوي ديگر با بالا رفتن ابعاد فضاي ورودي، نياز به پردازشهاي خاصي به منظور به‌کارگیری اين تصاوير در بسياري از کاربردهاي مطرح ميباشد [1].
يک مرحله مهم در پردازش تصاوير فرا طیفی به منظور استخراج اطلاعات، طبقهبندي آنها با يکسري کلاسهاي از پيش تعيين شده ميباشد. در تصاوير فرا طیفی، طبقهبندي کنندههاي پارامتريک به علت نياز به تخمين توزيع آماري کلاسها و عدم توازن بين تعداد باندها و تعداد نمونههاي آموزشي، با پديده هيوز1 مواجه ميشوند [2]. در اين شرايط به علت بزرگ شدن فضاي فرضيه و محدوديت تعداد نمونههاي آموزشي، احتمال بيش تطابق نمودن2 مدل به دادههاي آموزشي وجود دارد [3]. به منظور رفع مشکلات روشهاي پارامتريک در سالهاي اخير طبقهبندي کنندههاي غير پارامتريک مختلفي به منظور طبقهبندي تصاوير فرا طیفی ارائه شدهاند، از جمله: شبکه عصبي [4]، درخت تصميمگيري [5]، Random Forest [6] و روشهاي کرنل مبنا [3].
در اين خصوص ماشينهاي بردار پشتيبان3 به عنوان يک روش کرنل مبنا، توانستهاند به با توجه به عملکردشان بر مبناي ويژگيهاي هندسي و عدم نياز به تخمين ويژگيهاي آماري، ابزاري بسيار کارا و قدرتمند براي طبقهبندي تصاوير فرا طیفی به حساب آيند [7-9]. ايده ماشينهاي بردار پشتيبان يافتن يک صفحه تصميمگيري بهينه براي جداسازي دو کلاس می‌باشد به صورتي که دو کلاس بيشترين حاشيه جداسازي را در یک طبقه‌بندی باينري داشته باشند. در صورتی که نمونهها به صورت خطي جدا پذیر نباشند، ابتدا با يک کرنل به فضايي با ابعاد بالاتر منتقل ميشود و صفحه جداکننده در آن فضا تعريف ميشود [10].
هر چند در سالهاي اخير ماشينهاي بردار پشتيبان با موفقيت در طبقهبندي بسياري از تصاوير فرا طیفی به کار گرفته شدهاند، با اين حال ميبايست به تأثیر دو عامل که بر عملکرد آنها تأثیرگذار هستند، توجه داشت: پارامترهاي ماشينهاي بردار پشتيبان و فضاي ويژگي ورودي (باندهاي ورودي طبقهبندي). به منظور طراحي يک سيستم بهينه طبقهبندي براي تصاوير فرا طیفی بر مبناي ماشينهاي بردار پشتيبان، انتخاب مقادير بهينه پارامترهاي مدل و انتخاب زير مجموعهاي از باندهاي بهينه چالشهايي است که در اين زمينه وجود دارند. به علت اهميت موضوع، مطالعات زيادي در سالهاي اخير در اين زمينه انجام شده است که می‌توان آنها را به سه دسته تقسيم کرد. در دسته اول، از همه ويژگيهاي ورودي داده استفاده ميشود و پارامترهاي مدل بهينه ميگردد تا کارایی ماشينهاي بردار پشتيبان بالا رود [11-13]. انتخاب ويژگيهاي بهينه با ثابت درنظر گرفتن پارامترها گروه دوم تحقيقات ميباشد [14-16] که با حذف ويژگيهاي اضافي و وابسته، دقت و سرعت طبقهبندي را بهبود ميبخشند. در اين دسته از مطالعات، در ابتدا مقادير پارامترهاي مدل با استفاده از يک روش کلاسيک محاسبه شده و يا از مقادير پيش فرض استفاده ميکنند. سپس در پروسه انتخاب ويژگي آن مقادير ثابت در نظر گرفته ميشوند. با توجه به تأثیر فضاي ورودي بر مقدار بهينه پارامترها و بالعکس، دسته سوم الگوریتم‌ها به حل همزمان تعيين پارامترها و انتخاب زير مجموعه ويژگيهاي بهينه ميپردازند [17-20].
به منظور حل اين مسائل، با توجه به بزرگ بودن فضاي مجهولات نياز به يک الگوريتم بهينهسازي قوي و کارا می‌باشد تا بتواند جواب بهينه سراسري را بدست آورد. از آنجایي که الگوريتمهاي بهينه سازي مرسوم معمولاً در فضاي جستجوي بزرگ با مشکل مواجه ميشوند و به جواب زير بهينه ميرسند، در اين تحقيق از الگوريتم فرا ابتکاری4 ژنتيک استفاده گرديده است. الگوريتم ژنتيک به علت جمعيت مبنا بودن و اجراي همزمان جستجوي سراسري5 و جستجوي محلي6 پتانسيل بالايي در حل مسائل پيچيده بهينهسازي دارد [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 کلاس، 
طبقهبندي کننده ماشین بردار پشتيبان باينري نياز داريم. در نهايت همه ماشينهاي بردار پشتيبان باينري با روش راي گيري حداکثر ادغام ميشود.
روش «يک در مقابل مابقي»، روش مرسوم ديگر می‌باشد که در آن هر ماشين بردار پشتيبان باينري، دادههاي يک کلاس را از دادههاي کلاسهاي ديگر جدا ميکند. در اين روش، براي M کلاس، M طبقهبندي کننده باينري خواهيم داشت. پس از طبقهبندي داده جديد با M طبقهبندي کننده، داده به کلاسي که بيشترين نتيجه مثبت را داشته باشد، نسبت داده ميشود [10].
3. مروري بر تحقيقات
با توجه به اطلاعات طيفي غني موجود در تصاوير فرا طیفی، همراه با پيشرفت تکنولوژی ساخت سنجیده‌های فرا طیفی، الگوريتمهاي پردازش اين دسته از تصاوير نيز رشد چشمگيري داشتهاند که در اين بين الگوريتمهاي طبقه‌بندی به منظور استخراج اطلاعات و همچنين تهيه نقشههاي موضوعي بسيار مورد توجه قرار گرفتهاند. از این رو مطالعات گستردهاي در زمينه ارزیابی عملکرد طبقهبندي کنندههاي گوناگون در تصاوير فرا طیفی صورت گرفته است. از اوايل سال 2000، نخستين تحقيقات بر مبناي استفاده از ماشينهاي بردار پشتيبان در طبقهبندي تصاوير فرا طیفی صورت پذيرفت. در سالهاي بعد عملکرد طبقهبندي کنندههاي ديگر از قبیل شبکه‌های عصبي، نزديکترين همسايه، کمترين فاصله، بيشترين شباهت، درخت تصميمگيري و آناليز تفکيک کرنل فيشر در مقايسه با ماشينهاي بردار پشتيبان بررسي شد که نتايج حاکي از برتري ماشينهاي بردار پشتيبان ميباشد ]3، 4، 5، 6[. از این رو در اين تحقيق از طبقهبندي کننده ماشينهاي بردار پشتيبان به منظور پردازش تصوير فرا طیفی استفاده شده است.
هرچند ماشينهاي بردار پشتيبان به عنوان ابزاري کارا در طبقهبندي تصاوير فرا طیفی به کار برده شدهاند، به منظور بهبود عملکرد اين طبقهبندي کننده به لحاظ دقت و پيچيدگيهاي محاسباتي، ميبايست به دو عامل تأثیرگذار توجه شود: پارامترهاي طبقهبندي کننده و باندهاي ورودي آن. از این رو مطالعات گوناگوني بر مبناي بهينهسازي سيستم طبقهبندي تصاوير فرا طیفی ارائه شدهاند. تحقيقات موجود در اين زمينه را ميتوان در سه بخش انتخاب مدل، انتخاب ويژگي و حل همزمان این دو دستهبندي کرد.
انتخاب بهينه پارامترهاي تشکيل دهنده مدل در ماشينهاي بردار پشتيبان از تأثیر مستقيمي در کارایی اين روش برخوردار ميباشند [13]. دو دسته پارامتر در اين طبقهبندي کنندهها وجود دارد. «پارامتر تنظيم» که تعادل بين کمينه شدن خطا و کمينه شدن پیچیدگی‌های مدل را برقرار می‌کند (پارامتر C) و «پارامترهاي کرنل» که با توجه به کرنل انتخابي، متغيرهاي آن کرنل جزء مجهولات می‌شوند. مانند در کرنل گوسين و d در کرنل پلي نوميال [13].
همان طور که در بخش قبل بيان شد، ماشينهاي بردار پشتيبان ذاتاً باينري هستند و براي مسائل چند کلاسه از ترکيب چندين طبقهبندي کننده باينري استفاده ميشود. از اين نقطه نظر ميتوان الگوريتمهاي موجود در تعیین پارامترهاي ماشينهاي بردار پشتيبان که انتخاب مدل نيز ناميده ميشوند، را به دو دسته تقسيم کرد. در دسته اول تکنيکهاي انتخاب مدل، براي همهي ماشينهاي بردار پشتيبان باينري يک دسته پارامتر يکسان در نظر گرفته ميشود [13, 26]. در حالی که در دسته دوم، براي هر طبقه‌بندی کننده باينري يکسري پارامتر متفاوت تعيين ميشود [23, 27]. تحقيقات انجام شده نشان داده است که با اضافه شدن مجهولات در اکثر موارد نه تنها دقت طبقهبندي بالا نميرود بلکه به دليل بيش تطابق نمودن به دادههاي آموزشي، سيستم طبقهبندي داراي قدرت تعميم کمي خواهد بود [27]. در نتيجه در اين تحقيق از يک دسته پارامتر براي همه ماشينهاي بردار پشتيبان باينري استفاده می‌شود.
در سالهاي اخير روشهاي متنوعي به منظور تعيين پارامترهاي بهينه در ماشينهاي بردار پشتيبان، توسط محققين مختلف ارائه گرديده است [11-13]. الگوريتم جستجوي شبکهاي، روش رايج در انتخاب پارامترهاي بهينه مدل ميباشد. در اين روش، شبکهاي k بعدي بر روي محدوده پارامترها قرار ميگيرد که k تعداد پارامترهاي مجهول ميباشد (در اين تحقيق براي به کارگيري هر دو کرنل گوسين و پلينوميال k=2 در نظر گرفته شده است). سپس کيفيت تمام مجموعه جوابهاي ممکن در نقاط شبکه ارزيابي ميشود و آن دسته از پارامترهايي که کمترين خطاي طبقهبندي را دارند، به عنوان پارامترهاي ماشينهاي بردار پشتيبان انتخاب ميشوند [28]. به علت پيوسته بودن مقادير پارامترهاي مورد نظر، براي رسيدن به دقت بالا ميبايست شبکهاي با تراکم بالا در نظر گرفته شود که بررسي تمام اين نقاط شبکه زمان محاسبات را به شدت افزايش ميدهد.
با توجه به محدوديتهاي روش جستجوي شبکهاي در زمان و محاسبات، الگوریتم‌های بهينه سازي مختلفي براي حل اين مسئله در نظر گرفته شدهاند: الگوریتم‌های خرد جمعي [12, 27]، شبيه سازي تبريد تدريجي [18] و الگوريتم ژنتيک [13, 23, 26].
در اين بين، الگوريتم ژنتيک از الگوریتم‌های فرا ابتکاري هستند که به طور موفقيت آميز و گستردهاي در سالهاي اخير در زمينه انتخاب پارامترهاي بهينه مدل در ماشينهاي بردار پشتيبان استفاده شدهاند [23, 26]. الگوريتم ژنتيک به دو شکل در انتخاب مدل ميتواند استفاده گردد: کدگذاري اعداد حقيقي [13, 23] و کدگذاري باينري [15, 26].
دسته ديگر مطالعات در زمينه بهينهسازي سيستمهاي طبقهبندي، به مسئله انتخاب زيرمجموعه بهينه باندهاي ورودی ميپردازند. الگوريتمهاي انتخاب ويژگي را ميتوان به دو دسته پوششي7 و فيلتر8 تقسيم کرد. تکنيکهاي پوششي به منظور ارزيابي کيفيت زيرمجموعه ويژگيهاي انتخاب شده، از دقت طبقهبندي کننده استفاده ميکنند. در مقابل الگوريتمهاي فيلتر، از معيارهاي ديگري مانند جداسازي بين کلاسها، قدرت نمايش و غيره استفاده ميکند. اين دسته از تکنيکها داراي سرعت بالايي هستند ولي لزوماً داراي دقت طبقهبندي مناسبي نيستند [14]. با توجه به اهميت دقت طبقهبندي در اين تحقيق از روشهاي پوششي که در آن کيفيت باندهاي انتخابي به وسیله دقت طبقهبندي کنندهي ماشينهاي بردار پشتيبان بدست ميآيد، استفاده خواهد شد.
با توجه به ابعاد بالاي ورودي در تصاوير فرا طیفی، انتخاب يک زير مجموعه بهينه از باندها بدون پيش فرضي در مورد تعداد باندهاي بهينه يک مسئله بهينهسازي NP-hard ميباشد [29]. در اين راستا در سالهاي اخير الگوريتمهاي بهينهسازي مختلفي از قبيل جستجوي ممنوع9 [30]، الگوريتمهاي خرد جمعي [31, 32] و الگوريتم ژنتيک [14, 16, 33] براي حل اين موضوع ارائه گرديده است. با توجه به ساختار الگوريتم ژنتيک در حالت باينري، مسئله انتخاب ويژگي سازگاري بسيار مناسبي با الگوريتم ژنتيک دارد. لذا تحقيقات بسياري در رابطه با انتخاب ويژگي بر مبناي الگوريتم ژنتيک در زمينههاي گوناگون و با طبقهبندي کنندههاي مختلف وجود دارد [14, 33].
در سال 2006 هوئرتا و همکاران از الگوريتم ژنتيک به منظور کاهش ابعاد دادههاي پزشکی استفاده کردند. در اين تحقيق در ابتدا در مرحله پيش پردازش با منطق فازي ابعاد فضاي ورودي را کاهش داده و سپس با الگوريتم پوششي بر مبناي الگوريتم ژنتيک در فضاي کاهش يافته، ويژگيهاي بهينه انتخاب گرديد. همچنين پارامترهاي ماشينهاي بردار پشتيبان ثابت در نظر گرفته شد [14].
در سال 2008، بهاتيا و همکاران از الگوريتم ژنتيک که با اعداد صحيح کدگذاري شده بود به منظور انتخاب ويژگي با طبقهبندي کننده ماشينهاي بردار پشتيبان استفاده کردند [34]. در الگوريتم ارائه شده، طول کروموزم به تعداد ويژگيهايي است که انتخاب خواهد شد و درايههاي کروموزم شمارههاي ويژگيهاي انتخاب شده ميباشد. پارامترهاي ماشينهاي بردار پشتيبان نيز قبل از انتخاب ويژگي با بررسي چندين مقدار و انتخاب بهترين آنها محاسبه شده است [34]. محدوديت اين روش نياز به دانستن تعداد ويژگيهاي بهينه به عنوان اطلاعات از پيش تعريف شده در مسئله ميباشد. از آنجایي که اين پارامتر از قبل مشخص نيست، به ازاي مقادير مختلف آزمايش تکرار شده و زير مجموعه ويژگيها با بهترين دقت طبقهبندي انتخاب شد که البته اين روش در فضاي با ابعاد بالا امکان پذير نيست.
در سال 2009، ژانگ و همکاران الگوريتمي براي سرعت بخشيدن به انتخاب ويژگي بر مبناي الگوريتم ژنتيک ارائه دادند [16]. در این مقاله براي ارزيابي هر عضو در الگوريتم ژنتيک، ابتدا پارامترهاي ماشينهاي بردار پشتيبان با الگوريتم جستجوي شبکهاي محاسبه و سپس با ارزيابي 10 قسمتي، دقت محاسبه ميشود. به علت حجم محاسباتي بالاي اين الگوريتم از تکنيک محاسباتي موازي سازي10 در الگوريتم ژنتيک و ماشينهاي بردار پشتيبان استفاده شده است [16].
در سال 2012، سنتوس و همکاران از الگوريتم ژنتيک به منظور انتخاب ويژگي بر اساس روش فيلتر استفاده کردند و سه روش طبقهبندي ماشينهاي بردار پشتيبان، نزديکترين همسايگي و شبکههاي عصبي به منظور ارزيابي نتايج پيادهسازي شد ]35[.
از آنجایی که پارامترهاي ماشينهاي بردار پشتيبان دارای تأثیر متقابل بر زير مجموعه ويژگيهاي مورد استفاده در طبقهبندي است، راه حل بهينه در انجام طبقهبندي حل همزمان پارامترها و فضاي ويژگي ميباشد [20]. با اين وجود با بزرگ شدن فضاي جستجو و پيچيده شدن آن، نياز به استفاده از تکنيکهاي بهينهسازي قدرتمندي در اين وضعيت مطرح ميگردد. در سالهاي اخير الگوريتمهاي فرا ابتکاري متنوعي براي حل اين مسئله مانند الگوريتمهاي خرد جمعي [17, 19]، شبيهسازي تبريد تدريجي [18] و الگوريتم ژنتيک [15, 20, 36, 37] توسط محققين مختلف ارائه شده است.
در حل همزمان انتخاب مدل و ويژگي توجه به ماهيت متفاوت اين دو مسئله ضروري ميباشد که در آن پارامترهاي ماشينهاي بردار پشتيبان داراي ماهيتي پيوسته است، برخلاف ويژگيهاي ورودي که داراي ماهيتي گسسته می‌باشد. به منظور ادغام اين دو مفهوم، دو راه حل در مطالعات ارائه شده است [20, 38]. در روش اول بردار ويژگيها نيز در کنار پارامترها به صورت پيوسته مدل‌سازی شده و با استفاده از توابعي همچون سيگمويد به بازه [0,1]منتقل ميشود و براي ارزيابي ويژگيهاي انتخاب شده، اين ويژگيها به فضاي باينري منتقل ميشوند [20, 38]. در روش دوم پارامترهاي ماشينهاي بردار پشتيبان، تبديل به فرمت باينري شده و در کنار بردار ويژگيهاي انتخابي قرار ميگيرند [20].
در سال 2005، سوزا و کاروالو مقدار پارامتر تنظيم و زيرمجموعه بهينه ويژگيها را بر مبناي الگوريتم ژنتيک باینری تعیین نمودند و مقدار پارامتر کرنل در اين روش ثابت در نظر گرفته شد. همچنين در اين تحقيق تنها سه مقدار ممکن براي پارامتر تنظيم در نظر گرفته شده است [39].
در سال 2006، هوانگو وانگ پارامترهاي کرنل RBF به همراه ويژگيهاي ورودي در حالت باينري بهينه گرديد. نتايج بدست آمده در اين روش با تکنيک جستجوي شبکهاي که قابليت انتخاب ويژگي ندارد، مقايسه گرديده است که نشان می‌دهد، الگوريتم پيشنهادي با ويژگيهاي انتخاب شده به دقت بالاتري ميرسد [20].در همين سال بِگي و مِلگاني الگوريتم ژنتيک را با کروموزمهايي به طول تعداد ويژگيها به علاوه 2 (دو پارامتر کرنل) پياده سازي کردند. براي ارزيابي الگوريتم ارائه شده، از تصاوير فرا طیفی استفاده کردند [7].
در سال 2007، مِجيا-گوئواراو اکوري-مولارساز ماشین‌های بردار پشتيبان براي رگرسيون استفاده کردند که در اين حالت سه پارامتر مجهول برای ماشينهاي بردار پشتيبان وجود دارد. در اين مقاله علاوه بر ويژگي و پارامترها، احتمال ترکيب و جهش در الگوريتم ژنتيک نيز به عنوان مجهول در نظر گرفته شده است. براي نمايش راه حل با کروموزم، از کدگذاري باينري استفاده شد [36].
ژو و همکاران در سال 2008 الگوريتم ارائه شده در [20] را بر روي تصاوير فرا طیفی هايپريون آزمايش کردند و مشاهده گرديد نتايج بدست آمده نسبت به زماني که از همه باندها استفاده شده باشد، بهبود يافته است [15]. در اين مطالعه تأثیر روش پيشنهادي تنها با استفاده از يک کرنل و يک روش چند کلاسه در ماشينهاي بردار پشتيبان بررسي شد.
در سال 2009، اکوي الگوريتمي ارائه داد که علاوه بر ويژگي و پارامترها، نوع کرنل نيز در يک پروسه مبتني بر الگوريتم ژنتيک بهينه ميگرديد. در اين مقاله، از انتقال موجک براي استخراج ويژگي استفاده گرديده و براي اين منظور 16 نوع موجک و 8 نوع کرنل در نظر گرفته شده است. بعد از پايان الگوريتم، نوع موجک و کرنل بهينه به همراه پارامترهاي آن بدست ميآيد [38].
در سال 2011، ژائو و همکاران از الگوريتم ژنتيک در بهينهسازي ماشينهاي بردار پشتيبان به منظور طبقهبندي دادههاي UCI استفاده کردند ]40[. در همين سال چِن و همکاران در پيشبيني ورشکستگي بانکها از الگوريتم بهينهسازي ژنتيک به منظور بهبود عملکرد سيستم تصميمگيري بر مبنای انتخاب زيرمجموعه ويژگيهاي بهينه و تعيين پارامترهاي شبکه عصبي (پيشبيني کننده) استفاده شد ]41[.
4. تعيين طبقهبندي کننده بهينه ماشین‌های بردار پشتيبان بر مبناي الگوريتم ژنتيک
در سالهاي اخير ماشین‌های بردار پشتيبان به عنوان يکي از کاراترين طبقهبندي کنندههاي پايدار در تصاوير فرا طیفی مطرح شدهاند [3]. يکي از عوامل موثر بر عملکرد ماشین‌های بردار پشتيبان، پارامترهاي آن ميباشند [23]. انتخاب زير مجموعه بهينه به عنوان ورودي طبقهبندي يک گام مهم ديگر در بهينهسازي ماشينهاي بردار پشتيبان به منظور طبقهبندي تصاوير فرا طیفی است. هرچند ماشينهاي بردار پشتيبان در فضاي با ابعاد بالا پايدار ميباشند ولي انتخاب زيرمجموعه بهينه از ويژگيها ميتواند با حذف ويژگيهاي اضافي و زائد عملکرد طبقهبندي کننده را از لحاظ دقت، سرعت و هزينه بهبود ببخشد [16].
با توجه به عوامل تأثیرگذار بر عملکرد ماشينهاي بردار پشتيبان، به منظور تعيين يک سيستم طبقهبندي بهينه در فضاي با ابعاد بالاي تصاوير فرا طیفی، ميبايست از يک تکنيک بهينهسازي قدرتمند بهره برد [20]. الگوريتمهاي فرا ابتکاری، تکنيکهاي محاسباتي هستند که در يک پروسه تکراري با توجه به تابع هدفي که کيفيت راهحل را بيان ميکند، راهحلهاي کانديد را بهبود ميبخشند (بدون پيش فرضي راجع به مسئله) و معمولاً در فضاي جستجوي بزرگ کارا عمل ميکنند [24]. در نتيجه اين دسته الگوريتمها گزينهاي مناسب در بهينهسازي سيستم طبقهبندي تصاوير فرا طیفی بر مبناي ماشينهاي بردار پشتيبان باشند.
الگوريتم ژنتيک يک نمونه از الگوريتمهاي فرا ابتکاری ميباشد که با موفقيت در بسياري از مسائل بهينهسازي در کاربردهاي مختلف به کار گرفته شده است [14, 20, 25] . اين الگوريتم، روشي جمعيت مبنا ميباشد که در يک پروسه تکراري تکاملي کيفيت جمعيت را بهبود ميبخشد. در اين الگوريتم ابتدا ميبايست راهحل را به صورت يک رشته باينري که کروموزم ناميده ميشود، نمايش دهيم. در مرحله بعد جمعيت اوليه به صورت تصادفي ساخته و کيفيت آن به وسيله تابع هدف ارزيابي ميشود.
سه عملگر اصلي در الگوريتم ژنتيک عبارتند از: انتخاب، تلفيق و جهش. پس از اندازهگيري کيفيت اعضاء، احتمال انتخاب هر عضو براي شرکت در مرحله تلفيق مشخص ميشود و با استفاده از چرخ گردان11 کروموزمهاي منتخب مشخص و وارد نسل بعد ميشود. انتقال نخبه12 هر مرحله که مستقيماً به مرحله بعد منتقل ميشود نيز به منظور حفظ نتايج مطلوب در نظر گرفته شده است.
يک تکنيک رايج مرحله تلفيق13، روش تک نقطه‌ای14 ميباشد که در اين تحقيق نيز مورد استفاده قرار گرفته است. تلفيق تک نقطه‌ای توسط انتخاب يک نقطه به صورت تصادفي در کروموزم و تعويض اطلاعات دو کروموزم والد از نقطه مشخص شده، صورت ميپذيرد.
به منظور ارزيابي مناطق جديد در فضاي جستجو، از جهش15 استفاده ميشود تا الگوريتم قابليت جستجوي تصادفي را نيز داشته باشد. عملگر جهش باينري16 با تغيير مقدار درایه‌هایی (0 را به 1 و بالعکس) که احتمال آنها از احتمال جهش بيشتر شده است، عمل ميکند. اين پروسه تکرار ميشود تا شرط توقف (حداکثر تکرار و يا عدم تغيير بهترين مقدار در طي تکرارهاي مشخص) برقرار شود [21].
با توجه به انعطاف پذيري الگوريتم ژنتيک نسبت به ديگر روشهاي ديگر در زمينه بهينهسازي فرا ابتکاری و حساسيت کمتر آن به تعريف پارامترهاي مبنايي، در اين تحقيق از الگوريتم ژنتيک به منظور انتخاب مدل، انتخاب ويژگي و حل همزمان اين دو مسئله استفاده گرديد.
4.1. انتخاب مدل
در روش پيشنهادي اين تحقيق، با در نظر گرفتن عملگرهاي معمول در کدگذاري باينري و همچنين ذات باينري قسمتهاي بعدي، از کدگذاري باينري استفاده شده است. همچنين هر کروموزم نمايشگر دو پارامتر تنظيم و کرنل ميباشد که با يک رشته از صفر و يک تعريف ميشود (شکل 2). طول کروموزم متناسب با محدوده تغييرات پارامترها و همچنين دقت مورد نياز مسئله تعيين ميگردد.
0 | 1 | ... | 1 | 0 | 1 | 0 | ... | 0 | 1 |
شکل 2- نمايش باينري پارامترهاي ماشينهاي بردار پشتيبان
براي ارزيابي کيفيت هر عضو، می‌بایست هر يک از دو قسمت کروموزم به عدد حقيقي تبديل شود. براي اين منظور، از رابطه (6) استفاده ميکنيم.
(6)
که در اين رابطه، p مقدار حقيقي پارامتر، minp و maxp به ترتيب کمينه و بيشينه مقدار پارامتر، l تعداد بيتهاي نمايشگر پارامتر و d مقدار عددي رشته باينري در پايه 10 ميباشد.
در مرحله بعد ماشينهاي بردار پشتيبان به وسيله دادههاي آموزشي و پارامترهاي محاسبه شده، آموزش ديده و ابر صفحههاي مورد نظر ساخته ميشوند. سپس به منظور محاسبه تابع هدف، دادههاي تست به وسيله ماشينهاي بردار پشتيبان آموزش ديده، طبقهبندي ميشود و سپس ماتريس خطا تشکيل ميشود. از ضريب کاپا به علت استفاده از تمام اطلاعات ماتريس خطا، به عنوان دقت طبقهبندي و تابع هدف در اين بخش استفاده گرديد که با رابطه (7) تعريف ميشود.
(7)
در اين رابطه، N تعداد کل نمونهها، r تعداد کلاسها، xii عناصر روي قطر اصلي ماتريس خطا، xi+ جمع حاشيه اي سطرها و x+iجمع حاشيه اي ستون‌ها ميباشد. پس از ارزيابي اعضا، سه مرحله انتخاب، تلفيق و جهش بر روي فرمت باينري پارامترها انجام ميشود و جمعيت جديد ساخته ميشود و اين مراحل تکرار ميشود تا شرط توقف برقرار شود (شکل 3).
4.2. انتخاب ويژگي
انتخاب ويژگي يکي از مراحل تأثیرگذار در طبقهبندي تصاوير فرا طیفی بر مبناي ماشينهاي بردار پشتيبان می‌باشد که در آن با حذف باندهاي نامربوط و نويزي، عملکرد طبقهبندي کننده را از لحاظ دقت و سرعت بهبود ميبخشد.
در روش پيشنهادي اين تحقيق، انتخاب ويژگي بر مبناي الگوريتم ژنتيک با استفاده از تکنيک پوششي پيادهسازي شده است. در مرحله پيش پردازش روش پيشنهادي ابتدا با حضور همه باندها، مقادير در پروسه اصلي انتخاب ويژگيهاي بهينه، از کدگذاري باينري پارامترهاي ماشينهاي بردار پشتيبان با روش جستجوي شبکهاي تعيين و اين مقادير در طول پروسه انتخاب ويژگي ثابت در نظر گرفته شدند.
شکل 3- فلوچارت تعيين مقادير بهينه پارامترهاي ماشينهاي بردار پشتيبان بر مبناي الگوريتم ژنتيک
استفاده شد که در آن هر عضو جمعيت به وسيله يک رشته از 0 و 1 به طول تعداد باندهاي تصوير فرا طیفی نمايش داده ميشود (شکل 4). در اين کروموزم، مقدار بيت 0 به معناي حذف باند متناظر و 1 به معناي انتخاب آن ميباشد.
1 | 0 | 0 | 1 | 1 | ... | 1 | 0 | 1 | 0 |
طول کروموزم به تعداد باندهاي تصوير فرا طیفی |
شکل 4- نمايش کروموزم به منظور انتخاب ويژگي بر مبناي الگوريتم ژنتيک
به منظور تعريف معياري براي ارزيابي کيفيت زير مجموعه ويژگيهاي انتخاب شده، ميبايست دو پارامتر دقت طبقهبندي و تعداد ويژگيهاي انتخاب شده را در نظر گرفت. به عبارت ديگر، طبقهبندي بر مبنای زیرمجموعه ويژگيهاي مطلوب داراي دقت طبقهبندي بالاتر و تعداد ويژگيهاي انتخاب شده کمتر ميباشد. لذا تابع هدف با قرار دادن این دو معيار در يک تابع تعريف ميشود و مسئله به بيشينه سازي معادله (8) تبديل می‌شود.
(8)
در اين رابطه، f مقدار تابع هدف، w يک کميت ثابت در بازه ]1و0 [می‌باشد که وزن بين دقت طبقهبندي و تعداد ويژگيها را مشخص ميکند. همچنين accuracy، دقت طبقهبندي ميباشد که با رابطه (7) محاسبه ميشود و Nf تعداد باندهاي انتخاب شده ميباشد.
پس از ارزيابي اعضاي جمعيت، سه عملگر انتخاب، تلفيق و جهش با توجه به کيفيت هر عضو عمل ميکنند و مجدداً جمعيت ساخته شده توسط تابع هدف ارزيابي خواهد شد و اين پروسه تکرار ميشود تا شرط توقف برقرار گردد (شکل 5).
شکل 5- فلوچارت انتخاب زير مجموعه بهينه باندها بر مبناي الگوريتم ژنتيک
4.3. حل همزمان پارامتر و ويژگي
با توجه به هدف اين تحقيق که حل همزمان تعيين پارامتر و انتخاب ويژگي در اين بخش ميباشد، در روش پيشنهادي ويژگيها و پارامترهاي کرنل در کروموزم به صورت باينري کدگذاري ميشود. هر کروموزم از سه قسمت تشکيل شده است: ويژگيها، پارامتر تنظيم و پارامتر کرنل (شکل 6). طول قسمت اول به تعداد باندهاي تصوير و طول دو قسمت آخر به دقت مورد نياز براي پارامترها بستگي دارد.
1 | 0 | ... | 0 | 1 | 0 | ... | 1 | 1 | ... | 0 |
شکل 6- نمايش کروموزم به منظور حل همزمان انتخاب ويژگي و پارامترهاي کرنل
در اين مرحله بعد از ساخت جمعيت اوليه به صورت تصادفي، به منظور ارزيابي اعضاي جمعيت، با توجه به قسمت اول کروموزم (ویژگی‌های انتخاب شده) در داده هاي آموزشي با باندهاي انتخاب شده استخراج ميشود. سپس دو قسمت پارامترها با استفاده از رابطه (6) به مقدار حقيقي تبديل می‌شود و ماشينهاي بردار پشتيبان با استفاده از داده هاي آموزشي با باندهاي منتخب و پارامترهاي بدست آمده، آموزش داده ميشود. در مرحله بعد داده هاي تست توسط ماشین‌های بردار پشتيبان آموزش ديده طبقهبندي ميشوند و ماتريس خطا تشکيل و دقت طبقهبندي با رابطه (7) محاسبه ميشود. سپس با توجه به قسمت اول هر عضو که بيانگر تعداد باندهاي انتخابي است و دقت بدست آمده، مقدار تابع هدف با رابطه (8) محاسبه ميشود. در ادامه مشابه مسائل قبل، مراحل انتخاب، تلفيق و جهش انجام و اين مراحل تکرار ميشود تا شرط توقف برقرار شود (شکل 7).
شکل 7- فلوچارت تعيين مقادير بهينه پارامترهاي ماشينهاي بردار پشتيبان و زيرمجموعه بهينه باندها بر مبناي الگوريتم ژنتيک
5. نتايج عملي
به منظور ارزيابي توانايي روشهاي ارائه شده در اين تحقيق، نسبت به پيادهسازي و به کارگيري آنها در طبقهبندي تصوير فرا طیفی سنجنده AVIRIS اقدام گرديد. نتايج حاصل در قالب سه گروه: انتخاب پارامترهاي مدل، انتخاب ويژگي و حل همزمان هردو شرح داده شده است. در ماشينهاي بردار پشتيبان از دو کرنل گوسين و پلينوميال و دو روش چند کلاسه «يک در مقابل يک» و «يک در مقابل مابقي» استفاده شده است. به منظور مقايسه نتايج بدست آمده، الگوريتم شبيهسازي تبريد تدريجي نيز پيادهسازي شد.
5.1. مشخصات داده
براي پياده سازي الگوريتمهاي ارائه شده از تصوير فرا طیفی مربوط به منطقه اي کشاورزي-جنگلي که توسط سنجنده AVIRIS در سال 1992 از شمال شرقي ايالت اينديانا اخذ شده، استفاده گرديد. به دليل شباهت بين کلاسها، اين تصوير داراي پيچيدگيهايي براي طبقه بندي است. اين تصوير داراي 220 باند ميباشد که 15 باند نويزي و 20 باند جذبي آب حذف گرديد و در نهايت از 185 باند باقيمانده استفاده شد. تصوير داراي 145×145 پيکسل، دقت راديومتريک 8 بيت و داراي 16 کلاس می‌باشد که برخي از کلاسها به دليل کوچک بودن تعداد نمونههاي آموزشي براي ارزيابي مناسب نميباشد. به همين علت از 9 کلاس که بيشترين داده را در مقايسه با ديگر کلاسها داشتند، در اين تحقيق استفاده شده است.
5.2. تنظيم پارامترها
به منظور تعيين پارامترهاي ماشينهاي بردار پشتيبان و فضاي ويژگي، پارامترهاي الگوريتم ژنتيک ميبايست تنظيم شوند. پارامترهاي مورد استفاده در الگوريتم ژنتيک به صورت تجربي و با آزمون و خطا طبق جدول 1 بدست آمدند.
تعداد بيتهاي مورد نياز براي نمايش پارامتر تنظيم، پارامتر کرنل گوسين و درجه پلينوميال به ترتيب 20، 22 و 4 تعيين شدند. در پروسه انتخاب ويژگي و حل همزمان تعيين پارامترها و انتخاب ويژگي با در نظر گرفتن ابعاد بزرگ فضاي جستجو و به منظور تعيين جمعيت اوليه مناسب ابتدا يک جمعيت با ابعاد بزرگ به صورت اوليه ساخته ميشود و سپس اعضاي برتر به عنوان جمعيت اوليه انتخاب ميشود. همچنين در تابع هدف، مطابق معادله (8) با توجه به اهميت بيشتر دقت نسبت به تعداد ويژگي، w=0.8 در نظر گرفته شد.
جدول1- پارامترهاي الگوريتم ژنتيک
روش | پارامتر | مقدار |
انتخاب مدل | سايز جمعيت | 5 |
طول کروموزم (گوسين) | 42 | |
طول کروموزم (پلينوميال) | 24 | |
انتخاب ويژگي | سايز جمعيت اوليه | 300 |
سايز جمعيت | 30 | |
طول کروموزم | 185 | |
حل همزمان تعيين پارامتر و انتخاب ويژگي | سايز جمعيت اوليه | 500 |
سايز جمعيت | 50 | |
طول کروموزم (گوسين) | 227 | |
طول کروموزم (پلينوميال) | 209 | |
پارامترهای عمومی | نرخ تلفيق | 5/0 |
نرخ جهش | 05/0 | |
حداکثر تکرار | 300 | |
|
|
|
پارامترهاي الگوريتم شبيهسازي تبريد تدريجي نيز به گونه‌ای تنظيم شدهاند که داراي حجم محاسباتي يکسان با الگوريتم ژنتيک باشند. همچنين پارامتر دماي اوليه و نرخ کاهش دما، به ترتيب 1000 و 01/0 در نظر گرفته شد.
5.3. ارزيابي نتايج
يکي از پارامترهاي تأثیرگذار در طبقه بندي، تعيين معياري براي ارزيابي نتايج ميباشد. براي اين منظور ابتدا 50% دادهها به صورت تصادفي به داده آموزشي و 50% باقيمانده به داده تست تخصيص داده شد. ماشينهاي بردار پشتيبان بر روي دادههاي آموزشي، آموزش ديده و ماتريس خطا با استفاده از داده تست تشکيل داده شد. دو معيار کلي ارزيابي دقت که از ماتريس خطا محاسبه ميشوند، عبارتند از: ضريب کاپا که با رابطه (7) محاسبه و دقت کلي که به رابطه (9) محاسبه می‌گردد.
(9)
در اين رابطه، N تعداد کل نمونهها، r تعداد کلاسها و xii عناصر روي قطر اصلي ماتريس خطا ميباشد معيار ديگري که براي بررسي نتايج استفاده گرديد، دقت براي هر کلاس می‌باشد که با رابطه (10) محاسبه می‌شود.
(10)
از آنجایی که ضريب کاپا و دقت کلي معيارهايي کلي براي طبقهبندي ميباشد، استفاده از دقت هر کلاس ميتواند به صورت مناسب نمايانگر نحوه پخش خطا در بين کلاسها باشد. از این رو در اين تحقيق در کنار معيارهاي کلي، از دقت هر کلاس نيز استفاده گرديد. در ادامه نتايج بدست آمده در 3 رويکرد بيان شده، ارائه گرديده است.
5.3.1. نتايج انتخاب پارامترهاي بهينه مدل
به منظور ارزيابي اثر هر يک از پارامترهاي ماشينهاي بردار پشتيبان (C, d,) بر روي دقت طبقهبندي تصاوير فرا طیفی، روند ذيل انجام پذيرفت. ابتدا در کرنل گوسين، پارامتر کرنل ثابت در نظر گرفته شد و دقت طبقهبندي بر اساس تغييرات پارامتر C محاسبه شد (شکل 8- الف). سپس با تغيير پارامتر و ثابت نگه داشتن پارامتر C، اثر پارامتر کرنل گوسين اندازهگيري شد (شکل 8- ب). در نهايت در کرنل پلينوميال، اثر درجه آن بر دقت طبقهبندي بدست آمد (شکل 8- ج).
(الف)
(ب)
(ج)
شکل8- تأثیر پارامترهاي ماشينهاي بردار بر دقت طبقهبندي، الف) تأثیر پارامتر تنظيم ب) تأثیر پارامتر کرنل گوسين ج) تأثیر درجه پلي نوميال
همان طور که در شکل 8 ديده می‌شود، هر سه پارامتر تأثیر بسزايي بر عملکرد طبقهبندي کننده دارند و در نتيجه تعيين مقدار بهينه اين پارامترها از تأثیر بسزايي در دقت طبقهبندي برخوردار ميباشد. از این رو در اين مرحله از جستجوي شبکهاي، الگوريتم شبيهسازي تبريد تدريجي و الگوريتم ژنتيک براي تعيين مقادير بهينه پارامترهاي دو کرنل گوسين و پلينوميال استفاده گرديد. به منظور تعيين پارامترهاي ماشينهاي بردار پشتيبان مبتني بر اين سه روش، پارامترهاي 
و d به ترتيب در بازههاي 
، 
و 
در نظر گرفته شدند. نمودار همگرايي انتخاب مدل بر مبناي الگوريتم شبيهسازي تبريد تدريجي و الگوريتم ژنتيک به ترتيب در شکلهاي 9 و 10 نمايش داده شده است. نمودار همگرايي الگوريتم ژنتيک حاکي از همگرايي سريع آن (حداکثر 30 تکرار) به مقدار بهينه می‌باشد؛ در حالی که الگوريتم شبيهسازي تبريد تدريجي نياز به تکرارهاي بيشتري براي همگرايي دارد.
به منظور مقايسه نتايج بدست آمده، روش کلاسيک جستجوي شبکهاي پياده سازي گرديد. تغيير نمايي پارامترهاي تنظيم و کرنل گوسين در اين روش به صورت تجربي بدست آمده است. ابتدا دقت طبقه‌بندی با تمام زوج پارامترها در هر کرنل محاسبه و در نهايت، زوج پارامتر با بيشترين دقت طبقهبندي به عنوان مقادير نهايي ماشينهاي بردار پشتيبان انتخاب شدند. از آنجایی که الگوريتم جستجوي شبکهاي به منظور تعيين مقادير بهينه پارامترها جستجوي جامع انجام می‌دهد، می‌توان انتظار داشت که دقت بدست آمده از اين روش، دقتي نزديک به بهينه باشد و در نتيجه معيار مناسبي به منظور مقايسه با الگوريتم ژنتيک و شبيهسازي تبريد تدريجي باشد.
شکل 9- نمودار همگرايي تعيين پارامترهاي ماشينهاي بردار پشتيبان بر مبناي الگوريتم شبيهسازي تبريد تدريجي براي کرنل گوسين و پلينوميال در دو حالت يک در مقابل يک و يک در مقابل مابقي
شکل 10- نمودار همگرايي تعيين پارامترهاي ماشينهاي بردار پشتيبان بر مبناي الگوريتم ژنتيک براي کرنل گوسين و پلينوميال در دو حالت يک در مقابل يک و يک در مقابل مابقي
مقادير بهينه پارامترها و دقت متناظر با آن، براي دو کرنل گوسين و پلينوميال در دو حالت چند کلاسه، يک در مقابل يک و يک در مقابل مابقي در جدول 2 ارائه شده است. همچنين دقت هر کلاس با رابطه (10) محاسبه و در جدول 2 ارائه شده است.
همان طور که در جدول2 نشان داده شده است، دقت کلي طبقهبندي در روشهاي الگوريتم ژنتيک، شبيهسازي تبريد تدريجي و جستجوي شبکهای نزديک به هم ميباشد. با توجه به حجم محاسباتي کمتر الگوريتم ژنتيک، سرعت همگرايي بالا و عدم جستجوي جامع، ميتواند در زمان محاسباتي کمتر، به دقتي نزديک و يا بالاتر از الگوريتم جستجوي شبکهاي و شبيهسازي تبريد تدريجي برسد. ولي نحوه پخش خطا در سه روش متفاوت است. از این رو در برخي از کلاسها، دقت تعيين پارامتر بر مبناي الگوريتم ژنتيک، در برخي الگوريتم شبيهسازي تبريد تدريجی و در برخي کلاسها الگوريتم جستجوي شبکهاي به دقت بالاتري رسيده است.
[1] 1 Hughes phenomena
[2] 2 Over-fitting
[3] 3 Support Vector Machines
[4] 1 Meta-heuristic
[5] 2 Exploration
[6] 3 Exploitation
[7] 1Wrapper
[8] 2Filter
[9] 3Tabu Search
[10] 1 Parallelization
[11] 1 Roulette wheel
[12] 2 Elite
[13] 3 Crossover
[14] 4 Single Point
[15] 5 Mutation
[16] 6 Bit-Flip
جدول2- نتايج تعيين پارامترهاي بهينه بر مبناي الگوريتم ژنتيک، شبيهسازي تبريد تدريجي و جستجوي شبکهاي
ضريب کلي | کاپا | کلاس 9 | کلاس 8 | کلاس 7 | کلاس 6 | کلاس 5 | کلاس 4 | کلاس 3 | کلاس 2 | کلاس 1 | پارامتر کرنل | پارامتر تنظيم | تکنيک | ||
83/84 | 82/0 | 594/0 | 872/0 | 868/0 | 569/0 | 982/0 | 653/0 | 1 | 1 | 816/0 | 2048 | 64 | شبکهاي | گوسين، يک در مقابل يک | |
47/85 | 828/0 | 562/0 | 882/0 | 869/0 | 642/0 | 982/0 | 702/0 | 1 | 1 | 77/0 | 2208 | 304/313 | SA | ||
47/85 | 828/0 | 595/0 | 872/0 | 868/0 | 642/0 | 982/0 | 7/0 | 1 | 1 | 785/0 | 61/2488 | 22/220 | GA | ||
62/84 | 819/0 | 725/0 | 819/0 | 912/0 | 492/0 | 1 | 79/0 | 1 | 1 | 722/0 | 4096 | 1024 | شبکهاي | گوسين، يک در مقابل مابقي | |
62/84 | 819/0 | 725/0 | 808/0 | 912/0 | 54/0 | 1 | 767/0 | 1 | 1 | 723/0 | 262/3852 | 044/932 | SA | ||
33/84 | 821/0 | 725/0 | 819/0 | 912/0 | 541/0 | 1 | 767/0 | 1 | 1 | 723/0 | 95/3891 | 93/950 | GA | ||
42/78 | 746/0 | 658/0 | 672/0 | 912/0 | 453/0 | 964/0 | 546/0 | 1 | 971/0 | 734/0 | 3 | 64 | شبکهاي | پلينوميال، يک در مقابل يک | |
42/78 | 746/0 | 658/0 | 672/0 | 912/0 | 453/0 | 964/0 | 546/0 | 1 | 971/0 | 734/0 | 3 | 02/65 | SA | ||
42/78 | 746/0 | 658/0 | 672/0 | 912/0 | 453/0 | 964/0 | 546/0 | 1 | 971/0 | 734/0 | 3 | 61/67 | GA | ||
44/72 | 677/0 | 657/0 | 489/0 | 736/0 | 518/0 | 1 | 517/0 | 1 | 941/0 | 597/0 | 8 | 512 | شبکهاي | پلينوميال، يک در مقابل مابقي | |
65/72 | 68/0 | 656/0 | 489/0 | 736/0 | 545/0 | 1 | 517/0 | 1 | 941/0 | 598/0 | 669/7 | 37/209 | SA | ||
65/72 | 68/0 | 656/0 | 489/0 | 736/0 | 545/0 | 1 | 517/0 | 1 | 941/0 | 598/0 | 6/7 | 661 | GA | ||
5.3.2. نتايج انتخاب ويژگي
در اين قسمت هدف يافتن زيرمجموعهاي از ويژگيهاي بهينه تصوير فرا طیفی به منظور طبقهبندي با بيشترين کارایی ميباشد. در اين قسمت پارامترهاي ماشينهاي بردار پشتيبان، در حضور تمام باندها و با استفاده از الگوريتم جستجوي شبکهاي بدست آمده و مقدار آنها در طول پروسه انتخاب ويژگي ثابت در نظر گرفته ميشود.
شکل 11 و 12 به ترتيب نمودار همگرايي الگوريتم شبيهسازي تبريد تدریجی و الگوريتم ژنتيک براي 4 مورد در نظر گرفته شده را نشان ميدهد. همان طور که در اين دو شکل ديده ميشود، انتخاب ويژگي موجب بهبود قابل توجهي بر دقت کرنلهاي پلينوميال و گوسين ميشود. با توجه به شکلهاي 9 و 10، کرنل گوسين دقت بسيار بالاتري نسبت به کرنل پلينوميال دارد ولي پروسه انتخاب ويژگي با تأثیر بالايي که بر کرنل پلينوميال داشته، باعث نزديکي دو کرنل در دو حالت يک در مقابل يک و يک در مقابل مابقي گرديده است که حاکي از تأثیر بيشتر انتخاب ويژگي بر کرنل پلينوميال نسبت به کرنل گوسين ميباشد. نکته ديگر تفاوت در سرعت همگرايي دو کرنل ميباشد. با توجه به شکل 12، کرنل گوسين در تکرارهاي کمتري به دقت بهينه همگرا ميشوند، از طرف مقابل دقت کرنل پلينوميال تا تکرارهاي پاياني افزايش پيدا ميکند و به تکرارهاي بيشتري براي رسيدن به ثبات احتياج دارد.
به منظور مقايسه دقيقتر نتايج در سه حالتي که از همه باندها استفاده شده باشد و نتايج بعد از مرحله انتخاب ويژگي توسط الگوريتم شبيهسازي تبريد تدريجي و ژنتيک، معيارهاي ضريب کاپا، دقت کلي و دقت هر کلاس، به کار گرفته شد (جدول 3). نتايج نشان ميدهند با حذف ويژگيهاي اضافي نه تنها سرعت طبقهبندي بالا ميرود بلکه دقت آن نيز افزايش مييابد.
شکل 11-نمودار همگرایی انتخاب ویژگی بر مبناي الگوريتم شبيهسازي تبريد تدريجي براي کرنل گوسين و پلينوميال در دو حالت يک در مقابل يک و يک در مقابل مابقي
شکل 12-نمودار همگرايي انتخاب ویژگی بر مبناي الگوريتم ژنتيک براي کرنل گوسين و پلينوميال در دو حالت يک در مقابل يک و يک در مقابل مابقي
جدول3-نتايج حاصل از انتخاب ويژگي بر مبناي الگوريتم ژنتيک و شبيهسازي تبريد تدريجي در مقايسه با حضور همه باندها
دقت کلي | ضريب کاپا |
| کلاس 9 | کلاس 8 | کلاس 7 | کلاس 6 | کلاس 5 | کلاس 4 | کلاس 3 | کلاس 2 | کلاس 1 | تعداد باندها | تکنيک | |
83/84 | 82/0 |
| 594/0 | 872/0 | 868/0 | 569/0 | 982/0 | 653/0 | 1 | 1 | 816/0 | 185 | همه باندها | گوسين، يک در مقابل يک |
61/87 | 853/0 |
| 628/0 | 908/0 | 868/0 | 641/0 | 1 | 745/0 | 1 | 1 | 82/0 | 81 | SA | |
46/88 | 864/0 |
| 694/0 | 887/0 | 868/0 | 717/0 | 1 | 723/0 | 1 | 1 | 851/0 | 102 | GA | |
62/84 | 819/0 |
| 725/0 | 819/0 | 912/0 | 492/0 | 1 | 789/0 | 1 | 1 | 722/0 | 185 | همه باندها | گوسين، يک در مقابل مابقي |
04/85 | 823/0 |
| 725/0 | 83/0 | 912/0 | 469/0 | 1 | 747/0 | 1 | 1 | 783/0 | 82 | SA | |
11/86 | 836/0 |
| 759/0 | 844/0 | 912/0 | 514/0 | 1 | 725/0 | 1 | 1 | 816/0 | 99 | GA | |
42/78 | 746/0 |
| 658/0 | 672/0 | 912/0 | 453/0 | 964/0 | 546/0 | 1 | 971/0 | 734/0 | 185 | همه باندها | پلينوميال، يک در مقابل يک |
12/83 | 805/0 |
| 795/0 | 785/0 | 912/0 | 485/0 | 982/0 | 659/0 | 1 | 971/0 | 749/0 | 96 | SA | |
04/85 | 825/0 |
| 827/0 | 773/0 | 912/0 | 636/0 | 1 | 633/0 | 1 | 1 | 797/0 | 94 | GA | |
44/72 | 677/0 |
| 657/0 | 489/0 | 736/0 | 518/0 | 1 | 517/0 | 1 | 941/0 | 597/0 | 185 | همه باندها | پلينوميال، يک در مقابل مابقي |
62/81 | 796/0 |
| 691/0 | 744/0 | 823/0 | 559/0 | 982/0 | 614/0 | 1 | 941/0 | 783/0 | 103 | SA | |
97/83 | 812/0 |
| 79/0 | 731/0 | 825/0 | 661/0 | 1 | 679/0 | 958/0 | 1 | 801/0 | 81 | GA | |
در تمام موارد الگوريتم ژنتيک به دقتي بالاتر از الگوريتم شبيهسازي تبريد تدريجي دست يافت. همچنين در نتايج بدست آمده از الگوريتم ژنتيک با کرنل گوسين در حالت يک در مقابل يک، مرحله انتخاب ويژگي با حذف 83 باند اضافي، توانست دقت طبقه بندي را نسبت به حالتی که تمام باندها حضور دارند، 4% بهبود ببخشد. در مورد کرنل گوسين و در حالت يک در مقابل همه، 86 باند اضافي حذف و دقتي 2% بالاتر از زمان حضور همه باندها حاصل گرديد.
کرنل پلينوميال با حذف باندهاي بيشتر، افزايش دقت بيشتري نسبت به کرنل گوسين حاصل نمود. در حالت چند کلاسهي يک در مقابل يک، دقت طبقهبندي با حذف 91 باند اضافي، 7% افزايش يافت. در بين کرنلهاي در نظر گرفته شده، کرنل پلينوميال در حالت يک در مقابل مابقي، با حذف بيشترين باندهاي اضافي، بالاترين افزايش دقت را داشت. در اين مورد، بيش از نيمي از باندها (104 باند) حذف گرديد و دقت 11% افزايش يافت. همچنين دقت هر کلاس هم پس از انتخاب ويژگي در اکثر موارد افزايش بهبود قابل توجهي نسبت به حضور همه باندها داشته است.
5.3.3. نتايج حل همزمان انتخاب مدل و ويژگي
با توجه به تأثیر مقدار پارامترها در نحوه انتخاب زيرمجموعهي بهينه ويژگيها و بالعکس، در اين مرحله نسبت به تعيين همزمان مقادير پارامترها و ويژگيها اقدام گرديد. شکلهاي13 و 14 به ترتيب نمودار همگرايي الگوريتم شبيهسازي تبريد تدريجي و الگوريتم ژنتيک را براي 4 وضعيت در نظر گرفته شده نشان می‌دهند. با توجه به اين دو شکل با در نظر گرفتن همزمان پارامترها و ويژگيها، دقت طبقهبندي بدست آمده بيشتر تحت تأثیر نوع کرنل ميباشد و تأثیر نوع روش چند کلاسه کاهش يافته است. از طرف ديگر با توجه به بزرگ بودن ابعاد فضاي جستجو در اين بخش، زمان يافتن جواب بهينه نيز در هر 4 وضعيت افزايش يافت.
بهمنظور ارزيابي دقيقتر نتايج، مقادير پارامترهاي ماشينهاي بردار پشتيبان، تعداد باندهاي انتخابي، ضريب کاپا و دقت کلي به عنوان معيارهاي دقت کلي و دقت کلاسها به صورت مجزا در جدول 4 ارائه شده است.
شکل 13- نمودار همگرایی تعيين همزمان پارامترهاي ماشينهاي بردار پشتيبان و زيرمجموعه بهينه ويژگي بر مبناي الگوريتم شبيهسازي تبريد تدریجی براي کرنل گوسين و پلينوميال در دو حالت يک در مقابل يک و يک در مقابل مابقي
شکل 14-نمودار همگرايي تعيين همزمان پارامترهاي ماشينهاي بردار پشتيبان و زير مجموعه بهينه ويژگي بر مبناي الگوريتم ژنتيک براي کرنل گوسين و پلينوميال در دو حالت يک در مقابل يک و يک در مقابل مابقي
جدول4- نتايج حاصل از حل همزمان تعيين پارامترها و انتخاب ويژگي بر مبناي الگوريتم ژنتيک و شبيهسازي تبريد تدريجي
دقت کلي | ضريب کاپا | کلاس 9 | کلاس 8 | کلاس 7 | کلاس 6 | کلاس 5 | کلاس 4 | کلاس 3 | کلاس 2 | کلاس 1 | پارامتر کرنل | پارامتر تنظيم | تعداد باندها | روش | وضعيت |
96/86 | 846/0 | 626/0 | 885/0 | 868/0 | 691/0 | 982/0 | 747/0 | 1 | 1 | 788/0 | 51/1550 | 339/627 | 81 | SA | گوسين- يک در مقابل يک |
53/89 | 876/0 | 794/0 | 91/0 | 912/0 | 644/0 | 1 | 769/0 | 1 | 1 | 851/0 | 5/2057 | 16/181 | 90 | GA | |
96/86 | 846/0 | 793/0 | 809/0 | 912/0 | 568/0 | 1 | 769/0 | 1 | 1 | 85/0 | 26/2829 | 753/289 | 78 | SA | گوسين- يک در مقابل مابقي |
1/89 | 871/0 | 725/0 | 887/0 | 913/0 | 69/0 | 1 | 768/0 | 1 | 1 | 852/0 | 23/2093 | 67/565 | 98 | GA | |
62/81 | 784/0 | 727/0 | 705/0 | 912/0 | 657/0 | 964/0 | 522/0 | 1 | 97/0 | 798/0 | 196/5 | 339/627 | 93 | SA | پلينوميال- يک در مقابل يک |
47/85 | 829/0 | 828/0 | 831/0 | 912/0 | 689/0 | 1 | 611/0 | 1 | 971/0 | 737/0 | 6/4 | 1/404 | 89 | GA | |
2/81 | 78/0 | 869/0 | 689/0 | 78/0 | 634/0 | 1 | 548/0 | 1 | 941/0 | 765/0 | 968/4 | 184/955 | 88 | SA | پلينوميال- يک در مقابل مابقي |
19/84 | 814/0 | 792/0 | 769/0 | 824/0 | 712/0 | 1 | 596/0 | 1 | 94/0 | 818/0 | 10 | 15/738 | 89 | GA |
مقايسه نتايج اين بخش با مراحل قبل، حاکي از رسيدن به دقتهاي بالاتري در هر چهار وضعيت ميباشد که نشان از بهينه بودن نتايج در حل همزمان ميباشد. همچنين مقايسه نتايج حاصل از دو روش حاکي از برتري بيشتر الگوريتم شبيهسازي تبريد تدريجي نسبت به الگوريتم ژنتيک ميباشد که بيانگر توانايي الگوريتم ژنتيک در فضاي جستجوي پيچيده ميباشد.
5.3.4. مقايسه نتايج
به منظور مقايسه بهتر بين نتايج بدست آمده، منحني همگرايي الگوريتم ژنتِکدر سه رويکرد ارائه شده (تعيين پارامترها، انتخاب ويژگي و حل همزمان هر دو) را بر روي 4 وضعيت در نظر گرفته شده، در شکل 15 نمايش داده شد. همان طور که در اين شکل ديده ميشود، تعيين پارامترهاي بهينه ماشينهاي بردار پشتيبان در تکرارهاي اوليه به همگرايي رسيده و نسبت به دو رويکرد ديگر بهبود کمتري در دقت ايجاد کرده است. در حالی که، انتخاب ويژگي با توجه به استفاده از پارامترهاي بدست آمده از جستجوي شبکهاي دقت را نسبت به تعيين پارامترها افزايش داده است. در نهايت حل همزمان پارامترها و انتخاب ويژگي بالاترين دقت را در 4 وضعيت دارد. همچنين ميتوان از شکل 12 نتيجه گرفت با توجه به افزايش دقت بيشتر در حل همزمان براي کرنل گوسين، تأثیر پارامترها بر فضاي ورودي در اين کرنل بيشتر از کرنل پلينوميال ميباشد.
6. نتيجه گيري و پيشنهادات
در اين تحقيق سه رويکرد در ايجاد يک طبقهبندي کننده بهينه مبتني بر ماشينهاي بردار پشتيبان بر مبناي الگوريتم ژنتيک ارائه گرديد. نتايج حاصل در مقايسه با الگوريتم شبيهسازي تبريد تدريجي، بيانگر برتري الگوريتم ژنتيک به خصوص با افزايش ابعاد فضاي جستجو ميباشد. همچنين نتايج بهينه با به‌کارگیری الگوريتم ژنتيک در حل همزمان تعيين پارامتر و انتخاب ويژگي حاصل ميشود که در آن با انتخاب باندهاي کمتر، دقت بالاتر حاصل شد. از این رو با استفاده از طبقهبندي کنندهي کارا و قدرتمند ماشین‌های بردار پشتيبان در کنار
الگوريتم بهينه سازي و فرا ابتکاری ژنتيک، ميتواند يک سيستم طبقهبندي ترکيبي بهينه براي تصاوير فرا طیفی طراحي کرد.
پيشنهاد ميشود در تحقيقات آينده با توجه به بزرگ بودن فضاي جستجوي مسئله ارائه شده از الگوريتمهاي فرا ابتکاری ديگر از قبيل روشهاي مبني بر خرد جمعی به منظور بهينهسازي ماشينهاي بردار پشتيبان در تصاوير فرا طیفی استفاده گردد. همچنين بهينهسازي اتوماتيک پارامترهاي الگوريتم ژنتيک که در اين نوشته با آزمون و خطا بدست آمد، از موضوعات ديگر پيش رو ميباشد.
| |||
|
| ||
|
| ||
شکل 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.