すべてのチャレンジ
中級 1件解決済み 正答率100.0%

K-Nearest Neighbors Classifier

Predict a label by majority vote of the k closest training points.

このチャレンジで学べること

  • Find the closest training points
  • Predict by majority vote
  • Break ties deterministically

問題

翻訳を表示

K-nearest neighbors (KNN) classifies a new point by looking at the k training points closest to it and taking the most common label.

  1. Compute the Euclidean distance from query to every point.
  2. Sort the points by distance; if two distances are equal, the point with the smaller index comes first.
  3. Take the first k points and count their labels.
  4. Return the label with the most votes. If labels tie, return the tied label whose closest point comes first in the sorted order.

Implement knn_predict(points, labels, query, k).

Input

points: The training points, each a list of coordinates.

labels: The label of each point.

query: The point to classify.

k: How many neighbors vote.

Output

Return the predicted label.

制約

1 ≤ k ≤ number of points ≤ 1,000

1 ≤ dimensions ≤ 20

-1,000 ≤ each coordinate ≤ 1,000

例

例 1
入力:
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";

解説

Distances from (3, 3): (2, 2) ≈ 1.41, (1, 1) ≈ 2.83, (8, 8) ≈ 7.07. The 3 nearest labels are A, A and B, so the answer is A.

例 2
入力:
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";

解説

The nearest point is (0, 0) (red); the next two, (4, 0) and (0, 4), are at the same distance, so the smaller index (4, 0) (blue) wins the tie. Red and blue have one vote each, and red's point came first, so the answer is red.

解き方のヒント

まずは自分で考えてから、ヒントを 1 つずつ開いてみましょう。

ヒント 1

Measure each point’s Euclidean distance to the query, then rank points by distance with smaller indices breaking ties.

ヒント 2

Only the first k sorted points vote, so the final label depends on a tiny subset of the training set.

ヒント 3

If vote counts tie, use the label whose nearest contributing point appears earliest in the sorted neighbor list.

目安の計算量

O(n log n) time, O(n) extra space

参考資料

この課題はCodeUtility用に調整されています。上記の説明と制約に従ってください。

ランキング

全体ランキング

コーダーごとのいちばん良い合格解答です。速く、メモリが少なく、評価が高い解答ほど上位になります。

# コーダー 言語 時間 メモリ AI 評価 解答
1 ННикита Python 930 ms - 5/5 コードを見る

他の人の解答から学ぶ

コミュニティの解答

ネタバレ注意:下に1件の全解答あり まずは自分で挑戦してみましょう。他の開発者のコードやAIレビューも見ることができます。 サインインして課題を解くと議論に参加できます。