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()