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

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

کسب اطلاعات یک متغیر تصادفی X که از مشاهده یک متغیر تصادفی A وقتیکه مقدار الگو:Tmath را می‌گیرد به صورت $$I{G}_{X,A}(X,a)=D_{\text{KL}}(P_X(x|a)\Vert P_X(x|I)),$$ تعریف می‌شود، که واگرایی کولبک-لیبلر توزیع پیشین $P_X(x|I)$ از x از توزیع پسین $P_{X|A}(x|a)$ برای x موقعی است که a داده شود.

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

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

تعریف عمومی

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

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

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

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

تعریف صوری

فرض کنید که الگو:Mvar به یک مجموعه از مثال‌های آموزشی اشاره کند، که هر کدام حالت $(\mathbf{\text{x}},y)=(x_1,x_2,x_3,...,x_k,y)$ را دارد که در آن $x_a\in \mathrm{v}\mathrm{a}\mathrm{l}\mathrm{s}(a)$ برابر مقدار ویژگی $a^{\text{th}}$ با ویژگی مثال $\mathbf{\text{x}}$ و الگو:Mvar برابر برچسب کلاس متناظر است. میزان کسب اطلاعات یک ویژگی الگو:Mvar به صورت انتروپی شانون $\mathrm{H}(-)$ به این صورت تعریف می‌شود. برای یک مقدار الگو:Mvar که ویژگی الگو:Mvar آن را گرفته است، فرض کنید که $$S_a(v)=\{\mathbf{\text{x}}\in T|x_a=v\}$$ به صورت مجموعه ورودی‌های آموزشی از الگو:Mvar که در آن ویژگی الگو:Mvar با مقدار الگو:Mvar برابر است تعریف شده باشد. آنوقت کسب اطلاعات الگو:Mvar برای ویژگی الگو:Mvar برابر تفاضل بین انتروپی شانون پیشین $\mathrm{H}(T)$ از مجموعه آزمایشی و انتروپی شرطی $\mathrm{H}(T|a)$ است.

$$\mathrm{H}(T|a)=\sum _{v\in \mathrm{v}\mathrm{a}\mathrm{l}\mathrm{s}(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)$ یک افراز از داده‌های مجموعه آموزشی الگو:Mvar به زیرمجموعه‌های متقابل انحصاری و کامل شامل‌شونده است، که یک توزیع احتمالی طبقه‌ای $P_a(v)$ را روی مقادیر $v\in vals(a)$ از ویژگی الگو:Mvar القا می‌کند. این توزیع به این صورت است:$P_a(v):=\frac{|S_a(v)|}{|T|}$. در این نمایش، کسب اطلاعات الگو:Mvar با داشتن الگو:Mvar را می‌توان به صورت تفاضل بین انتروپی شانون غیرشرطی از الگو:Mvar و انتروپی انتظاری الگو:Mvar با این شرط که الگو:Mvar با داده شدن الگو:Mvar را بتوان به صورت تفاضل بین انتروپی شانون غیرشرطی الگو:Mvar و انتروپی انتظاری الگو:Mvar مشروط بر الگو:Mvar تعریف کرد، که در آن مقدار انتظاری نسبت به توزیع القاشده روی مقادیر الگو:Mvar به دست می‌آید.$$\begin{array}{cc}IG(T,a)& =\mathrm{H}(T)-\sum _{v\in \mathrm{v}\mathrm{a}\mathrm{l}\mathrm{s}(a)}{P}_a(v)\mathrm{H}\left(S_a(v)\right)\\ & =\mathrm{H}(T)-{𝔼}_{P_a}\left[\mathrm{H}(S_a(v))\right]\\ & =\mathrm{H}(T)-\mathrm{H}(T|a).\end{array}$$

مزیت‌ها

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

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

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

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

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

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