K-Nearest Neighbour

Understanding k-Nearest Neighbour

วัตถุประสงค์

• เข้าใจแนวคิดของ k-Nearest Neighbour

Theory

• kNN เป็นขั้นหนึ่งในการตอนวิธีการที่ง่ายที่สุดของการจัดหมวดหมู่ที่มีอยู่สำหรับการเรียนรู้ภายใต้กำกับดูแล เป็นไอเดียโดยการหาพื้นที่ใกล้เคียง ทดสอบในพื้นที่นั้น และหาพื้นทีว่าง โดยดูรูปเพิ่มเติม

kNN In OpenCV

• จะสาธิตวิธีการหา 2 กลุ่ม ดังั้นเราจะต้องติดป้ายให้กับเหล่ากลุ่มที่เป็นสีแดง ให้เท่ากับ Class 0 และกลุ่มของสีฟ้าเป็น Class-1 และสร้างจำนวนกลุ่มมา 25 กลุ่ม และติดป้ายให้ทั้ง 2 ชั้น Class0 , Class 1 โดยใช้ Random Number Generator ใน Numpy
• จากนั้นจะทำการ plot ด้วยฟังก์ชั่น Matplotlib ให้สีแดงนั้นแสดงเป็น สามเหลี่ยมสีแดง และสีฟ้าแสดงเป็นสี่เหลี่ยม

Code Example

import cv2
import numpy as np
import matplotlib.pyplot as plt
 
# Feature set containing (x,y) values of 25 known/training data
trainData = np.random.randint(0,100,(25,2)).astype(np.float32)
 
# Labels each one either Red or Blue with numbers 0 and 1
responses = np.random.randint(0,2,(25,1)).astype(np.float32)
 
# Take Red families and plot them
red = trainData[responses.ravel()==0]
plt.scatter(red[:,0],red[:,1],80,'r','^')
 
# Take Blue families and plot them
blue = trainData[responses.ravel()==1]
plt.scatter(blue[:,0],blue[:,1],80,'b','s')
 
plt.show()

• จะได้ผมลัพธ์คล้ายกัน เนื่องจากการใช้ฟังก์ชั่นสุ่มตัวเลขออกมา เลยจะได้ข้อมูลที่แตกต่างกันทุกๆครั้งเมื่อ RUN CODE

• ถัดไปจะเริ่มขั้นตอน kNN และผ่านการ trainData และการตอบสนองในการ Train kNN นั้นจะสร้าง construct a search tree

• จากนั้นจะได้ new-corner และถูก classify โดยกลุ่มของมันเองโดยอัตโนมัตด้วยการใช้ kNN เข้ามาช่วย ก่อนที่จะไปใช้ kNN เราจำเป็นต้องเรียนรู่บางอย่างเกี่ยวกับการทดสอบข้อมูล และข้อมูลเหล่านั้นจำเป็นต้องเป็นชนิด point array with size โดยที่ numberoftestdata×numberoffeatures เมื่อเราค้นหาจุดที่ใกล้เคียงของ new-corner โดยจะสามารถหาได้ว่าจะนวน neighbours (จุดใกล้เคียง) หากเราต้องการ

โดยการติดป้ายชื่อให้กับ new-corner จะขึ้นอยู่กับ ทฤษฏี kNN โดยเราจะเห็นก่อนหน้านี้ได้ว่า หากคุฯต้องการ Nearest Neighbour algorithm โดยเฉพาะค่า k=q เมื่อ k คือตัวเลขของ neighbours

• ต่อไปเป็นการหา New comer โดยจะติดป้ายสีเขียวให้

newcomer = np.random.randint(0,100,(1,2)).astype(np.float32)
plt.scatter(newcomer[:,0],newcomer[:,1],80,'g','o')
 
knn = cv2.KNearest()
knn.train(trainData,responses)
ret, results, neighbours ,dist = knn.find_nearest(newcomer, 3)
 
print "result: ", results,"\n"
print "neighbours: ", neighbours,"\n"
print "distance: ", dist
 
plt.show()

• โดยจะได้ผลลัพธ์ คือ

 result:  [[ 1.]]
 neighbours:  [[ 1.  0.  1.]]
 distance:  [[ 17.  29.  281.]]

• โดยผลลัพธ์ จะได้ไม่เท่ากันเพราะ RANDOM ต่างกัน
  • • (0 คือแดง , 1 คือฟ้า) 17 , 29 , 281 คือระยะห่าง

Code Full แก้ไขสำหรับ OpenCV 3.1.0

import cv2
import numpy as np
import matplotlib.pyplot as plt

# Feature set containing (x,y) values of 25 known/training data
trainData = np.random.randint(0,100,(25,2)).astype(np.float32)

