وهي من خوارزميات التعلم الآلي ضمن مجموعة التعلم المراقب Supervised Learning،وألتي تُعد من أبسط الخوارزميات نظراً لسهولة استخدامها وأستهلاكها للقليل من

خوارزمية K-Nearest Neighbors 

وهي من خوارزميات التعلم الآلي ضمن مجموعة التعلم المراقب Supervised Learning،وألتي تُعد من أبسط الخوارزميات نظراً لسهولة استخدامها وأستهلاكها للقليل من الوقت.وتُستخدم في مجالات عدة والأستخدام الشائع لها في مجال نظام التفضيلات Recommendation Systems،حيث أستخدمتها شركة نيتفلكس Netflix عند عرضها أقتراحات مشاهدة الأفلام المفضلة للمشاهدين.

خصائص خوارزمية KNN:

وتُعَرف هذه الخوارزمية على أنها non-parametric و instance-based learning سنتناول هذين المفهومين وتعريفهما كلآتي:   

1- n0n-parametric

وهي الخوارزميات التي لاتحتوي على بارامترات parameters للتدريب بل تحتفظ ببيانات التدريب وأستخدامها أثناء عملية التصنيف لنقطة الأختبارtest point ويكون هذا النوع من الخوارزميات ذات اداء عالي في النتائج بسبب عدم بناء       فرضيات كثيرة عن دالة النموذج.

2-instance-based learning

وهي الخوارزميات التي لاتعتمد على تنظيم البارامترات parameters في عملية تدريب البيانات،بل تعتمد على ترتيب نقاط التدريب training points على أساس مقياس التشابه similarity measures بين مواقع نقاط البيانات data points.أي أن عملية التدريب تتم أثناء تصنيف بيانات الاختبار test data.

كيف تعمل خوارزمية KNN ؟

