मीन शिफ्ट

मीन शिफ्ट एक गैर पैरामीट्रिक सुविधा स्थान गणितीय विश्लेषण तकनीक है जो एक घनत्व फलन के मैक्सिमा का पता लगाने के लिए एक आधारशील एल्गोरिदम है, जिसे मोड संवेदना खोजी एल्गोरिदम कहा जाता है। इसके अनुप्रयोग डिजिटल दृष्टि में क्लस्टर विश्लेषण और छवि प्रसंस्करण में किया जाता है।

इतिहास

मीन शिफ्ट प्रक्रिया को सामान्यतः 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$ को $x\leftarrow m(x)$ से सेट करता है और अनुमानन को$m(x)$का संघटन होने तक दोहराता है।

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

गॉसियन मीन-शिफ्ट एक अपेक्षासंग्रह एवं अधिकतमीकरण एल्गोरिदम है।

विवरण

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

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

एल्गोरिथ्म के प्रत्येक पुनरावृत्ति में, $s\leftarrow m(s)$ सभी के लिए किया जाता है $s\in S$ इसके साथ ही।

प्रत्येक एल्गोरिदम के प्रत्यावर्तन में, सभी S के प्रत्येक p के लिए m(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++ कार्यान्वयन.
• स्किकिट-लर्न नम्पी/पायथन कार्यान्वयन कुशल पड़ोसी बिंदुओं के लुकअप के लिए बॉल ट्री का उपयोग करता है

यह भी देखें

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