# Labels each one either Red or Blue with numbers 0 and 1
responses = np.random.randint(0,2,(25,1)).astype(np.float32)

# Take Red families and plot them
red = trainData[responses.ravel()==0]
plt.scatter(red[:,0],red[:,1],80,'r','^')

# Take Blue families and plot them
blue = trainData[responses.ravel()==1]
plt.scatter(blue[:,0],blue[:,1],80,'b','s')

newcomer = np.random.randint(0,100,(1,2)).astype(np.float32)
plt.scatter(newcomer[:,0],newcomer[:,1],80,'g','o')

# knn = cv2.ml.KNearest_create()
# knn.train(trainData,responses)
knn = cv2.ml.KNearest_create()
knn.train(trainData,cv2.ml.ROW_SAMPLE,responses)
ret, results, neighbours, dist = knn.findNearest(newcomer, 3)

print "result: ", results,"\n"
print "neighbours: ", neighbours,"\n"
print "distance: ", dist

plt.show()

OCR of Hand-written Data using kNN

วัตถุประสงค์

• ในเรื่องนี้จะนำ kNN เพื่อสร้าง OCR แอพลิเคชั่นแบบง่ายๆ
• ทดลองหาตัวอักษร หรือ ตัวเลข จากรูปที่นำเข้ามา ด้วย OpenCV

OCR of Hand-written Digits

• ในเป้าหมายของของการสร้าง application เพื่ออ่าน ตัวอักษรหรือตัวเลขด้วยมือนั้น สำหรับบมนี้จะใช้ ใช้ train_data และ test_data ใน OpenCV โดยจะ Print ความแม่นยำออกมาเป็น %

ตาม Code ต่อไปนี้

import numpy as np
import cv2
from matplotlib import pyplot as plt
 
img = cv2.imread('digits.png')
gray = cv2.cvtColor(img,cv2.COLOR_BGR2GRAY)
 
# Now we split the image to 5000 cells, each 20x20 size
cells = [np.hsplit(row,100) for row in np.vsplit(gray,50)]
 
# Make it into a Numpy array. It size will be (50,100,20,20)
x = np.array(cells)
 
# Now we prepare train_data and test_data.
train = x[:,:50].reshape(-1,400).astype(np.float32) # Size = (2500,400)
test = x[:,50:100].reshape(-1,400).astype(np.float32) # Size = (2500,400)
 
# Create labels for train and test data
k = np.arange(10)
train_labels = np.repeat(k,250)[:,np.newaxis]
test_labels = train_labels.copy()
 
# Initiate kNN, train the data, then test it with test data for k=1
knn = cv2.KNearest()
knn.train(train,train_labels)
ret,result,neighbours,dist = knn.find_nearest(test,k=5)

# Now we check the accuracy of classification
# For that, compare the result with test_labels and check which are wrong
matches = result==test_labels
correct = np.count_nonzero(matches)
accuracy = correct*100.0/result.size
print accuracy

• ในเบื้องต้นนั้น ผลลัพธ์ที่ได้มา = 91% โดยการทำงานให้ดีขึ้นนั้นควรจะ save ด้วย Numpy ไว้ด้วย เป็นไฟล์ npz โดยฟังก์ชั่น np.savez , และทำการ load มาใช้งาน np,load
  • ตัวอย่างการ Save

# save the data
np.savez('knn_data.npz',train=train, train_labels=train_labels)
 
 # Now load the data
with np.load('knn_data.npz') as data:
    print data.files
    train = data['train']
    train_labels = data['train_labels']

OCR of English Alphabets

• ต่อมาเป็นการทำเหมือนกันกับตัวเลขแต่จะเป็นการอ่านหรือหาตัวอกษรเอาท์ฟาเบทส์ โดยจะนำไฟล์ที่ Save *. หรือ ในต่อไปนี้จะนำไฟล์ชื่อว่า [letter-recognition.data] มา load เพื่อใช้

ตาม Code ต่อไปนี้

import cv2
import numpy as np
import matplotlib.pyplot as plt
 
# Load the data, converters convert the letter to a number
data= np.loadtxt('letter-recognition.data', dtype= 'float32', delimiter = ',',
                    converters= {0: lambda ch: ord(ch)-ord('A')})
 
# split the data to two, 10000 each for train and test
train, test = np.vsplit(data,2)
 
# split trainData and testData to features and responses
responses, trainData = np.hsplit(train,[1])
labels, testData = np.hsplit(test,[1])
 
# Initiate the kNN, classify, measure accuracy.
knn = cv2.KNearest()
knn.train(trainData, responses)
ret, result, neighbours, dist = knn.find_nearest(testData, k=5)
 
correct = np.count_nonzero(result == labels)
accuracy = correct*100.0/10000
print accuracy

• โดยได้ผลลัพธ์ 93.22%