ParsX.com
پذیرش پروژه از دانشجویی ... تا سازمانی 09376225339
 
   ProfileProfile   Log in to check your private messagesLog in to check your private messages  |  FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups Log inLog in   RegisterRegister 

فصل 3 Decision Tree Learning

 
Post new topic   Reply to topic    ParsX.com Forum Index -> بازشناسی اماری الگو
View previous topic :: View next topic  
Author Message
vahid
بي تو هرگز


Joined: 26 Nov 2004
Posts: 3067
Location: Tehran

PostPosted: Fri Aug 14, 2020 11:27 am    Post subject: فصل 3 Decision Tree Learning Reply with quote

حتما فیلم statquest decision tree را از یوتیوب ببینید خیلی عالیه. Cool

یادگیری درخت تصمیم یکی از گسترده ترین و کاربردی ترین روش های استدلال استنتاجی است.
یک روش برای تخمین توابع با مقادیر گسسته ایست که داده های نویزی دارند و توانایی یادگیری عبارات انفصالی disjunctive expression را دارد. در این فصل الگوریتم های یادگیری مثل ID3 ASSISTANT C4.5 را تشریح می کنیم. این روش یادگیری درخت تصیمیم یک جستجوی کامل در فصال نمونه عبارات انجام می دهد و بنابرایناز مشکلات فضاهای نمونه محدود می کاهد. اریب استقرایی inductive bias یک ارجحیت برای درخت های کوچک روی درخت های بزرگ است.
Back to top
vahid
بي تو هرگز


Joined: 26 Nov 2004
Posts: 3067
Location: Tehran

PostPosted: Fri Aug 14, 2020 11:37 am    Post subject: 3.1 Introduction Reply with quote

یادگیری درخت تصمیم یک روش تخمین توابع هدفی که مقادیر گسسته می باشد که در آن تابع یادگیرنده توسط یک درخت تصمیم گیرنده نمایش داده می شود. درخت های آموخته شده می توانند توسط یک سری قوانین if then برای خوانده شدن بهتر بشری نمایش داده شوند. این روش های یادگیری در بین بیشترین الگوریتم های استدلال استنتاجی در طیف وسیعی از وظایف یادگیری از موارد پزشکی تا ارزیابی اعتبار به وام گیرندگان را شامل می شود. Laughing
Back to top
vahid
بي تو هرگز


Joined: 26 Nov 2004
Posts: 3067
Location: Tehran

PostPosted: Sun Aug 16, 2020 7:55 am    Post subject: 3.3 Appropriate problems for decision tree learning Reply with quote

در مثال اسکی بازی مفهوم playyingTennis بود که باید در برگ های درخت نتیجه این مفهوم را ببینیم.
درخت تصمیم نمایش disjunction of conjunctions می باشد. یعنی هر مسیر در درخت یک disjunction می باشد که با وصل کردن مقادیر true می شود قسمت conjunctions

گرچه روش های متعددی برای یادگیری به روش درخت تصمیم درست شده برای مسایل خاصی اما دقت کنید که درخت تصمیم برای مسایلی با مشخصات ذیل بهترین انتخاب می باشد:

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

+تابع هدف مقادیر گسسته در خروجی داردالبته خروجی را می توان به مقادیر عددی نیز تبدیل کرد اما کاربر در خت تصمیم در این زمره مسایل خیلی کم است Exclamation
+لزوم وجود توضیحات منفصل Disjunctive description
+داده های آموزشی ممکن است خطا داشته باشند. چه در مقادیری که خصایص آموزشی می گیرند و چه در خود خصایصی که نمونه ها را تشریح می کنند.
+داده های آموزشی ممکن است مقادیر گمشده missing داشته باشند. که بازهم روش برای آن وجود دارد.
در مسایلی که وظیفه طبقه بندی classify نمونه ها به یک مجموعه گسسته از مقادیر می باشد مسایل کلاس بندی classification problems گوییم.

