پیاده سازی الگوریتم KNN در پایتون — آموزش کامل با Scikit-Learn

تئوری الگوریتم KNN

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

حال فرض کنید می خواهیم یک نقطه داده جدید با نام ‘X’ را به کلاس “آبی” یا کلاس “قرمز” دسته بندی کنیم. مقادیر مختصات نقطه داده x=45 و y=50 است. فرض کنید مقدار K=3 باشد. الگوریتم KNN با محاسبه فاصله نقطه X از تمام نقاط شروع می شود. سپس ۳ نزدیکترین نقطه با کمترین فاصله تا نقطه X را پیدا می کند. شکل زیر سه نقطه نزدیک ‘X’ را نشان می دهد.

مرحله آخر الگوریتم KNN این است که نقطه جدیدی را به کلاسی که اکثریت سه نقطه نزدیک به آن تعلق دارد، اختصاص دهد. از شکل بالا متوجه خواهید شد که دو نقطه از سه نقطه نزدیک به کلاس “قرمز” و یکی متعلق به کلاس “آبی” است. بنابراین نقطه داده جدید ‘X’ به عنوان “قرمز” طبقه بندی یا دسته بندی می‌شود. درلینک زیر پاورپوینت الگوریتم K_means و knn با اسلاید‌های جذاب به دانشجویان و دانش آموزان کمک می‌کند تا یک ارائه بی‌نظیر داشته باشند و اطلاعات مفیدی را در این زمینه برای شما بازگو کنند.

• پاورپوینت الگوریتم K_means و knn — کلیک کنید.

مزایا و معایب الگوریتم KNN

هر الگوریتم و روشی علاوه بر دارا بودن مزایا، معایبی نیز دارد. در این بخش برخی از مزایا و معایب استفاده از الگوریتم KNN را معرفی می‌کنیم.

مزایای الگوریتم KNN

1. اجرای آن بسیار آسان است.
2. همانطور که قبلاً گفته شد، این الگوریتم یک الگوریتم یادگیری تنبل است و بنابراین نیازی به آموزش قبل از انجام پیش‌بینی‌های زمان واقعی ندارد. این ویژگی سبب می‌شود که الگوریتم KNN بسیار سریع‌تر از سایر الگوریتم‌هایی باشد که به آموزش نیاز دارند مانند SVM، رگرسیون خطی و غیره.
3. از آنجایی که الگوریتم قبل از انجام پیش‌بینی نیازی به آموزش ندارد، داده‌های جدید را می‌توان به طور یکپارچه اضافه کرد.
4. تنها دو پارامتر برای پیاده سازی KNN مورد نیاز است، یعنی مقدار K و تابع فاصله (به عنوان مثال اقلیدسی یا منهتن و غیره).

معایب الگوریتم KNN

1. الگوریتم KNN با داده‌های با ابعاد بالا به خوبی کار نمی‌کند زیرا با تعداد ابعاد زیاد، محاسبه فاصله در هر بعد، برای الگوریتم دشوار می‌شود.
2. الگوریتم KNN هزینه پیش‌بینی بالایی برای مجموعه داده‌های بزرگ دارد. این به این دلیل است که در مجموعه داده‌های بزرگ هزینه محاسبه فاصله بین نقطه جدید و هر نقطه موجود بیشتر می‌شود.
3. در نهایت، الگوریتم KNN با ویژگی‌های طبقه بندی به خوبی کار نمی‌کند زیرا یافتن فاصله بین ابعاد با ویژگی‌های طبقه بندی دشوار است.

پیاده سازی الگوریتم KNN در پایتون با Scikit-Learn

در این بخش، خواهیم دید که چگونه می‌توان از کتابخانه Scikit-Learn پایتون برای پیاده سازی الگوریتم KNN در پایتون در کمتر از ۲۰ خط کد استفاده کرد. راهنمای دانلود و نصب کتابخانه Scikit-Learn در این لینک (+) موجود است. همچنین می توانید از مقاله راهنمای نصب پکیج در پایتون ما نیز برای نصب استفاده کنید.

مجموعه داده یا Dataset

ما از مجموعه داده های iris data برای پیاده سازی الگوریتم KNN در پایتون استفاده می کنیم. مجموعه داده شامل چهار ویژگی است: عرض کاسبرگ، طول کاسبرگ، عرض گلبرگ و طول گلبرگ. این ویژگی،از  ویژگی های انواع خاصی از گیاه زنبق است. وظیفه KNN پیش بینی دسته ای است که این گیاهان به آن تعلق دارند. سه کلاس در مجموعه داده وجود دارد: Iris-setosa، Iris-versicolor و Iris-virginica. لینک دانلود و جزئیات بیشتر مجموعه داده Data set در این لینک (+) موجود است.

