मीन शिफ्ट

मीन शिफ्ट एक गैर पैरामीट्रिक सुविधा स्थान है|घनत्व फ़ंक्शन की अधिकतमता का पता लगाने के लिए फ़ीचर-स्पेस गणितीय विश्लेषण तकनीक, एक तथाकथित मोड (सांख्यिकी)-चाहने वाला एल्गोरिदम। एप्लिकेशन डोमेन में कंप्यूटर दृष्टि और मूर्ति प्रोद्योगिकी में क्लस्टर विश्लेषण शामिल है।

इतिहास

औसत शिफ्ट प्रक्रिया का श्रेय आमतौर पर 1975 में फुकुनागा और होस्टेटलर द्वारा किए गए काम को दिया जाता है। हालाँकि, यह 1964 में श्नेल के पहले के काम की याद दिलाता है।

सिंहावलोकन

मीन शिफ्ट उस फ़ंक्शन से नमूना किए गए असतत डेटा को देखते हुए एक घनत्व फ़ंक्शन के मैक्सिमा - मोड (सांख्यिकी) - का पता लगाने की एक प्रक्रिया है।यह एक पुनरावृत्तीय विधि है, और हम प्रारंभिक अनुमान से शुरू करते हैं $x$. आइए एक कर्नेल (सांख्यिकी) $K(x_{i}-x)$ दिया जा। यह फ़ंक्शन माध्य के पुनः आकलन के लिए निकटवर्ती बिंदुओं का भार निर्धारित करता है। आमतौर पर वर्तमान अनुमान की दूरी पर एक रेडियल आधार फ़ंक्शन कर्नेल का उपयोग किया जाता है, $K(x_{i}-x)=e^{-c||x_{i}-x||^{2}}$. विंडो में घनत्व का भारित माध्य किसके द्वारा निर्धारित किया जाता है? $K$ है

$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)}}$

कहाँ $N(x)$ का पड़ोस है $x$, जिसके लिए अंकों का एक सेट $K(x_{i}-x)\neq 0$.

के अंतर $m(x)-x$ फुकुनागा और होस्टेटलर में माध्य बदलाव कहा जाता है। माध्य-शिफ्ट एल्गोरिथ्म अब सेट हो गया है $x\leftarrow m(x)$, और अनुमान को तब तक दोहराता है $m(x)$ जुटता है.

यद्यपि माध्य शिफ्ट एल्गोरिदम का व्यापक रूप से कई अनुप्रयोगों में उपयोग किया गया है, उच्च आयामी स्थान में सामान्य कर्नेल का उपयोग करके एल्गोरिदम के अभिसरण के लिए एक कठोर प्रमाण अभी भी ज्ञात नहीं है। अलियारी घासाबेह ने एक विभेदक, उत्तल और कड़ाई से घटते प्रोफ़ाइल फ़ंक्शन के साथ एक आयाम में माध्य शिफ्ट एल्गोरिदम के अभिसरण को दिखाया। हालाँकि, एक-आयामी मामले में वास्तविक दुनिया के अनुप्रयोग सीमित हैं। साथ ही, स्थिर (या पृथक) बिंदुओं की एक सीमित संख्या के साथ उच्च आयामों में एल्गोरिदम का अभिसरण साबित हुआ है। हालाँकि, सामान्य कर्नेल फ़ंक्शन के लिए परिमित स्थिर (या पृथक) बिंदु रखने के लिए पर्याप्त स्थितियाँ प्रदान नहीं की गई हैं।

गॉसियन मीन-शिफ्ट एक उम्मीद-अधिकतमकरण एल्गोरिथ्म है।

विवरण

मान लीजिए कि डेटा एक सीमित सेट है $S$ में सन्निहित है $n$-आयामी यूक्लिडियन अंतरिक्ष, $X$. होने देना $K$ एक सपाट कर्नेल हो जो कि का विशिष्ट कार्य है $\lambda$-बॉल इन $X$,

$K(x)={\begin{cases}1&{\text{if}}\ \|x\|\leq \lambda \\0&{\text{if}}\ \|x\|>\lambda \\\end{cases}}$

एल्गोरिथ्म के प्रत्येक पुनरावृत्ति में, $s\leftarrow m(s)$ सभी के लिए किया जाता है $s\in S$ इसके साथ ही। तो, पहला सवाल यह है कि नमूनों के विरल सेट को देखते हुए घनत्व फ़ंक्शन का अनुमान कैसे लगाया जाए। सबसे सरल तरीकों में से एक है डेटा को सुचारू बनाना, उदाहरण के लिए, इसे चौड़ाई के एक निश्चित कर्नेल के साथ जोड़कर $h$,

