الگوریتم Mean Shift چیست؟ آموزش کامل انتقال میانگین:بخش دوم

10. تحلیل رفتاری و تبیین علمی

10.1 تحلیل هندسی

هندسه Mean Shift را می‌توان میدان برداری‌ای تصور کرد که در هر نقطه جهت میانگین وزن‌دار محلی را نشان می‌دهد. مسیر seedها منحنی‌هایی در این میدان‌اند و مُدها به‌صورت جاذب‌های محلی عمل می‌کنند. مرز میان خوشه‌ها از مرز حوزه‌های جذب نتیجه می‌شود؛ بنابراین خوشه‌ها الزاماً با سلول‌های Voronoi پیرامون مراکز نهایی یکسان نیستند.

در مقایسه با k-means، مرزهای خوشه در Mean Shift مستقیماً توسط centroidهای ثابت تعریف نمی‌شوند. ساختار KDE می‌تواند مرزهای پیچیده‌تری ایجاد کند، ولی اینکه Mean Shift «هر شکل دلخواهی» را بدون محدودیت بازیابی می‌کند، ادعای دقیقی نیست. bandwidth و kernel می‌توانند مُدهای چند ناحیه را ادغام یا برعکس، مُدهای کاذب ایجاد کنند.

10.2 تحلیل آماری

Mean Shift از KDE استفاده می‌کند و در نتیجه با همان مصالحه هموارسازی روبه‌روست. bandwidth کوچک bias هموارسازی را کاهش می‌دهد، اما variance تخمین را افزایش می‌دهد و مُدهای نمونه‌ای یا کاذب می‌تواند زیاد شود. bandwidth بزرگ variance را کاهش می‌دهد، ولی مُدهای واقعی کوچک یا نزدیک ممکن است محو شوند. از منظر clustering، این مصالحه به‌صورت تغییر تعداد و موقعیت خوشه‌ها ظاهر می‌شود.

10.3 داده کم

در نمونه کوچک، KDE به انتخاب bandwidth بسیار حساس است. اگر bandwidth بیش از حد کوچک باشد، هر نمونه یا چند نمونه محدود می‌توانند یک قله جداگانه بسازند. اگر بسیار بزرگ باشد، ساختارهای واقعی با هم ادغام می‌شوند. بنابراین نتیجه Mean Shift روی داده کم باید همراه با تحلیل پایداری نسبت به bandwidth تفسیر شود.

10.4 داده زیاد

با افزایش تعداد نمونه‌ها، برآورد چگالی از نظر آماری می‌تواند باثبات‌تر شود، اما هزینه محاسباتی نسخه مستقیم به‌سرعت افزایش می‌یابد. اگر هر نمونه seed باشد و هر تکرار همه داده را بررسی کند، هزینه تقریبی درجه دوم نسبت به  می‌شود. بنابراین در مقیاس بزرگ، seed reduction، approximate neighbor search یا واریانت‌های شتاب‌یافته اهمیت پیدا می‌کنند.

10.5 نویز

پس نویز پراکنده در صورت bandwidth مناسب معمولاً وزن محلی کمی دارد، ولی در bandwidth کوچک می‌تواند سطح KDE را ناهموار کند. گروه کوچکی از نقاط نویزی متراکم نیز ممکن است یک مُد مستقل تشکیل دهد. Mean Shift نسخه پایه سازوکار صریحی مشابه DBSCAN برای برچسب‌گذاری noise ندارد.

10.6 داده پرت

یک outlier منفرد، اگر bandwidth متوسط یا بزرگ باشد، ممکن است اثر کمی بر مُدهای اصلی داشته باشد؛ اما bandwidth بسیار کوچک می‌تواند آن را به یک مُد محلی تبدیل کند. ارتباط Mean Shift با robust M-estimation در مقاله Comaniciu–Meer نباید به معنای مقاومت کامل و تضمین‌شده در برابر هر نوع آلودگی تفسیر شود (Comaniciu & Meer, 2002).

10.7 عدم‌توازن اندازه و چگالی خوشه‌ها

اگر یک خوشه کوچک و کم‌چگالی در کنار خوشه‌ای بزرگ و پُرچگالی قرار گیرد، bandwidth ثابت ممکن است برای هر دو مناسب نباشد. bandwidth کوچک برای حفظ خوشه کوچک می‌تواند خوشه بزرگ را به چند مُد تقسیم کند؛ bandwidth بزرگ برای هموارکردن خوشه بزرگ می‌تواند خوشه کوچک را حذف کند. این مسئله یکی از انگیزه‌های Variable-Bandwidth و Adaptive Mean Shift است.

