Home الذكاء الاصطناعي K-Nearest Neighbor algorithm
K-Nearest Neighbor algorithm

K-Nearest Neighbor algorithm

183
0

بسم الله الرحمن الرحيم

والصلاة والسلام على أشرف المرسلين سيدنا محمد صلى الله علية وسلم

 

K-Nearest Neighbour algorithm

تخيل أنك تحاول أن تتنبأ من هو الرئيس الذى سوف أنتخبة فى الانتخابات القادمة . أذا أنت لا تعرف أى شىء عنى  سوى أين أسكن فمن الأمور المرجح أن تفعلها  أنك سوف تنظر إلى جيرانى وتعرف من سينتخبوا؟

هذا هو أساس خوارزمية K-Nearest Neighbour algorithm

Nearest Neighbors هى أحد خوارزميات التنبؤ Predictive Model وهى لاتحتاج الى تعلم معادلات رياضية معقدة بل تحتاج فقط إلى توفر شيئن فى البيانات DataSet:

  • طريقة لحساب المسافة distance بين البيانات
  • تحقيق افتراضية أن البيانات القريبة من بعضها تكون متشابهة والبعيدة عن بعضها تكون غير متشابهة؟

معظم التقنيات التى تستخدم فى  خوارزميات التنبؤ Predictive Model تنظر الى مجموعة البيانات ككل من أجل معرفة أنماط البيانات لكن  Nearest neighborsمن ناحية أخرى تهمل الكثير من المعلومات حيث ان فيها يتم التنبؤ لكل نقطة جديدة(مثال جديد new instance)  اعتمادا فقط على عدد النقاط القريبة منها.

الخوارزمية خطوة بخطوة:

1-نحدد قيمة  المتغير  k الذى يعبر عن عدد المجاورين

2-نحسب قيمة المسافة بين المثال الجديد والامثلة التى فى dataset

3-نرتب الامثلة لنحصل على المجاورين أعتمادا على أقل مسافة تم حسابها فى الخطوة السابقة ونأخذ منهم عدد k مجاور

4-نحدد الكلاس للمجاورين

5-الكلاس الاكثر اغلبية للمجاورين هو الكلاس المتوقع لهذا المثال

اى الخوارزمية بأختصار “Tell me who your neighbors are, and I’ll tell you who you are”

مثال بسيط لتوضيح طريقة عمل الخوارزمية:

نفترض ان لدينا مصنع يقوم بصنع الاقلام وقمنا بعمل إستطلاع عن جودتهم  من خلال السؤال عن بعض الخصائص (attributes)  فى الاقلام وليكن منهم نوع الحبر ولنعبر عنة بالمتغير  X1,وقابليتة للمسح ونعبر عنة بالمتغير X2 فتجمع لدينا هذة المعلومات

نوع الحبر x1 قابليتة للمسح  x2 التصنيف Classification  Y
7 7 BAD
7 4 BAD
3 4 GOOD
1 4 GOOD

الان لدينا منتج جديد فى المصنع لقلم جديد ولة خاصيتين  X1=3 , X2=7 هل يمكننا التنبؤ بتصنيف هذا القلم؟ لنتبع خطوات الخوارزمية:

1-نحدد قيمة للمتغير الذى سوف يعبر عن عدد المجاورين k  وليكن قيمة k=3

2- نحسب قيمة المسافة بين المنتج الجديد والامثلة التى فى dataset ,فى مثالنا هذا سوف نعتمد على Euclidean Distance حيث يتم حساب المسافة بين نقطتين p,q من المعادلة:


3- نرتب الامثلة لنحصل على المجاورين أعتمادا على أقل مسافة تم حسابها فى الخطوة السابقة ونأخذ منهم عدد k مجاور وحيث k  هنا قيمتة 3 مجاورين فقط وبترتيب الامثلة  حسب المسافة الاقل سوف نلغى المثال الثانى من ان يكون من المجاورين


4-نحدد قيمة التصنيف للمجاورين كما فى العمود الاخير فى الجدول التالى

5- الكلاس الاكثر اغلبية للمجاورين هو GOOD  حيث لدينا ثلاثة أمثلة اثنين منهم GOOD  وواحد فقط BAD لذا الكلاس المتوقع لهذا القلم الجديد هو GOOD

الان أعتقد أن الخوارزمية بسيطة جدا لنطبق على أمثلة معقدة او مشاكل حقيقية من الحياة  Real World Problem

~ The Iris dataset  ~

