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

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

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

استاد راهنما : جناب دکتر جواد وحيدي

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

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

زمستان 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 چالش هايي براي KDD 15
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دلايل استفاده از SVM 34
2-8-3 کاربردهاي SVM 35
2-8-4 مزايا و معايب SVM 36
2-8-5 تعاريف کلي 36
2-8-5-1تابع تصميم مسائل دو کلاسي 36
2-8-5-2 تعيين تابع تصميم(ابر صفحه جداکننده) 38
2-8-5-3 بعد VC 39
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 SCM 63
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-Link 67
2-9-2-2 روشهاي يادگيري جمعي 68
2-9-2-2-1الگوريتم آموزشي Bagging 69
2-9-2-2-2 الگوريتم آموزشي Boosting 70
2-9-3 روشهاي يادگيري عدم تعادل داخلي براي ماشين بردار پشتيبان 71
2-9-3-1 هزينه خطاي متفاوت 71
2-9-3-2 يادگيري يک کلاس 73
2-9-3-3zSVM 73
2-9-3-4 روشهاي اصلاح کرنل 74
2-9-3-5 يادگيري فعال 75
2-9-3-6 روش هاي ترکيبي 75
فصل سوم:روش تحقيق
3-1مقدمه 77
3-2 ماشين بردار پشتيبان فازي براي يادگيري عدم توازن کلاس 77
3-2-1 روش SVMFuzzy 77
3-2-2متد FSVM-CIL 79
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-8 38
شکل (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بيان مساله
هرچند که روشهاي مختلفي براي پيش پردازش داده ها موجود است ولي عملکرد و دقت اين روش ها متفاوت است و تلاش در جهت ارائه روشي کارامد امري ضروري است.با توجه به اهميت داده ها در جهان کنوني و افزايش حجم داده ها مساله پيش پردازش مناسب داده ها، بخصوص داده هاي نامتوازن يک چالش به نظر ميرسد.اغلب روش هاي موجود در پيش پردازش داده هاي ناتوازن به سمت کلاس اکثريت تمايل دارند و اين امر باعث مي شود که داده هاي کلاس اقليت به صورت نويز در نظر گرفته شود.
همانطور که پيش از اين نيز گفته شد براي دست يابي به نتايج مطلوب در داده کاوي نياز به پيش پردازش داده ها داريم.ميتوان ادعا کرد که اگر مرحله آماده سازي داده ها به خوبي صورت نپذيرد، نتايجي بدست ميآيد که نميتواند مورد استفاده قرار گيرد و ممکن است که هزينه و زمان به کار رفته براي دست يابي به نتيجه موثر هدر رود و نتايج حاصل به دليل عدم پيش پردازش مناسب داده غير قابل استفاده و نادرست باشد.
اخيراً مشكل نامتوازن بودن كلاسها مورد توجه محققان در زمينه ي داده كاوي قرار گرفته است. در موارد متعددي كلاسي كه از نقطه نظر دامنه ي كاربردي اهميت زيادي دارد(كلاس اصلي) شامل تعداد حالات كمتري نسبت به كلاسي است كه كلاس اكثريت ميباشد. اين مجموعه ي داده ها نامتوازن ناميده ميشود. رويكرد سنتي داده كاوي توانايي خوبي براي پيش بيني

دسته بندی : No category

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