موضوع مقاله: الگوریتم C4.5 | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # الگوریتم C4.5 | مقدمه: C4.5 الگوریتمی است که برای تولید درخت تصمیم در یک مجموعه داده استفاده می‌شود و توسط راس کوینلان ابداع شده‌است.Quinlan, J. | ## بخش 1: الگوریتم C4.5 | درخت‌های تصمیم تولید شده توسط این الگوریتم برای طبقه‌بندی به کار گرفته می‌شوند، به همین دلیل الگوریتم C4.5 به عنوان یک طبقه‌بندی آماری شناخته می‌شود. الگوریتم C4.5 درخت تصمیم را با روشی مانند الگوریتم آی‌دی۳ و با استفاده از مفهوم آنتروپی بر روی داده‌های آموزش می‌سازد. الگوریتم C4.5 با یک مجموعه اصلی مانند S شروع می‌شود که به‌عنوان گره ریشه شناخته می‌شود. در هر تکرار از الگوریتم، برای هر ویژگی در مجموعه S که تا آن مرحله مورد استفاده قرار نگرفته‌است، مقدار آنتروپی H(s) آن ویژگی یا مقدار بهره اطلاعات IG(S) آن محاسبه می‌شود و ویژگی‌ای که دارای کمترین مقدار آنتروپی (یا بیشترین کسب اطلاعات (درخت تصمیم) باشد را انتخاب می‌کند. سپس به وسیلهٔ ویژگی انتخاب شده تقسیم می‌شود تا زیرمجموعه‌هایی از داده‌ها را تولید کند و الگوریتم همچنان باتوجه به ویژگی‌هایی که تا قبل از آن تکرار انتخاب نشده‌اند یه صورت بازگشتی بر روی مجموعه داده‌های تولیده شده به فرایند تقسیم کردن ادامه می‌دهد. این الگوریتم بازگشتی چند حالت پایه دارد: اگر همه نمونه‌ها در یک زیرمجموعه فقط متعلق به یک کلاس باشند، یک گره برگ می‌سازد و برچسب آن را کلاس نمونه (یا نمونه‌هایی) که در خود دارد می‌گذارد. اگر هیچ‌کدام از ویژگی‌ها به ما بهره اطلاعاتی ندهد، با استفاده از امید ریاضی کلاس یک گره تصمیم بر روی درخت می‌سازد. اگر نمونه‌ای از کلاسی که قبلاً دیده نشده‌است بیاید، مشابه قبلی با استفاده از امید ریاضی کلاس یک گره تصمیم بر روی درخت می‌سازد. مجوعه S را با استفاده از ویژگی‌ای که بیشترین بهره اطلاعاتی را دارد به زیرمجموعه‌هایی افراز (تقسیم) کنید. | ## بخش 2: الگوریتم C4.5 | باتوجه به ویژگی‌های باقیمانده، این عمل را به‌صورت بازگشتی برروی زیرمجموعه‌ها تکرار کنید. معیارهای ID3 میزان آنتروپی معیاری است که می‌تواند برای محاسبه میزان عدم قطعیت در مجموعه داده مورداستفاده قرار گیرد. همان مجموعه داده‌های ما است که برای آن میزان آنتروپی را محاسبه می‌کنیم، مجموعه کلاس‌ها در و نسبت تعداد عناصر در کلاس به تعداد عناصر در مجموعه است. در الگوریتم C4.5، میزان آنتروپی برای هر ویژگی ای که باقیمانده باشد محاسبه می‌شود. در هر تکرار الگوریتم، ویژگی با کمترین میزان آنتروپی برای تقسیم مجموعه داده مورد استفاده قرار می‌گیرد. هرچه میزان آنتروپی در یک گره بیشتر باشد، انتظار اطلاعات کمتری در مورد طبقه‌بندی داده‌ها در این مرحله از درخت وجود دارد و درنتیجه پتانسیل بیشتری برای بهبود طبقه‌بندی در این گره وجود دارد. بهره اطلاعات معیاری برای اندازه‌گیری تفاوت میزان آنتروپی قبل و بعد از تقسیم مجموعه باتوجه به ویژگی است. به بیان دیگر، تقسیم مجموعه با استفاده از ویژگی تا چه میزان عدم قطعیت در مجموعه را کاهش می‌دهد. - میزان آنتروپی مجموعه - زیر مجموعه‌های تولیدشده به‌وسیله تقسیم مجموعه با استفاده از ویژگی به طوری که - نسبت تعداد عناصر موجود در به تعداد عناصر در مجموعه - آنتروپی زیر مجموعه در الگوریتم C4.5، برای هر ویژگی باقی مانده می‌توان بهره اطلاعات را (به جای آنتروپی اطلاعات) محاسبه کرد. | ## بخش 3: الگوریتم C4.5 | در هر تکرار، برای تقسیم مجموعه ، ویژگی با بیشترین بهره اطلاعات مورداستفاده قرار می‌گیرد. بهبودهایی نسبت به الگوریتم ID3 این الگوریتم قابلیت تقسیم‌بندی به واسطه هر نوع صفتی (پیوسته و گسسته) را دارد. توانایی تقسیم‌بندی داده‌ها با مقادیر صفت از دست رفته را نیز دارد که به جای آنها؟ می‌گذارد، مقادیر صفت از دست رفته در محاسبات مربوط به آنتروپی یا بهره اطلاعات استفاده نمی‌شوند. درختان تصمیم‌گیری‌کوچکتر - C5.0 نتایجی مشابه با C4.5 با درختان تصمیم‌گیری بسیار کوچک‌تر دریافت می‌کند. پشتیبانی برای تقویت - تقویت، درختان را بهبود می‌بخشد و به آنها دقت بیشتری می‌دهد. وزن‌دهی - C5.0 به شما امکان می‌دهد موارد مختلف و انواع طبقه‌بندی اشتباه را وزن کنید. منبع یک نسخه لینوکس تک رشته‌ای C5.0 تحت مجوز عمومی عمومی گنو (GPL) در دسترس است. | ## جمع‌بندی | پیاده‌سازی‌ها J48 یک پیاده‌سازی متن باز جاوا از الگوریتم C4.5 در ابزار داده کاوی Weka است.