الگوریتم آی‌دی۳ کیست؟ توضیح بده.
در یادگیری درخت تصمیم، 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) Create a root node for the tree If all examples are positive, Return the single-node tree Root, with label = +. If all examples are negative, Return the single-node tree Root, with label = -. If number of predicting attributes is empty, then Return the single node tree Root, with label = most common value of the target attribute in the examples. Otherwise Begin A ← The Attribute that best classifies examples. Decision Tree attribute for Root = A. For each possible value, , of A, Add a new tree branch below Root, corresponding to the test A = . Let Examples() be the subset of examples that have the value for A If Examples() is empty Then below this new branch add a leaf node with label = most common target value in the examplesویژگی ها.الگوریتم ID3 تضمین نمی‌کند که جواب حاصله بهینه باشد اما می‌تواند به یک بهینه محلی همگرا شود. ID3 از یک استراتژِی حریصانه استفاده می‌کند که در هر تکرار بهترین ویژگی محلی را برای افراز مجموعه داده مورد استفاده قرار می‌دهد. روند بهینه سازی الگوریتم را می‌توان با استفاده از یک روش عقب‌گرد در طول جستجوی درخت تصمیم‌گیری بهینه و با قبول صرف زمان بیشتر، بهبود بخشید.ID3 می‌تواند باعث بیش برازش بر روی داده‌های آموزشی شود. برای جلوگیری از این امر، درختان تصمیم کوچک‌تر باید به درختان تصمیم بزرگتر ترجیح داده شوند. این الگوریتم معمولاً درختان تصمیم کوچک تولید می‌کند، اما این به معنی نیست که همواره کوچکترین درخت تصمیم ممکن را تولید کند.استفاده از ID3 در داده‌های پیوسته سخت‌تر از داده‌های عاملی است (داده‌های عاملی داده‌هایی هستند که دارای اعداد گسسته از مقادیر ممکن است، بنابراین نقاط انشعاب ممکن را کاهش می‌دهد). اگر مقادیر هر یک از ویژگی‌های داده شده پیوسته باشند، امکان‌های بیشتری برای افراز داده‌ها برروی آن ویژگی وجود دارد و انتخاب بهترین مقدار ممکن برای افراز می‌تواند زمانبر باشد.استفاده.الگوریتم ID3 برروی یک مجموعه داده مانند formula_1 استفاده می‌شود تا درخت تصمیمی را تولید کند که در حافظه ذخیره می‌شود. در طول زمان اجرای الگوریتم، این درخت تصمیم می‌تواند برای طبقه‌بندی داده‌های جدید (تست) استفاده شود. این امر با پیمایش درخت تصمیم باتوجه به ویژگی‌های موجود در هر نود و حرکت در طول درخت تا رسیدن به یک گره برگ قابل انجام است.معیارهای ID3.آنتروپی.میزان آنتروپی 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، ویژگی با بیشترین بهره اطلاعات مورداستفاده قرار می‌گیرد.