दिलचस्प पोस्ट
मैट ओएस एक्सयोस्मिथ / एल कैप्टन पर ऑटोस्टार्ट माइस् SQL सर्वर गुणों के लिए __noSuchMethod__ सुविधा के बराबर है, या इसे जेएस में लागू करने का एक तरीका है? जावा में चर के नामकरण प्रतिबंध यह: स्थिर संदर्भ में इसका उपयोग नहीं कर सकता टाइप किए गए स्मृति दृश्य के लिए मेमोरी आवंटित करने का अनुशंसित तरीका क्या है? क्यों दस्तावेज़.all फाल्सी है? डाटाबेस। बेनिफ्रेंस ट्रांजैक्शन बनाम लेनदेन। ट्रांन्सैक्शनस्स्कोप लैम्ब्डा इस संदर्भ में जावा कॉर्डोवा प्लगइन विकास – एआर जोड़ना इनपुट पाठ तत्व पर सीमा को उजागर कैसे करें आत्म-समापन इनपुट टैग HTML 4 में मान्य हैं? रिजक्स रिटर्न फ़ाइल का नाम, पथ और फ़ाइल एक्सटेंशन हटाएं जावा रीगेक्स कैप्चर समूह AngularJS संसाधन वादा मैं सही तरीके से स्वरूपित होने के लिए कुछ पायथन कोड को autoformat कैसे कर सकता हूं?

कश्मीर के निकटतम पड़ोसी और इसके कार्यान्वयन ढूँढना

मैं यूक्लिडियन दूरी के साथ केएनएन का उपयोग कर सरल डेटा को वर्गीकृत करने पर काम कर रहा हूं। मैंने देखा है कि MATLAB knnsearch फ़ंक्शन के साथ किया गया है कि मैं क्या करना चाहूंगा पर एक उदाहरण देखा है:

 load fisheriris x = meas(:,3:4); gscatter(x(:,1),x(:,2),species) newpoint = [5 1.45]; [n,d] = knnsearch(x,newpoint,'k',10); line(x(n,1),x(n,2),'color',[.5 .5 .5],'marker','o','linestyle','none','markersize',10) 

उपरोक्त कोड एक नया बिंदु यानी [5 1.45] लेता है और नए बिंदु के 10 निकटतम मान पाता है। क्या कोई मुझे एक MATLAB एल्गोरिथ्म दिखा सकता है जो कि knnsearch समारोह क्या करता है knnsearch विस्तृत व्याख्या है? ऐसा करने के लिए कोई और रास्ता नहीं है?

गणना दूरी और छँटाई के विवरण के साथ

Solutions Collecting From Web of "कश्मीर के निकटतम पड़ोसी और इसके कार्यान्वयन ढूँढना"

के-निकटतम पड़ोसी (केएनएन) एल्गोरिथ्म का आधार यह है कि आपके पास डेटा मैट्रिक्स है जिसमें N पंक्तियाँ और M कॉलम हैं, जहां N हमारे पास डेटा बिंदुओं की संख्या है, जबकि M प्रत्येक डेटा बिंदु की आयाम है उदाहरण के लिए, अगर हम डेटा मैट्रिक्स के अंदर कार्टेशियन को समन्वयित करते हैं, तो यह आमतौर पर एक N x 2 या N x 3 मैट्रिक्स होता है। इस डेटा मैट्रिक्स के साथ, आप एक क्वेरी बिंदु प्रदान करते हैं और आप इस डेटा मैट्रिक्स के भीतर निकटतम k अंक की खोज करते हैं जो इस क्वेरी बिंदु के निकटतम हैं।

हम आमतौर पर क्वेरी के बीच यूक्लिडियन दूरी और अपने डेटा मैट्रिक्स में अपने सभी बिंदुओं का उपयोग हमारी दूरी की गणना करने के लिए करते हैं। हालांकि, अन्य दूरी जैसे एल 1 या सिटी-ब्लॉक / मैनहट्टन दूरी का उपयोग भी किया जाता है। इस ऑपरेशन के बाद, आपके पास N यूक्लिडियन या मैनहट्टन की दूरी है जो डेटा सेट में प्रत्येक संबंधित बिंदु के साथ क्वेरी के बीच की दूरी का प्रतीक है। एक बार जब आप इन्हें खोजते हैं, तो आप केवल निकटतम बिंदुओं की खोज को आरोहण क्रम में क्रमबद्ध करके और उन बिंदुओं को पुनः प्राप्त करने के लिए क्वेरी के लिए खोज कर सकते हैं, जो आपके डेटा सेट और क्वेरी के बीच की सबसे छोटी दूरी है।

