Xem Nhiều 8/2022 # Cây Quyết Định (Decision Tree) Là Gì? Tìm Hiểu Thuật Toán Id3 # Top Trend | Maiphuongus.net

Xem Nhiều 8/2022 # Cây Quyết Định (Decision Tree) Là Gì? Tìm Hiểu Thuật Toán Id3 # Top Trend

Xem 17,523

Cập nhật thông tin chi tiết về Cây Quyết Định (Decision Tree) Là Gì? Tìm Hiểu Thuật Toán Id3 mới nhất ngày 12/08/2022 trên website Maiphuongus.net. Hy vọng nội dung bài viết sẽ đáp ứng được nhu cầu của bạn, chúng tôi sẽ thường xuyên cập nhật mới nội dung để bạn nhận được thông tin nhanh chóng và chính xác nhất. Cho đến thời điểm hiện tại, bài viết này đã đạt được 17,523 lượt xem.

--- Bài mới hơn ---

  • 4 Địa Điểm Cánh Đồng Quạt Gió Đẹp Nhất Việt Nam
  • Thuyết Minh Về Cây Quạt Giấy
  • 3 Cách Trang Trí Cây Quất Ngày Tết Đơn Giản Nhất
  • Khám Phá Thú Vị Về Cây Quất Cảnh Ngày Tết
  • Ý Nghĩa Của Cây Quất Ngày Tết
  • Cây quyết định là gì?

    DT được áp dụng vào cả 2 bài toán: Phân loại ( Classification) và Hồi quy ( Regression). Tuy nhiên bài toán phân loại được sử dụng nhiều hơn.

    Có nhiều thuật toán để xây dựng DT, trong bài này ta tìm hiểu một thuật toán nổi tiếng và cơ bản nhất của DT là thuật toán ID3.

    Thuật toán ID3

    Iterative Dichotomiser 3 (ID3) là thuật toán nổi tiếng để xây dựng Decision Tree, áp dụng cho bài toán Phân loại ( Classification) mà tất các các thuộc tính để ở dạng category.

    Để dễ hiểu ta cùng tìm hiểu thuật toán này qua ví dụ.

    Ta có tập Training Data như bảng dưới:

    Data của ta có 4 thuộc tính: Engine, Type, Color, 4WD.

    Để tính toán được DT, ta cần phân chia các thuộc tính vào các node đánh giá. Vậy làm sao để biết được thuộc tính nào quan trọng, nên đặt ở gốc, thuộc tính nào ở nhánh…

    Trong thuật toán ID3, các thuộc tính được đánh giá dựa trên Hàm số Entropy, hàm số phổ biến trong toán học xác suất.

    Hàm số Entropy

    Cho một phân phối xác suất của một biến rời rạc $x$ có thể nhận $n$ giá trị khác nhau $x_1, x_2, dots, x_n$. Giả sử rằng xác suất để $x$ nhận các giá trị này là $p_i = p(x = x_i)$

    Ký hiệu phân phối này là $mathbf{p} = (p_1, p_2, dots, p_n)$.

    Entropy của phân phối này là:

    $$ H(mathbf{p}) = -sum_{i=1}^n p_i log_2(p_i)quadquad $$

    Hàm Entropy được biểu diễn dưới dạng đồ thị như sau:

    Từ đồ thị ta thấy, hàm Entropy sẽ đạt giá trị nhỏ nhất nếu có một giá trị $p_i = 1$, đạt giá trị lớn nhất nếu tất cả các $p_i$ bằng nhau.

    Hàm Entropy càng lớn thì độ ngẫu nhiên của các biến rời rạc càng cao (càng không tinh khiết).

    Với cây quyết định, ta cần tạo cây như thế nào để cho ta nhiều thông tin nhất, tức là Entropy là cao nhất.

    Information Gain

    Bài toán của ta trở thành, tại mỗi tầng của cây, cần chọn thuộc tính nào để độ giảm Entropy là thấp nhất.

    Người ta có khái niệm Information Gain được tính bằng $$ Gain(S,f) = H(S) – H(f,S) $$ trong đó:

    $H({S})$ là Entropy tổng của toàn bộ tập data set $S$.

    $H(f, S)$ là Entropy được tính trên thuộc tính $f$.

    Do $H({S})$ là không đổi với mỗi tầng, ta chọn thuộc tính $f$ có Entropy nhỏ nhất để thu được $Gain(S,f)$ lớn nhất.

    Tính Entropy của các thuộc tính

    Xét thuộc tính Engine

    Thuộc tính này có thể nhận 1 trong 2 giá trị 1000cc, 2000cc, tương ứng với 2 child node.

    Gọi tập hợp các điểm trong mỗi child node này lần lượt là $S_1$, $S_2$.

    Sắp xếp lại theo thuộc tính Engine ta có 2 bảng nhỏ.

    Engine 1000cc ($S_1$)

    Engine 2000cc ($S_2$)

    Child node ứng với Engine 1000cc sẽ có Entropy = 0 do tất cả các giá trị đều là Yes.

    Ta chỉ việc tính Entropy với Engine 2000cc. Sau đó tính Entropy trung bình.

    Cụ thể như sau:

    $$ begin{aligned} H(S_1) &=& 0 cr H(S_2) &=& -frac{2}{4}mathcal{log}_2left(frac{2}{4}right) – frac{2}{4}mathcal{log}_2left(frac{2}{4}right) = 1 cr H({engine}, S) &=& frac{4}{8}H(S_1) + frac{4}{8}H(S_2) = 0.5 end{aligned} $$

    Xét thuộc tính Type

    Thuộc tính này có thể nhận 1 trong 3 giá trị SUV, Senda, Sport tương ứng với 3 child node.

    Gọi tập hợp các điểm trong mỗi child node này lần lượt là $S_u$, $S_e$, $S_p$.

    Sắp xếp lại theo thuộc tính Type ta có 3 bảng nhỏ.

    Type SUV ($S_u$)

    Type Sedan ($S_e$)

    Type Sport ($S_p$)

    Tương tự, ta lần lượt tính Entropy như bên dưới:

    $$ begin{aligned} H(S_u) &=& 0 cr H(S_e) &=& -frac{2}{3}mathcal{log}_2left(frac{2}{3}right) – frac{1}{3}mathcal{log}_2left(frac{1}{3}right) approx 0.918 cr H(S_p) &=& -frac{1}{2}mathcal{log}_2left(frac{1}{2}right) – frac{1}{2}mathcal{log}_2left(frac{1}{2}right) = 1 cr H({type}, S) &=& frac{3}{8}H(S_u) + frac{3}{8}H(S_e) + frac{2}{8}H(S_p) approx 0.594 end{aligned} $$

    Xét thuộc tính Color

    Thuộc tính này có thể nhận 1 trong 2 giá trị Silver, Blue tương ứng với 2 child node.

    Gọi tập hợp các điểm trong mỗi child node này lần lượt là $S_s$, $S_b$.

    Sắp xếp lại theo thuộc tính Color ta có 2 bảng nhỏ.

    Color Silver ($S_s$)

    Color Blue ($S_b$)

    Dễ thấy, 2 giá trị Silver và Blue đều có tỉ lệ Yes, No như nhau là 3414.

    Do đó ta tính luôn Entropy trung bình:

    $$ begin{aligned} H({color}, S) &=& -frac{3}{4}mathcal{log}_2left(frac{3}{4}right) – frac{1}{4}mathcal{log}_2left(frac{1}{4}right) approx 0.811 end{aligned} $$

    Xét thuộc tính 4WD

    Thuộc tính này có thể nhận 1 trong 2 giá trị Yes, No tương ứng với 2 child node.

    Gọi tập hợp các điểm trong mỗi child node này lần lượt là $S_y$, $S_n$.

    Sắp xếp lại theo thuộc tính 4WD ta có 2 bảng nhỏ.

    4WD Yes ($S_y$)

    4WD No ($S_n$)

    Tương tự Color, ta tính Entropy trung bình:

    $$ begin{aligned} H({4wd}, S) &=& -frac{3}{4}mathcal{log}_2left(frac{3}{4}right) – frac{1}{4}mathcal{log}_2left(frac{1}{4}right) approx 0.811 end{aligned} $$

    Chọn thuộc tính có Entropy nhỏ nhất

    Sau khi tính Entropy trung bình của 4 thuộc tính ta thu được:

    $H({engine}, S) = 0.5$

    $H({type}, S) approx 0.594$

    $H({color}, S) approx 0.811$

    $H({4wd}, S) approx 0.811$

    Thuộc tính Engine có giá trị Entropy nhỏ nhất nên ta chọn là node đánh giá đầu tiên.

    Với Engine 1000cc, tất cả các data đều có giá trị Yes, vì vậy ta thu được node là Yes ở nhánh 1000cc.

    Ta tiếp tục tính cho nhánh Engine 2000cc với tập data nhỏ hơn là

    Tương tự ta lần lượt tính Entropy cho 3 thuộc tính là: Type, Color, 4WD

    Với thuộc tính Type:

    $$ begin{aligned} H(S_u) &=& 0 cr H(S_e) &=& 0 cr H(S_p) &=& -frac{1}{2}mathcal{log}_2left(frac{1}{2}right) – frac{1}{2}mathcal{log}_2left(frac{1}{2}right) = 1 cr H({type}, S) &=& frac{1}{4}H(S_u) + frac{1}{4}H(S_e) + frac{2}{4}H(S_p) = 0.5 end{aligned} $$

    Với thuộc tính Color:

    Do 2 giá trị Silver và Blue có cùng tỉ lệ Yes, No là 1212.

    $$ begin{aligned} H({color}, S) &=& -frac{1}{2}mathcal{log}_2left(frac{1}{2}right) – frac{1}{2}mathcal{log}_2left(frac{1}{2}right) = 1 end{aligned} $$

    Với thuộc tính 4WD:

    $$ begin{aligned} H(S_y) &=& -frac{2}{3}mathcal{log}_2left(frac{2}{3}right) – frac{1}{3}mathcal{log}_2left(frac{1}{3}right) approx 0.918 cr H(S_n) &=& 0 cr H({4wd}, S) &=& frac{3}{4}H(S_y) + frac{1}{4}H(S_n) approx 0.688 end{aligned} $$

    Vậy ta chọn Type là node đánh giá tiếp theo.

    Với trường hợp Type là SUV hoặc Sedan, ta có ngay node lá vì chỉ có một kết quả.

    Với trường hợp Type là Sport, do thuộc tính Color là giống nhau với tất cả data, ta chọn node đánh giá tiếp theo là 4WD.

    Kết quả

    Ta thu được Decision Tree như hình bên dưới.

    Kiểm tra (Validation)

    Ta sẽ tiến hành kiểm tra mô hình DT ta vừa tạo được bằng tập Test Data như bên dưới:

    Ta có bảng mapping đánh giá kết quả như sau:

    Dựa vào DT ta vừa tạo được, ta tiến hành đánh giá như sau:

    Các thông số áp dụng để đánh giá được tính như sau:

    $$ begin{aligned} Accuracy &=& frac{TP+TN}{TP+FP+TN+FN} = 0.5 cr Recall &=& frac{TP}{TP+FN} = 0.5 cr Precision &=& frac{TP}{TP+FP} = 1 cr F-Measure &=& frac{2 times Recall times Precision}{Recall + Precision} approx 0.667 end{aligned} $$

    Nhìn chung Decision Tree tìm được có độ chính xác không cao khi chạy thử với Test Data.

    Nguyên nhân chính có lẽ là do tập Training Data quá ít.

    --- Bài cũ hơn ---

  • Bài Giảng Cây Quyết Định Và Lý Thuyết Dụng Ích
  • Cây Quyết Định (Decision Tree)
  • Thuyết Minh Về Cái Quạt Giấy
  • Thuyết Minh Về Cây Quạt Giấy Hay Nhất
  • Tranh Phong Cảnh Cây Phong Lá Đỏ Mùa Thu Amia 1504
  • Bạn đang xem bài viết Cây Quyết Định (Decision Tree) Là Gì? Tìm Hiểu Thuật Toán Id3 trên website Maiphuongus.net. Hy vọng những thông tin mà chúng tôi đã chia sẻ là hữu ích với bạn. Nếu nội dung hay, ý nghĩa bạn hãy chia sẻ với bạn bè của mình và luôn theo dõi, ủng hộ chúng tôi để cập nhật những thông tin mới nhất. Chúc bạn một ngày tốt lành!

  • Web hay
  • Links hay
  • Push
  • Chủ đề top 10
  • Chủ đề top 20
  • Chủ đề top 30
  • Chủ đề top 40
  • Chủ đề top 50
  • Chủ đề top 60
  • Chủ đề top 70
  • Chủ đề top 80
  • Chủ đề top 90
  • Chủ đề top 100
  • Bài viết top 10
  • Bài viết top 20
  • Bài viết top 30
  • Bài viết top 40
  • Bài viết top 50
  • Bài viết top 60
  • Bài viết top 70
  • Bài viết top 80
  • Bài viết top 90
  • Bài viết top 100