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

في الإحصاء والتعلم الآلي ، تُعد خوارزمية أقرب الجيران k ( k -NN ) طريقة تعلم غير بارامترية خاضعة للإشراف ، تُعطي وزنًا لعدد الجيران k الأقرب إلى كيان ما عند اتخاذ قرار بشأنه. تُستخدم هذه الخوارزمية في كلٍ من التصنيف - حيث يُسند تصنيفٌ لمثال جديد بناءً على تصنيفات أقرب k مثال تدريبي له - والانحدار - حيث تُحسب التنبؤات من قيم هؤلاء الجيران. ^{[ 1 ] [ 2 ]} ويُستخدم هذا النوع من الخوارزمية بشكلٍ أكثر شيوعًا في التصنيف ، حيث يُحدد مُصنف k -NN انتماء الكائن إلى فئة معينة من خلال تصويت أغلبية الجيران. عادةً ما يكون k عددًا صحيحًا صغيرًا؛ فإذا كان k = 1، يُنسب الكائن ببساطة إلى فئة هذا الجار الأقرب. طُوّرت هذه الخوارزمية لأول مرة على يد إيفلين فيكس وجوزيف هودجز عام 1951، ^{[ 1 ]} ثم وُسّعت لاحقًا على يد توماس كوفر . ^{[ 2 ]}  

يمكن تعميم خوارزمية k -NN لتشمل الانحدار . في انحدار k -NN ، المعروف أيضًا باسم تنعيم الجوار الأقرب ، تكون المخرجات هي قيمة الخاصية للكائن. هذه القيمة هي متوسط ​​قيم أقرب k جار. إذا كانت k  = 1، فإن المخرجات تُسند ببساطة إلى قيمة هذا الجار الأقرب، وهو ما يُعرف أيضًا باسم استيفاء الجوار الأقرب .

في كلٍ من التصنيف والانحدار، تُعدّ تقنية إسناد أوزان لمساهمات الجيران أسلوبًا مفيدًا، بحيث يُسهم الجيران الأقرب في المتوسط ​​أكثر من الجيران الأبعد. على سبيل المثال، يتألف نظام الترجيح الشائع من إعطاء كل جار وزنًا مقداره 1/ d ، حيث d هي المسافة إلى الجار. ^{[ 3 ]}

تتكون المدخلات من أقرب k مثال تدريبي في مجموعة البيانات . تُختار الجيران من مجموعة كائنات معروفة فئتها ( لتصنيف k -NN) أو قيمة خاصية الكائن (لانحدار k -NN). يمكن اعتبار هذه المجموعة بمثابة مجموعة التدريب للخوارزمية، مع العلم أنه لا توجد حاجة إلى خطوة تدريب صريحة.

من خصائص خوارزمية k -NN (بل وعيبها أحيانًا) حساسيتها للبنية المحلية للبيانات. في تصنيف k -NN، يتم تقريب الدالة محليًا فقط، وتُؤجل جميع العمليات الحسابية حتى تقييم الدالة. ولأن هذه الخوارزمية تعتمد على المسافة، فإذا كانت الميزات تمثل وحدات فيزيائية مختلفة أو تأتي بمقاييس متباينة بشكل كبير، فإن تطبيع بيانات التدريب على مستوى الميزات يمكن أن يحسن دقتها بشكل كبير. ^{[ 4 ]}

لنفترض أن لدينا أزواجًا${\displaystyle (X_{1},Y_{1}),(X_{2},Y_{2}),\dots ,(X_{n},Y_{n})}$أخذ القيم في${\displaystyle \mathbb {R} ^{d}\times \{1,2\}}$حيث Y هو تصنيف X ، بحيث${\displaystyle X|Y=r\sim P_{r}}$ل${\displaystyle r=1,2}$(وتوزيعات الاحتمالات)${\displaystyle P_{r}}$). بالنظر إلى معيار معين${\displaystyle \|\cdot \|}$على${\displaystyle \mathbb {R} ^{d}}$ونقطة${\displaystyle x\in \mathbb {R} ^{d}}$، يترك${\displaystyle (X_{(1)},Y_{(1)}),\dots ,(X_{(n)},Y_{(n)})}$إعادة ترتيب بيانات التدريب بحيث$\displaystyle \|X_{(1)}-x\|\leq \dots \leq \|X_{(n)}-x\|}$.

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

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

