KNN(K-Nearest Neighbor)アルゴリズム
7871 ワード
アルゴリズムの背景
K近傍(K-Nearest Neighbor,KNN)アルゴリズムは,機械学習分類アルゴリズムにおいてかなりの地位を占める有名なモード識別統計学法である.理論的に成熟した方法です最も簡単な機械学習アルゴリズムの一つであり、インスタンスベースの学習方法の中で最も基本的であり、最良のテキスト分類アルゴリズムの一つでもある.
KNN動作原理
訓練サンプルセットとも呼ばれるサンプルデータセットが存在し、サンプルセットの各データにはラベルが存在します.すなわち、サンプルセットの各データが属する分類に対応する関係を知っています.ラベルのないデータを入力した後、新しいデータの各特徴をサンプルセットデータに対応する特徴と比較し、サンプルセット特徴が最も類似しているデータ(近隣)の分類ラベルを抽出する.一般に,試料データセットの前のk個の最も類似したデータのみを選択し,これがk近傍アルゴリズムにおけるkの出所であり,通常kは20未満の整数である.最後に,k個の最も類似したデータの中で最も出現回数の多い分類を新しいデータの分類として選択した.
説明:KNNは訓練過程を示さず、「怠惰学習」の代表であり、訓練段階でデータを保存するだけで、訓練時間のオーバーヘッドは0で、テストサンプルを受け取ってから処理する.
KNNアルゴリズムの長所と短所
KNNアルゴリズムの利点:
1)簡単、効果的.2)再訓練のコストは低い(カテゴリ体系の変化と訓練セットの変化は,Web環境と電子商取引応用においてよく見られる).3)時間と空間が訓練セットの規模に線形であることを計算する(場合によってはそれほど大きくない).4)KNN法は,クラスドメインを判別する方法ではなく,主に周囲に限られた隣接するサンプルに依存するため,クラスドメインの交差や重複が多い被分割サンプルセットに対しては,他の方法よりもKNN法が適している.5)このアルゴリズムは比較的大きいサンプル容量のクラスドメインの自動分類に適しているが、それらのサンプル容量の小さいクラスドメインはこのアルゴリズムを採用すると比較的に誤分を生じやすい.
KNNアルゴリズムの欠点:
1)KNNアルゴリズムは怠惰学習法(lazy learning,基本的には学習しない)であり,積極的に学習するアルゴリズムはかなり速い.2)カテゴリスコアは正規化されていない(確率スコアとは異なる).3)出力の解釈性は強くなく,例えば決定木の解釈性が強い.4)このアルゴリズムの分類において主な不足点は、1つのクラスのサンプル容量が大きい場合、他のクラスのサンプル容量が小さい場合、1つの新しいサンプルを入力した場合、そのサンプルのK個の隣接する大容量クラスのサンプルが多数を占める可能性があることである.このアルゴリズムは、「最も近い」隣接サンプルのみを計算し、あるクラスのサンプルの数が大きい場合、またはこのようなサンプルがターゲットサンプルに近づいていない場合、またはこのようなサンプルがターゲットサンプルに近い場合を計算します.いずれにしても、数量は実行結果に影響しません.重み値の方法(サンプル距離の小さい隣接重み値と大きい)を用いて改善することができる.5)計算量が多い.現在よく用いられている解決策は,既知のサンプルポイントを事前にクリップし,分類にあまり役に立たないサンプルを事前に除去することである.
Python実現
平均分散正規化法を用い,データを正規化した後,距離重み付けを考慮してアヤメの分類を計算した.
ソースプログラム
sklearnを呼び出す
python tips
元のデータを乱す:shuffle_indexes = np.random.permutation(len(X)) test_size = int(len(X)*test_ratio) test_indexes = shuffle_indexes[:test_size] train_indexes = shuffle_indexes[test_size:]
リストとマトリクスの相互変換:y_list = y_train.tolist()#トレーニングy値マトリクスをリストselfに変換する.y_possible = np.array(y_possible_list)#リストをマトリクスに変換
K近傍(K-Nearest Neighbor,KNN)アルゴリズムは,機械学習分類アルゴリズムにおいてかなりの地位を占める有名なモード識別統計学法である.理論的に成熟した方法です最も簡単な機械学習アルゴリズムの一つであり、インスタンスベースの学習方法の中で最も基本的であり、最良のテキスト分類アルゴリズムの一つでもある.
KNN動作原理
訓練サンプルセットとも呼ばれるサンプルデータセットが存在し、サンプルセットの各データにはラベルが存在します.すなわち、サンプルセットの各データが属する分類に対応する関係を知っています.ラベルのないデータを入力した後、新しいデータの各特徴をサンプルセットデータに対応する特徴と比較し、サンプルセット特徴が最も類似しているデータ(近隣)の分類ラベルを抽出する.一般に,試料データセットの前のk個の最も類似したデータのみを選択し,これがk近傍アルゴリズムにおけるkの出所であり,通常kは20未満の整数である.最後に,k個の最も類似したデータの中で最も出現回数の多い分類を新しいデータの分類として選択した.
説明:KNNは訓練過程を示さず、「怠惰学習」の代表であり、訓練段階でデータを保存するだけで、訓練時間のオーバーヘッドは0で、テストサンプルを受け取ってから処理する.
KNNアルゴリズムの長所と短所
KNNアルゴリズムの利点:
1)簡単、効果的.2)再訓練のコストは低い(カテゴリ体系の変化と訓練セットの変化は,Web環境と電子商取引応用においてよく見られる).3)時間と空間が訓練セットの規模に線形であることを計算する(場合によってはそれほど大きくない).4)KNN法は,クラスドメインを判別する方法ではなく,主に周囲に限られた隣接するサンプルに依存するため,クラスドメインの交差や重複が多い被分割サンプルセットに対しては,他の方法よりもKNN法が適している.5)このアルゴリズムは比較的大きいサンプル容量のクラスドメインの自動分類に適しているが、それらのサンプル容量の小さいクラスドメインはこのアルゴリズムを採用すると比較的に誤分を生じやすい.
KNNアルゴリズムの欠点:
1)KNNアルゴリズムは怠惰学習法(lazy learning,基本的には学習しない)であり,積極的に学習するアルゴリズムはかなり速い.2)カテゴリスコアは正規化されていない(確率スコアとは異なる).3)出力の解釈性は強くなく,例えば決定木の解釈性が強い.4)このアルゴリズムの分類において主な不足点は、1つのクラスのサンプル容量が大きい場合、他のクラスのサンプル容量が小さい場合、1つの新しいサンプルを入力した場合、そのサンプルのK個の隣接する大容量クラスのサンプルが多数を占める可能性があることである.このアルゴリズムは、「最も近い」隣接サンプルのみを計算し、あるクラスのサンプルの数が大きい場合、またはこのようなサンプルがターゲットサンプルに近づいていない場合、またはこのようなサンプルがターゲットサンプルに近い場合を計算します.いずれにしても、数量は実行結果に影響しません.重み値の方法(サンプル距離の小さい隣接重み値と大きい)を用いて改善することができる.5)計算量が多い.現在よく用いられている解決策は,既知のサンプルポイントを事前にクリップし,分類にあまり役に立たないサンプルを事前に除去することである.
Python実現
平均分散正規化法を用い,データを正規化した後,距離重み付けを考慮してアヤメの分類を計算した.
ソースプログラム
#!/usr/bin/env python
# -*- coding: UTF-8 -*-
import numpy as np
from math import sqrt
from collections import Counter
from sklearn import datasets
from sklearn.metrics import accuracy_score
class KNN:
def __init__(self, k, p):
""" kNN """
assert k >= 1, "k must be valid"
self.k = k
self.p = p
self._X_train = None
self._y_train = None
self.y_possible = None
def data_split (self, X, y, test_ratio=0.2, seed=None):
""" test_ratio """
assert X.shape[0] == y.shape[0],\
"the size of X must equal to the size of y"
assert 0.0 <=test_ratio <=1.0, \
"test_ratio must be valid"
if seed:
np.random.seed(seed)
#
shuffle_indexes = np.random.permutation(len(X))
test_size = int(len(X)*test_ratio)
test_indexes = shuffle_indexes[:test_size]
train_indexes = shuffle_indexes[test_size:]
X_train = X[train_indexes]
y_train = y[train_indexes]
X_test = X[test_indexes]
y_test = y[test_indexes]
#y
y_list = y_train.tolist() # y
y_possible_list = sorted(set(y_list),key=y_list.index) # ，
self.y_possible = np.array(y_possible_list) #
#
X_train, X_test= self._scaling(X_train, X_train), self._scaling(X_train, X_test)
return X_train, y_train, X_test, y_test
def _scaling(self, X_train, original_X):
# """ """
# scaling_X = np.ones(shape=original_X.shape)
# for i in range(original_X.shape[1]):
# scaling_X[:,i] = (original_X[:,i] - np.min(X_train[:,i]))/(np.max(X_train[:,i])-np.min(X_train[:,i]))
""" """
scaling_X = np.zeros(shape=original_X.shape)
for i in range(original_X.shape[1]):
scaling_X[:,i] = (original_X[:,i] - np.mean(X_train[:,i]))/(np.std(X_train[:,i]))
return scaling_X
def fit(self, X_train, y_train):
""" X_train y_train kNN """
assert X_train.shape[0] == y_train.shape[0], \
"the size of X_train must be equal to the size of y_train"
assert self.k <= X_train.shape[0], \
"the size of X_train must be at least k."
self._X_train = X_train
self._y_train = y_train
return self
def predict(self, X_predict):
""" X_predict， X_predict """
assert self._X_train is not None and self._y_train is not None, \
"must fit before predict!"
assert X_predict.shape[1] == self._X_train.shape[1], \
"the feature number of X_predict must be equal to X_train"
y_predict = [self._predict(x) for x in X_predict]
return np.array(y_predict)
def _predict(self, x):
""" x， x """
assert x.shape[0] == self._X_train.shape[1], \
"the feature number of x must be equal to X_train"
distances = [pow(np.sum((abs(x_train - x)) ** self.p), 1/self.p)
for x_train in self._X_train]
nearest = np.argsort(distances)
topK_y = [self._y_train[i] for i in nearest[:self.k]]
topK_distance = [distances[i] for i in nearest[:self.k]]
votes_count = np.zeros(shape=(self.y_possible.shape))
for j in range(self.k):
vote_id = np.argwhere(self.y_possible == topK_y[j])
votes_count[vote_id] += 1/(topK_distance[j]+1e-8) #
predict_value_id = np.argmax(votes_count)
predict_value = self.y_possible[predict_value_id]
return predict_value
def score(self, X_test, y_test):
""" X_test y_test """
y_predict = self.predict(X_test)
return accuracy_score(y_test, y_predict)
def __repr__(self):
return "KNN(k=%d)" % self.k
#KNN
iris = datasets.load_iris()
X = iris.data
y = iris.target
iris_knn = KNN(3,7)
X_train, y_train, X_test, y_test = iris_knn.data_split (X, y)
iris_knn.fit(X_train, y_train)
score = iris_knn.score(X_test, y_test)
print(score)
sklearnを呼び出す
#!/usr/bin/env python
# -*- coding: UTF-8 -*-
import numpy as np
from sklearn import datasets
from sklearn.metrics import accuracy_score
from sklearn.neighbors import KNeighborsClassifier
from sklearn.model_selection import train_test_split
from sklearn.model_selection import GridSearchCV
from sklearn.preprocessing import StandardScaler
if __name__=='__main__':
iris = datasets.load_iris()
print(iris.DESCR) #
X = iris.data
y = iris.target
#
X_train, X_test, y_train, y_test = train_test_split (X, y, test_size=0.2, random_state=None)
#
StandardScaler = StandardScaler()
StandardScaler.fit(X_train)
X_train = StandardScaler.transform(X_train)
X_test = StandardScaler.transform(X_test)
#KNN
knn_clf = KNeighborsClassifier(n_neighbors=3)
knn_clf.fit(X_train, y_train)
print(knn_clf.score(X_test, y_test))
param_grid = [
{
'weights':['uniform'],
'n_neighbors':[i for i in range(1,6)]
},
{
'weights':['distance'],
'n_neighbors':[i for i in range(1,6)],
'p':[i for i in range(1,4)]
}
]
#
grid_search = GridSearchCV(knn_clf, param_grid, n_jobs=-1, verbose=2)
grid_search.fit(X_train, y_train)
print(grid_search.best_score_)
print(grid_search.best_params_)
knn_clf = grid_search.best_estimator_
print(knn_clf.score(X_test, y_test))
python tips
元のデータを乱す:shuffle_indexes = np.random.permutation(len(X)) test_size = int(len(X)*test_ratio) test_indexes = shuffle_indexes[:test_size] train_indexes = shuffle_indexes[test_size:]
リストとマトリクスの相互変換:y_list = y_train.tolist()#トレーニングy値マトリクスをリストselfに変換する.y_possible = np.array(y_possible_list)#リストをマトリクスに変換