۳.۴ الگوریتم ID3 را برای یادگیری بتصویر می کشد.
۳.۵ فضای فرضیه جستجویی برای این الگوریتم یادگیری را بررسی می کند
۳.۶ بایاس استقرایی این درخت تصمیم را تشریح می کند
۳.۷ بیش برازش داده های اموزشی و تکنیک های ان را توضیح می دهد. Idea
Back to top
vahid
بي تو هرگز


Joined: 26 Nov 2004
Posts: 3067
Location: Tehran

PostPosted: Sun Aug 16, 2020 1:55 pm    Post subject: 3.4 The basic decision tree learning algorithm Reply with quote

اکثر الگوریتم هایی که برای یادگیری به روش درخت تصمیم ایجاد شده اند از روش بالابه پایین و از روش جستجوی حریصانه استفاده می کنند. مثل الگوریتم های ID3 , C4.5
ID3 به روش بالا به پایین درخت را درست می کند. با پاسخ به این سوال که کدام خصیصه باید در ریشه هرم تست شود؟ برای جواب به این سوال هرخصیصه نمونه ارزشیابی می شود و به یک روش آماری جواب را برای کلاس بندی مثال های آموزشی پیدا می کند.

3.4.1 Which attribute is the best classifier?

یک ویژگی آماری به نام information gain تعریف می کنیم که اندازه می گیرد که خصیصه ای که به آن داده شده است به چه میزان خوبی مثالهای آموزشی را بر اساس هدف کلاسبندی تفکیک می کند.
ID3 با استفاده از این معیار information gain از بین خصایص کاندیدا در هر گام که درخت در حال رشد است معیار منتخب را جدامیکند Rolling Eyes
Back to top
vahid
بي تو هرگز


Joined: 26 Nov 2004
Posts: 3067
Location: Tehran

PostPosted: Tue Aug 18, 2020 7:41 am    Post subject: 3.4.1.1 Entropy measures homogeneity of examples Reply with quote

مفهوم تیوری اطلاعات و انتروپی را می توانید از لینک ذیل مشاهده فرمایید. Shocked
برای بدست اوردن مقدار مناسب برای information gain از معیار معمول entropy در تیوری اطلاعات استفاده می کنیم. اگر یک مجموعه ای مثل S داشته باشیم که شامل نمونه های مثبت و منفی مفهوم هدف باشد انتروپی S می شود
 -plogp-plogp = entropy(S)

در فرمول فوق یکی از p هامثبت و یکی دیگر منفی می باشد طبق فرمول ۳.۱ کتاب Wink که منفی یعنی نمونه های منفی در مجموعه S , .
Idea log0 چنده؟ بینهایت . در تمام محاسبات شامل انتروپی 0log0 صفر است. Arrow
Idea انتروپی که ۱ می شه؟ یعنی چی انتروپی ۱ یعنی هیچ اطلاعاتی عاید ما نشد. زمانی که تعداد نمونه های مثبت و منفی برابرباشد انتروپی ۱ است.
هرچقدر مقدار انتروپی از ۱ کمتر شود و به صفر نزدیک شود یعنی میزان اطلاعات ما بیشتر می شود.

یکی از تفاسیر انتروپی در تیوری اطلاعات این است که مشخص می کند تعداد حداقل بیت های اطلاعاتی که مورد نیاز است تا انکود کند دسته کلاس عضو دلخواه S را . مثلا اگر pمثبت ۱ باشد گیرنده می داند که نمونه استخراج شده مثبت است بنابراین هیچ پیامی برای ارسال لازم نیست و انتروپی صفر است. از طرف دیگر اگر p مقدارش ۰.۵ باشد یک بیت لازم است تا مشخص کند که نمونه استخراج شده مثبت است یا منفی . اگر pمثبت ۰.۸ باشد مجموعه ای از پیام ها روی میانگین کمتر از ۱ بیت بر پیام با مشخص کردن کدهای کوتاه تر برای مجموعه نمونه های مثبت و کدهای طولانی تر برای نمونه های منفی غیرمشابه تر استفاده می کند.
تا اینجا در مورد انتروپی برای مواردی که دسته بند هدف بولی بودند صحبت کردیم . بطور کلی اگر خصیصه هدف روی چند مقدار c مختلف باشد آنگاه انتروپی Sبر مبنای c توسط فرمول ۳.۳ مشخص می شود.
همان فرمول ۳.۲ منتها یک سیگما اضافه می شود و p مثبت و منفی اندیس iمیگیرند i=1 تاc منفی
Entropy(S)=Sigma(-PilogPi)

