entropy_Ai(D)= × entropy(D_j)
اگر ما قصد داریم از خصیصه A_i استفاده کنیم، D به زیر مجموعه های D₁، D₂، …….،D_v تقسیم می شود.
Information gain از فرمول زیر محاسبه می شود]۳۶[:
(۲-۱۰)
Gain(D,A_i)= entropy(D)-entropy_Ai(D)
دو نوع شاخص دیگر که اغلب به طور گسترده برای ارزیابی اینکه یک گره باید تقسیم شود یا نه استفاده

( اینجا فقط تکه ای از متن پایان نامه درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. )

می شود، شاخص های Gini index و انحراف انتروپی است.
Gini index به صورت زیر تعریف می شود ]۳۶[:
(۲-۱۱)
Gini (T)=1-
و انحراف انتروپی به صورت زیر تعریف می شود ]۳۶[:
(۲-۱۲)
entropy(T)=-
که p_j فراوانی نسبی کلاس j در درخت T می باشد.
اگرچه درختان تصمیم از روش های یادگیری محبوب هستند اما آنها مشکل overfitting دارند، پیش بینی با کیفیت بالا روی داده های آموزشی در حالی که داده های تست دیده نشده، دارای این کیفیت نیست.
۲-۵-۳- ماشین بردار پشتیبان (SVM):
ماشین های بردار پشتیبان نوع دیگری از سیستم های یادگیری هستند که دارای ویژگی های مطلوب بسیاری است که آن را یکی از محبوبترین الگوریتم ها نموده است. این الگوریتم در داده های با ابعاد بالا کاربرد دارد. برای نمونه، محققان زیادی نشان داده اند که ماشین بردار پشتیبان شاید دقیق ترین الگوریتم برای طبقه بندی متن باشد و هم چنین در طبقه بندی وب و کاربردهای بیوانفورماتیک به طور گسترده ای استفاده می شود. به طور کلی می توان گفت که ماشین بردار پشتیبان، یک سیستم یادگیری خطی است که طبقه بندی کننده با دو کلاس می سازد.
اگر نمونه آموزشی D به صورت زیر باشد:
{(,), (,),…… (,)}
که x_i=(x_i1,x_i2,…….x_ir) یک بردار ورودی r بعدی در فضای مقادیر حقیقیR² x ; y_i برچسب کلاس و y_i={1,-1}، ۱ کلاس مثبت و ۱- کلاس منفی را نشان می دهد. هر نمونه داده یک بردار ورودی خوانده می شود و با حروف تیره بزرگ نمایش داده می شود. در زیر ما از حروف تیره بزرگ برای همه بردارها استفاده کرده ایم.
برای ساخت یک طبقه بندی کننده، ماشین بردار پشتیبان یک تابع خطی به شکل زیر پیدا می کند.
f(x)=<W.X>+b (*)
بنابراین اگر f(x)≥۰ یک بردار ورودی X_i، به کلاس مثبت اختصاص یافته است و برای کلاس منفی برعکس.
اگر ۰ ≤ <W.X_i>+b 1
y_i=
اگر ۰ ≥ <W.X_i>+b 1-
بنابراین f(x) یک تابع حقیقی است،R² R.W=(w₁,w₂,…..,w_r) R² f: x که بردار وزن خوانده می شود وR b پایه خوانده می شود.
بدون بردار معادله * به صورت زیر نوشته می شود:
f(x₁,x₂,………………,x_r)=w₁x₁+w₂x₂+…………….+w_rx_r+b
که x_i متغیر بیان کننده i امین مختصات بردار x می باشد. ماشین بردار پشتیبان یک ابر صفحه پیدا می کند(<w.x>+b=0) که نمونه های مثبت و منفی را جدا می کند. این ابر صفحه، مرز تصمیم گیری یا صفحه تصمیم گیری نامیده می شود ]۳۷[.
ابر صفحه در فضای دوبعدی معمولاً خط و در فضای سه بعدی معمولاً صفحه است.طرح زیر یک فضای دو بعدی را نشان می دهد.

الف
ب
شکل۲-۵: الف: یک مجموعه تفکیک شده خطی شکل ب: مرزهای تصمیم گیری ممکن ]۳۷[
در این طرح خطوط ضخیم در میانه، مرز تصمیم می باشند(در اینجا یک خط)، که نقاط مثبت و منفی را از هم جدا می کند. تعداد زیادی خط وجود دارد که نقاط مثبت و منفی را جدا می کند، ماشین بردار پشتیبان ابرصفحه ای را انتخاب می کند که حاشیه ها میان نقاط مثبت و منفی را بیشینه می کند. ماشین بردار پشتیبان در مورد داده های غیرخطی از توابع کرنل استفاده می کند.
برای پیدا کردن ابر صفحه بهینه نقاط (x⁺,1) و (x^–, -1) را در نظر می گیریم و در ابر صفحه H⁺ وH^– را تعریف می کنیم که از این دو نقطه بگذرند و موازی با صفحه <w.x>+b=0 باشند و سپس حاشیه بین این دو ابر صفحه موازی را محاسبه می کنیم. با توجه به جبر خطی داریم ]۲۴[:
که ||W|| برابر است با :
||W||==
حال فاصله ی نقطه ی x_s روی <w.x>+b=0 از صفحه <w.x⁺>+b=1 محاسبه می کنیم. در نتیجه حاشیه برابر است با:
=
و به همین ترتیب حاشیه برای نقاط منفی محاسبه می شود ، بنابراین حاشیه برابر خواهد بود. بیشینه سازی حاشیه یک مسئله بهینه سازی است و بیشینه کردن حاشیه همان کمینه کردن است ]۲۴[.
۲-۶- ترکیب طبقه بندی کننده ها:
در خیلی از موارد، می توان طبقه بندی کننده ها را با هم ترکیب کنیم. دو تکنیک خوب و شناخته شده در این زمینه وجود دارد، bagging و boosting.
در هر دوی این روش ها، تعدادی طبقه بندی کننده ساخته می شود و طبقه بندی کننده تصمیم گیر نهایی برای هر نمونه تست، مبتنی بر انواع رای گیری می باشد.
۲-۶-۱- Bagging:
یک مجموعه آموزشی D با n نمونه داده شده و یک الگوریتم یادگیری پایه، bagging مطابق با آنچه در زیر آمده کار می کند:
یادگیری:
۱-k نمونه bootstrap، s₁، s₂ و s_k را خلق می کند. هر نمونه به صورت تصادفی از D با جایگزینی تولید می شود. هر نمونه s_i، ۲/۶۳% نمونه های اصلی درD به همراه تعدادی نمونه ها که چندین بار آشکار می شوند را شامل می شود.