وارد کردن کتابخانه‌ها

import numpy as np
import matplotlib.pyplot as plt
import pandas as pd

وارد کردن مجموعه داده Dataset

برای وارد کردن dataset و بارگذاری آن در قالب داده pandas، کد زیر را اجرا کنید:

url = "https://archive.ics.uci.edu/ml/machine-learning-databases/iris/iris.data"

# Assign colum names to the dataset
names = ['sepal-length', 'sepal-width', 'petal-length', 'petal-width', 'Class']

# Read dataset to pandas dataframe
dataset = pd.read_csv(url, names=names)

برای دیدن اینکه مجموعه داده در واقع چه شکلی است، دستور زیر را اجرا کنید:

dataset.head()

اجرای اسکریپت بالا پنج ردیف اول مجموعه داده ما را مطابق جدول زیر نمایش می دهد:

پیش پردازش

مرحله بعدی این است که مجموعه داده خود را به ویژگی‌ها و برچسب‌های آن تقسیم کنیم. برای این کار از کد زیر استفاده کنید:

X = dataset.iloc[:, :-1].values
y = dataset.iloc[:, 4].values

متغیر X شامل چهار ستون اول مجموعه داده (یعنی ویژگی‌ها) است و y حاوی برچسب‌ها است.

تقسیم بندی داده‌های تست و آموزش

برای جلوگیری از برازش بیش از حد over-fitting، مجموعه داده‌های خود را به دو بخش آموزشی Trainو آزمایشی Test تقسیم می‌کنیم، که به ما ایده بهتری درباره نحوه عملکرد الگوریتم در مرحله آزمایش می‌دهد. به این ترتیب الگوریتم بر روی داده‌های دیده نشده آزمایش می‌شود. برای ایجاد تقسم بندی آموزشی و تست، اسکریپت زیر را اجرا کنید:

from sklearn.model_selection import train_test_split
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.20)

اسکریپت فوق مجموعه داده را به ۸۰ درصد داده‌‎های آموزشی و ۲۰ درصد داده‌های تستی تقسیم می‌کند. به این معنی که از مجموع ۱۵۰ رکورد (نمونه)، مجموعه آموزشی شامل ۱۲۰ رکورد و مجموعه تستی شامل ۳۰ رکورد خواهد بود.

نرمال سازی یا مقیاس بندی ویژگی‌ها

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

الگوریتم نزول گرادیان gradient descent ( که در آموزش شبکه های عصبی و سایر الگوریتم‌های یادگیری ماشین استفاده می‌شود) نیز سریع‌تر با ویژگی‌های نرمال شده همگرا می‌شود. اسکریپت زیر مقیاس بندی ویژگی‌ها را انجام می‌دهد:

from sklearn.preprocessing import StandardScaler
scaler = StandardScaler()
scaler.fit(X_train)

X_train = scaler.transform(X_train)
X_test = scaler.transform(X_test)

آموزش و تست دیتاست با الگوریتم KNN

آموزش الگوریتم KNN در پایتون و پیش‌بینی با آن، مخصوصاً هنگام استفاده از Scikit-Learn، بسیار ساده است. برای این کار از کد زیر استفاده کنید.

from sklearn.neighbors import KNeighborsClassifier
classifier = KNeighborsClassifier(n_neighbors=5)
classifier.fit(X_train, y_train)

اولین گام import کردن کلاس KNeighborsClassifier از کتابخانه sklearn.neighbors است. در خط دوم، این کلاس با یک پارامتر، یعنی n_neigbours مقداردهی اولیه می‌شود. این متغیر همان مقدار K است. هیچ مقدار ایده‌آلی برای K وجود ندارد و پس از آزمایش و ارزیابی می‌توان مقدار K را انتخاب کرد، اما برای شروع، مقدار ۵ رایج‌ترین مقدار مورد استفاده برای الگوریتم KNN است.مرحله آخر این است که روی داده‌های آزمایشی خود پیش‌بینی کنیم. برای انجام این کار، اسکریپت زیر را اجرا کنید:

y_pred = classifier.predict(X_test)

ارزیابی الگوریتم KNN

برای ارزیابی یک الگوریتم، ماتریس کانفیوژن Confusion Matrix، دقت precision، فراخوانی recall و F1 score رایج‌ترین معیارهای مورد استفاده هستند. برای محاسبه این معیارها می‌توان از روش‌های confusion_matrix و classification_report sklearn.metrics استفاده کرد. به اسکریپت زیر دقت کنید:

