Unsupervised learner--k-Nearest Neighbor

K最近接（k-Nearest Neighbor，KNN）分類アルゴリズム

導入背景

最も乱暴な分類器は、すべての訓練データを記録し、テスト対象の属性がある訓練対象の属性と完全に一致した場合、分類する.

被験者は、それと完全に一致する訓練対象を見つけられなかった.

試験対象は同時に複数の訓練対象と一致し、1つの訓練対象が分割される.

げんり

KNNは機械学習における最も基本的な分類器である

は、異なる特徴値間の距離をテストすることによって分類される

.

あるサンプルが、特徴空間におけるk個の最も類似した(すなわち、特徴空間において最も隣接している)サンプルの大部分があるカテゴリに属する場合、そのサンプルもこのカテゴリに属する.

KNNアルゴリズムはKの選択に依存し、k値が比較的小さい場合は、サンプル中の少ないデータだけを用いて「訓練」を行ったことに相当し、==オーバーフィット===が発生しやすく、誤差が大きすぎる.k値が比較的大きい場合,推定データに近いサンプルに相当する予測も関与し,モデル偏差が大きすぎる.1つの経験は、kが訓練サンプル数の平方根

より一般的に低いことである.

距離の選択は主にヨーロッパ式距離とマンハッタン距離(範数)漫談を採用する:機械学習における距離と類似性メトリック法

ステップ

は、テストデータと各トレーニングデータ(既知のカテゴリデータ)との間の距離を計算する.

距離インクリメント順

距離値が最も小さいK個の点を選択する.

は、前K個の点が存在するカテゴリの出現頻度を決定する.

は、試験データの予測分類として、前K点の中で最も頻度の高いカテゴリを返す.

長所と短所

の利点:簡単で、多種類の分類問題に適しており、相対精度が高く、異常値に敏感ではなく、データ入力仮定がない.

欠点:計算量が大きく、予測のたびにすべてのサンプルの距離を計算する必要がある.サンプルが不均衡で、予測結果が不正確で、空間複雑度が高い.

Python実現

# === （ KNN ）====
def classify0(x, dataset, labels, k):
    dataset_size = dataset.shape[0]  # shape[0] stands for the num of row
    # step 1: calculate Euclidean distance
    # tile(A, reps): Construct an array by repeating A reps times
    # the following copy numSamples rows for dataSet
    diff_mat = np.tile(x, (dataset_size, 1)) - dataset
    sq_diff_mat = diff_mat ** 2
    sq_distances = sq_diff_mat.sum(axis=1)
    distances = sq_distances ** 0.5
    # step 2: sort the distance
    # argsort() returns the indices that would sort an array in a ascending order
    sorted_dist_indicies = distances.argsort()

    class_count = {}
    for i in range(k):
        # step 3: choose the min k distance
        voted_label = labels[sorted_dist_indicies[i]]
        # step 4: count the times labels occur
        # when the key voteLabel is not in dictionary classCount, get()
        # will return 0
        class_count[voted_label] = class_count.get(voted_label, 0) + 1
        # step 5: the max voted class will return
        # Python 2.x  `class_count.iteritems()
    sorted_class_count = sorted(class_count.iteritems(),
                                key=operator.itemgetter(1),
                                reverse=True)
    return sorted_class_count[0][0]