الگوريتم درخت تصمیم

[nagola]

سلام. بچه ها با استادم کل کل کردم، خواهش میکنم کمکم کنید کم نیارم!
در مورد درخت تصمیم مطلب میخوام.الگوریتم درخت تصمیم مخصوصا c5 و Id3

 

[آبجی]

سلام. بچه ها با استادم کل کل کردم، خواهش میکنم کمکم کنید کم نیارم!
در مورد درخت تصمیم مطلب میخوام.الگوریتم درخت تصمیم مخصوصا c5 و Id3

مگه با استاد کل کل میکنند ؟؟؟

دیگه کل کل نکنیا بیا اینم کمک :

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

الگوریتم پایهءID3 – این الگوریتم درختان تصمیم از بالا به پایین می سازد و با طرح این سوال که چه صفتی باید در ریشهء درخت آزمایش شود آغاز می کند. برای پاسخ به این سوال، با استفاده از یکی از انواع آزمایش های آماری برای تعیین مناسب ترین صفت برای دسته بندی مثال های آموزشی، تصمیم براساس هر صفت نمونه را ارزیابی می کند. سپس بهترین صفت را انتخاب کرده و به عنوان تست در گرهء ریشهء درخت استفاده می کند. برای هر مقدار ممکن صفت تست شده در ریشه، یک گرهء متناظر ایجاد شده و مثال های آموزشی براساس مقادیر صفت تست، بین این گره ها افراز می شوند. تمام فرایند ذکر شده، با استفاده از مثال های آموزشی نسبت داده شده به هر گره، برای انتخاب بهترین صفت برای آزمایشی در آن گرهء درخت تکرار می شود. این روش جستجویی حریصانه را برای یک درخت تصمیم قابل قبول ارائه می دهد که در این الگوریتم، هیچ گاه برای در نظر گرفتن دوبارهء انتخاب های قبلی، به عقب برگشت نمی شود. این الگوریتم در یادگیری نمونه هایی با صفات فاقد مقدار مشکل داشته و غیرافزایشی و ارزان می باشد.

ID3 (Examples, Target_Attribute, Attributes)​

Create a root node for the tree​

If all examples are positive, Return the single-node tree Root, with label = +.​

If all examples are negative, Return the single-node tree Root, with label = -.​

If number of predicting attributes is empty, then Return the single node tree Root, with label = most common value of the target attribute in the examples.​

Otherwise Begin​

• A = The Attribute that best classifies examples.
• Decision Tree attribute for Root = A.
• For each possible value, vi, of A,
  • Add a new tree branch below Root, corresponding to the test A = vi.
  • Let Examples(vi), be the subset of examples that have the value vi for A
  • If Examples(vi) is empty
    • Then below this new branch add a leaf node with label = most common target value in the examples
  • Else below this new branch add the subtree ID3 (Examples(vi), Target_Attribute, Attributes – {A})

End​

Return Root​

توسط Schlimmer &Fisher توسعه یافته است و یک الگوریتم افزایشی می باشد. نتیجهء نهایی ID3 را تولید می کند اما زمان بیشتری می برد. این الگوریتم از تست χ2 برای استقلال استفاده می کند و زمانی که داده های آموزشی دارای نویز باشند مانع از اورفیتینگ داده های آموزشی خواهد شد.

الگوریتم ID4-hat – تغییریافتهء الگوریتم ID4 است؛ به شکلی که اگر درخت موجود نتواند نمونهء جدید را به شکل صحیح دسته بندی کند این الگوریتم درخت را دوباره می سازد. اگر درخت نتواند دوباره ساخته شود بنابراین بهترین درخت نخواهد بود. در این حالت نتیجه با درخت نهایی تولید شده توسط ID3 متفاوت خواهد بود. هر دوی این الگوریتم ها وقتی بی نظمی صفر است یا تعداد خروجی های تصمیم را نگه می دارند و وقتی تمام ... بجز یکی صفر است آن را متوقف می کنند.