$f(x)=\sum _{i}K(x-x_{i})=\sum _{i}k\left({\frac {\|x-x_{i}\|^{2}}{h^{2}}}\right)$

कहाँ $x_{i}$ इनपुट नमूने हैं और $k(r)$ कर्नेल फ़ंक्शन (या पार्ज़ेन विंडो) है। $h$ एल्गोरिथम में एकमात्र पैरामीटर है और इसे बैंडविड्थ कहा जाता है। इस दृष्टिकोण को कर्नेल घनत्व अनुमान या पार्ज़ेन विंडो तकनीक के रूप में जाना जाता है। एक बार हमने गणना कर ली $f(x)$ उपरोक्त समीकरण से, हम ग्रेडिएंट एसेंट या किसी अन्य अनुकूलन तकनीक का उपयोग करके इसकी स्थानीय मैक्सिमा पा सकते हैं। इस क्रूर बल दृष्टिकोण के साथ समस्या यह है कि, उच्च आयामों के लिए, इसका मूल्यांकन करना कम्प्यूटेशनल रूप से निषेधात्मक हो जाता है $f(x)$ संपूर्ण खोज स्थान पर. इसके बजाय, मीन शिफ्ट एक प्रकार का उपयोग करता है जिसे अनुकूलन साहित्य में मल्टीपल रीस्टार्ट ग्रेडिएंट डिसेंट के रूप में जाना जाता है। स्थानीय अधिकतम के लिए कुछ अनुमान से प्रारंभ करते हुए, $y_{k}$, जो एक यादृच्छिक इनपुट डेटा बिंदु हो सकता है $x_{1}$, माध्य शिफ्ट घनत्व अनुमान के ग्रेडिएंट की गणना करता है $f(x)$ पर $y_{k}$ और उस दिशा में एक कठिन कदम उठाता है।

गुठली के प्रकार

कर्नेल परिभाषा: चलो $X$ हो $n$-आयामी यूक्लिडियन अंतरिक्ष, $\mathbb {R} ^{n}$. का आदर्श $x$ एक गैर-ऋणात्मक संख्या है, $\|x\|^{2}=x^{\top }x\geq 0$. एक समारोह $K:X\rightarrow \mathbb {R}$ यदि कोई प्रोफ़ाइल मौजूद है तो उसे कर्नेल कहा जाता है, $k:[0,\infty ]\rightarrow \mathbb {R}$ , ऐसा है कि

$K(x)=k(\|x\|^{2})$ और

• k गैर-नकारात्मक है।
• k गैर-बढ़ती है: $k(a)\geq k(b)$ अगर $a<b$.
• k टुकड़े-टुकड़े निरंतर है और $\int _{0}^{\infty }k(r)\,dr<\infty \$

माध्य बदलाव के लिए दो सबसे अधिक उपयोग की जाने वाली कर्नेल प्रोफ़ाइल हैं:

फ्लैट कर्नेल

$k(x)={\begin{cases}1&{\text{if}}\ x\leq \lambda \\0&{\text{if}}\ x>\lambda \\\end{cases}}$

गाऊसी कर्नेल

$k(x)=e^{-{\frac {x}{2\sigma ^{2}}}},$

जहां मानक विचलन पैरामीटर $\sigma$ बैंडविड्थ पैरामीटर के रूप में काम करता है, $h$.

अनुप्रयोग

क्लस्टरिंग

द्वि-आयामी अंतरिक्ष में बिंदुओं के एक सेट पर विचार करें। मान लीजिए कि एक गोलाकार खिड़की केन्द्रित है $C$ और त्रिज्या वाला $r$ कर्नेल के रूप में. मीन-शिफ्ट एक पहाड़ी चढ़ाई एल्गोरिथ्म है जिसमें अभिसरण तक इस कर्नेल को उच्च घनत्व वाले क्षेत्र में पुनरावृत्त रूप से स्थानांतरित करना शामिल है। प्रत्येक शिफ्ट को माध्य शिफ्ट वेक्टर द्वारा परिभाषित किया जाता है। माध्य शिफ्ट वेक्टर हमेशा घनत्व में अधिकतम वृद्धि की दिशा की ओर इशारा करता है। प्रत्येक पुनरावृत्ति पर कर्नेल को केन्द्रक या उसके भीतर के बिंदुओं के माध्य में स्थानांतरित कर दिया जाता है। इस माध्य की गणना करने की विधि कर्नेल की पसंद पर निर्भर करती है। इस मामले में यदि फ्लैट कर्नेल के बजाय गॉसियन कर्नेल को चुना जाता है, तो प्रत्येक बिंदु को पहले एक भार सौंपा जाएगा जो कि कर्नेल के केंद्र से दूरी बढ़ने पर तेजी से घट जाएगा। अभिसरण पर, ऐसी कोई दिशा नहीं होगी जिस पर एक बदलाव कर्नेल के अंदर अधिक बिंदुओं को समायोजित कर सके।

