KNN算法原理
- KNN(K-Nearest Neighbor,KNN)算法，是著名的模式識别統計學方法，在機器學習分類算法中占有相當大的地位。它既是最簡單的機器學習算法之一，也是基于執行個體的學習方法中最基本的，又是最好的文本分類算法之一。
- 算法的基本思想為：在訓練集中資料和标簽已知的情況下，輸入測試資料，将測試資料的特征與訓練集中對應的特征進行互相比較，找到訓練集中與之最為相似的前K個資料，則該測試資料對應的類别就是K個資料中出現次數最多的那個分類。
-
KNN算法涉及3個主要因素：執行個體集、距離或相似的衡量、k的大小。
一個執行個體的最近鄰是根據标準歐氏距離定義的。更精确地講，把任意的執行個體x表示的特征向量：[a1(x),a2(x),…,an(x)]，假定所有實力對應于n維歐式空間an中的點，通過計算一個點與其他所有點的距離，取出與該點最近的k個點，然後統計這k個點裡面所屬分類比例最大的，則這個點屬于該分類，如下圖：
基于KNN算法的手勢圖像分類
KNN算法流程
- 準備資料，對資料進行預處理
- 選用合适的資料結構存儲訓練資料和測試元組
-
設定參數，如k
4.維護一個大小為k的的按距離由大到小的優先級隊列，用于存儲最近鄰訓練元組。随機從訓練元組中選取k個元組作為初始的最近鄰元組，分别計算測試元組到這k個元組的距離，将訓練元組标号和距離存入優先級隊列
- 周遊訓練元組集，計算目前訓練元組與測試元組的距離，将所得距離L 與優先級隊列中的最大距離Lmax
- 進行比較。若L>=Lmax，則舍棄該元組，周遊下一個元組。若L < Lmax，删除優先級隊列中最大距離的元組，将目前訓練元組存入優先級隊列。
- 周遊完畢，計算優先級隊列中k 個元組的多數類，并将其作為測試元組的類别。
- 測試元組集測試完畢後計算誤差率，繼續設定不同的k值重新進行訓練，最後取誤差率最小的k 值。
算法實作
1.計算歐式距離
n維空間下的歐式距離：
本次實驗僅考慮平面二維空間的歐氏距離。
from numpy import *
class KnnClassifier(object):
def __init__(self,labels,samples):
""" Initialize classifier with training data. """
self.labels = labels
self.samples = samples
def classify(self,point,k=3):
""" Classify a point against k nearest
in the training data, return label. """
# compute distance to all training points
dist = array([L2dist(point,s) for s in self.samples])
# sort them
ndx = dist.argsort()
# use dictionary to store the k nearest
votes = {}
for i in range(k):
label = self.labels[ndx[i]]
votes.setdefault(label,0)
votes[label] += 1
return max(votes, key=lambda x: votes.get(x))
def L2dist(p1,p2):
return sqrt( sum( (p1-p2)**2) )
def L1dist(v1,v2):
return sum(abs(v1-v2))
2.建立二維執行個體資料集
建立一個簡單的二維執行個體資料集來說明并可視化分類器的工作原理，下面的腳本将建立兩個不同的二維點集，每個集點有兩類，并用pickle子產品來儲存建立的資料：
# -*- coding: utf-8 -*-
from numpy.random import randn
import pickle
from pylab import *
# create sample data of 2D points
n = 200
# two normal distributions
class_1 = 0.6 * randn(n,2)
class_2 = 1.2 * randn(n,2) + array([5,1])
labels = hstack((ones(n),-ones(n)))
# save with Pickle
#with open('points_normal.pkl', 'w') as f:
with open('points_normal_test.pkl', 'wb') as f:
pickle.dump(class_1,f)
pickle.dump(class_2,f)
pickle.dump(labels,f)
# normal distribution and ring around it
print ("save OK!")
class_1 = 0.6 * randn(n,2)
r = 0.8 * randn(n,1) + 5
angle = 2*pi * randn(n,1)
class_2 = hstack((r*cos(angle),r*sin(angle)))
labels = hstack((ones(n),-ones(n)))
# save with Pickle
#with open('points_ring.pkl', 'w') as f:
with open('points_ring_test.pkl', 'wb') as f:
pickle.dump(class_1,f)
pickle.dump(class_2,f)
pickle.dump(labels,f)
print ("save OK!")
3.k鄰近分類器分類二維資料
在每個示例中，不同顔色代表類标記，正确分類的點用星号表示，分類錯誤的點用圓表示，曲線是分類器的決策邊界：
# -*- coding: utf-8 -*-
import pickle
from pylab import *
from PCV.classifiers import knn
from PCV.tools import imtools
pklist=['points_normal.pkl','points_ring.pkl']
figure()
# load 2D points using Pickle
for i, pklfile in enumerate(pklist):
with open(pklfile, 'rb') as f:
class_1 = pickle.load(f)
class_2 = pickle.load(f)
labels = pickle.load(f)
# load test data using Pickle
with open(pklfile[:-4]+'_test.pkl', 'rb') as f:
class_1 = pickle.load(f)
class_2 = pickle.load(f)
labels = pickle.load(f)
model = knn.KnnClassifier(labels,vstack((class_1,class_2)))
# test on the first point
print (model.classify(class_1[0]))
#define function for plotting
def classify(x,y,model=model):
return array([model.classify([xx,yy]) for (xx,yy) in zip(x,y)])
# lot the classification boundary
subplot(1,2,i+1)
imtools.plot_2D_boundary([-6,6,-6,6],[class_1,class_2],classify,[1,-1])
titlename=pklfile[:-4]
title(titlename)
show()
4.dense SIFT原理
dense SIFT在目标分類和場景分類有重要的應用。dense SIFT是提取我們感興趣的patches中的每個位置的SIFT特征。而通常做特征比對的SIFT算法隻是得到感興趣區域或者圖像上若幹個穩定的關鍵點的SIFT特征。如圖所示，目前關于dense SIFT提取比較流行的做法是，拿一個size固定的掩模或bounding box，以一定的步長（stepsize）在圖像上自左向右、從上到下提取dense SIFT的patch塊。
def process_image_dsift(imagename,resultname,size=20,steps=10,force_orientation=False,resize=None):
""" Process an image with densely sampled SIFT descriptors
and save the results in a file. Optional input: size of features,
steps between locations, forcing computation of descriptor orientation
(False means all are oriented upwards), tuple for resizing the image."""
im = Image.open(imagename).convert('L')
if resize!=None:
im = im.resize(resize)
m,n = im.size
if imagename[-3:] != 'pgm':
#create a pgm file
im.save('tmp.pgm')
imagename = 'tmp.pgm'
# create frames and save to temporary file
scale = size/3.0
x,y = meshgrid(range(steps,m,steps),range(steps,n,steps))
xx,yy = x.flatten(),y.flatten()
frame = array([xx,yy,scale*ones(xx.shape[0]),zeros(xx.shape[0])])
savetxt('tmp.frame',frame.T,fmt='%03.3f')
#path = os.path.abspath(os.path.join(os.path.dirname("__file__"),os.path.pardir))
#path = path + "\\python2-ch08\\win32vlfeat\\sift.exe "
if force_orientation:
cmmd = str(r"D:\python2019\code\python3-test8\sift.exe "+imagename+" --output="+resultname+
" --read-frames=tmp.frame --orientations")
else:
cmmd = str(r"D:\python2019\code\python3-test8\sift.exe "+imagename+" --output="+resultname+
" --read-frames=tmp.frame")
os.system(cmmd)
print ('processed', imagename, 'to', resultname)
5.手勢分類訓練及識别：
def get_imagelist(path):
""" Returns a list of filenames for
all jpg images in a directory. """
return [os.path.join(path,f) for f in os.listdir(path) if f.endswith('.ppm')]
def read_gesture_features_labels(path):
# create list of all files ending in .dsift
featlist = [os.path.join(path,f) for f in os.listdir(path) if f.endswith('.dsift')]
# read the features
features = []
for featfile in featlist:
l,d = sift.read_features_from_file(featfile)
features.append(d.flatten())
features = array(features)
# create labels
labels = [featfile.split('/')[-1][0] for featfile in featlist]
return features,array(labels)
def print_confusion(res,labels,classnames):
n = len(classnames)
# confusion matrix
class_ind = dict([(classnames[i],i) for i in range(n)])
confuse = zeros((n,n))
for i in range(len(test_labels)):
confuse[class_ind[res[i]],class_ind[test_labels[i]]] += 1
print ('Confusion matrix for')
print (classnames)
print (confuse)
filelist_train = get_imagelist('gesture/train1')
filelist_test = get_imagelist('gesture/test1')
imlist=filelist_train+filelist_test
# process images at fixed size (50,50)
for filename in imlist:
featfile = filename[:-3]+'dsift'
dsift.process_image_dsift(filename,featfile,10,5,resize=(50,50))
features,labels = read_gesture_features_labels('gesture/train1/')
test_features,test_labels = read_gesture_features_labels('gesture/test1/')
classnames = unique(labels)
# test kNN
k = 1
knn_classifier = knn.KnnClassifier(labels,features)
res = array([knn_classifier.classify(test_features[i],k) for i in
range(len(test_labels))])
# accuracy
acc = sum(1.0*(res==test_labels)) / len(test_labels)
print ('Accuracy:', acc)
print_confusion(res,test_labels,classnames)
使用參考資料測試的标記、分類結果為：
對照片名字标記并識别，可以看到：
使用自己手勢拍攝的照片作為訓練集，另一組自己拍攝的照片作為測試集，其中測試集中含有部分訓練集中的照片，訓練的結果為：
在這個結果裡，Accuracy的結果為手勢圖檔分類的精确性，在實驗中我發現在樣本資料很少時，Accuracy的值很容易受到樣本的值的影響，并且波動較大；而當樣本資料增多到一定程度，根據其進行訓練，再進行測試，圖檔的分類結果穩定性較好，但是缺點在于運作時間太長。而下面的混淆矩陣的每一行之和代表某一類别的真實樣本容量，每一列之和代表預測樣本容量。在使用自己的圖檔進行測試的結果中我們可以看到對于類C、F的預測全部是對的，而對于V而言，有一個被錯誤分類到了C，一個錯誤分類到了f。
由此，我們可以了解到，KNN算法的優點在于她非常簡單人性化，易于了解，易于實作，同時她适合處理多分類問題，比如猜你喜歡，推薦産品等。但她也存在着屬于時間複雜度較高，屬于懶惰算法，樣本平衡度依賴高，當出現極端情況樣本不平衡時，分類絕對會出現偏差等缺點。