T-sne کاهش ابعاد داده

نمایش T-SNE از دیتاست MNIST

t-SNE یک الگوریتم تجزیه و تحلیل داده‌های چند بعدی است که برای تصویرسازی داده‌ها در فضایی با بعد کمتر(عموما دو بعدی یا سه‌ بعدی) استفاده می‌شود و اولین‌بار، توسط لورنس ون در ماتن و جفری هینتون در سال ۲۰۰۸ معرفی شده است.

با استفاده از t-SNE، می‌توان داده‌های پیچیده و چند بعدی را به صورت یکنواخت و منظم در فضای کاهش‌یافته نشان داد. این الگوریتم باعث ایجاد فضای جدیدی می‌شود که در آن داده‌های مشابه به هم نزدیک و داده‌های متفاوت از هم دور قرار می‌گیرند. به عبارت دیگر، داده‌هایی که در فضای اصلی به هم نزدیک بودند، در فضای کاهش‌یافته نیز به هم نزدیک باقی می‌مانند و داده‌هایی که در فضای اصلی دور از هم بودند، در فضای کاهش‌یافته نیز دور از هم قرار می‌گیرند.

t-SNE برای تصویرسازی داده‌هایی که به صورت غیرخطی در فضای چند بعدی نشان داده می‌شوند، بسیار مناسب است. این الگوریتم برای کاهش ابعاد داده‌های پیچیده، مانند تصاویر و داده‌های صوتی، نیز کارآمد است.

در کل، t-SNE یک الگوریتم کارآمد و مفید برای تصویرسازی داده‌هاست که به صورت گسترده در حوزه‌های مختلف مانند علم داده، بینایی ماشین، آمار، ژنومیک، امنیت سایبری، پردازش زبان طبیعی، تحلیل موسیقی، تحقیقات سرطان، بیوانفورماتیک، تفسیر ژئولوژی، و پردازش سیگنال های پزشکی و ... استفاده می‌شود.

مقدمه

این الگوریتم با محاسبه ماتریس شباهت بین داده‌های مختلف(به صورت پیش‌فرض بر اساس فاصله اقلیدسی)، شروع به کاهش ابعاد داده‌ها می‌کند و با استفاده از توزیع احتمال برای جفت داده‌ها در فضای بالا بعد و فضای پایین بعد، کاهش بعد را انجام می‌دهد. سپس با کمینه کردن فاصله بین این دو توزیع احتمال با استفاده از الگوریتم گرادیان کاهشی، سعی در حفظ ساختار محلی فضای بالا بعد اصلی دارد.

نتیجه‌ی این الگوریتم، نمایشی بهتر و کاهش بعد داده‌ها در فضای پایین بعد است. داده‌هایی که در فضای بالا بعد به هم نزدیک بوده‌اند، در فضای پایین بعد نیز به هم نزدیک باقی خواهند ماند و داده‌هایی که در فضای بالا بعد دور از هم بوده‌اند، در فضای پایین بعد نیز دور از هم خواهند بود.

یکی از مزایای t-SNE، توانایی آن در درک روابط غیرخطی بین داده‌ها است که این الگوریتم را برای تصویرسازی داده‌های پیچیده مانند تصاویر و فایل‌های صوتی مناسب می‌سازد. با این حال، این الگوریتم پردازشی هزینه‌بر است و نیاز به تنظیم دقیق پارامترهای آن دارد تا نتایج بهتری حاصل شود.

جزئیات الگوریتم

t-SNE، با استفاده از یک روش دو مرحله‌ای، نقاط با ویژگی‌های مشابه را در نزدیکی یکدیگر و نقاط با ویژگی‌های متفاوت را در فاصله‌ای دور از یکدیگر قرار می‌دهد. در این روش، توزیع احتمالاتی ابتدا بر اساس فاصله‌های اقلیدسی بین نقاط در فضای بالابعد ساخته می‌شود. سپس، با ساخت یک توزیع احتمالاتی مشابه در فضای پایین‌بعد و کاهش اختلاف کولبک-لایبلر ، نموداری از داده‌های پایین‌بعد ایجاد می‌کند.

با داشتن مجموعه‌ای از $N$ شیء با بعد بالا به عنوان ورودی، t-SNE ابتدا احتمالات $p_{ij}$ را محاسبه می‌کند که نسبت مستقیم با شباهت شیء $x_{i}$ و $x_{j}$ دارند.

برای $i\neq j$، این احتمالات با استفاده از فرمول زیر محاسبه می‌شوند:

$p_{j\mid i}={\frac {\exp(-\lVert \mathbf {x} _{i}-\mathbf {x} _{j}\rVert ^{2}/2\sigma _{i}^{2})}{\sum _{k\neq i}\exp(-\lVert \mathbf {x} _{i}-\mathbf {x} _{k}\rVert ^{2}/2\sigma _{i}^{2})}}$

توجه داشته باشید که $p_{i\mid i}=0$ و برای هر $i$، مجموع $\sum _{j}p_{j\mid i}=1$ است.

همانطور که ون در ماتن و هینتون توضیح داده‌اند: "شباهت نقطه‌ی $x_{j}$ نسبت به نقطه‌ی $x_{i}$، احتمال شرطی $p_{j|i}$ است، که در آن $x_{i}$ نقطه $x_{j}$ را به عنوان همسایه‌اش انتخاب می‌کند اگر همسایه‌ها بر اساس چگالی احتمال خود تحت یک گوسی با مرکز $x_{i}$، انتخاب شوند."

حالا می‌توانیم $p_{ij}$ را به صورت زیر تعریف کنیم:

$p_{ij}={\frac {p_{j\mid i}+p_{i\mid j}}{2N}}$

این ایده به این دلیل مطرح شده است که $p_{i}$ و $p_{j}$ در $N$ نمونه،‌ با ${\frac {1}{N}}$ تخمین زده می‌شوند؛ بنابراین احتمال شرطی می‌تواند به صورت $p_{i\mid j}=Np_{ij}$ و $p_{j\mid i}=Np_{ji}$ نوشته شود؛ و از آنجا که $p_{ij}=p_{ji}$، فرمول قبلی بدست می‌آید.

همچنین توجه داشته باشید که $p_{ii}=0$ و $\sum _{i,j}p_{ij}=1$.

پهنای توابع گاوسی، $\sigma _{i}$ به گونه‌ای تعیین می‌شود که آنتروپی توزیع شرطی برابر با یک آنتروپی از پیش تعریف شده با استفاده از روش دوبخشی باشد. در نتیجه، $\sigma _{i}$ با چگالی داده‌ها متناسب است: مقادیر کوچکتری از $\sigma _{i}$ در قسمت‌های چگال‌تر فضای داده‌ها استفاده می‌شود.

هدف t-SNE این است که نقشه‌ی d-بعدی $\mathbf {y} _{1},\dots ,\mathbf {y} _{N}$ (که در آن $\mathbf {y} _{i}\in \mathbb {R} ^{d}$ و d معمولاً به عنوان 2 یا 3 انتخاب می‌شود) را یاد بگیرد که شباهت‌های $p_{ij}$ را به بهترین شکل ممکن بازتاب می‌دهد. برای این منظور، این الگوریتم شباهت‌های $q_{ij}$ بین دو نقطه در نقشه $\mathbf {y} _{i}$ و $\mathbf {y} _{j}$ را با استفاده از روشی بسیار مشابه اندازه‌گیری می‌کند. به طور خاص، برای $i\neq j$، $q_{ij}$ را به صورت زیر تعریف می‌کنیم:

$q_{ij}={\frac {(1+\lVert \mathbf {y} _{i}-\mathbf {y} _{j}\rVert ^{2})^{-1}}{\sum _{k}\sum _{l\neq k}(1+\lVert \mathbf {y} _{k}-\mathbf {y} _{l}\rVert ^{2})^{-1}}}$

و $q_{ii}$ را صفر قرار می‌دهیم. در اینجا از یک توزیع تی-استیودنت(با درجه آزادی برابر یک، مشابه توزیع کوشی) برای اندازه‌گیری شباهت‌ها بین نقاط با بعد کم استفاده می‌شود تا امکان قرار گرفتن اشیاء نامشابه در فاصله‌های دور در نقشه فراهم شود.

مکان نقاط $\mathbf {y} _{i}$ در نقشه با کمینه کردن اختلاف کولبک-لایبلر غیرمتقارن توزیع P از توزیع Q به دست می‌آید، یعنی:

$\mathrm {KL} \left(P\parallel Q\right)=\sum _{i\neq j}p_{ij}\log {\frac {p_{ij}}{q_{ij}}}$

کمینه‌سازی اختلاف کولبک-لایبلر با توجه به نقاط $\mathbf {y} _{i}$، با استفاده از روش گرادیان کاهشی انجام می‌شود. نتیجه‌ی این بهینه‌سازی، نقشه‌ای است که شباهت‌ها بین ورودی‌های با بعد بالا را بازتاب می‌دهد.