يُعدّ البُعد الإقليدي مقياسًا شائع الاستخدام لقياس المسافة بين المتغيرات المستمرة . أما بالنسبة للمتغيرات المنفصلة، ​​كما هو الحال في تصنيف النصوص، فيمكن استخدام مقياس آخر، مثل مقياس التداخل (أو مسافة هامينغ ). في سياق بيانات مصفوفات التعبير الجيني ، على سبيل المثال، استُخدمت خوارزمية أقرب جار k مع معاملات الارتباط، مثل بيرسون وسبيرمان، كمقياس. ^{[ 5 ]} غالبًا ما تتحسن دقة تصنيف خوارزمية أقرب جار k بشكل ملحوظ إذا تم تعلم مقياس المسافة باستخدام خوارزميات متخصصة، مثل خوارزمية أقرب جار بهامش كبير أو تحليل مكونات الجوار .

من عيوب تصنيف "التصويت بالأغلبية" الأساسي ظهورُ انحراف في توزيع الفئات. أي أن أمثلة الفئة الأكثر شيوعًا تميل إلى الهيمنة على تنبؤ المثال الجديد، نظرًا لشيوعها بين أقرب k جار بسبب كثرة عددها. ^{[ 7 ]} إحدى طرق التغلب على هذه المشكلة هي ترجيح التصنيف، مع مراعاة المسافة من نقطة الاختبار إلى كلٍّ من أقرب k جار لها. تُضرب فئة (أو قيمة، في مسائل الانحدار) كل نقطة من أقرب k نقطة بوزن يتناسب عكسيًا مع المسافة من تلك النقطة إلى نقطة الاختبار. طريقة أخرى للتغلب على الانحراف هي التجريد في تمثيل البيانات. على سبيل المثال، في خريطة التنظيم الذاتي (SOM)، تمثل كل عقدة مركزًا لمجموعة من النقاط المتشابهة، بغض النظر عن كثافتها في بيانات التدريب الأصلية. يمكن بعد ذلك تطبيق خوارزمية k -NN على خريطة التنظيم الذاتي.

يعتمد اختيار قيمة k المثلى على البيانات؛ فعمومًا، تقلل القيم الأكبر لـ k من تأثير التشويش على التصنيف، ^{[ 8 ]} ولكنها تجعل الحدود بين الفئات أقل وضوحًا. يمكن اختيار قيمة k مناسبة باستخدام تقنيات استدلالية متنوعة (انظر تحسين المعلمات الفائقة ). تُسمى الحالة الخاصة التي يُتوقع فيها أن تكون الفئة هي فئة أقرب عينة تدريبية (أي عندما k = 1) بخوارزمية أقرب جار.

قد تتأثر دقة خوارزمية k -NN سلبًا بوجود خصائص مشوشة أو غير ذات صلة، أو إذا لم تتناسب مقاييس الخصائص مع أهميتها. وقد بُذلت جهود بحثية كبيرة في اختيار الخصائص أو تحديد مقاييسها لتحسين التصنيف. ومن الأساليب الشائعة استخدام الخوارزميات التطورية لتحسين مقاييس الخصائص. ^{[ 9 ]} كما يُعدّ تحديد مقاييس الخصائص بناءً على المعلومات المتبادلة بين بيانات التدريب وفئات التدريب أسلوبًا شائعًا آخر.

في مسائل التصنيف الثنائي (ذات الفئتين)، من المفيد اختيار قيمة فردية لـ k لتجنب تعادل الأصوات. إحدى الطرق الشائعة لاختيار القيمة المثلى تجريبياً لـ k في هذا السياق هي استخدام طريقة التمهيد (Bootstrap). ^{[ 10 ]}

