شنبه 28 مهر 1397 | Saturday 20 th of October 2018 صفحه اصلی گروه الکترونیکی کامپیوتر
4-6-4- مدل ها و الگوریتم های داده کاوی

در این بخش قصد داریم مهمترین الگوریتم­ها و مدل­های داده­کاوی را بررسی کنیم. بسیاری از محصولات تجاری داده­کاوی از مجموعه­ای، از این الگوریتم­ها استفاده می­کنند و معمولا هر کدام انها در یک بخش خاص قدرت دارند وبرای استفاده از یکی از انها باید بررسی­های لازم در جهت انتخاب متناسب­ترین محصول توسط گروه متخصص در نظر گرفته شود.

نکته مهم دیگر این است که در بین این الگوریتم­ها و مدل­ها، بهترین وجود ندارد و با توجه به داده­ها و کارایی مورد نظر باید مدل انتخاب گردد.

شبکه­های عصبی:

شبکه­ های عصبی از پرکاربردترین و عملی­ترین روش­های مدل­سازی مسائل پیچیده و بزرگ، که شامل صدها متغیر هستند، می­باشد. شبکه­های عصبی می­توانند برای مسائل کلاس­بندی (که خروجی یک کلاس است) یا مسائل رگرسیون (که خروجی یک مقدار عددی است) استفاده شوند.

هر شبکه عصبی شامل یک لایه ورودیمی­باشد که هر گره در این لایه معادل یکی از متغیرهای پیش­بینی می­باشد. گره­های موجود در لایه میانی به تعدادی گره در لایه نهان، وصل می­شوند. هر گره ورودی به همه گره های لایه نهان وصل می­شود.

گره­های موجود در لایه نهان می­توانند به گره­های یک لایه نهان دیگر وصل شوند  یا می­توانند به لایه خروجی وصل شوند.

لایه خروجی شامل یک یا چند متغیر خروجی می­باشد.  

شکل 4-7- شبکه عصبی با یک لایه نهان

شکل 4-7- شبکه عصبی با یک لایه نهان

هر یال که بین نود های X,Yمی­باشد دارای یک وزن است که با Wx,y  نمایش داده می­شود. این وزن­ها در محاسبات لایه­های میانی استفاده می­شوند و طرز استفاده انها به این صورت است که هر نود در لایه­های میانی (لایه­های غیر از لایه اول) دارای چند ورودی از چند یال مختف می­باشدکه همانطور که گفته شد هر کدام یک وزن خاص دارند.

هر نود لایه میانی میزان هر ورودی را در وزن یال مربوطه ان ضرب می­کند و حاصل این ضرب­ها را با هم جمع می­کند و سپس یک تابع از پیش تعیین شده (تابع فعال­سازی) روی این حاصل اعمال می­کند و نتیجه را به عنوان خروجی به نودهای لایه بعد می­دهد.

وزن یال­ها پارامترهای ناشناخته­ای هستند که توسط تابع اموزش و داده­های اموزشی که به سیستم داده     می­شود، تعیین می­گردند.

تعداد گره­ها و تعداد لایه­های نهان و نحوه وصل شدن گره­ها به یکدیگر معماری  شبکه عصبی را مشخص می­کند. کاربر یا نرم­افزاری که شبکه عصبی را طراحی می­کند باید تعداد نودها، تعداد لایه­های نهان، تابع      فعال­سازی و محدودیت­های مربوط به وزن یال­ها را مشخص کند.

شکل4-8- Wx,y وزن یال بین X و Y است

شکل4-8- Wx,yوزن یال بین Xو Yاست.

از مهمترین انواع شبکه­های عصبی Feed-Forward Backpropagation می­باشد که در اینجا به اختصار انرا توضیح می­دهیم.

Feed-Forward  به معنی این است که مقدار پارامتر خروجی براساس پارامترهای ورودی و یک سری     وزن­های اولیه تعیین می­گردد.  مقادیر ورودی با هم ترکیب شده و در لایه­های نهان استفاده می­شوند و مقادیر این لایه­های نهان نیز برای محاسبه مقادیر خروجی ترکیب می­شوند.

