تحليل مكونات الحي

لنفترض أننا نتنبأ بتصنيف نقطة بيانات واحدة من خلال توافق آراء${\displaystyle k}$- أقرب الجيران بمقياس مسافة محدد. يُعرف هذا بتصنيف "حذف واحد" . ومع ذلك، فإن مجموعة أقرب الجيران${\displaystyle C_{i}}$قد تختلف النتائج اختلافًا كبيرًا بعد تطبيق تحويل خطي على جميع النقاط. على وجه التحديد، يمكن أن تخضع مجموعة النقاط المجاورة لنقطة ما لتغييرات منفصلة استجابةً لتغييرات سلسة في عناصرها.${\displaystyle A}$مما يعني أن أي دالة هدف${\displaystyle f(\cdot )}$بناءً على جيران نقطة ما، ستكون الدالة ثابتة جزئياً ، وبالتالي غير قابلة للتفاضل .

يمكننا حل هذه الصعوبة باستخدام نهج مستوحى من انحدار التدرج العشوائي . بدلاً من النظر في${\displaystyle k}$عند كل نقطة مُحوَّلة في تصنيف LOO، سنعتبر مجموعة البيانات المُحوَّلة بأكملها بمثابة أقرب الجيران العشوائيين . نُعرِّف هؤلاء باستخدام دالة softmax للمسافة الإقليدية التربيعية بين نقطة تصنيف LOO مُعطاة وكل نقطة أخرى في الفضاء المُحوَّل.

${\displaystyle p_{ij}={\begin{cases}{\frac {e^{-||Ax_{i}-Ax_{j}||^{2}}}{\sum _{k\neq i}e^{-||Ax_{i}-Ax_{k}||^{2}}}},&{\mbox{if }}j\neq i\\0,&{\mbox{if }}j=i\end{cases}}}$

احتمالية تصنيف نقطة البيانات بشكل صحيح${\displaystyle i}$هي احتمالية تصنيف نقاط كل من جيرانها ضمن نفس الفئة${\displaystyle C_{i}}$:

${\displaystyle p_{i}=\sum _{j\in C_{i}}p_{ij}\quad }$أين${\displaystyle p_{ij}}$احتمال تصنيف الجار${\displaystyle j}$نقطة${\displaystyle i}$.

حدد دالة الهدف باستخدام تصنيف LOO، هذه المرة باستخدام مجموعة البيانات بأكملها كأقرب الجيران العشوائيين:

${\displaystyle f(A)=\sum _{i}\sum _{j\in C_{i}}p_{ij}=\sum _{i}p_{i}}$

لاحظ أنه في ظل أقرب الجيران العشوائيين، فإن فئة التوافق لنقطة واحدة${\displaystyle i}$هي القيمة المتوقعة لفئة نقطة ما في حالة عدد لا نهائي من العينات المسحوبة من التوزيع على جيرانها.${\displaystyle j\in C_{i}}$أي:${\displaystyle P(Class(X_{i})=Class(X_{j}))=p_{ij}}$وبالتالي، فإن الفئة المتوقعة هي مزيج خطي من فئات كل نقطة أخرى، مرجحة بدالة softmax لكل منها.${\displaystyle j\in C_{j}}$أين${\displaystyle C_{j}}$وهي الآن مجموعة البيانات المحولة بالكامل.

يُفضّل اختيار دالة الهدف هذه لأنها قابلة للتفاضل بالنسبة إلى${\displaystyle A}$(دل${\displaystyle x_{ij}=x_{i}-x_{j}}$):

${\displaystyle {\frac {\partial f}{\partial A}}=-2A\sum _{i}\sum _{j\in C_{i}}p_{ij}\left(x_{ij}x_{ij}^{T}-\sum _{k}p_{ik}x_{ik}x_{ik}^{T}\right)}$

${\displaystyle =2A\sum _{i}\left(p_{i}\sum _{k}p_{ik}x_{ik}x_{ik}^{T}-\sum _{j\in C_{i}}p_{ij}x_{ij}x_{ij}^{T}\right)}$

الحصول على تدرج لـ${\displaystyle A}$يعني هذا أنه يمكن إيجادها باستخدام خوارزمية حل تكرارية مثل خوارزمية التدرج المترافق . تجدر الإشارة إلى أنه عمليًا، تُصبح معظم الحدود الداخلية للتدرج ذات تأثير ضئيل نظرًا لتناقص تأثير النقاط البعيدة عن النقطة محل الاهتمام بسرعة. هذا يعني أنه يمكن اقتطاع المجموع الداخلي للتدرج، مما يُؤدي إلى أوقات حساب معقولة حتى مع مجموعات البيانات الكبيرة.

"تحقيق أقصى قدر من${\displaystyle f(\cdot )}$يعادل تقليل${\displaystyle L_{1}}$المسافة بين التوزيع المتوقع للفئات والتوزيع الحقيقي للفئات (أي: حيث${\displaystyle p_{i}}$ناتج عن${\displaystyle A}$(جميعها تساوي 1). البديل الطبيعي هو تباعد KL، والذي ينتج عنه دالة الهدف والتدرج التاليين: (Goldberger 2005)

${\displaystyle g(A)=\sum _{i}\log \left(\sum _{j\in C_{i}}p_{ij}\right)=\sum _{i}\log(p_{i})}$

${\displaystyle {\frac {\partial g}{\partial A}}=2A\sum _{i}\left(\sum _{k}p_{ik}x_{ik}x_{ik}^{T}-{\frac {\sum _{j\in C_{i}}p_{ij}x_{ij}x_{ij}^{T}}{\sum _{j\in C_{i}}p_{ij}}}\right)}$

عملياً، تحسين${\displaystyle A}$يؤدي استخدام هذه الوظيفة عادةً إلى نتائج أداء مماثلة لتلك التي تم الحصول عليها باستخدام الوظيفة الأصلية.

• تحتوي مكتبة MLPACK على تطبيق بلغة C++
• nca ( C++ )
• تطبيق " NeighborhoodComponentsAnalysis " الخاص بمكتبة scikit-learn (باستخدام لغة بايثون )