التصنيف بخوارزمية أقرب الجيران (KNN)

يقدم هذا القسم أبسط مصنف (classifier) في المقرر: خوارزمية أقرب الجيران (k-nearest neighbors, KNN). لتصنيف عينة جديدة، تنظر KNN إلى عينات التدريب الأقرب إليها وتدعها تصوت. ستطبق الطريقة أولا يدويا على تسع أزهار iris حقيقية، ثم تبني نماذج KNN وتقيمها وتضبطها في scikit-learn باستخدام دفتري (notebooks) الأسبوع 5.

الأهداف

في نهاية هذا القسم يجب أن تكون قادرا على:

• شرح كيف تتنبأ KNN بالصنف: مسافة، ثم أقرب K من صفوف التدريب، ثم تصويت بالأغلبية (majority vote).
• حساب المسافات الإقليدية (Euclidean distances) وتنبؤ KNN يدويا عند K = 1 و3 و5.
• تحجيم (scaling) الخصائص (features) باستخدام StandardScaler، وشرح سبب حاجة النموذج المعتمد على المسافة إليه.
• تدريب KNeighborsClassifier، ثم قراءة مصفوفة الالتباس (confusion matrix) والدقة (accuracy) والضبط (precision) والاستدعاء (recall).
• اختيار K بطريقة الكوع (elbow method).
• بناء نموذج KNN واستخدامه على مجموعة بيانات iris، وتطبيق الخطوات نفسها على مشروع فريقك.

موقع الدرس من المقرر

للأسبوع 5 في الخطة ثلاثة أجزاء:

• دفتران. يعمل KNN_Classification على مجموعة بيانات من 1000 صف فيها 10 خصائص مجهولة الاسم وتسمية (label) قيمتها 0 أو 1. ويعمل Nearest Neighbors على أزهار iris.
• سيناريو من الواقع. بناء نموذج تعلم موجه (supervised learning) بسيط باستخدام مجموعة بيانات iris الشهيرة، وهي تحتوي على 150 عينة تصف قياسات ثلاثة أنواع من زهرة iris.
• مرحلة المشروع (project milestone). تنفيذ نموذج تعلم الآلة (Machine Learning Model Implementation): في هذا الأسبوع ينفذ فريقك نموذجا أول على بياناته الخاصة.

في الأسبوعين 3 و4 قسمت البيانات، ودربت نموذج انحدار (regression) ونموذج انحدار لوجستي (logistic regression)، وقيمتهما. وتعيد KNN استخدام نمط fit وpredict وscore نفسه تماما، فالجديد هو الفكرة داخل النموذج.

الجزء 1: فكرة KNN

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

خوارزمية أقرب الجيران خوارزمية تعلم موجه بسيطة تتنبأ بالنتيجة بتحديد نقاط البيانات الأقرب إلى بيانات الإدخال. وفي جملة واحدة: لتصنيف عينة جديدة، ابحث عن أقرب K من عينات التدريب إليها ودعها تصوت؛ والصنف الأكثر تكرارا بينها هو التنبؤ.

المصطلحات على بيانات iris

الخوارزمية في أربع خطوات

1. خزن صفوف التدريب وتسمياتها. وهذا كل ما يحتاج fit إلى فعله.
2. احسب المسافة من نقطة الاستعلام إلى كل صف تدريب.
3. رتب المسافات واحتفظ بأصغر K منها.
4. احسب عدد كل تسمية بين هذه الصفوف الـK. تسمية الأغلبية هي التنبؤ.

يتعلم الانحدار الخطي (linear regression) والانحدار اللوجستي أوزانا أثناء fit. أما KNN فلا تتعلم أي معادلة: إنها تحتفظ بالبيانات نفسها وتؤدي عملها وقت التنبؤ، حين تقيس المسافات.

قياس القرب: المسافة الإقليدية

لصف تدريب x ونقطة استعلام q، ولكل منهما n من الخصائص:

d = square root of ( (x1 - q1)^2 + (x2 - q2)^2 + ... + (xn - qn)^2 )

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

حين تطبع scikit-learn نموذجا مدربا، تعرض metric='minkowski' مع p=2. وهذا المزيج هو المسافة الإقليدية أعلاه تماما.

