تجزیه و تحلیل اجزای همسایگی

تجزیه و تحلیل اجزای همسایگی

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

تعریف

تجزیه و تحلیل اجزای همسایگی "یادگیری" یک معیار فاصله با یافتن یک تبدیل خطی از داده‌های ورودی را هدف قرار می دهد به گونه ای که عملکرد طبقه بندی leave-one-out (LOO) متوسط در فضای تبدیل شده حداکثر شود. بینش کلیدی الگوربتم این است که یک ماتریس $A$ مربوط به تبدیل را می توان با تعریف یک تابع هدف قابل تفکیک برای $A$ بتوان پیدا کرد ، به دنبال آن ، از یک حل کننده تکراری مانند روش گرادیان مزدوج استفاده می شود. یکی از مزایای این الگوریتم این است که تعداد کلاس های $k$ را میتوان به عنوان یک تابع از $A$ تعیین کرد ، تا یک ثابت اسکالر. بنابراین، این استفاده از الگوریتم به موضوع انتخاب مدل می پردازد.

توضیح

به منظور تعریف $A$ ، ما یک تابع هدف را تعریف می کنیم که دقت طبقه بندی را در فضای تبدیل شده توصیف می کند ، و سعی می کنیم $A^{*}$ را طوری تعیین کنیم که این تابع هدف حداکثر شود.

$A^{*}={\mbox{argmax}}_{A}f(A)$

طبقه بندی ترک یکی از نمونه ها (LLO)

پیش‌بینی برچسب کلاس یک نقطه داده با اجماع آن را با کی-نزدیکترین همسایه با متریک فاصله معین نظر بگیرید. این به عنوان طبقه بندی ترک یک نمونه شناخته می شود. با این حال ، مجموعه ای از نزدیکترین همسایگان $C_{i}$ پس از گذراندن تمام نقاط از یک تبدیل خطی می تواند به طور کامل متفاوت باشد. به طور خاص ، یک مجموعه از همسایه ها برای یک نقطه می تواند در پاسخ به تغییرات صاف در عناصر $A$ محتمل تغییرات گسسته شود ، دلالت دارد بر اینکه هر تابع هدف $f(\cdot )$ بر اساس همسایه های یک نقطه تکه ای-ثابت ، و از این رو قابل تمایز نیست.

حل

ما می توانیم این مشکل را با استفاده از رویکردی الهام گرفته از گرادیان کاهشی تصادفی حل کنیم. به جای در نظر گرفتن کی-نزدیکترین همسایه در هر نقطه تبدیل شده در طبقه بندی-LOO ، ما کل مجموعه داده تبدیل شده را به عنوان نزدیکترین همسایه تصادفی در نظر خواهیم گرفت. ما اینها را با استفاده از یک تابع بیشینه هموار از مجذور فاصله اقلیدسی میان یک طبقه بندی-LOO و هر نقطه دیگر در فضای تبدیل شده تعریف می کنیم:

$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}}$

احتمال طبقه بندی صحیح نقطه داده $i$ ، احتمال طبقه بندی نقاط هر یک از همسایگان آن با همان کلاس $C_{i}$ است:

$p_{i}=\sum _{j\in C_{i}}p_{ij}\quad$ که در آن $p_{ij}$ احتمال طبقه بندی همسایه $j$ از نقطه $i$ است.

این بار با استفاده از کل مجموعه داده به عنوان نزدیکترین همسایه های تصادفی تابع هدف را با استفاده از طبقه بندی LOO تعریف کنید:

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

توجه داشته باشید که تحت تصادفی نزدیکترین همسایگان ، کلاس اجماع برای یک نقطه $i$ مقدار مورد انتظار کلاس یک نقطه در حد تعداد نامتناهی نمونه است که از توزیع بر روی همسایگان آن گرفته شده است:

$j\in C_{i}$ i.e.: $P(Class(X_{i})=Class(X_{j}))=p_{ij}$

بنابراین کلاس پیش‌ بینی‌ شده یک ترکیب آفین از کلاس‌ های هر نقطه دیگر است که با تابع بیشینه هموار برای هر $j\in C_{j}$ نقطه وزن می‌شود که $C_{j}$ اکنون کل مجموعه داده تبدیل شده است.

این انتخاب تابع هدف ترجیح داده می شود زیرا با توجه به $A$ قابل تمایز است (مشخص کن $x_{ij}=x_{i}-x_{j}$):

${\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)$

$=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)$

بدست آوردن گرادیان برای $A$ به این معنی است که می توان آن را با یک حل کننده تکراری مانند نزول گرادیان مزدوج پیدا کرد. توجه داشته باشید که در عمل، بیشتر درونی‌ترین اصطلاحات گرادیان به دلیل کاهش سریع سهم نقاط دوردست از نقطه مورد نظر ، به سهم‌های ناچیز ارزیابی می‌شوند. این به این معنی است که مجموع داخلی گرادیان را می توان کوتاه کرد و در نتیجه زمان های محاسباتی معقولی حتی برای مجموعه داده های بزرگ ایجاد می شود.

فرمول جایگزین

"به حداکثر رساندن $f(\cdot )$ ، معادل به حداقل رساندن مقدار $L_{1}$ است ، فاصله بین توزیع کلاس پیش‌ بینی‌ شده و توزیع کلاس واقعی (یعنی: جایی که $p_{i}$ ناشی از $A$ ، همه برابر با یک هستند). یک جایگزین طبیعی واگرایی کولبک-لایبلر است که تابع هدف و گرادیان زیر را شامل می شود:" (گلدبرگر 2005)

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

${\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)$

در عمل، بهینه سازی از $A$ با استفاده از این تابع ، تمایل دارد نتایج عملکردی مشابه با نسخه اصلی ارائه دهد.

تاریخچه و پیشینه

تجزیه و تحلیل اجزای همسایگی توسط جیکوب گلدبرگر، سم رویس، روسلان سالاخودینوف و جف هینتون در بخش علوم کامپیوتر دانشگاه تورنتو در سال 2004 توسعه یافت.

منبع

• J. Goldberger, G. Hinton, S. Roweis, R. Salakhutdinov. (2005) Neighbourhood Components Analysis. Advances in Neural Information Processing Systems. 17, 513–520, 2005.