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 – chuc1803@gmail.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.

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 http://bis.net.vn/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ính là 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.

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/Km là 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ữu bao 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

Dựa vào các luật này, việc dự đoán lớp cho các dữ liệu chưa biết (unseen data hay Testing data) rất đơn giản. Trong ví dụ này, Alex có giá trị của thuộc tính Travel Cost/Km là Standard nên sẽ chọn phương tiện là Train (Rule 2) mà không cần quan tâm đến các thuộc tính khác của Alex. Buddy có giá trị của thuộc tính Travel Cost/Km là Cheap và Gender của anh ta là Male nên anh ta sẽ chọn Bus (Rule 3). Cheery cũng có giá trị thuộc tính Travel Cost/Km là Cheap nhưng Gender là Female và sở hữu 1 xe hơi cho nên theo cây quyết định trên (Rule 5) cô ta sẽ chọn phương tiện là Train.

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

 

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.

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.

Training data như sau

Giả sử hôm nay các thông tin về thời tiết mà người quản lý sân tennis có được là

Vấn đề đặt ra là với thời tiết như vậy, người chơi tennis có đến sân để chơi hay không? (Play = Yes hay No). Việc dự đoán này sẽ giúp cho người quản lý sân giảm được rất nhiều chi phí quản lý sân như  điều chỉnh (tăng hoặc giảm) số nhân viên phục vụ cũng như các dịch vụ khác nhằm phục vụ tốt hơn nhu cầu của người chơi tennis.

 Load file weather.arff trong Weka (Tải file weather.arff tại đây)

Chọn tab Classify , chọn tree và chọn thuật toán J48 (có thể chọn các thuật toán khác để so sánh hiệu quả phân lớp của các thuật toán khác nhau như ID3, SimpleCart,….)

 

Decision tree được sinh ra theo training data trên

 

Các luật (Series of Rules) được sinh ra bởi cây quyết định

Rule 1:  If outlook = “sunny” and humidity <= 75 then Play = “yes”

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@ud.edu.vn. Thank you and welcome!

@import url(/cutesoft_client/cuteeditor/communityservercommon.css);

anh ơi biết được nhân tố quyết định trong cây ID3 rùi thì vẽ thế nào hả anh

Thuật toán ID3 sử dụng Entropy để tìm node gốc (root). Tiếp tục như vậy cho đến khi xây dựng xong cây

em cảm ơn anh rất nhiều vì bài viết anh gửi cho em nhưng em đã thi xong môn đó rùi anh ah.

Em chào thầy,em có 1 bài tập làm trên dữ liệu poker hands,em có dược 2 tập tin du lieu và train và test,khi du liệu train có 25000 Instances,còn dữ liệu test có 1.000.000,em đã tiền xử lý dữ liệu với bài hướng dẫn của thầy.khi ấy việc chọn mô hình phân loại là id3 hay j48 là dựa vào yếu tố nào dể chọn ko ạ,và còn vấn đề tính cân bằng của dữ liệu huấn luyện có ảnh hưởng đến việc xây dựng bộ phân loại không ạ,em xin cảm ơn

Dạ em cảm ơn thầy, em hiểu rồi.

Em chào anh Chức ạ ! Bài của anh rất ý nghĩa ạ. Dạ cho em hỏi cách sử dụng thuật toán ID3 và C4.5 với WEKA với ạ.  Trong tab Classify/tree  thì không chọn được  id3 vì nó ẩn ạ, và không có C4.5 ở đó ạ. Vậy thì phải làm sao để dùng đc 2 thuật toán này trên WEKA ạ ? Em chân thành cảm ơn ạ.