君はKNN（k nearest neighbor）の本当のすごさを知らない

はじめに

　KNNといえば機械学習入門書の最初の方に載っている、わかりやすいけど性能はいまいちな初心者向けの手法という認識の人も多いと思います。

　しかし、本当はけっこう優秀なのです。

2次元で予測させてみる

　予測させます。コードは軽く読み流して結果の図だけ見てください。

import numpy as np
import matplotlib.pyplot as plt
from matplotlib.colors import ListedColormap

from sklearn.datasets import make_moons, make_circles,\
    make_classification
from sklearn.ensemble import RandomForestClassifier
from sklearn.ensemble import BaggingClassifier
from sklearn.neighbors import KNeighborsClassifier

def main():
    knn3 = KNeighborsClassifier(n_neighbors=3)
    knn5 = KNeighborsClassifier(n_neighbors=5)
    knn7 = KNeighborsClassifier(n_neighbors=7)
    knnb = BaggingClassifier(base_estimator=knn5,
                             n_estimators=1000,
                             n_jobs=-1)
    rfc = RandomForestClassifier(n_estimators=1000)

    X, y = make_classification(
        n_features=2, n_redundant=0, n_informative=2,
        random_state=1, n_clusters_per_class=1)
    rng = np.random.RandomState(2)
    X += 2 * rng.uniform(size=X.shape)
    linearly_separable = (X, y)

    datasets = [make_moons(noise=0.3, random_state=0),
                make_circles(
                    noise=0.2, factor=0.5, random_state=1),
                linearly_separable]

    fig, axes = plt.subplots(
        nrows=3, ncols=5, figsize=(16, 9))
    plt.subplots_adjust(wspace=0.2, hspace=0.3)

    cm = plt.cm.RdBu
    cm_bright = ListedColormap(['#FF0000', '#0000FF'])
    for i, (X, y) in enumerate(datasets):
        x_min = X[:, 0].min()-0.5
        x_max = X[:, 0].max()+0.5
        y_min = X[:, 1].min()-0.5
        y_max = X[:, 1].max()+0.5

        xx, yy = np.meshgrid(np.arange(x_min, x_max, 0.1),
                             np.arange(y_min, y_max, 0.1))

        for j, (cname, clf) in enumerate(
                [("KNN k=3", knn3), ("KNN k=5", knn5),
                 ("KNN k=7", knn7), ("Bagg-KNN", knnb),
                 ("RFC", rfc)]):
            clf.fit(X, y)
            Z = clf.predict_proba(
                np.c_[xx.ravel(), yy.ravel()])[:, 1]
            Z = Z.reshape(xx.shape)
            axes[i,j].contourf(xx, yy, Z, 20, cmap=cm, alpha=.8)
            axes[i,j].scatter(X[:,0], X[:,1], c=y, s=20,
                              cmap=cm_bright, edgecolors="black")
            
            axes[i,j].set_title(cname)
    plt.savefig("result.png", bbox_inches="tight")

if __name__ == "__main__":
    main()

result.png

　KNNの方が決定境界が綺麗ですね。まあ、sklearnの実装でpredict_probaすると1/k刻みの確率で出てくるので、そのままではちょっとですが。バギングするとめったに見られない感じの綺麗な確率が出てきます。

digitsを予測させてみる

　先に結論を書くと、ランダムフォレストに勝てます。

from sklearn.datasets import load_digits
from sklearn.ensemble import RandomForestClassifier
from sklearn.ensemble import BaggingClassifier
from sklearn.neighbors import KNeighborsClassifier
from sklearn.model_selection import StratifiedKFold,\
    cross_validate

def main():
    digits = load_digits()

    knn3 = KNeighborsClassifier(n_neighbors=3)
    knn5 = KNeighborsClassifier(n_neighbors=5)
    knn7 = KNeighborsClassifier(n_neighbors=7)
    knnb = BaggingClassifier(base_estimator=knn3,
                             n_estimators=50,
                             n_jobs=-1)
    rfc = RandomForestClassifier(n_estimators=1000)
    skf = StratifiedKFold(n_splits=10, random_state=0)
    for name, clf in [("KNN k=3", knn3), ("KNN k=5", knn5),
                      ("KNN k=7", knn7), ("Bagg-KNN", knnb),
                      ("RFC", rfc)]:

        result = cross_validate(
            clf, digits.data, digits.target,
            cv=skf, scoring="f1_macro",
            return_train_score=False)

        tf = result["fit_time"].mean()
        ts = result["score_time"].mean()
        f1 = result["test_score"].mean()

        print(name)
        print("fit time:{:.3f} test time:{:.3f}".format(tf, ts))
        print("f1-macro:{:.3f}".format(f1))
        print()

if __name__ == "__main__":
    main()

KNN k=3
fit time:0.003 test time:0.039
f1-macro:0.978

KNN k=5
fit time:0.004 test time:0.038
f1-macro:0.974

KNN k=7
fit time:0.003 test time:0.040
f1-macro:0.970

Bagg-KNN
fit time:0.178 test time:1.467
f1-macro:0.979

RFC
fit time:2.624 test time:0.120
f1-macro:0.950

　ランダムフォレストは不甲斐ないなんてレベルじゃなく負けています。

まとめ

　ということで、KNNはけっこう優秀です。学習時間がほとんど必要ないのも魅力的です。

　ただ、ノイズが多いデータに対しては脆弱な面もあります。実際のデータではランダムフォレストに負けることの方が多い印象ですが、それでも頑張るときはがんばります。

　性能重視のときでも試しに使ってみる価値はあると言えるでしょう。