10.8 ابعاد بالا

در ابعاد بالا، فاصله‌ها تمرکز پیدا می‌کنند و KDE با curse of dimensionality مواجه می‌شود. هم از نظر آماری به نمونه بیشتری برای تخمین چگالی نیاز است و هم ساختارهای جست‌وجوی همسایگی مانند KD Tree و Ball Tree کارایی کمتری پیدا می‌کنند. Mean Shift پایه به همین دلیل در فضاهای بسیار پُربعد معمولاً نیازمند کاهش بُعد، انتخاب ویژگی یا embedding مناسب است (Georgescu et al., 2003).

10.9 داده ناقص

فرمول پایه Mean Shift فرض می‌کند فاصله و kernel برای بردارهای کامل قابل محاسبه‌اند. در داده دارای missing value، باید قبل از الگوریتم روش مناسبی برای برآورد، حذف یا تعریف فاصله سازگار انتخاب شود. Mean Shift پایه سازوکار بومی برای داده ناقص ندارد.

10.10 همبستگی ویژگی‌ها

اگر ویژگی‌ها همبستگی شدید و مقیاس هندسی ناهمسان داشته باشند، kernel کروی با bandwidth واحد ممکن است ساختار واقعی را به‌خوبی بازنمایی نکند. در چنین وضعیتی، whitening، metric learning یا bandwidth/covariance تطبیقی می‌تواند مناسب‌تر باشد. این موضوع به‌ویژه زمانی مهم است که خوشه‌ها در امتداد جهت‌های باریک و کشیده قرار دارند.

.

11. تحلیل پیچیدگی و مقیاس‌پذیری

فرض کنید N تعداد نمونه‌ها،  dبُعد،  Sتعداد seedها و T تعداد متوسط تکرارها برای هر seed باشد.

11.1 هزینه یک به‌روزرسانی

اگر برای هر seed فاصله تا همه نمونه‌ها محاسبه شود، یک به‌روزرسانی هزینه‌ای از مرتبه زیر دارد:

O(Nd)

برای  seed:

O(SNd)

و برای T تکرار:

O(TSNd)

اگر هر نمونه seed باشد، S=N و هزینه نسخه مستقیم به صورت زیر می‌شود:

O(T N ²d)

11.2.Best Case

برای Mean Shift عمومی، یک best-case مجانبی واحد بدون مشخص‌کردن seed strategy، kernel و ساختار جست‌وجو معنی ندارد. در نسخه مستقیم با S seed و یک پیمایش کامل داده برای هر seed، حتی اگر تعداد تکرارها ثابت و کوچک باشد، هزینه از مرتبه Θ(SNd) است. اگر همه N نمونه seed باشند، هزینه هر تکرار Θ(N²d) باقی می‌ماند؛ کاهش مرتبه عملی مستلزم کاهش seedها، محدودکردن همسایگی، ساختارهای جست‌وجوی مؤثر یا تقریب است.

11.3. Average Case

شواهد کافی برای یک average-case نظری عمومی وجود ندارد. مناسب‌تر است هزینه عملی را با رابطه  گزارش کنیم و تأکید کنیم که  و  به bandwidth، seed strategy، tolerance و هندسه داده وابسته‌اند.

11.4.Worst Case

برای نسخه مستقیم با seed روی همه نمونه‌ها:

O(T N²d)

اگر convergence کند باشد، عامل T می‌تواند قابل توجه شود.

11.5 پیچیدگی حافظه

اگر ماتریس کامل فاصله ذخیره نشود، نگهداری داده و seedها تقریباً نیازمند:

O(Nd+Sd)

است. ذخیره مُدهای نهایی نیز O(kd) حافظه نیاز دارد. اگر وزن یا فاصله همه زوج‌های seed–sample به‌صورت کامل ذخیره شود:

O(SN)

حافظه لازم است و برای S=N به O(N²) می رسد.

11.6 هزینه پیش‌بینی یا انتساب نمونه جدید

Mean Shift در تعریف کلاسیک یک مدل parametric prediction با تابع تصمیم ثابت تولید نمی‌کند. برای نمونه جدید، می‌توان مسیر Mean Shift را از آن آغاز کرد یا پس از استخراج مُدها، آن را با قاعده‌ای مانند نزدیک‌ترین مُد تخصیص داد. هزینه این مرحله بنابراین به قرارداد استفاده وابسته است.

11.7 مقیاس‌پذیری در پیاده‌سازی‌های جدید

