Computer Vision

[Image Classification] Random Forests

Xin chào, trong bài viết này chúng ta sẽ tìm hiểu về Random Forest, một thuật toán Machine Learning dựa trên Decision Trees, cho phép cải thiện độ chính xác khi phân loại hình ảnh.


RANDOM FOREST LÀ GÌ?

Random Forest là một ensemble classification method (phương pháp phân loại hòa hợp), tức là áp dụng phối hợp nhiều thuật toán phân loại khác nhau (như là kNN, Logistic Regression, SVM, Decision Tree) để đạt được kết quả phân loại tốt nhất.

Trong phạm vi bài viết này chúng ta sẽ xây dựng một Random Forest từ nhiều Decision Tree (nhiều cây thì sẽ tạo thành rừng) sau đó sử dụng Random Forest để đưa ra dự đoán.

Architecture-of-the-random-forest-model

Hình 1 – Random Forest

Từ hình 1 chúng ta thấy rằng Random Forest được cấu thành bởi một số Decision Tree. Các Decision Tree này cùng nhận input là Feature Vector x và đưa ra quyết định về category của x. Các quyết định này sẽ được tổng hợp lại để chọn ra quyết định cuối cùng.


BẤT ĐẲNG THỨC JENSEN

Nền tảng lý thuyết của Random Forest là bất đẳng thức Jensen, chúng ta sẽ tìm hiểu về nó một chút nhé.

Bất đẳng thức Jensen: giả sử f là hàm liên tục và lồi (convex function) trên I. Nếu x_1, x_2, ..., x_n \in I khi đó ta có:

f(\frac{x_1+x_2+...+x_n}{n}) \leq \frac{f(x_1)+f(x_2)+...+f(x_n)}{n}

Dấu bằng xảy ra khi x_1=x_2=...=x_n. Bất đẳng thức đảo chiều khi f là hàm lõm (concave function) trên I.

GNBZ4

Hình 2 – Hàm lồi (convex) và hàm lõm (concave)

Áp dụng vào bài toán phân loại, ta có thể suy ra rằng việc áp dụng tổng hợp nhiều mô hình sẽ cho sai số nhỏ hơn hoặc bằng với trung bình sai số của từng mô hình riêng lẻ.


BOOTSTRAPPING

Bootstrapping là một kỹ thuật lấy mẫu có trùng lặp từ một dataset (sample with replacement). Ví dụ khi chúng ta thực hiện Bootstrapping N lần một dataset, sẽ có một số Feature Vector được lấy mẫu nhiều lần (sẽ có sự trùng lặp), trong khi đó một số khác sẽ không được lấy mẫu.

Thông thường, nếu dataset có N Feature Vector thì chúng ta sẽ thực hiện Bootstrapping N lần. Giả sử chúng ta có dataset gồm 20 bức ảnh, trích xuất được các Feature Vector 10-d (xem hình 3). Sau khi thực hiện bootstrapping 20 lần chúng ta sẽ nhận được kết quả như hình 4.

bootstrap2

Hình 3 – Dataset trước khi bootstrapping

bootstrap

Hình 4 – Sau khi bootstrapping 20 lần