أكثر أنواع مصنفات الجوار الأقرب بديهية هو المصنف الذي يُعيّن النقطة x إلى فئة أقرب جار لها في فضاء الميزات، أي${\displaystyle C_{n}^{1nn}(x)=Y_{(1)}}$.

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

يمكن اعتبار مصنف أقرب k جار بمثابة تعيين وزن لأقرب k جار${\displaystyle 1/k}$وبقية العناصر وزنها صفر . يمكن تعميم ذلك على مصنفات الجوار الأقرب الموزون. أي، حيث يُخصص وزن للجار الأقرب رقم i.${\displaystyle w_{ni}}$، مع${\textstyle \sum _{i=1}^{n}w_{ni}=1}$وينطبق الأمر نفسه على النتيجة المتعلقة بالاتساق القوي لمصنفات الجوار الأقرب الموزون. ^{[ 11 ]}

يترك${\displaystyle C_{n}^{wnn}}$يشير إلى المصنف الأقرب المرجح بالأوزان${\displaystyle \{w_{ni}\}_{i=1}^{n}}$مع مراعاة شروط الانتظام، والتي تُعرف في نظرية التقارب بأنها متغيرات شرطية تتطلب افتراضات للتمييز بين المعلمات وفقًا لمعايير محددة. وبالنسبة لتوزيعات الفئات، فإن للمخاطر الزائدة التوسع التقاربي التالي ^{[ 12 ].}$${\displaystyle {\mathcal {R}}_{\mathcal {R}}(C_{n}^{wnn})-{\mathcal {R}}_{\mathcal {R}}(C^{\text{Bayes}})=\left(B_{1}s_{n}^{2}+B_{2}t_{n}^{2}\right)\{1+o(1)\},}$$ للثوابت${\displaystyle B_{1}}$و${\displaystyle B_{2}}$أين${\displaystyle s_{n}^{2}=\sum _{i=1}^{n}w_{ni}^{2}}$و${\displaystyle t_{n}=n^{-2/d}\sum _{i=1}^{n}w_{ni}\left\{i^{1+2/d}-(i-1)^{1+2/d}\right\}}$.

مخطط الترجيح الأمثل${\displaystyle \{w_{ni}^{*}\}_{i=1}^{n}}$يتم إعطاء المجموعة التي توازن بين الحدين في العرض أعلاه على النحو التالي:${\displaystyle k^{*}=\lfloor Bn^{\frac {4}{d+4}}\rfloor }$، $${\displaystyle w_{ni}^{*}={\frac {1}{k^{*}}}\left[1+{\frac {d}{2}}-{\frac {d}{2{k^{*}}^{2/d}}}\{i^{1+2/d}-(i-1)^{1+2/d}\}\right]}$$ل${\displaystyle i=1,2,\dots ,k^{*}}$و $${\displaystyle w_{ni}^{*}=0}$$ل${\displaystyle i=k^{*}+1,\dots ,n}$.

باستخدام الأوزان المثلى، يكون الحد المهيمن في التوسع التقاربي للمخاطر الزائدة هو${\displaystyle {\mathcal {O}}(n^{-{\frac {4}{d+4}}})}$. وتكون النتائج مماثلة عند استخدام مصنف أقرب جار مجمع .

يستخدم أحد أشكال أسلوب الجوار الأقرب أبعد k جارًا بدلًا من أقربهم. في هذا السياق، يُختار الجيران بناءً على أقصى اختلاف بينهم بدلًا من التشابه. وقد طُرح هذا الأسلوب في أنظمة التوصية كنموذج "جوار معكوس"، حيث يُحدد المستخدمون الأكثر اختلافًا وتُستخدم تفضيلاتهم بشكل عكسي لتوليد التوصيات. ^{[ 13 ]} والهدف عادةً هو زيادة التنوع أو الجدة في العناصر الموصى بها، لأن أساليب الجوار الأقرب التقليدية قد تُفضل العناصر الشائعة أو الواضحة. وقد وجدت التقييمات التجريبية أن أساليب الجوار الأبعد تحقق عمومًا دقة تنبؤية أقل من أساليب الجوار الأقرب k القياسية، على الرغم من أن الفائدة التي يدركها المستخدم قد تكون مماثلة أو أعلى في بعض الحالات.