دقت کنید که لگاریتم پایه دو می باشد این به آن علت است معیار اندازه بر مبنای bits محاسبه می شود. Exclamation
توجه کنید که اگر خصیصه هدف c مقدار ممکن می گیرد انتروپی به بزرگی logc می شود.
Back to top
vahid
بي تو هرگز


Joined: 26 Nov 2004
Posts: 3067
Location: Tehran

PostPosted: Tue Aug 18, 2020 11:24 am    Post subject: 3.4.1.2 Information gain measures the expected reduction Reply with quote

...In Entropy
انتروپی معیار ناخالصی یک مجموعه از نمونه های آموزشی می باشد . می توانیم یک معیار کارا از موثر بودن خصیصه در کلاس بندی داده های آموزشی تعریف کنیم.
معیاری که استفاده می کنیم بهش می گن infromation gain

Gain(S,A)=Entropy(S)-Sigma(Sv/SEntropy(Sv))

فرمول بالا بیانگر این موضوع است که انتروپی S مجموعه اولیه می باشد بعد از رویت خصیصه A مجموعه S تقسیم شده است .Gain(S,A) میزان کاهش مورد انتظار در انتروپی است که با دیدن خصیصه A انتظار داریم . از منظری دیگر این میزان اطلاعاتی است که در مورد ارزش تابع هدف داریم

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


Last edited by vahid on Sun Aug 23, 2020 6:44 am; edited 3 times in total
Back to top
vahid
بي تو هرگز


Joined: 26 Nov 2004
Posts: 3067
Location: Tehran

PostPosted: Wed Aug 19, 2020 8:26 am    Post subject: 3.4.2 An Illustrative example Reply with quote

playTennis خصیصه هدف است target attribute این خصیصه هدف بر اساس سایر خصایص پیش بینی می شود .
در زیر جدول مثال ها playTennis را به عنوان target conept آورده است.
Back to top
vahid
بي تو هرگز


Joined: 26 Nov 2004
Posts: 3067
Location: Tehran

PostPosted: Sun Aug 23, 2020 10:02 am    Post subject: 3.6 Inductive bias in decision tree learning Reply with quote

در inductive bias همانطور که در فصل دو اشاره شد یعنی یک پیشفرضی برای حل مساله داشته باشیم . الگوریتمی وجود دارد به نام BFS-ID3 منطق الگوریتم این است که از درختی به عمق صفرش روع می کند و به درخت های با عمق بیشتر را بررسی می کند تا اخرسر درختی را پیدا می کند که کمترین عمق را داشته باشد و با داده های اموزشی ما سازگار باشد . این هم یک روش است .
بنابراین در الگوریتم BFS-ID3 پیشفرض این است که درخت های کوتاه تر ارجح تر هستند به درخت های بلند تر .
ID3 چگونه از فضای فرضیه که می تواند شامل درخت های زیادی باشد انتخاب می کند؟ الف درخت کوتاه تر را به نسبت بلندتر انتخاب می کند ب. درختی را انتخاب می کند که نودها بیتشرین مقدار را در information gain هر چه به ریشه درخت نزدیکتر باشند داشته باشند
چون ID3 از information gain و استراتژی تپه نوردی استفاده می کند پس از بایاس پیچیده تری نسبت به BFS-ID3 استفاده می کند. علی الخصوص همیشه بر کوتاهی درخت پافشاری ندارد بلکه خصیصه ای که بیشترین information gain را دارد به ریشه نزدیک قرار می دهد را ارجح می داند.
Back to top
vahid
بي تو هرگز


