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 – [email protected] 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: 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. 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 [email protected]. Thank you and welcome! |