يُعدّ k -NN حالة خاصة من مُقدِّر "البالون" ذي النطاق الترددي المتغير وكثافة النواة مع نواة منتظمة . ^{[ 14 ] [ 15 ]}

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

يُظهر خوارزمية k- NN نتائج اتساق قوية . فعندما يقترب حجم البيانات من اللانهاية، تضمن خوارزمية k- NN ثنائية التصنيف معدل خطأ لا يتجاوز ضعف معدل خطأ بايز (أقل معدل خطأ ممكن تحقيقه بالنظر إلى توزيع البيانات). ^{[ 2 ]} ويمكن تحسين سرعة خوارزمية k -NN باستخدام رسوم بيانية للتقارب. ^{[ 16 ]}

في تصنيف k- NN متعدد الفئات ، أثبت كوفر وهارت (1967) حدًا أعلى لمعدل الخطأ قدره $${\displaystyle R^{*}\ \leq \ R_{k\mathrm {NN} }\ \leq \ R^{*}\left(2-{\frac {MR^{*}}{M-1}}\right)}$$ أين${\displaystyle R^{*}}$معدل الخطأ في نظرية بايز (وهو أقل معدل خطأ ممكن)،${\displaystyle R_{kNN}}$يمثل معدل الخطأ التقاربي لخوارزمية أقرب جار k ، و M عدد الفئات في المسألة. هذا الحد دقيق بمعنى أن كلا الحدين الأدنى والأعلى يمكن تحقيقه بواسطة توزيع ما. ^{[ 17 ]} لـ${\displaystyle M=2}$ومعدل الخطأ البايزي${\displaystyle R^{*}}$عندما يقترب من الصفر، ينخفض ​​هذا الحد إلى "لا يزيد عن ضعف معدل الخطأ البايزي".

توجد نتائج عديدة حول معدل الخطأ لمصنفات الجوار الأقرب k . ^{[ 18 ]} يتميز مصنف الجوار الأقرب k بقوة (أي لأي توزيع مشترك على${\displaystyle (X,Y)}$) متسقة بشرط${\displaystyle k:=k_{n}}$يتباعد و${\displaystyle k_{n}/n}$يتقارب إلى الصفر عندما${\displaystyle n\to \infty }$.

يترك${\displaystyle C_{n}^{knn}}$لنرمز إلى مصنف أقرب k جار بناءً على مجموعة تدريب بحجم n . في ظل شروط انتظام معينة، ينتج عن المخاطرة الزائدة التوسع التقاربي التالي ^{[ 12 ]}$${\displaystyle {\mathcal {R}}_{\mathcal {R}}(C_{n}^{knn})-{\mathcal {R}}_{\mathcal {R}}(C^{\text{Bayes}})=\left\{B_{1}{\frac {1}{k}}+B_{2}\left({\frac {k}{n}}\right)^{4/d}\right\}\{1+o(1)\},}$$ بالنسبة لبعض الثوابت${\displaystyle B_{1}}$و${\displaystyle B_{2}}$.

الخيار${\displaystyle k^{*}=\left\lfloor Bn^{\frac {4}{d+4}}\right\rfloor }$يُقدّم هذا حلاً وسطاً بين المصطلحين المذكورين في العرض أعلاه، والذي من أجله...${\displaystyle k^{*}}$يتقارب خطأ أقرب جار إلى خطأ بايز بالمعدل الأمثل ( الحد الأدنى الأقصى ).${\displaystyle {\mathcal {O}}\left(n^{-{\frac {4}{d+4}}}\right)}$.

