نمایش مبدأ برای تجزیه و تحلیل اجزای همسایگی

== تجزیه و تحلیل اجزای همسایگی ==
'''تجزیه و تحلیل اجزای همسایگی''' یک روش [[یادگیری تحت نظارت]] برای [[طبقه بندی آماری|طبقه بندی]] [[آمار چندمتغیره|چند متغیره]] داده ها در کلاس های مختلف بر اساس یک [[فضای متری|معیار فاصله]] ی داده شده بر روی داده ها است. از نظر عملکردی ، این روش هدفی مشابه با [[الگوریتم کی-نزدیک‌ترین همسایه]] (KNN) را ارائه می کند ، و به طور مستقیم از یک مفهوم مرتبط به نام همسایگان نزدیک تصادفی استفاده می کند.

== تعریف ==
تجزیه و تحلیل اجزای همسایگی "یادگیری" یک معیار فاصله با یافتن یک تبدیل خطی از داده‌های ورودی را هدف قرار می دهد به گونه ای که عملکرد طبقه بندی leave-one-out (LOO) متوسط در فضای تبدیل شده حداکثر شود. بینش کلیدی الگوربتم این است که یک ماتریس <math>A</math> مربوط به تبدیل را می توان با تعریف یک تابع هدف قابل تفکیک برای <math>A</math> بتوان پیدا کرد ، به دنبال آن ، از یک حل کننده تکراری مانند [[روش گرادیان مزدوج]] استفاده می شود. یکی از مزایای این الگوریتم این است که تعداد کلاس های <math>k</math> را میتوان به عنوان یک تابع از <math>A</math> تعیین کرد ، تا یک ثابت اسکالر. بنابراین، این استفاده از الگوریتم به موضوع [[Model selection|انتخاب مدل]] می پردازد.
== توضیح ==
به منظور تعریف <math>A</math> ، ما یک تابع هدف را تعریف می کنیم که دقت طبقه بندی را در فضای تبدیل شده توصیف می کند ، و سعی می کنیم <math>A^*</math> را طوری تعیین کنیم که این تابع هدف حداکثر شود.
{{چپ‌چین}}
<math>A^* = \mbox{argmax}_A f(A)</math>
{{پایان چپ‌چین}}
'''طبقه بندی ترک یکی از نمونه ها (LLO)'''

پیش‌بینی برچسب کلاس یک نقطه داده با اجماع آن را با کی-نزدیکترین همسایه با متریک فاصله معین نظر بگیرید. این به عنوان طبقه بندی ''ترک یک نمونه'' شناخته می شود. با این حال ، مجموعه ای از نزدیکترین همسایگان <math>C_i</math> پس از گذراندن تمام نقاط از یک تبدیل خطی می تواند به طور کامل متفاوت باشد. به طور خاص ، یک مجموعه از همسایه ها برای یک نقطه می تواند 
در پاسخ به تغییرات صاف در عناصر <math>A</math> محتمل تغییرات گسسته شود ، دلالت دارد بر اینکه هر تابع هدف <math>f(\cdot)</math> بر اساس همسایه های یک نقطه ''تکه ای-ثابت'' ، و از این رو قابل ''تمایز'' نیست.
== حل ==
ما می توانیم این مشکل را با استفاده از رویکردی الهام گرفته از [[گرادیان کاهشی تصادفی]] حل کنیم.
به جای در نظر گرفتن کی-نزدیکترین همسایه در هر نقطه تبدیل شده در طبقه بندی-LOO ، ما کل مجموعه داده تبدیل شده را به عنوان ''نزدیکترین همسایه تصادفی'' در نظر خواهیم گرفت. ما اینها را با استفاده از یک تابع [[بیشینه هموار]] از مجذور [[فاصله اقلیدسی]] میان یک طبقه بندی-LOO و هر نقطه دیگر در فضای تبدیل شده تعریف می کنیم:
{{چپ‌چین}}
<math>p_{ij} =
\begin{cases}
 \frac{e^{-||Ax_i - Ax_j||^2}}{\sum_{k \neq i} e^{-||Ax_i - Ax_k||^2}}, & \mbox{if} j \ne i \\
 0, & \mbox{if} j = i
\end{cases}
</math>
{{پایان چپ‌چین}}

