Tag Archives: الجيران الأقرب

خوارزمية الجيران الأقرب k Nearest Neighbours

تعتبر خوارزمية knn من أبسط الخوارزميات التي تستخدم في تعليم الآلة machine learning حتى أن البعض لا يدرجها فعليا ضمن تعليم الآلة وذلك لأنها لا تقوم بالاستفادة من البيانات المقدمة إليها في إيجاد نموذج pattern. بمعنى آخر أنها لا تقوم بالتعلم من المعلومات المقدمة لها. كل ما هنالك أنها تجري عمليات حسابية وتتبع خطوات سنتعرف إليها في المقالة لتوقع نتيجة لبيانات جديدة

 

الخوارزمية تعتمد بشكل أساسي:

أولاً: إلى حساب المسافة (مقياس التشابه similarity measure) باستخدام طرق الحسابية للمسافات الشهيرة مثل المسافة الإقليدية Euclidean أو مانهاتن Manhattan

ثانيا: تقوم باستخدام التصويت في للتوقع نتيجة بيانات جديدة

 

إلى الآن إذا لم تفهم شيئا فلا عليك ، سنقوم بعرض مثال يوضح لك آلية عمل الخوارزمية. لنقل أنك مؤخرا قد أقضيت وقتا في تحضير الكعك cake في المطبخ. بعد تحضير عدة وصفات بمختلف المقادير قررت استخدام حاسوبك القابع في غرفة عملك ليقوم بالتوقع بمستوى جودة الكعك عندما تستخدم وصفة جديدة. أليس سيبدوا ذلك ممتعا؟ وعندها يمكنك تجنب العديد من الوقت الضائع والوصفات التي لو أجريتها لربما باء بعضها بالفشل وضاع المجهود

 

حسنا دعنا نضع المقادير والنتائج التي حصلت عليها إلى الآن وأنت في المطبخ تحضر وصفات مختلفة للكعك

الوصفة

البيض

الماء

الدقيق

النتيجة

1

3

1

3

جيد

2

4

1

4

جيد

3

3

2

3

غير جيد

4

3

2

4

غير جيد

5

4

2

4

؟؟

كما ترى فالمقادير ضمن الجدول تحديد لك الوصفات وبالتالي كمثال لو أخذت السطر الأول (الوصفة الأولى) فالوصفة ستكون عبارة عن 3 بيضات و 1 كوب من الماء و 3 أكواب من الدقيق والنتيجة كانت جيدة أما السطر الأخير فيمثل الوصفة الرابعة وهي عبارة عن 3 بيضات و 2 كوب من الماء و 4 أكواب من الدقيق

 

الآن كيف لنا أن نتوقع نتيجة وصفة جديدة على وشك القيام بها. ولنقل أن الوصفة هي عبارة عن 4 بيضات و 2 كوب من الماء و 4 أكواب من الدقيق

 

لتوقع النتيجة لنقم باستخدام خوارزمية knn باستخدام مقياس إقليدس Euclidean للحساب ولنقم بتطبيق الخطوات على النحول التالي

 

أ. الخطوة الأولى: حساب الفروقات

حساب المسافة (الفروق) بين الوصفة الجديدة وجميع الوصفات القديمة، سنجري عملية الحساب يدويا ثم نكتب طريقة الحساب باستخدام لغة بايثون

لنحسب الفرق بين الوصفة الأولى والوصفة الجديدة
الوصفة الأولى: (3 بيض، 1 ماء، 3 دقيق)

الوصفة الجديدة: (4 بيض، 2، ماء، 4 دقيق)

الفرق باستخدام إقليدس = (3-4)2 + (1-2)2 + (3-4)2

الفرق = 3

 

نكرر العمليات الحسابية على جميع الوصفات وعندها ستكون الفروقات على النحو التالي (لاحظ العمود الأخير باللون الأرجواني -بنفسجي):

الوصفة

البيض

الماء

الدقيق

