International Journal of Industrial Engineering & Production Management (2013)

-144144-24523

February 2013, Volume 23, Number 4
pp. 485-501

http://IJIEPM.iust.ac.ir/

Presenting a Multi-Objective Mathematical Optimization
Model for Classification in Data Mining

A. Kazemi* & S. Aboutaleb
Abolfazl Kazemi, Assistant Professor, Faculty of Industrial and Mechanical Engineering, Qazvin Branch, Islamic Azad University,
Siamak Aboutaleb, M.Sc, Faculty of Industrial and Mechanical Engineering, Qazvin Branch, Islamic Azad University, siamak_a84@yahoo.com

Keywords 1ABSTRACT

Data Mining, In this paper we investigate the issues of data classification (as one
Optimization Model of Classification, of the branches of data mining science) in form of multi-objective Multi-Objective Mathematical mathematical programming model. The model that we present and Programming, investigate is a MODM problem. First time, based on support vector
1268732040127

Downloaded from ijiepm.iust.ac.ir at 14:44 IRST on Saturday November 4th 2017

Downloaded from ijiepm.iust.ac.ir at 14:44 IRST on Saturday November 4th 2017

Support Vector Machine machine (SVM) idea (To maximize the margin of two groups), a multi-criteria mathematical programming model was proposed for data mining problems to classified instances in two separated group based on two goals of data discriminate (To maximize the distance between different groups and to minimize the misclassification of observations). Since then, some people have been working on developing the classification models based on mathematical programming methods. Simultaneously and also independently, individuals worked on support vector machine methods to improve them. Regarding to the same philosophy of these two groups of optimization methods, in this paper, to fill the gap between these two research paths, we use the updated and improved SVM methods to present a model for classification in data mining based on multiobjective programming.
© 2013 IUST Publication, IJIEPM. Vol. 23, No. 4, All Rights Reserved

*
Corresponding author. Abolfazl Kazemi Email: abkaazemi@qiau.ac.ir
-116839-1453591

ارائه یک مدل بهینه سازی ریاضی چند هدفه برای طبقه بندی در
داده کاوی

ابوالفضل کاظمی* و سیامک ابوطالب

کلمات کلیدی چکیده:
داده کاوي ، مدل بهينه سازي طبقه بندي، برنامه ريزي رياضي چند هدفه ، ماشين بردار پشتيبان.

-1662316985

