![]() |
وهي من خوارزميات التعلم الآلي ضمن مجموعة التعلم المراقب Supervised Learning،وألتي تُعد من أبسط الخوارزميات نظراً لسهولة استخدامها وأستهلاكها للقليل من |
خوارزمية K-Nearest Neighbors
خصائص خوارزمية 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:
- الفئة الأولى (المربع الأحمر).
- الفئة الثانية (المثلث الأخضر).
وهناك نقطة أختبار واحدة(مؤشرة بالدائرة الزرقاء).أذا أردنا أن نقوم بتصنيف نقطة الأختبار بين هاتين الفئتين،فأي فئة ستنتمي لها؟؟
من البديهي ستكون الأجابة هي الفئة الأولى(المربع الأحمر) وذلك كما نرى أن المسافة بين عينة الأختبارtest point وبين نقاط هذه الفئة هي الأقرب عن نقاط الفئة الأخرى(المثلث الأخضر). وتعتمد خوارزمية KNN على باراميتر نقوم بتنظيمه وهو K حيث يمثل عدد الجيران الأقرب nearest neighbors لنقطة الأختبارtest point. وفي الشكل الأتي نرى تم أختيار قيمة K وهي 3 معنى ذلك أن أقرب نقاط تدريب training points لنقطةالأختبارtest point هي 3 نقاط.
أختيار القيمة المناسبة ل 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 فأرجوا الأطلاع على الموقع الأتي من هنا)، والتي يكون القانون العام لها هو:
حيث تمثل الدائرة باللون الأزرق نقطة الأختبار 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 وتم تصنيفها بشكل دقيق.ولمن اراد الكود كاملاً يمكنه تحميله من ايقونة التحميل في الأسفل.
تعليقات
إرسال تعليق