Q4: データの分類 (paizaランク A 相当)

※この問題は、2021年1月に開催されたP共通テスト（バンタンテックフォードアカデミー中高プログラミング共通テスト）で出題された問題です。

データを分類する手法の一つに、k 近傍法というものがあります。

これは、クラスを予測したいデータに最も距離が近い k 個のデータのクラスを調べ、それらによる多数決をとり一番多いクラスをそのデータのクラスの予測値とする考え方です。

なお、データのクラス (ラベル) とは、そのデータの属するカテゴリを指し示すものです。例えば、画像に写っている動物が犬なのか猫なのかを判別する際には、「犬」「猫」がクラスとなります。



本問では、2 次元座標を持つデータの分類について考えることにします。
各データは 2 次元座標 (x_i, y_i) とクラス (c_i) を持っています。
クラスがわかっているいくつかのデータがある状態で、クラス不明のデータのクラスを予測することを考えます。
今 6 個のデータがあり、そのうち 5 個のデータのクラスがわかっているとしましょう。
残りの 1 つのデータのクラスを k 近傍法で分類すると、下図のようになります。






? がクラス不明のデータです。

・k = 1 のときは クラス 1 が 1 つなので、? のクラスは 1 と分類されます。

・k = 3 のときは クラス 1 が 1 つ、クラス 2 が 2 つなので、多数決をとって ? のクラスは 2 と分類されます。

・k = 5 のときは クラス 1 が 3 つ、クラス 2 が 2 つなので、多数決をとって ? のクラスは 1 と分類されます。



k 近傍法による分類がどういったものなのかわかったところで、実装してみましょう。



n 個の 2 次元データとそのクラス、そしてクラス不明の 2 次元データが 1 つ与えられます。そして、q 個の k が与えられるので、各 k について k 近傍法による分類をおこなってください。



なお、k 近傍法による分類は分類結果が一意に定まらない場合がありますが、その場合は以下のようにして分類してください。

・距離が等しいデータが複数存在する場合
　　　　クラスの値が小さいデータを、より近いデータとして採用してください。
・多数決をとった結果、1 番多いクラスが一意に定まらない場合
　　　　値が 1 番小さいクラスを予測値として採用してください。

入力例を例にとって説明します。以下では、座標 (x, y) にあるクラス c のデータを (x, y)-c と表すことにします。






k = 1 のとき、予測したいデータ (0, 0) に最も距離が近い 1 データは (0, 1)-10 と (-1, 0)-5 で 2 つありますが、クラスの値がより小さい 5 を予測値として採用します。

k = 5 のとき、予測したいデータ (0, 0) に最も距離が近い 5 データは (0, 1)-10 と (-1, 0)-5 と (1, 1)-10 と (2, 0)-5 と (2, -2)-100 です。多数決をとるとクラス 5 が 2 つ、クラス 10 が 2 つ、クラス 100 が 1 つで、クラス 5 と クラス 10 が共に 2 つずつありますが、クラスの値がより小さい 5 を予測値として採用します。

k = 3 のとき、予測したいデータ (0, 0) に最も距離が近い 3 データは (0, 1)-10 と (-1, 0)-5 と (1, 1)-10 です。多数決をとるとクラス 5 が 1 つ、クラス 10 が 2 つなので、予測値は 10 となります。