अपने डेटा मैट्रिक्स का newpoint x में संग्रहीत किया गया था, और newpoint एक नमूना बिंदु है जहां इसमें M कॉलम (यानी 1 x M ) है, यह सामान्य प्रक्रिया है जिसे आप बिंदु के रूप में पालन करेंगे:

  1. newpoint और x में हर बिंदु के बीच यूक्लिडियन या मैनहट्टन की दूरी का पता लगाएं
  2. इन दूरी को आरोही क्रम में क्रमबद्ध करें
  3. x में मौजूद k डेटा बिंदु पर लौटें जो newpoint सबसे नज़दीकी हैं।

चलो हर कदम धीरे धीरे करते हैं


चरण 1

एक ऐसा तरीका जो कोई ऐसा कर सकता है शायद ऐसा लूप के लिए है:

 N = size(x,1); dists = zeros(N,1); for idx = 1 : N dists(idx) = sqrt(sum((x(idx,:) - newpoint).^2)); end 

यदि आप मैनहट्टन दूरी को लागू करना चाहते हैं, तो यह बस होगा:

 N = size(x,1); dists = zeros(N,1); for idx = 1 : N dists(idx) = sum(abs(x(idx,:) - newpoint)); end 

dists N तत्व वेक्टर होगा जिसमें x और newpoint में प्रत्येक डेटा बिन्दु के बीच की दूरी शामिल newpoint । हम newpoint और x में एक डेटा बिन्दु के बीच एक तत्व-बाय-एलिमेंट घटाव करते हैं, अंतर का अंतर, फिर उन सभी को एक साथ sum करें। यह राशि तब बनी हुई है जो युक्लिडियन दूरी को पूरा करती है। मैनहट्टन की दूरी के लिए, आप तत्व घटाव के द्वारा एक तत्व निष्पादित करेंगे, पूर्ण मान लें, फिर सभी घटकों को एक साथ जोड़ दें। संभवतः यह समझने के लिए कार्यान्वयन का सबसे आसान तरीका है, लेकिन यह संभवत: सबसे ज्यादा अक्षम नहीं हो सकता है … खासकर बड़े आकार के डेटा सेट के लिए और आपके डेटा की बड़ी आयामी।

एक और संभावित समाधान, नए newpoint को दोहराने के लिए होगा और इस मैट्रिक्स को x के समान आकार बनाना होगा, फिर इस मैट्रिक्स का एक तत्व-बाय-एलिमेंट घटाकर करना चाहिए, फिर प्रत्येक पंक्ति के सभी कॉलमों पर newpoint और वर्गमूल करना। इसलिए, हम ऐसा कुछ कर सकते हैं:

 N = size(x, 1); dists = sqrt(sum((x - repmat(newpoint, N, 1)).^2, 2)); 

मैनहट्टन की दूरी के लिए, आप ऐसा करेंगे:

 N = size(x, 1); dists = sum(abs(x - repmat(newpoint, N, 1)), 2); 

repmat एक मैट्रिक्स या वेक्टर लेता है और उन्हें किसी निश्चित दिशा में एक निश्चित मात्रा में दोहराता है। हमारे मामले में, हम अपने newpoint वेक्टर लेना चाहते हैं, और N x M मैट्रिक्स बनाने के लिए इस N बार को एक दूसरे के ऊपर ढेर करना चाहते हैं, जहां प्रत्येक पंक्ति M तत्वों की लंबी होती है। हम इन दो मैट्रिक्स को एक साथ घटाते हैं, फिर प्रत्येक घटक स्क्वायर करते हैं। एक बार जब हम ऐसा करते हैं, तो हम प्रत्येक पंक्ति के सभी कॉलमों पर sum करते हैं और अंत में सभी परिणामों का वर्गमूल लेते हैं। मैनहट्टन की दूरी के लिए, हम घटाव करते हैं, पूर्ण मूल्य लेते हैं और फिर योग करते हैं।

हालांकि, मेरी राय में ऐसा करने का सबसे प्रभावी तरीका bsxfun का उपयोग करना होगा। यह अनिवार्य रूप से एक फ़ंक्शन कॉल के साथ हुड के तहत हम जिस प्रतिकृति के बारे में बात करते थे इसलिए, कोड बस यह होगा:

 dists = sqrt(sum(bsxfun(@minus, x, newpoint).^2, 2)); 

मेरे लिए यह बहुत क्लीनर और बिंदु पर दिखता है। मैनहट्टन की दूरी के लिए, आप ऐसा करेंगे:

 dists = sum(abs(bsxfun(@minus, x, newpoint)), 2); 

