وزارت علوم، تحقيقات و فناوري
دانشگاه علوم و فنون مازندران

پايان نامه مقطع کارشناسي ارشد
رشته فناوري اطلاعات/ مديريت سيستم هاي اطلاعاتي

عنوان :
پيش پردازش داده هاي نا متوازن با استفاده از ماشين بردار پشتيبان
استاد راهنما : جناب دکتر جواد وحيدي

استاد مشاور : جناب دکتر بابک شيرازي

دانشجو : مائده گلباغي

زمستان 1392
تشکر و قدرداني
حمد وسپاس بيکران ازخداوند باريتعالي که توفيق انجام اين تحقيق را به اينجانب ارزاني فرمود درآغاز، مراتب سپاس خود را از يکايک اساتيد و بزرگواراني که در طول تحقيق و تحصيل از محضرشان بهره برده ام به جا ميآورم.
از زحمات و حمايت هاي استاد گرامي آقاي دکتر جواد وحيدي استاد راهنماي اينجانب که سعي و تلاش بسياري دراجراي اين پايان نامه نمودند کمال تشکر را دارم.
از جناب آقاي دکتر بابک شيرازي که از مشاوره وکمک هاي ايشان درطي اجراي اين تحقيق بهره برده ام سپاسگزارم .
در پايان مراتب قدرداني خود را از تمامي عزيزاني که در طول انجام تحقيق حاضر اينجانب را ياري فرمودند ابراز مينمايم.

تقديم به . . .
پدر و مادر عزيزم كه در تمام مراحل تحصيل مرا ياري نمودند و با زحمات خود رنج و سختي كار را برايم آسان ساختند .

چکيده
براي دست يابي به نتايج مطلوب در داده کاوي نياز به پيش پردازش داده ها داريم.پيش پردازش داده ها يکي از اجزاي مهم در فرايند کشف دانش است.روش هاي بسياري براي پيش پردازش داده وجود دارد که ميتوان از آنها استفاده کرد.اما اين روش ها براي داده هاي نامتوازن مناسب نيستند. اصطلاح “مجموعه داده نامتوازن” عموما به مجموعه داده‌اي گفته مي‌شود که در آن تعداد نمونه‌هايي که نمايانگر يک کلاس هستند از نمونه‌هاي ديگر در کلاس‌هاي متفاوت کمتر است مشکل عدم توازن کلاس در بسياري از برنامه هاي کاربردي جهان واقعي به رسميت شناخته شده است و موضوع تحقيقات يادگيري مبتني بر ماشين قرار گرفته است از اين رو اخيراً مشكل نامتوازن بودن كلاسها مورد توجه محققان در زمينه ي داده كاوي قرار گرفته است.آنها به دنبال کشف روش هايي بودند که با اعمال بر روي داده هاي نامتوازن به نتايج مطلوبي دست يابند.
در اين پروژه روش هاي گوناگون پيش پردازش داده هاي نامتوازن مورد بحث قرار گرفته و الگوريتم جديدي براي بهبود نتايج طبقه بندي ارائه ميشود، به گونه اي که کارايي و دقت آن مورد توجه باشد.
کلمات کليدي : پيش پردازش داده، مجموعه داده نامتوازن، ماشين بردار پشتيبان

