التحول المتوسط

يُعدّ إزاحة المتوسط ​​تقنية تحليل رياضي غير بارامترية في فضاء الميزات لتحديد القيم القصوى لدالة الكثافة ، وهي ما يُعرف بخوارزمية البحث عن النمط . ^{[ 1 ]} تشمل مجالات التطبيق تحليل التجمعات في رؤية الحاسوب ومعالجة الصور . ^{[ 2 ]}

عادة ما يُنسب إجراء تحويل المتوسط ​​إلى عمل فوكوناغا وهوستتلر في عام 1975. ^{[ 3 ]} ومع ذلك، فهو يذكرنا بعمل سابق لشنيل في عام 1964. ^{[ 4 ]}

إزاحة المتوسط ​​هي إجراء لتحديد القيم العظمى - أو الأنماط - لدالة الكثافة الاحتمالية، وذلك باستخدام بيانات منفصلة مأخوذة من تلك الدالة. ^{[ 1 ]} هذه طريقة تكرارية، ونبدأ بتقدير أولي.${\displaystyle x}$. لنفترض دالة النواة${\displaystyle K(x_{i}-x)}$يتم تحديد هذه الدالة. وتحدد وزن النقاط القريبة لإعادة تقدير المتوسط. وعادةً ما يتم استخدام نواة غاوسية على المسافة إلى التقدير الحالي.${\displaystyle K(x_{i}-x)=e^{-c||x_{i}-x||^{2}}}$المتوسط ​​المرجح للكثافة في النافذة المحددة بواسطة${\displaystyle K}$يكون

${\displaystyle m(x)={\frac {\sum _{x_{i}\in N(x)}K(x_{i}-x)x_{i}}{\sum _{x_{i}\in N(x)}K(x_{i}-x)}}}$

أين${\displaystyle N(x)}$هو حي${\displaystyle x}$، مجموعة من النقاط التي${\displaystyle K(x_{i}-x)\neq 0}$.

الفرق${\displaystyle m(x)-x}$يُطلق عليه اسم إزاحة المتوسط ​​في فوكوناغا وهوستتلر. ^{[ 3 ]} تقوم خوارزمية إزاحة المتوسط ​​الآن بضبط${\displaystyle x\leftarrow m(x)}$ويكرر التقدير حتى${\displaystyle m(x)}$يتقارب.

على الرغم من الاستخدام الواسع لخوارزمية إزاحة المتوسط ​​في العديد من التطبيقات، إلا أن برهانًا قاطعًا لتقارب هذه الخوارزمية باستخدام نواة عامة في فضاء عالي الأبعاد لا يزال غير معروف. ^{[ 5 ]} وقد أثبت علياري غسابه تقارب خوارزمية إزاحة المتوسط ​​في بُعد واحد باستخدام دالة ملف تعريف قابلة للتفاضل، ومحدبة، ومتناقصة تمامًا. ^{[ 6 ]} ومع ذلك، فإن حالة البُعد الواحد محدودة التطبيقات العملية. كما تم إثبات تقارب الخوارزمية في أبعاد أعلى مع عدد محدود من النقاط الثابتة (أو المعزولة). ^{[ 5 ] [ 7 ]} إلا أنه لم يتم تقديم شروط كافية لكي تحتوي دالة النواة العامة على عدد محدود من النقاط الثابتة (أو المعزولة).

خوارزمية إزاحة المتوسط ​​الغاوسي هي خوارزمية التوقع والتعظيم . ^{[ 8 ]}

لنفترض أن البيانات مجموعة منتهية${\displaystyle S}$مضمنة في${\displaystyle n}$الفضاء الإقليدي ذو الأبعاد n،${\displaystyle X}$. يترك${\displaystyle K}$لتكن نواة مسطحة تمثل الدالة المميزة لـ${\displaystyle \lambda }$الكرة في${\displaystyle X}$،

في كل تكرار للخوارزمية،${\displaystyle s\leftarrow m(s)}$يتم تنفيذه للجميع${\displaystyle s\in S}$في آنٍ واحد. إذن، السؤال الأول هو كيفية تقدير دالة الكثافة الاحتمالية بالنظر إلى مجموعة عينات متفرقة. إحدى أبسط الطرق هي تنعيم البيانات، على سبيل المثال، عن طريق دمجها مع نواة ثابتة العرض.${\displaystyle h}$،

