الگوریتم آی‌دی۳

در یادگیری درخت تصمیم، ID3 (Iterative Dichotomiser 3) یک الگوریتم ابداع شده توسط راس کوینلان  بوده که میتواند برای تولید درخت تصمیم در یک مجموعه داده استفاده شود. ID3 شاکله اصلی الگوریتم C4.5 است و عموما در حوزه های یادگیری ماشین و پردازش زبان های طبیعی مورد استفاده قرار میگیرد.

الگوریتم 
الگوریتم ID3 با یک مجموعه اصلی مانند S شروع میشود که بعنوان گره ریشه شناخته میشود. در هر تکرار از الگوریتم، برای هر ویژگی در مجموعه S که تا آن مرحله مورد استفاده قرار نگرفته است، مقدار آنتروپی H(s) آن ویژگی یا مقدار بهره اطلاعات IG(S) آن ویژگی محاسبه میشود. سپس ویژگی ای که دارای کمترین مقدار آنتروپی (یا بیشترین بهره اطلاعات) باشد را انتخاب می کند. مجموعه  سپس توسط ویژگی انتخاب شده تقسیم  یا اصطلاحا افراز شده تا زیرمجموعه هایی از داده ها را تولید کند. (به عنوان مثال، یک گره داخلی را می توان بر اساس زیر مجموعه های جمعیتی که سن آنها کمتر از 50 سال، بین 50 تا 100 و بیشتر از 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 برروی یک مجموعه داده مانند  استفاده میشود تا درخت تصمیمی را تولید کند که در حافظه ذخیره میشود. در طول زمان اجرای الگوریتم، این درخت تصمیم میتواند برای طبقه‌بندی داده های جدید (تست) استفاده شود. این امر با پیمایش درخت تصمیم باتوجه به ویژگی های موجود در هر نود و حرکت در طول درخت تا رسیدن به یک گره برگ قابل انجام است.

معیارهای ID3

آنتروپی 
میزان آنتروپی  معیاری است که میتواند برای محاسبه میزان عدم قطعیت در مچموعه داده  مورداستفاده قرار گیرد.

 

که در آن،

  - مجموعه داده فعلی است که میزان آنتروپی برای آن محاسبه میشود.
 این میزان در هر تکرار از الگوریتم ID3، تغییر می کند. درصورت تقسیم باتوجه به یک ویژگی به زیرمجموعه ای از مجموعه قبلی تقسیم میشود و در صورتی که عملیات بازگشتی قبلا خاتمه یافته باشد، به نودهای «خواهر و برادر» تقسیم میشود. 
  – مجموعه کلاس ها در 
  - نسبت تعداد عناصر در کلاس  به تعداد عناصر در مجموعه 

زمانی که   باشد، به این معنی است که مجموعه  کاملا طبقه بندی شده است (به این معنی که همه عناصر موجود در  مربوط به یک کلاس هستند).

در الگوریتم ID3، میزان آنتروپی برای هر ویژگی ای که باقیمانده باشد محاسبه میشود. در هر تکرار الگوریتم، ویژگی با کمترین میزان آنتروپی برای تقسیم مجموعه داده  مورداستفاده قرار میگیرد. آنتروپی در تئوری اطلاعات مقدار اطلاعاتی که در اندازه گیری متغیر تصادفی انتظار می رود را محاسبه میکند. به این ترتیب، می توان از آنتروپی برای تعیین کمیت مقداری که توزیع مقادیر کمیت در آن نامعلوم است نیز استفاده کرد. یک کمیت ثابت به این دلیل که توزیع آن کاملا مشخص است دارای میزان آنتروپی صفر است. در سمت مقابل، یک متغیر تصادفی توزیع شده یکنواخت (گسسته یا پیوسته) میزان آنتروپی را به حداکثر می رساند. بنابراین هرچه میزان آنتروپی در یک گره بیشتر باشد، انتظار اطلاعات کمتری در مورد طبقه بندی داده ها در این مرحله از درخت وجود دارد و درنتیجه پتانسیل بیشتری برای بهبود طبقه بندی در این گره وجود دارد.

ID3 یک روش اکتشافی حریصانه است که یک روش ابتدا-بهترین جستجو را برای پیدا کردن مقادیر آنتروپی بهینه محلی اجرا میکند. دقت الگوریتم را میتوان با عملیات پیش پردازش داده ها بهبود بخشید.

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

 

که در آن،

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

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

همچنین ببینید 

 درخت طبقه بندی و رگرسیون (CART)
 الگوریتم C4.5
 یادگیری درخت تصمیم
 مدل درخت تصمیم

منابع

خواندن بیشتر

لینک های خارجی 

 سمینارها – http://www2.cs.uregina.ca/
 توضیحات و نمونه - http://www.cise.ufl.edu/
 توضیحات و نمونه - http://www.cis.temple.edu/
 درختان تصمیم و طبقه بندی احزاب سیاسی
الگوریتم‌های دسته‌بندی
درخت تصمیم