نمایش مبدأ برای الگوریتم C4.5

'''C4.5''' الگوریتمی است که برای تولید [[درخت تصمیم]] در یک مجموعه داده استفاده می‌شود و توسط راس کوینلان ابداع شده‌است.<ref>Quinlan, J. R. C4.5: ''Programs for Machine Learning''. Morgan Kaufmann Publishers, 1993</ref> این الگوریتم یک افزونه از [[الگوریتم آی‌دی۳]] راس کوینلان است. درخت‌های تصمیم تولید شده توسط این الگوریتم برای طبقه‌بندی به کار گرفته می‌شوند، به همین دلیل الگوریتم C4.5 به عنوان یک [[طبقه‌بندی آماری]] شناخته می‌شود. این الگوریتم پس از اینکه در مقاله برجسته ۱۰ الگوریتم برتر داده کاوی (به [[انگلیسی]]: ''Top 10 Algorithms in Data Mining'') که توسط [[اشپرینگر ساینس+بیزینس مدیا|اشپرینگر ساینس]] در سال ۲۰۰۸ منتشر شد رتبه یک را کسب کرد، شهرت بسیار زیادی پیدا کرد.<ref>{{یادکرد وب|نشانی=http://www.cs.umd.edu/~samir/498/10Algorithms-08.pdf|عنوان=Umd.edu - Top 10 Algorithms in Data Mining}}</ref>

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

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

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

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

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

== معیارهای ID3 ==
==== {{درشت|آنتروپی}} ====
میزان [[آنتروپی اطلاعات|آنتروپی]] <math>\Eta{(S)}</math> معیاری است که می‌تواند برای محاسبه میزان عدم قطعیت در مجموعه داده <math>S</math> مورداستفاده قرار گیرد.

<math> \Eta{(S)} = \sum_{x \in X}{-p(x) \log_{2}p(x)}
 </math>
* <math>S</math> همان مجموعه داده‌های ما است که برای آن میزان آنتروپی را محاسبه می‌کنیم، <math>X</math> مجموعه کلاس‌ها در <math>S</math> و <math>p(x)</math> نسبت تعداد عناصر در کلاس <math>x</math> به تعداد عناصر در مجموعه <math>S</math> است.
* زمانی که <math>H(S) = 0</math> باشد، به این معنی است که مجموعه کاملاً طبقه‌بندی شده‌است. در الگوریتم C4.5، میزان آنتروپی برای هر ویژگی ای که باقیمانده باشد محاسبه می‌شود. در هر تکرار الگوریتم، ویژگی با کمترین میزان آنتروپی برای تقسیم مجموعه داده مورد استفاده قرار می‌گیرد. هرچه میزان آنتروپی در یک گره بیشتر باشد، انتظار اطلاعات کمتری در مورد طبقه‌بندی داده‌ها در این مرحله از درخت وجود دارد و درنتیجه پتانسیل بیشتری برای بهبود طبقه‌بندی در این گره وجود دارد.

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

<math>IG(S, A) = \Eta{(S)} - \sum_{t \in T} p(t)\Eta{(t)}
= \Eta{(S)} - \Eta{(S|A)}.</math>
* <math>\Eta(S)</math> - میزان آنتروپی مجموعه <math>S</math>
* <math>T</math> - زیر مجموعه‌های تولیدشده به‌وسیله تقسیم مجموعه <math>S</math> با استفاده از ویژگی <math>A</math> به طوری که <math>S = \bigcup_{t \in T} t</math>
* <math>p(t)</math> - نسبت تعداد عناصر موجود در <math>t</math> به تعداد عناصر در مجموعه <math>S</math>
* <math>\Eta(t)</math> - آنتروپی زیر مجموعه <math>t</math>

در الگوریتم C4.5، برای هر ویژگی باقی مانده می‌توان [[کسب اطلاعات (درخت تصمیم)|بهره اطلاعات]] را (به جای [[آنتروپی اطلاعات]]) محاسبه کرد. در هر تکرار، برای تقسیم مجموعه <math>S</math>، ویژگی با بیشترین بهره اطلاعات مورداستفاده قرار می‌گیرد.

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

== بهبود در الگوریتم C5.0/See5 ==
کوینلان در ادامه C5.0 و See5 (C5.0 برای یونیکس/لینوکس، See5 برای ویندوز) را ساخت. C5.0 تعدادی بهبود در C4.5 ارائه می‌دهد. برخی از این موارد عبارتند از:<ref>[http://www.rulequest.com/see5-comparison.html Is See5/C5.0 Better Than C4.5?]</ref><ref>M. Kuhn and K. Johnson, Applied Predictive Modeling, Springer 2013</ref>
* سرعت - C5.0 به‌طور قابل توجهی سریعتر از C4.5 است. (چند مرتبه بزرگی)
* استفاده از حافظه - C5.0 از نظر حافظه از C4.5 کارآمدتر است.
* درختان تصمیم‌گیری‌کوچکتر - C5.0 نتایجی مشابه با C4.5 با درختان تصمیم‌گیری بسیار کوچک‌تر دریافت می‌کند.
* پشتیبانی برای [[بوستینگ|تقویت]] - تقویت، درختان را بهبود می‌بخشد و به آنها دقت بیشتری می‌دهد.
* وزن‌دهی - C5.0 به شما امکان می‌دهد موارد مختلف و انواع طبقه‌بندی اشتباه را وزن کنید.
* Winnowing - یک گزینه [[Winnow (الگوریتم)|C5.0]] به‌طور خودکار ویژگی‌ها را برای حذف مواردی که ممکن است مفید نباشند، باز می‌کند.

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

== پیاده‌سازی‌ها ==
'''J48''' یک پیاده‌سازی [[متن‌باز|متن باز]] [[جاوا]] از الگوریتم C4.5 در ابزار [[داده‌کاوی|داده کاوی]] [[وکا (یادگیری ماشینی)|Weka]] است.

== جستارهای وابسته ==
* [[یادگیری ماشینی|یادگیری ماشین]]
* [[درخت تصمیم]]
* [[الگوریتم آی‌دی۳]]

== منابع ==
{{پانویس}}<!--- رده‌بندی --->
[[رده:الگوریتم‌های دسته‌بندی]]
[[رده:درخت تصمیم]]
[[رده:مقاله‌های ایجاد شده توسط ایجادگر]]