أين${\displaystyle x_{i}}$هي عينات الإدخال و${\displaystyle k(r)}$هي دالة النواة (أو نافذة بارزن ).${\displaystyle h}$يُعدّ هذا المتغير هو المعامل الوحيد في الخوارزمية ويُسمى عرض النطاق. تُعرف هذه الطريقة بتقدير كثافة النواة أو تقنية نافذة بارزن. بمجرد حسابنا لـ${\displaystyle f(x)}$انطلاقًا من المعادلة أعلاه، يمكننا إيجاد قيمها القصوى المحلية باستخدام خوارزمية التدرج الصاعد أو أي تقنية تحسين أخرى. تكمن مشكلة هذا النهج "المباشر" في أنه يصبح حسابيًا مكلفًا للغاية في الأبعاد الأعلى.${\displaystyle f(x)}$على كامل مساحة البحث. بدلاً من ذلك، يستخدم تحويل المتوسط ​​صيغة معدلة لما يُعرف في أدبيات التحسين باسم هبوط التدرج متعدد إعادة التشغيل . بدءًا من تخمين ما للحد الأقصى المحلي،${\displaystyle y_{k}}$، والتي يمكن أن تكون نقطة بيانات إدخال عشوائية${\displaystyle x_{1}}$، يحسب متوسط ​​الإزاحة تدرج تقدير الكثافة${\displaystyle f(x)}$في${\displaystyle y_{k}}$ويتخذ خطوة صعبة في ذلك الاتجاه. ^{[ 9 ]}

تعريف النواة: ليكن${\displaystyle X}$كن${\displaystyle n}$الفضاء الإقليدي ذو الأبعاد n،${\displaystyle \mathbb {R} ^{n}}$. معيار${\displaystyle x}$هو عدد غير سالب،${\displaystyle \|x\|^{2}=x^{\top }x\geq 0}$دالة${\displaystyle K:X\rightarrow \mathbb {R} }$يُقال إنها نواة إذا كان هناك ملف تعريف لها ،${\displaystyle k:[0,\infty ]\rightarrow \mathbb {R} }$بحيث

${\displaystyle K(x)=k(\|x\|^{2})}$ و

• قيمة k غير سالبة.
• k غير متزايدة:${\displaystyle k(a)\geq k(b)}$لو${\displaystyle a<b}$.
• الدالة k متصلة على أجزاء و${\displaystyle \int _{0}^{\infty }k(r)\,dr<\infty \ }$

أكثر ملفين تعريف للنواة استخداماً في تحويل المتوسط ​​هما:

حبة مسطحة

نواة غاوس

حيث معامل الانحراف المعياري${\displaystyle \sigma }$يعمل كمعامل لعرض النطاق الترددي،${\displaystyle h}$.

1. يُعدّ تحويل المتوسط ​​أداة مستقلة عن التطبيق ومناسبة لتحليل البيانات الحقيقية.
2. لا يفترض أي شكل محدد مسبقًا على مجموعات البيانات.
3. وهو قادر على التعامل مع مساحات الميزات العشوائية.
4. يعتمد الإجراء على اختيار معيار واحد: عرض النطاق الترددي.
5. إن عرض النطاق/حجم النافذة 'h' له معنى مادي، على عكس k -means .

1. إن اختيار حجم النافذة ليس بالأمر البسيط.
2. قد يؤدي حجم النافذة غير المناسب إلى دمج الأوضاع، أو إنشاء أوضاع "سطحية" إضافية.
3. غالباً ما يتطلب ذلك استخدام حجم نافذة تكيفي.

يمكن العثور على نسخ مختلفة من الخوارزمية في حزم التعلم الآلي ومعالجة الصور:

• ELKI . أداة لاستخراج البيانات مكتوبة بلغة جافا، مزودة بالعديد من خوارزميات التجميع.
• برنامج ImageJ . تصفية الصور باستخدام مرشح إزاحة المتوسط.
• mlpack . تطبيق فعال قائم على خوارزمية الشجرة المزدوجة.
• يحتوي OpenCV على تطبيق لخوارزمية إزاحة المتوسط ​​عبر طريقة cvMeanShift
• مجموعة أدوات أورفيو . تطبيق بلغة C++.
• يستخدم تطبيق NumPy/Python في مكتبة scikit-learn شجرة الكرة للبحث الفعال عن النقاط المجاورة.

• DBSCAN
• خوارزمية البصريات
• تقدير كثافة النواة (KDE)
• النواة (الإحصائيات)