ما هو K- أقرب الجار؟ خوارزمية ML لتصنيف البيانات

تقود الخوارزميات عالم التعلم الآلي.

غالبًا ما يتم الإشادة بهم على قدراتهم التنبؤية ويتم التحدث عنهم على أنهم عمال شاقون يستهلكون كميات هائلة من البيانات لتحقيق نتائج فورية.

من بينها ، هناك خوارزمية غالبًا ما يتم تصنيفها على أنها كسولة. لكنها مؤدية تمامًا عندما يتعلق الأمر بتصنيف نقاط البيانات. يطلق عليه خوارزمية k-الأقرب للجيران وغالبًا ما يتم اقتباسه كواحد من أهمها   التعلم الالي   الخوارزميات.

ما هي خوارزمية k- أقرب الجيران؟

تعد خوارزمية k- الأقرب للجيران (KNN) طريقة تصنيف البيانات لتقدير احتمالية أن تصبح نقطة البيانات عضوًا في مجموعة أو أخرى بناءً على المجموعة التي تنتمي إليها نقاط البيانات الأقرب إليها.

تعد خوارزمية k- الجار نوعًا من   التعلم الآلي الخاضع للإشراف   الخوارزمية المستخدمة لحل مشاكل التصنيف والانحدار. ومع ذلك ، فهي تستخدم بشكل أساسي لمشاكل التصنيف.

KNN هي خوارزمية التعلم الكسول وغير المعلمية .

يطلق عليه خوارزمية التعلم الكسول أو المتعلم الكسول لأنه لا يقوم بأي تدريب عند توفير بيانات التدريب. بدلاً من ذلك ، يقوم فقط بتخزين البيانات أثناء وقت التدريب ولا يقوم بأي حسابات. لا يُنشئ نموذجًا حتى يتم تنفيذ استعلام على مجموعة البيانات. هذا يجعل KNN مثاليًا لـ   بيانات التعدين.

تعتبر طريقة غير معلمية لأنها لا تقدم أي افتراضات حول توزيع البيانات الأساسي. ببساطة ، يحاول KNN تحديد المجموعة التي تنتمي إليها نقطة البيانات من خلال النظر في نقاط البيانات المحيطة بها.

ضع في اعتبارك أن هناك مجموعتين ، أ و ب.

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

باختصار ، تتضمن KNN تصنيف نقطة بيانات من خلال النظر إلى أقرب نقطة بيانات مشروحة ، والمعروفة أيضًا باسم أقرب جار .

لا تخلط بين تصنيف K-NN و K-mean clustering. KNN هي خوارزمية تصنيف خاضعة للإشراف تصنف نقاط بيانات جديدة بناءً على أقرب نقاط بيانات. من ناحية أخرى ، فإن K-mean clustering هو   بدون إشراف   خوارزمية التجميع التي تجمع البيانات في عدد K.

كيف يعمل KNN؟

كما ذكر أعلاه ، يتم استخدام خوارزمية KNN في الغالب كمصنف. دعنا نلقي نظرة على كيفية عمل KNN لتصنيف نقاط بيانات الإدخال غير المرئية.

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

في الأساس ، تقوم KNN بتنفيذ آلية تصويت لتحديد فئة الملاحظة غير المرئية. هذا يعني أن الفصل الذي حصل على تصويت الأغلبية سيصبح فئة نقطة البيانات المعنية.

إذا كانت قيمة K تساوي واحدًا ، فسنستخدم أقرب جار فقط لتحديد فئة نقطة البيانات. إذا كانت قيمة K تساوي عشرة ، فسنستخدم أقرب عشرة جيران ، وهكذا.

لوضع ذلك في المنظور ، ضع في اعتبارك نقطة بيانات غير مصنفة X. هناك العديد من نقاط البيانات بفئات معروفة ، A و B ، في مخطط مبعثر.

افترض أن نقطة البيانات X موضوعة بالقرب من المجموعة A.