Backpropagation: خطای خروجی با مقایسه مقدار خروجی با مقدار موردنظر در داده­های ازمایشی محاسبه می­گردد و این مقدار برای تصحیح شبکه و تغییر وزن یال ها استفاده می­شود و از گره خروجی       شروع شده و به عقب محاسبات ادامه می­یابد.

این عمل برای هر رکورد موجود در بانک اطلاعاتی تکرار می­گردد.

به هر بار اجرای این الگوریتم برای تمام داده­های موجود در بانک، یک دورهگفته می­شود. این دوره­ها انقدر ادامه می­یابند که دیگر مقدار خطا تغییر نکند.

از انجایی که تعداد پارامترها در شبکه­های عصبی زیاد می­باشد محاسبات این شبکه­ها می­تواند وقت­گیر باشد. ولی اگر این شبکه­ها به مدت کافی اجرا گردند معمولا موفقیت­امیز خواهند بود. مشکل دیگری که   ممکن است به وجود بیاید Overfitting می­باشد و ان بدین­صورت است که که شبکه فقط روی داده­ها اموزشی خوب کار می­کند و برای سایر مجموعه داده­ها مناسب نمی­باشد. برای رفع این مشکل ما باید بدانیم چه زمانی اموزش شبکه را متوقف کنیم. یکی از راه­ها این است که شبکه را علاوه  بر داده­های ازمایشی روی    داده­های تست نیز مرتبا اجرا کنیم و جریان تغییر خطا را در انها بررسی کنیم. اگر در این داده­ها به جایی رسیدیم که میزان خطا رو به افزایش بود حتی اگر خطا در داده­های ازمایشی همچنان رو به کاهش باشد اموزش را متوقف کنیم.

از انجایی که پارامترهای شبکه­های عصبی زیاد است یک خروجی خاص می­تواند با مجموعه­های مختلفی از مقادیر پارامترها ایجاد گردد، درنتیجه این پارامترها مثل وزن یالها قابل تفسیر نبوده و معنی خاصی نمی­دهند.

یکی از مهمترین فواید شبکه­های عصبی قابلیت اجرای انها روی کامپیوترهای موازی می­باشد.

درخت تصمیم[1]

درخت­های تصمیم روشی برای نمایش یک سری از قوانین هستند که منتهی به یک رده یا مقدار می­شوند. برای مثال، می­خواهیم متقاضیان وام را به دارندگان ریسک اعتبار خوب و بد تقسیم کنیم. شکل زیر یک درخت تصمیم را که این مسئله را حل می­کند، نشان می­دهد و همه مؤلفه­های اساسی یک درخت  تصمیم در ان نشان داده شده است: نود تصمیم، شاخه­ها و برگ­ها.

شکل 4-9- درخت تصمیم گیری

شکل 4-9- درخت تصمیم گیری

براساس الگوریتم، ممکن است دو یا تعداد بیشتری شاخه داشته باشد. برای مثال، CARTدرختانی با تنها دو شاخه در هر نود ایجاد می­کند. هر شاخه منجر به نود تصمیم دیگر یا یک نود برگ می­شود. با پیمایش یک درخت تصمیم از ریشه به پایین به یک مورد، یک رده یا مقدار نسبت می­دهیم. هر نود از داده­های یک مورد برای تصمیم­گیری درباره ان انشعاب استفاده می­کند.

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

یکی از تفاوت­ها بین متد­های ساخت درخت تصمیم، این است که این فاصله چگونه اندازه­گیری می­شود. درخت­های تصمیمی که برای پیش­بینی متغیرهای دسته­ای استفاده می­شوند، درخت­های دسته­بندینامیده        می­شوند زیرا نمونه­ها را در دسته­ها یا رده­ها قرار می­دهند. درخت­های تصمیمی که برای پیش­بینی متغیرهای پیوسته استفاده می­شوند درخت­های رگرسیون نامیده می­شوند.

