समस्या
K-नियरेस्ट नेबर्स (KNN) किसी नए पॉइंट को उसके सबसे नज़दीकी k ट्रेनिंग पॉइंट देखकर और सबसे आम लेबल चुनकर वर्गीकृत करता है।
queryसे हर पॉइंट तक की यूक्लिडियन दूरी निकालें।- पॉइंटों को दूरी के अनुसार क्रम में लगाएँ; अगर दो दूरियाँ बराबर हों, तो छोटे इंडेक्स वाला पॉइंट पहले आता है।
- पहले k पॉइंट लें और उनके लेबल गिनें।
- सबसे ज़्यादा वोट वाला लेबल लौटाएँ। बराबरी होने पर वह लेबल लौटाएँ जिसका सबसे नज़दीकी पॉइंट क्रम में पहले आता है।
knn_predict(points, labels, query, k) लागू करें।
इनपुट
points: ट्रेनिंग पॉइंट, हर एक निर्देशांकों की सूची।
labels: हर पॉइंट का लेबल।
query: वह पॉइंट जिसे वर्गीकृत करना है।
k: कितने पड़ोसी वोट करते हैं।
आउटपुट
अनुमानित लेबल लौटाएँ।
सीमाएँ
1 ≤ k ≤ पॉइंटों की संख्या ≤ 1,000
1 ≤ आयाम ≤ 20
-1,000 ≤ हर निर्देशांक ≤ 1,000
उदाहरण
इनपुट:
points = [
[1.0, 1.0],
[2.0, 2.0],
[8.0, 8.0],
[9.0, 9.0]
]
labels = ["A", "A", "B", "B"]
query = [3.0, 3.0]
k = 3
अपेक्षित आउटपुट:
expected = "A"
इनपुट:
std::vector<std::vector<double>> points = {
{1.0, 1.0},
{2.0, 2.0},
{8.0, 8.0},
{9.0, 9.0}
};
std::vector<std::string> labels = {"A", "A", "B", "B"};
std::vector<double> query = {3.0, 3.0};
long long k = 3;
अपेक्षित आउटपुट:
std::string expected = "A";
इनपुट:
double[][] points = new double[][] {
new double[] {1.0, 1.0},
new double[] {2.0, 2.0},
new double[] {8.0, 8.0},
new double[] {9.0, 9.0}
};
string[] labels = new string[] {"A", "A", "B", "B"};
double[] query = new double[] {3.0, 3.0};
long k = 3;
अपेक्षित आउटपुट:
string expected = "A";
व्याख्या
(3, 3) से दूरियाँ: (2, 2) ≈ 1.41, (1, 1) ≈ 2.83, (8, 8) ≈ 7.07। 3 सबसे नज़दीकी लेबल A, A और B हैं, इसलिए उत्तर A है।
इनपुट:
points = [
[0.0, 0.0],
[4.0, 0.0],
[0.0, 4.0],
[4.0, 4.0]
]
labels = ["red", "blue", "blue", "red"]
query = [1.0, 1.0]
k = 2
अपेक्षित आउटपुट:
expected = "red"
इनपुट:
std::vector<std::vector<double>> points = {
{0.0, 0.0},
{4.0, 0.0},
{0.0, 4.0},
{4.0, 4.0}
};
std::vector<std::string> labels = {"red", "blue", "blue", "red"};
std::vector<double> query = {1.0, 1.0};
long long k = 2;
अपेक्षित आउटपुट:
std::string expected = "red";
इनपुट:
double[][] points = new double[][] {
new double[] {0.0, 0.0},
new double[] {4.0, 0.0},
new double[] {0.0, 4.0},
new double[] {4.0, 4.0}
};
string[] labels = new string[] {"red", "blue", "blue", "red"};
double[] query = new double[] {1.0, 1.0};
long k = 2;
अपेक्षित आउटपुट:
string expected = "red";
व्याख्या
सबसे नज़दीकी पॉइंट (0, 0) (red) है; अगले दो, (4, 0) और (0, 4), बराबर दूरी पर हैं, इसलिए छोटा इंडेक्स (4, 0) (blue) चुना जाता है। red और blue को एक-एक वोट मिला, और red का पॉइंट पहले आया, इसलिए उत्तर red है।
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
हर point की query तक Euclidean distance मापें, फिर distance के आधार पर points को rank करें, और tie होने पर smaller indices को पहले रखें।
संकेत 2
सिर्फ sorted points में से पहले k ही vote करते हैं, इसलिए final label training set के एक छोटे हिस्से पर depend करता है।
संकेत 3
अगर vote counts tie हों, तो उस label को चुनें जिसका nearest contributing point sorted neighbor list में सबसे पहले आता है।
अपेक्षित जटिलता
समय O(n log n), अतिरिक्त स्थान O(n)
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।