निकटवर्ती घटकों का विश्लेषण

निकटवर्ती घटकों का विश्लेषण सांख्यिकीय वर्गीकरण के लिए पर्यवेक्षित सीखने की विधि है जो डेटा पर दिए गए मापन (गणित) के अनुसार अलग-अलग वर्गों में बहुभिन्नरूपी सांख्यिकी डेटा को विभाजित करता है। कार्यात्मक रूप से, यह K-निकटतम निकटवर्तीय एल्गोरिदम के समान उद्देश्यों को पूर्ण करता है, और प्रसंभाव्य निकटतम निकटवर्तीय नामक संबंधित अवधारणा का प्रत्यक्ष उपयोग करता है।

परिभाषा

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

स्पष्टीकरण

$A$ को परिभाषित करने के लिए, हम परिवर्तित स्थान में वर्गीकरण यथार्थता का वर्णन करने वाले एक उद्देश्य फलन को परिभाषित करते हैं और $A^{*}$ को निर्धारित करने का प्रयास करते हैं ताकि यह उद्देश्य फलन अधिकतम हो।

$A^{*}={\mbox{argmax}}_{A}f(A)$

लीव-वन-आउट (एलओओ) वर्गीकरण

किसी दिए गए दूरी मापन के साथ उसके $k$-निकटतम निकटवर्तीय की सहमति से एकल डेटा बिंदु के वर्ग लेबल की भविष्यवाणी करने पर विचार करें। इसे लीव-वन-आउट वर्गीकरण के रूप में जाना जाता है। यद्यपि, सभी बिंदुओं को एक रैखिक परिवर्तन से गुज़रने के बाद निकटतम-निकटवर्तीय $C_{i}$ का समूह अत्यधिक भिन्न हो सकता है। विशेष रूप से, किसी बिंदु के लिए निकटवर्तीय का समूह $A$ के अवयवों में सुचारू परिवर्तनों के उत्तर में अलग-अलग परिवर्तनों से गुजर सकता है, जिसका अर्थ है कि किसी बिंदु के निकटवर्तीय के आधार पर कोई भी उद्देश्य फलन $f(\cdot )$ टुकड़े-टुकड़े-स्थिर होगा, और इसलिए अलग-अलग नहीं होगा।

हल

हम प्रसंभाव्य प्रवणता अवरोहण से प्रेरित दृष्टिकोण का उपयोग करके इस जटिलता को हल कर सकते हैं। एलओओ-वर्गीकरण में प्रत्येक परिवर्तित बिंदु पर $k$-निकटतम निकटवर्तीय पर विचार करने के अतिरिक्त, हम संपूर्ण रूपांतरित डेटा समूह को प्रसंभाव्य निकटतम निकटवर्तीय के रूप में मानेंगे। हम किसी दिए गए एलओओ-वर्गीकरण बिंदु और रूपांतरित स्थान में दूसरे बिंदु के बीच वर्गित यूक्लिडियन दूरी के सॉफ्टमैक्स सक्रियण फलन का उपयोग करके इन्हें परिभाषित करते हैं:

$p_{ij}={\begin{cases}{\frac {e^{-||Ax_{i}-Ax_{j}||^{2}}}{\sum _{k\neq i}e^{-||Ax_{i}-Ax_{k}||^{2}}}},&{\mbox{if}}j\neq i\\0,&{\mbox{if}}j=i\end{cases}}$

डेटा बिंदु $i$ को ठीक रूप से वर्गीकृत करने की प्रायिकता उसके प्रत्येक निकटवर्ती बिंदु को समान वर्ग $C_{i}$ के साथ वर्गीकृत करने की प्रायिकता है::

$p_{i}=\sum _{j\in C_{i}}p_{ij}\quad$ जहाँ $p_{ij}$ बिंदु $i$ के निकटवर्ती $j$ को वर्गीकृत करने की प्रायिकता है।

एलओओ वर्गीकरण का उपयोग करके उद्देश्य फलन को परिभाषित करें, इस बार संपूर्ण डेटा समूह को प्रसंभाव्य निकटतम निकटवर्तीय के रूप में उपयोग करें:

$f(A)=\sum _{i}\sum _{j\in C_{i}}p_{ij}=\sum _{i}p_{i}$

