Computer Vision

[Image Classification] k-Nearest Neighbor classification

Xin chào, trong bài viết này chúng ta sẽ tìm hiểu về k-Nearest Neighbor classifier được sử dụng rộng rãi trong Computer Vision.


HIỂU VỀ K-NEAREST NEIGHBOR CLASSIFIER

Cho đến nay k-Nearest Neighbor (viết tắt là kNN) là thuật toán phân loại hình ảnh đơn giản nhất, nó đơn giản đến mức chẳng có một tí gì gọi là “learning” cả, kNN phân loại hình ảnh dựa trên khoảng cách giữa các Feature Vectors.

Thuật toán kNN phân loại một đối tượng bằng cách tìm ra category phù hợp với nó nhất trong số k đối tượng có Feature Vector tương tự nó nhất (còn gọi là data point). Mỗi data point trong số k data points này sẽ đưa ra đóng góp một phiếu bầu cho category tương ứng. Cuối cùng, category nào có số phiếu bầu chọn cao nhất sẽ được gán cho đối tượng. Tất nhiên, k luôn luôn phải là một số lẻ.

Figure 1 là một ví dụ về thuật toán kNN.

knn

Figure 1 – k-Nearest Neighbor algorithm

Nhìn vào Figure 1, hình tròn màu xanh lá chính là đối tượng cần được phân loại, xung quanh nó có các hình vuông (Category = class 1) và hình tam giác (Category = class 2) khác.

  • Khi k=1, category của đối tượng mà tương đồng với nó nhất sẽ được chọn, đó chính là hình vuông;
  • Khi k=3, trong số 3 đối tượng tương đồng với nó nhất có đến 2 hình tam giác, do đó category tam giác sẽ được chọn.

Khi áp dụng kNN chúng ta cần chú ý đến hai yếu tố. Đầu tiên là giá trị của k, tức là số lượng neighbor sẽ được xem xét để phân loại đối tượng. Nếu k quá bé thì kết quả rất dễ bị ảnh hưởng bởi nhiễu, tuy nhiên nếu k quá lớn thì độ lệch cũng sẽ lớn hơn.

Yếu tố tiếp theo chính là phương pháp so sánh Feature Vector. Chúng ta sẽ áp dụng Euclidean Distance, Manhattan Distance hay Chi-Squared Distance?

Để giải quyết các vấn đề này, ngoài Traning Set và Testing Set, chúng ta sẽ cần thêm Validation Set để điều chỉnh các tham số cho phù hợp. Các bước thực hiện như sau:

  1. Train bộ classifier với Training Set, sử dụng nhiều giá trị k và Distance Function khác nhau để đánh giá độ chính xác;
  2. Đánh giá hiệu năng của bộ classifier với từng tham số k, Distance Function khác sau bằng cách sử dụng Validation Set và chọn ra các tham số tốt nhất;
  3. Train bộ classifier với các tham số tốt nhất vừa nhận được;
  4. Đánh giá hiệu năng của bộ classifier với Testing Set.

NHẬN DẠNG CHỮ SỐ VIẾT TAY VỚI BỘ DỮ LIỆU MNIST

MNIST là một dataset được sử dụng phổ biến trong nghiên cứu Computer Vision và Machine Learning. Trong bộ thư viện scikit-learn đã có một phần của MNIST, gồm 1797 bức ảnh grayscale 8×8 đã được xử lý rất tốt. Mục đích của chúng ta là train một bộ classifier dựa trên các bức ảnh raw này. Các bước thực hiện như sau:

  1. Chuẩn bị dataset, gồm 1797 bức ảnh grayscale 8×8;
  2. Chia dataset thành 3 phần: Traning Set, Validation Set và Testing Set;
  3. Chiết xuất đặc trưng, vì chúng ta sẽ sử dụng các cường độ điểm ảnh có trong bức ảnh grayscale 8×8 nên bước này không có gì đặc biệt;
  4. Training bộ classifier;
  5. Đánh giá hiệu năng của bộ classifier.

Source code: kNN.py

from sklearn.neighbors import KNeighborsClassifier
from sklearn.metrics import classification_report
from sklearn.model_selection import train_test_split
from sklearn import datasets
from skimage import exposure
import numpy as np
import imutils
import cv2

