Giới thiệu
Cây quyết định (DT) là một phương pháp học có giám sát phi tham số được sử dụng để phân loại và hồi quy. Mục tiêu là tạo ra một mô hình dự đoán giá trị của biến mục tiêu bằng cách tìm hiểu các quy tắc quyết định đơn giản được suy ra từ các đặc điểm dữ liệu.
##Entropy
Mục tiêu của việc đào tạo là tìm ra cách phân chia tốt nhất trong các nút để tìm ra cây tối ưu nhất. Việc phân chia được thực hiện bằng cách sử dụng một số tiêu chí như: Entropy.
Có nhiều định nghĩa về entropy như:
-
Entropy tương ứng với lượng thông tin chứa trong một nguồn thông tin.
-
Entropy cũng có thể được coi là tính ngẫu nhiên hay thước đo mức độ bất ngờ trong một tập hợp.
-
Entropy là thước đo đo lường tính không thể đoán trước hoặc độ tạp chất trong hệ thống.
Trong cây quyết định, chúng ta sẽ coi entropy là thước đo độ tinh khiết bên trong một nút. Mục tiêu của mô hình cây quyết định là giảm entropy của các nút tại mỗi lần phân chia:
Vì vậy, chúng tôi muốn tối đa hóa sự khác biệt giữa entropy của nút cha và entropy của nút con. Sự khác biệt này được gọi là Tăng được thông tin.
Entropy $H$ của một tập hợp $X$ được tính toán như sau:
$$ H(X) = - \sum\limits_{x \in X} p(x) \log p(x) $$
Thu thập thông tin
Mức tăng thông tin là sự khác biệt giữa entropy của nút cha và tổng có trọng số của entropies của nút chlid, và do đó nó có thể được tính toán như sau:
$$IG(Y, X) = H(Y) - \sum_{x \in unique(X)} P(x|X) \times H(Y | X = x)$$
$$= H(Y) - \sum_{x \in unique(X)} \frac{X.count(x)}{len(X)} \times H(Y[X == x])$$
Ở đâu:
-
$H(.)$ là entropy.
-
$Y$ là dân số trước khi phân chia, nó đại diện cho nút cha.
-
$X$ là biến mà chúng ta muốn sử dụng để phân tách.
-
$x$ là giá trị duy nhất của X.
-
$Y[X==x]$ là một danh sách được chia nhỏ chỉ có các giá trị $x$.
hãy lấy một ví dụ thích hợp:
Chúng ta sẽ tính Mức tăng thông tin khi chia nút cha bằng cách sử dụng các giá trị của X:
$$IG(parent, X) = H(parent) - \sum_{x \in unique(X)} P(x|X) \times H(parent | X = x)$$
\
Đầu tiên, chúng tôi tính toán entropy của nút cha:
$$ H(parent) = - P(Y=Blue) \times \log P(Y=Blue) - P(Y=Yellow) \times \log P(Y=Yellow) $$
$$ = - \frac{11}{21} \times \log(\frac{11}{21}) - \frac{10}{21} \times \log(\frac{10}{21}) = 0.3 $$
\
Sau đó, chúng ta sẽ tính xác suất bên trong của mỗi nút con sau khi phân chia bằng cách sử dụng các giá trị duy nhất của X:
$$ unique(X) = [Circle, Square] $$
$$ \sum_{x \in unique(X)} P(x|X) \times H(Y | X = x) = P(Square|X) \times H(Y | X = Square) $$
$$ + P(Circle|X) \times H(Y | X = Circle) $$
$$ = \frac{9}{21} \times H(Y | X = Square) + \frac{12}{21} \times H(Y | X = Circle) $$
Chẳng hạn như:
-
$H(Y | X = Square)$ : biểu thị entropy của nút con đầu tiên.
-
$H(Y | X = Circle)$ : biểu thị entropy của nút con thứ hai.
\
Chúng ta bắt đầu với nút con đầu tiên:
$$ H(Y | X = Square) = - P(Y=Blue | X = Square) \times \log P(Y=Blue| X = Square) $$
$$ - P(Y=Yellow| X = Square) \times \log P(Y=Yellow| X = Square) $$
$$ = - \frac{7}{9} \times \log\frac{7}{9} - \frac{2}{9} \times \log\frac{2}{9} = 0.23 $$
\
Và sau đó là nút con thứ hai:
$$ H(Y | X = Circle) = - P(Y=Blue | X = Circle) \times \log P(Y=Blue| X = Circle) $$
$$ - P(Y=Yellow| X = Circle) \times \log P(Y=Yellow| X = Circle) $$
$$ = - \frac{4}{12} \times \log\frac{4}{12} - \frac{8}{12} \times \log\frac{8}{12} = 0.28 $$
\
Cuối cùng, chúng tôi thay thế các entropy trong công thức Tăng thông tin:
$$IG(parent, X) = H(parent) - \sum_{x \in unique(X)} P(x|X) \times H(parent | X = x)$$
$$ = 0.3 - \frac{9}{21} \times 0.23 - \frac{12}{21} \times 0.28 = 0.041 $$
\
\
Như đã nêu trước đây, mục tiêu của việc phân chia nút là tối đa hóa Mức tăng thông tin và do đó giảm thiểu Entropy trong nút con kết quả. Để làm điều này, chúng tôi cần thử phân chia nút với các nhóm đầu vào khác nhau $ X_1, X_2, \ldots, Xn $ và chúng tôi chỉ giữ phần phân tách để tối đa hóa Thu thập thông tin:
$$ X^{*} = \underset{X_i}{\operatorname{argmax}} IG(Y, X_i) $$
Khi nào nên ngừng chia tách
Việc phân tách nút trong cây quyết định là một phép đệ quy, do đó phải có một tiêu chí mà chúng ta có thể sử dụng để dừng việc phân tách. Sau đây là một số tiêu chí được thực hiện nhiều nhất:
-
Khi nút thuần túy: H(nút) = 0. Việc chia nút thêm nữa là vô nghĩa.
-
Số độ sâu tối đa: Chúng ta có thể đặt độ sâu tối đa mà mô hình có thể đạt tới, điều đó có nghĩa là ngay cả khi nút không thuần túy thì quá trình phân tách vẫn dừng lại.
-
Số lượng mẫu tối thiểu trên mỗi nút: Chúng tôi cũng có thể đặt số lượng mẫu tối thiểu $N$ cho mỗi nút. Nếu số lượng mẫu trên mỗi nút bằng $N$ thì chúng tôi sẽ ngừng phân tách ngay cả khi nút đó không thuần túy.
Khi kết thúc quá trình đào tạo (phân tách), mỗi nút dựa vào phần cuối của cây quyết định được gọi là "Lá", vì nó không phải là gốc của bất kỳ cây con nào. Mỗi lá sẽ đại diện cho năng suất của lớp có nhiều mẫu nhất.
Phần kết luận
Cây quyết định là một trong những thuật toán học máy nổi tiếng nhất nhờ tính hiệu quả, nền tảng trực quan và cách triển khai đơn giản. Thuật toán này có thể được sử dụng thêm với các biến độc lập bằng số (Cây quyết định Gaussian) và nó cũng có thể được mở rộng để giải các tác vụ hồi quy.
