آخرين ارسالهاي تالار

خطا: mod_kunenalatest:كيوننا نسخه 1.7 (يا بالاتر) بر روي سيستم شما نصب نيست!
پیغام
  • Kunena is not installed or the installed Kunena version is not supported. The plug-in has now been disabled. Please install/upgrade Kunena to version 1.7 for the Kunena Discuss Plug-in to function properly.
درخت های تصمیم گیری: الگوریتم ID3 مشاهده در قالب PDF چاپ فرستادن به ایمیل
نوشته شده توسط admin   
یکشنبه, 06 اسفند 1391 ساعت 21:09

درخت های تصمیم گیری: الگوریتم ID3

برای دسته بندی اطلاعات و نیز فرآیند انتخاب های ماشینی می توان از الگوریتم های تصمیم گیری استفاده کرد ، به طور مثال در ما می توانیم مقداری از اطلاعات را به یک کامپیوتر بدهیم و سپس از آن بخواهیم با گرفتن اطلاعات بعدی (بر اساس اطلاعات قبلی) برای ما تصمیم گیری کند. یکی از الگوریتم های موجود الگوریتم ID3 نام دارد که در سال 1975 توسط J. Ross Quinlan و در کتابMachine Learning معرفی شد.

به طور ساده یک الگوریتم id3 از تعدادی داده ثابت برای ما یک درخت تصمیم گیری می سازد که این درخت برای طبقه بندی کردن اطلاعات و در نتیجه تصمیم گیری به کار می روند . مثال هایی که ما به کامپیوتر می دهیم شامل تعدادی مشخصات و تعدادی کلاس هستند. به طور مثال وقتی می گوییم یک مرد باید از 170 سانتیمتر بلند تر باشد ، دو مولفه ی کلاس و مشخصه را تعریف کرده ایم که در اینجا مشخصه "اندازه ی قد" و کلاس "مرد بودن" است و یا ممکن است بگوییم یک زن حتما موهایی بلندتر از 30 سانتی متر دارد که در اینجا "اندازه ی مو" مشخصه و نیز "زن بودن" کلاس است.

انتخاب مشخصه ی کلاس بندی

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

 

جواب در یک متغییر آماری به نام ig و یا همان ضریب اطلاعات خلاصه شده است که این ضریب مشخص می کند که یک مشخصه "چقدر خوب؟"می تواند اطلاعات را دسته بندی کند و به این صورت بهترین مشخصه انتخاب می شود تا بر اساس آن طبقه بندی اطلاعات صورت گیرد یعنی همان مشخصه ای که ig بیشتری داشته باشد برای آنکه بتوانیم ig را تعریف کنیم باید از تئوری اطلاعات و نیز مفهوم آنتروپی استفاده نماییم (اگر با این مفهوم آشنا نیستید نگران نباشید زیرا نیازی به جزئیات نیست). آنتروپی میزان اطلاعاتی است که درون یک مشخصه گنجانده شده است و با فرمول زیر اندازه گیری می شود:

Entropy(S) = S -p(I) log2 p(I)

که در اینجا p(I) سهم نوع S در مجموعه ی I است.S مجموعه ی اطلاعاتی است که به کامپیوتر داده می  شود تا بر اساس آنها درخت تصمیم گیری را بسازد. در حقیقت آنتروپی نشان می دهد که تا چه حد اطلاعات دسته بندی شده اند. اگر آنتروپی به سمت صفر بروند یعنی اطلاعات کاملا دسته بندی شده اند .

به طور مثال مجموعه ای داریم که شامل 14 عضو است که در این مجموعه 9 yes و 5 no وجود دارد.

آنتروپی مجموعه به صورت زیر حساب می شود:

 

Entropy(S) = - (9/14) Log2 (9/14) - (5/14) Log2 (5/14) = 0.940

- Ig برای یک مجموعه از مثال (در اینجا s)به صورت زیر حساب می شود:

Gain(S, A) = Entropy(S) - S ((|Sv| / |S|) * Entropy(Sv))

که در آن :

s = تعداد کل اعضای مجموعه ی s

Sv = زیر مجموعه ای از S که مقدار مشخصه ی A آنها برابر v است.

|Sv| = اندازه زیر مجوعه

