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

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

درخت های تصمیم گیری: الگوریتم 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

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

۱۳۹۲-۸-۱۰ ۲۰:۴۲:۲۴ +۰۳:۳۰آبان ۱۰ام, ۱۳۹۲|عمومی دسته بندی ها|بدون ديدگاه

ثبت ديدگاه

پرداخت

1-پرداخت آنلاین
برای پرداخت آنلاین از لینک زیر استفاده کنید
پرداخت آنلاین
2- پرداخت آفلاین
برای پرداخت آفلاین مبلغ مورد نظر را به یکی از شماره کارت
6037997245888723بانک ملی