احتمال طبقه بندی صحیح نقطه داده <math>i</math> ، احتمال طبقه بندی نقاط هر یک از همسایگان آن با همان کلاس <math>C_i</math> است:
{{چپ‌چین}}
<math>p_i = \sum_{j \in C_i} p_{ij} \quad </math> که در آن <math> p_{ij} </math> احتمال طبقه بندی همسایه <math>j</math> از نقطه <math>i</math> است.
{{پایان چپ‌چین}}

این بار با استفاده از کل مجموعه داده به عنوان نزدیکترین همسایه های تصادفی تابع هدف را با استفاده از طبقه بندی LOO تعریف کنید:
{{چپ‌چین}}
<math>f(A) = \sum_i \sum_{j \in C_i} p_{ij} = \sum_i p_i</math>
{{پایان چپ‌چین}}

توجه داشته باشید که تحت تصادفی نزدیکترین همسایگان ، کلاس اجماع برای یک نقطه <math>i</math> مقدار مورد انتظار کلاس یک نقطه در حد تعداد نامتناهی نمونه است که از توزیع بر روی همسایگان آن گرفته شده است: {{چپ‌چین}}
<math>j \in C_i</math> i.e.: <math>P(Class(X_i) = Class(X_j)) = p_{ij}</math>
{{پایان چپ‌چین}}

بنابراین کلاس پیش‌ بینی‌ شده یک [[Affine combination|ترکیب آفین]] از کلاس‌ های هر نقطه دیگر است که با تابع بیشینه هموار برای هر <math>j \in C_j</math> نقطه وزن می‌شود که <math>C_j</math> اکنون کل مجموعه داده تبدیل شده است.

این انتخاب تابع هدف ترجیح داده می شود زیرا با توجه به <math>A</math> قابل تمایز است (مشخص کن <math>x_{ij} = x_i - x_j</math>):
{{چپ‌چین}}
<math>
\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 )
</math>

<math> 
 = 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 )
</math>
{{پایان چپ‌چین}}

بدست آوردن [[گرادیان]] برای <math>A</math> به این معنی است که می توان آن را با یک حل کننده تکراری مانند [[روش گرادیان مزدوج|نزول گرادیان مزدوج]] پیدا کرد. توجه داشته باشید که در عمل، بیشتر درونی‌ترین اصطلاحات گرادیان به دلیل کاهش سریع سهم نقاط دوردست از نقطه مورد نظر ، به سهم‌های ناچیز ارزیابی می‌شوند. این به این معنی است که مجموع داخلی گرادیان را می توان کوتاه کرد و در نتیجه زمان های محاسباتی معقولی حتی برای مجموعه داده های بزرگ ایجاد می شود.

== فرمول جایگزین ==
"به حداکثر رساندن <math>f(\cdot)</math> ، معادل به حداقل رساندن مقدار <math>L_1</math> است ، فاصله بین توزیع کلاس پیش‌ بینی‌ شده و توزیع کلاس واقعی (یعنی: جایی که <math>p_i</math> ناشی از <math>A</math> ، همه برابر با یک هستند). یک جایگزین طبیعی واگرایی کولبک-لایبلر است که تابع هدف و گرادیان زیر را شامل می شود:" (گلدبرگر 2005)
{{چپ‌چین}}
<math>
g(A) = \sum_i \log \left ( \sum_{j \in C_i} p_{ij} \right ) = \sum_i \log (p_i)
</math>

<math>
\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 )
</math>
{{پایان چپ‌چین}}

در عمل، بهینه سازی از
<math>A</math> با استفاده از این تابع ، تمایل دارد نتایج عملکردی مشابه با نسخه اصلی ارائه دهد.
== تاریخچه و پیشینه ==
تجزیه و تحلیل اجزای همسایگی توسط جیکوب گلدبرگر، سم رویس، روسلان سالاخودینوف و جف هینتون در بخش علوم کامپیوتر دانشگاه تورنتو در سال 2004 توسعه یافت.
== منبع ==
*J. Goldberger, G. Hinton, S. Roweis, R. Salakhutdinov. (2005) ''[http://www.csri.utoronto.ca/~roweis/papers/ncanips.pdf Neighbourhood Components Analysis].'' Advances in Neural Information Processing Systems. 17, 513–520, 2005.
[[رده:دسته‌بندی آماری]]