中級 1件解決済み 正答率100.0%

k近傍法による分類

最も近い k 個の学習点の多数決でラベルを予測します。

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

  • 最も近い学習データを見つける
  • 多数決で予測する
  • 同数を決まった方法で解決する

問題

原文(英語)を表示

k近傍法(KNN)は、新しい点に最も近い k 個の学習点を見て、最も多いラベルで分類します。

  1. query からすべての点までのユークリッド距離を計算します。
  2. 点を距離順に並べます。距離が同じ場合は、インデックスが小さい点が先です。
  3. 先頭の k 個の点を取り、ラベルを数えます。
  4. 最も票の多いラベルを返します。同票の場合は、並べた順で最も近い点が先に来るラベルを返します。

knn_predict(points, labels, query, k) を実装してください。

入力

points: 学習点。各点は座標のリストです。

labels: 各点のラベル。

query: 分類する点。

k: 投票する近傍の数。

出力

予測したラベルを返してください。

制約

1 ≤ k ≤ 点の数 ≤ 1,000

1 ≤ 次元数 ≤ 20

-1,000 ≤ 各座標 ≤ 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";

解説

(3, 3) からの距離:(2, 2) ≈ 1.41、(1, 1) ≈ 2.83、(8, 8) ≈ 7.07。最も近い3つのラベルは A、A、B なので、答えは 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";

解説

最も近い点は (0, 0)(red)です。次の2つ (4, 0) と (0, 4) は同じ距離なので、インデックスが小さい (4, 0)(blue)が選ばれます。red と blue が1票ずつで、red の点が先に来たので、答えは red です。

解き方のヒント

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

ヒント 1

各点の query までの Euclidean distance を測り、距離順に並べる。タイブレークは小さい index を優先する。

ヒント 2

並べた先頭の k 個だけが投票するので、最終ラベルは学習データのごく一部で決まる。

ヒント 3

票数が同数なら、投票に使われた点のうち最も早く sorted neighbor list に現れるラベルを選ぶ。

目安の計算量

時間 O(n log n)、追加メモリ O(n)

参考資料

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

ランキング

全体ランキング

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

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

他の人の解答から学ぶ

コミュニティの解答

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