from sklearn.metrics import classification_report, confusion_matrix
print(confusion_matrix(y_test, y_pred))
print(classification_report(y_test, y_pred))

خروجی اسکریپت بالا به شکل زیر است:

[[۱۱  ۰  ۰]
   ۰ ۱۳  ۰]
   ۰  ۱  ۶]]
                 precision   recall   f1-score   support

    Iris-setosa       1.00     1.00       1.00        11
Iris-versicolor       1.00     1.00       1.00        13
 Iris-virginica       1.00     1.00       1.00         6

    avg / total       1.00     1.00       1.00        30

نتایج نشان می‌دهد که الگوریتم KNN توانسته است تمام ۳۰ رکورد موجود در مجموعه تست را با دقت ۱۰۰ درصد طبقه بندی کند که بسیار عالی است. اگرچه الگوریتم با این مجموعه داده بسیار خوب عمل کرد، اما انتظار نداشته باشید که نتایج یکسانی در همه دیتاست‌ها وجود داشته باشد. همانطور که قبلاً ذکر شد، KNN همیشه با ویژگی٬های با ابعاد بالا خوب عمل نمی‌کند ولی برای ویژگی‌های کم بهترین کارکرد را دارد. برای مطالعه بیشتر و آشنایی با این الگوریتم به لینک زیر مراجعه کنید.

• الگوریتم یادگیری ماشین K نزدیک‌ترین همسایه — کلیک کنید.

مقایسه میزان خطا با مقدار K

در بخش آموزش و تست الگوریتم KNN در پایتون گفتیم که هیچ راهی وجود ندارد که از قبل بدانیم کدام مقدار K بهترین نتیجه را دارد. ما به طور تصادفی ۵ را به عنوان مقدار K انتخاب کردیم و اتفاقاً به دقت ۱۰۰٪ منجر شد. یکی از راه‌هایی که به شما کمک می‌کند بهترین مقدار K را پیدا کنید، رسم نمودار مقدار K و میزان خطای مربوطه برای مجموعه داده است.

در این بخش، میانگین خطای مقادیر پیش‌بینی‌شده مجموعه تست را برای همه مقادیر K بین ۱ تا ۴۰ رسم می‌کنیم. برای انجام این کار، اجازه دهید ابتدا میانگین خطا را برای تمام مقادیر پیش‌بینی‌شده که در آن K از ۱ و ۴۰ متغیر است محاسبه کنیم. اسکریپت زیر را اجرا کنید:

error = []

# Calculating error for K values between 1 and 40
for i in range(1, 40):
    knn = KNeighborsClassifier(n_neighbors=i)
    knn.fit(X_train, y_train)
    pred_i = knn.predict(X_test)
    error.append(np.mean(pred_i != y_test))

[/vc_column_text][vc_column_text]

اسکریپت بالا یک حلقه از ۱ تا ۴۰ را اجرا می کند. در هر تکرار میانگین خطای مقادیر پیش بینی شده مجموعه تست محاسبه می‌شود و نتیجه به لیست خطا اضافه می‌شود. مرحله بعدی ترسیم مقادیر خطا در برابر مقادیر K است. اسکریپت زیر را برای ایجاد طرح اجرا کنید:

plt.figure(figsize=(12, 6))
plt.plot(range(1, 40), error, color='red', linestyle='dashed', marker='o',
         markerfacecolor='blue', markersize=10)
plt.title('Error Rate K Value')
plt.xlabel('K Value')
plt.ylabel('Mean Error')

نمودار خروجی به شکل زیر است:

از خروجی می٬بینیم که وقتی مقدار K بین ۵ تا ۱۸ باشد میانگین خطا صفر است. توصیه می‌کنم با مقدار K بازی کنید تا ببینید که چگونه بر دقت پیش بینی‌ها تأثیر می‌گذارد.

سخن پایانی

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

توصیه می‌کنیم برای آمادگی بهتر در پیاده سازی و کدنویسی الگوریتم KNN در پایتون، الگوریتم KNN را برای مجموعه داده‌های متفاوت پیاده سازی کنید. اندازه تست و تمرین را به همراه مقدار K تغییر دهید تا ببینید نتایج شما چگونه متفاوت است و چگونه می‌توانید دقت الگوریتم خود را بهبود ببخشید. مجموعه خوبی از دیتاست‌های مسائل دسته بندی در این لینک (+) در دسترس شماست.

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

آموزش الگوریتم K نزدیکترین همسایه KNN

آموزش الگوریتم K نزدیکترین همسایه KNN

کلیک کنید