مستندات فعلی scikit-learn، MeanShift را مبتنی بر flat kernel و جست‌وجوی Ball Tree توصیف می‌کنند؛ در ابعاد پایین، هزینه با استفاده از جست‌وجوی همسایگی می‌تواند بسیار بهتر از پیمایش زوجی مستقیم باشد، اما در ابعاد بالا به رفتار درجه دوم نزدیک می‌شود. همان مستندات تصریح می‌کنند که estimate_bandwidth دست‌کم نسبت به تعداد نمونه‌های استفاده‌شده هزینه درجه دوم دارد و می‌تواند گلوگاه اصلی باشد (scikit-learn Developers, 2026a, 2026b). MeanShift++ نیز زمان را نسبت به تعداد نقاط خطی می‌کند، اما وابستگی نمایی به بُعد دارد؛ بنابراین مزیت آن عمدتاً برای فضاهای کم‌بُعد معنا دارد (Jang & Jiang, 2021).

.

12. ابرپارامترها و تنظیم

12.1.Bandwidth

bandwidth مهم‌ترین ابرپارامتر Mean Shift است. مقدار کوچک سبب تمرکز kernel در مقیاس محلی‌تر می‌شود و تعداد مُدها را افزایش می‌دهد. مقدار بزرگ ساختار چگالی را بیشتر هموار و تعداد مُدها را کاهش می‌دهد.

هیچ بازه عددی جهانی برای  وجود ندارد، زیرا مقدار مناسب به واحد و scale داده وابسته است. بنابراین پیش از تنظیم bandwidth باید ویژگی‌ها به‌طور معنی‌دار مقیاس‌بندی شوند.

راهبردهای رایج عبارت‌اند از:

• قواعد کلاسیک bandwidth در KDE؛
• استفاده از quantile فاصله‌های زوجی؛
• بررسی پایداری تعداد و موقعیت مُدها در یک sweep از ؛
• انتخاب بر اساس معیارهای کیفیت خوشه، در صورتی که این معیارها با هدف مسئله سازگار باشند؛
• دانش دامنه؛
• تحلیل چندمقیاسی.

مستندات فعلی scikit-learn در estimate_bandwidth از quantile فاصله‌های زوجی استفاده می‌کنند و مقدار پیش‌فرض quantile=0.3 را ارائه می‌دهند. خود مستندات نیز هزینه این تخمین را دست‌کم درجه دوم در تعداد نمونه‌های مورد استفاده می‌دانند و برای داده بزرگ subsampling را پیشنهاد می‌کنند؛ این پیش‌فرض یک مقدار بهینه عمومی نیست (scikit-learn Developers, 2026a).

12.2.Kernel

kernel نحوه افت وزن با فاصله را تعیین می‌کند. Gaussian kernel وزن پیوسته و smooth ایجاد می‌کند؛ flat kernel همسایگی صریح شعاعی دارد. تفاوت kernel می‌تواند trajectory و تعداد modeها را تغییر دهد، بنابراین در مقایسه نتایج باید نوع kernel ثبت شود.

12.3.Seed strategy

استفاده از همه داده‌ها به‌عنوان seed دقت پوشش خوبی دارد ولی گران است. bin seeding، sampling یا seedهای density-aware می‌توانند هزینه را کاهش دهند. با این حال، حذف seed در یک ناحیه کوچک ممکن است مُد کم‌حجم را از دست بدهد.

12.4.Tolerance

آستانه همگرایی عددی تعیین می‌کند حرکت چه زمانی «به اندازه کافی کوچک» تلقی شود. tolerance بزرگ‌تر سرعت را افزایش می‌دهد اما نقاط پایانی را خشن‌تر می‌کند؛ tolerance کوچک‌تر محاسبه بیشتری می‌طلبد.

12.5.Max iterations

حداکثر تکرار یک محدودیت ایمنی برای مسیرهایی است که کند حرکت می‌کنند یا به tolerance تعیین‌شده نمی‌رسند. در مستندات فعلی scikit-learn مقدار پیش‌فرض max_iter=300 است. این عدد نتیجه نظری Mean Shift نیست و صرفاً قرارداد نرم‌افزاری است (scikit-learn Developers, 2026b).

12.6.Mode merging threshold

پس از همگرایی seedها، نقاط پایانی بسیار نزدیک باید ادغام شوند. آستانه ادغام باید در نسبت با bandwidth و scale داده انتخاب شود. نبود قاعده یکتا برای این مرحله یکی از دلایل تفاوت خروجی پیاده‌سازی‌هاست.

.

13. مزایا