الگوریتم ID5 – یک الگوریتم افزایشی بهبود یافته است که توسط Utgoff توسعه یافته و همانند الگوریتم ID4 شروع می شود. وقتی یک نمونهء جدید اضافه می شود، اگر توسط درخت موجود به شکل صحیح دسته بندی نشود بهترین صفت بعدی را با استفاده از نفع اطلاعات برای دسته بندی این مثال اضافه می کند (در غیر این صورت درخت موجود را حفظ می کند.). در هر مرحله، اگر برای تمام نمونه هایی که تا این مرحله دیده شده اند، صفت پایین تر به نسبت صفت بالاتر بی نظمی شرطی کوچکتری داشته باشد درخت را با انجام تقسیم، معکوس کردن، ادغام و ساده سازی دوباره می سازد.

الگوریتم ID5-hat – در الگوریتم ID5 هرگاه که یک نمونهء آموزشی اضافه می شود، بی نظمی های شرطی دوباره کنترل می شوند (و در صورت لزوم ساختار درخت تغییر می یابد.). این الگوریتم مشابه الگوریتم ID5 می باشد جز اینکه بی نظمی های شرطی فقط زمانی دوباره درنظر گرفته می شوند که درخت قادر به دسته بندی صحیح یک نمونهء جدید نباشد.
الگوریتم C4.5 - نسل بعدی الگوریتم ID3 است و از نوعی از قانون هرس بعدی استفاده می کند. همچنین قادر است صفات گسسته، صفات فاقد مقدار و داده های نویزی را استفاده کند. این الگوریتم بهترین صفت را با استفاده از معیار بی نظمی انتخاب می کند و به دلیل استفاده از عامل GainRatio قادر به بکارگیری صفات با مقادیر بسیار زیاد می باشد. حتی اگر هیچ خطایی در داده های آموزشی وجود نداشته باشد هرس انجام می شود که باعث می شود درخت عام تر شده و کمتر به مجموعهء آموزشی وابسته شود.
هرس در این الگوریتم نسبتاًٌ پیچیده و برپایهء توزیع دوجمله ای و به شکل بازگشتی به برگ های درخت است. وقتی هرس یک شاخه متوقف می شود به سمت بالا ادامه نمی یابد. برای ممانعت از داشتن برگ هایی با یک نمونهء آزمایشی، جداسازی بیشتر روی دسته هایی که در حال حاضر به دو عنصر کاهش یافته اند انجام نمی شود. هرس فقط زمانی انجام می شود که تعداد پیش بینی شدهء خطاها افزایش نیابد. این الگوریتم، با در نظر گرفتن بی نظمی های هریک از آنها برای هر موردی که برای آنها داده داده شده است یک صفت را انتخاب می کند. بعد از انتخب بهترین صفت، موارد صفات فاقد مقدار با مقادیری از صفت در بخشی از مواردی که داده فراهم است تخصیص می یابند و الگوریتم ادامه می یابد.

منبع :
http://ceit.aut.ac.ir/~shiry/lecture/machine-learning/tutorial/dt/Pages/DT-Algorithms.htm

 

[آبجی]

اینا هم بهت کمک میکنه :

http://www.pnr.blogfa.com/post-20.aspx


http://fumblog.um.ac.ir/fumindex.php?op=ViewArticle&articleId=776&blogId=30

اینو دانلود کن خوبه منم خودم دانلود کردمش دارم میخونمش
http://www.google.com/url?sa=t&source=web&cd=13&ved=0CCYQFjACOAo&url=http%3A%2F%2Fceit.aut.ac.ir%2F~shiry%2Flecture%2Fmachine-learning%2FDecision%2520Tree.ppt&rct=j&q=%D8%A7%D9%84%DA%AF%D9%88%D8%B1%DB%8C%D8%AA%D9%85%20%D8%AF%D8%B1%D8%AE%D8%AA%20%D8%AA%D8%B5%D9%85%DB%8C%D9%85&ei=j_RLTbacG86hOr_SsfUP&usg=AFQjCNF55i1WWIBk5oAl5rK0QlqP8eT9Eg&cad=rja

 

[nagola]

مرسیییییی آبجی جووونم. واقعا ممنون.
الگوریتم c5 رو کسی نداره؟​