التصنيف باستخدام خوارزمية الجار الأقرب

ملخص المحتوى

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

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

تعتبر خوارزمية الجار الأقرب (بالإنجليزية: Nearest Neighbor Algorithm) من تقنيات التنقيب في البيانات. وهي من خوارزميات التصنيف والتنبؤ التي تهدف للتنبؤ عن طريق مقارنة السجلات الشبيهة بالسجل المراد التنبؤ له وتقدير القيمة المجهولة لهذا السجل بناء على معلومات لتلك السجلات.

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

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

استخدامات خوارزمية الجار الأقرب

كثيرًا ما تستخدم خوارزمية الجار الأقرب في مجال التسويق الاستهدافي أو التسويق بالاستهداف.

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

وهناك العديد من الاستخدامات الأخرى لهذه الخوارزمية في العديد من المجالات.

وقد تكون العملية أكثر تعقيدًا كما هو الحال في مشكلات تحديد أسعار البضائع وفق السلاسل الزمنية السابقة.

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

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

مثلا عدد (10) سجلات، ثم استخدام القيم التسعة الأولى منها للتنبؤ بالقيمة العاشرة الأخيرة.

وإذا كان لدينا (100) سجل يمكن تقسيمها لنحصل على (10) مجموعات وعشرة قيم يتم التنبؤ بها بنفس الطريقة.

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

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

الثقة في نتائج الاستكشاف

إن الثقة في نتائج ما يتم التوصل له من استكشاف باستخدام هذه الخوارزمية لها أهمية أيضًا.

ويُعبر عن الثقة بأن نقول أننا على ثقة بنسبة 70% من قيمة معينة قمنا باستكشافها.

وتتم عملية تقدير نسبة الثقة بعدة طرق، منها:

أن يؤخذ بعين الاعتبار المسافة بين السجل المستكشف وبين أقرب جار، فتلك المسافة تلعب دورًا مهما في تقدير نسبة الثقة.

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

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

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

بعكس ما إذا كانت المجموعة منقسمة لقسمين ويؤديان لاستكشاف قيمتين مختلفتين للسجل المستكشف.

المصدر

• كتاب التحليل المتقدم وتنقيب البيانات، د. م. مصطفى فؤاد عبيد، دار الفكر العربي، القاهرة، 2017.