Trong số 20 Feature Vector có trong Dataset ban đầu, chỉ có 12 Feature Vector được chọn (gồm #1, #3, #5, #6, #9, #10, #12, #13, #16, #17, #18 và #20) và một vài trong số chúng được chọn nhiều lần.

Bootstrapping thường được sử dụng để tăng độ chính xác cho các thuật toán machine learning cũng như giảm thiểu nguy cơ overfitting.

Cũng cần nói thêm về overfitting. Overfitting ám chỉ đến các mô hình được training quá tốt. Mô hình này “học” tất cả các chi tiết (kể cả nhiễu) có trong Training Set đến mức nó tác động tiêu cực lên hiệu suất của chính nó khi áp dụng lên các tập dữ liệu mới, vì trong tập dữ liệu mới, các nhiễu (noise) mà nó “học” được từ Training Set không hề tồn tại. Điều này làm mất đi tính tổng quát của mô hình.


TÍNH NGẪU NHIÊN TRONG RANDOM FOREST

Chúng ta đã biết rằng Decision Tree phân chia dữ liệu vào các nhánh bằng cách chọn ra các feature phù hợp trong Feature Vector. Tuy nhiên, đối với Random Forest, sẽ chỉ có một phần của Feature Vector (không phải toàn bộ Feature Vector) được sử dụng để chọn ra các feature nhằm phân tách dữ liệu và nó thực sự cải thiện độ chính xác.

Trên thực tế, chúng ta sẽ lấy căn bậc hai hoặc logarit của kích thước của Feature Vector để xác định số lượng feature được sử dụng. Trở lại ví dụ ở trên, chúng ta có các Feature Vector 10-d, với \sqrt {10}=3,16\simeq3 chúng ta sẽ ngẫu nhiên chọn ra 3 feature, từ đó tiếp tục chọn ra các feature phù hợp nhất để phân tách dữ liệu, xem hình 5.

random

Hình 5 – Chọn ra 3 feature từ Feature Vector 10-d

Như vậy chỉ có các feature F2, F5 và F10 được lựa chọn từ Feature Vector.


TỔNG HỢP KẾT QUẢ

Mỗi Decision Tree sẽ đưa ra một quyết định về category của bức ảnh, các quyết định này sau đó sẽ được tổng hợp lại và kết quả cuối cùng sẽ được đưa ra, xem hình 6.

rf_example

Hình 6 – Tổng hợp kết quả từ các Decision Trees


ÁP DỤNG RANDOM FOREST ĐỂ PHÂN LOẠI HÌNH ẢNH

Sử dụng lại dataset đã dùng ở bài Decision Tree, chúng ta sẽ áp dụng Random Forest để phân loại các bức ảnh phong cảnh với thư viện scikit-learn.

Source code:

from sklearn.ensemble import RandomForestClassifier
import numpy as np
import argparse
import mahotas
import cv2
import imutils
from glob import glob

def describe(image):
    (mean, stds) = cv2.meanStdDev(cv2.cvtColor(image, cv2.COLOR_BGR2HSV))
    colorStats = np.concatenate([mean, stds]).flatten()

    gray = cv2.cvtColor(image, cv2.COLOR_BGR2GRAY)
    haralick = mahotas.features.haralick(gray).mean(axis=0)

    return np.hstack([colorStats, haralick])

ap = argparse.ArgumentParser()
ap.add_argument("-d", "--dataset", required=True)
ap.add_argument("-t", "--test", required=True)
args = vars(ap.parse_args())

print("[INFO] Extracting features...")
imagePaths = glob(args["dataset"]+"/*")
trainLabels = []
trainData = []

for imagePath in imagePaths:
    image = cv2.imread(imagePath)
    label = imagePath[imagePath.rfind("/")+1:].split("-")[0]

    features = describe(image)
    trainLabels.append(label)
    trainData.append(features)

print("[INFO] Training model...")
model = RandomForestClassifier(n_estimators=20, random_state=42)
model.fit(trainData, trainLabels)

print("[INFO] Testing...")
imagePaths = glob(args["test"]+"/*")

for imagePath in imagePaths:
    image = cv2.imread(imagePath)
    features = describe(image)
    prediction = model.predict(features.reshape(1,-1))[0]
    image = imutils.resize(image, width=640)
    cv2.putText(image, prediction, (20,30), cv2.FONT_HERSHEY_SIMPLEX, 1.0, (0,255,0), 2)
    cv2.imshow("image", image)
    cv2.waitKey(0)

Giải thích:
– Dòng 1: import class RandomForestClassifier từ thư viện sklearn;
– Dòng 37: khởi tạo đối tượng RandomForestClassifier với số lượng Decision Tree n_estimators = 20.


SUMMARY

Qua bài viết này chúng ta đã tìm hiểu về thuật toán Random Forest và cách ứng dụng vào bài toán phân loại hình ảnh. Cần chú ý rằng, Random Forest chỉ phù hợp khi các Feature Vector có kích thước lớn và chứa đựng nhiều thông tin. Vì phạm vi của bài viết chỉ là giới thiệu về thuật toán và cách áp dụng vào Computer Vision nên chúng ta không tìm hiểu thật kỹ. Cảm ơn các bạn đã theo dõi bài viết.

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

Reference:
[1] Bootstrap aggregating.
[2] Overfitting and Underfitting With Machine Learning Algorithms.
[3] sklearn.ensemble.RandomForestClassifier

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