مبتدی (مناسب برای درک مفهوم کلی مطلب) 

الگوریتم انتقال میانگین اساساً یک الگوریتم تپه‌نوردی است؛ یعنی الگوریتم انتقال میانگین که از هر نقطه x شروع می‌شود، یک الگوی توالی ضروری است که را به بالای تپه KDE برده و در نهایت در بیشینه (یا مد) موضعی KDE متوقف می‌شود که حوزه مطلوب x در آن واقع شده است. برای تعیین توالی انتقال میانگین، شکل کرنل را به وصرت صریح ساده نموده و شکل تقارن شعاعی K(x)=ck(‖z‖^۲ ) را بدست می‌آوریم که k در آن، پروفایلی یک بعدی همانند پروفایل‌های گاوسین یک بعدی، یکنواخت یا اپانچنیکوف بوده و c یک بهنجارش می‌باشد. با قرار دادن علامت g=k’، توالی انتقال میانگین به صورت زیر در می‌آید برای آوردن x به مدی که حوزه مطلوب در آن واقع می‌باشد، فرایند تکرار تعدادی نامتناهی از زمان‌ها تضمین شده است. مزیت این روش بر روش صعود گرادیانی عادی، عدم نیاز به مجموعه پارامتر گام زمانی است (شایان ذکر است که چنین پارامتری در عبارت بالا وجود ندراد)؛ از لحاظ عملی، انتقال میانگین در تعداد گام‌های بسیار کوچک که معمولاً در حدود ۵ می‌باشد، همگرا می‌گردد.
برای استفاده از الگوریتم انتقال میانگین برای قطعه‌بندی یا خوشه‌بندی در مجموعه {x_i }_(i=1)^n، می‌توان فرایند تکرار را از هر نقطه داده آغاز نمود. با قرار دادن M^1 (x)=M(x)، M^2 (x)=M(M(x)) و غیره، هر نقطه x_i را در M^∞ (x_i ) می‌نگاریم (خاطرنشان می‌نماییم که معمولاً M^5 (x_i ) این کار را انجام خواهد داد). از آنجا که تعداد مدها از تعداد نقاط بسیار کمتر می‌باشند بنابراین شکلی از قطعه‌بندی یا خوشه‌بندی وجود دارد که در عمل در تعدادی از کاربردها بسیار خوب عمل می‌نمایند [۲۰، ۶، ۱۴].

۲٫ ۲٫ KDE متراکم‌تر: مسئله
بدون محاسبه صریح پیچیدگی خوشه‌بندی انتقال میانگین (بحث در خصوص این تمرین را به بخش ۲٫ ۵ موکول می‌نماییم)، خاطرنشان می‌نماییم که زمان اجرا در n، تعداد نقاط داده‌ای ابرخطی خواهد بود. اگر با تصاویر بزرگی که از دوربین‌های روزانه حاصل می‌شوند سر و کار داشته باشیم آنگاه n به سادگی در محدوده ۱۰۷ می‌باشند. اما موضوع ناگوار آن است که گاهی اوقات علاقمندیم تا از روش انتقال میانگین برای ویدیوها و یا در تصویرسازی سه بعدی همچون تصاویر CT یا MRI استفاده نماییم؛ در این حالت، n از مرتبه ۱۰۸ یا بالاتر نیز به سادگی قابل انتظار خواهد بود. بنابراین بهتر آن است که روش انتقال میانگین سریع استفاده نماییم. یکی از تنگناهای اصلی فراروی سرعت، پیچیدگی توصیف KDE است که O(n) می‌باشد؛ بنابراین با بررسی مسئله یافتن توصیفی متراکم‌تر برای KDE، کار خود را آغاز می‌نماییم.

گزینه‌های طبیعی مختلفی برای مقیاس فاصله D، از فواصل L_p گونه گرفته تا مقیاس‌های نظری با اطلاعات بیشتری همچون واگرایی کولبک- لیبلر وجود دارند. در تمامی این حالت‌ها، به طور کلی حل مسئله بهینه‌سازی حاصل کار دشواری است؛ این موضوع ناشی از این حقیقت است که x ̂_j در کرنل K ظاهر می‌گردد که به بهینه‌سازی غیرمحدب منجر شده و راه‌حل‌های کلی موثری را نمی‌توان برای آن یافت. با این وجود f و f ̂ چیزی بیشتر از تابع می‌باشند؛ هر دو آنها چگالی بوده و این حقیقت، ابزاری برای یافتن راه‌حلی موثر جهت مسئله نمایش تراکم را برای ما فراهم می‌آورد.

