مقایسه الگوریتم های پیش بینی K نزدیک ترین همسایگی و درخت تصمیم

الگوریتم KNN

K نزدیک ترین همسایه یا همان KNN در خانواده الگوریتم هایی قرار میگیرد که ما نیاز داریم تا داده هایی را با ویژگی های خاص که با X مشخص میکنیم و با برچسب مربوطه که با Y مشخص میکنیم، را داشته باشیم تا بتوانیم در قبال نمونه جدید که برچسب آن را نمیدانیم تصمیم گیری کنیم.

KNN Classifier یک الگوریتم یادگیری مبتنی بر نمونه و ناپارامتری است که در تنظیمات دسته بندی یا همان Classification، با توجه به مقدار مشخص شده برای K، به محاسبه فاصله نقطه ای که میخواهیم برچسب آن را مشخص کنیم با نزدیک ترین نقاط میپردازد و با توجه به تعداد رای حداکثری این نقاط همسایه، در رابطه با برچسب نقطه مورد نظر تصمیم گیری می‌کنیم. برای محاسبه این فاصله میتوان از روش های مختلفی استفاده کرد که یکی از مطرح ترین این روش ها، فاصله اقلیدسی است که از طریق رابطه زیر می‌توان آن را محاسبه کرد.

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

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

البته همانطور که در قسمت (b) شکل بالا مشهود است، بکارگیری اعداد زوج برای K مناسب به نظر نمیرسد. چون در صورتی که تعداد داده های هر کلاس با هم برابر باشند، برچسب گذاری بر روی نمونه مورد نظر سخت تر می‌شود. در برخی موارد نیز ممکن است برخی نقاط همسایه، فاصله بسیار کمتری، نسب به باقی همسایه ها داشته باشند که در این موارد نیز توصیه میشود به همسایه های نزدیک تر، وزن بیشتری دهیم تا از این طریق بتوانیم KNN را با دقت بالاتری پیاده سازی کنیم.

الگوریتم Decision Tree

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

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

یکی از کاربردهای رایج Decision tree ، دسته بندی یا همان Classification است که ابتدا به کمک داده های تمرین، به مدلسازی می‌پردازیم. در نهایت، داده های تست را به عنوان ورودی به درخت تصمیم میدهیم تا کلاس و یا برچسب هریک از سطرهای اطلاعاتی را برای ما پیشبینی کند. نحوه تقسیم شاخه های درخت تصمیم بسته به پارامتر مورد بررسی می‌تواند دو مقداره (Binary Split) و یا چند مقداره (Multi-way Split) باشد. در رابطه با مقادیر پیوسته مانند سن افراد نیز دقیقا مانند مقادیر گسسته عمل میکنیم. یعنی ابتدا این مقادیر را بازه بندی کرده و با بازه های موجود، مانند مقادیر گسسته برخورد میکنیم و به طور مثال در یک درخت تصمیم Binary Split ، افراد بزرگ تر از 37 سال را به عنوان یک شاخه و افراد کوچک تر از 37 سال را به عنوان شاخه ای دیگر در نظر میگیریم.

درخت تصمیم را میتوان علاوه بر نمایش در قالب ساختار درختی، به صورت دستورات شرطی نیز پیاده سازی کرد که در زیر، یک نمونه ساده از آن را مشاهده می‌کنید:

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

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

در رابطه زیر D دلالت بر مجموعه داده های آموزشی دارد. C نیز تعداد لیبل های کلاس‏های موجود در داده های آموزشی، P_i احتمال اینکه نمونه‏ای از داده ها متعلق به کلاس iام باشد، v تعداد اعضای دامنه صفت خاص A و D_j قسمتی از داده های اولیه که مقدار صفت آنها v_j است را نشان می‏دهد.

از تفاضل دو رابطه‌ی فوق مقدار Information Gain برای صفت A بدست می‌آید. حال با توجه به تعداد حالت های ممکن به ازای صفت انتخاب شده به عنوان ریشه، تقسیم بندی اولیه را انجام میدهیم. البته روش های دیگری چون Gini Index و Gain Ration نیز وجود دارند که به کمک آن ها می‌توانیم درخت تصمیم را شکل دهیم.

Over fitting / Under fitting

هنگام استفاده از الگوریتم درخت تصمیم به مواردی که باعث کاهش کارایی و دقت مدل میشوند، مانند Over fitting (که نتیجه حفظ کردن مدل و بکار گرفتن تمام صفات خاصه است) یا Under fitting (که نتیجه عدم استفاده از صفات با اهمیت است)، دقت کنید. نکته جالب اینجاست که به عنوان مثال در Over fitting به نظر میرسد که دقت مدل به شدت بالاست، درحالی که مدل تنها برای داده های تمرین، درست جواب می‌دهد و در قبال داده های تست، دقت خوبی ندارد. برای رفع مشکل Over fitting میتوانیم از مفاهیمی چون پیش هرس (Preprinting) یا پس هرس (Post pruning) استفاده کنیم.

حال با در نظر گرفتن موارد بالا، میتوانیم از الگوریتم های مختلفی چون ID3، C4.5، CART و یا CHAID که برای ساخت درخت تصمیم معرفی شده اند، استفاده کنیم. دقت کنید که هریک از این الگوریتم ها میتوانند از یک معیار و تکنیک خاصی استفاده کنند و ورودی های مختص به خود را بپذیرند!

در تمرین زیر می‌خواهیم دو مدل KNN و Decision tree را به منظور دسته بندی پیاده سازی کرده و خروجی آن‌ها را با یکدیگر مقایسه کنیم:

در فیلمک زیر، علیرضا قره داغی به حل تمرین بالا پرداخته است:

<p>