تقوم خوارزمية KNN بعملية تصنيف نقطة الأختبار test point أعتماداً على نقاط التدريب المحيطة بها، أي الجيران الأقرب لنقطة الأختبار (لذلك سميت هذه الخوارزمية neighbors(nearest.

وأنطلاقاً من المثل الشائع "ألطيور على أشكالها تقع" فعندما تكون مسافة بعض من هذه النقاط الجارة لنقطة الأختبارtest point أقرب من بقية النقاط ستُعتبر نقطة الأختبار منتمية لفئة تلك النقاط.
نستطيع أن نقول أن خوارزمية KNN تعتمد على مقياس التشابه لنقطة الأختبار test point مع أقرب نقاط تدريب لها.وفي الشكل الآتي نرى فضاء ثنائي الأبعاد 2-Dimensional Space يحتوي على فئتين من نقاط التدريب training points:

1. الفئة الأولى (المربع الأحمر).
2. الفئة الثانية (المثلث الأخضر). 

وهناك نقطة أختبار واحدة(مؤشرة بالدائرة الزرقاء).أذا أردنا أن نقوم بتصنيف نقطة الأختبار بين هاتين الفئتين،فأي فئة ستنتمي لها؟؟
من البديهي ستكون الأجابة هي الفئة الأولى(المربع الأحمر) وذلك كما نرى أن المسافة بين عينة الأختبارtest point وبين نقاط هذه الفئة هي الأقرب عن نقاط الفئة الأخرى(المثلث الأخضر). وتعتمد خوارزمية KNN على باراميتر نقوم بتنظيمه وهو K حيث يمثل عدد الجيران الأقرب nearest neighbors لنقطة الأختبارtest point. وفي الشكل الأتي نرى تم أختيار قيمة K وهي 3 معنى ذلك أن أقرب نقاط تدريب training points لنقطةالأختبارtest point هي 3 نقاط.

كيف نختار قيمة K بشكل صحيح؟؟

أختيار القيمة المناسبة ل K وألتي تسمى هذه العملية تنظيم البرامترparameter tuning شيء أساسي في خوارزمية KNN للحصول على أفضل دقة ممكنة.
تصادفنا مشكلة في أختيار قيمة K ،فعند أختيار قيم متنوعة سنلاحظ أختلاف في نتيجة التصنيف كل مرة.سنوضح هذا الأختلاف من خلال الشكل الآتي:

فلو أخترنا قيمة K=3 ،فبالطبع ستنتمي نقطة الأختبار test point الى فئة (المربع الأحمر).أما أذا أخترنا قيمة K=7،فستنتمي عينة الأختبار الى فئة (المثلث الأزرق).
وهنا وقعنا في مشكلة وهي ستتغير نتيجة التصنيف في كل مرة عند تغيير قيم K ،ويمكننا أن نقول أن:

• لايمكننا تحديد القيمة الأفضل لبرامتر K من المرة الأولى،علينا أن نجرب عدة قيم ونختبر نتيجة التصنيف في كل مرة.
• عند أختيار قيم صغيرة لبرامتر K مثلاًK=1 أو K=2 سيسبب المزيد من الضوضاء Noise في البيانات وستتدهور نتيجة التصنيف.
• عند أختيار قيم كبيرة لبرامتر K سيكون هناك خلط في فئات التصنيف،أي ستزداد نسبة التصويت Votes بين الفئات وبالتالي هذا شيء غير مرغوب في عملية التصنيف.

• يُفضل عند أختيار قيم K أن تكون القيم فردية مثلاً K=3,5,7,.. لكي يتم ترجيح كفة واحدة من الفئات على الأخرى دائماً.

يمكن أستعمال طريقة k-fold cross validation لمعالجة هذه المشكلة ويتم خلالها تجزئة بيانات التدريب الى عدة أجزاء والقيام بعملية التدريب لكل جزء وتفحص مدى سلامة عمل الخوارزمية.
والآن نأتي الى مثال بسيط نوضح فيه عمل خوارزمية KNN

في الجدول لآتي بيانات Dataset بسيطة لأشخاص تتكون من بُعدين فقط 2-Dimensions هُما الطول Height والوزن Weight والفئة الخاصة Class لكل سطر. وهذه البيانات هي معلومات لأوزان وأطوال أشخاص ومعرفة حالة كل منهم سواء كان بدين Fat أو نحيف Thin

Class	Weight in kg	Height in cm
Thin	52	175
Fat	80	177
Fat	67	160
Thin	55	182
Fat	100	180
Fat	83	179
Thin	56	177

حسناً,لدينا معلومات لشخص جديد(الطول والوزن) ونحتاج أن نعرف حالة هذا الشخص هل هو بدين أم نحيف؟

??

61

181

لأيجاد الجيران الأقرب لنقطة الأختبار يجب علينا أستخدام المسافة الأقليدية Euclidean Distance (أن كنتَ غير مطَلع على المسافة الأقليدية Euclidean Distance فأرجوا الأطلاع على الموقع الأتي من هنا)، والتي يكون القانون العام لها هو:

عند حساب المسافة الأقليدية Euclidean Distance لنقطة الأختبار test point مع جميع النقاط في فضاء ثنائي الأبعاد 2-Dimensional Space كما في الشكل الأتي:

حيث تمثل الدائرة باللون الأزرق نقطة الأختبار test point و d1,d2,d3,...,d7 المسافة بينها وبين جميع نقاط التدريب         training points. لنفرض أننا حصلنا على نتائج المسافات الموضحة في الجدول أدناه:

Euclidean Distance	Class	Weight in kg	Height in cm
4	Thin	52	175
11	Fat	80	177
15.3	Fat	67	160
1.3	Thin	55	182
16.1	Fat	100	180
11.4	Fat	83	179
1.5	Thin	56	177

أذن كما نلاحظ حصلنا على أصغر مسافة أقليدية الموضحة في المربع الأصفر في الجدول عندما نختار قيمة K=3 ،وبذلك ستُعتبر نقطة الأختبار ضمن فئة النحيف Thin

Thin

61

181

مثال عملي خوارزمية KNN بلغة بايثون: 

سنقوم بشرح مثال بسيط تم تصميمه بلغة بايثون لكي يتم فهم هذه الخوارزمية الرائعة جيداً وايضاً تعلم الواقع العملي بأستخدام البرمجة.وأخترت لغة بايثون خصيصاً لقوة هذه اللغة التي اثبتت جدارتها في معظم المجالات وخصوصاً في مجال تقنيات الذكاء الاصطناعي.

:لنبدأ

import numpy as np

import matplotlib.pyplot as plt

from matplotlib import style

import warnings

from collections import Counter

style.use('fivethirtyeight')

تم إستدعاء المكتبات ألتي سنحتاج إلى إستخدامها وهي: 

• مكتبة matplot ألخاصة برسم ألنماذج والنقاط على الأحداثيات.

• مكتبة warnings ووظيفتها عمل تنبيه للمستخدم في حالة أختيار قيمة k أصغر من عدد الفئات classes.

• مكتبة counter ألتي ستقوم بتعداد أكثر نقاط من ضمن ألنقاط ألقريبة لنقطة الأختبار لكي يتم أختيار ألفئة class ألتي سيتم تصميف نقطة الأختبار إاليها.

,[[training_points = {'black':[[1,2],[2,3],[3,1 
{[['red':[[6,5],[7,7],[8,6'
[test_point = [5,6

قمنا على سبيل المثال بأنشاء نقاط التدريب تحت أسم training_points تحوي مجموعتين هما black و red،وتم أنشاء نقطة أختبار لأجراء عملية التصنيف تحت أسم test_point.

for i in training_points:
    for j in training_points[i]:
        plt.scatter(j[0],j[1],s=100,color=i)
plt.scatter(test_point[0], test_point[1], s=100)
plt.show()

هذا الجزء من الكود يقوم بأجراء عداد على كل نقاط التدريب ونقطة الأختبار ليتم رسمها على مستوي الأحداثيات والذي سيكون بالشكل ادناه:

حيث تمثل النقاط السوداء مجموعة black والنقاط الحمراء مجموعة red وتمثل النقطة الزرقاء هي عينة الأختبار test point

:(def KNN_algorthim(training_data, test_data, k=3
    :if len(training_data) >= k  
        ('!warnings.warn('K is less than classes   
    [] = distances   
    :for c in training_data  
       :[for points in training_data[c  
            )euclidean_distance =np.linalg.norm(np.array 
            ((points) - np.array(test_data 
           ([distances.append([euclidean_distance, c 
    [[major = [i[1] for i in sorted(distances)[:k 
    [majore_result = Counter(major).most_common(1)[0][0 
    return majore_result

الآن نقوم بأنشاء دالة ()KNN_algorthim تحتوي على ثلاث مدخلات وهي training_data,test_data,k .قيمة K ستكون 3 .لنقوم بشرح أسطر كود هذه الدالة بالتفصيل:

if len(training_data) >= k:
    warnings.warn('K is less than classes!')

وضعنا تنبيه للمستخدم يتم تنبيهه في حال تم وضع قيمة للK أصغر من عدد الفئات classes في الخوارزمية.

 []= distances 
:for c in training_data
  :[for points in training_data[c
        )euclidean_distance = np.linalg.norm(np.array
        ((points) - np.array(test_data
        ([distances.append([euclidean_distance, c

تم أنشاء قائمة list تحت أسم distances والتي سيتم اضافة المسافات بين النقاط أليها،بعد ذلك تم عمل عداد لنقاط التدريب لحساب المسافة بين نقطة الأختبار test_data ونقاط التدريب points بأستخدام دالة np.linalg.norm().

major = [i[1] for i in sorted(distances)[:k]]
majore_result = Counter(major).most_common(1)[0][0]
return majore_result

خارج العداد سيتم أستخدام السطرين أعلاه،عند الحصول على المسافات في قائمة distances سنقوم بترتيب المسافات تصاعدياً،أي يكون العنصر الأول في القائمة هي المسافة الأصغر ثم تليها مسافة أكبر منها ثم الأكبر فهكذا.

result = KNN_algorthim(training_points, test_point)
print(result)

 

نأتي الى عملية تصنيف نقطة الأختبار test point بأستخدام دالة الخوارزمية KNN_algorthim ألتي قمنا بأنشائها وتحتوي على مدخلات اثنين هما(training_points, test_point) بعدها نقوم بطباعة النتيجة result سنلاحظ ظهور نتيجة red وهي بالفعل القيمة الصحيحة للتصنيف ونقوم بعدها برسم أحداثيات المستوي للتصنيف الجديد.

:for i in training_points
   :[for j in training_points[i 
        (plt.scatter(j[0],j[1],s=100,color=i  
,plt.scatter(test_point[0], test_point[1], s=100 
(color = result  
()plt.show  

سنرى النقاط الآن بالشكل الآتي:

لاحظنا الآن أن نقطة الآختبار test point أصبحت من ضمن فئة red وتم تصنيفها بشكل دقيق.ولمن اراد الكود كاملاً يمكنه تحميله من ايقونة التحميل في الأسفل.

بهذا ينتهي شرح خوارزمية K-Nearest Neighbors أتمنى أن أكون قد وُفقت في هذا المقال وأذا كان لديكم أي أستفسار أتركو تعليق في أسفل المقالة وأن شاء الله سوف أجاوب عن الأستفسارات وأستودعكم الله.

 م.م رسول حسن