Joined: 26 Nov 2004
Posts: 3067
Location: Tehran

PostPosted: Mon Aug 24, 2020 12:35 pm    Post subject: 3.7.1.2 Rule post-pruning Reply with quote

در کاربرد یک روش موفق به نام rule post-pruning که دقت بالایی دارد یک گونه ای از این هرس کردن توسط C4.5 که رشد یافته الگوریتم ID3 می باشد.
ًَRule post-pruning شامل گام های ذیل است:‌
۱. درخت تصمیم را از داده های اموزشی استنتاج کنیداجازه دهید درخت تصمیم بصورت معمول رشد کند و اتفاقا بیش برازش هم اتفاق بیفتد.
۲. درخت یادگرفته شده را به مجموعه قوانینی تبدیل کنید که هر مسیر در درخت از ریشه به برگ یک قانون باشد.
۳. هرس کنید هر قانون را با حذف هر پیش شرطی که منتج به پیشرفت تخمین صحت شود.
۴.قوانین هرس شده را مرتب کنید و وقتی دارید نمونه هارا دسته بندی می کنید در نظر داشته باشید.
Back to top
vahid
بي تو هرگز


Joined: 26 Nov 2004
Posts: 3067
Location: Tehran

PostPosted: Tue Aug 25, 2020 7:37 am    Post subject: فصل ۹ کتاب آلپایدین Reply with quote

درخت تصمیم یک ساختمان داده سلسله مراتبی است که از روش تقسیم و غلبه استفاده می کند. روشی غیرپارامتری که هم برای کلاس بندی هم رگرسیون استفاده می شود.
۱. مقدمه :
در تخمین پارامتری مدل را بر اساس تمام فضای ورودی مشخص می کردیم و پارامترهایش را از داده های اموزشی یاد می گرفتیم. سپس برای هر ورودی تستی با استفاده از مدل یکسان و پارامترهای یکسان استفاده می کردیم.
در روش غیرپارامتری فضای ورودی را به مناطق محلی تقسیم می کنیم با معیار فاصله ای مثل نرم اقلیدسی و برای هر ورودی که مدل محلی متناسب با ان داده اموزشی در ان ناحیه باشد استفاده می کنیم. در مدل های instance-based با دادن یک رورودی باید مشخص می کردیم که داده محلی در مدل محلی قرار می گیرد یا نه که این هزینه بر بود چون باید فاصل داده ورودی به تمام نمونه های اموزشی را در زمان O(N) حساب می کردیم.
یک درخت تصمیم یک مدل سلسله مراتبی یادگیری نظارت شونده است که منطقه محلی در دنباله ای از قطعات بازگشتی در تعدادگام های کوچکتر شناسایی می شود .یک درخت تصمیم متشکل از نودهای داخلی تصمیم گیری و برگ های انتهایی هست. هر نود تصمیم گیری m یک تابع تست راfm(x) را پیاده سازی می کند با خروجی های گسسته که لیبل شاخه ها می شود. با دادن هر ورودی به هر نود یک تست اجرا می شود و یکی از شاخه ها خروجی را دریافت می کنند. این پروسس بصورت بازگشتی از ریشه شروع و به یک برگ ختم می شود که مقدار خروجی در برگ تشکیل دهنده خروجی است.
درخت تصمیم یک مدل غیرپارامتری است
هر نود برگ یک لیبل خروجی دارد که در کلاس بندی کد کلاس است و در رگرسیون یک مقدار عددی.
یک نود برگ یک محدوده محلی را در فضای ورودی مشخص می کند که وقتی نمونه ها در این محدوده میفتند لیبل های مشابهی دارند در کلاس بندی و اعدادخروجی مشابهی در رگرسیون دارند.
درخت تصمیم می تواند به یک سری قوانین if then تبدیل شود. بهترین حالت این است که اگر تصمیم گیری های باینری باشد هر تصمیم نصف کیس ها را حذف کند بنابراین اگر b منطقه داشته باشیم بهترین مورد در lgo2b تصمیم پیدا می شود.
درخت های تصمیم به همین دلیل قابلیت تبدیل به قوانین if-then بسیار خوانا و قابل تفسیر هستند لذا گاهی اوقات نسبت به روش های صحیح تر ارجح هستند.
برای یک مساله چندین درخت ممکن است جواب باشد اما دنبال درختی هستیم که کوتاهتر باشد. پیدا کردن کوچکترین درخت جز مسایل NP-Complete می باشد.
الگوریتم های یادگیری درخت حریصانه هستند که در هر گام با شروع از ریشه با داده آموزشی کامل دنبال بهترین شکاف هستیم. این تصمیم بسته به اینکه عددی باشد یا گسسته داده اموزشی را به دو یا n قسمت تقسیم می کند.بصورت بازگشتی زیرمجموعه ها را جدا می کنیم تا نیازی به جداسازی نداشته باشیم تا به ریشه برسیم.

