機械学習における分類タスクで頻繁に利用されるアルゴリズムの一つに、k-近傍法（k-Nearest Neighbors, kNN）があります。

k-近傍法の仕組み

k-近傍法は、ラベル付きの訓練データセットが与えられた上で、ラベルのない新しいデータ点を分類する手法です。新しいデータ点の各特徴量を、訓練データセット内のデータ点の対応する特徴量と比較し、最も類似した（距離が最も近い）k個のデータ点を特定します。このk個の近傍データ点の中で最も頻繁に出現するクラスを、新しいデータ点のクラスと予測します。kは通常、20以下の整数として設定されます。

直感的な理解としては、新しいデータの分類は、その「近所に住む」データの大多数の分類によって決まる、という考え方です。例えば、ある人物の周りに多くの退役軍人がいる場合、その人物も退役軍人である可能性が高い、というロジックです。アルゴリズムの目的は、まず近所のデータを特定し、その中で最も多い分類を探し出すことです。

適用シナリオと特性

長所:

• 高い精度：適切なk値を選択すれば、分類精度が高くなります。
• 異常値に強い：多数決によって決まるため、少数の異常値の影響を受けにくいです。
• データの分布に関する仮定が不要：データが特定の分布に従っていることを仮定しません。

短所:

• 計算コストが高い：新しいデータ点と全ての訓練データ点との距離を計算する必要があるため、計算量が大きくなります。
• 高い空間複雑性：全ての訓練データを保存する必要があるため、メモリ使用量が大きくなります。

適用データ型:

• 数値型（Numerical）：連続的な値を取る特徴量。
• 名義型（Nominal）：有限個のカテゴリ値を取る特徴量。

実装例と解説

ここでは、オンラインデートサイトのマッチング相手を分類するシナリオを例に、k-近傍法を実装します。この例は、『機械学習実戦』のケーススタディを参考にしています。コードはPythonで記述します（matplotlibとNumPyライブラリが必要）。

ケーススタディ：ヘレンのデート相手分類

ヘレンはオンラインデートサイトを利用していますが、気に入る相手を見つけることができません。彼女は過去のデート相手を3つのタイプに分類しました。

1. 好みのない人（タイプ1）
2. 魅力的な人（タイプ2）
3. 非常に魅力的な人（タイプ3）

ヘレンは、デートサイトが提供する情報だけでなく、自身で収集した追加データ（毎年獲得する飛行機のマイル数、ビデオゲームをプレイする時間の割合、毎週消費するアイスクリームのリットル数）が、相手の分類に役立つと考えました。彼女の目標は、これらのデータに基づいて、新しいマッチング相手を正確に3つのタイプのいずれかに分類することです。

1. データの収集

ヘレンが収集したデータは、テキストファイル（.txt）形式で保存されています。各行は1人のデータを表し、前3列は3つの特徴量、最後の列はその人の分類（1, 2, または3）を示します。

2. データの準備

コンピュータがテキストファイルを読み込み、処理できる形式（行列）に変換する必要があります。特徴量データを格納する行列と、対応する分類ラベルを格納するリストを作成します。

import numpy as np

def load_data_from_file(filename):
    """
    テキストファイルからデータを読み込み、特徴量行列とラベルリストを返す。
    """
    with open(filename, 'r') as fr:
        lines = fr.readlines()
        number_of_lines = len(lines)
        feature_matrix = np.zeros((number_of_lines, 3))
        label_vector = []
        
        for index, line in enumerate(lines):
            line = line.strip()
            feature_list = line.split('\t')
            feature_matrix[index, :] = feature_list[0:3]
            label_vector.append(int(feature_list[-1]))
            
    return feature_matrix, label_vector

3. アルゴリズムの設計とデータ分析

k-近傍法の核心は、新しいデータ点と既存のデータ点との「距離」を計算し、最も近いk個のデータ点を見つけることです。ここでは、ユークリッド距離を使用します。

A点(x1, x2, x3)とB点(y1, y2, y3)の距離は、以下の式で計算されます。 √[(x1-y1)² + (x2-y2)² + (x3-y3)²]

しかし、元のデータセットでは、1つ目の特徴量（飛行機のマイル数）の値の範囲が他の特徴量よりもはるかに広いため、距離計算において不公正な影響を与えてしまいます。この問題を解決するために、特徴量の値を0から1の範囲に正規化する必要があります。正規化の式は以下の通りです。

newValue = (oldValue - min) / (max - min)

正規化とkNN分類器の実装は以下の通りです。

def normalize_features(data_set):
    """
    データセットの特徴量を0-1の範囲に正規化する。
    """
    min_vals = data_set.min(0)
    max_vals = data_set.max(0)
    ranges = max_vals - min_vals
    normalized_data = (data_set - min_vals) / ranges
    return normalized_data, ranges, min_vals

def knn_classifier(new_sample, training_data, training_labels, k_value):
    """
    k-近傍法による分類を行う。
    """
    data_set_size = training_data.shape[0]
    diff_matrix = np.tile(new_sample, (data_set_size, 1)) - training_data
    sq_diff_matrix = diff_matrix ** 2
    sq_distances = sq_diff_matrix.sum(axis=1)
    distances = sq_distances ** 0.5
    sorted_distance_indices = distances.argsort()
    
    class_count = {}
    for i in range(k_value):
        vote_label = training_labels[sorted_distance_indices[i]]
        class_count[vote_label] = class_count.get(vote_label, 0) + 1
        
    sorted_class_count = sorted(class_count.items(), key=lambda item: item[1], reverse=True)
    return sorted_class_count[0][0]

4. アルゴリズムのテスト

準備した関数を使用して、モデルの性能をテストします。訓練データセットの一部をテストデータとして使用し、予測結果と実際のラベルを比較することで、誤り率を計算します。

def evaluate_knn_model(file_path, test_ratio=0.10, k_value=3):
    """
    k-近傍法モデルをテストし、誤り率を計算する。
    """
    dating_matrix, dating_labels = load_data_from_file(file_path)
    normalized_matrix, feature_ranges, feature_mins = normalize_features(dating_matrix)
    
    total_samples = normalized_matrix.shape[0]
    num_test_samples = int(total_samples * test_ratio)
    error_count = 0.0
    
    for i in range(num_test_samples):
        predicted_class = knn_classifier(
            normalized_matrix[i, :], 
            normalized_matrix[num_test_samples:total_samples, :], 
            dating_labels[num_test_samples:total_samples], 
            k_value
        )
        actual_class = dating_labels[i]
        print(f"予測結果: {predicted_class}, 実際のラベル: {actual_class}")
        
        if predicted_class != actual_class:
            error_count += 1.0
            
    error_rate = error_count / float(num_test_samples)
    print(f"総誤り率: {error_rate:.4f}")

# モデルの評価を実行
evaluate_knn_model('datingTestSet.txt')

このテストコードは、データセットの最初の10%をテストデータとして使用し、残りを訓練データとしてモデルを評価します。結果として、モデルの誤り率が表示されます。この例では、テストの結果として総誤り率が約0.05（5%）となりました。