موضوع مقاله: الگوریتم آی‌دی۳ | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # الگوریتم آی‌دی۳ | مقدمه: 1986), 81–106 بوده که می‌تواند برای تولید درخت تصمیم در یک مجموعه داده استفاده شود. | ## بخش 1: الگوریتم آی‌دی۳ | ID3 شاکله اصلی الگوریتم C4.5 است و عموما در حوزه‌های یادگیری ماشین و پردازش زبان‌های طبیعی مورد استفاده قرار میگیرد. الگوریتم الگوریتم ID3 با یک مجموعه اصلی مانند S شروع می‌شود که بعنوان گره ریشه شناخته می‌شود. در هر تکرار از الگوریتم، برای هر ویژگی در مجموعه S که تا آن مرحله مورد استفاده قرار نگرفته است، مقدار آنتروپی H(s) آن ویژگی یا مقدار بهره اطلاعات IG(S) آن ویژگی محاسبه می‌شود. سپس ویژگی‌ای که دارای کمترین مقدار آنتروپی (یا بیشترین بهره اطلاعات) باشد را انتخاب می‌کند. مجموعه سپس توسط ویژگی انتخاب شده تقسیم یا اصطلاحا افراز شده تا زیرمجموعه‌هایی از داده‌ها را تولید کند. (به عنوان مثال، یک گره داخلی را می‌توان بر اساس زیر مجموعه‌های جمعیتی که سن آنها کمتر از 50 سال، بین 50 تا 100 و بیشتر از 100 سال است، به گره‌های فرزند تقسیم کرد) و الگوریتم همچنان باتوجه به ویژگی‌هایی که تا قبل از آن تکرار انتخاب نشده‌اند، به فرایند تقسیم کردن ادامه میدهد. عملیات بازگشتی بر روی یک زیر مجموعه ممکن است در یکی از موارد زیر متوقف شود: هر نمونه در یک زیرمجموعه فقط متعلق به یک کلاس باشد. در این حالت نود حاصل یک نود برگ بوده و برچسب آن، کلاس نمونه (یا نمونه‌هایی) است که در خود دارد. تمام ویژگی ها انتخاب شده باشند و دیگر ویژگی‌ای برای انتخاب شدن و تقسیم وجود نداشته باشد، اما هنوز برخی نمونه ها وجود داشته باشند که به یک کلاس تنها تعلق نداشته باشند. در این حالت، یک گره به عنوان گره برگ ایجاد شده و برچسب آن کلاسی انتخاب می‌شود که بیشترین فراوانی را در نمونه‌های موجود در آن نود داشته باشد. این مورد زمانی اتفاق می‌افتد که هیچ نمونه‌ای در مجموعه والد پیدا نشود که با مقدار خاصی از ویژگی انتخاب شده مطابقت داشته باشد. به عنوان مثال می‌توان عدم حضور نمونه‌ای در جمعیت با سن بالای 100 سال را نام برد. سپس یک گره برگ ایجاد می‌شود و با رایج ترین کلاس از نمونه‌های مجموعه گره والد برچسب گذاری می‌شود. بعد از پایان یافتن الگوریتم، درخت تصمیمی ایجاد می‌شود که گره‌های غیرپایانی (گره داخلی) آن، نشان دهنده ویژگی‌های انتخابی هستند که داده‌ها با توجه به آن ها تقسیم شده‌اند و گره‌های پایانی (گره برگ) آن شامل برچسب‌های کلاس مربوط به زیرمجموعه نهایی آن شاخه است. | ## بخش 2: الگوریتم آی‌دی۳ | مجوعه را با استفاده از ویژگی‌ای باعث مینیمم شدن میزان آنتروپی می‌شود به زیرمجموعه‌هایی افراز (تقسیم) کنید. باتوجه به ویژگی‌های باقیمانده، این عمل را به‌صورت بازگشتی برروی زیرمجموعه‌ها تکرار کنید. الگوریتم ID3 تضمین نمی‌کند که جواب حاصله بهینه باشد اما می‌تواند به یک بهینه محلی همگرا شود. ID3 از یک استراتژِی حریصانه استفاده می‌کند که در هر تکرار بهترین ویژگی محلی را برای افراز مجموعه داده مورد استفاده قرار می‌دهد. روند بهینه سازی الگوریتم را می‌توان با استفاده از یک روش عقب‌گرد در طول جستجوی درخت تصمیم‌گیری بهینه و با قبول صرف زمان بیشتر، بهبود بخشید. برای جلوگیری از این امر، درختان تصمیم کوچک‌تر باید به درختان تصمیم بزرگتر ترجیح داده شوند. این الگوریتم معمولاً درختان تصمیم کوچک تولید می‌کند، اما این به معنی نیست که همواره کوچکترین درخت تصمیم ممکن را تولید کند. استفاده از ID3 در داده‌های پیوسته سخت‌تر از داده‌های عاملی است (داده‌های عاملی داده‌هایی هستند که دارای اعداد گسسته از مقادیر ممکن است، بنابراین نقاط انشعاب ممکن را کاهش می‌دهد). اگر مقادیر هر یک از ویژگی‌های داده شده پیوسته باشند، امکان‌های بیشتری برای افراز داده‌ها برروی آن ویژگی وجود دارد و انتخاب بهترین مقدار ممکن برای افراز می‌تواند زمانبر باشد. استفاده الگوریتم ID3 برروی یک مجموعه داده مانند استفاده می‌شود تا درخت تصمیمی را تولید کند که در حافظه ذخیره می‌شود. در طول زمان اجرای الگوریتم، این درخت تصمیم می‌تواند برای طبقه‌بندی داده‌های جدید (تست) استفاده شود. این امر با پیمایش درخت تصمیم باتوجه به ویژگی‌های موجود در هر نود و حرکت در طول درخت تا رسیدن به یک گره برگ قابل انجام است. معیارهای ID3 آنتروپی میزان آنتروپی معیاری است که می‌تواند برای محاسبه میزان عدم قطعیت در مچموعه داده مورداستفاده قرار گیرد. درصورت تقسیم باتوجه به یک ویژگی به زیرمجموعه‌ای از مجموعه قبلی تقسیم می‌شود و در صورتی که عملیات بازگشتی قبلا خاتمه یافته باشد، به نودهای «خواهر و برادر» تقسیم می‌شود. | ## بخش 3: الگوریتم آی‌دی۳ | – مجموعه کلاس ها در - نسبت تعداد عناصر در کلاس به تعداد عناصر در مجموعه زمانی که باشد، به این معنی است که مجموعه کاملا طبقه‌بندی شده است (به این معنی که همه عناصر موجود در مربوط به یک کلاس هستند). در الگوریتم ID3، میزان آنتروپی برای هر ویژگی‌ای که باقیمانده باشد محاسبه می‌شود. در هر تکرار الگوریتم، ویژگی با کمترین میزان آنتروپی برای تقسیم مجموعه داده مورداستفاده قرار می‌گیرد. آنتروپی در تئوری اطلاعات مقدار اطلاعاتی که در اندازه‌گیری متغیر تصادفی انتظار می‌رود را محاسبه می‌کند. به این ترتیب، می‌توان از آنتروپی برای تعیین کمیت مقداری که توزیع مقادیر کمیت در آن نامعلوم است نیز استفاده کرد. یک کمیت ثابت به این دلیل که توزیع آن کاملا مشخص است دارای میزان آنتروپی صفر است. در سمت مقابل، یک متغیر تصادفی توزیع شده یکنواخت (گسسته یا پیوسته) میزان آنتروپی را به حداکثر می‌رساند. بنابراین هرچه میزان آنتروپی در یک گره بیشتر باشد، انتظار اطلاعات کمتری در مورد طبقه‌بندی داده‌ها در این مرحله از درخت وجود دارد و درنتیجه پتانسیل بیشتری برای بهبود طبقه‌بندی در این گره وجود دارد. ID3 یک روش اکتشافی حریصانه است که یک روش ابتدا-بهترین جستجو را برای پیدا کردن مقادیر آنتروپی بهینه محلی اجرا می‌کند. بهره اطلاعات بهره اطلاعات معیاری برای اندازه‌گیری تفاوت میزان آنتروپی قبل و بعد از تقسیم مجموعه باتوجه به ویژگی است. به بیان دیگر، تقسیم مجموعه با استفاده از ویژگی تا چه میزان عدم قطعیت در مجموعه را کاهش میدهد. که در آن، - میزان آنتروپی مجموعه - زیر مجموعه‌های تولید شده بوسیله تقسیم مجموعه با استفاده از ویژگی به‌طوری که - نسبت تعداد عناصر موجود در به تعداد عناصر در مجموعه - آنتروپی زیر مجموعه در الگوریتم ID3، برای هر ویژگی باقی‌مانده می‌توان بهره اطلاعات را (به جای آنتروپی) محاسبه کرد. | ## جمع‌بندی | در هر تکرار، برای تقسیم مجموعه ، ویژگی با بیشترین بهره اطلاعات مورداستفاده قرار می‌گیرد.