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

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

الگوریتم

الگوریتم ID3 با یک مجموعه اصلی مانند S شروع می‌شود که بعنوان گره ریشه شناخته می‌شود. در هر تکرار از الگوریتم، برای هر ویژگی در مجموعه S که تا آن مرحله مورد استفاده قرار نگرفته است، مقدار آنتروپی H(s) آن ویژگی یا مقدار بهره اطلاعات IG(S) آن ویژگی محاسبه می‌شود. سپس ویژگی‌ای که دارای کمترین مقدار آنتروپی (یا بیشترین بهره اطلاعات) باشد را انتخاب می‌کند. مجموعه $S$ سپس توسط ویژگی انتخاب شده تقسیم یا اصطلاحا افراز شده تا زیرمجموعه‌هایی از داده‌ها را تولید کند. (به عنوان مثال، یک گره داخلی را می‌توان بر اساس زیر مجموعه‌های جمعیتی که سن آنها کمتر از 50 سال، بین 50 تا 100 و بیشتر از 100 سال است، به گره‌های فرزند تقسیم کرد) و الگوریتم همچنان باتوجه به ویژگی‌هایی که تا قبل از آن تکرار انتخاب نشده‌اند، به فرایند تقسیم کردن ادامه میدهد.

عملیات بازگشتی بر روی یک زیر مجموعه ممکن است در یکی از موارد زیر متوقف شود:

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

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

خلاصه

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

شبه کد

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,  $v i$ , of A,
            Add a new tree branch below Root, corresponding to the test A =  $v i$ .
            Let Examples( $v i$ ) be the subset of examples that have the value  $v i$  for A
            If Examples( $v i$ ) 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 برروی یک مجموعه داده مانند $S$ استفاده می‌شود تا درخت تصمیمی را تولید کند که در حافظه ذخیره می‌شود. در طول زمان اجرای الگوریتم، این درخت تصمیم می‌تواند برای طبقه‌بندی داده‌های جدید (تست) استفاده شود. این امر با پیمایش درخت تصمیم باتوجه به ویژگی‌های موجود در هر نود و حرکت در طول درخت تا رسیدن به یک گره برگ قابل انجام است.

معیارهای ID3

آنتروپی

میزان آنتروپی $\mathrm {H} {(S)}$ معیاری است که می‌تواند برای محاسبه میزان عدم قطعیت در مچموعه داده $S$ مورداستفاده قرار گیرد.

\mathrm {H} {(S)}=\sum _{x\in X}{-p(x)\log _{2}p(x)}

که در آن،

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

زمانی که $\mathrm {H} {(S)}=0$ باشد، به این معنی است که مجموعه $S$ کاملا طبقه‌بندی شده است (به این معنی که همه عناصر موجود در $S$ مربوط به یک کلاس هستند).

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

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

بهره اطلاعات

بهره اطلاعات $IG(A)$ معیاری برای اندازه‌گیری تفاوت میزان آنتروپی قبل و بعد از تقسیم مجموعه $S$ باتوجه به ویژگی $A$ است. به بیان دیگر، تقسیم مجموعه $S$ با استفاده از ویژگی $A$ تا چه میزان عدم قطعیت در مجموعه $S$ را کاهش میدهد.

IG(S,A)=\mathrm {H} {(S)}-\sum _{t\in T}p(t)\mathrm {H} {(t)}=\mathrm {H} {(S)}-\mathrm {H} {(S|A)}.

که در آن،

$\mathrm {H} (S)$ - میزان آنتروپی مجموعه $S$
$T$ - زیر مجموعه‌های تولید شده بوسیله تقسیم مجموعه $S$ با استفاده از ویژگی $A$ به‌طوری که $S=\bigcup _{t\in T}t$
$p(t)$ - نسبت تعداد عناصر موجود در $t$ به تعداد عناصر در مجموعه $S$
$\mathrm {H} (t)$ - آنتروپی زیر مجموعه $t$

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

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

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

منابع

↑ Quinlan, J. R. 1986. Induction of Decision Trees. Mach. Learn. 1, 1 (Mar. 1986), 81–106
↑ Taggart, Allison J; DeSimone, Alec M; Shih, Janice S; Filloux, Madeleine E; Fairbrother, William G (2012-06-17). "Large-scale mapping of branchpoints in human pre-mRNA transcripts in vivo". Nature Structural & Molecular Biology. 19 (7): 719–721. doi:10.1038/nsmb.2327. ISSN 1545-9993. PMC 3465671. PMID 22705790.

خواندن بیشتر

Grzymala-Busse, Jerzy W. (February 1993). "Selected Algorithms of Machine Learning from Examples" (PDF). Fundamenta Informaticae. 18 (2): 193–207 – via ResearchGate.

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

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

[1] Quinlan, J. R. 1986. Induction of Decision Trees. Mach. Learn. 1, 1 (Mar. 1986), 81–106

[2] Taggart, Allison J; DeSimone, Alec M; Shih, Janice S; Filloux, Madeleine E; Fairbrother, William G (2012-06-17). "Large-scale mapping of branchpoints in human pre-mRNA transcripts in vivo". Nature Structural & Molecular Biology. 19 (7): 719–721. doi:10.1038/nsmb.2327. ISSN 1545-9993. PMC 3465671. PMID 22705790.

[۱]

[۲]