مجموعة البيانات زهرة Iris أو مجموعة البيانات Fisher’s Iris هى مجموعة من البيانات متعددة المتغيرات multivariate data set وسميت بهذا الاسم نسبة الى العالم رونالد فيشر الذى اعلن عنها فى بحثة سنة 1936, مجموعة البيانات Dataset  عبارة عن 150 مثال(عينة) لثلاثة أنواع من زهرة Iris:

  • Iris setosa
  • Iris virginica
  • Iris versicolor

تم قياس أربع سمات او خصائص attributes or features  من كل نوع: طول وعرض sepals وطول وعرض  petals ,هذا جزء مستقطع من الـ Iris datasetلتوضيحها فى الجدول التالى:

المشكلة التي نريد حلها هي، “طبقا لمجموعة البيانات السابقة  DataSet” اذا حصلنا على  زهرة جديدة ، هل يمكننا التنبؤ بنوعها من قياساتها ؟

بداية  هل نكتب كود لعمل رسم بيانى لهذة الdataset  لان رؤية البيانات بشكل مرئى يعتبر خطوة أولية لفهم هذة المشكلة “Visualization is a good first step”

من الرسم البيانى نجد ان البيانات تنقسم الى مجموعتين كبيرتين :الاولى لزهرة Iris setosa والتى نرمز لها بالمربع الاحمر والمجموعة الثانية هى خليط من Iris virginica والتى نرمز لها بعلامة x  الزرقاء و Iris versicolor بالدائرة الخضراء, الان اذا لدينا زهرة جديدة  كما بالشكل التالى .هل يمكن تصنيفها ؟

المشكلة تعتبر مشكلة تصنيف Classification problem  حيث لدينا مجموعة بيانات dataset  تتكون من مجموعة أمثلة instances  كل مثال لة كلاس معين هل نستطيع تصميم قاعدة rule بحيث تجعلنا نتنبأ بالكلاس لاى مثال جديد غير موجود فى dataset, مشكلة التصنيف لها تطبيقات كثيرة فى الحياة منها تصينف الرسائل هل هى من الرسائل المزعجة spam  او ليست من الرسائل المزعجة not spam وغيرها من المشاكل التى سوف نتطرق لها بعد ذلك بأذن الله تعالى

~~~~     التطبيـــــق العمــــــلى بالكــــــــــــود~~~~~~ 

أولا :التصنيف بأستخدام خوارزمية   k-nearest neighborمن الصفر

k-nearest neighbor from scratch

بعد تحميل ملف الـ iris dataset  من الموقع:

https://archive.ics.uci.edu/ml/machine-learning-databases/iris/iris.data
1-الخطوة الاولى التعامل مع البيانات  Handle Data:
نبدأ بقراءة الملف وتقسيم البيانات عشوائيا الى training set ,test set  باستخدام الميثود loadDataset

يمكن تجربة الميثود بأستخدام الكود التالى:

2-الخطوة الثانية إنشاء ميثود لحساب المسافة او التشابهة  Similarity:
نكتب الميثود euclideanDistance تحسب المسافة بين اى مثاليين وقد تعرضنا من قبل للصيغة الرياضية لها

3-الخطوة الثالثة ايجاد المجاورين Neighbors:
هذة الميثود سوف تستخدم الميثود euclideanDistance لايجاد المسافة بين المثال الجديد والtrainingset  ثم ترتب الامثلة  تنازليا من التى لها مسافة أصغر للحصول على المجاورين

4-الخطوة الرابعة تحديد الmajority  : بعد تحديد المجاورين للمثال الجديد الان نحدد الكلاس الذى لة اكثر اغلبية بينهم وهو النتيجة لتصنيف هذا المثال الجديد

5- حساب دقة الخوارزمية Accuracy:
فى هذة الخطوة نحسب كم عدد الامثلة التى تم التنبؤ بالكلاس الصحيح لها فى testSet

 

ثانيا :التصنيف بأستخدام مكتبة scikit-learn

Classifying with scikit-learn

فى السابق كتابنا كود لبرمجة خوارزمية knn  من البداية ولكن لغة  python لغة مناسبة جدا لتعلم machine learning  لأنها تحتوى على  العديد من المكتبات الممتازة وخاصة المكتبة scikit-learn وفى هذا الجزء سوف نتعلم استخدامها لعمل تصنيف للبيانات باستخدام خوارزمية knn بداية يجب أن تعلم أن scikit-learn classification API تعتمد على أثنين ميثود :

  • fit(features, labels)
  • predict(features)