هر مسیر در درخت تصمیم تا یک برگ معمولا قابل فهم است. از این لحاظ یک درخت تصمیم می­تواند پیش­بینی­های خود را توضیح دهد، که یک مزیت مهم است. با این حال این وضوح ممکن است گمراه­کننده باشد. برای مثال، جداسازی­های سخت در درخت­های تصمیم، دقتی را نشان می­دهند که کمتر در واقعیت نمود دارند. (چرا باید کسی که حقوق او 400001 است از نظر ریسک اعتبار، خوب باشد درحالیکه کسی که حقوقش 40000 است بد باشد. بعلاوه، از انجاکه چندین درخت می­توانند داده­های مشابه­ای را با دقت مشابه نشان دهند، چه تفسیری ممکن است از قوانین شود؟)

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

راه دیگر برای توقف، هرس کردن درخت است. درخت می­تواند تا اندازه نهایی گسترش یابد، سپس با استفاده از روش­های اکتشافی توکار یا با مداخله کاربر، درخت به کوچکترین اندازه­ای که دقت در ان از دست نرود کاهش می­یابد.

یک اشکال معمول درخت­های تصمیم اینست که انها تقسیم­کردن را براساس یک الگوریتم حریصانه انجام  می دهند که در ان تصمیم­گیری اینکه براساس کدام متغیر تقسیم انجام شود، اثرات این تقسیم در تقسیم­های اینده را درنظر نمی­گیرد.

بعلاوه الگوریتم­هایی که برای تقسیم استفاده می­شوند، معمولا تک ­متغیری هستند: یعنی تنها یک متغیر را در هر زمان در نظر می­گیرند. درحالیکه این یکی از دلایل ساخت سری مدل است، تشخیص رابطه بین متغیرهای پیش­بینی کننده را سخت­تر می­کند.

الگوریتمMARS[2]

در میانه­های دهه 80 یکی از مخترعین CART، ـJerome H. Friedman، متدی را برای برطرف­کردن این کاستی­ها توسعه داد.

کاستی­های اساسی که او قصد برطرف­ کردن انها را داشت عبارتند از:

  • پیش­بینی­های غیرپیوسته (تقسیم سخت)
  • وابستگی همه تقسیم­ها به تقسیم­های قبلی

به این دلیل او الگوریتم MARSرا توسعه داد. ایده اصلی MARSنسبتا ساده است، درحالیکه خود الگوریتم نسبتا پیچیده است. ایده بسیار ساده این الگوریتم، عبارت است از:

  • جایگزینی انشعاب­های غیرپیوسته با گذرهای پیوسته که توسط یک جفت از خط­های مستقیم مدل   می­شوند. در انتهای فرایند ساخت مدل، خطوط مستقیم در هر نود با یک تابع بسیار هموار که splineنامیده می­شود جایگزین می­شوند.
  • عدم نیاز به اینکه تقسیم­های جدید وابسته به تقسیم­های قدیمی باشند.

متأسفانه این به معنی این است که MARSساختار درختی CARTرا ندارد و نمی­تواند قوانینی را ایجاد کند. از طرف دیگر، MARSبه صورت خودکار مهم­ترین متغیرهای پیش­بینی کننده و همچنین تعامل میان انها را    می­یابد.  MARS،  همچنین وابستگی میان پاسخ و هر پیش­بینی کننده را معین می­کند.

MARS، مانند بیشتر الگوریتم­های شبکه­های عصبی و درخت تصمیم، تمایل به overfitشدن برای داده­های اموزش­دهنده دارد. که می­توان انرا به دو طریق درست کرد. اول اینکه، وارسی اعتبار[3]، بصورت دستی انجام شود و الگوریتم برای تولید پیش­بینی خوب روی مجموعه تست تنظیم شود. دوم اینکه، پارامترهای تنظیم متفاوتی در خود الگوریتم وجود دارد که وارسی اعتبار درونی را هدایت می­کند.