• عدم نیاز به تعیین مستقیم تعداد خوشه‌ها: تعداد مُدها از ساختار KDE نتیجه می‌شود، هرچند به bandwidth وابسته است.
• ناپارامتری بودن: نیاز به فرض مستقیم توزیع Gaussian mixture یا شکل پارامتری مشخص ندارد.
• تفسیر مبتنی بر چگالی: خوشه‌ها با ساختار مُدهای فضای ویژگی مرتبط‌اند.
• انعطاف در هندسه خوشه: نسبت به k-means به ساختارهای غیربال‌مانند انعطاف بیشتری دارد، مشروط بر اینکه KDE آن‌ها را به مُدهای مناسب تفکیک کند.
• اتصال نظری غنی: با KDE، gradient ascent، bound optimization و در نسخه Gaussian با EM ارتباط دارد.
• عدم نیاز به initialization تعداد K centroid: seedها می‌توانند از خود داده انتخاب شوند.
• کاربردپذیری در بینایی ماشین: filtering، segmentation و tracking از کاربردهای کلاسیک و اثرگذار آن‌اند.
• قابلیت توسعه: kernel، bandwidth، metric، seed strategy و فضای داده قابل تغییرند و واریانت‌های متعددی بر همین مبنا ساخته شده‌اند.
• .

14. محدودیت‌ها و معایب

• حساسیت شدید به bandwidth؛
• هزینه محاسباتی بالا در نسخه مستقیم؛
• ضعف KDE در ابعاد بالا؛
• کاهش کارایی ساختارهای همسایگی در ابعاد زیاد؛
• احتمال ایجاد spurious mode با bandwidth کوچک؛
• احتمال ادغام خوشه‌های کوچک با bandwidth بزرگ؛
• دشواری استفاده از bandwidth واحد برای چگالی‌های بسیار متفاوت؛
• نبود سازوکار ذاتی و صریح برای برچسب noise مانند DBSCAN؛
• حساسیت به scale ویژگی‌ها؛
• وابستگی نتیجه به kernel و سیاست mode merging؛
• نبود پشتیبانی بومی برای داده missing یا categorical در نسخه اقلیدسی پایه؛
• مساوی نبودن مُد آماری با کلاس معنایی؛
• شرط‌دار بودن نتایج همگرایی؛
• هزینه بالقوه بالای bandwidth estimation؛
• تفاوت رفتار پیاده‌سازی‌های flat-kernel و Gaussian-kernel حتی با مقادیر ظاهراً مشابه bandwidth.

.

15. کاربردها و موارد استفاده

15.1 پردازش تصویر و قطعه‌بندی

یکی از مهم‌ترین کاربردهای تاریخی Mean Shift، تحلیل فضای ویژگی تصاویر است. رنگ و مختصات مکانی می‌توانند در یک فضای مشترک تعریف شوند و حرکت Mean Shift نواحی مشابه را به نقاط پرتراکم ببرد. Comaniciu و Meer filtering و segmentation را در همین چارچوب نشان دادند (Comaniciu & Meer, 2002).

15.2 رهگیری شیء

در رهگیری مبتنی بر histogram/backprojection، Mean Shift برای یافتن مُد توزیع احتمال مکانی استفاده می‌شود. نسخه CamShift نیز اندازه پنجره را تطبیق می‌دهد. OpenCV این جریان کاری را در مستندات رسمی خود نگه داشته است (OpenCV, 2026).

15.3 تحلیل بافت و فضای ویژگی پُربعد

Georgescu، Shimshoni و Meer استفاده از Mean Shift را در بافت و ابعاد بالا بررسی کردند و برای کاهش هزینه از locality-sensitive hashing بهره گرفتند (Georgescu et al., 2003).

15.4 داده‌های بزرگ و توزیع‌شده

نسخه‌های Stochastic Approximation و Distributed Approximate Mean Shift برای کاهش هزینه در داده‌های بزرگ توسعه یافته‌اند. Hyrien و Baran نسخه stochastic approximation و Beck و همکاران ساختار distributed مبتنی بر approximate nearest neighbors را مطالعه کردند (Hyrien & Baran, 2016; Beck et al., 2019).

15.5 داده‌های تابعی

واریانت‌های جدید Mean Shift، داده‌های تابعی ناهمتراز و فضاهای quotient را هدف قرار داده‌اند. Welbaum و Qiao الگوریتم را با elastic distance برای این نوع داده توسعه دادند. این کاربرد به نسخه تخصصی مربوط است و نباید مستقیماً به الگوریتم اقلیدسی پایه تعمیم داده شود.

15.6 یادگیری بازنمایی و کشف دسته‌های جدید

Contrastive Mean-Shift در CVPR 2024 Mean Shift را در حلقه یادگیری بازنمایی برای Generalized Category Discovery به کار گرفت. این کاربرد نشان‌دهنده نقش Mean Shift در فضای embedding آموخته‌شده است، نه شواهدی برای برتری عمومی Mean Shift کلاسیک در داده خام (Choi et al., 2024).

