Computer Vision

[Image Classification] Decision Trees

Xin chào, trong bài viết này chúng ta sẽ tìm hiểu về Decision Trees – một thuật toán đơn giản và mạnh mẽ được sử dụng phổ biến trong Machine Learning.


DECISION TREES LÀ GÌ?

Nếu bạn nào đã học về cấu trúc dữ liệu chắc chắn sẽ biết đến Binary Tree (Cây nhị phân) và nguyên lý hoạt động của nó. Decision Trees cũng hoạt động tương tự như vậy, bài toán phân loại dữ liệu sẽ được đơn giản hóa thành một tập hợp các lựa chọn từ các entry của Feature Vector. Hãy xem xét ví dụ dưới đây.

decisiontree

Hình 1 – Một ví dụ về Decision Tree

Decision Tree ở hình 1 đã mô tả lại cách tôi quyết định sẽ làm gì trong một ngày. Nếu hôm nay là ngày nghỉ nhưng thời tiết xấu thì tôi sẽ ở nhà và ngủ, tuy nhiên nếu thời tiết mát mẻ thì tôi sẽ đi phượt cùng ghệ, còn có lỡ nắng quá thì chúng tôi sẽ đi tắm biển. Còn nếu hôm nay là ngày thường, tôi sẽ phải đi làm hoặc đến trường, tùy vào thời gian biểu.

Những hình vuông và ellipse chứa điều kiện và quyết định được gọi chung là các node. Hình vuông trên cùng (“Ngày nghỉ”) là root-node, các hình ellipse ở dưới cùng được gọi là leaf-node. Leaf-node sẽ chứa các quyết định cuối cùng như “Ở nhà ngủ”, “Đi phượt”. Các node bình thường khác được gọi là child-node (“Đi làm”, “Trời đẹp”, “Thời tiết mát mẻ”)chứa các điều kiện cần được kiểm tra trước khi ra quyết định.

Với Decision Tree, chúng ta có thể kết hợp nhiều đặc điểm để phân loại các đối tượng, chẳng hạn như màu sắc, hình dạng, kết cấu và hoa văn (texture & pattern). Trong đó, mỗi đặc điểm sẽ đóng vai trò là một điều kiện để đưa ra quyết định.

Nhưng làm thế nào để có thể tạo ra một Decision Tree từ một tập hợp dữ liệu? Trên thực tế, chúng ta sẽ áp dụng các thuật toán như ID3, C4.5CART để tự động xây dựng một Decision Tree từ training data.

Trước khi tìm hiểu về giải thuật, chúng ta cần tìm hiểu một chút về hàm Entropy.

Cho một phân phối xác suất của một biến x có thể nhận n giá trị khác nhau x_1, x_2,..., x_n, với xác suất để x nhận các giá trị này p_i=p(x=x_i) với 0 \leq p_i \leq 1\sum p_i = 1. Entropy của phân phối này là:

H(p) = -\sum_{i=1}^n p_i\log_{2}(p_i)

Giả sử chúng ta có một tập dữ liệu chứa số tự nhiên được phân loại thành hai nhóm “số chẵn” và “số lẻ”.

  • Nếu tập dữ liệu chứa toàn số chẵn thì xác suất chúng ta chọn được một số chẵn từ tập hợp trên chắc chắn là 1, tức là p_i=1, dẫn đến entropy có giá trị H=H_{min}=0, điều này tương tự khi tập dữ liệu chứa toàn số lẻ.
  • Nếu số lượng số chẵn và lẻ trong tập dữ liệu bằng nhau, tức là p_i=0,5 thì entropy sẽ có giá trị H=H_{max}=1.

Vì tính chất này mà hàm Entropy được dùng để đo độ vẩn đục của dữ liệu (dữ liệu được gọi là vẩn đục nhất khi xác suất chọn được số chẵn bằng với khi chọn số lẻ). Xem hình 2 để hình dung rõ hơn.

dt_entropy

Hình 2 – Hàm Entropy của tập phân phối xác suất


THUẬT TOÁN TRAINING CART

Thư viện Skicit-Learn sử dụng thuật toán CART (Classification And Regression Tree) để train Decision Tree. Bước đầu tiên trong việc xây dựng một Decision Tree là chọn ra một feature (đặc trưng) k từ Feature Vector và một giá trị threshold t_k để phân chia dữ liệu thành hai subsets, sao cho mỗi subset ít bị vẩn đục nhất (giá trị Entropy nhỏ nhất).

Cost function:

J(k, t_k) = \frac{m_{left}}{m}H_{left} + \frac{m_{right}}{m}H_{right}

Trong đó:

  • m_{left}, m_{right} – số lượng instances trong mỗi subset;
  • m – tổng số lượng instance trong hai subset;
  • H_{left}, H_{right} – giá trị Entropy của mỗi subset.

Mỗi subset sẽ tiếp tục được phân chia theo ý tưởng ở trên cho đến khi đạt được max depth hoặc giá trị Entropy không thể nhỏ hơn được nữa.


ÁP DỤNG DECISION TREE ĐỂ PHÂN LOẠI ẢNH PHONG CẢNH

Với dataset là các tấm ảnh phong cảnh về bờ biển, rừng và núi, nhiệm vụ của chúng ta là phân loại chúng ba category “Beach”, “Forest” và “Mountain”. Các bức ảnh trong dataset được đặt tên theo quy tắc để dễ dàng tách được label tương ứng với nó. Hai folder data và test sẽ chứa traning set và testing set.

dataset

Hình 3 – dataset

Để phân loại các bức ảnh này chúng ta sẽ sử dụng cả đặc trưng về màu sắc và kết cấu của từng bức ảnh rồi đưa chúng vào thuật toán Decision Tree.

Đối với màu sắc, chúng ta chỉ tính giá trị trung bình và độ lệch chuẩn của cường độ màu sắc với từng kênh màu, nhận được một Feature Vector 6-d.  Đối với kết cấu, chúng ta sử dụng Haralick Texture và nhận được một Feature Vector 13-d.

Ghép hai Feature Vector này lại chúng ta nhận được một Feature Vector 19-d. Vì Haralick Texture chiếm đến tỉ lệ đến 16/19 nên quá trình “học” sẽ bị ảnh hưởng nhiều hơn bởi Haralick Texture.

Source code: DecisionTree.py

from sklearn.tree import DecisionTreeClassifier
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 = DecisionTreeClassifier(random_state=84)
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 DecisionTreeClassifier từ thư viện sklearn;
– Dòng 9-16: function describe được dùng để trích xuất đặc trưng về màu sắc và kết cấu cho các bức ảnh;
– Dòng 37,38: training dữ liệu.

Execution:
$ python DecisionTree.py -d data -t test

Output:
resultresult1result2


SUMMARY

Qua bài viết này chúng ta đã tìm hiểu về Decision Tree, cách xây dựng và áp dụng Decision Tree vào bài toán phân loại hình ảnh. Cảm ơn các bạn đã theo dõi bài viết.

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

Reference:
[1] machinelearningcoban.com – Decision Tree.
[2] sklearn.tree.DecisionTreeClassifier.


Nếu có câu hỏi, các bạn hãy để lại bình luận nhé.

One thought on “[Image Classification] Decision Trees

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