ترجمه فارسی مقاله خوشه‌بندی همسایه‌های تطبیقی ​​تصادفی مضاعف از طریق نگاشت مارکوس

چکیده

Clustering is a fundamental task in machine learning and data science, and similarity graph-based clustering is an important approach within this domain. Doubly stochastic symmetric similarity graphs provide numerous benefits for clustering problems and downstream tasks, yet learning such graphs remains a significant challenge. Marcus theorem states that a strictly positive symmetric matrix can be transformed into a doubly stochastic symmetric matrix by diagonal matrices. However, in clustering, learning sparse matrices is crucial for computational efficiency. We extend Marcus theorem by proposing the Marcus mapping, which indicates that certain sparse matrices can also be transformed into doubly stochastic symmetric matrices via diagonal matrices. Additionally, we introduce rank constraints into the clustering problem and propose the Doubly Stochastic Adaptive Neighbors Clustering algorithm based on the Marcus Mapping (ANCMM). This ensures that the learned graph naturally divides into the desired number of clusters. We validate the effectiveness of our algorithm through extensive comparisons with state-of-the-art algorithms. Finally, we explore the relationship between the Marcus mapping and optimal transport. We prove that the Marcus mapping solves a specific type of optimal transport problem and demonstrate that solving this problem through Marcus mapping is more efficient than directly applying optimal transport methods.

چکیده به فارسی (ترجمه ماشینی)

خوشه بندی یک کار اساسی در یادگیری ماشین و علم داده است و خوشه بندی مبتنی بر نمودار شباهت یک رویکرد مهم در این دامنه است.نمودارهای شباهت متقارن دو برابر تصادفی مزایای بی شماری را برای مشکلات خوشه بندی و کارهای پایین دست فراهم می کند ، اما یادگیری چنین نمودارهایی یک چالش مهم است.قضیه مارکوس اظهار می دارد که یک ماتریس متقارن کاملاً مثبت می تواند توسط ماتریس مورب به یک ماتریس متقارن دو برابر تبدیل شود.با این حال ، در خوشه بندی ، یادگیری ماتریس های پراکنده برای کارآیی محاسباتی بسیار مهم است.ما قضیه مارکوس را با پیشنهاد نقشه برداری مارکوس گسترش می دهیم ، که نشان می دهد برخی از ماتریس های پراکنده نیز می توانند از طریق ماتریس های مورب به ماتریس متقارن دو برابر تصادفی تبدیل شوند.علاوه بر این ، ما محدودیت های رتبه را در مشکل خوشه بندی معرفی می کنیم و الگوریتم خوشه بندی همسایگان سازگار با همسایگان را بر اساس نقشه برداری مارکوس (ANCMM) پیشنهاد می کنیم.این تضمین می کند که نمودار آموخته شده به طور طبیعی به تعداد دلخواه خوشه ها تقسیم می شود.ما اثربخشی الگوریتم خود را از طریق مقایسه های گسترده با الگوریتم های پیشرفته تأیید می کنیم.سرانجام ، ما رابطه بین نقشه برداری مارکوس و حمل و نقل بهینه را بررسی می کنیم.ما ثابت می کنیم که نقشه برداری مارکوس نوع خاصی از مشکل حمل و نقل بهینه را حل می کند و نشان می دهد که حل این مشکل از طریق نقشه برداری مارکوس از استفاده مستقیم از روشهای حمل و نقل بهینه کارآمدتر است.