चरण 2

अब जब हमारे पास हमारी दूरी है, हम बस उन्हें सॉर्ट करते हैं हम अपनी दूरी को सॉर्ट करने के लिए sort का उपयोग कर सकते हैं:

 [d,ind] = sort(dists); 

d में आरोही क्रम में क्रमबद्ध दूरी शामिल होती है, जबकि ind आपको प्रत्येक मान के लिए बताएंगे कि वह क्रमबद्ध परिणाम में प्रकट होता है। हमें ind का उपयोग करने, इस वेक्टर के पहले k तत्वों को निकालने की जरूरत है, फिर उन अंकों को वापस करने के लिए हमारे x डेटा मैट्रिक्स में सूचकांक का उपयोग करें, जो newpoint ओर से सबसे नज़दीकी थे।

चरण 3

अंतिम चरण अब उन k डेटा बिंदुओं को वापस करना है जो newpoint सबसे नज़दीकी हैं। हम यह बहुत आसानी से कर सकते हैं:

 ind_closest = ind(1:k); x_closest = x(ind_closest,:); 

ind_closest में मूल डेटा मैट्रिक्स x में सूचकांक होना चाहिए जो कि newpoint के निकटतम हैं। विशेष रूप से, ind_closest में ind_closest के सबसे निकटतम बिंदुओं को प्राप्त करने के लिए x में नमूने की आवश्यकता वाली पंक्तियां शामिल हैं। x_closest में उन वास्तविक डेटा बिंदुओं को शामिल किया जाएगा


आपकी नकल और चिपकाने के लिए कोड यही दिखता है:

 dists = sqrt(sum(bsxfun(@minus, x, newpoint).^2, 2)); %// Or do this for Manhattan % dists = sum(abs(bsxfun(@minus, x, newpoint)), 2); [d,ind] = sort(dists); ind_closest = ind(1:k); x_closest = x(ind_closest,:); 

अपने उदाहरण के माध्यम से चल रहा है, चलो कार्रवाई में हमारा कोड देखें:

 load fisheriris x = meas(:,3:4); newpoint = [5 1.45]; k = 10; %// Use Euclidean dists = sqrt(sum(bsxfun(@minus, x, newpoint).^2, 2)); [d,ind] = sort(dists); ind_closest = ind(1:k); x_closest = x(ind_closest,:); 

ind_closest और x_closest निरीक्षण करके, हम यही प्राप्त करते हैं:

 >> ind_closest ind_closest = 120 53 73 134 84 77 78 51 64 87 >> x_closest x_closest = 5.0000 1.5000 4.9000 1.5000 4.9000 1.5000 5.1000 1.5000 5.1000 1.6000 4.8000 1.4000 5.0000 1.7000 4.7000 1.4000 4.7000 1.4000 4.7000 1.5000 

यदि आप knnsearch , तो आप देखेंगे कि आपकी चर n ind_closest साथ मेल खाता है हालांकि, चर d newpoint से दूरी प्रत्येक बिंदु x , न कि वास्तविक डेटा बिंदुओं को स्वयं। यदि आप वास्तविक दूरी चाहते हैं, तो बस मैंने लिखा कोड के बाद निम्नलिखित करें:

 dist_sorted = d(1:k); 

ध्यान दें कि उपर्युक्त उत्तर में N उदाहरण के एक बैच में केवल एक क्वेरी बिंदु का उपयोग होता है। बहुत बार केएनएन का प्रयोग कई उदाहरणों पर एक साथ किया जाता है। मान लीजिए कि हमारे पास Q क्वेरी पॉइंट हैं जो हम केएनएन में परीक्षण करना चाहते हैं। इसके परिणामस्वरूप एक kx M x Q मैट्रिक्स होगा, जहां प्रत्येक उदाहरण या प्रत्येक टुकड़ा के लिए, हम M एक आयाम के साथ के सबसे निकटतम बिंदु वापस लेते हैं। वैकल्पिक रूप से, हम k निकटतम बिंदुओं की आईडी वापस कर सकते हैं जिसके परिणामस्वरूप एक Q xk मैट्रिक्स हो सकता है। चलो दोनों की गणना करें।

ऐसा करने के लिए एक भोले-भरे तरीके से प्रत्येक उदाहरण पर लूप और पाश में उपरोक्त कोड लागू करना होगा।

