LOGIN
ثبت نام یا ورود
Avatar
هنوز ثبت نام نکرده اید؟

هم اکنون عضو پلاک آبی شوید .و به اطلاعات وب سایت ما دسترسی داشته باشید

تنظیم مجدد کلمه عبور - نام کاربری را فراموش کرده ام

نام کاربری
کلمه عبور
مرا به خاطر بسپار

placabi articles

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

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

  • این مورد را ارزیابی کنید
    (7 رای‌ها)

بررسی مفاهیم دو مدل دسته بندی K نزدیک ترین همسایگی یا KNN و درخت تصمیم یا Decision Tree و پیاده سازی و مقایسه این دو مدل Classification به صورت فیلم آموزشی در پایتون

الگوریتم KNN

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

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

رابطه ریاضی فاصله اقلیدسی

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

فرمول الگوریتم دسته بندی KNN

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

k نزدیکترین همسایه در KNN

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

 

الگوریتم Decision Tree

الگوریتم درخت تصمیم یا 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

از تفاضل دو رابطه‌ی فوق مقدار 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 را به منظور دسته بندی پیاده سازی کرده و خروجی آن‌ها را با یکدیگر مقایسه کنیم:

توسعه مهارت با حل تمرین

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

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

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

<p>

دانلود دیتاست برای انجام پروژه

File name: Diabetes_Diagnosis.xls

1479 84
</p>

خواندن 749 دفعه آخرین ویرایش در جمعه, 11 اسفند 1396 09:40
علیرضا قره داغی

کارشناس صنایع شرکت پلاک آبی

 

 

عضو تیم تولید محتوای وب سایت و شبکه‌های اجتماعی شرکت پلاک آبی

دانشجوی کارشناسی مهندسی صنایع دانشگاه صنعتی شریف

 

  • هیچ نظری یافت نشد

نظر خود را اضافه کنید.

ارسال نظر به عنوان مهمان

0
نظر شما به دست مدیر خواهد رسید
 تماس با ما

شهرک غرب، بلوار فرحزادی، خیابان تربیت معلم،
انتهای خیابان گلبان،
مجتمع موج، واحد 105
کد پستی: 1998963193
تلفن: 5 - 88560784
فکس: 88560786
پست الکترونیک:
info @ p l a c a b i . com
ibig @ p l a c a b i . com

 

We use cookies to improve our website. By continuing to use this website, you are giving consent to cookies being used. More details…