۳٫ ۲٫ KDE متراکم‌تر از طریق نمونه‌برداری
راه‌حل ارائه شده ما بسیار ساده می‌باشد: با نمونه‌برداری از توزیع داده شده با f(.)، نمونه‌های موردنظر x ̂_j خود را انتخاب می‌نماییم. قبل از پرداختن به منطق این روش، خاطرنشان می‌نماییم که این نمونه‌برداری به صورت کلی امکان‌پذیر بوده و می‌توان آن را به عنوان یک روش سه مرحله‌ای به اجرا درآورد:
قضیه ۱٫ برای هر j=1,…,m، فرض می‌کنیم که x ̂_j به صورت زیر ساخته می‌شود:
۱٫ عدد صحیح r_j∈{۱,…,n} را به صورت تصادفی انتخاب می‌نماییم.
۲٫ نمونه تصادفی δ_j را از K(.) انتخاب می‌کنیم.
۳٫ x ̂_j=x_(r_j )+H^(1⁄۲) δ_j را قرار می‌دهیم.
بنابراین x ̂_j، نمونه مناسبی از f می‌باشد.
اثبات: مرجع [۹] را ملاحظه نمایید.
مادامی که می‌توان نمونه را به سادگی از K(.) ساده‌سازی نمود (همانند آنچه که در حالت‌های موجود برای کرنل‌های گاوسین، یکنواخت و اپانچنیکوف بود)، روش مورد نظر بسیار ساده خواهد بود.
اکنون، سئوال اصلی این است: اگر KDE f ̂ مبتنی بر نمونه‌های تصادفی x ̂_j را بسازیم آیا به KDE واقعی نزدیک خواهند بود یا خیر؟ البته KDE f ̂ به خودی خود، متغیری تصادفی است (یعنی یک تابع تصادفی) و بنابراین هر نتیجه‌ای که به دنبال اثبات آن باشیم، ماهیتی احتمالی خواهند داشت. در حقیقت نتیجه زیر را داریم که مطابق انتظار، نزدیک بودن f و f ̂ در یک حس یا مفهوم L_2 را تضمین می‌نماید:
قضیه ۲٫ همانند آنچه که در بالا بود f، KDE با n نقطه و f ̂، KDE ایجاد شده با روش نمونه‌برداری m بار از f را در نظر گرفته و ماتریس پهنای باند قطری H ̂=h ̂^۲ I را مدنظر قرار می‌دهیم. فاصله مربعی چشم‌انتظاری L_2 بین دو چگالی را در رابطه J=E[∫▒(f(x)-f ̂(x))^2 dx] در نظر می‌گیریم. بنابراین

که در آن A، B و V ثابت‌هایی هستند که به h ̂ یا m بستگی ندارند.
اثبات: مرجع [۹] را ملاحظه نمایید.
معنی این قضیه بسیار سرراست است: دو KDE، f و f ̂ (مطابق انتظار) نزدیک خواهند بود اگر m به اندازه کافی بزرگ بوده و پهنای باند h ̂ به صورت مناسب به عنوان تابعی از m انتخاب شده باشد. این دقیقاً همان چیزی است که در نمایش تراکم به دنبال آن می‌باشیم: پیچیدگی توصیف KDE از O(n) به O(m) کاهش یافته است اما در حس L_2 مورد انتظار، مقداری نزدیک به همان چگالی ایجاد نموده‌ایم.
به مسئله انتخاب پهنای باند در بخش ۲٫ ۷ برمی‌گردیم؛ در بخش بعدی، به مسئله حساس نحوه استفاده از نمایش KDE کاهیده خود در خوشه‌بندی انتقال میانگین باز خواهیم گشت.