مثال محلول: زهرة جديدة واحدة يدويا

نأخذ تسع أزهار حقيقية من مجموعة بيانات iris ونستخدم خاصيتين فقط، طول البتلة وعرض البتلة بوحدة سم. قياسات الزهرة الجديدة (4.7, 1.7). نتنبأ بنوعها عند K = 1 وK = 3 وK = 5.

الخطوة 1: مربعات المسافات

لكل زهرة، اطرح نقطة الاستعلام من الزهرة، وربع الفرقين، واجمعهما. الفرق السالب يصبح موجبا عند تربيعه، مثلا (-0.2)^2 = 0.04.

الزهرة F1، وهي من نوع setosa، بعيدة (مربع مسافتها 13.14)، لذا لن تكون أبدا من الجيران القلائل الأقرب.

الخطوة 2: الترتيب وأخذ الجذور

تتعادل F4 وF9 عند مربع مسافة قدره 0.17؛ ولا يهم ذلك هنا، لأنهما في الترتيبين 7 و8 ونحن لا ننظر أبعد من الترتيب 5.

الخطوة 3: التصويت

• K = 1: تصوت F2 وحدها. 1 versicolor، إذن التنبؤ versicolor.
• K = 3: تصوت F2 وF7 وF6. 2 virginica، و1 versicolor، إذن التنبؤ virginica. تتغلب زهرتا virginica على F2.
• K = 5: تنضم F5 وF3. 3 versicolor، و2 virginica، إذن التنبؤ versicolor.

حصلت الزهرة نفسها على ثلاث إجابات مختلفة مع زيادة K. فقيمة K إعداد يغير سلوك النموذج، ويبين الجزء 3 كيف يختارها الدفتر.

لترى المثال يتحرك، افتح ملعب KNN على الأزهار التسع بملء الشاشة. اسحب الزهرة الجديدة، وغير K، واضغط تشغيل أو خطوة لكشف الجيران واحدا بعد الآخر.

قيمة K اختيار، والتعادل وارد

• لا تتعلم الخوارزمية قيمة K من البيانات. أنت تختارها، ثم تتحقق من اختيارك على بيانات الاختبار.
• قيمة K الصغيرة تتبع الصف الأقرب وحده، حتى لو كان صفا شاذا.
• قيمة K الأكبر تصغي إلى صفوف أكثر، فيقل أثر الصف الشاذ الواحد.
• مع قيمة K زوجية قد يتعادل التصويت، مثل 1 مقابل 1 عند K = 2.

حين يتعادل التصويت، تعطي scikit-learn التنبؤ للصنف صاحب الرقم الأصغر (في iris يغلب versicolor 1 على virginica 2). ومع صنفين لا يمكن أن يتعادل التصويت عند قيمة K فردية.

الجزء 2: الدفتر 1، بيانات Classified Data

افتح الدفتر

افتح KNN_Classification في Colab

تقرأ الخلية الأولى البيانات من ملف اسمه Classified Data في مجلد الدفتر نفسه. هذا الملف غير موجود حين يفتح الدفتر في Colab: فهو في المستودع داخل المجلد Datasets. اقرأه من المستودع بدلا من ذلك:

import pandas as pd
import numpy as np
import seaborn as sns
import matplotlib.pyplot as plt
 
url = ("https://raw.githubusercontent.com/"
       "tirthajyoti/Machine-Learning-with-Python/"
       "master/Datasets/Classified%20Data")
df = pd.read_csv(url, index_col=0)
df.head()

تحميل البيانات وفحصها

يعرض df.info() عدد 1000 صف و11 عمودا: 10 أعمدة خصائص بأسماء مختلقة (WTT، وPTI، وEQW، وغيرها) وعمود تسمية واحد، TARGET CLASS، قيمه 0 و1. والصنفان متوازنان: 500 صف لكل منهما.

ثم يرسم الدفتر مخطط صندوق (boxplot) لكل خاصية، مقسما حسب TARGET CLASS، لنرى أي الخصائص تأخذ قيما مختلفة في الصنفين:

