الگوریتم آی‌دی۳
در یادگیری درخت تصمیم، ID3 (Iterative Dichotomiser 3) یک الگوریتم ابداع شده توسط راس کوینلان بوده که میتواند برای تولید درخت تصمیم در یک مجموعه داده استفاده شود. ID3 شاکله اصلی الگوریتم C4.5 است و عموما در حوزه های یادگیری ماشین و پردازش زبان های طبیعی مورد استفاده قرار میگیرد.
الگوریتم ID3 با یک مجموعه اصلی مانند S شروع میشود که بعنوان گره ریشه شناخته میشود. در هر تکرار از الگوریتم، برای هر ویژگی در مجموعه S که تا آن مرحله مورد استفاده قرار نگرفته است، مقدار آنتروپی H(s) آن ویژگی یا مقدار بهره اطلاعات IG(S) آن ویژگی محاسبه میشود. سپس ویژگی ای که دارای کمترین مقدار آنتروپی (یا بیشترین بهره اطلاعات) باشد را انتخاب می کند. مجموعه formula_1 سپس توسط ویژگی انتخاب شده تقسیم یا اصطلاحا افراز شده تا زیرمجموعه هایی از داده ها را تولید کند. (به عنوان مثال، یک گره داخلی را می توان بر اساس زیر مجموعه های جمعیتی که سن آنها کمتر از 50 سال، بین 50 تا 100 و بیشتر از 100 سال است، به گره های فرزند تقسیم کرد) و الگوریتم همچنان باتوجه به ویژگی هایی که تا قبل از آن تکرار انتخاب نشده اند، به فرایند تقسیم کردن ادامه میدهد.
عملیات بازگشتی بر روی یک زیر مجموعه ممکن است در یکی از موارد زیر متوقف شود:بعد از پایان یافتن الگوریتم، درخت تصمیمی ایجاد می شود که گره های غیرپایانی (گره داخلی) آن، نشان دهنده ویژگی های انتخابی هستند که داده ها با توجه به آن ها تقسیم شده اند و گره های پایانی (گره برگ) آن شامل برچسب های کلاس مربوط به زیرمجموعه نهایی آن شاخه است. ID3 (Examples, Target_Attribute, Attributes)
الگوریتم ID3 تضمین نمی کند که جواب حاصله بهینه باشد اما می تواند به یک بهینه محلی همگرا شود. ID3 از یک استراتژِی حریصانه استفاده میکند که در هر تکرا ربهترین ویژگی محلی را برای افراز مجموعه داده مورداستفاده قرار می دهد. روند بهینه سازی الگوریتم را میتوان با استفاده از یک روش عقب‌گرد در طول جستجوی درخت تصمیم گیری بهینه و با قبول صرف زمان بیشتر، بهبود بخشید. ID3 می تواند باعث بیش برازش برروی داده های آموزشی شود. برای جلوگیری از این امر، درختان تصمیم کوچک تر باید به درختان تصمیم بزرگتر ترجیح داده شوند. این الگوریتم معمولاً درختان تصمیم کوچک تولید می کند، اما این به معنی نیست که همواره کوچکترین درخت تصمیم ممکن را تولید کند.
استفاده از ID3 در داده‌های پیوسته سخت‌تر از داده‌های عاملی است (داده‌های عاملی داده هایی هستند که دارای اعداد گسسته از مقادیر ممکن است، بنابراین نقاط انشعاب ممکن را کاهش می‌دهد). اگر مقادیر هر یک از ویژگی‌های داده شده پیوسته باشند، امکان های بیشتری برای افراز داده ها برروی آن ویژگی وجود دارد و انتخاب بهترین مقدار ممکن برای افراز میتواند زمانبر باشد.
الگوریتم ID3 برروی یک مجموعه داده مانند formula_1 استفاده میشود تا درخت تصمیمی را تولید کند که در حافظه ذخیره میشود. در طول زمان اجرای الگوریتم، این درخت تصمیم میتواند برای طبقه‌بندی داده های جدید (تست) استفاده شود. این امر با پیمایش درخت تصمیم باتوجه به ویژگی های موجود در هر نود و حرکت در طول درخت تا رسیدن به یک گره برگ قابل انجام است.
میزان آنتروپی formula_6 معیاری است که میتواند برای محاسبه میزان عدم قطعیت در مچموعه داده formula_1 مورداستفاده قرار گیرد.
که در آن،زمانی که formula_15 باشد، به این معنی است که مجموعه formula_1 کاملا طبقه بندی شده است (به این معنی که همه عناصر موجود در formula_1 مربوط به یک کلاس هستند).
در الگوریتم ID3، میزان آنتروپی برای هر ویژگی ای که باقیمانده باشد محاسبه میشود. در هر تکرار الگوریتم، ویژگی با کمترین میزان آنتروپی برای تقسیم مجموعه داده formula_1 مورداستفاده قرار میگیرد. آنتروپی در تئوری اطلاعات مقدار اطلاعاتی که در اندازه گیری متغیر تصادفی انتظار می رود را محاسبه میکند. به این ترتیب، می توان از آنتروپی برای تعیین کمیت مقداری که توزیع مقادیر کمیت در آن نامعلوم است نیز استفاده کرد. یک کمیت ثابت به این دلیل که توزیع آن کاملا مشخص است دارای میزان آنتروپی صفر است. در سمت مقابل، یک متغیر تصادفی توزیع شده یکنواخت (گسسته یا پیوسته) میزان آنتروپی را به حداکثر می رساند. بنابراین هرچه میزان آنتروپی در یک گره بیشتر باشد، انتظار اطلاعات کمتری در مورد طبقه بندی داده ها در این مرحله از درخت وجود دارد و درنتیجه پتانسیل بیشتری برای بهبود طبقه بندی در این گره وجود دارد.
ID3 یک روش اکتشافی حریصانه است که یک روش ابتدا-بهترین جستجو را برای پیدا کردن مقادیر آنتروپی بهینه محلی اجرا میکند. دقت الگوریتم را میتوان با عملیات پیش پردازش داده ها بهبود بخشید.
بهره اطلاعات formula_19 معیاری برای اندازه گیری تفاوت میزان آنتروپی قبل و بعد از تقسیم مجموعه formula_1 باتوجه به ویژگی formula_21 است. به بیان دیگر، تقسیم مجموعه formula_1 با استفاده از ویژگی formula_21 تا چه میزان عدم قطعیت در مجموعه formula_1 را کاهش میدهد.
که در آن،در الگوریتم ID3، برای هر ویژگی باقی مانده می توان بهره اطلاعات را (به جای آنتروپی) محاسبه کرد. در هر تکرار، برای تقسیم مجموعه formula_1، ویژگی با بیشترین بهره اطلاعات مورداستفاده قرار میگیرد.