كما تعلم ، نصنف نقطة بيانات من خلال النظر إلى أقرب نقاط مشروحة. إذا كانت قيمة K تساوي واحدًا ، فسنستخدم أقرب جار واحد فقط لتحديد مجموعة نقطة البيانات.

في هذه الحالة ، تنتمي نقطة البيانات X إلى المجموعة A حيث أن أقرب جار لها يقع في نفس المجموعة. إذا كانت المجموعة A تحتوي على أكثر من عشر نقاط بيانات وقيمة K تساوي 10 ، فإن نقطة البيانات X ستظل تنتمي إلى المجموعة A حيث أن أقرب جيرانها موجودون في نفس المجموعة.

لنفترض أن نقطة بيانات أخرى غير مصنفة Y موضوعة بين المجموعة A والمجموعة B. إذا كانت K تساوي 10 ، فإننا نختار المجموعة التي حصلت على أكبر عدد من الأصوات ، مما يعني أننا نصنف Y إلى المجموعة التي بها أكبر عدد من الجيران. على سبيل المثال ، إذا كان لدى Y سبعة جيران في المجموعة B وثلاثة جيران في المجموعة A ، فإنها تنتمي إلى المجموعة B.

حقيقة أن المصنف يقوم بتعيين الفئة ذات أكبر عدد من الأصوات صحيح بغض النظر عن عدد الفئات الموجودة.

قد تتساءل عن كيفية حساب مقياس المسافة لتحديد ما إذا كانت نقطة البيانات جارة أم لا.

هناك أربع طرق لحساب قياس المسافة بين نقطة البيانات وأقرب جار لها: المسافة الإقليدية ، ومسافة مانهاتن ، ومسافة هامينج ، ومسافة مينكوفسكي . من بين الثلاثة ، تعد المسافة الإقليدية هي دالة أو مقياس المسافة الأكثر استخدامًا.

للتحقق من دقة تصنيف KNN ، أ   الارتباك مصفوفة   يستخدم. يتم أيضًا استخدام طرق إحصائية أخرى مثل اختبار نسبة الاحتمالية للتحقق من الصحة.

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

لماذا نستخدم خوارزمية KNN؟

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

فيما يلي بعض المجالات التي يمكن فيها استخدام خوارزمية الجوار k:

• التصنيف الائتماني: تساعد خوارزمية KNN في تحديد التصنيف الائتماني للفرد من خلال مقارنتها مع تلك ذات الخصائص المماثلة.
• الموافقة على القرض: على غرار التصنيف الائتماني ، فإن خوارزمية k-الأقرب للجوار مفيدة في تحديد الأفراد الذين من المرجح أن يتخلفوا عن سداد القروض من خلال مقارنة سماتهم بأفراد مشابهين.
• المعالجة المسبقة للبيانات: يمكن أن تحتوي مجموعات البيانات على العديد من القيم المفقودة. تُستخدم خوارزمية KNN لعملية تسمى احتساب البيانات المفقودة والتي تقدر القيم المفقودة.
• التعرف على الأنماط: إن قدرة خوارزمية KNN على تحديد الأنماط تخلق مجموعة واسعة من التطبيقات. على سبيل المثال ، يساعد في اكتشاف الأنماط في استخدام بطاقة الائتمان وتحديد الأنماط غير العادية. يعد اكتشاف الأنماط مفيدًا أيضًا في تحديد الأنماط في سلوك الشراء لدى العميل.
• توقع أسعار الأسهم: نظرًا لأن خوارزمية KNN لديها ميل للتنبؤ بقيم الكيانات غير المعروفة ، فهي مفيدة في التنبؤ بالقيمة المستقبلية للأسهم بناءً على البيانات التاريخية.
• أنظمة التوصيات: نظرًا لأن KNN يمكن أن تساعد في العثور على مستخدمين ذوي خصائص متشابهة ، يمكن استخدامها في أنظمة التوصية. على سبيل المثال ، يمكن استخدامه في منصة دفق الفيديو عبر الإنترنت لاقتراح المحتوى الذي من المرجح أن يشاهده المستخدم من خلال تحليل ما يشاهده المستخدمون المماثلون.
• رؤية الكمبيوتر: تستخدم خوارزمية KNN لتصنيف الصور. نظرًا لأنه قادر على تجميع نقاط بيانات متشابهة ، على سبيل المثال ، تجميع القطط معًا والكلاب في فئة مختلفة ، فهي مفيدة في العديد من   رؤية الكمبيوتر   التطبيقات.

