Cây quyết định

• Dùng cấu trúc cây để đưa ra một hàm phân lớp cần học (hàm mục tiêu có giá trị rời rạc)

Figure 1: Cây ra quyết định chỉ ra khách hàng nào thường mua máy tính

• Một cây quyết định có thể được biểu diễn (diễn giải) bằng một tập các luật IF-THEN (dễ đọc và dễ hiểu)
• Được áp dụng thành công trong rất nhiều các bài toán ứng dụng thực tế

Ví dụ về cây quyết định

Cho tập dữ liệu sau:

Có điểm dữ liệu mới với giá trị thuộc tính x = 1, màu của điểm này nên là gì? (nên phân vào lớp nào?)

Đó là cây ra quyết định đơn giản với một node phân loại kiểm tra xem x < 2.

Nếu kểm tra x < 2, chúng ta lẫy nhánh trái và gán nhãn màu xanh da trời, nêu kiểm tra không đúng (x > 2), chúng ta lầy nhánh phải và gán nhãn màu xanh lá cây.

Bây giờ tập dữ liệu có 3 lớp

Cây quyết định cũ không hiệu quả, với mẫu dữ liệu mới (x, y)

Nếu x >= 2, chúng ta có thể vẫn tự tin phân loại vào lớp xanh lá cây.

Nếu x < 2, chúng ta không thể phân loại ngay vào lớp xanh da trời, nó cũng có thể đỏ

Chúng ta cần thêm node quyết định vào cây quyết định

Dó là ý tưởng chính của cây ra quyết định.

Biểu diễn cây quyết định

Mỗi nút trong (internal node} biểu diễn một thuộc tính cần kiểm tra giá trị đôi với các ví dụ (mẫu).

Mỗi nhánh (branch) từ một nút sẽ tương ứng với một giá trị có thể của thuộc tính gắn với nút đó.

Mỗi nút lá (leaf node) biểu diễn một lớp.

Một cây quyết định học được sẽ phân lớp đối với một ví dụ, bằng cách duyệt cây từ nút gốc đến một nút lá

—> Nhãn lớp gắn với nút lá đó sẽ được gán cho ví dụ cần phân lớp

Học các cây quyết định

Bài toán: Học xem khi nào thì nên ngồi bàn đợi tại một restaurant:

1. 1. Alternate: Có restaurant nào cạnh đây không?
   2. Bar: Liệu có khu vực quầy bar có thể ngồi không?
   3. Fri/Sat: hôm nay là thứ 6 hay thứ 7?
   4. Hungry: có đang đói không?
   5. Patrons: Số người trong restaurant (None, Some, Full)
   6. Price: khoảng giá ($, $$, $$$)
   7. Raining: ngoài trời có mưa không?
   8. Reservation: đã đặt trước chưa?
   9. Type: loại restaurant (French, Italian, Thai, Burger)
   10.  WaitEstimate: thời gian chờ đợi (0-10, 10-30, 30-60, >60)

Biểu diễn thuộc tính giá trị

Cây quyết định

• Biểu diễn giả thiết cần học.
• Ví dụ:

Thuật toán học cây quyết định

• Mục đích: Tìm cây nhỏ nhất quán với tập mẫu huấn luyện.
• Ý tưởng: Tìm kiếm heuristic chọn thuộc tính quan trọng nhất để phân tách (đệ quy)

Chọn thuộc tính

• Ý tưởng: chọn thuộc tính (giá trị) sao cho sao cho nó giúp phân tách tập mẫu thanh hai tập thuần khiết (chỉ có positive hay chỉ có negative).

• Patrons? là lựa chọn tốt hơn

Sử dụng lý thuyết thông tin

• để cài đặt Choose-Attribute trong thuật toán DTL:
• Lượng thông tin (Entropy):

I(P(v₁), … , P(v_n)) = Σ_i=1 -P(v_i) log₂ P(v_i)

• Đối với tập có p mẫu positive và n negative:

Lợi thông tin (Information gain)

• chọn thuộc tính A chia tập huấn luyện E thành các  tập con E₁, … , E_v tính theo giá trị của A, và giả sự A có v giá trị khác nhau.
• Lợi thông tin (IG) là độ giảm trong entropy trong việc test thuộc tính:

• Chọn thuộc tính có IG lớn nhất

Trong tập mẫu của ví dụ, p = n = 6, I(6/12, 6/12) = 1 bit

Xét thuộc tính Patrons và Type (và các thuộc tính khác):

Patrons có giá trị IG cao nhất nên được DTL chọn làm gốc của cây quyết định.

• Cây quyết định học bởi DTL từ 12 ví dụ:

• Nhỏ hơn cây quyết định đưa ra lúc đầu

Xây dựng cây quyết định