|S| = اندازه مجموعه

مثال : فرض کنید مجموعه ی s شامل 14 مثال است که یکی از مشخصات آنها باد است که باد می تواند ضعیف یا قوی باشد که نتایج این اطلاعات شامل 5 YES و 4 NO است. برای مشخصه ی باد 8 رخداد ضعیف و 6 رخداد قوی داریم و برای مشخصه ی باد ضعیف 6 نتیجه YES و 2 نتیجه ی NO داریم

Gain(S,Wind)=Entropy(S)-(8/14)*Entropy(Sweak)-(6/14)*Entropy(Sstrong)

= 0.940 - (8/14)*0.811 - (6/14)*1.00

= 0.048

Entropy(Sweak) = - (6/8)*log2(6/8) - (2/8)*log2(2/8) = 0.811

Entropy(Sstrong) = - (3/6)*log2(3/6) - (3/6)*log2(3/6) = 1.00

برای هر کدام از مشخصات ضریب حساب می شود و مشخصه ای که دارای بیشترین ضریب است به عنوان بهترین مشخصه برای طبقه بندی انتخاب می شود.

مثال معروف بازی کردن بیس بال:

فرض کنید که به وسیله ی الگوریتم می خواهیم تشخیص دهیم که آیا هوا برای بازی کردن بیس بال خوب است یا نه؟

در دوره ی دو هفته ای از بازی کردن بیس بال اطلاعات زیر جمع آوری شده است این اطلاعات به id3 کمک می کند تا یک درخت تصمیم گیری ساخته شود. هدف ساختن در ختی است که تعیین کند که آیا باید در یک روز با اطلاعات خاص بیس بال بازی کنیم یا نه؟

اطلاعات شامل :

نوع هوا{آفاتابی ، ابری ، بارانی}

دما {گرم ، معتدل ، سرد}

رطوبت {زیاد، کم}

شدت باد {قوی ، ضعیف}

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

Day

Outlook

Temperature

Humidity

Wind

Play ball

D1

Sunny

Hot

High

Weak

No

D2

Sunny

Hot

High

Strong

No

D3

Overcast

Hot

High

Weak

Yes

D4

Rain

Mild

High

Weak

Yes

D5

Rain

Cool

Normal

Weak

Yes

D6

Rain

Cool

Normal

Strong

No

D7

Overcast

Cool

Normal

Strong

Yes

D8

Sunny

Mild

High

Weak

No

D9

Sunny

Cool

Normal

Weak

Yes

D10

Rain

Mild

Normal

Weak

Yes

D11

Sunny

Mild

Normal

Strong

Yes

D12

Overcast

Mild

High

Strong

Yes

D13

Overcast

Hot

Normal

Weak

Yes

D14

Rain

Mild

High

Strong

No

ابتدا باید بفهمیم که کدام یک از مشخصات ریشه ی درخت تصمیم گیری هستند؟

برای این منظور باید آنتروپی تمامی مشخصات را حساب کنیم.

Gain(S, Outlook) = 0.246

Gain(S, Temperature) = 0.029

Gain(S, Humidity) = 0.151

Gain(S, Wind) = 0.048 (calculated in example 2)

بیشترین ضریب مربوط به نوع هوا است (Oultlook) ، بنا بر این به عنوان ریشه درخت ما مورد استفاده قرار می گیرد.

به خاطر اینکه نوع هوا شامل 3 مقدار است پس درخت تصمیم گیری شامل 3 شاخه می شود .

سوال بعدی این است که در شاخه ی نوع هوای آفتابی چه نوع تصمیم گیری باید انجام شود ؟

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

Ssunny = {D1, D2, D8, D9, D11} = 5 examples from table 1 with outlook = sunny

Gain(Ssunny, Humidity) = 0.970

Gain(Ssunny, Temperature) = 0.570

Gain(Ssunny, Wind) = 0.019

که در اینجا رطوبت دارای بیشترین ضریب است و به عنوان مشخصه تصمیم انتخاب می شود و این فرآیند ادامه پیدا می کند تا زمانی که مشخصات ما به اتمام برسد.

منبع: matlab-pro.blogfa.com

نظر ها (0)
تنها کاربران عضو شده می توانند نظر ارسال کنند!
 
logo-samandehi