.

16. مقایسه با الگوریتم‌های مشابه

روش	ساختار اصلی	نیاز به تعداد خوشه	پارامتر حساس اصلی	مزیت نسبی	محدودیت نسبی
Mean Shift	مُدهای KDE و حوزه جذب	خیر، به‌صورت صریح	bandwidth	تفسیر چگالی و mode seeking	هزینه بالا و حساسیت به bandwidth
k-means	کمینه‌سازی SSE پیرامون centroidها	بله	K و initialization	سریع و ساده	ترجیح خوشه‌های نسبتاً کروی
GMM/EM	مدل mixture احتمالاتی	معمولاً بله	K و covariance model	احتمال و عدم‌قطعیت صریح	فرض پارامتری
DBSCAN	اتصال چگالی	خیر	eps و min_samples	noise صریح و شکل‌های اتصال‌محور	حساسیت به چگالی متغیر
HDBSCAN	سلسله‌مراتب چگالی	خیر	min_cluster_size و پارامترهای مرتبط	چگالی چندمقیاسی و noise	تفسیر متفاوت از mode clustering
Spectral Clustering	گراف شباهت و eigenvectors	معمولاً بله	graph scale و K	مرزهای غیرخطی	هزینه ماتریسی و نیاز به K
Affinity Propagation	تبادل پیام و exemplar	خیر، صریح	preference/damping	انتخاب exemplar واقعی	هزینه و حساسیت به similarity
Quick Shift	ساخت درخت به نقاط با چگالی بیشتر	خیر	kernel/threshold	mode seeking سریع‌تر در برخی کاربردها	trajectory متفاوت از Mean Shift

Mean Shift16.1. در برابر k-means

k-means یک تابع هدف مشخص مبتنی بر مجموع مربعات فاصله دارد و K را از پیش نیاز دارد. Mean Shift K را مستقیماً نمی‌گیرد و ساختار را از مُدهای KDE استخراج می‌کند. در داده‌های بزرگ با K معلوم، k-means غالباً محاسباتی‌تر است. در مسائل mode seeking یا زمانی که تفسیر چگالی اهمیت دارد، Mean Shift مزیت مفهومی بیشتری دارد.

Mean Shift.16.2 در برابر DBSCAN/HDBSCAN

DBSCAN خوشه را به‌صورت ناحیه متصل چگال تعریف می‌کند و noise را صریحاً جدا می‌کند؛ Mean Shift خوشه را از حوزه جذب مُدها می‌سازد. بنابراین دو روش حتی اگر هر دو «density-based» نامیده شوند، تعریف خوشه یکسانی ندارند. برای داده با چگالی بسیار متغیر و نیاز به noise labeling، HDBSCAN ممکن است مناسب‌تر باشد؛ برای تحلیل مستقیم مُدهای چگالی و trajectory، Mean Shift طبیعی‌تر است.

.

17. گونه‌ها، توسعه‌ها و نوآوری‌ها

17.1.Gaussian Mean Shift

صورت کلاسیک smooth با Gaussian kernel که پیوند نظری روشنی با KDE و EM دارد (Carreira-Perpiñán, 2007).

17.2.Flat-Kernel Mean Shift

میانگین یکنواخت نمونه‌های داخل شعاع bandwidth؛ پیاده‌سازی scikit-learn بر این مبناست.

17.3.Blurring Mean Shift

به‌جای ثابت‌بودن داده، خود نقاط در هر دور به میانگین‌های محلی منتقل می‌شوند. Carreira-Perpiñán نسخه Gaussian Blurring Mean Shift را از نظر سرعت و clustering بررسی کرده است (Carreira-Perpiñán, 2006a).

17.4 Variable-Bandwidth و Adaptive Mean Shift

برای سازگاری با چگالی‌های ناهمگن، bandwidth می‌تواند با موقعیت یا نمونه تغییر کند. این مسیر مشکل «یک scale برای کل داده» را هدف قرار می‌دهد، ولی انتخاب و تحلیل bandwidth محلی پیچیده‌تر است.

17.5 Medoid Shift و Quick Shift

در Medoid Shift، نقاط نماینده به نمونه‌های واقعی محدود می‌شوند. Quick Shift نیز برای mode seeking یک ساختار درختی به سمت نقاط چگال‌تر می‌سازد (Vedaldi & Soatto, 2008).

17.6.Stochastic Approximation Mean Shift