۲٫۴٫ انتقال میانگین سریع
چگونه می‌توان KDE با تراکم بیشتر خود را الگوریتم خوشه‌بندی انتقال میانگین گنجاند؟ از روش سه مرحله‌ای زیر استفاده می‌کنیم:
۱٫ نمونه‌برداری: m نمونه از چگالی f را در نظر می‌گیریم تا {x ̂_j }_(i=1)^m را بدست آوریم. چگالی جدید f ̂(x)=∑_(j=1)^m▒〖K_h ̂ (x,x ̂_j ) 〗 را تشکیل می‌دهیم.
۲٫ انتقال میانگین: روش انتقال میانگین را بر روی هر m نمونه به اجرا درمی‌آوریم: x ̂_j→M ̂^∞ (x ̂_j ). در اینجا، M ̂ حاکی از آن است که از f ̂ (به جای f) برای انتقال میانگین استفاده نموده‌ایم.
۳٫ نگاشت رو به عقب: برای هر x_i، نزدیک‌ترین نمونه جدید x ̂_(j^* ) را می‌یابیم. بنابراین x_i→M ̂^∞ (x ̂_(j^* ) ).
در مرحله ۱، KDE کاهیده را ساخته و در مرحله ۲، انتقال میانگین را بر روی این KDE کوچکتر به اجرا درمی‌آوریم. با تعیین این مدها در KDE کاهیده، مسئله موجود همانا نگاشت رو به عقب به سمت داده‌های اصلی است. در مرحله ۳، با نگاشت از هر نقطه در داده‌های اصلی (x_i) به نزدیک‌ترین نقطه در داده‌های کاهیده (x ̂_(j^* )) و از آنجا به مدی که در آن نقطه جریان می‌یابد (M ̂^∞ (x ̂_(j^* ) ))، مواجه می‌باشیم.
افزایش سرعت اصلی در مرحله دوم رخ می‌دهد؛ به جای استفاده از تمامی m نمونه جهت محاسبه انتقال میانگین می‌توان از مجموعه کاهش‌یافته‌ای از m نمونه استفاده نمود. در بخش بعدی، افزایش سرعت نظری دقیقت که این روش در پی دارد را به صورت کیفی مورد بررسی قرار خواهیم داد؛ در اینجا خاطرنشان می‌شود که اجرای فرایند به صورت ساده می‌تواند به افزایش سرعت n/m منتهی می‌شود که در عمل می‌تواند از مرتبه ۱۰۰ بزرگتر و حتی خیلی بیشتر از آن نیز برود.

۲٫۵٫ تحلیل پیچیدگی
جنبه کلیدی موجود در محاسبه پیچیدگی، سرعت جستجوی نزدیک‌ترین همسایه است. شایان ذکر است که در تکرار روش انتقال میانگین، معادله (۱) را ملاحظه نمایید)، باید نزدیک‌ترین همسایه‌های n نمونه x_i به نقطه موردنظر، x، را محاسبه نمود. فرض کنید که ساختار داده‌ای را داریم که امکان جستجوی نزدیک‌ترین همسایه در زمان q(n) را داده و به زمان پردازش p(n) جهت محاسبه نیازمند می‌باشد؛ به طور خلاصه به نمونه‌هایی از این ساختارها خواهیم پرداخت اما در اینجا فعلاً آنها را باقی خواهیم گذاشت. در این حالت، هر تکرار فرایند انتقال میانگین به زمان O(q(n)) جهت محاسبه نیاز دارد؛ و فرض می‌کنیم (که در عمل هم صادق می‌باشد) که تکرارهای O(1) برای همگرایی لازم می‌باشند، بنابراین هزینه اجرای الگوریتم بر روی تمامی n نقطه داده (یعنی الگوریتم کاهش کلی داده‌ها) به صورت زیر خواهد بود

الگوریتم پیشنهادی ما چقدر سریع‌تر است؟ به بخش ۲٫ ۴ برگشته و پیچیدگی مربوط به هر مرحله را تفکیک می‌کنیم. مرحله ۱، مرحله نمونه‌برداری، O(m)، است. قبلاً پیچیدگی مرحله ۲، مرحله انتقال میانگین، را محاسبه نموده‌ایم؛ که دارای عبارت ساده بالا است اما این کار را به جای n نمونه برای m نمونه انجام می‌دهیم یعنی O(p(m)+mq(m)). در مرحله ۳، باید نگاشت رو به عقب را به اجرا درآوریم؛ یعنی برای هر n نمونه اصلی باید نزدیک‌ترین نقاط موجود m نمونه جدید را بیابیم. برای استفاده از ساختار داده‌های خود (که زمان پیش‌پردازش را قبلاً برای آن در مرحله ۲ به حساب آورده‌ایم)، به O(nq(m)) نیاز داریم. بنابراین مجموع موردنظر به صورت زیر می‌باشد