يمكن تحسين أداء تصنيف أقرب جار K بشكل ملحوظ من خلال التعلم المتري ( المُشرف عليه ). ومن الخوارزميات الشائعة تحليل مكونات الجوار وخوارزمية أقرب جار بهامش كبير . تستخدم خوارزميات التعلم المتري المُشرف عليها معلومات التصنيف لتعلم مقياس جديد أو مقياس شبه جديد .

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

مثال على مسار معالجة نموذجي للرؤية الحاسوبية للتعرف على الوجوه باستخدام خوارزمية أقرب جار (k -NN)، بما في ذلك خطوات المعالجة المسبقة لاستخراج الميزات وتقليل الأبعاد (يتم تنفيذها عادةً باستخدام مكتبة OpenCV ):

1. تقنية التعرف على الوجوه من نوع هار
2. تحليل تتبع متوسط ​​التحول
3. إسقاط PCA أو Fisher LDA في فضاء الميزات، متبوعًا بتصنيف k -NN

بالنسبة للبيانات عالية الأبعاد (على سبيل المثال، التي يزيد عدد أبعادها عن 10)، يتم عادةً إجراء تقليل الأبعاد قبل تطبيق خوارزمية k -NN لتجنب آثار لعنة الأبعاد . ^{[ 19 ]}

إن لعنة الأبعاد في سياق k -NN تعني أساسًا أن المسافة الإقليدية غير مفيدة في الأبعاد العالية لأن جميع المتجهات متساوية البعد تقريبًا عن متجه استعلام البحث (تخيل نقاطًا متعددة تقع بشكل أو بآخر على دائرة مع وجود نقطة الاستعلام في المركز؛ المسافة من الاستعلام إلى جميع نقاط البيانات في مساحة البحث متساوية تقريبًا).

يمكن دمج استخلاص الميزات وتقليل الأبعاد في خطوة واحدة باستخدام تقنيات تحليل المكونات الرئيسية (PCA) أو تحليل التمييز الخطي (LDA) أو تحليل الارتباط الكنسي (CCA) كخطوة معالجة مسبقة، يليها التجميع باستخدام خوارزمية أقرب جار (k -NN) على متجهات الميزات في فضاء ذي أبعاد منخفضة. تُسمى هذه العملية أيضًا بالتضمين منخفض الأبعاد . ^{[ 20 ]}

بالنسبة لمجموعات البيانات عالية الأبعاد للغاية (على سبيل المثال عند إجراء بحث عن التشابه في تدفقات الفيديو المباشرة أو بيانات الحمض النووي أو السلاسل الزمنية عالية الأبعاد)، قد يكون تشغيل بحث k -NN التقريبي السريع باستخدام التجزئة الحساسة للموقع ، أو "الإسقاطات العشوائية"، ^{[ 21 ]} أو "الرسومات التخطيطية" ^{[ 22 ]} أو تقنيات البحث عن التشابه عالية الأبعاد الأخرى من مجموعة أدوات VLDB هو الخيار الوحيد الممكن.

تقوم قواعد الجوار الأقرب فعلياً بحساب حدود القرار ضمنياً . كما يمكن حساب حدود القرار بشكل صريح، وبكفاءة عالية، بحيث يكون التعقيد الحسابي دالةً لتعقيد الحدود. ^{[ 23 ]}

يُعدّ اختزال البيانات من أهمّ المشاكل التي تواجه العمل مع مجموعات البيانات الضخمة. عادةً، لا نحتاج إلا إلى بعض نقاط البيانات للتصنيف الدقيق. تُسمى هذه البيانات بالنماذج الأولية ، ويمكن إيجادها كما يلي:

1. حدد القيم الشاذة للفئة ، أي بيانات التدريب التي تم تصنيفها بشكل غير صحيح بواسطة k -NN (لقيمة k معينة ).
2. قسّم باقي البيانات إلى مجموعتين: (أ) النماذج الأولية المستخدمة في قرارات التصنيف، و(ب) النقاط المدمجة التي يمكن تصنيفها بشكل صحيح باستخدام خوارزمية أقرب جار (k -NN) بالاعتماد على النماذج الأولية. بعد ذلك، يمكن إزالة النقاط المدمجة من مجموعة التدريب.

