International Journal of Industrial Engineering & Production Management (2013)

تحقیق abkaazem A 10 587 2 4a472fc65 1

-144144-24523

تحقیق abkaazem A 10 587 2 4a472fc65 1

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

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

در این سایت فقط تکه هایی از این مطلب درج می شود که ممکن است هنگام انتقال از فایل ورد به داخل سایت کلمات به هم بریزد یا شکل ها درج نشود

شما می توانید تکه های دیگری از این مطلب را با جستجو در همین سایت بخوانید

ولی برای دانلود فایل اصلی با فرمت ورد حاوی تمامی قسمت ها با منابع کامل

به سایت مرجع

www.homatez.com

مراجعه نمایید

 

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

تحقیق abkaazem A 10 587 2 4a472fc65 1

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
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

تحقیق abkaazem A 10 587 2 4a472fc65 1

تحقیق abkaazem A 10 587 2 4a472fc65 1

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

تحقیق abkaazem A 10 587 2 4a472fc65 1

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

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

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

-1662316985

تحقیق abkaazem A 10 587 2 4a472fc65 1

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

تحقیق abkaazem A 10 587 2 4a472fc65 1

9. مقدمه9
از دهه 08 میلادی، با توسعه علوم و ارتباطات در جوامع بشری و انباشته شدن حجم عظیمی از داده های تجاری و علمی، نیاز به کسب دانش از داده های انباشته به صورت قابل ملاحظه ای افزایش یافت. این حجم عظیم داده ها که روز به روز به آنها اضافه می گردد، عموما حاوی اطلاعات مهمی بوده که استخراج آنها از پایگاه های داده و پردازش آنها به آسانی امکان پذیر نیست. این نیاز روز افزون، منجر به رشد سریع دانش داده کاوی2 گردید .
داده کاوی به مفهوم استخراج اطلاعات و دانش از پایگاه های داده در راستای کشف الگوها و مفاهیمی که به سادگی قابل درک
تاریخ وصول: 91/9/19 تاریخ تصویب: 1/8/19
*نویسنده مسئول مقاله: دکتر ابوالفضل کاظمی، استادیار دانشکده صنایع و
مکانیک، دانشگاه آزاد اسلامی واحد قزوین، قزوین، ایران
abkaazemi@qiau.ac.ir
سیامک ابوطالب، کارشناسی ارشد مهندسی صنایع، دانشکده صنایع و مکانیک ،دانشگاه آزاد اسلامی واحد قزوین، قزوین، ایران Data Mining siamak_a84@yahoo.com 2
نیستند، می باشد. داده کاوی یکی از مراحل فرآیند کشف دانش در پایگاه داده ها )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. مرور ادبیات
در سال 1031، Fisher اولین الگوریتم را برای شناسایی الگو ارائه نمود )الگوریتم تفکیک خطی( ]1[ . Vapnik و Lerner در سال 1013، الگوریتم تعمیم یافته ای را برای ساخت ابرصفحه های تفکیک کننده با حاشیه بهینه معرفی کردند. الگوریتمی که به عنوان ماشین بردار پشتیبان ارائه شده است تعمیم غیرخطی این الگوریتم می باشد ]7[ . در سال 1015، Mangasarian یک طبقه بندی کننده با حاشیه بزرگ را با استفاده از تکنیکهای بهینه سازی به صورت مدل برنامه ریزی خطی تنظیم و ارائه کرد ]0[ . بین سالهای 1008 تا 1008، Freed و Glover چند مدل
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

تحقیق abkaazem A 10 587 2 4a472fc65 1

ماتریس ضرایب

تحقیق abkaazem A 10 587 2 4a472fc65 1

(
ام

(

ام

بردار ضرایب )بردار قائم بر ابرصفحه جداکننده
مقدار ضریب خصیصه ام نسبت به ابرصفحه
جداکننده ام
امتیاز طبقه بندی رکورد ام نسبت به
ابرصفحه جداکننده ام بردار مرزی بایاس
اسکالر مرزی بایاس جدا کننده کلاس های ام و
ام
ماتریس انحراف
فاصله امتیاز رکورد ام با طبقه بندی نادرست یا خطای حاشیه از ابرصفحه مرزی تنظیم شده
فاصله امتیاز رکورد ام با طبقه بندی نادرست یا
خطای حاشیه از ابرصفحه مرزی تنظیم شده
جدا کننده ام
ماتریس انطباق
فاصله امتیاز رکورد ام با طبقه بندی صحیح یا
صحت حاشیه از ابرصفحه مرزی تنظیم شده فاصله امتیاز رکورد ام با طبقه بندی صحیح یا
صحت حاشیه از ابرصفحه مرزی تنظیم شده
جدا کننده ام

3-2. فرموله کردن مسئله و محدودیت های مدل جامع پیشنهادی
1981201045634

تحقیق abkaazem A 10 587 2 4a472fc65 1


تحقیق abkaazem A 10 587 2 4a472fc65 1
قیمت: تومان

پاسخ دهید