l = list(df.columns)
for i in range(len(l) - 1):
    sns.boxplot(x='TARGET CLASS', y=l[i], data=df)
    plt.figure()

لماذا تحتاج KNN إلى خصائص محجمة

تجمع المسافة مربعات فروق كل الخصائص. والخاصية المقيسة على مقياس أكبر تضيف أرقاما أكبر، فتقرر وحدها أي الصفوف تعد قريبة. يعيد StandardScaler تحجيم كل خاصية إلى متوسط (mean) قدره 0 وانحراف معياري (standard deviation) قدره 1، فيصبح لكل خاصية صوت عادل:

z = (x - mean) / standard deviation

تدرب أداة التحجيم على الخصائص فقط، df.drop('TARGET CLASS', axis=1). ولا تحجم التسمية أبدا.

مثال محلول: تحجيم قيمة واحدة

قيمة الصف 0 في WTT هي x = 0.913917. وعلى الصفوف الـ1000، متوسط WTT هو 0.949682 وانحرافه المعياري 0.289490.

z = (0.913917 - 0.949682) / 0.289490 = -0.12354 (rounded)

القيمة أدنى من المتوسط بقليل، لذا تكون z سالبة قليلا. ويعرض df_feat.head() في الدفتر القيمة -0.123542 في هذه الخلية، وهي القيمة نفسها محسوبة دون تقريب المدخلات.

ويطبع df.describe() انحرافا معياريا مختلفا قليلا للعمود WTT، هو 0.289635، لأن describe() يقسم على n ناقص 1 بينما يقسم StandardScaler على n. ولو استخدمت قيمة describe() لحصلت على -0.123480، وهي لا تطابق الدفتر.

التحجيم والتقسيم والتدريب والتنبؤ

from sklearn.preprocessing import StandardScaler
scaler = StandardScaler()
scaler.fit(df.drop('TARGET CLASS', axis=1))
scaled_features = scaler.transform(df.drop('TARGET CLASS', axis=1))
 
df_feat = pd.DataFrame(scaled_features, columns=df.columns[:-1])
 
from sklearn.model_selection import train_test_split
X_train, X_test, y_train, y_test = train_test_split(
    scaled_features, df['TARGET CLASS'], test_size=0.50, random_state=101)
 
from sklearn.neighbors import KNeighborsClassifier
knn = KNeighborsClassifier(n_neighbors=1)
knn.fit(X_train, y_train)
pred = knn.predict(X_test)

تتعلم fit متوسط كل عمود وانحرافه المعياري، وتطبق transform المعادلة على كل قيمة. وتقسم test_size=0.50 الصفوف إلى 500 صف للتدريب و500 صف للاختبار، وتجعل random_state=101 التقسيم نفسه في كل مرة تشغله.

مثال محلول: تقييم النموذج عند K = 1

يطبع print(confusion_matrix(y_test, pred)):

الصفوف هي الصنف الحقيقي والأعمدة هي التنبؤ، لذا يحمل القطر التنبؤات الصحيحة، وتحمل الخانتان الأخريان الأخطاء.

• التنبؤات الخاطئة: 17 + 24 = 41. والصحيحة: 233 + 226 = 459.
• الدقة: (233 + 226) / 500 = 0.918.
• نسبة الخطأ (error rate): (17 + 24) / 500 = 0.082. ويطبع الدفتر الرقم نفسه باستخدام np.mean(pred != y_test)، وهي نسبة خطأ التصنيف (misclassification error rate).

ويضيف classification_report(y_test, pred) مقياسين لكل صنف:

• ضبط الصنف: من بين الصفوف التي تنبأ النموذج بأنها من هذا الصنف، نسبة ما ينتمي إليه فعلا. للصنف 0: 233 / (233 + 24) = 0.907.
• استدعاء الصنف: من بين الصفوف التي تنتمي فعلا إلى هذا الصنف، نسبة ما وجده النموذج منها. للصنف 0: 233 / (233 + 17) = 0.932.

ويقرب التقرير هذه القيم إلى منزلتين عشريتين:

              precision    recall  f1-score   support
 
           0       0.91      0.93      0.92       250
           1       0.93      0.90      0.92       250
 
    accuracy                           0.92       500
   macro avg       0.92      0.92      0.92       500