فهرست مطالب
فصل اول مقدمه و کليات تحقيق
1-1مقدمه2
1-2بيان مساله2
1-3 اهداف تحقيق4
1-4 پرسش هاي اصلي تحقيق4
1-5فرضيه هاي تحقيق4
1-6 نوآوري تحقيق5
1-7 تعريف واژگان کليدي5
1-8 ساختار پايان نامه9
فصل دوم ادبيات و پيشينه تحقيق
2-1 مقدمه11
2-2 مفاهيم داده کاوي11
2-2-1 تعاريف داده کاوي11
2-2-2 فرايند کشف دانش12
2-2-3 حوزه ها و عملکردهاي داده کاوي12
2-3 کاربردهاي داده کاوي و کشف دانش14
2-4 چالش هايي براي KDD15
2-5 پيش پردازش و آماده سازي داده ها :16
2-5-1اجزاي اصلي پيش پردازش داده ها17
2-5-1-1 پاکسازي داده ها18
2-5-1-2يکپارچه سازي داده ها20
2-5-1-3 تبديل داده ها20
2-5-1-3-1هموار سازي20
2-5-1-3-2 تجميع21
2-5-1-3-3 تعميم21
2-5-1-3-4 ساخت ويژگي21
2-5-1-3-5 نرمال سازي21
2-5-1-4 کاهش داده ها21
2-5-1-4-1 تجميع مکعبي داده23
2-5-1-4-2 انتخاب زير مجموعه مشخصه ها23
2-5-1-4-3 کاهش تعدد نقاط24
2-5-1-5 تصوير کردن براي کاهش بعد24
2-6 روش هاي ارزيابي دسته بندي25
2-6-1 ارزيابي صحت روشهاي دسته بندي27
2-7 تکنيک حداقل مربعات30
2-7-1 تقريب کمترين مربعات گسسته چند جمله اي31
2-8 ماشين بردار پشتيبان33
2-8-1مقدمه33
2-8-2دلايل استفاده از SVM34
2-8-3 کاربردهاي SVM35
2-8-4 مزايا و معايب SVM36
2-8-5 تعاريف کلي36
2-8-5-1تابع تصميم مسائل دو کلاسي36
2-8-5-2 تعيين تابع تصميم(ابر صفحه جداکننده)38
2-8-5-3 بعد VC39
2-8-5-4حداقل سازي ريسک تجربي40
2-8-5-5حداقل سازي ريسک ساختاري42
2-8-6 ماشين بردار پشتيبان طبقه بندي کننده خطي با داده هاي جدا شدني به طور خطي44
2-8-7ماشين بردار پشتيبان طبقه بندي کننده خطي با داده هاي جدا نشدني به طور خطي (49
2-8-8 ماشين بردار پشتيبان غير خطي52
2-8-9 انواع کرنل ها55
2-8-9-1 کرنل چند جمله اي55
2-8-9-2 کرنل هاي شبکه عصبي55
2-8-9-3 کرنل هاي گوسي56
2-9 تکنيک هاي پيش پردازش نامتوازن58
2-9-1 ماشين بردار پشتيبان و مشکل عدم توازن کلاس58
2-9-1-1 عيب مشکل بهينه سازي با ناحيه مرزي نرم59
2-9-1-2 نسبت بردار پشتيبان نامتوازن60
2-9-2 روشهاي يادگيري عدم توازن خارجي براي SVM (روشهاي پيش پردازش داده)61
2-9-2-1 روشهاي نمونه برداري دوباره61
2-9-2-1-1زير نمونه برداري61
2-9-2-1-2بيش نمونه برداري62
2-9-2-1-3 SCM63
2-9-2-1-4 نمونه برداري پيشرفته63
2-9-2-1-5 تکنيک بيش نمونه برداري اقليت مصنوعي64
2-9-2-1-6 نزديک ترين همسايه فشرده(CNN)64
2-9-2-1-7 نزديک ترين همسايه تغيير يافته(ENN)66
2-9-2-1-8 Tomek-Link67
2-9-2-2 روشهاي يادگيري جمعي68
2-9-2-2-1الگوريتم آموزشي Bagging69
2-9-2-2-2 الگوريتم آموزشي Boosting70
2-9-3 روشهاي يادگيري عدم تعادل داخلي براي ماشين بردار پشتيبان71
2-9-3-1 هزينه خطاي متفاوت71
2-9-3-2 يادگيري يک کلاس73
2-9-3-3zSVM73
2-9-3-4 روشهاي اصلاح کرنل74
2-9-3-5 يادگيري فعال75
2-9-3-6 روش هاي ترکيبي75
فصل سوم:روش تحقيق
3-1مقدمه77
3-2 ماشين بردار پشتيبان فازي براي يادگيري عدم توازن کلاس77
3-2-1 روش SVMFuzzy77
3-2-2متد FSVM-CIL79
3-3 ماشين بردار پشتيبان حداقل مربعات (LS-SVM)83
3-4 الگوريتم پيشنهادي87
فصل چهارم:محاسبات و يافته هاي تحقيق
4-1 مقدمه90
4-2 مجموعه داده ها90
4-3 نتايج کارايي روش هاي مختلف بر روي مجموعه داده ها91
فصل پنجم:نتيجه گيري و پيشنهادات
5-1 جمع بندي و نتيجه گيري94
5-2 کارهاي آتي96
منابع و مآخذ :97
چکيده انگليسي……………………………………………………………………………………………………….102

فهرست جداول

جدول 2-1 متغيرهاي ارزيابي دسته بندي29
جدول 4-1 جزييات مجموعه داده هاي نامتوازن90
جدول 4-2- مقايسه کارايي روش هاي مختلف92
فهرست اشکال
شکل (2-1)- فرايند کشف دانش]1[12
شکل(2-2)-حوزه هاي مختلف داده کاوي]1[13
شکل(2-3)-عملکردهاي داده کاوي]1[13
شکل(2-4)-عمليات مختلف در پاکسازي داده]1[18
شکل(2-5)-فشرده سازي بي اتلاف و پر اتلاف]1[22
شکل(2-6)-تجميع مکعبي داده]1[23
شکل(2-7)-نمايي از ريسک در دسته بندي]1[27
شکل (2-8)-تابع تصميم فضاي دو بعدي37
شکل (2-9)- مرکز کلاس براي شکل 2-838
شکل (2-10)- مرز کلاس بدون هيچ اشتراکي39
شکل (2-11)- بعد VC ]11[40
شکل (2-12)- ابر صفحه جدا کننده بهينه در دو بعد47
شکل (2-13)- حالت جداناپذير خطي در دو بعد49
شکل (2-14)- نگاشت داده هاي آموزشي غيرخطي به فضايي از ويژگي ها با ابعاد بالاتر با تابع ]11[53
شکل (2-15)-مثالي از تقسيم بندي غير خطي با کرنل گوسي بر روي داده ها ]11[57
شکل (2-16)- منحني تغييرات خطا نسبت به مقاديرمختلف ]11[57
شکل (2-17)- (a) مجموعه داده اصلي. (b) مجموعه داده بعد از اعمال SMOTE. ) (c Tomek-Link هاي شناخته شده (d) مجموعه داده بعد از پاکسازي Tomek-Link ها]36[68

فصل اول
مقدمه و کليات تحقيق

1-1مقدمه
کشف دانش و داده کاوي يک حوزه جديد ميان رشته اي و در حال رشد است که حوزه هاي مختلفي همچون پايگاه داده، آمار، يادگيري ماشين و ساير زمينه هاي مرتبط را با هم تلفيق کرده تا اطلاعات و دانش ارزشمند نهفته در حجم بزرگي از داده ها را استخراج کند.هدف کشف دانش و داده کاوي يافتن الگوها در پايگاه داده است که در ميان حجم عظيمي از داده ها مخفي هستند]1[ .کشف دانش شامل مراحل متعددي است که در اين تحقيق به مرحله پيش پردازش توجه ميکنيم.

مرحله آماده سازي داده ها مهم ترين و زمانبرترين مرحله در پروژه هاي داده کاوي است.از آنجا که داده ها در اين پروژه ها ورودي پروژه هستند هر قدر اين ورودي دقيق تر باشد، خروجي کار دقيق تر خواهد بود.يعني ما از پديده “ورودي نامناسب، خروجي نامناسب ” دور ميشويم]1[.داده هاي خام معمولا دچار مشکلاتي مانند نويز، داده پرت، تغييرات در نمونه برداري هستند و استفاده از آنها به همين صورت موجب تضعيف نتايج مورد انتظار ميشود.بنابراين بايد از روشي براي بهبود نتايج استفاده کرد.پيش پردازش داده ها جهت بهبود کيفيت داده هاي واقعي براي داده کاوي لازم است.بنابراين پردازش اوليه اي مورد نياز است تا مقادير مفقوده، انحرافات و مسائلي از اين دست را در داده هاي اوليه بيابد. پيش پردازش داده ها شامل همه تبديلاتي است که بر روي داده هاي خام صورت ميگيرد وآنها را به صورتي در ميآورد که براي پردازشهاي بعدي نظير استفاده در دسته بندي و خوشه بندي، ساده تر و موثرتر ميسازد.
در حال حاضر سازمانها نياز دارند تا بتوانند داده ها را به صورت کاراتر دسته بندي کنند و از تحليل نتايج آن براي بهبود روند پيشرفت کسب و کار استفاده نمايند.ممکن است که داده هاي در دسترس ، داده هايي مبهم و مغشوش باشند و يا کلاس هاي داده نامتوازن باشند. بنابراين نياز به پيش پردازش دقيق داده ها رو به افزايش است. براي پاسخ به اين نياز رو به افزايش ، افراد همواره سعي در ارائه روش هاي نوين و موثرتري دارند.
1-2بيان مساله
هرچند که روشهاي مختلفي براي پيش پردازش داده ها موجود است ولي عملکرد و دقت اين روش ها متفاوت است و تلاش در جهت ارائه روشي کارامد امري ضروري است.با توجه به اهميت داده ها در جهان کنوني و افزايش حجم داده ها مساله پيش پردازش مناسب داده ها، بخصوص داده هاي نامتوازن يک چالش به نظر ميرسد.اغلب روش هاي موجود در پيش پردازش داده هاي ناتوازن به سمت کلاس اکثريت تمايل دارند و اين امر باعث مي شود که داده هاي کلاس اقليت به صورت نويز در نظر گرفته شود.
همانطور که پيش از اين نيز گفته شد براي دست يابي به نتايج مطلوب در داده کاوي نياز به پيش پردازش داده ها داريم.ميتوان ادعا کرد که اگر مرحله آماده سازي داده ها به خوبي صورت نپذيرد، نتايجي بدست ميآيد که نميتواند مورد استفاده قرار گيرد و ممکن است که هزينه و زمان به کار رفته براي دست يابي به نتيجه موثر هدر رود و نتايج حاصل به دليل عدم پيش پردازش مناسب داده غير قابل استفاده و نادرست باشد.
اخيراً مشكل نامتوازن بودن كلاسها مورد توجه محققان در زمينه ي داده كاوي قرار گرفته است. در موارد متعددي كلاسي كه از نقطه نظر دامنه ي كاربردي اهميت زيادي دارد(كلاس اصلي) شامل تعداد حالات كمتري نسبت به كلاسي است كه كلاس اكثريت ميباشد. اين مجموعه ي داده ها نامتوازن ناميده ميشود. رويكرد سنتي داده كاوي توانايي خوبي براي پيش بيني نمونه هاي اقليت كه مورد توجه است ندارند. متأسفانه در اكثر موارد داده هاي واقعي داراي اين خصوصيت هستند. به عنوان مثال در تشخيص بيماريهاي نادر، حملات شبكه، متنكاوي و … معمولاً توزيع دادهها نامتوازن مي باشد.
در واقع مساله اين است که چگونه ميتوان داده هاي نامتوازن را به گونه اي پيش پردازش کرد که در خوشه هاي مناسب و درست طبقه بندي شوند.بنابراين مساله اين تحقيق ارائه روشي جهت پيش پردازش داده هاي نا متوازن است به گونه اي که کارايي و دقت آن در مقايسه با روش هاي ديگر بيشتر باشد.
در روش ارائه شده در اين تحقيق براي ارتقاي روش ماشين بردار پشتيبان از تکنيک حداقل مربعات با متر اقليدسي استفاده نموديم.اين روش بهبود يافته را M-SVM ميناميم.بنابراين مساله را بدين شکل طرح مي نماييم، چگونه ميتوان در روش پيش پردازش داده هاي نامتوازن به دقت بالاتري دست يافت و از پيش پردازش صحيح داده براي دست يابي به نتايج صحيح در حوزه کاربردي استفاده نمود.از انجا که داده هاي متفاوتي وجود دارد ما پيش پردازش بر روي مجموعه داده هاي نامتوازن را انتحاب کرديم

1-3 اهداف تحقيق
هدف از اين تحقيق ارائه راهکاري به منظور افزايش دقت متعادل سازي داده و غلبه بر مشکل عدم توازن کلاس است.سعي کرده ايم تا متعادل سازي داده که در مرحله پيش پردازش داده صورت ميگيرد باعث بهبود نتايج طبقه بندي نمونه ها شود.بدين منظور اثربخشي و کارايي روش ارائه شده با ساير روش هاي موجود مورد مقايسه و ارزيابي قرار ميگيرد.اميد است که نتايج الگوريتم نهايي اميدوار کننده باشد و نشان دهنده پيشرفت الگوريتم باشد.اين تحقيق بر اساس نياز به دسته بندي دقيق داده ها و استفاده از تحليل نتايج داده ها در بهبود شرايط مرجع مورد استفاده کننده داده ها شکل گرفته است.
1-4 پرسش هاي اصلي تحقيق
تحقيقات انجام شده در اين پروژه سعي در پاسخگويي به سوالات زير را دارد :
معيارهاي اندازه گيري کارايي روش هاي متعادل سازي چيست؟
روش هاي کنوني متعادل سازي چيست؟
چگونه مي توان مشکل عدم توازن کلاس را حل کرد؟
چگونه مي توان مشکل نويز در طبقه بندي را حل کرد؟
1-5فرضيه هاي تحقيق
کارايي روش ارائه شده در مقايسه با ساير روش ها بهتر است.
استفاده از اين روش باعث بهبود نتايج طبقه بندي داده ها در حضور داده هاي پرت و نويز ميشود.
استفاده از الگوريتم پيشنهادي باعث کاهش حساسيت به عدم توازن کلاس ميشود.
1-6 نوآوري تحقيق
مي توان نوآوري را به صورت استفاده از تکنيک حداقل مربعات با استفاده از مفاهيم فازي براي استفاده در ماشين بردار پشتيبان در جهت پيش پردازش داده هاي نامتوازن بيان کرد.

1-7 تعريف واژگان کليدي
پيش پردازش داده
با توجه به حجم عظيم داده هاي موسسات جهت تحليل اطلاعات و كشف دانش نهفته در اين داده ها به مساله مهمي تبديل شده است . براي كشف دانش نهفته در اين داده ها به كارگيري تكنيك هاي داده كاوي امري بديهي است.وجود مسائلي نظير ناقص بودن داده ها، ناسازگاري آنها و وجود ناخالصي هايي همچون خطاها، مقادير تقريبي و مقادير خارج از محدوده نرمال در پايگاه داده هاي واقعي، باعث كاهش كيفيت داده كاوي ميشود. براي دستيابي به نتايج مطلوب تر، نياز به داده هاي با كيفيت بالاتر وجود دارد. پيش پردازش، گامي مهم در راستاي داده كاوي موفقيت آميز است. اعمالي كه در پيش پردازش انجام مي شوند عبارتند از حذف ناخالصيها و اصلاح داده هاي نادرست، يكپارچهسازي داده ها، تغيير داده ها و كاهش داده ها. بر اساس نوع كاربردي كه عمل داده كاوي بايد روي آن انجام شود، تكنيك هاي مختلفي براي هر يك از اين اعمال وجود دارد]4[.
داده هاي نامتوازن
اصطلاح “مجموعه داده نامتوازن” عموما به مجموعه داده‌اي گفته مي‌شود که در آن تعداد نمونه‌هايي که نمايانگر يک کلاس هستند از نمونه‌هاي ديگر در کلاس‌هاي متفاوت کمتر است.در واقع مشکل عدم توازن کلاس زماني رخ ميدهد که براي کلاس هاي با اهميت، نمونه هاي کم و يا بسيار کمي در حوزه هاي کاربردي جهان واقعي در دسترس باشد. اين حالت در کلاسه بندي زماني مشکل‌ساز مي‌شوند که يک کلاس که عموما کلاس مطلق يا اقليت(Minority Class) مي‌باشد در مجموعه داده‌ها نشان داده‌ نمي‌شود و به بيان ديگر تعداد مشاهدات اشتباه از مشاهدات درست در يک کلاس بيشتر مي‌شود.مثلا در حوزه هايي مانند ارتباط از راه دور، تشخيص غنائم نفت در تصاوير راداري ماهواره اي، طبقه بندي متن، تشخيص پزشکي،تشخيص نفوذ و کشف تقلب. در اين موارد الگوريتم استاندارد کلاسه بندي کننده تمايل بيشتري به کلاس‌هاي اکثريت (MajorityClass)دارد، زيرا قوانيني که اين نمونه‌ها را به درستي پيش‌بيني مي‌کنند به درستي وزن‌دهي شده اند در حالي که قوانين خاصي که نمونه‌هاي کلاس اقليت را پيش‌بيني مي‌کنند عموما ناديده گرفته مي‌شوند و در واقع به صورت نويز با آنها برخورد مي‌شود و در نتيجه نمونه‌هاي کلاس اقليت به اشتباه کلاسه‌بندي خواهند شد[15].
براي غلبه بر اين مشکل، از طبقه بندي مجموعه داده هاي نامتوازن استفاده ميشود. يکي از مشکلات کليدي در هنگام يادگيري با مجموعه داده نامتوازن، فقدان داده است که در آن تعداد نمونه هاي کمي در دسترس است و يا هيچ نمونه اي براي يک کلاس خاص در دسترس نيست روش هاي مقابله با مشکل عدم توازن عبارتند از : تغيير اندازه مجموعه آموزشي( که شامل بيش نمونه گيري از نمونه هاي کلاس اقليت و کوچک سازي نمونه هاي کلاس اکثريت)، تنظيم هزينه هاي طبقه بندي نادرست و تشخيص مبتني بر يادگيري]14[.
تکنيک هاي مواجهه با مجموعه داده هاي نامتوازن
به منظور رسيدگي به مسائل مربوط به مجموعه داده‌هاي نامتوازن تکنيک‌هاي متعددي معرفي شده اند که در سه دسته زير طبقه بندي مي‌شوند:
رويکردهايي در سطح الگوريتم1
اين رويکرد به الگوريتم‌هاي يادگيري کلاسه بند کمک مي‌کند تا فرآيند يادگيري را به سمت کلاس اقليت سوق دهد.
رويکردهايي در سطح داده2
اين رويکرد با باز نمونه گيري از فضاي داده باعث تغيير توزيع داده‌ها مي‌شود به طوري که تغييري در الگوريتم يادگيري ايجاد نمي‌شود و تلاش مي‌کند در مرحله پيش پردازش تأثيرات ناشي از عدم توازن را برطرف کند.
چارچوب يادگيري حساس به هزينه3
اين رويکرد مابين رويکرد الگوريتمي و داده‌اي قرار دارد. به طوري که هم در سطح داده و هم در سطح الگوريتم تغيير ايجاد خواهد کرد. مهمترين نقطه ضعف اين رويکرد تعريف هزينه‌ي رده بندي نادرست مي‌باشد که عموما در مجموعه داده وجود ندارند[15].

ماشين بردار پشتيبان4
اولين الگوريتم براي طبقه بندي و دسته بندي الگوها در سال 1936 ارائه شد و معيار آن براي بهينه بودن، كم كردن خطاي طبقه بندي الگوهاي آموزشي بوده است.بسياري از الگوريتم ها و روشهايي نيز كه تاكنون براي طراحي طبقه بندي كننده هاي الگو ارائه شده است، ازهمين استراتژي پيروي ميكنند.محققي در سال 1965 گامي بسيار مهم در طراحي دسته بندي كننده ها برداشت و نظريه آماري يادگيري را بصورت مستحكم تري بنا نهاد و ماشينهاي بردار پشتيبان (SVM)را بر اين اساس ارائه داد.
ماشينهاي بردار پشتيبان داراي خواص زير هستند:
1?طراحي دسته بندي كننده با حداكثر تعميم
2?رسيدن به بهينة سراسري تابع هزينه
3?تعيين خودكار ساختار و توپولوژي بهينه براي طبقه بندي كننده
4?مدل كردن توابع تمايز غير خطي با استفاده از هسته هاي غير خطي و مفهوم حاصلضرب داخلي در فضاهاي هيلبرت]12[.
در واقع يکي از ابزارهاي مورد استفاده براي پيش پردازش داده ماشين بردار پشتيبان است. SVM يک روش مبتني بر يادگيري آماري و يکي از بهترين تکنيک هاي يادگيري ماشين مورد استفاده در داده کاوي است.از SVM در طيف گسترده اي از برنامه هاي کاربردي مانند پيش بيني سرطان روده، تجزيه و تحليل ژن، تجزيه و تحليل رتبه اعتباري، پيش بيني هاي سري زماني مالي، تشخيص تقلب مالي، برآورد عملکرد کارخانه و رفتار کاربران وب استفاده ميشود.
بهترين ويژگي SVM اين است که هميشه منجر به راه حل بهينه سراسري ميشود.در عوض الگوريتم هاي هوشمند ديگر از گير کردن در مينيمم محلي رنج ميبرند.SVM تلاش ميکند تا مرز تصميمگيري بين کلاسهاي مختلف را (بدون هيچگونه نگراني در مورد تعداد نمونه هاي در دسترس براي کلاس)پيدا کند.SVM براي مشکلات چندبعدي مناسب است و از آن ميتوان در مواقعي استفاده کرد که تعداد کمي از مشاهدات در دسترس است]14[.
براي حل مساله طبقه بندي دو کلاسه، اصلي ترين هدف SVM يافتن ابرصفحه جداکننده بهينه به گونه اي است که نقاط داده را تا حد امکان به درستي طبقه بندي کند و داده هاي دو کلاس را تا جاي ممکن از يکديگر دور سازد.همچنين بايد ريسک طبقه بندي نادرست نمونه هاي آموزشي و نمونه هاي تست کاهش يابد]14[.
منطق فازي
تئوري مجموعه‌هاي فازي و منطق فازي را اولين بار پرفسور لطفي‌زاده در رساله‌اي به نام “مجموعه‌هاي فازي – اطلاعات و كنترل”در سال 1965 معرفي نمود. هدف اوليه او در آن زمان، توسعه مدلي كارآمدتر براي توصيف فرآيند پردازش زبان‌هاي طبيعي بود. او مفاهيم و اصطلاحاتي همچون مجموعه‌هاي فازي، رويدادهاي فازي، اعداد فازي و فازي‌سازي را وارد علوم رياضيات و مهندسي نمود.
ماشين بردار پشتيبان فازي
در دسته بندي كنندة SVMاستاندارد، اهميت ميزان خطا ( مقدارمتغيرهاي Ei ) به ازاي نمونه هاي آموزشي مختلف يكسان است، در حاليكه منطقًا نبايد چنين باشد.با استفاده از منطق فازي، ميتوان ميزان اهميت هر نمونه را در فاز آموزش دخالت داد.همچنين ميتوان در مرحله تصميمگيري به جاي يك تصميمگيري خشن5 (در SVM استاندارد) يك تصميمگيري نرم را انجام داد]12،3[.

1-8 ساختار پايان نامه
پايان نامه حاضر متشکل از پنج فصل مجزا مي باشد:
فصل حاضر کلياتي از تحقيق را ارائه داده است.
در ادامه اين پايان نامه در فصل دوم ادبيات موضوع تحقيق مرور ميشود.در اين فصل ابتدا روش هاي پيش پردازش داده به صورت کلي بيان ميشود و تعدادي از روش هاي مطرح در ارتباط با پيش پردازش داده هاي نامتوازن بررسي ميشود و مباني ورود به تحقيق را براي خواننده تشريح مينمايد.
فصل سوم که مهمترين فصل اين مسند است به تشريح کامل روش پيشنهادي يعني الگوريتمي براي پيش پردازش داده هاي نامتوازن ميپردازد.
در فصل چهارم روش پيشنهادي مورد ارزيابي قرار گرفته و کارايي آن با ساير روش ها مقايسه ميشود.
فصل پنج مختص نتيجه گيري تحقيق و ارائه پيشنهادها براي بهبود کار است. در اين فصل فعاليتهاي آتي كه ميبايست انجام شود تا اين تحقيق تكامل پيدا كند، فهرست خواهد شد.

فصل دوم
ادبيات و پيشينه تحقيق

2-1 مقدمه
نتايج تحليل داده ها زماني ميتواند مورد اطمينان باشد که داده ها به درستي طبقه بندي شده باشند.لذا پيش پردازش داده ها جهت بهبود کيفيت داده هاي واقعي براي داده کاوي لازم است.اين فصل به تشريح ادبيات موضوع اختصاص دارد.براي ورود به بحث پيش پردازش داده هاي نامتوازن از طريق SVM ، نياز است تا مفاهيم کلي داده کاوي ، پيش پردازش داده ها،تعريف داده هاي نامتوازن و برخي مفاهيم تخصصي ارائه شود.
در بخش دوم از اين فصل به مفاهيم و مباني مورد نياز در مورد داده کاوي، از جمله تعريف آن، مزايا و معايب، عملکردهاي داده کاوي پرداخته شده است.سپس به تعريف اجمالي از روش هاي پيش پردازش داده ميپردازيم.
در بخش سوم اين فصل تکنيک هاي ماشين بردار پشتيبان توضيح داده ميشود.

2-2 مفاهيم داده کاوي
2-2-1 تعاريف داده کاوي
برخي تعاريف متداول داده کاوي و کشف دانش به شرح زير مي باشند
تحليل داده هاي توصيفي کامپيوتري، در مجموعه هاي بزرگ و پيچيده داده ها
پرس و جوي الگو در پايگاه داده ها
ويرايشي از يادگيري ماشين که به مجموعه هاي بزرگ داده اعمال شده و علاوه بر يادگيري با ناظر، طيف وسيع تري از روش هاي بدون ناظر را نيز در برميگيرد.
داده کاوي تحليل حجم زيادي از داده ها براي کشف الگوها و قواعد معنادار است.فرايند داده کاوي گاهي کشف دانش نيز ناميده ميشود.
2-2-2 فرايند کشف دانش
کشف دانش از پايگاه داده ها در واقع فرايند تشخيص الگوها و مدلهاي موجود در دادهها است.داده کاوي مرحله اي از فرايند کشف دانش است که با کمک الگوريتم هاي خاص داده کاوي و با کارايي قابل قبول محاسباتي، الگوها يا مدل ها را در داده ها پيدا ميکند.بر اساس ديدگاهي که داده کاوي را بخشي از فرايند کشف دانش ميدانند، کشف دانش شامل مراحل متعددي مطابق شکل (2-1) است :

2-2-3 حوزه ها و عملکردهاي داده کاوي
” کشف دانش و داده کاوي6″ يک حوزه ميان رشته اي است که با موضوعات زير مرتبط است : آمار، يادگيري ماشين، پايگاه داده، الگوريتم ها، مصور سازي، محاسبات موازي و کسب دانش7 براي سيستم هاي خبره.شکل (2-2) اين ارتباطات را نشان مي دهد.

حوزه هاي يادگيري ماشين8 و تشخيص الگو9 در مباحث مرتبط با نظريه ها و الگوريتم هاي استخراج الگو از داده ها با حوزه KDD به نوعي همپوشاني دارند.عملکردهاي داده کاوي در شکل (2-3) نشان داده شده اند :

دسته بندي : دسته بندي، فرايند يافتن مدلي است که با تشخيص دسته ها يا مفاهيم داده ميتواند دسته ناشناخته اشيا ديگر را پيش بيني کند.دسته بندي يک تابع يادگيري است که يک قلم داده را به يکي از دسته هاي از قبل تعريف شده نگاشت ميکند.داده هاي موجود به دو قسمت آموزش و آزمون تقسيم ميشوند.داده هاي آموزش براي يادگيـري قواعد توسط سيسـتم استفاده ميشوند و دادههاي آزمون براي بررسي دقت دسته بندي و جلوگيري از بيش برازش به کار ميروند]1[.
برخي روش هاي متداول دسته بندي عبارتند از :
درخت تصميم
دسته بندي بيزي : داراي دو نوع بيز ساده و شبکه هاي بيزي است.
شبکه عصبي پس انتشار10
ماشين هاي بردار پشتيبان
دسته بندي تلازمي
يادگيرندگان کاهل : نزديک ترين همسايگان، استدلال مبتني بر مورد11.
روش ماشين بردار پشتيبان در اين تحقيق مورد توجه است که در ادامه تشريح خواهد شد.

لازم به ذکر است که دسته بندي و خوشه بندي متفاوت هستند.دسته بندي هر جز از داده ها را بر مبناي اختلاف بين داده ها به مجموعه هاي از پيش تعريف شده دسته ها تصوير ميکند.در حالي که خوشه بندي داده ها را به گروه هاي مختلف(خوشه ها) که از قبل معين نيستند، (براساس مشابهت درون خوشه و تفاوت بيرون خوشه) تقسيم ميکند.لذا اگر بخواهيم با استفاده از مفهوم يادگيري، دسته بندي و خوشه بندي را متمايز کنيم، بايد بگوييم دسته بندي يادگيري با نظارت و خوشه بندي يادگيري بدون نظارت است.

2-3 کاربردهاي داده کاوي و کشف دانش
در بسياري از داده ها فنون KDD قابل به کار گرفتن هستند، براي مثال :
اطلاعات کسب و کار
تحليل داده هاي بازاريابي و فروش
تشخيص تقلب
تحليل نتايج آزمايشات فني
اطلاعات علمي
پايگاه داده هاي پزشکي
زلزله يابي در زمين شناسي
کنترل و زمان بندي
اطلاعات شخصي

2-4 چالش هايي براي KDD
پايگاه داده بزرگتر
پايگاه داده با صدها فيلد و جدول و اندازه هاي چند ميليارد بايتي کاملا متداول هستند و استفاده از پايگاه داده ترابايتي معمول ميشود.
بعد زياد
نه تنها اغلب تعداد زيادي رکورد در پايگاه داده ها وجود دارد بلکه تعداد زيادي فيلد ممکن است موجود باشند.بنابراين مساله داراي ابعاد زيادي است
بيش برازش12
وقني الگوريتم به دنبال بهترين پارامترهاي يک مدل خاص با استفاده از مجموعه محدودي داده ميگردد، ممکن است داده ها را بيش برازش کند که منجر به عملکرد ضعيف مدل روي داده هاي آزمون ميشود.
داده ها و دانش در حال تغيير
داده هاي در حال تغيير و بي ثبات13 ممکن است الگوهاي کشف شده قبلي را بياعتبار کند.
داده مفقوده و مغشوش
اين مشکل به خصوص در پايگاه داده هاي تجاري حاد است.اگر پايگاه داده از ابتدا با هدف کشف دانش طراحي نشده باشد ممکن است فاقد برخي ويژگي هاي مهم باشد.
روابط پيچيده بين فيلدها
ويژگي ها يا مقادير با ساختار سلسله مراتبي، روابط ميان ويژگيها و نيز انواع روشهاي پيچيده نمايش دانش، نياز به الگوريتم هايي دارند که به طور موثر از اين اطلاعات استفاده کنند.
قابل درک بودن الگوها
در بسياري از کاربردهاي داده کاوي، اينکه کشفيات براي انسان قابل فهم تر شوند، بسيار مهم است]1[.

2-5 پيش پردازش و آماده سازي داده ها :
آماده سازي داده ها براي داده کاوي هنر چلاندن و فشردن داده هاي موجود و بيرون کشيدن داده هاي با ارزش است.آماده سازي نيز به عنوان جزئي از داده کاوي بستگي به نوع مسئله و نيز روشها و ابزارهايي دارد که ميخواهيم بر روي داده به کار ببنديم.
آماده سازي داده ها حدود 60 تا 90 درصد زمان مورد نياز براي کاوش داده را صرف کرده و 75 تا 90 درصد موفقيت پروژه هاي داده کاوي به آن مربوط ميشود.ممکن است داده مفقوده يا تکراري باعث گمراهي شوند.ميتوان گفت داده ها در عالم واقع داراي آلودگي14 هاي زير هستند :
ناقص15 : مانند نمونه هاي ناکافي، کمبود مقادير برخي مشخصه ها
مغشوش16 : داده ها داراي خطا يا مقادير پرت هستند.
ناسازگار17 : داراي تناقض در کدها و يا نام ها هستند.

2-5-1اجزاي اصلي پيش پردازش داده ها

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

وظايف اصلي فاز پاکسازي داده ها عبارتنداز:
*پر کردن داده هاي مفقوده
* شناخت داده هاي پرت و هموار کردن داده هاي مغشوش
* درست کردن داده هاي ناسازگار
* حل کردن مشکل افزونگي که بر اثر يکپارچه ساختن داده ها ايجاد شده است.

مقادير مفقود:
در داده هاي اوليه که براي داده کاوي که در اختيار داريم ممکن است برخي نمونه ها براي برخي ويژگيها مقدار نداشته باشند. مثلا در داده هاي فروش ممکن است براي چند مشتري درآمد مشتري درج نشده باشد، ما به اين مقادير، مقادير مفقود مي گوييم.
داده مغشوش:
اغتشاش يا نويز، خطاي تصادفي يا مغايرت در متغير اندازه گيري شده است. مقادير ويژگي ممکن است به دلايل زير نادرست باشد:
*ابزارهاي معيوب جمع آوري داده.
* مسائل و مشکلات حين ورود داده.
* محدوديت فناوري.

2-5-1-2يکپارچه سازي داده ها
داده کاوي اغلب به يکپارچه سازي داده ( ادغام داده ها از چندين منبع داده) نياز دارد. همچنين ممکن است لازم باشد که داده ها به شکل مناسب داده کاوي تبديل شوند.
در اين مرحله، داده هاي چندين منبع را در يک مخزن منسجم ترکيب ميکنيم.مهم ترين مسئله شناخت موجوديتهاي مشابه درون چندين منبع است.مثلا اگر در پايگاه داده A براي مشتري فيلد A.Cust_id و در پايگاه داده B از فيلد B.Cust# به همان منظور استفاده شده باشد، در صورت عدم حذف يکي از اين دو، آنگاه مشکل افزونگي داده ايجاد ميشود. البته اين مشکل ميتواند درون يک پايگاه داده هم رخ دهد و آن وقتي است که يک فيلد از روي فيلد ديگري درون همان پايگاه داده قابل استنتاج بوده، در آن نگهداري شود. مثلا نگهداري تاريخ تولد و سن به صورت همزمان ايجاد افزونگي ميکند.
بنابراين براي رفع مشکل افزونگي داده ها بايستي فيلد هاي تکراري شناسايي شوند.استفاده از فرا داده و اطلاعاتي که در هنگام طراحي پايگاه داده مستند شده است، مي توان به ما کمک کند. علاوه بر اين استفاده از روشهاي آماري براي شناخت ويژگيهايي که داراي وابستگي هستند نيز به ما کمک ميکند. در واقع براي اين کار نياز به استفاده از تحليلهاي همبستگي داريم.
2-5-1-3 تبديل داده ها
در اين مرحله داده ها به شکل مناسب براي داده کاوي تبديل ميشوند.
2-5-1-3-1هموار سازي
با حذف کردن مقادير مغشوش داده سرو کار دارد. برخي روشهاي مورد استفاده براي هموارسازي عبارتند از بسته بندي، رگرسيون و خوشه بندي.حتي مشخصه هايي که انتظار مي رود خطاي کمي در مقاديرشان داشته باشند، مي توانند از هموارسازي مقاديرشان براي کاهش تغييرات تصادفي استفاده کنند. برخي روشها مثل شبکه هاي عصبي با توابع سيگموئيد يا درختان رگرسيوني در بازنمايي خود به طور ضمني هموارساز دارند.
2-5-1-3-2 تجميع
گاه عمليات تلخيص و تجميع بر روي داده ها انجام ميشود. براي مثال فروش روزانه ممکن است تجميع شده و به شکل فروش هفتگي يا ماهانه نمايش داده شود. اين کار عموما در ايجاد مکعب داده استفاده ميشود.
2-5-1-3-3 تعميم
در تعميم با استفاده از سلسله مراتب مفهومي، داده سطح پايين يا اوليه با مفاهيم سطح بالاتر جايگزين ميشود. براي مثال ويژگي طبقه اي مانند خيابان با مفهوم بالاتر مانند شهر يا کشور عموميت داده ميشود.
2-5-1-3-4 ساخت ويژگي
جايي که از ويژگي هاي موجود ويژگي جديدي ساخته شده و براي کمک به فرآيند داده کاوي به آن اضافه ميشود. براي مثال، ممکن است ويژگي مساحت را از ضرب دو ويژگي طول و عرض که موجودند، بسازيم.
2-5-1-3-5 نرمال سازي



قیمت: تومان


پاسخ دهید