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

الگوریتم K نزدیک ترین همسایه (K-nearest neighbors | KNN) نوعی از الگوریتم های یادگیری ماشینی نظارت شده است. پیاده سازی الگوریتم KNN در پایتون در ابتدایی ترین شکل آن بسیار آسان است. الگوریتم K همسایه نزدیک یک الگوریتم یادگیری به اصطلاح تنبل یا lazy learning algorithm است چون فاز آموزش تخصصی ندارد.

در KNN برای طبقه بندی یا دسته بندی (Classification) یک نمونه جدید از تمام داده ها برای آموزش استفاده می شود. KNN یک الگوریتم یادگیری ناپارامتریک non-parametric است، به این معنی که فرضی در مورد داده های اساسی underlying data ندارد. این خاصییت یک ویژگی بسیار خوب برای الگوریتم است چون بیشتر داده های دنیای واقعی (جداسازی خطی linear-separability، توزیع یکنواخت uniform distribution و غیره)، واقعاً از هیچ فرض نظری پیروی نمی کنند. در این مقاله آموزشی از مجموعه آموزشی پی استور خواهیم دید که چگونه KNN را می توان با کتابخانه Scikit-Learn پایتون پیاده سازی کرد. اما قبل از آن اجازه دهید ابتدا تئوری الگوریتم KNN را بررسی کنیم و ببینیم برخی از مزایا و معایب الگوریتم چیست؟

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

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

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

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

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

در این آموزش به توضیح و تشریح کامل روش K همسایه نزدیک پرداخته شده است. این آموزش توسط مهندس امین جلیل زاده در 24 دقیقه تدریس شده است. برای تهیه این آموزش روی لینک زیر کلیک کنید.

همین الان کلیک کنید

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

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

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

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

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

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

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

در این بخش، خواهیم دید که چگونه می توان از کتابخانه Scikit-Learn پایتون برای پیاده سازی الگوریتم KNN در پایتون در کمتر از 20 خط کد استفاده کرد. راهنمای دانلود و نصب کتابخانه 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)

اسکریپت فوق مجموعه داده را به 80 درصد داده های آموزشی و 20 درصد داده های تستس تقسیم می کند. به این معنی که از مجموع 150 رکورد (نمونه)، مجموعه آموزشی شامل 120 رکورد و مجموعه تستی شامل 30 رکورد خواهد بود.

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

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

الگوریتم نزول گرادیان 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 را انتخاب کرد، اما برای شروع، مقدار 5 رایج‌ترین مقدار مورد استفاده برای الگوریتم 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))

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

[[11  0  0]
   0 13  0]
   0  1  6]]
                 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 توانسته است تمام 30 رکورد موجود در مجموعه تست را با دقت 100 درصد طبقه بندی کند که بسیار عالی است. اگرچه الگوریتم با این مجموعه داده بسیار خوب عمل کرد، اما انتظار نداشته باشید که نتایج یکسانی در همه دیتاست ها وجود داشته باشد. همانطور که قبلاً ذکر شد، KNN همیشه با ویژگی های با ابعاد بالا خوب عمل نمی کند ولی برای ویژگی های کم بهترین کارکرد را دارد.

سورس کد تشخیص نفوذ با الگوریتم یادگیری KNN در متلب

در سورس کد تشخیص نفوذ با الگوریتم یادگیری KNN در متلب، دیتاست معروف سیستم تشخیص نفوذ یعنی NSL-KDD با استفاده از الگوریتم یادگیری ماشین k نزدیکترین همسایه دسته بندی یا کلاس بندی Classfication شده است. برای تهیه این سورس کد روی لینک زیر کلیک کنید.

همین الان کلیک کنید

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

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

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

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))

اسکریپت بالا یک حلقه از 1 تا 40 را اجرا می کند. در هر تکرار میانگین خطای مقادیر پیش بینی شده مجموعه تست محاسبه می شود و نتیجه به لیست خطا اضافه می شود. مرحله بعدی ترسیم مقادیر خطا در برابر مقادیر 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 بین 5 تا 18 باشد میانگین خطا صفر است. توصیه می کنم با مقدار K بازی کنید تا ببینید که چگونه بر دقت پیش بینی ها تأثیر می گذارد.

سخن پایانی

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

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

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