خوارزمية الجوار الأقرب المكثفة لتقليل حجم البيانات

خوارزمية الجوار الأقرب المكثف (CNN، خوارزمية هارت ) هي خوارزمية مصممة لتقليل حجم مجموعة البيانات لتصنيف k -NN. ^{[ 24 ]} تختار هذه الخوارزمية مجموعة النماذج الأولية U من بيانات التدريب، بحيث يمكن لخوارزمية الجوار الأقرب 1NN مع U تصنيف الأمثلة بدقة تقارب دقة تصنيفها مع مجموعة البيانات الكاملة.

بالنظر إلى مجموعة التدريب X ، تعمل الشبكة العصبية التلافيفية بشكل تكراري:

1. قم بمسح جميع عناصر X ، وابحث عن عنصر x الذي يكون أقرب نموذج أولي له من U له تسمية مختلفة عن x .
2. أزل x من X وأضفه إلى U
3. كرر عملية المسح حتى لا تتم إضافة المزيد من النماذج الأولية إلى U.

استخدم U بدلاً من X للتصنيف. تُسمى الأمثلة التي ليست نماذج أولية بالنقاط "المستوعبة".

من الفعال فحص أمثلة التدريب بترتيب تنازلي لنسبة الحدود. ^{[ 25 ]} تُعرَّف نسبة الحدود لمثال تدريبي x على النحو التالي:

a ( x ) = ‖x' - y‖ / ‖xy‖​​​

حيث ‖ xy ‖ هي المسافة إلى أقرب مثال y له لون مختلف عن x ، و ‖ x'-y ‖ هي المسافة من y إلى أقرب مثال له x' بنفس التسمية مثل x .

تقع نسبة الحدود في الفترة [0,1] لأن ‖ x'-y ‖ لا تتجاوز أبدًا ‖ xy ‖ . يُعطي هذا الترتيب الأفضلية لحدود الفئات لإدراجها في مجموعة النماذج الأولية U. تُسمى النقطة ذات التسمية المختلفة عن x نقطة خارجية بالنسبة لـ x . يوضح الشكل على اليمين كيفية حساب نسبة الحدود. تُسمى نقاط البيانات بالألوان: النقطة الابتدائية هي x وتسميتها حمراء. النقاط الخارجية زرقاء وخضراء. أقرب نقطة خارجية إلى x هي y . أقرب نقطة حمراء إلى y هي x' . نسبة الحدود a ( x ) = ‖ x'-y ‖ / ‖ xy ‖ هي سمة النقطة الابتدائية x .

فيما يلي توضيح لشبكة CNN في سلسلة من الأشكال. توجد ثلاث فئات (أحمر، أخضر، وأزرق). الشكل 1: في البداية، توجد 60 نقطة في كل فئة. يوضح الشكل 2 خريطة تصنيف أقرب جار واحد (1NN): حيث يتم تصنيف كل بكسل باستخدام أقرب جار واحد (1NN) مع جميع البيانات. يوضح الشكل 3 خريطة تصنيف أقرب خمسة جيران (5NN). تشير المناطق البيضاء إلى المناطق غير المصنفة، حيث يكون تصويت أقرب خمسة جيران (5NN) متعادلًا (على سبيل المثال، إذا كانت هناك نقطتان خضراوان، ونقطتان حمراوان، ونقطة زرقاء واحدة من بين أقرب خمسة جيران). يوضح الشكل 4 مجموعة البيانات المُصغّرة. تمثل علامات الضرب (×) القيم الشاذة للفئات المختارة وفقًا لقاعدة (3,2)NN (جميع أقرب ثلاثة جيران لهذه الحالات ينتمون إلى فئات أخرى)؛ والمربعات تمثل النماذج الأولية، والدوائر الفارغة تمثل النقاط المُدمجة. تُظهر الزاوية السفلية اليسرى أعداد القيم الشاذة للفئات، والنماذج الأولية، والنقاط المُدمجة لجميع الفئات الثلاث. يتراوح عدد النماذج الأولية من 15% إلى 20% للفئات المختلفة في هذا المثال. يوضح الشكل 5 أن خريطة تصنيف أقرب جار واحد (1NN) باستخدام النماذج الأولية تشبه إلى حد كبير تلك المستخدمة مع مجموعة البيانات الأولية. وقد تم إنتاج هذه الأشكال باستخدام تطبيق Mirkes. ^{[ 25 ]}