النتيجة

الفرق

1

3

1

3

جيدة

3

2

4

1

4

جيدة

1

3

3

2

3

غير جيدة

2

4

3

2

4

غير جيدة

1

 

ب. الخطوة الثانية: ترتيب النتائج

نقوم بترتيب الجدول السابق حسب قيمة الفرق ترتيبا تصاعديا

الوصفة

البيض

الماء

الدقيق

النتيجة

الفرق

2

4

1

4

جيدة

1

4

3

2

4

غير جيدة

1

3

3

2

3

غير جيدة

2

1

3

1

3

جيدة

3

 ج. الخطوة الثالثة: عملية التصويت

حتى نجري عملية التصويت لتوقع النتيجة نحتاج إلى تحدد عدد الوصفات السابقة التي تود المقارنة معها. لنقل على سبيل المثال سنجري مقارنة مع 3 وصفات للتصويت. يمعنى سيتم مقارنة نتيجة أول ثلاث وصفات من الجدول السابق ذات المسافات الأقصر (الأقرب إلى الوصفة الجديد). بعد البدء بعملية التصويت ستجد أن هناك وصفة جيدة ووصفتان غير جيدتان أي 1 لصالح النتيجة “الجيدة” و 2 لصالح النتيجة “غير جيدة” (عد للجدول السابق). وعندها سيكون تقيم الوصفة الجديدة هو “غير جيد”. لماذا؟ لأن بالعودة للوصفات الثلاث الأولى في الجدول السابق ستجد أن وحدة منهن كانت “جيدة” و إثنتان “غير جيدة” وبالتالي ستحصل على نتيجة التوقع بأن الوصفة الجديدة ستؤول إلى الوصفات “غير جيدة” فيما لو قمت بتحضيرها

 

 

تطبيق الخطوات السابقة باستخدام بايثون

الآن لنقم بالعلميات السابقة باستخدام بايثون:

 

import numpy as np

x = np.array([[3, 1, 3], [4, 1, 4], [3, 2, 3], [4, 2, 3]])

y = np.array([0, 0, 1, 1])

لاحظ أن y عبارة عن 0 و 1 وهما فقط ترميز للنتائج إذ أن الحاسوب يتعامل فقط مع الأرقام! وبالتالي القيمة 0 تمثل النتيجة “جيدة” وقيمة 1 تمثل النتيجة “غير جيدة”. ولعلمك يمكنك أن تعكس الترميز ولا ضير في ذلك فهي مجرد ترميز لا أكثر ولا تؤثر على النتائج إطلاقا.

 

الآن لنقم بتجهيز الخوارزمية وتدريبها على النحو التالي

from sklearn.neighbors import KNeighborsClassifier

k = 3

knn = KNeighborsClassifier(n_neighbors=k).fit(x, y)

لاحظ أن k تمثل عدد الوصفات التي ستدخل في عملية التصويت

 

وأخير لنقم بإيجاد نتيجة التوقع للوصفة الجديدة على النحو التالي:

knn.predict(np.array([[4, 2, 4]]))

 

وستظهر النتيجة كما يلي

array([1])

لاحظ أن النتيجة هي 1 وهو الترميز الذي استخدمناه للدلالة إلى الوصفة “غير جيدة”. وبالتالي فإنك إن قمت بتحضير الوصفة فإن هذه الخوارزمية تقول لك أن النتيجة ستكون غير جيدة.

 

هذا لا يعني أن النتيجة ستكون غير جيدة قطعا. ولكن يمكن ترجيح النتيجة. ومع ذلك يمكن أيضا معرفة مدى دقة النتائج باستخدام حسابات أخرى في هذه المسألة سأحاول التطرق إلى ذلك في مقالة أخرى.

 

يمكنك الوصل إلى الكود على github: https://github.com/a-kanaan/SharedWorkspace/blob/master/ml/knn/knn_np.ipynb

%d مدونون معجبون بهذه: