الگوریتم C4.5

C4.5 الگوریتمی است که برای تولید درخت تصمیم در یک مجموعه داده استفاده می‌شود و توسط راس کوینلان ابداع شده‌است.^[۱] این الگوریتم یک افزونه از الگوریتم آی‌دی۳ راس کوینلان است. درخت‌های تصمیم تولید شده توسط این الگوریتم برای طبقه‌بندی به کار گرفته می‌شوند، به همین دلیل الگوریتم C4.5 به عنوان یک طبقه‌بندی آماری شناخته می‌شود. این الگوریتم پس از اینکه در مقاله برجسته ۱۰ الگوریتم برتر داده کاوی (به انگلیسی: Top 10 Algorithms in Data Mining) که توسط اشپرینگر ساینس در سال ۲۰۰۸ منتشر شد رتبه یک را کسب کرد، شهرت بسیار زیادی پیدا کرد.^[۲]

الگوریتم[ویرایش]

C4.5 درخت تصمیم را با روشی مانند الگوریتم آی‌دی۳ و با استفاده از مفهوم آنتروپی بر روی داده‌های آموزش می‌سازد.

الگوریتم C4.5 با یک مجموعه اصلی مانند S شروع می‌شود که به‌عنوان گره ریشه شناخته می‌شود. در هر تکرار از الگوریتم، برای هر ویژگی در مجموعه S که تا آن مرحله مورد استفاده قرار نگرفته‌است، مقدار آنتروپی H(s) آن ویژگی یا مقدار بهره اطلاعات IG(S) آن محاسبه می‌شود و ویژگی‌ای که دارای کمترین مقدار آنتروپی (یا بیشترین کسب اطلاعات (درخت تصمیم) باشد را انتخاب می‌کند.

سپس به وسیلهٔ ویژگی انتخاب شده تقسیم می‌شود تا زیرمجموعه‌هایی از داده‌ها را تولید کند و الگوریتم همچنان باتوجه به ویژگی‌هایی که تا قبل از آن تکرار انتخاب نشده‌اند یه صورت بازگشتی بر روی مجموعه داده‌های تولیده شده به فرایند تقسیم کردن ادامه می‌دهد.

این الگوریتم بازگشتی چند حالت پایه دارد:

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

بنابراین خلاصه این الگوریتم به شرح زیر است:

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

معیارهای ID3[ویرایش]

آنتروپی[ویرایش]

میزان آنتروپی $\mathrm {H} {(S)}$ معیاری است که می‌تواند برای محاسبه میزان عدم قطعیت در مجموعه داده $S$ مورداستفاده قرار گیرد.

$\mathrm {H} {(S)}=\sum _{x\in X}{-p(x)\log _{2}p(x)}$

$S$ همان مجموعه داده‌های ما است که برای آن میزان آنتروپی را محاسبه می‌کنیم، $X$ مجموعه کلاس‌ها در $S$ و $p(x)$ نسبت تعداد عناصر در کلاس $x$ به تعداد عناصر در مجموعه $S$ است.
زمانی که $H(S)=0$ باشد، به این معنی است که مجموعه کاملاً طبقه‌بندی شده‌است. در الگوریتم C4.5، میزان آنتروپی برای هر ویژگی ای که باقیمانده باشد محاسبه می‌شود. در هر تکرار الگوریتم، ویژگی با کمترین میزان آنتروپی برای تقسیم مجموعه داده مورد استفاده قرار می‌گیرد. هرچه میزان آنتروپی در یک گره بیشتر باشد، انتظار اطلاعات کمتری در مورد طبقه‌بندی داده‌ها در این مرحله از درخت وجود دارد و درنتیجه پتانسیل بیشتری برای بهبود طبقه‌بندی در این گره وجود دارد.

بهره اطلاعات[ویرایش]

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

$IG(S,A)=\mathrm {H} {(S)}-\sum _{t\in T}p(t)\mathrm {H} {(t)}=\mathrm {H} {(S)}-\mathrm {H} {(S|A)}.$

$\mathrm {H} (S)$ - میزان آنتروپی مجموعه $S$
$T$ - زیر مجموعه‌های تولیدشده به‌وسیله تقسیم مجموعه $S$ با استفاده از ویژگی $A$ به طوری که $S=\bigcup _{t\in T}t$
$p(t)$ - نسبت تعداد عناصر موجود در $t$ به تعداد عناصر در مجموعه $S$
$\mathrm {H} (t)$ - آنتروپی زیر مجموعه $t$

در الگوریتم C4.5، برای هر ویژگی باقی مانده می‌توان بهره اطلاعات را (به جای آنتروپی اطلاعات) محاسبه کرد. در هر تکرار، برای تقسیم مجموعه $S$ ، ویژگی با بیشترین بهره اطلاعات مورداستفاده قرار می‌گیرد.

بهبودهایی نسبت به الگوریتم ID3[ویرایش]

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

بهبود در الگوریتم C5.0/See5[ویرایش]

کوینلان در ادامه C5.0 و See5 (C5.0 برای یونیکس/لینوکس، See5 برای ویندوز) را ساخت. C5.0 تعدادی بهبود در C4.5 ارائه می‌دهد. برخی از این موارد عبارتند از:^[۳]^[۴]

سرعت - C5.0 به‌طور قابل توجهی سریعتر از C4.5 است. (چند مرتبه بزرگی)
استفاده از حافظه - C5.0 از نظر حافظه از C4.5 کارآمدتر است.
درختان تصمیم‌گیری‌کوچکتر - C5.0 نتایجی مشابه با C4.5 با درختان تصمیم‌گیری بسیار کوچک‌تر دریافت می‌کند.
پشتیبانی برای تقویت - تقویت، درختان را بهبود می‌بخشد و به آنها دقت بیشتری می‌دهد.
وزن‌دهی - C5.0 به شما امکان می‌دهد موارد مختلف و انواع طبقه‌بندی اشتباه را وزن کنید.
Winnowing - یک گزینه C5.0 به‌طور خودکار ویژگی‌ها را برای حذف مواردی که ممکن است مفید نباشند، باز می‌کند.

منبع یک نسخه لینوکس تک رشته‌ای C5.0 تحت مجوز عمومی عمومی گنو (GPL) در دسترس است.

پیاده‌سازی‌ها[ویرایش]

J48 یک پیاده‌سازی متن باز جاوا از الگوریتم C4.5 در ابزار داده کاوی Weka است.

جستارهای وابسته[ویرایش]

منابع[ویرایش]

↑ Quinlan, J. R. C4.5: Programs for Machine Learning. Morgan Kaufmann Publishers, 1993
↑ «Umd.edu - Top 10 Algorithms in Data Mining» (PDF).
↑ Is See5/C5.0 Better Than C4.5?
↑ M. Kuhn and K. Johnson, Applied Predictive Modeling, Springer 2013

[1] Quinlan, J. R. C4.5: Programs for Machine Learning. Morgan Kaufmann Publishers, 1993

[2] «Umd.edu - Top 10 Algorithms in Data Mining» (PDF).

[3] Is See5/C5.0 Better Than C4.5?

[4] M. Kuhn and K. Johnson, Applied Predictive Modeling, Springer 2013

[۱]

[۲]

[۳]

[۴]