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

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

परिभाषा

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

स्पष्टीकरण

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

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

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

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

समाधान

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

$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}$ निकटवर्ती को वर्गीकृत करने की संभावना है $j$ बिंदु का $i$.

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

$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}$-अनुमानित वर्ग वितरण और वास्तविक वर्ग वितरण के बीच की दूरी (यानी: जहां $p_{i}$ प्रेरक $A$ सभी 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 में टोरंटो विश्वविद्यालय के कंप्यूटर विज्ञान विभाग में जैकब गोल्डबर्गर, सैम रोविस, रुस्लान सलाखुदिनोव और ज्योफ हिंटन द्वारा विकसित किया गया था।

यह भी देखें

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

संदर्भ

• J. Goldberger, G. Hinton, S. Roweis, R. Salakhutdinov. (2005) Neighbourhood Components Analysis. Advances in Neural Information Processing Systems. 17, 513–520, 2005.

बाहरी संबंध

सॉफ्टवेयर

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

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