استنتاج قوانین

استنتاج قوانین متدی برای تولید مجموعه­ای از قوانین است که موارد را دسته­بندی می­کند. اگرچه      درخت­های تصمیم می­توانند مجموعه­ای از قوانین را ایجاد کند، متدهای استنتاج قوانین مجموعه­ای از قوانین مستقل را ایجاد می­کند. که لزوما یک درخت را ایجاد نمی­کنند. از انجا که استنتاج­گر قوانین، اجباری به تقسیم در هر سطح ندارد، و می­تواند به اینده بنگرد، قادر است الگوهای متفاوت و گاها بهتری برای رده­بندی بیابد. برخلاف درختان، قوانین ایجاد شده ممکن است همه موارد ممکن را نپوشاند. همچنین برخلاف درختان، قوانین ممکن است در پیش­بینی متعارض باشند، که در هر مورد باید قانونی را برای دنبال کردن انتخاب کرد. یک روش برای حل این تعارضات انتصاب یک میزان اطمینان به هر قانون است و استفاده از قانونی است که میزان اطمینان بالاتری دارد.

K-نزدیکترین همسایگی(k-NN)[4]واستدلال مبتنی بر حافظه(MBR)[5]

هنگام تلاش برای حل مسائل جدید، افراد معمولا به راه­حل های مسائل مشابه که قبلا حل شده­اند مراجعه می کنند. K- نزدیکترین همسایگی، یک تکنیک دسته­بندی است که از نسخه­ای از این متد استفاده می­کند. در این روش تصمیم­گیری اینکه یک مورد جدید در کدام دسته قرار گیرد با بررسی تعدادی(k) از شبیه ترین موارد یا همسایه­ها انجام می­شود. تعداد موارد برای هر کلاس شمرده می­شوند، و مورد جدید به دسته­ای که تعداد بیشتری از همسایه­ها به ان تعلق دارند نسبت داده می­شود.