Hyrien و Baran با استفاده از subsampling و stochastic approximation هزینه محاسبات را کاهش دادند و نتایج همگرایی را تحت شروط مربوط بررسی کردند (Hyrien & Baran, 2016).

 17.7.Distributed / Approximate Mean Shift

Beck و همکاران از approximate nearest neighbors و محاسبات توزیع‌شده برای داده مقیاس بزرگ استفاده کردند (Beck et al., 2019).

17.8.MeanShift++

Jang و Jiang در CVPR 2021 الگوریتم grid-based سریعی برای mode seeking معرفی کردند. مزیت اصلی آن کاهش وابستگی زمانی به تعداد نمونه‌ها در داده کم‌بُعد است، ولی وابستگی به dimension به گونه‌ای است که نباید مزیت آن به فضاهای پُربعد تعمیم داده شود (Jang & Jiang, 2021).

17.9.Subspace Constrained Mean Shift

SCMS به‌جای جست‌وجوی مُدهای صفر‌بُعدی، برای برآورد density ridge استفاده می‌شود. هدف هندسی این روش متفاوت است و نباید صرفاً «Mean Shift بهتر برای clustering» معرفی شود.

17.10 Mean Shift در manifold و functional data

با جایگزینی فاصله، میانگین و عملیات اقلیدسی با ساختار مناسب manifold می‌توان Mean Shift را به فضاهای غیرخطی توسعه داد. پژوهش‌های جدید داده تابعی نیز از elastic distance و quotient space استفاده کرده‌اند (Welbaum & Qiao, 2025).

17.11 روندهای ۲۰۲۲ تا ۲۰۲۶

بر پایه بانک دانش مرحله ۱ و راستی‌آزمایی در ۸ اوت ۲۰۲۶، پژوهش جدید در چهار جهت اصلی دیده می‌شود: پیوند با representation learning، داده‌های functional/manifold، stochastic/scalable mode seeking و تحلیل نظری density ridge. Contrastive Mean-Shift در CVPR 2024 نمونه‌ای peer-reviewed از ترکیب Mean Shift با contrastive learning است (Choi et al., 2024) و روش Welbaum و Qiao (2025) توسعه peer-reviewed برای داده تابعی ناهم‌تراز است. در مقابل، Stochastic Mean-Shift Clustering (Lapidot et al., 2025)، Doubly Stochastic Mean-Shift Clustering (Trigano et al., 2026) و Stable Density Ridges برای SCMS (Qiao, 2026) در تاریخ ممیزی همچنان preprint هستند؛ بنابراین نتایج آن‌ها باید با برچسب شواهد اولیه و بدون تعمیم به Mean Shift کلاسیک نقل شوند.

17.12 جهت‌گیری‌های آینده

• انتخاب خودکار و پایدار bandwidth؛
• bandwidth تطبیقی و چندمقیاسی؛
• approximate nearest-neighbor و GPU acceleration؛
• Mean Shift در embeddingهای آموخته‌شده؛
• نسخه‌های differentiable برای معماری‌های عمیق؛
• streaming و concept-drift-aware Mean Shift؛
• robust kernels و کاهش حساسیت به outlier؛
• mode persistence در scale-space؛
• نسخه‌های manifold، graph و functional-data؛
• مدل‌های uncertainty-aware برای مُدها و حوزه‌های جذب.

.

18. جمع‌بندی، نکات کلیدی و سنجش یادگیری

18.1 جمع‌بندی فصل

Mean Shift یک الگوریتم mode seeking مبتنی بر تخمین چگالی هسته‌ای است که ساختار خوشه‌ای را از مُدهای چگالی و حوزه‌های جذب آن‌ها استخراج می‌کند. هسته محاسباتی روش، انتقال تکراری seed به میانگین وزن‌دار محلی است. این حرکت تحت صورت‌بندی استاندارد با جهت گرادیان KDE مرتبط است؛ بنابراین می‌توان Mean Shift را نوعی صعود تطبیقی چگالی دانست.

مهم‌ترین نکته عملی و نظری الگوریتم bandwidth است. bandwidth کوچک ساختار محلی ریز و مُدهای بیشتر ایجاد می‌کند، در حالی‌که bandwidth بزرگ ساختار را هموار و مُدها را ادغام می‌کند. از این رو، Mean Shift بدون K صریح عمل می‌کند، اما «بدون پارامتر» نیست. تعداد خوشه‌های نهایی به scale انتخاب‌شده وابسته است.

از نظر محاسباتی، نسخه naïve با seed برای همه نمونه‌ها می‌تواند هزینه‌ای در حد O(TN²d) داشته باشد. این محدودیت همراه با curse of dimensionality باعث شده است واریانت‌های stochastic، approximate، distributed و grid-based توسعه یابند. همچنین نتایج همگرایی باید با فرض‌های مربوط بیان شوند و ادعای همگرایی عمومی بدون شرط علمی نیست.

