मीन शिफ्ट

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

इतिहास

मीन शिफ्ट प्रक्रिया को सामान्यतः 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. बैंडविड्थ/विंडो का आकार 'h' भौतिक अर्थ रखता है, जो k-मीन्स के विपरीत है।

कमजोरियाँ

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

उपलब्धता

अभिकलन\ के विभिन्न रूप डेटा विश्लेषण और छवि प्रसंस्करण पैकेजों में देखे जा सकते हैं:

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

यह भी देखें

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