کسب اطلاعات (درخت تصمیم)

در نظریه اطلاعات و یادگیری ماشین، کسب اطلاعات (به انگلیسی: information gain) مترادف واگرایی کولبک-لیبلر است؛ یعنی میزان اطلاعات کسب‌شده درباره یک متغیر تصادفی یا سیگنال از مشاهده متغیر تصادفی دیگر. با این حال، در زمینه درخت‌های تصمیم‌گیری، این اصطلاح مترادف با اطلاعات متقابل است، که مقدار انتظاری شرطی واگرایی کولبک-لیبلر از توزیع احتمال تک‌متغیره از یک متغیر از توزیع شرطی این متغیر با شرط اینکه دیگری داده شود.

کسب اطلاعات یک متغیر تصادفی X که از مشاهده یک متغیر تصادفی A وقتیکه مقدار $A=a$ را می‌گیرد به صورت

$$IG_{X,A}{(X,a)}=D_{\text{KL}}{\left(P_{X}{(x|a)}\|P_{X}{(x|I)}\right)},$$

تعریف می‌شود، که واگرایی کولبک-لیبلر توزیع پیشین $P_{X}{(x|I)}$ از x از توزیع پسین $P_{X|A}{(x|a)}$ برای x موقعی است که a داده شود.

مقدار انتظاری کسب اطلاعات برابر اطلاعات متقابل $I(X;A)$ از X و A است، یعنی کاهش انتروپی X که توسط یادگیری حالت متغیر تصادفی A به دست می‌آید.

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

تعریف عمومی

به صورت عام، کسب اطلاعات انتظاری برابر کاهش انتروپی اطلاعات Η از یک حالت پیشین به یک حالت است که اطلاعاتی گرفته است، به این صورت:

$IG(T,a)=\mathrm {H} {(T)}-\mathrm {H} {(T|a)},$

که در آن $\mathrm {H} {(T|a)}$ برابر انتروپی شرطی $T$ موقعی است که مقدار ویژگی $a$ را داشته باشیم.

این موضوع به صورت بدیهی موقعی قابل قبول است که انتروپی Η به صورت مقدار عدم‌قطعیت یک متغیر تصادفی $T$ تفسیر شود: با یادگیری (یا فرض) $a$ درباره $T$، عدم‌قطعیت ما درباره $T$ کاهش می‌یابد (یعنی $IG(T,a)$ مثبت است)، مگر آنکه $T$ مستقل از $a$ باشد که در این حالت، $\mathrm {H} (T,a)=\mathrm {H} (T)$ است، یعنی $IG(T,a)=0$ است.

تعریف صوری

فرض کنید که T به یک مجموعه از مثال‌های آموزشی اشاره کند، که هر کدام حالت $({\textbf {x}},y)=(x_{1},x_{2},x_{3},...,x_{k},y)$ را دارد که در آن $x_{a}\in \mathrm {vals} (a)$ برابر مقدار ویژگی $a^{\text{th}}$ با ویژگی مثال ${\textbf {x}}$ و y برابر برچسب کلاس متناظر است. میزان کسب اطلاعات یک ویژگی a به صورت انتروپی شانون $\mathrm {H} (-)$ به این صورت تعریف می‌شود. برای یک مقدار v که ویژگی a آن را گرفته است، فرض کنید که

$$S_{a}{(v)}=\{{\textbf {x}}\in T|x_{a}=v\}$$

به صورت مجموعه ورودی‌های آموزشی از T که در آن ویژگی a با مقدار v برابر است تعریف شده باشد. آنوقت کسب اطلاعات T برای ویژگی a برابر تفاضل بین انتروپی شانون پیشین $\mathrm {H} (T)$ از مجموعه آزمایشی و انتروپی شرطی $\mathrm {H} {(T|a)}$ است.

$$\mathrm {H} (T|a)=\sum _{v\in \mathrm {vals} (a)}{{\frac {|S_{a}{(v)}|}{|T|}}\cdot \mathrm {H} \left(S_{a}{\left(v\right)}\right)}.$$

$IG(T,a)=\mathrm {H} (T)-\mathrm {H} (T|a)$

اطلاعات متقابل برابر انتروپی کلی برای یک ویژگی است اگر برای هرکدام از مقادیر ویژگی یک طبقه‌بندی یکتا برای ویژگی نتیجه شده قابل ساخت باشد. در این حالت، انتروپی‌های نسبی که از انتروپی کلی کم می‌شود برابر 0 است. بخصوص، مقادیر $v\in vals(a)$ یک افراز از داده‌های مجموعه آموزشی T به زیرمجموعه‌های متقابل انحصاری و کامل شامل‌شونده است، که یک توزیع احتمالی طبقه‌ای ${\textstyle P_{a}{(v)}}$ را روی مقادیر ${\textstyle v\in vals(a)}$ از ویژگی a القا می‌کند. این توزیع به این صورت است:${\textstyle P_{a}{(v)}:={\frac {|S_{a}{(v)}|}{|T|}}}$. در این نمایش، کسب اطلاعات T با داشتن a را می‌توان به صورت تفاضل بین انتروپی شانون غیرشرطی از T و انتروپی انتظاری T با این شرط که T با داده شدن a را بتوان به صورت تفاضل بین انتروپی شانون غیرشرطی T و انتروپی انتظاری T مشروط بر a تعریف کرد، که در آن مقدار انتظاری نسبت به توزیع القاشده روی مقادیر a به دست می‌آید.

$${\begin{alignedat}{2}IG(T,a)&=\mathrm {H} (T)-\sum _{v\in \mathrm {vals} (a)}{P_{a}{(v)}\mathrm {H} \left(S_{a}{(v)}\right)}\\&=\mathrm {H} (T)-\mathbb {E} _{P_{a}}{\left[\mathrm {H} {(S_{a}{(v)})}\right]}\\&=\mathrm {H} (T)-\mathrm {H} {(T|a)}.\end{alignedat}}$$

مزیت‌ها

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

مفهوم تابع کسب اطلاعات تحت الگوریتم C4.5 برای تولید درخت‌های تصمیم، و انتخاب شکست بهینه برای یک گره درخت تصمیم قرار می‌گیرد. بعضی از مزیت‌ها شامل:

• هم با متغیر پیوسته و هم گسسته می‌تواند کار کند.
• به دلیل عامل –[p ∗ log(p)] در تعریف انتروپی که در بالا آمد، گره‌های برگ که تعداد نمونه کمتری دارند دارای وزن کمتری خواهند بود، و علاقه به آن است که بقیه داده را به گروه‌های بزرگتر ولی همگن تقسیم کنیم. و بنابراین، مادامیکه به سمت عمق درخت فرو می‌رویم، مجموعه داده همگن‌تر می‌شود. این دیدگاه پایدارتر است و تاثیرگذارترین ویژگی‌ها را در گره‌ها انتخاب می‌کند.

عیوب و ‌راه‌حل‌ها

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

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

منابع

مشارکت‌کنندگان ویکی‌پدیا. «Information gain (decision tree)». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۲۳ ژوئیهٔ ۲۰۲۲.