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

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

فهرست مطالب
فصل اول مقدمه و کلیات تحقیق
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 تجمیع
گاه عملیات تلخیص و تجمیع بر روی داده ها انجام میشود. برای مثال فروش روزانه ممکن است تجمیع شده و به شکل فروش هفتگی یا ماهانه نمایش داده شود. این کار عموما در ایجاد مکعب داده استفاده میشود.

دسته بندی : پایان نامه ها

پاسخ دهید