كيفية اختيار القيمة المثلى لـ K.

لا توجد طريقة محددة لتحديد أفضل قيمة K - بمعنى آخر - عدد الجيران في KNN. هذا يعني أنك قد تضطر إلى تجربة بعض القيم قبل أن تقرر أيها ستمضي قدمًا.

إحدى الطرق للقيام بذلك هي التفكير (أو التظاهر) بأن جزءًا من عينات التدريب "غير معروف". بعد ذلك ، يمكنك تصنيف البيانات غير المعروفة في مجموعة الاختبار باستخدام خوارزمية k-الأقرب للجيران وتحليل مدى جودة التصنيف الجديد من خلال مقارنته بالمعلومات التي لديك بالفعل في بيانات التدريب.

عند التعامل مع مشكلة من فئتين ، من الأفضل اختيار قيمة فردية لـ K. وإلا ، يمكن أن يظهر سيناريو حيث يكون عدد الجيران في كل فئة هو نفسه. أيضًا ، يجب ألا تكون قيمة K مضاعفًا لعدد الفئات الموجودة.

هناك طريقة أخرى لاختيار القيمة المثلى لـ K وهي حساب الجذر التربيعي (N) ، حيث يشير N إلى عدد العينات في مجموعة بيانات التدريب.

ومع ذلك ، فإن K ذات القيم المنخفضة ، مثل K = 1 أو K = 2 ، يمكن أن تكون صاخبة وتخضع لتأثيرات القيم المتطرفة. فرصة فرط التخصيص عالية أيضًا في مثل هذه الحالات.

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

مزايا وعيوب KNN

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

بالطبع ، هذا مكلف حسابيًا ويستغرق وقتًا طويلاً. ولكن إذا كان لديك الموارد الحسابية اللازمة ، يمكنك استخدام KNN لحل مشاكل الانحدار والتصنيف. على الرغم من وجود العديد من الخوارزميات الأسرع التي يمكن أن تنتج تنبؤات دقيقة.

بالطبع ، KNN ليست خوارزمية تعلم آلي مثالية. نظرًا لأن متنبئ KNN يحسب كل شيء من الألف إلى الياء ، فقد لا يكون مثاليًا لمجموعات البيانات الكبيرة.

KNN ولعنة الأبعاد

عندما يكون لديك كميات هائلة من البيانات في متناول اليد ، فقد يكون من الصعب للغاية استخراج معلومات سريعة ومباشرة منها. لذلك ، يمكننا استخدام خوارزميات تقليل الأبعاد التي ، في جوهرها ، تجعل البيانات "تصل مباشرة إلى النقطة".

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

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

خوارزمية k-الأقرب عرضة للتركيب الزائد بسبب لعنة الأبعاد. ومع ذلك ، يمكن حل هذه المشكلة مع   تنفيذ القوة الغاشمة   خوارزمية KNN. لكنها ليست عملية لمجموعات البيانات الكبيرة.

لا تعمل KNN بشكل جيد إذا كان هناك الكثير من الميزات. ومن ثم ، يجب إجراء تقنيات تقليل الأبعاد مثل تحليل المكونات الرئيسية (PCA) واختيار الميزة أثناء مرحلة إعداد البيانات.

KNN: الخوارزمية الكسولة التي كسبت القلوب

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

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