weighted avg       0.92      0.92      0.92       500

ويحسب الصنف 1 بالطريقة نفسها: الضبط 226 / (226 + 17) = 0.930 والاستدعاء 226 / (226 + 24) = 0.904. تعرض المخرجات المحفوظة في الدفتر شكلا أقدم للتقرير نفسه، فيه صف أخير باسم avg / total؛ أما الإصدارات الحالية من scikit-learn فتطبع صفوف accuracy وmacro avg وweighted avg الظاهرة هنا.

الجزء 3: اختيار K بطريقة الكوع

يدرب الدفتر نموذجا لكل قيمة K من 1 إلى 59 على التقسيم نفسه، ويسجل نسبة الخطأ على بيانات الاختبار لكل نموذج:

error_rate = []
 
for i in range(1, 60):
    knn = KNeighborsClassifier(n_neighbors=i)
    knn.fit(X_train, y_train)
    pred_i = knn.predict(X_test)
    error_rate.append(np.mean(pred_i != y_test))
 
plt.figure(figsize=(10, 6))
plt.plot(range(1, 60), error_rate, color='blue', linestyle='dashed', marker='o',
         markerfacecolor='red', markersize=8)
plt.title('Error Rate vs. K Value', fontsize=20)
plt.xlabel('K', fontsize=15)
plt.ylabel('Error (misclassification) Rate', fontsize=15)

القيم العشرون الأولى من الحلقة:

كيف تقرأ المنحنى:

• ينخفض الخطأ من 0.082 عند K = 1 إلى 0.048 عند K = 11. وبعد ذلك يستوي المنحنى: كل القيم من K = 12 إلى 59 تقع بين 0.046 و0.056.
• الانحناءة التي يتحول عندها الانخفاض السريع إلى الجزء المستوي هي الكوع. وبعدها لا تكاد قيمة K الأكبر تضيف شيئا، وكل تنبؤ يحتاج إلى حساب مسافات أكثر.
• أدنى خطأ، 0.046، يظهر عند K = 24 و38 و40. والفرق 0.002 يساوي صف اختبار واحدا من 500، فلا تتوج قيمة K بسبب فروق بهذا الصغر.
• القيمة K = 2 أسوأ من K = 1 (0.094 مقابل 0.082). ففي 55 صفا من صفوف الاختبار الـ500 يختلف الجاران الأقربان، فيتعادل التصويت 1 مقابل 1، وتعطي scikit-learn كل تعادل من هذا النوع إلى الصنف 0.

افتح أداة حلقة الكوع بملء الشاشة لتعيد تشغيل الحلقة قيمة بعد قيمة من قيم K وترى مصفوفة الالتباس خلف كل نقطة.

الجزء 4: الدفتر 2، أزهار iris

تحميل iris في DataFrame

import pandas as pd
import matplotlib.pyplot as plt
import seaborn as sns
 
from sklearn.datasets import load_iris
 
iris = load_iris()
df = pd.DataFrame(iris.data, columns=iris.feature_names)
df['class'] = iris.target
df['class name'] = iris.target_names[iris['target']]
df.head()
 
sns.pairplot(df)

مجموعة البيانات مضمنة في scikit-learn، فلا حاجة إلى تنزيل شيء. وهي تضم 150 زهرة، 50 من كل نوع، وأربع خصائص بوحدة سم. يرسم مخطط الأزواج (pair plot) كل زوج من الخصائص أحدهما مقابل الآخر. وفي لوحات طول البتلة وعرض البتلة، يشكل setosa مجموعة بعيدة عن النوعين الآخرين، بينما يقع versicolor وvirginica متجاورين ويتداخلان قليلا، وهناك تحديدا قد تخطئ KNN.

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

from sklearn.model_selection import train_test_split
 
x_train, x_test, y_train, y_test = train_test_split(
    iris.data, iris.target, test_size=0.2, random_state=0)
 
from sklearn.neighbors import KNeighborsClassifier
 
model = KNeighborsClassifier()
model.fit(x_train, y_train)
model.score(x_test, y_test)