ऐसा कुछ ऐसा काम करेगा जहां हम एक Q xk मैट्रिक्स को आवंटित करते हैं और डेटासेट के सबसे निकटतम बिंदुओं में आउटपुट मैट्रिक्स की प्रत्येक पंक्ति को सेट करने के लिए bsxfun आधारित दृष्टिकोण को लागू करते हैं, जहां हम फिशर आईरिस डाटासेट का उपयोग करते हैं जैसे कि हमारे पास पहले था। हम पिछले आयाम में भी उसी आयाम को बनाए रखेंगे, और मैं चार उदाहरणों का उपयोग करूँगा, इसलिए Q = 4 और M = 2 :

 %// Load the data and create the query points load fisheriris; x = meas(:,3:4); newpoints = [5 1.45; 7 2; 4 2.5; 2 3.5]; %// Define k and the output matrices Q = size(newpoints, 1); M = size(x, 2); k = 10; x_closest = zeros(k, M, Q); ind_closest = zeros(Q, k); %// Loop through each point and do logic as seen above: for ii = 1 : Q %// Get the point newpoint = newpoints(ii, :); %// Use Euclidean dists = sqrt(sum(bsxfun(@minus, x, newpoint).^2, 2)); [d,ind] = sort(dists); %// New - Output the IDs of the match as well as the points themselves ind_closest(ii, :) = ind(1 : k).'; x_closest(:, :, ii) = x(ind_closest(ii, :), :); end 

हालांकि यह बहुत अच्छा है, हम भी बेहतर कर सकते हैं। वैक्टर के दो सेटों के बीच स्क्वेर्ड युक्लिडियन दूरी को कुशलता से गणना करने का एक तरीका है। यदि आप मैनहट्टन के साथ ऐसा करना चाहते हैं तो मैं इसे एक अभ्यास के रूप में छोड़ दूँगा इस ब्लॉग को परामर्श करना, कि A एक Q1 x M मैट्रिक्स है, जहां प्रत्येक पंक्ति Q1 अंकों के साथ आयामी M का एक बिंदु है और B एक Q2 x M मैट्रिक्स है, जहां प्रत्येक पंक्ति भी Q2 अंकों के साथ आयामी M एक बिंदु है, हम कुशलता से कर सकते हैं एक दूरी मैट्रिक्स D(i, j) गणना करें जहां पंक्ति i और कॉलम j में तत्व A पंक्ति i के बीच की दूरी को और B के B पंक्ति को इंगित करते हैं, जो निम्न मैट्रिक्स फॉर्मूलेशन का उपयोग करते हैं:

 nA = sum(A.^2, 2); %// Sum of squares for each row of A nB = sum(B.^2, 2); %// Sum of squares for each row of B D = bsxfun(@plus, nA, nB.') - 2*A*B.'; %// Compute distance matrix D = D.^(0.5); %// Compute square root to complete calculation 

इसलिए, यदि हम A को क्वेरी पॉइंट्स का मैट्रिक्स बनाते हैं और B को अपने मूल डेटा से युक्त डेटासेट बनाते हैं, तो हम प्रत्येक पंक्ति को व्यक्तिगत रूप से क्रमबद्ध करके और प्रत्येक पंक्ति के k स्थानों का निर्धारण करते हैं जो सबसे छोटा था। हम वास्तविक अंक खुद को पुनः प्राप्त करने के लिए इसके अतिरिक्त उपयोग भी कर सकते हैं।

इसलिए:

 %// Load the data and create the query points load fisheriris; x = meas(:,3:4); newpoints = [5 1.45; 7 2; 4 2.5; 2 3.5]; %// Define k and other variables k = 10; Q = size(newpoints, 1); M = size(x, 2); nA = sum(newpoints.^2, 2); %// Sum of squares for each row of A nB = sum(x.^2, 2); %// Sum of squares for each row of B D = bsxfun(@plus, nA, nB.') - 2*newpoints*x.'; %// Compute distance matrix D = D.^(0.5); %// Compute square root to complete calculation %// Sort the distances [d, ind] = sort(D, 2); %// Get the indices of the closest distances ind_closest = ind(:, 1:k); %// Also get the nearest points x_closest = permute(reshape(x(ind_closest(:), :).', M, k, []), [2 1 3]); 