18.2 نکات کلیدی برای مرور سریع

• ریشه ریاضی Mean Shift: Fukunaga & Hostetler (1975).
• صورت‌بندی mode seeking و clustering: Cheng (1995).
• چارچوب استاندارد مدرن: Comaniciu & Meer (2002).
• Mean Shift بر KDE تکیه دارد.
• بردار Mean Shift = میانگین وزن‌دار محلی منهای نقطه جاری.
• bandwidth مهم‌ترین ابرپارامتر است.
• تعداد خوشه ورودی مستقیم نیست، ولی به bandwidth وابسته است.
• Gaussian و flat kernel می‌توانند رفتار متفاوتی ایجاد کنند.
• حوزه جذب مُدها پایه تفسیر modal clustering است.
• mode merging مرحله اجرایی مهمی است.
• convergence نتایج شرط‌دار دارد.
• نسخه naïve برای داده بزرگ گران است.
• ابعاد بالا برای KDE و جست‌وجوی همسایگی چالش‌برانگیزند.

18.3 پرسش‌های مفهومی

1. چرا Mean Shift را نمی‌توان صرفاً k-means بدون K دانست؟
2. رابطه Mean Shift و KDE چیست؟
3. چرا bandwidth تعداد خوشه‌های خروجی را تحت تأثیر قرار می‌دهد؟
4. تفاوت mode و centroid را توضیح دهید.
5. چرا نتیجه scikit-learn MeanShift ممکن است با Gaussian Mean Shift متفاوت باشد؟
6. منظور از basin of attraction چیست؟
7. چرا ادعای همگرایی بدون شرط برای Mean Shift نادرست است؟
8. Mean Shift و DBSCAN چگونه تعریف متفاوتی از خوشه ارائه می‌کنند؟

18.4 تمرین‌های محاسباتی و تحلیلی

1. مثال X={0,1,4} را برای h=0.5 و h=5 محاسبه کنید و جهت جابه‌جایی seed را مقایسه کنید.
2. برای یک داده دوبعدی دوخوشه‌ای، مسیر چند seed را روی کاغذ یا نرم‌افزار رسم و نقطه همگرایی را مشخص کنید.
3. هزینه زمانی Mean Shift را وقتی تنها S=sqrt N seed استفاده می‌شود، بر حسب N,d,T استخراج کنید.
4. نشان دهید چگونه تغییر مقیاس یک ویژگی می‌تواند همسایگی kernel و در نتیجه مسیر Mean Shift را تغییر دهد.
5. برای یک مجموعه داده با خوشه کوچک کنار خوشه بزرگ، توضیح دهید چرا یک bandwidth ثابت ممکن است برای هر دو نامناسب باشد.

18.5 پروژه یا سناریوی پیشنهادی

یک مجموعه داده دوبعدی شامل سه ناحیه با چگالی‌های متفاوت ایجاد کنید. Mean Shift را در چند bandwidth اجرا و تعداد مُدها، پایداری مراکز و شاخص silhouette را ثبت کنید. سپس نتایج را با DBSCAN و k-means مقایسه کنید. هدف پروژه یافتن «برنده» نیست؛ بلکه تحلیل تفاوت تعریف خوشه، حساسیت پارامتر و ساختار هندسی خروجی است.

18.6 پیشنهاد شکل‌های فصل

• KDE یک‌بعدی و نمایش مُدها؛
• بردار Mean Shift روی منحنی چگالی؛
• چند trajectory که به یک مُد می‌رسند؛
• حوزه‌های جذب چند مُد در دوبعد؛
• مقایسه bandwidth کوچک، متوسط و بزرگ؛
• مقایسه Gaussian و flat kernel؛
• شمای mode merging؛
• نمودار هزینه زمانی بر حسب ؛
• مقایسه مفهومی Mean Shift، k-means و DBSCAN؛
• نمودار تعداد مُدها بر حسب bandwidth.

.

19. منابع

Beck, G., Duong, T., Lebbah, M., Azzag, H., & Cérin, C. (2019). A distributed approximate nearest neighbors algorithm for efficient large scale mean shift clustering. Journal of Parallel and Distributed Computing, 134, 128–139. https://doi.org/10.1016/j.jpdc.2019.07.015

Carreira-Perpiñán, M. Á. (2006a). Fast nonparametric clustering with Gaussian blurring mean-shift. In Proceedings of the 23rd International Conference on Machine Learning (pp. 153–160). https://doi.org/10.1145/1143844.1143864