• تحتفظ test_size=0.2 بـ30 زهرة من 150 للاختبار، وتدرب النموذج على 120.
• لم نحدد n_neighbors، لذا تستخدم القيمة الافتراضية K = 5.
• تعيد model.score الدقة على مجموعة الاختبار: 0.9667، أي 29 زهرة صحيحة من 30 زهرة اختبار.

التنبؤ بزهرة لم يرها النموذج من قبل

predicted_class = model.predict([[5.6, 4.4, 1.2, 0.4]])
print(predicted_class)
print(iris.target_names[predicted_class[0]])

المخرجات هي [0] ثم setosa. لاحظ زوجي الأقواس: تتوقع predict جدولا من الصفوف، حتى لزهرة واحدة.

ويبين model.kneighbors([[5.6, 4.4, 1.2, 0.4]]) السبب. فهو يعيد أقرب خمس أزهار تدريب ومسافاتها:

لأقرب جار: (5.6 - 5.7)^2 + (4.4 - 4.4)^2 + (1.2 - 1.5)^2 + (0.4 - 0.4)^2 = 0.01 + 0 + 0.09 + 0 = 0.1، والجذر التربيعي للعدد 0.1 هو 0.3162. والجيران الخمسة كلهم من setosa، لذا فالتصويت 5 مقابل 0.

أين يخطئ نموذج iris

مصفوفة confusion_matrix(y_test, model.predict(x_test)) للنموذج نفسه:

الخطأ الوحيد زهرة versicolor تنبأ النموذج بأنها virginica: وهما النوعان المتداخلان في مستوى البتلة.

ومع 30 زهرة اختبار فقط، تساوي الزهرة الواحدة 1/30 = 0.0333 من النتيجة. وعلى هذا التقسيم تحصل K = 1 على 1.0 وتحصل K = 5 على 0.9667؛ وهذا فرق زهرة واحدة، لا فرق حقيقي بين الإعدادين.

افتح ملعب KNN على الأزهار الـ150 كلها بملء الشاشة، وشغل مناطق القرار (decision regions) لترى كيف ينقسم المستوى عند كل قيمة K.

الأخطاء الشائعة

• نسيان تحجيم الخصائص قبل نموذج يعتمد على المسافة.
• تمرير قائمة مسطحة واحدة إلى predict. فهي تحتاج إلى قائمة من الصفوف: [[5.6, 4.4, 1.2, 0.4]].
• قراءة Classified Data في Colab من مجلد لا يحتويه.
• الحكم على النموذج بصفوف التدريب بدلا من صفوف الاختبار.
• تتويج قيمة K بسبب فرق صف أو صفين من صفوف الاختبار.
• استخدام قيمة K زوجية مع صنفين والوقوع في التعادل.

مرحلة المشروع: تنفيذ النموذج

مرحلة هذا الأسبوع هي تنفيذ نموذج تعلم آلة على بيانات مشروع فريقك. باستخدام KNN:

1. خذ الخصائص والهدف (target) اللذين اخترتهما في الأسبوع 4.
2. حجم الخصائص، ثم قسمها إلى مجموعة تدريب ومجموعة اختبار.
3. درب KNeighborsClassifier وتنبأ بمجموعة الاختبار.
4. اعرض مصفوفة الالتباس وclassification_report.
5. شغل حلقة الكوع، واختر K، واكتب سبب اختيارك.

احتفظ بنسب الخطأ وبقيمة K التي اخترتها. في الأسبوع القادم تستمر المرحلة مع أشجار القرار (decision trees) والغابات العشوائية (random forests).

الخلاصة

1. تتنبأ KNN بالتصويت بالأغلبية بين صفوف التدريب الـK الأقرب إلى نقطة الاستعلام.
2. القرب هو المسافة الإقليدية، لذا يجب أن تكون الخصائص على المقياس نفسه.
3. قد يتغير صنف نقطة الاستعلام نفسها مع تغير K: فقيمة K إعداد تختاره أنت.
4. قيم النموذج على بيانات الاختبار بمصفوفة الالتباس والدقة والضبط والاستدعاء.
5. اختر K بطريقة الكوع، ولا تلاحق فروقا من صف أو صفين من صفوف الاختبار.

