静かなる名辞

pythonとプログラミングのこと

2019/03/22:TechAcademyがteratailの質問・回答を盗用していた件
2019/03/26:TechAcademy盗用事件 公式発表と深まる疑念


scikit-learnで重み付きk近傍法(Weighted kNN)を試してみる

はじめに

 k近傍法には、近傍点の重み付けをどうするかで複数のやり方が考えられます。普通のk近傍点では予測対象の点のkつの近傍点を取ってきて、そのクラスを単純に多数決します。一方で、より近い点にはより大きい重みを持たせるという発想もまた自然です。

 という訳で、scikit-learnのKNeighborsClassifierはweightsオプションを指定することで重み付けを加味したKNNモデルを作成できます。これはとても簡単なので、やってみようと思います。

sklearn.neighbors.KNeighborsClassifier — scikit-learn 0.21.3 documentation

しくみとやること

 weightsオプションには"uniform"と"distance"、または任意のcallableを渡せます。"uniform"は重みなし(普通のkNN、デフォルト)、"distance"は距離の逆数を重みにします。callableを渡す場合、距離行列を引数に取り、重み行列を返すようなcallableでなければなりません。たとえば、lambda x:1/xを指定することは(おそらく)"distance"を指定することと同じ意味を持ちます。

 今回はk=3, 5, 10の条件で、デフォルト(指定なし:"uniform")と"distance"を比べてみます。二次元の2クラスのデータに対して予測させることで、そのまま可視化します。

コード

 以前やった実験のコードを書き換えて使用しました。

君はKNN(k nearest neighbor)の本当のすごさを知らない - 静かなる名辞

 そもそものベースになっているのは、scikit-learnが公式で出している分類器の比較のためのコードです。下記ページで雰囲気を掴んでおくと読みやすいと思います。

Classifier comparison — scikit-learn 0.21.3 documentation

 今回の実験だとサンプル数が少ないほうが傾向がわかりやすいので、サンプル数50でやっています。

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.neighbors import KNeighborsClassifier

def main():
    knn3 = KNeighborsClassifier(n_neighbors=3)
    knn3w = KNeighborsClassifier(n_neighbors=3, weights="distance")
    knn5 = KNeighborsClassifier(n_neighbors=5)
    knn5w = KNeighborsClassifier(n_neighbors=5, weights="distance")
    knn10 = KNeighborsClassifier(n_neighbors=10)
    knn10w = KNeighborsClassifier(n_neighbors=10, weights="distance")

    X, y = make_classification(
        n_samples=50, 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(n_samples=50, noise=0.3, random_state=0),
                make_circles(
                    n_samples=50, noise=0.2, factor=0.5, random_state=1),
                linearly_separable]

    fig, axes = plt.subplots(
        nrows=3, ncols=6, figsize=(32, 18))
    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=3 weighted", knn3w),
                 ("KNN k=5", knn5), ("KNN k=5 weighted", knn5w),
                 ("KNN k=10", knn10), ("KNN k=10 weighted", knn10w)]):
            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
result.png

 全体の傾向はさほど変わりませんが、

  • 重み付きの方が確率の階段がなめらか
  • ノイズっぽいサンプルに引っ張られる(過学習気味になる)。特に周囲に他のサンプルがないと引っ張られやすい

 という傾向が見られました。

考察

 距離の逆数で重みを付けて多数決することで、分離境界が少しなめらかになります。

 また、近くの点をより重視するので、kを小さくしたかのような効果があります。そのままでは過学習っぽくなってしまいますが、kを大きくして使うことで、汎化性能もある程度は確保できます。

 原理的には、より広い領域の上方をまったく捨てるのではなく多少は活用できることになります。そういうポリシーのもとで使うべきでしょう。

 また、"distance"を指定すると少し重み付けが効きすぎるかな? という気がするので、lambda x:x**(-1/2)を試してみるといった努力の方向性もありだと色々試してみて感じました。

 以前やったバギングと比べると計算が軽く、境界の確率がなめらかになるという意味では近い効果があります。

まとめ

 ということで気軽に指定できるので、kNNで精度を求める時(なにそれ)は"distance"も試してみる価値はあります。