Carreira-Perpiñán, M. Á. (2007). Gaussian mean-shift is an EM algorithm. IEEE Transactions on Pattern Analysis and Machine Intelligence, 29(5), 767–776. https://doi.org/10.1109/TPAMI.2007.1057

Chen, Y.-C., Genovese, C. R., & Wasserman, L. (2016). A comprehensive approach to mode clustering. Electronic Journal of Statistics, 10(1), 210–241. https://doi.org/10.1214/15-EJS1102

Cheng, Y. (1995). Mean shift, mode seeking, and clustering. IEEE Transactions on Pattern Analysis and Machine Intelligence, 17(8), 790–799. https://doi.org/10.1109/34.400568

Choi, S., Kang, D., & Cho, M. (2024). Contrastive Mean-Shift Learning for Generalized Category Discovery. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (pp. 23094–23104).

Comaniciu, D., & Meer, P. (2002). Mean shift: A robust approach toward feature space analysis. IEEE Transactions on Pattern Analysis and Machine Intelligence, 24(5), 603–619. https://doi.org/10.1109/34.1000236

Fashing, M., & Tomasi, C. (2005). Mean shift is a bound optimization. IEEE Transactions on Pattern Analysis and Machine Intelligence, 27(3), 471–474. https://doi.org/10.1109/TPAMI.2005.59

Fukunaga, K., & Hostetler, L. D. (1975). The estimation of the gradient of a density function, with applications in pattern recognition. IEEE Transactions on Information Theory, 21(1), 32–40. https://doi.org/10.1109/TIT.1975.1055330

Georgescu, B., Shimshoni, I., & Meer, P. (2003). Mean shift based clustering in high dimensions: A texture classification example. In Proceedings of the IEEE International Conference on Computer Vision (pp. 456–463). https://doi.org/10.1109/ICCV.2003.1238382

Ghassabeh, Y. A. (2013). On the convergence of the mean shift algorithm in the one-dimensional space. Pattern Recognition Letters, 34(12), 1423–1427. https://doi.org/10.1016/j.patrec.2013.05.004

.

Ghassabeh, Y. A. (2015). A sufficient condition for the convergence of the mean shift algorithm with Gaussian kernel. Journal of Multivariate Analysis, 135, 1–10. https://doi.org/10.1016/j.jmva.2014.11.009

Hyrien, O., & Baran, A. (2016). Fast nonparametric density-based clustering of large data sets using a stochastic approximation mean-shift algorithm. Journal of Computational and Graphical Statistics, 25(3), 899–916. https://doi.org/10.1080/10618600.2015.1051625

Jang, J., & Jiang, H. (2021). MeanShift++: Extremely fast mode-seeking with applications to segmentation and object tracking. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (pp. 4102–4113).

Lapidot, I., Sepulcre, Y., & Trigano, T. (2025). Stochastic Mean-Shift Clustering. arXiv preprint arXiv:2511.09202. https://arxiv.org/abs/2511.09202

Li, X., Hu, Z., & Wu, F. (2007). A note on the convergence of the mean shift. Pattern Recognition, 40(6), 1756–1762. https://doi.org/10.1016/j.patcog.2006.10.016

OpenCV. (2026). Meanshift and Camshift. OpenCV 4.x documentation. https://docs.opencv.org/4.x/d7/d00/tutorial_meanshift.html

Qiao, W. (2026). Stable Density Ridges: Consistency and Convergence of Subspace Constrained Mean Shift. arXiv preprint arXiv:2608.05112. https://arxiv.org/abs/2608.05112

scikit-learn Developers. (2026a). estimate_bandwidth. scikit-learn 1.9.0 documentation. https://scikit-learn.org/stable/modules/generated/sklearn.cluster.estimate_bandwidth.html

scikit-learn Developers. (2026b). MeanShift. scikit-learn 1.9.0 documentation. https://scikit-learn.org/stable/modules/generated/sklearn.cluster.MeanShift.html

Trigano, T., Sepulcre, Y., & Lapidot, I. (2026). Doubly Stochastic Mean-Shift Clustering. arXiv preprint arXiv:2602.15393. https://arxiv.org/abs/2602.15393

Vedaldi, A., & Soatto, S. (2008). Quick shift and kernel methods for mode seeking. In European Conference on Computer Vision (pp. 705–718). https://doi.org/10.1007/978-3-540-88693-8_52

Welbaum, A., & Qiao, W. (2025). Mean shift-based clustering for misaligned functional data. Computational Statistics & Data Analysis, 206, 108107. https://doi.org/10.1016/j.csda.2024.108107