BÀI TẬP CÂY QUYẾT ĐỊNH CÓ ĐÁP ÁN

Home Blogs bài tập cây quyết định có đáp án
trong Data Mining and Business Intelligence...Data Mining and Business Intelligence...(Entire Site)
Tìm kiếm
jualkaosmuslim.com » Data Mining and Business Intelligence » Data Mining and Business Intelligence » Cây quyết định (Decision Tree)




Cây quyết định với bài toán phân lớp (Decision Tree with Classification Problem)

Nguyễn Văn Chức – chuc1803gmail.com

1. Giới thiệu về cây quyết định

Cây quyết định (Decision Tree) là một cây phân cấp có cấu trúc được dùng để phân lớp các đối tượng dựa vào dãy các luật (series of rules). Các thuộc tính của đối tượng (ngoại trừ thuộc tính phân lớp – Category attribute) có thể thuộc các kiểu dữ liệu khác nhau (Binary, Nominal, ordinal, quantitative values) trong khi đó thuộc tính phân lớp phải có kiểu dữ liệu là Binary hoặc Ordinal.Bạn đang xem: Bài tập cây quyết định có đáp án

Tóm lại, cho dữ liệu về các đối tượng gồm các thuộc tính cùng với lớp (classes) của nó, cây quyết định sẽ sinh ra các luật để dự đoán lớp của các đối tượng chưa biết (unseen data)

Bài viết này chỉ trình bày ứng dụng cây quyết định vào giải quyết bài toán phân lớp. Nếu bạn quan tâm đến lý thuyết về xây dựng cây quyết định như thế nào (các thuật toán xây dựng cây quyết định), các bạn có thể tìm đọc thêm các tài liệu khác hoặc đón đọc bài viết tiếp theo (Building a decision tree using ID3 Algorithm) trên https://jualkaosmuslim.com/forums/, topic Data Mining and Business Intelligence

Để giúp các bạn ứng dụng được cây quyết định trong bài toán phân lớp chúng ta cùng bắt đầu với ví dụ dưới đây:

Ta có dữ liệu (training data) về 10 đối tượng (người). Mỗi đối tượng được mô tả bởi 4 thuộc tínhlà Gender, Car Ownership, Travel Cost/Km, Income Level và 1 thuộc tính phân loại (category attribute) là Transportation mode. Trong đó thuộc tính Gender có kiểu binary, thuộc tính Car Ownership có kiểu Quantitative integer (0,1), Travel Cost/Km vàIncome Level có kiểu dữ liệu Ordinal.

Bạn đang xem: Bài tập cây quyết định có đáp án

Tranining data cho biết sự lựa chọn về loại phương tiện vận chuyển (car, bus, train) của khách dựa vào 4 thuộc tính đã cho (xem bảng).

Attributes

Classes

Gender

Car ownership

Travel Cost ($)/km

Income Level

Transportation mode

Male

0

Cheap

Low

Bus

Male

1

Cheap

Medium

Bus

Female

1

Cheap

Medium

Train

Female

0

Cheap

Low

Bus

Male

1

Cheap

Medium

Bus

Male

0

Standard

Medium

Train

Female

1

Standard

Medium

Train

Female

1

Expensive

High

Car

Male

2

Expensive

Medium

Car

Female

2

Expensive

High

Car

Dựa vào Training Data ở trên, chúng ta có thể tạo ra cây quyết định như sau



Chú ý rằng trong cây quyết định trên, thuộc tính “Income Level” không xuất hiện trong cây bởi vì dựa vào training data đã cho, thuộc tính “Travel Cost/Km” sẽ sinh ra cây quyết định tốt dùng để phân loại tốt hơn “Income Level”

Làm sao để sử dụng cây quyết định trong dự đoán lớp của các dữ liệu chưa biết

Mục đích chính của cây quyết định là dùng để dự đoán lớp (xác định lớp) của các đối tượng chưa biết (unseen data). Giả sử rằng ta có dữ liệu về 3 người với các giá trị dữ liệu đã biết về các thuộc tính Gender, Car Ownership,Travel Cost/Km, Income Level. Tuy nhiên ta chưa biết họ sẽ chọn phương tiện vận chuyển nào (Car, Bus, Train). Nhiệm vụ của chúng ta là sử dụng cây quyết định đã tạo ra để dự đoán (predict) Alex, Buddy và Cherry sẽ chọn phương tiện vận chuyển nào dựa vào 4 thuộc tính của họ. Dữ liệu dưới đây còn được gọi là Testing Data.

Person name

Gender

Car ownership

Travel Cost ($)/km

Income Level

Transportation Mode

Alex

Male

1

Standard

High

?

Buddy

Male

0

Cheap

Medium

?

Cherry

Female

1

Cheap

High

?