mnist = datasets.load_digits()

(trainData, testData, trainLabels, testLabels) = train_test_split(np.array(mnist.data),
                                                mnist.target, test_size=0.25, random_state=42)

(trainData, valData, trainLabels, valLabels) = train_test_split(trainData, trainLabels,
                                                test_size=0.1, random_state=84)

print("training data points: {}".format(len(trainLabels)))
print("validation data points: {}".format(len(valLabels)))
print("testing data points: {}".format(len(testLabels)))

kVals = range(1,30,2)
accuracies = []

for k in range(1,30,2):
    model = KNeighborsClassifier(n_neighbors=k)
    model.fit(trainData, trainLabels)

    score = model.score(valData, valLabels)
    print("k={}, accuracy={:.2f}%".format(k, score*100))
    accuracies.append(score)

i = int(np.argmax(accuracies))
print("k={} achieved highest accuracy of {:.2f}% on validation data".format(kVals[i], accuracies[i] * 100))

model = KNeighborsClassifier(n_neighbors=kVals[i])
model.fit(trainData, trainLabels)
predictions = model.predict(testData)

print("EVALUATION ON TESTING DATA")
print(classification_report(testLabels, predictions))

for i in list(map(int, np.random.randint(0, high=len(testLabels), size=10))):
    image = testData[i]
    prediction = model.predict(image.reshape(1,-1))[0]

    image = image.reshape((8,8)).astype("uint8")
    image = exposure.rescale_intensity(image, out_range=(0,255))
    image = imutils.resize(image, width=32, inter=cv2.INTER_CUBIC)

    print("I think that digit is: {}".format(prediction))
    cv2.imshow("Image", image)
    cv2.waitKey(0

Giải thích:
– Dòng 10-15: chuẩn bị Training Set, Validation Set và Testing Set;
– Dòng 22-34: training bộ classifier với các giá trị k khác nhau rồi đánh giá, lựa chọn là giá trị k tốt nhất;
– Dòng 36-41: áp dụng giá trị k tìm được ở trên để traning bộ classifier;
– Dòng 43-53: sử dụng bộ classifier để phân loại một số bức ảnh chứa chữ số viết tay trong Testing Set.

Output:
Các bạn chạy đoạn code trên và tự đưa ra nhận xét nhé.

result

Figure 2 – Training result

Sau khi chạy đoạn code trên các bạn sẽ nhận được một bảng kết quả như Figure 2. Có thể thấy rằng độ chính xác trung bình lên đến 98%, điều này là do các bức ảnh trong MNIST dataset đã được xử lý rất tốt. Trong các ứng dụng thực tế, dataset của chúng ta sẽ không thể hoàn hảo như MNIST, chúng ta sẽ phải trích xuất vector đặc trưng của từng bức ảnh thay vì chỉ dựa vào cường độ điểm ảnh như ví dụ trên.


ƯU VÀ NHƯỢC ĐIỂM CỦA KNN

Ưu điểm lớn nhất của kNN là sự đơn giản và không tốn thời gian traning, vì thực sự nó chẳng “học” gì cả, đơn giản là tính Distance giữa các Feature Vector rồi đưa ra dự đoán. Tuy nhiên, mọi thứ đều có cái giá của nó, khi sử dụng bộ classifier kNN để phân loại các đối tượng, các Feature Vector trong Testing Set sẽ lần lượt được so sánh với Traning Set, thời gian thực hiện so sánh sẽ là tuyến tính O(N) và điều này sẽ rất không hiệu quả khi chúng ta có một dataset lớn.

kNN phù hợp với các ứng dụng nhỏ, yêu cầu độ chính xác không cao. Ngoài ra, kNN còn được dùng như một mốc đo sự chính xác của bộ classifier, từ đó có thể áp dụng các kỹ thuật, giải thuật nâng cao hơn.


SUMMARY

Như vậy chúng ta đã tìm hiểu về thuật toán k-Nearest Neighbor và ứng dụng vào bài toán nhận dạng chữ số viết tay ở mức cơ bản. Cảm ơn các bạn đã theo dõi bài viết.

Thân ái và quyết thắng.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s