univariate tree دز هر نود داخلی تست فقط یکی از ابعاد ورودی را چک می کند. اگر xj گسسته باشد به یکی از n شاخه هدایت می کند. برای مثال خصیصه رنگ red blue green نود دارای سه شاخه می شود.
نود تصمیم گیری شاخه های گسسته دارد و ورودی عددی باید گسسته شود مثلا بایک مقایسه بزرگتر کوچکتر شاخه خود را پیدا می کند.
Tree inductionساختن درخت با نمونه اموزشی می باشد. برای یک مجموعه اموزشی درخت های زیادی وجود دارد که کد میکند درخت را بدون خطا اما ما دنبال کوچکترین درخت هستیم.
impurity measure : در مورد کلاس بندی درخت تصمیم خوب بودن یک درخت کلاس بندی توسط معیار ناخالصی مشخص می شود . یک شکافی زمانی خالص و درست است که بعد از شکاف تمام شاخه ها تمام نمونه ها در هر شاخه به کلاس مشابهی تعلق داشته باشند. مثلا برای گره
نود mرا خالص می گوییم هرگاه برای تمام i ها(زیرشاخه) ۰ یا ۱ باشد.
حالا اگر نودما pure نبود باید نمونه ها باید شکافته شوند تا ناخالصی کم شود که باید بازانتخاب کنیم روی کدام خصیصه این شکاف را انجام دهیم
تمام خصایص چه گسسته و چه عددی باید ناخالصی را حساب کنیم و آنی را که حداقل انتروپی را دارد انتخاب کنیم . ساخت درخت بصورت بازگشتی ادامه پیدا می کند تا تمام شاخه های دارای ناخالصی خالص شوند. این مبنای الگوریتم CART می باشد. Classification and regression tree
Idea
می توان اینطوری بیان کرد که در هر مرحله ساخت درخت ما شکافی را انتخاب می کنیم که بیشترین کاهش در ناخالصی را داشته باشد . تفاصل بین ناخالصی داده و انتروپی در هر شاخه این اختلاف را نشان می دهد difference between the impurity of data and the total entropy of data
Back to top
vahid
بي تو هرگز


Joined: 26 Nov 2004
Posts: 3067
Location: Tehran

PostPosted: Mon Aug 31, 2020 9:57 am    Post subject: regression tree 9.2.2 Reply with quote

در رگرسیون معیار شکاف توسط خطای مربع میانه حساب می شود.
در مقایسه preprunning و postprunning باید بگم که اولی سریعتر اما دومی درخت های صحیح تری می دهد.
rule induction از روش DFS استفاده می کند و یک مسیر(قانون) در لحظه تولید می کند در حالیکه tree induction از روش BFS و تمام مسیرها را درلحظه تولید می کند.
Back to top
Display posts from previous:   
Post new topic   Reply to topic    ParsX.com Forum Index -> بازشناسی اماری الگو All times are GMT + 3.5 Hours
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum