समस्या
K-मीन्स बिना लेबल वाले डेटा में समूह खोजता है। दिए गए सेंट्रॉइड से शुरू करके iterations बार दोहराएँ:
- सौंपना: हर पॉइंट को उसके सबसे नज़दीकी सेंट्रॉइड (यूक्लिडियन दूरी) के क्लस्टर में डालें। अगर दो सेंट्रॉइड बराबर दूरी पर हों, तो छोटे इंडेक्स वाला चुनें।
- अपडेट: हर सेंट्रॉइड को उसे सौंपे गए पॉइंटों के औसत पर ले जाएँ। जिस सेंट्रॉइड को कोई पॉइंट न मिले, वह अपनी जगह रहता है।
k_means(points, centroids, iterations) लागू करें।
इनपुट
points: डेटा पॉइंट, हर एक निर्देशांकों की सूची।
centroids: k शुरुआती सेंट्रॉइड, निर्देशांकों की संख्या पॉइंटों जितनी।
iterations: सौंपने और अपडेट करने के कितने चक्र चलाने हैं।
आउटपुट
अंतिम सेंट्रॉइड उनके मूल क्रम में लौटाएँ।
सीमाएँ
1 ≤ पॉइंटों की संख्या ≤ 1,000, 1 ≤ k ≤ 20, 1 ≤ आयाम ≤ 10
0 ≤ iterations ≤ 100
-1,000 ≤ हर निर्देशांक ≤ 1,000
उदाहरण
इनपुट:
points = [
[1.0, 1.0],
[1.5, 2.0],
[8.0, 8.0],
[9.0, 8.5]
]
centroids = [
[0.0, 0.0],
[10.0, 10.0]
]
iterations = 1
अपेक्षित आउटपुट:
expected = [
[1.25, 1.5],
[8.5, 8.25]
]
इनपुट:
std::vector<std::vector<double>> points = {
{1.0, 1.0},
{1.5, 2.0},
{8.0, 8.0},
{9.0, 8.5}
};
std::vector<std::vector<double>> centroids = {
{0.0, 0.0},
{10.0, 10.0}
};
long long iterations = 1;
अपेक्षित आउटपुट:
std::vector<std::vector<double>> expected = {
{1.25, 1.5},
{8.5, 8.25}
};
इनपुट:
double[][] points = new double[][] {
new double[] {1.0, 1.0},
new double[] {1.5, 2.0},
new double[] {8.0, 8.0},
new double[] {9.0, 8.5}
};
double[][] centroids = new double[][] {
new double[] {0.0, 0.0},
new double[] {10.0, 10.0}
};
long iterations = 1;
अपेक्षित आउटपुट:
double[][] expected = new double[][] {
new double[] {1.25, 1.5},
new double[] {8.5, 8.25}
};
व्याख्या
पहले दो पॉइंट (0, 0) के ज़्यादा पास हैं और आखिरी दो (10, 10) के। नए सेंट्रॉइड औसत हैं: ((1 + 1.5) / 2, (1 + 2) / 2) = (1.25, 1.5) और ((8 + 9) / 2, (8 + 8.5) / 2) = (8.5, 8.25)।
इनपुट:
points = [
[0.0],
[1.0],
[10.0]
]
centroids = [
[0.0],
[100.0]
]
iterations = 2
अपेक्षित आउटपुट:
expected = [
[3.666667],
[100.0]
]
इनपुट:
std::vector<std::vector<double>> points = {
{0.0},
{1.0},
{10.0}
};
std::vector<std::vector<double>> centroids = {
{0.0},
{100.0}
};
long long iterations = 2;
अपेक्षित आउटपुट:
std::vector<std::vector<double>> expected = {
{3.666667},
{100.0}
};
इनपुट:
double[][] points = new double[][] {
new double[] {0.0},
new double[] {1.0},
new double[] {10.0}
};
double[][] centroids = new double[][] {
new double[] {0.0},
new double[] {100.0}
};
long iterations = 2;
अपेक्षित आउटपुट:
double[][] expected = new double[][] {
new double[] {3.666667},
new double[] {100.0}
};
व्याख्या
चक्र 1: (100) हर पॉइंट से दूर है, इसलिए तीनों पॉइंट सेंट्रॉइड 1 में जाते हैं, जो (0 + 1 + 10) / 3 ≈ 3.666667 पर खिसक जाता है; सेंट्रॉइड 2 को कोई पॉइंट नहीं मिलता और वह 100 पर रहता है। चक्र 2 में भी यही होता है, इसलिए परिणाम [[3.666667], [100]] है।
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।