درخت تصمیم گیری

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

در بسیاری از از مواقع اکتساب دانش از فرد خبره سخت و مشکل است ؛ این مسئله بدین دلیل است که وقتی میزان خبرگی بالا می‌رود ، فرد خبره ، مسائل و جزئیاتی را بدیهی فرض می‌کند ، در حای که مهندس دانش نیاز به این جزئیات برای طراحی سیستم خبره دارد. به عبارت ساده ، در این موارد فرد خبره با سوال و جواب ، پاسخ‌های مناسبی به مهندس دانش نمی‌دهد. راه‌حل یا راه‌حل ها کدامند؟

در این موارد فرد خبره نمی‌تواند بگوید مساله را چگونه حل نموده است و مهندس دانش ، خود باید راه‌حل را با روش استقرا بیابد.

استقرا (Induction)

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

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


نکته
درخت تصمیم‌گیری ؛ روشی برای نمایش یک سری از قوانین است که منتهی به یک رده یا مقدار می‌شود..


روند کلی:

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

پرسش: اگر سکه‌ای را یک میلیون بار بیندازیم ، چنانچه این نتایج را بخواهیم برای فرد دیگری ارسال کنیم ، به چه تعداد بیت نیاز خواهد بود؟

برای پاسخ به این سوال دو حالت زیر را درنظر بگیرید:

حالت اول:سکه سالم باشد

احتمال وقوع خط = احتمال وقوع شیر (در هر پرتاب)

تعداد بیت‌ها جهت نمایش وضعیت هر پرتاب = 1بیت

تعداد کل بیت‌های موردنیاز = 1000000 bits

حالت دوم : سکه ناسالم باشد

فرض کنید احتمال شیرآمدن 1.1000 و احتمال خط آمدن 999.1000 باشد.

در یک میلیون پرتاب انتظار داریم 1000بار شیر بیاید.


نکته
دنباله نمایش سکه‌های ناسالم ، حاوی اطلاعات کمتری نسبت به دنباله نمایش سکه‌های سالم است ، لذا به بیت‌های کمتری برای انتقال نیاز دارد.


محتوای اطلاعاتی(Information Content)

تعداد بیت‌های لازم برای ارسال یک دنباله با استفاده از یک کدگذاری بهینه .

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

مثال:

1000 بار پرتاب یک تاس 8 وجهی را در نظر بگیرید:

حالت اول : تاس سالم باشد

تعداد بیت‌های موردنیاز برای بیان وضعیت پرتاب تاس : 3 بیت به ارسال 3000 بیت نیاز خواهیم داشت.

حالت دوم: تاس ناسالم باشد

فرض کنید احتمال آمدن وجه (i(i=1...8 به صورت زیر است و کدهای زیر را به هر یک از 8 حالت تاس اختصاص دهیم:

A → 0

B → 10

C → 110

D → 1110

E → 11110

F → 111110

G → 1111110

H → 1111111

نرخ وقوع آن حالت* تعداد بیت‌های هر حالت ∑ = متوسط بیت‌های مورد نیاز برای ارسال

آنتروپی

فرض کنید دو نفر x و y که یکی از آنها یک سوال می‌پرسد و دیگری به آن سوال پاسخ بله یا خیر می‌دهد.

مقدار اطلاعاتی که در این سوال - جواب‌ها بین طرفین رد و بدل می‌شود ، آنتروپی نامیده ‌می‌شود.

فکر می‌کنید با یک سوال - جواب چه مقدار اطلاعات بدست خواهید آورد؟

مثال:

توپی داخل یکی از دو جعبه قرار دارد

الف) آیا توپ داخل جعبه سمت راست است؟ ب) بله

با یک سوال - جواب می‌توان فهمید که توپ کجاست . پس می‌توان گفت که مقدار اطلاعات 1 بیت است.

مثال:

مثالی از آنتروپی.JPG

الف) آیا توپ داخل جعبه‌های بالایی است؟ ب) خیر

الف) آیا توپ داخل جعبه سمت راستی است؟ ب) خیر

مقدار اطلاعات 2 بیت است.

کلاس‌بندی و آنتروپی

فرض کنید 5 کلاس A,B,C,D,E را داریم و می‌خواهیم یک شی را در آنها کلاس‌بندی کنیم

الف) اگر عدم قطعیت نداشته باشیم:

احتمال : A = 0 ، B = 1 ، C = 0 ، D = 0 ، E = 0

H(x) = 0Log(1/0) + 0Log(1/1) + 0Log(1/0) + ... = 0 (عدم قطعیت نداریم)

ب) اگر بین دو کلاس شک داشته باشیم:

احتمال : A = 0.5 ، B = 0.5 ، C = 0 ، D = 0 ، E = 0

H(x) = 0.5Log(1/0.5) + 0.5Log(1/0.5) + 0 ... = 1

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

ج) اگر بین چهار کلاس شک داشته باشیم:

احتمال : 25.A = 0.25 ، B = 0 ، C = 0.25 ، D = 0.25 ، E = 0

H(x) = 0.25Log(1/0.25) + 0Log(1/0) + ... = 2

د) اگر حالت زیر را بین کلاس‌ها داشته باشیم:

احتمال : 125.A = 0.5 ، B = 0.125 ، C = 0.125 ، D = 0.125 ، E = 0

H(x) =2.

اگر بخواهیم اطلاعات را ارسال کنیم به طور متوسط (زمانی) به و بیت احتیاج داریم.

A =1 ، B = 000 ، C = 001 ، D = 010 ، E = 011


نکته
هرچه همه کلاس‌ها به طور یکنواخت محتمل شوند ، (H(X بزرگتر می‌شود ، یعنی میزان عدم قطعیت در انتخاب کلاس ، افزایش می‌یابد.


آنتروپی (عدم قطعیت) و اطلاعات دو روی یک سکه‌اند!

در تئوری اطلاعات تنها سمبل‌هایی که برای گیرنده دارای عدم قطعیت هستند ، به عنوان اطلاعات قلمداد می‌شوند.( تنها اطلاعاتی که برای فهمیدن اساسی هستند ، باید فرستاده شوند.)

اطلاعات

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

بهره اطلاعاتی (Information Gain)

بعد از آزمون یک صفت به چند بیت نیاز داریم؟ صفت مورد آزمایش چقدر به ما اطلاعات می‌دهد؟

Gain (A) = Info (I) - Reminder (A) = Info(I) - Info(I,A)

در استفاده از بهره اطلاعاتی باید آن صفت یا attributeای را انتخاب کرد که بیشترین بهره اطلاعاتی را داراست و معمولا از فرمول نرمال‌سازی شده در محاسبه بهره اطلاعاتی استفاده می‌شود.

Gain Ratio(A) = Info(I) - Info(I,A) / SplitInfo

(Split(A عدم قطعیت نمونه‌ها نسبت به صفت A است.

(Split(A در دو حالت بزرگ می‌شود:

1. تعداد شاخه‌های k (مقادیر صفت A) بیشتر شود.

2. تعداد نمونه‌ها در هر کلاس j کم باشد.

بروز دو حالت فوق موجب جامعیت کمتر صفت می‌شود.

پرسش: چرا از فرمول بهره اطلاعاتی به صورت نرمال شده استفاده می‌کنیم؟

جواب:

ما به دنبال صفت Aای هستیم که: اولا بهره اطلاعاتی بالاتری داشته باشد ثانیا جامعیت کلاس‌بندی آن بیشتر باشد.