در اين مقاله به بررسي مسائل طبقه بندي داده ها )به عنوان يکي از شاخه هاي علم داده کاوي( در قالب مدل برنامه ريزي رياضي چند هدفه مي پردازيم. مدلي که ارائه و بررسي مي گردد يک مسئله MODM مي باشد. اولين بار بر پايه ايده ماشين بردار پشتيبان (SVM) )ماکزيمم کردن حاشيه دو گروه(، يک مدل برنامه ريزي رياضي چند معياره براي مسائل داده کاوي بر پايه طبقه بندي مشاهدات به دو گروه مجزا مبتني بر دو هدف تفکيک داده ها )ماکزيمم کردن فاصله بين گروه هاي مختلف و مينيمم کردن طبقه بندي نادرست داده هاي مورد مشاهده( معرفي شد و از آن پس تاکنون ضمن اينکه افراد زيادي روي گسترش مدلهاي طبقه بندي مبتني بر روش هاي برنامه ريزي رياضي کار کرده اند ،همزمان و به صورت مستقل افرادي نيز روي بهبود روش هاي ماشين بردار پشتيبان مطالعه نموده اند. با توجه به فلسفه يکسان اين دو دسته از روش هاي بهينه سازي، در اين مقاله به منظور پر کردن شکاف بين اين دو مسير پژوهش، از روش هاي به روز و بهبود يافته SVM جهت ارائه مدلي به منظور طبقه بندي در داده کاوي مبتني بر برنامه ريزي چند هدفه استفاده خواهد شد.
-1371560989

9. مقدمه9
از دهه 08 ميلادي، با توسعه علوم و ارتباطات در جوامع بشري و انباشته شدن حجم عظيمي از داده هاي تجاري و علمي، نياز به کسب دانش از داده هاي انباشته به صورت قابل ملاحظه اي افزايش يافت. اين حجم عظيم داده ها که روز به روز به آنها اضافه مي گردد، عموما حاوي اطلاعات مهمي بوده که استخراج آنها از پايگاه هاي داده و پردازش آنها به آساني امکان پذير نيست. اين نياز روز افزون، منجر به رشد سريع دانش داده کاوي2 گرديد .
داده کاوي به مفهوم استخراج اطلاعات و دانش از پايگاه هاي داده در راستاي کشف الگوها و مفاهيمي که به سادگي قابل درک
تاریخ وصول: 91/9/19 تاریخ تصویب: 1/8/19
*نویسنده مسئول مقاله: دکتر ابوالفضل کاظمی، استاديار دانشکده صنايع و
مکانيک، دانشگاه آزاد اسلامي واحد قزوين، قزوين، ايران
abkaazemi@qiau.ac.ir
سیامک ابوطالب، کارشناسي ارشد مهندسي صنايع، دانشکده صنايع و مکانيک ،دانشگاه آزاد اسلامي واحد قزوين، قزوين، ايران Data Mining siamak_a84@yahoo.com 2
1268732040127

Downloaded from ijiepm.iust.ac.ir at 14:44 IRST on Saturday November 4th 2017

Downloaded from ijiepm.iust.ac.ir at 14:44 IRST on Saturday November 4th 2017

نيستند، مي باشد. داده کاوي يکي از مراحل فرآيند کشف دانش در پايگاه داده ها )KDD( مي باشد. يکي از بهترين تعاريف براي «کشف دانش در پايگاه داده» توسط Fayyad و همکاران ارائه شده است ]1[. بر اساس اين تعريف KDD يک فرآيند تکرار پذير و تعاملي و داراي چندين مرحله مي باشد که «داده کاوي» قسمتي از اين فرآيند مي باشد. در تحقيقات صورت گرفته، داده کاوي بيشترين توجه را در بين مراحل مختلف KDD به خود معطوف کرده است و گاهاً در برخي از روشها، با قسمتي از مراحل قبل و بعد از خود ادغام شده است .«کشف دانش در پايگاه داده» فرآيند غيربديهي شناسايي الگوهاي معتبر، جديد، بالقوه مفيد و سرانجام قابل درک در داده ها مي ياشد که در حالت کلي داراي گامهاي زير است ]1[:
درک دامنه، تعريف مسئله و جمع آوري داده ها
پيش پردازش داده ها )آماده سازي داده ها جهت داده کاوي(
داده کاوي )کشف الگوها از داده ها(

پس پردازش الگوها )آماده سازي الگوها جهت استفاده ازدانش کشف شده(
استفاده از دانش کشف شده و پايش سيستم يکي از کاربردهاي مهم داده کاوي در طبقه بندي1 داده ها مي باشد .
در مسائل طبقه بندي، هر رکورد از مجموعه داده ها در قالب نقاطي در فضاي ورودي يا فضاي ويژگي توسط يک يا چند ابر صفحه از يکديگر جدا ميگردند. اين ايده، منجر به طراحي الگوريتمي مي شود که در آن دسته بندي کننده از طريق حل يک مدل برنامه ريزي رياضي چند هدفه توليد مي شود ]2[. الگوريتم هاي داده کاوي که براي ساخت مدل طبقه بندي کننده استفاده مي شوند، در زمره الگوريتم هاي يادگيري قرار مي گيرند. يادگيري ماشيني) ML(، به عنوان يکي از شاخه هاي وسيع و پرکاربرد هوش مصنوعي )AI(، با استخراج قوانين معنيدار از داده هاي خام ذخيره شده، مبناي علمي و فني مناسبي را براي دانش دادهکاوي ايجاد نموده است. روشهاي يادگيري ماشيني شامل شيوه ها و الگوريتم هايي مي باشند که بر اساس آنها رايانه ها )در کلي ترين مفهوم آن( به منظور کشف رفتار داده ها، توانايي تعلتعلُم و يادگيري پيدا مي کنند ]3[.
در طبقهبندي از تکنيکهاي گسترده اي مانند درخت تصميم ، شبکههاي عصبي، نزديکترين k همسايه3، نيو-بيز4، تحليل تفکيک خطي و غيرخطي و تکنيکهاي بهينه سازي رياضي استفاده مي گردد ]3[. استفاده از روشهاي مبتني بر بهينه سازي، منجر به ارتقاي مبناي تئوري و همچنين گسترش کاربرد عملي داده کاوي شده است. تغيير دادن پارامترهاي يک طبقه بندي کننده، موجب دوران و حرکت انتقالي ابرصفحه مي شود. با تغيير دادن موقعيت مرز تصميم، کيفيت طبقه بندي کننده دچار تغيير و خطاي طبقه بندي کمينه مي شود. کمينه سازي اين خطا از طريق بهينه سازي پارامترهاي طبقه بندي کننده، و به کمک يادگيري ميسر مي شود. اگر طبقه بندي کننده، يک تابع خطي از پارامترهايش بوده و مشتق پذير باشد، مي توان به يک فرمول از نوع بسته رسيد. ممکن است که راه حلي با چنين ويژگي، يک کمينه سراسري را براي شاخص عملکرد به دست دهد. اگر مساله در حقيقت غير خطي باشد، استفاده از تکنيکهاي بهينه سازي نظير تکنيکهاي مبتني بر گراديان، بهينه سازي تکاملي، و غيره اجتناب ناپذير خواهد بود. مي توان معروف ترين الگوريتم مبتني بر بهينه سازي رياضي ارائه شده تاکنون را ماشين بردار پشتيبان )SVM( دانست ]4[. اين تکنيک که يکي از روشهاي يادگيري به
1 Classification
681
شمار مي آيد در دهه 08 ميلادي توسعه پيدا کرد. استفاده از روشهاي برنامه ريزي چندهدفه) MOP( در طبقه بندي داده ها تقريبا از سال 2888 آغاز گرديد و توسعه اين روشها همچنان ادامه دارد. در کليه اين روشها، اهداف مدل به منظور تفکيک داده ها در گروه يا گروه هاي مجزا تعريف مي شوند ]5[.
در اين مقاله، از برنامه ريزي رياضي و روشهاي مبتني بر بهينه سازي، به منظور ارائه و بررسي مدل هاي يادگيري جهت طبقه بندي داده ها استفاده مي کنيم. با استخراج نقاط مشترک و فلسفه يکسان تعدادي از مشهورترين مدل هاي بهينه سازي رياضي در چند سال گذشته، مدل بهينه سازي چند هدفه جامعي پيشنهاد مي گردد. نمايش هندسي مدل به منظور درک ساده تر از خصوصيات مدل ارائه شده خواهد بود. سپس نشان داده مي شود که تعداد زيادي از مدلهاي مورد بررسي در گذشته و حال، زير مجموعه و حالات خاصي از اين مدل جامع پيشنهادي مي باشند و نحوه تبديل مدل جامع پيشنهادي به اين روشها مورد بررسي قرار خواهد گرفت. از اين طريق سعي مي گردد تا شکاف بين مدلهاي جديد برنامه ريزي چندهدفه و روشهاي قدرتمند و بهبود يافته SVM که به منظور طبقه بندي در داده کاوي ارائه مي شوند را پر کرده و مطالعاتي که در راستاي بهبود هر کدام از اين روشها صورت مي گيرد را قابل تعميم به روشهاي ديگر نمود. در اين راستا و در ادامه مقاله، زيرمدل جديدي بر پايه مدل جامع، ارائه خواهد شد. در ادامه و در بخش دوم، به بررسي ادبيات موضوع پرداخته خواهد شد و مطالعات صورت گرفته در زمينه تحقيق مرور مي شود. در بخش سوم، مدل جامع پيشنهادي براي طبقه بندي معرفي خواهد شد و در بخش چهارم، نحوه تبديل مدل جامع پيشنهادي به حالات خاص آن بررسي مي شود. اين حالات خاص شامل مدل هاي معرفي شده توسط ساير محققين و يک زيرمدل جديد پيشنهادي مي باشد. در نهايت، در بخش آخر ،نتايج حاصل از تحقيق جمع بندي شده و تحقيقات آتي مورد بررسي قرار مي گيرد.
2. مرور ادبیات
1268732040127

Downloaded from ijiepm.iust.ac.ir at 14:44 IRST on Saturday November 4th 2017

Downloaded from ijiepm.iust.ac.ir at 14:44 IRST on Saturday November 4th 2017

در سال 1031، Fisher اولين الگوريتم را براي شناسايي الگو ارائه نمود )الگوريتم تفکيک خطي( ]1[ . Vapnik و Lerner در سال 1013، الگوريتم تعميم يافته اي را براي ساخت ابرصفحه هاي تفکيک کننده با حاشيه بهينه معرفي کردند. الگوريتمي که به عنوان ماشين بردار پشتيبان ارائه شده است تعميم غيرخطي اين الگوريتم مي باشد ]7[ . در سال 1015، Mangasarian يک طبقه بندي کننده با حاشيه بزرگ را با استفاده از تکنيکهاي بهينه سازي به صورت مدل برنامه ريزي خطي تنظيم و ارائه کرد ]0[ . بين سالهاي 1008 تا 1008، Freed و Glover چند مدل
1268732040127

Downloaded from ijiepm.iust.ac.ir at 14:44 IRST on Saturday November 4th 2017

Downloaded from ijiepm.iust.ac.ir at 14:44 IRST on Saturday November 4th 2017

688
برنامه ريزي خطي را به منظور حل مسائل تفکيک کننده با نمونهکوچک داده ها ارائه نمودند ]0[ . ماشين بردار پشتيبان به شکلنزديک به روش فعلي، براي اولين بار در قالب يک مقاله در سال1002 توسط Boser و همکاران معرفي شد. آنها همچنين در اين مقاله راهي را براي ساخت طبقه بندي کننده هاي غيرخطي با حداکثر حاشيه با استقاده از کاربرد Kernel Trick در نگاشت غيرخطي ابرصفحه هاي بهينه به فضاي ويژگي )با ابعاد بيشتر( ارائه کردند. الگوريتم PCG-Chunking جهت حل مدل ارائه گرديد ]18[. در سال 1005، Cortes و Vapnik، ايده حداکثر حاشيه اصلاح شده را مطرح نمودند. در اين روش، خطاي طبقه بندي نادرست در مدل SVM در نظر گرفته شده است و الگوريتم حداکثر حاشيه با تعريف متغير کمبود در مدل بهينه سازي، به مسائلي که بصورت خطي جدا پذير نيستند، تعميم داده شد) -CSVC( ]11[. در سال 1007، Osuna و همکاران، رسماًرسما اولين الگوريتم تجزيه براي آموزش مسائل با داده هايي در ابعاد بزرگ را براي SVM ارائه نمودند. آنها همچنين روشي را جهت برخورد با کلاسهاي نامتعادل ارائه نمودند ]12[. در سال 1000، Mangasarian مدل ننُرمُرم اول SVM را ارئه کرد ]13[. در سال 1000، Suykens و Vandewalle مدل LS-SVC را ارئه کردند ]14[. در سال 2888، Schölkopf و همکاران مدل ν-SVC را ارئه کردند ]15[. Mangasarian و همکاران در سال 2881 تعدادي الگوريتم براي SVM ارائه کردند. از جمله مي توان به PSVM ،RSVM ،LSVM ،ASVM ،SSVM اشاره کرد. آنها همچنين از روش Newton Armijo براي حل تعدادي از مدلهاي خود استفاده کردند ]11-28[ . در سال 2881، Shi و همکاران از يک رويکرد مبتني بر برنامه ريزي چند معياره به منظور معرفي مدل MCLP استفاده کردند و به اين ترتيب استفاده از مدلهاي بهينه سازي رياضي را در مسائل داده کاوي گسترش دادند ]21[.
در سال 2882، Bugera و همکاران يک تابع مطلوبيت درجه دوم محدب را براي SVM معرفي کردند و از آن براي مدل سازي مسئله طبقه بندي حساب کارتهاي اعتباري استفاده کردند ]22[.
Peng و همکارانش در سال 2882 بهبود يافته روش برنامه ريزي خطي Shi را براي طبقه بندي چند گروهي پيشنهاد دادند )-MCHsu .]23[ )MCLP و همکاران در سال 2883 يک رويکرد مبتني بر فرآيند براي استفاده از SVM ارائه کردند ]24[. در سال 2883، Bi مدل C-SVM را در قالب يک مسئله برنامه ريزي چند هدفه ارائه نمود و از روش ε-Constraint براي حل آن استفاده کرد ]25[. در سال 2883، Perez-Cruz و همکاران مدل ν-SVC را به مدل Eν-SVC توسعه دادند ]21[. Asada و همکاران در سال 2884 از رويکرد برنامه ريزي آرماني) GP( در طبقه بندي توسط SVM استفاده کردند ]27[.
Shi و همکارانش در سال 2885 روش برنامه ريزي غير خطي چند معياره چندگروهي (MC-MCQP) را براي مسائل تصميم گيري در طبقه بندي داده کاوي ارائه نمودند ]20[. در سال 2881، Kou و همکارانش يک روش برنامه ريزي درجه دوم محدب چند معياره) MCCQP( معرفي نمودند و از آن در تجزيه و تحليل ريسک کارتهاي اعتباري استفاده کرده و نتايج مقايسه آن با چند روش ديگر را نيز ارائه نمودند ]20[ . در سال 2887، Zhang و Shi يک چارچوب جامع بهينه سازي براي طبقه بندي ارائه کرده و چند مدل مشهور بهينه سازي طبقه بندي )مدلهاي LP و MCLP( را به عنوان حالات خاصي از مدل جامع ارائه دادند. آنها در ادامه چند مدل جديد بهينه سازي طبقه بندي را مبتني بر مدل جامع توسعه دادند )از جمله مدلهاي MCVQP، MCCQP و MCIQP( ]38[ . Li و همکارانش در سال 2880 روش برنامه ريزي خطي چند معياره جريمه بسته شده (PMCLP) را در راستاي بهبود روش MCLP پيشنهاد نمودند و کارايي اين مدل را در مقايسه با دو مدل توسعه يافته ديگر متد MCLP، با استفاده از نمونه هاي آزمايشي بررسي کردند [20]. در سال 2880، Kou و همکارانش يک مدل برنامه ريزي رياضي درجه دو چند هدفه را براي طبقه بندي چند گروهي ارائه کردند) .MC-MCQP يا MC2MP( سپس به جاي جستجوي جواب بهينه براي حل يک مسئله برنامه ريزي رياضي محدب، نشان داده شد که محاسبه پاسخ بهينه مدل ارائه شده تنها نياز به محاسبات ماتريسي دارد ]31[. Ben-Hur و Weston در سال 2818 مروري بر الگوريتم هاي ماشين بردار پشتيبان و انتخاب پارامترها داشتند ]32[. در سال 2811، Zhang و همکاران، مدل هاي طبقه بندي MCLP را با سيستم هاي خبره ادغام کردند تا نقاط ضعف هرکدام از اين روشها را بپوشانند ]33[ .
استفاده از روشهاي مبتني بر بهينه سازي، منجر به ارتقاي مبناي تئوري و همچنين گسترش کاربرد عملي داده کاوي )به خصوص در زمينه طبقه بندي داده ها( شده است. در قالب يک دسته بندي کلي، تاکنون دو دسته از روشهاي طبقه بندي مبتني بر بهينه سازي مورد مطالعه قرار گرفته اند: دسته اول، مطالعات اوليه اي است که در دهه 18 توسط Vapnik و همکارانش و همچنين Mangasarian و همکارانش صورت گرفت و سپس در دهه 08 در قالب ماشين بردار پشتيبان (SVM) به بلوغ رسيد و سپس به مرور به تکامل دست يافت. دسته دوم شامل مطالعاتي است که اولين بار توسط Freed و Glover در دهه 08 ارائه شد و از سال 2888 توسط Shi و همکارانش در قالب روشهاي برنامه ريزي رياضي چندهدفه خطي و غيرخطي بسط داده شد. در طول اين مدت، تاکنون افراد مختلفي روي بهبود اين روشها مطالعه نموده اند. مطالعات صورت گرفته در دو زمينه «ارائه ياتوسعه مدل هاي بهينه سازي» و «ارائه يا توسعه الگوريتم حلمدل ها» بوده است. در اين ميان، نکته قابل توجه، فلسفه يکسانهر دو دسته از روشهاي طبقه بندي مبتني بر بهينه سازي مي باشد .

3. مدل جامع بهینه سازی پیشنهادی
در اين بخش، پس از تعريف نمادهاي مشترک، محدوديت ها و توابع هدفهدفِ مدل جامع، طبقه بندي کننده را به صورت هندسي و همچنين در قالب برنامه ريزي رياضي، مدل سازي خواهيم کرد .
مدل جامع طبقه بندي، به گونه اي طراحي شده است که مدل هاي اوليه و بهبود يافته SVM و همچنين مدل هاي برنامه ريزي رياضي يک و چندهدفه خطي و غيرخطي که تاکنون ارائه شده اند را به عنوان حالات خاصي از خود دربرگيرد و همچنين، ايجاد حالات خاص جديد نيز امکان پذير باشد.

3-9. نمادگذاری
به منظور ايجاد قابليت مقايسه بين مدل هاي مختلف و بررسي ساده تر آنها، نمادهاي مشترکي را تعريف نموده و از قالب اين نمادگذاري در طول مقاله استفاده خواهد شد.

تعداد خصيصه ها بردار خصيصهها
خصيصه ام بطوري که:
تعداد رکوردها
ماتريس رکوردها رکورد ام بطوري که:
مقداري که رکورد ام به ازاي خصيصه ام
اختيار کرده است
تعداد ابرصفحه هاي جدا کننده )که همواره يکي
کمتر از تعداد کلاس ها ميباشد(
بردار برچسب ها )مشخصکننده وضعيت عضويت-
درکلاس هاي (
برچسب ام بطوري که:
ماتريس برچسب ها برچسب حقيقي رکورد ام
مقداري که برچسب حقيقي رکورد ام نسبت به ابرصفحه جداکننده ام اختيار کرده است بطوري
که:
681

ماتريس ضرايب

(
ام



قیمت: تومان


دیدگاهتان را بنویسید