हम देखते हैं कि हमने दूरी मैट्रिक्स की गणना के लिए तर्क का इस्तेमाल किया है, लेकिन उदाहरण के अनुरूप कुछ वैरिएबल्स बदल गए हैं। हम प्रत्येक पंक्ति को स्वतंत्र रूप से सॉर्ट के दो इनपुट संस्करणों का उपयोग करके स्वतंत्र रूप से sort और ind प्रति पंक्ति आईडी होंगे और d में इसी दूरी शामिल होंगे हम तो यह पता लगा सकते हैं कि यह मैट्रिक्स केवल k कॉलम को छोटा करके प्रत्येक सूचक बिंदु के सबसे निकटतम सूचकांक हैं। हम फिर permute उपयोग permute और निर्धारित करते हैं कि निकटतम बिंदु क्या हैं हम सबसे पहले सभी सूचकांकों का उपयोग करते हैं और एक बिंदु मैट्रिक्स बनाते हैं जो एक दूसरे के ऊपर सभी आईडी ढेर कर देते हैं, इसलिए हमें एक Q * kx M मैट्रिक्स मिलता है। permute और permute का उपयोग करने से हमें हमारे 3 डी मैट्रिक्स बनाने की अनुमति मिलती है ताकि यह हमारे द्वारा निर्दिष्ट किए गए जैसे एक kx M x Q मैट्रिक्स हो। यदि आप खुद को वास्तविक दूरी प्राप्त करना चाहते हैं, तो हम d में इंडेक्स कर सकते हैं और हमें जो जरूरत है उसे हासिल कर सकते हैं। ऐसा करने के लिए, आपको रैखिक सूचकांक प्राप्त करने के लिए sub2ind का उपयोग करना होगा ताकि हम एक शॉट में d को सूचक कर सकें। ind_closest मान पहले से ही हमें ind_closest कि हमें किस कॉलम में पहुंच की आवश्यकता है। हमारे द्वारा उपयोग की जाने वाली पंक्तियां केवल 1, k समय, 2, k समय आदि हैं। k अंक की संख्या के लिए है जिसे हम वापस करना चाहते थे:

 row_indices = repmat((1:Q).', 1, k); linear_ind = sub2ind(size(d), row_indices, ind_closest); dist_sorted = D(linear_ind); 

जब हम उपरोक्त क्वेरी पॉइंट के लिए उपरोक्त कोड चलाते हैं, तो ये ये सूचकांक, अंक और दूरी हैं जो हम प्राप्त करते हैं:

 >> ind_closest ind_closest = 120 134 53 73 84 77 78 51 64 87 123 119 118 106 132 108 131 136 126 110 107 62 86 122 71 127 139 115 60 52 99 65 58 94 60 61 80 44 54 72 >> x_closest x_closest(:,:,1) = 5.0000 1.5000 6.7000 2.0000 4.5000 1.7000 3.0000 1.1000 5.1000 1.5000 6.9000 2.3000 4.2000 1.5000 3.6000 1.3000 4.9000 1.5000 6.7000 2.2000 x_closest(:,:,2) = 4.5000 1.6000 3.3000 1.0000 4.9000 1.5000 6.6000 2.1000 4.9000 2.0000 3.3000 1.0000 5.1000 1.6000 6.4000 2.0000 4.8000 1.8000 3.9000 1.4000 x_closest(:,:,3) = 4.8000 1.4000 6.3000 1.8000 4.8000 1.8000 3.5000 1.0000 5.0000 1.7000 6.1000 1.9000 4.8000 1.8000 3.5000 1.0000 4.7000 1.4000 6.1000 2.3000 x_closest(:,:,4) = 5.1000 2.4000 1.6000 0.6000 4.7000 1.4000 6.0000 1.8000 3.9000 1.4000 4.0000 1.3000 4.7000 1.5000 6.1000 2.5000 4.5000 1.5000 4.0000 1.3000 >> dist_sorted dist_sorted = 0.0500 0.1118 0.1118 0.1118 0.1803 0.2062 0.2500 0.3041 0.3041 0.3041 0.3000 0.3162 0.3606 0.4123 0.6000 0.7280 0.9055 0.9487 1.0198 1.0296 0.9434 1.0198 1.0296 1.0296 1.0630 1.0630 1.0630 1.1045 1.1045 1.1180 2.6000 2.7203 2.8178 2.8178 2.8320 2.9155 2.9155 2.9275 2.9732 2.9732 

knnsearch साथ इसकी तुलना करने के लिए, आप इसके बजाय दूसरे पैरामीटर के लिए अंकों का एक मैट्रिक्स निर्दिष्ट करेंगे, जहां प्रत्येक पंक्ति एक क्वेरी बिन्दु है और आप देखेंगे कि इस क्रियान्वयन और knnsearch बीच इंडेक्स और सॉर्ट किए गए दूरी का मिलान।


आशा है कि यह आपको मदद करता है सौभाग्य!