• تقليل نموذج الشبكة العصبية التلافيفية لمصنفات k-NN
• 
  الشكل 1. مجموعة البيانات.
• 
  الشكل 2. خريطة تصنيف أقرب جار واحد.
• 
  الشكل 3. خريطة تصنيف 5NN.
• 
  الشكل 4. مجموعة البيانات المخفضة لشبكة CNN.
• 
  الشكل 5. خريطة تصنيف أقرب جار واحد بناءً على النماذج الأولية المستخرجة بواسطة الشبكة العصبية التلافيفية.

في انحدار k -NN، المعروف أيضًا باسم تنعيم k -NN، تُستخدم خوارزمية k -NN لتقدير المتغيرات المستمرة . إحدى هذه الخوارزميات تستخدم المتوسط ​​المرجح لأقرب k جار، مُرجّحًا بمعكوس المسافة بينهم. تعمل هذه الخوارزمية على النحو التالي:

1. احسب المسافة الإقليدية أو مسافة ماهالانوبيس من مثال الاستعلام إلى الأمثلة المصنفة.
2. رتب الأمثلة المصنفة حسب زيادة المسافة.
3. ابحث عن العدد الأمثل k من أقرب الجيران، بناءً على جذر متوسط ​​مربع الخطأ (RMSE) . يتم ذلك باستخدام التحقق المتبادل.
4. احسب المتوسط ​​المرجح بالمسافة العكسية باستخدام أقرب k جار متعدد المتغيرات.

يمكن اعتبار المسافة إلى أقرب جار k بمثابة تقدير للكثافة المحلية، ولذا فهي تُعدّ من معايير الكشف عن القيم الشاذة الشائعة . فكلما زادت المسافة إلى أقرب جار k ، انخفضت الكثافة المحلية، وازداد احتمال كون نقطة الاستعلام قيمة شاذة. ^{[ 26 ]} على الرغم من بساطته، فإن نموذج الكشف عن القيم الشاذة هذا، إلى جانب طريقة أخرى كلاسيكية في استخراج البيانات ، وهي عامل الكشف عن القيم الشاذة المحلية ، يُظهر أداءً جيدًا مقارنةً بالأساليب الأحدث والأكثر تعقيدًا، وذلك وفقًا لتحليل تجريبي واسع النطاق. ^{[ 27 ]}

تُستخدم مصفوفة الارتباك أو "مصفوفة المطابقة" غالبًا كأداة للتحقق من دقة تصنيف k -NN. كما يمكن تطبيق أساليب إحصائية أكثر قوة مثل اختبار نسبة الاحتمال .

• مصنف أقرب مركز ثقل
• مسألة إيجاد أقرب زوج من النقاط
• رسم بياني لأقرب جار
• تصنيف الكائنات بناءً على التجزئة

• داساراثي، بيلور ف. ، محرر (1991). معايير أقرب جار: تقنيات تصنيف أنماط أقرب جار . مطبعة جمعية مهندسي الكهرباء والإلكترونيات. ISBN 978-0818689307.
• شاخناروفيتش، غريغوري؛ داريل، تريفور؛ إنديك، بيوتر، محرران. (2005). أساليب الجوار الأقرب في التعلم والرؤية . مطبعة معهد ماساتشوستس للتكنولوجيا . ISBN 978-0262195478.