ध्यान दें कि प्रसंभाव्य निकटतम निकटवर्तीय के अंतर्गत, एक बिंदु $i$ के लिए सर्वसम्मति वर्ग अपने निकटवर्तीय $j\in C_{i}$ अर्थात: $P(Class(X_{i})=Class(X_{j}))=p_{ij}$ पर वितरण से खींचे गए प्रतिदर्शों की अनंत संख्या की सीमा में एक बिंदु के वर्ग का अपेक्षित मान है। इस प्रकार अनुमानित वर्ग प्रत्येक दूसरे बिंदु के वर्गों का संयोजन है, जिसे प्रत्येक $j\in C_{j}$ के लिए सॉफ्टमैक्स फलन द्वारा भारित होता है जहाँ $C_{j}$ अब संपूर्ण परिवर्तित डेटा समूह है।

उद्देश्य फलन का यह विकल्प ठीक है क्योंकि यह $A$ ($x_{ij}=x_{i}-x_{j}$ को इंगित करें) के संबंध में भिन्न है:

${\frac {\partial f}{\partial A}}=-2A\sum _{i}\sum _{j\in C_{i}}p_{ij}\left(x_{ij}x_{ij}^{T}-\sum _{k}p_{ik}x_{ik}x_{ik}^{T}\right)$

$=2A\sum _{i}\left(p_{i}\sum _{k}p_{ik}x_{ik}x_{ik}^{T}-\sum _{j\in C_{i}}p_{ij}x_{ij}x_{ij}^{T}\right)$

$A$ के लिए प्रवणता प्राप्त करने का अर्थ है कि इसे संयुग्मी प्रवणता विधि जैसे पुनरावृत्त हलकर्ता के साथ पाया जा सकता है। ध्यान दें कि व्यवहार में, रुचि के बिंदु से दूर के बिंदुओं के तीव्रता से घटते योगदान के कारण प्रवणता के अधिकांश आंतरिक शब्द महत्वहीन योगदान का मूल्यांकन करते हैं। इसका अर्थ यह है कि प्रवणता के आंतरिक योग को छोटा किया जा सकता है, जिसके परिणामस्वरूप बड़े डेटा समूह के लिए भी उचित गणना समय प्राप्त होता है।

वैकल्पिक सूत्रीकरण

"$f(\cdot )$ को अधिकतम करना अनुमानित वर्ग वितरण और वास्तविक वर्ग वितरण के बीच $L_{1}$-दूरी को कम करने के बराबर है (अर्थात: जहां $A$ द्वारा प्रेरित $p_{i}$ सभी 1 के बराबर हैं)। प्राकृतिक विकल्प केएल-भिन्नता है, जो निम्नलिखित उद्देश्य फलन और प्रवणता को प्रेरित करता है:" (गोल्डबर्गर 2005)

$g(A)=\sum _{i}\log \left(\sum _{j\in C_{i}}p_{ij}\right)=\sum _{i}\log(p_{i})$

${\frac {\partial g}{\partial A}}=2A\sum _{i}\left(\sum _{k}p_{ik}x_{ik}x_{ik}^{T}-{\frac {\sum _{j\in C_{i}}p_{ij}x_{ij}x_{ij}^{T}}{\sum _{j\in C_{i}}p_{ij}}}\right)$

व्यवहार में, इस फलन का उपयोग करके $A$ का अनुकूलन से मूल के समान निष्पादन परिणाम देता है।

इतिहास और पृष्ठभूमि

निकटवर्ती के घटकों का विश्लेषण 2004 में टोरंटो विश्वविद्यालय के कंप्यूटर विज्ञान विभाग में जैकब गोल्डबर्गर, सैम रोविस, रुस्लान सलाखुदिनोव और ज्योफ हिंटन द्वारा विकसित किया गया था।

यह भी देखें

• वर्णक्रमीय क्लस्टरिंग
• बड़ा अंतर निकटतम निकटवर्ती

संदर्भ

• जे. गोल्डबर्गर, जी. हिंटन, एस. रोविस, आर. सलाखुतदीनोव। (2005) निकटवर्ती के घटकों का विश्लेषण. न्यूरल इन्फर्मेशन प्रोसेसिंग सिस्टम्स में प्रगति। 17, 513-520, 2005।

बाहरी संबंध

सॉफ्टवेयर

• mlpack में C++ कार्यान्वयन सम्मिलित है
• nca (C++)
• स्किकिट-लर्न का NeighborhoodComponentsAnalyss कार्यान्वयन (पायथन (प्रोग्रामिंग भाषा))

श्रेणी:सांख्यिकीय वर्गीकरण