التمارين

نحو 30 دقيقة. حاول حل كل مهمة قبل أن تقرأ إجابتها في نهاية الصفحة.

التمرين 1: زهرة جديدة ثانية (نحو 10 دقائق)

استخدم الأزهار التسع نفسها من F1 إلى F9 من المثال المحلول (طول البتلة، عرض البتلة). الزهرة الجديدة هي (5.1, 1.75).

1. احسب مربع المسافة من الزهرة الجديدة إلى كل واحدة من الأزهار التسع.
2. رتب الأزهار من الأقرب إلى الأبعد.
3. تنبأ بالنوع عند K = 1 وK = 3 وK = 5.

تلميح: الفروق تنتهي الآن بالرقم 5، مثلا 0.05^2 = 0.0025 و0.15^2 = 0.0225.

التمرين 2: قراءة مصفوفة الالتباس (نحو 5 دقائق)

يعطي الدفتر 1 مع n_neighbors=20 مصفوفة الالتباس هذه على صفوف الاختبار الـ500:

احسب الدقة، ونسبة الخطأ، والضبط والاستدعاء للصنف 1.

التمرين 3: التقييس (standardization) يدويا (نحو 5 دقائق)

تأخذ خاصية واحدة القيم الخمس 4, 6, 8, 10, 12. احسب المتوسط، والانحراف المعياري (اقسم على n، كما يفعل StandardScaler)، وقيم z الخمس.

التمرين 4: في Colab، على iris (نحو 10 دقائق)

1. شغل الدفتر 2 حتى model.score(x_test, y_test).
2. تنبأ بالزهرة [[6.0, 2.9, 4.5, 1.5]] واطبع اسم نوعها.
3. استدع model.kneighbors عليها. كيف صوت جيرانها الخمسة؟
4. مر على قيم K من 1 إلى 15 في حلقة على التقسيم نفسه، واطبع نتيجة كل نموذج. أعد استخدام حلقة الكوع من الدفتر 1 مع x_train وy_train وx_test وy_test وmodel.score.

الإجابات

الإجابة 1

الفروق هي الزهرة ناقص نقطة الاستعلام.

الترتيب:

الأصوات:

• K = 1: 1 virginica، إذن virginica.
• K = 3: 2 versicolor، و1 virginica، إذن versicolor. تتغلب F3 وF4 على F9.
• K = 5: 3 virginica، و2 versicolor، إذن virginica. تعيد F6 وF8 الكفة إلى virginica.

ومرة أخرى تتغير الإجابة مع K.

الإجابة 2

• الدقة: (238 + 238) / 500 = 0.952.
• نسبة الخطأ: (12 + 12) / 500 = 0.048، وهي القيمة التي تسجلها حلقة الكوع عند K = 20.
• ضبط الصنف 1: 238 / (238 + 12) = 0.952.
• استدعاء الصنف 1: 238 / (238 + 12) = 0.952.

الإجابة 3

• المتوسط: (4 + 6 + 8 + 10 + 12) / 5 = 8.
• مربعات الفروق عن المتوسط: 16, 4, 0, 4, 16، ومجموعها 40.
• الانحراف المعياري: square root of (40 / 5) = square root of 8 = 2.8284.
• قيم z: -1.4142, -0.7071, 0, 0.7071, 1.4142.

للتحقق: مجموع قيم z يساوي 0، والقيمة المساوية للمتوسط تأخذ z = 0.

الإجابة 4

• يعيد model.predict([[6.0, 2.9, 4.5, 1.5]]) القيمة [1]، وiris.target_names[1] هو versicolor.
• الجيران الخمسة الذين يعيدهم model.kneighbors:

التصويت 4 versicolor مقابل 1 virginica، إذن يفوز versicolor.

• النتائج عند K من 1 إلى 15 على التقسيم نفسه:

كل نتيجة إما 1.0000 (أزهار الاختبار الـ30 كلها صحيحة) أو 0.9667 (29 من 30). ومجموعة الاختبار أصغر من أن تميز بين قيم K هذه.