شکل 4-10- محدوده همسایگی (بیستر همسایه ها در دسته X قرار گرفته اند

شکل 4-10- محدوده همسایگی (بیستر همسایه ها در دسته Xقرار گرفته اند)

اولین مورد برای بکاربردن k-NNیافتن معیاری برای فاصله بین صفات در داده­ها و محاسبه ان است. در حالیکه این عمل برای داده­های عددی اسان است، متغیرهای دسته­ای نیاز به برخورد خاصی دارند. هنگامیکه فاصله بین مواد مختلف را توانستیم اندازه بگیریم، می­توانیم مجموعه مواردی که قبلا دسته­بندی شده­اند را بعنوان پایه دسته­بندی موارد جدید استفاده کنیم، فاصله همسایگی را تعیین کنیم، و تعیین کنیم که خود همسایه­ها را چگونه بشماریم.

K-NN،  بار محاسباتی زیادی را روی کامپیوتر قرار می­دهد زیرا زمان محاسبه بصورت فاکتوریلی از تمام نقاط افزایش می­یابد. درحالیکه بکار بردن درخت تصمیم یا شبکه عصبی برای یک مورد جدید فرایند سریعی است، K-NN، نیاز به محاسبه جدیدی برای هر مورد جدید دارد. برای افزایش سرعتK-NNمعمولا تمام    داده­ها در حافظه نگه­داری می­شوند.

فهم مدل­های K-NNهنگامیکه تعداد متغیرهای پیش­بینی کننده کم است بسیار ساده است. انها همچنین برای ساخت مدل­هایی که شامل انواع داده غیر استاندارد هستند، مانند متن، بسیار مفیداند. تنها نیاز برای انواع داده جدید وجود معیار مناسب است.  

 رگرسیون منطقی[6]

رگرسیون منطقی یک حالت عمومی­تر از رگرسیون خطی می باشد. قبلا این روش برای پیش­بینی مقادیر باینری یا متغیرهای دارای چند مقدار گسسته (کلاس) استفاده می­شد. از انجایی که مقادیر مورد نظر برای    پیش­بینی مقادیر گسسته می­باشند نمی توان انرا به روش رگرسیون خطی مدل­سازی کرد برای این منظور این متغیرهای گسسته را به روشی تبدیل به متغیر عددی و پیوسته می­کنیم وبرای این منظور مقدار لگاریتم احتمال متغیر مربوطه را در نظر می­گیریم و برای این منظور احتمال پیشامد را بدین صورت در نظر می­گیریم:

احتمال اتفاق نیفتادن پیشامد/ احتمال اتفاق افتادن پیشامد

و تفسیر این نسبت مانند تفسیری است که در بسیاری از مکالمات روزمره در مورد مسابقات یا             شرط­بندی­های  موارد مشابه به کار می­رود. مثلا وقتی می گوییم شانس بردن یک تیم در مسابقه 3 به 1 است    در واقع از همین نسبت استفاده کرده و معنی ان این است که احتمال برد ان تیم 75% است.

وقتی که ما موفق شدیم لگاریتم احتمال مورد نظر را بدست اوریم با اعمال لگاریتم معکوس می­توان نسبت مورد نظر و از روی ان کلاس مورد نظر را مشخص نمود.

 تحلیل تفکیکی[7]

این روش از قدیمی­ترین روش­های ریاضی­وار گروه­بندی داده­ها می­باشد که  برای اولین بار در سال 1936 توسط فیشر استفاده گردید. روش کار بدین صورت است که داده­ها را مانند داده­های چند بعدی بررسی کرده و بین داده­ها مرزهایی ایجاد می­کنند (برای داده­های دو بعدی خط جدا کننده، برای داده­های سه بعدی سطح جدا کننده و. . ) که این مرزها مشخص کننده کلاس­های مختلف می­باشند و بعد برای مشخص کردن کلاس مربوط به داده­های جدید فقط باید محل قرارگیری ان را مشخص کنیم.

این روش از ساده­ترین و قابل رشدترین روش­های کلاس­بندی می­باشد، که در گذشته بسیار استفاده می­شد.

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

نسخه­های اخیر تحلیل تفکیکی بعضی از این مشکلات را رفع کرده­اند به این طریق اجازه می­دهند مرزهای جداکننده بیشتر از درجه 2 نیز باشند که باعث بهبود کارایی و حساسیت در بسیاری از موارد می­گردد.

مدل افزودنی کلی (GAM)[8]

این روش­ها در واقع بسطی بر روش­های رگرسیون خطی و رگرسیون منطقی می­باشند. به این دلیل به این روش افزودنی می­گویند که فرض می­کنیم، می­توانیم مدل را به صورت مجموع چند تابع غیر خطی (هر تابع برای یک متغیر پیش­بینی کننده) بنویسیم. GAMمی تواند هم به منظور رگرسیون و هم به منظور کلاس­بندی داده­ها استفاده گردد. این ویژگی غیر خطی بودن توابع باعث می­شود که این روش نسبت به روش­های رگرسیون خطی بهتر باشد.

Boosting

در این روش­ها مبنا کار این است، که الگوریتم پیش­بینی را چندین بار و هر مرتبه، با داده­های اموزشی متفاوت (که با توجه به اجرای قبلی انتخاب می­شوند) اجرا کنیم و در نهایت ان جوابی که بیشتر تکرار شده را انتخاب کنیم. این روش اگر چه وقت­گیر است ولی جواب­های  ان مطمئن­تر خواهند بود. این روش اولین بار در سال 1996 استفاده شد و در این روزها با توجه به افزایش قدرت محاسباتی کامپیوترها، مقبولیت ان افزایش   یافته است.


[1]Decision tree

[2]Multivariate Adaptive Regression Spline

[3]cross validation

[4]K-nearest neibour

[5]memory-based reansoning

[6]Logistic regression

[7]Discriminant analysis

[8]Generalized  Additive Model 

Compatability by:
آخرین به روز رسانی سایت: سه شنبه, 22 اسفند 1391 - 00:26