ट्रैकिंग

दृश्य ट्रैकिंग के लिए माध्य शिफ्ट एल्गोरिदम का उपयोग किया जा सकता है। इस तरह का सबसे सरल एल्गोरिदम पिछली छवि में ऑब्जेक्ट के रंग हिस्टोग्राम के आधार पर नई छवि में एक आत्मविश्वास मानचित्र तैयार करेगा, और ऑब्जेक्ट की पुरानी स्थिति के पास आत्मविश्वास मानचित्र के शिखर को खोजने के लिए माध्य बदलाव का उपयोग करेगा। कॉन्फिडेंस मैप नई छवि पर एक संभाव्यता घनत्व फ़ंक्शन है, जो नई छवि के प्रत्येक पिक्सेल को एक संभावना निर्दिष्ट करता है, जो पिछली छवि में ऑब्जेक्ट में होने वाले पिक्सेल रंग की संभावना है। कुछ एल्गोरिदम, जैसे कर्नेल-आधारित ऑब्जेक्ट ट्रैकिंग, समूह ट्रैकिंग, कैमशिफ्ट इस विचार का विस्तार करें.

चौरसाई

होने देना $x_{i}$ और $z_{i},i=1,...,n,$ हो $d$-संयुक्त स्थानिक-श्रेणी डोमेन में आयामी इनपुट और फ़िल्टर किए गए छवि पिक्सेल। प्रत्येक पिक्सेल के लिए,

• आरंभ करें $j=1$ और $y_{i,1}=x_{i}$
• गणना करें $y_{i,j+1}$ के अनुसार $m(\cdot )$ अभिसरण तक, $y=y_{i,c}$.
• सौंपना $z_{i}=(x_{i}^{s},y_{i,c}^{r})$. सुपरस्क्रिप्ट s और r क्रमशः एक वेक्टर के स्थानिक और श्रेणी घटकों को दर्शाते हैं। असाइनमेंट निर्दिष्ट करता है कि स्थानिक स्थान अक्ष पर फ़िल्टर किए गए डेटा में अभिसरण बिंदु का रेंज घटक होगा $y_{i,c}^{r}$.

ताकतें

1. मीन शिफ्ट वास्तविक डेटा विश्लेषण के लिए उपयुक्त एक एप्लिकेशन-स्वतंत्र उपकरण है।
2. डेटा क्लस्टर पर कोई पूर्वनिर्धारित आकार नहीं लेता है।
3. यह मनमाने फीचर स्पेस को संभालने में सक्षम है।
4. प्रक्रिया एकल पैरामीटर की पसंद पर निर्भर करती है: बैंडविड्थ।
5. बैंडविड्थ/विंडो आकार 'एच' का एक भौतिक अर्थ है, के-मीन्स|के-मीन्स के विपरीत।

कमजोरियाँ

1. विंडो आकार का चयन कोई मामूली बात नहीं है.
2. अनुपयुक्त विंडो आकार के कारण मोड मर्ज हो सकते हैं, या अतिरिक्त "उथले" मोड उत्पन्न हो सकते हैं।
3. अक्सर अनुकूली विंडो आकार का उपयोग करने की आवश्यकता होती है।

उपलब्धता

एल्गोरिदम के वेरिएंट मशीन लर्निंग और इमेजेज प्रोसेसिंग पैकेज में पाए जा सकते हैं:

• मूर्तियों । कई क्लस्टरिंग एल्गोरिदम के साथ जावा डेटा माइनिंग टूल।
• छवि जे. माध्य शिफ्ट फ़िल्टर का उपयोग करके छवि फ़िल्टरिंग।
• mlpack . कुशल दोहरे वृक्ष एल्गोरिदम-आधारित कार्यान्वयन।
• OpenCV में cvMeanShift विधि के माध्यम से माध्य-शिफ्ट कार्यान्वयन शामिल है
• ऑर्फियो टूलबॉक्स। एक C++ कार्यान्वयन.
• स्किकिट-लर्न नम्पी/पायथन कार्यान्वयन कुशल पड़ोसी बिंदुओं के लुकअप के लिए बॉल ट्री का उपयोग करता है

यह भी देखें

• डीबीएससीएएन
• प्रकाशिकी एल्गोरिथ्म
• कर्नेल घनत्व अनुमान (केडीई)
• कर्नेल (सांख्यिकी)