1. K近傍法（KNN）の概要

**K近傍法（K-Nearest Neighbors: KNN）とは、機械学習における基本的なアルゴリズムです。この手法は特徴空間内で最も近いk個のデータポイントに基づいて分類を行います。

1）定義

特徴空間内の任意のサンプルが、その周囲のk個の最も似ている（距離が近い）多数派と同じクラスに属すると仮定します。

2）距離計算式

以下は一般的なユークリッド距離の計算方法です。

• 2次元平面で点a(x₁, y₁)とb(x₂, y₂)間の距離: d₁₂ = √((x₁ - x₂)² + (y₁ - y₂)²)
• n次元空間での点aとb間の距離: d₁₂ = √(Σ(x₁k - x₂k)²)

映画ジャンル予測例

下表に示すように、いくつかの映画データがあります。9番目の映画のジャンルを予測する場合、KNNアルゴリズムを使用できます。

KNNアルゴリズムの手順

1. 現在の点と既知のデータセット内のすべての点との距離を計算。

2. 距離に基づき昇順に並べ替え。

3. 最も近いk個の点を選択。

4. k個の点のクラス出現頻度を統計的に集計。

5. 頻度が最も高いクラスを現在の点の予測クラスとして返す。

6. KNNアルゴリズムのPython実装

sklearn.neighbors.KNeighborsClassifierを使用した簡単な例を紹介します。

from sklearn.neighbors import KNeighborsClassifier

# データセットの作成
features = [[1], [2], [10], [20]]
labels = [0, 0, 1, 1]

# モデルの構築と訓練
classifier = KNeighborsClassifier(n_neighbors=1)
classifier.fit(features, labels)

# 予測
prediction = classifier.predict([[1]])
print(prediction)

出力結果：

[0]

3. 距離尺度の種類

ユークリッド距離 n次元空間での距離: d₁₂ = √(Σ(x₁k - x₂k)²)

マンハッタン距離 n次元空間での距離: d₁₂ = Σ| x₁k - x₂k |

チェビシェフ距離 n次元空間での距離: d₁₂ = max(|x₁k - x₂k|)

ミンコフ斯基距離 一般化された距離尺度: d₁₂ = (Σ| x₁k - x₂k |^p)^(1/p)

標準化ユークリッド距離 各次元の標準偏差を考慮した距離: d₁₂ = √(Σ((x₁k - x₂k) / sk)²)

コサイン類似度 方向性を比較する尺度: cosθ = (Σx₁k * x₂k) / (√(Σx₁k²) * √(Σx₂k²))

4. K値の選択

K値が小さい場合、異常値への影響を受けやすくなります。一方でK値が大きすぎると、データ分布の不均衡による問題が発生します。

5. kd木の概要

kd木とは？ k次元空間の効率的な探索を可能にするためのデータ構造です。

kd木の構築アルゴリズム

1. 方差が最大の次元を選ぶ。
2. 中央値を基準にデータを分割し、左右の子ノードを再帰的に生成。
3. 全てのデータが処理されるまで繰り返す。

kd木の検索アルゴリズム

1. 根から葉まで移動し、現在の最近点を特定。
2. 戻りながら他の領域にも最適な点がないか確認。
3. 根に戻ったら終了。

kd木のPython実装例

import numpy as np


class KDTreeNode:
    def __init__(self, point, left=None, right=None):
        self.point = point
        self.left = left
        self.right = right


class KDTree:
    def __init__(self, points):
        def build(points, depth=0):
            if not points:
                return None
            axis = depth % len(points[0])
            sorted_points = sorted(points, key=lambda point: point[axis])
            mid = len(sorted_points) // 2
            return KDTreeNode(
                sorted_points[mid],
                build(sorted_points[:mid], depth + 1),
                build(sorted_points[mid + 1:], depth + 1)
            )
        self.root = build(points)

    def nearest_neighbor(self, target):
        best_point = [None]
        best_distance = [float('inf')]

        def search(node, depth=0):
            if node is None:
                return
            axis = depth % len(target)
            distance = sum((p1 - p2) ** 2 for p1, p2 in zip(target, node.point))
            if distance < best_distance[0]:
                best_distance[0] = distance
                best_point[0] = node.point
            next_branch = target[axis] < node.point[axis]
            search(node.left if next_branch else node.right, depth + 1)
            if abs(target[axis] - node.point[axis]) < best_distance[0]:
                search(node.right if next_branch else node.left, depth + 1)
        search(self.root)
        return best_point[0]


if __name__ == '__main__':
    data = np.array([[2, 3], [5, 4], [9, 6], [4, 7], [8, 1], [7, 2]])
    tree = KDTree(data.tolist())
    query = [2, 4.5]
    print("最近傍点:", tree.nearest_neighbor(query))