pytorchが手がける——K近隣アルゴリズム
18865 ワード
概要
k近隣(knn)アルゴリズムは比較的単純な機械学習アルゴリズムであり,訓練を必要としない不活性アルゴリズムに属するが,予測のたびにデータセットを遍歴する必要があるため,時間的複雑度が高い.KNNモデルの3つの基本要素: Kは選択に値し,K値が小さいほど近似誤差が小さくなり,推定誤差が大きいほど過フィッティングに相当する.例えば、k=1であれば、カテゴリは彼の最近のポイントと同じカテゴリになります. 距離メトリック:距離は、特徴空間内の2つのインスタンスの類似度を反映します.オーステナイト距離、マンハッタン距離を採用できます. 分類決定規則:多数決を採用することが多い.
pytorch実装-Mnistデータセット検証
筆者らは,各試験例を反復し,もう1つは行列法により欧州距離を計算する2つの方法を用いて,欧州距離計算を実現した.マトリックス法原理マトリックス計算ユークリッド距離
2つの方法の結果は、5000のトレーニングセットと200のテストセットのサンプルの結果と同じです.
2つの方法の時間比較:
マトリックス実装
反復実装
<<1s
28s
k近隣(knn)アルゴリズムは比較的単純な機械学習アルゴリズムであり,訓練を必要としない不活性アルゴリズムに属するが,予測のたびにデータセットを遍歴する必要があるため,時間的複雑度が高い.KNNモデルの3つの基本要素:
pytorch実装-Mnistデータセット検証
筆者らは,各試験例を反復し,もう1つは行列法により欧州距離を計算する2つの方法を用いて,欧州距離計算を実現した.マトリックス法原理マトリックス計算ユークリッド距離
from torchvision import datasets, transforms
import numpy as np
from sklearn.metrics import accuracy_score
import torch
from tqdm import tqdm
import time
# matrix func
def KNN(train_x, train_y, test_x, test_y, k):
since = time.time()
m = test_x.size(0)
n = train_x.size(0)
# cal Eud distance mat
print("cal dist matrix")
xx = (test_x**2).sum(dim=1,keepdim=True).expand(m, n)
yy = (train_x**2).sum(dim=1, keepdim=True).expand(n, m).transpose(0,1)
dist_mat = xx + yy - 2*test_x.matmul(train_x.transpose(0,1))
mink_idxs = dist_mat.argsort(dim=-1)
res = []
for idxs in mink_idxs:
# voting
res.append(np.bincount(np.array([train_y[idx] for idx in idxs[:k]])).argmax())
assert len(res) == len(test_y)
print("acc", accuracy_score(test_y, res))
time_elapsed = time.time() - since
print('KNN mat training complete in {:.0f}m {:.0f}s'.format(time_elapsed // 60, time_elapsed % 60))
def cal_distance(x, y):
return torch.sum((x-y)**2)**0.5
# iteration func
def KNN_by_iter(train_x, train_y, test_x, test_y, k):
since = time.time()
# cal distance
res = []
for x in tqdm(test_x):
dists = []
for y in train_x:
dists.append(cal_distance(x,y).view(1))
idxs = torch.cat(dists).argsort()[:k]
res.append(np.bincount(np.array([train_y[idx] for idx in idxs])).argmax())
# print(res[:10])
print("acc",accuracy_score(test_y, res))
time_elapsed = time.time() - since
print('KNN iter training complete in {:.0f}m {:.0f}s'.format(time_elapsed // 60, time_elapsed % 60))
if __name__ == "__main__":
train_dataset = datasets.MNIST(root="./data", transform=transforms.ToTensor(), train=True)
test_dataset = datasets.MNIST(root="./data", transform=transforms.ToTensor(), train=False)
# build train&test data
train_x = []
train_y = []
for i in range(len(train_dataset)):
img, target = train_dataset[i]
train_x.append(img.view(-1))
train_y.append(target)
if i > 5000:
break
# print(set(train_y))
test_x = []
test_y = []
for i in range(len(test_dataset)):
img, target = test_dataset[i]
test_x.append(img.view(-1))
test_y.append(target)
if i > 200:
break
print("classes:" , set(train_y))
KNN(torch.stack(train_x), train_y, torch.stack(test_x), test_y, 7)
KNN_by_iter(torch.stack(train_x), train_y, torch.stack(test_x), test_y, 7)
2つの方法の結果は、5000のトレーニングセットと200のテストセットのサンプルの結果と同じです.
ACC = 0.94059
2つの方法の時間比較:
マトリックス実装
反復実装
<<1s
28s