Chúng ta bắt đầu từ node gốc của cây (root node) từ thuộc tính Travel Cost/Km, ta thấy rằng nếu Travel Cost/Km là Expensive thì người đó sẽ chọn phương tiện là Car. Nếu Travel Cost/Kmlà standard thì họ sẽ chọn phương tiện vận chuyển là Train. Nếu Travel Cost/Km là Cheap thì cây quyết định cần tới giá trị của trường Gender của người đó, nếu Gender là Male thì chọn Bus, nếu giới tính là Female thì cây quyết định cần kiểm tra xem người đó có sử hữubao nhiêu xe hơi (Car Ownership). Nếu số xe hơi sở hữu là 0 thì người đó sẽ chọn xe Bus, nếu số xe hơi sở hữu là 1 thì người đó sẽ chọn Train.

Theo cây quyết định trên, các luật (Series of Rules) được sinh ra từ cây quyết định dùng để dự đoán như sau:

Rule 1 : If Travel cost/km is expensive then mode = car

Rule 2 : If Travel cost/km is standard then mode = train

Rule 3 : If Travel cost/km is cheap and gender is male then mode = bus

Rule 4 : If Travel cost/km is cheap and gender is female and she owns no car then mode = bus

Rule 5 : If Travel cost/km is cheap and gender is female and she owns 1 car then mode = train

Kết quả phân lớp bằng cây quyết định như sau:

Person name

Travel Cost ($)/km

Gender

Car ownership

Transportation Mode

Alex

Standard

Male

1

Train

Buddy

Cheap

Male

0

Bus

Cherry

Cheap

Female

1

Train

Cây quyết định là một phương pháp phân lớp rất hiệu quả và dễ hiểu. Tuy nhiên có một số chú ý khi sử dụng cây quyết định trong xây dựng các mô hình phân lớp như sau:

Hiệu của phân lớp của cây quyết định (Series of Rules) phụ thuộc rất lớn vào training data. Chẳn hạn cây quyết định được tạo ra bởi chỉ giới hạn 10 samples training data trong ví dụ trên thì hiệu quả ứng dụng cây quyết định để dự đoán các trường hợp khác là không cao (thường training data phải đủ lớn và tin cậy) và vì vậy ta không thể nói rằng tập các luật (Series of Rules) được sinh ra bở cây quyết định trên là tập luật tốt nhất.

Xem thêm: 3Q 360Mobi Hướng Dẫn Cách Chơi 3Q 360Mobi Trung Quốc, 3Q 360Mobi 3D

Có rất nhiều thuật toán phân lớp như ID3, J48, C4.5, CART (Classification and Regression Tree),… Việc chọn thuật toán nào để có hiệu quả phân lớp cao tuy thuộc vào rất nhiều yếu tố, trong đó cấu trúc dữ liệu ảnh hưởng rất lớn đến kết quả của các thuật toán. Chẳn hạn như thuật toán ID3 và CART cho hiệu quả phân lớp rất cao đối với các trường dữ liệu số (quantitative value) trong khi đó các thuật toán như J48, C4.5 có hiệu quả hơn đối với các dữ liệu Qualititive value (ordinal, Binary, nominal).

2. Xây dựng mô hình phân lớp bằng cây quyết định trong Weka

Trong ví dụ sau đây, tôi sẽ xây dựng mô hình phân lớp (Classification Model) bằng cây quyết định trong weka. Dữ liệu được dùng trong ví dụ này là file weather.arff có 4 thuộc tính Outlook, Temperature, Humidity, Windy và thuộc tính phân loại là Play có 2 giá trị là Yes và No. Đây là dữ liệu mô tả về khả năng có đến sân để chơi thể thao (tennis chẳn hạn) hay không của những người chơi thể thao phụ thuộc vào thời tiết.



Rule 1: If outlook = “sunny” and humidity

Rule 2: If outlook = “sunny” and humidity > 75 then Play = “no”

Rule 3: If outlook = “overcast” then Play= “yes”

Rule 4: If outlook = “rainy” and windy = TRUE then Play =”no”

Rule 5: If outlook = “rainy” and windy = FALSE then Play =”yes”

Như vậy, với cây quyết định được sinh ra bởi training data trên, theo Rule 3 ta xác định giá trị cho trường phân lớp (play) của unseen data trên là “yes” (nghĩa là với thời tiết hôm nay là : outlook (overcast), temperature (85), humidity (80), windy (true) thì mọi người sẽ đến sân chơi tennis). Sử dụng cây quyết định trên sẽ giúp cho người quản lý dự đoán khả năng đến sân chơi tennis khách hàng tùy theo thời tiết.

PS. Next topic : Building a decision tree using ID3 Algorithm. All comments please send to chucnv

Bài viết xem nhiều