الميثود fit  وهى خطوة يتم فيها التعلم training  من الامثلة التى لدينا
ثم نستخدم الميثود predict للتنبؤ بالكلاس لمثال جديد
الان لنبدأ بخطوات استخدام المكتبة scikit-learn :
1-الخطوة الاولى التعامل مع البيانات  Loading the data:

  • بداية نعمل import لمجموعة البيانات dataset
  • ثم نستخدم الميثود load_iris() لجلب dataset كلها ثم حفظها فى الكائن iris

لجلب الامثلة instances نستخدم iris.data

لجلب الكلاس لكل مثال نستخدم iris.target

  • لمعرفة ابعاد dataset نستخدم الامر shape

والنتيجة هى انة يوجد 150 مثال كل واحد يحتوى على اربع خصائص

2-الخطوة الثانية : التعامل مع scikit-learn   فى 4 خطوات:
1)      قم بعمل import  للكلاس الذى سوف تستخدمة فى عملية التصنيف وسوف نستخدم هنا خوارزمية  knn لذا نكتب

2)قم بعمل كائن من Estimator وحدد عدد المجاورين

والنتيجة هى:

3)اعطى  الكائن الذى انشأتة knn  البيانات والتى هى الامثلة والكلاس المتوقع لها

4)استخدم الـ Estimatorللحصول على النتيجة اذا اعطيتة مثال جديد

النتيجة هى ان هذا المثال الجديد تم التنبؤ لة بالكلاس 2 وهى زهرة virginica array([2]))
array([2])
5)يمكن ان تعطية اكثر من مثال للحصول على نتيجة مرة واحدة

النتيجة هى ان هذا المثال الجديد الاول تم التنبؤ لة بالكلاس 2 وهى زهرة
Virginica والمثال الثانى تم التنبؤ لة بأنة من زهرة versicolor

 

~ The digits dataset~

هى عبارة عن مجموعة من البيانات تتكون من  1797 صورة وكل صورة عبارة عن مصفوفة  8X8 ، والصورة تمثل رقم ما كما هو  موضح  أدناه .

اذا هذة الdataset  عبارة عن مجموعة من الامثلة كل مثال عبارة عن صورة من 8×8 وعدد الكلاسات 10 ولدينا تقريبا 180 مثال لكل كلاس والمجموع الكلى للامثلة هو 1797 وسوف نمثل الصورة بvector  ابعادة 64 الخصائص تمثل بأرقام من” صفر الى 16″

Classes 10
Samples per class ~180
Samples total 1797
Dimensionality 64
Features integers 0-16

لمزيد من المعلومات عن digits dataset

http://scikitlearn.org/stable/modules/generated/sklearn.datasets.load_digits.html#sklearn.datasets.load_digits

ما الذى تنتظرة الان لدينا dataset  وفهمنا خصائصها لنستخدم مكتبة scikit-learn لعمل التصنيف classification

فى الكود السابق قمنا بالخطوات التى تعلمناها مسبقا  عمل load  الى  dataset ثم قمنا بعمل تدريب training  لهذة الdataset  بخوارزمية knn  حيث استخدامنا الميثود fit  ثم اختبرنا البرنامج بمثال لصورة الذى ترتيبها رقم 99 باستخدام الميثود  prdict ووجدنا انها اعطتنا تصنيف للكلاس الصحيح    الان هل يمكنك التنبؤ عن  الرقم  الموجود فى هذة الصورة: 

 

اذا لا تعرف الاجابة عند تطبيق الكود السابق فهذة الصورة تعبر عن الرقم “1”

ما هى عيوب هذة الخوارزمية

1-

يجب علينا إختيار قيمة دقيقة لعدد المجاورين “Choosing the right value of k “لانة يمكن ونحن نحل احد المشاكل نجد المجاورين يكون الكلاس الذى لة اغلبية كبيرة اكثر من واحد فمثلا  [‘blue’, ‘blue’, ‘red’, ‘red’]فكيف فى هذة الحالة نختار الكلاس الاكثر أغلبية؟

2-ان الخوارزمية تعتبر Lazy-learning اى انة لايتم تكوين قاعدة للتنبؤ إلا عند الاحتياج لمعرفة ما هو الكلاس لمثال جديد.

المراجع

 رجاء:لا تنسونى من الدعاء عن ظهر غيب

الحمد الله رب العالمين والصلاة والسلام على أشرف المرسلين سيدنا محمد صلى الله علية وسلم وعلى اله وصحبة وسلم -اللهم دومها نعمة وأحفظها من الزوال -أمين

(183)

مشاركة