Hiểu bằng cách triển khai: Cây quyết định

Hình ảnh của Tác giả

Nhiều mô hình máy học tiên tiến như rừng ngẫu nhiên hoặc thuật toán tăng cường độ dốc như XGBoost, CatBoost hoặc LightGBM (và thậm chí bộ mã hóa tự động!) dựa vào một thành phần chung quan trọng: cây quyết định!

Nếu không hiểu cây quyết định, thì không thể hiểu bất kỳ thuật toán tăng cường độ dốc hoặc đóng bao nâng cao nào đã nói ở trên, đây là một điều đáng hổ thẹn đối với bất kỳ nhà khoa học dữ liệu nào! Vì vậy, chúng ta hãy làm sáng tỏ hoạt động bên trong của cây quyết định bằng cách triển khai cây quyết định bằng Python.

Trong bài viết này, bạn sẽ học

• tại sao và làm thế nào một cây quyết định phân tách dữ liệu,
• thu được thông tin, và
• cách triển khai cây quyết định trong Python bằng NumPy.

Bạn có thể tìm thấy mã trên Github của tôi.

Để đưa ra dự đoán, cây quyết định dựa vào chia tách tập dữ liệu thành các phần nhỏ hơn theo kiểu đệ quy.

Hình ảnh của Tác giả

Trong hình trên, bạn có thể thấy một ví dụ về sự phân tách — tập dữ liệu gốc được tách thành hai phần. Trong bước tiếp theo, cả hai phần này lại được tách ra, v.v. Điều này tiếp tục cho đến khi một số loại tiêu chí dừng được đáp ứng, ví dụ:

• nếu sự phân tách dẫn đến một phần trống
• nếu đạt đến độ sâu đệ quy nhất định
• nếu (sau các lần phân tách trước) tập dữ liệu chỉ bao gồm một vài phần tử, thì việc phân tách thêm là không cần thiết.

Làm thế nào để chúng ta tìm thấy những sự phân chia này? Và tại sao chúng ta thậm chí quan tâm? Hãy cùng tìm hiểu.

Động lực

Giả sử rằng chúng ta muốn giải quyết một nhị phân vấn đề phân loại mà chúng ta tự tạo ra bây giờ:

import numpy as np
np.random.seed(0) X = np.random.randn(100, 2) # features
y = ((X[:, 0] > 0) * (X[:, 1] < 0)) # labels (0 and 1)

Dữ liệu hai chiều trông như thế này:

Hình ảnh của Tác giả

Chúng ta có thể thấy rằng có hai lớp khác nhau — màu tím trong khoảng 75% và màu vàng trong khoảng 25% trường hợp. Nếu bạn cung cấp dữ liệu này cho cây quyết định phân loại, cây này ban đầu có những suy nghĩ sau:

“Có hai nhãn khác nhau, điều đó quá lộn xộn đối với tôi. Tôi muốn dọn dẹp mớ hỗn độn này bằng cách chia dữ liệu thành hai phần—những phần này phải sạch hơn dữ liệu hoàn chỉnh trước đó.” — cái cây đã có ý thức

Và cái cây cũng vậy.

Hình ảnh của Tác giả

Cây quyết định phân chia khoảng dọc theo x-trục. Điều này có tác dụng là phần trên cùng của dữ liệu hiện đã hoàn hảo dọn dẹp, có nghĩa là bạn chỉ tìm thấy một lớp học duy nhất (màu tím trong trường hợp này) ở đó.

Tuy nhiên, phần dưới vẫn lộn xộn, thậm chí còn lộn xộn hơn trước theo một nghĩa nào đó. Tỷ lệ lớp từng là khoảng 75:25 trong tập dữ liệu hoàn chỉnh, nhưng trong phần nhỏ hơn này là khoảng 50:50, tỷ lệ này được trộn lẫn hết mức có thể

 Lưu ý: Ở đây, không có vấn đề gì khi màu tím và màu vàng được phân tách độc đáo trong ảnh. Chỉ là số lượng nguyên liệu của các nhãn khác nhau trong hai phần đếm.

Hình ảnh của Tác giả

Tuy nhiên, đây là bước đầu tiên đủ tốt cho cái cây, và cứ thế nó tiếp tục. Mặc dù nó sẽ không tạo ra sự phân chia khác ở trên cùng, giống cá lăng nữa, nó có thể tạo một phần khác ở phần dưới cùng để làm sạch nó.

Hình ảnh của Tác giả

Và voilà, mỗi phần trong số ba phần riêng biệt hoàn toàn sạch sẽ, vì chúng tôi chỉ tìm thấy một màu (nhãn) duy nhất cho mỗi phần.

Hiện tại, việc đưa ra dự đoán thực sự dễ dàng: Nếu có điểm dữ liệu mới, bạn chỉ cần kiểm tra xem điểm nào trong số Ba phần nó nằm và cho nó màu tương ứng. Điều này hoạt động rất tốt bây giờ bởi vì mỗi phần là giống cá lăng. Dễ dàng, phải không?

Hình ảnh của Tác giả

Được rồi, chúng ta đang nói về giống cá lăng và lộn xộn dữ liệu nhưng cho đến nay những từ này chỉ đại diện cho một số ý tưởng mơ hồ. Để thực hiện bất cứ điều gì, chúng ta phải tìm cách xác định sạch sẽ.

Các biện pháp vệ sinh

Giả sử rằng chúng ta có một số nhãn, ví dụ

y_1 = [0, 0, 0, 0, 0, 0, 0, 0] y_2 = [1, 0, 0, 0, 0, 0, 1, 0]
y_3 = [1, 0, 1, 1, 0, 0, 1, 0]

Một cách trực quan, y₁ là bộ nhãn sạch nhất, tiếp theo là y₂ và sau đó y₃. Cho đến nay rất tốt, nhưng làm thế nào chúng ta có thể đưa ra những con số về hành vi này? Có lẽ điều dễ dàng nhất xuất hiện trong đầu là như sau:

Chỉ cần đếm số lượng số không và số lượng. Tính toán sự khác biệt tuyệt đối của họ. Để làm cho nó đẹp hơn, hãy chuẩn hóa nó bằng cách chia cho chiều dài của các mảng.

Ví dụ, y₂ có tổng cộng 8 mục — 6 số không và 2 số một. Do đó, định nghĩa tùy chỉnh của chúng tôi điểm sạch sẽ sẽ là |6 – 2| /8 = 0.5. Thật dễ dàng để tính toán rằng điểm số sạch sẽ của y₁ và y₃ lần lượt là 1.0 và 0.0. Ở đây, chúng ta có thể thấy công thức chung:

Hình ảnh của Tác giả

Ở đây, n₀ và n₁ lần lượt là các số XNUMX và XNUMX, n = n₀ + n₁ là độ dài của mảng và p₁ = n₁ / n là thị phần của 1 nhãn.

Vấn đề với công thức này là nó là đặc biệt phù hợp với trường hợp của hai lớp, nhưng rất thường chúng ta quan tâm đến phân loại nhiều lớp. Một công thức hoạt động khá tốt là Đo tạp chất Gini:

Hình ảnh của Tác giả

hoặc trường hợp tổng quát:

Hình ảnh của Tác giả

Nó hoạt động tốt đến mức scikit-learning thông qua nó như là biện pháp mặc định cho nó DecisionTreeClassifier lớp học.

Hình ảnh của Tác giả

 Lưu ý: biện pháp Gini lộn xộn thay vì sự sạch sẽ. Ví dụ: nếu một danh sách chỉ chứa một lớp duy nhất (=dữ liệu rất sạch!), thì tất cả các số hạng trong tổng bằng 1, do đó tổng bằng 1. Trường hợp xấu nhất là nếu tất cả các lớp xuất hiện với số lần chính xác, trong trường hợp đó Gini là XNUMX–XNUMX/C Ở đâu C là số lớp.

Bây giờ chúng ta đã có thước đo độ sạch sẽ/lộn xộn, hãy xem cách sử dụng thước đo này để tìm ra sự phân chia tốt.

Tìm chia tách

Có rất nhiều sự phân chia mà chúng tôi chọn, nhưng cái nào là tốt? Hãy để chúng tôi sử dụng lại bộ dữ liệu ban đầu của mình, cùng với thước đo tạp chất Gini.

Hình ảnh của Tác giả

Bây giờ chúng ta sẽ không tính số điểm, nhưng hãy giả sử rằng 75% là màu tím và 25% là màu vàng. Sử dụng định nghĩa của Gini, tạp chất của bộ dữ liệu hoàn chỉnh là

Hình ảnh của Tác giả

Nếu chúng ta chia tập dữ liệu dọc theo x-axis, như đã làm trước đây:

Hình ảnh của Tác giả

Sản phẩm phần trên cùng có tạp chất Gini là 0.0 và phần dưới cùng

Hình ảnh của Tác giả

Trung bình, hai phần có tạp chất Gini là (0.0 + 0.5) / 2 = 0.25, tốt hơn so với mức 0.375 của toàn bộ tập dữ liệu trước đây. Chúng ta cũng có thể diễn đạt nó theo cái gọi là thu thập thông tin:

Mức tăng thông tin của sự phân chia này là 0.375 – 0.25 = 0.125.

Dễ dàng như vậy. Độ lợi thông tin càng cao (nghĩa là tạp chất Gini càng thấp) thì càng tốt.

Lưu ý: Một sự phân tách ban đầu tốt không kém khác sẽ dọc theo trục y.

Một điều quan trọng cần ghi nhớ là nó rất hữu ích để cân tạp chất Gini của các bộ phận theo kích thước của các bộ phận. Ví dụ, chúng ta hãy giả sử rằng

• phần 1 bao gồm 50 điểm dữ liệu và có tạp chất Gini là 0.0 và
• phần 2 bao gồm 450 điểm dữ liệu và có tạp chất Gini là 0.5,

thì tạp chất Gini trung bình không phải là (0.0 + 0.5) / 2 = 0.25 mà là 50 / (50 + 450) * 0.0 + 450 / (50 + 450) * 0.5 = 0.45.

Được rồi, và làm thế nào để chúng ta tìm ra sự phân chia tốt nhất? Câu trả lời đơn giản nhưng tỉnh táo là:

Chỉ cần thử tất cả các phần tách và chọn phần có mức thu được thông tin cao nhất. Về cơ bản, đó là một cách tiếp cận vũ phu.

Nói chính xác hơn, cây quyết định tiêu chuẩn sử dụng tách dọc theo các trục tọa độ, I E xᵢ = c cho một số tính năng i và ngưỡng c. Điều này có nghĩa rằng

• một phần của dữ liệu phân chia bao gồm tất cả các điểm dữ liệu x với xᵢ cvà
• phần khác của tất cả các điểm x với xᵢ ≥ c.

Các quy tắc phân tách đơn giản này đã được chứng minh là đủ tốt trong thực tế, nhưng tất nhiên bạn cũng có thể mở rộng logic này để tạo các phân tách khác (tức là các đường chéo như xᵢ + 2xⱼ = 3, ví dụ).

Tuyệt vời, đây là tất cả những thành phần mà chúng ta cần để bắt đầu ngay bây giờ!

Bây giờ chúng ta sẽ triển khai cây quyết định. Vì nó bao gồm các nút, chúng ta hãy định nghĩa một Node lớp học đầu tiên.

from dataclasses import dataclass @dataclass
class Node: feature: int = None # feature for the split value: float = None # split threshold OR final prediction left: np.array = None # store one part of the data right: np.array = None # store the other part of the data

Một nút biết tính năng mà nó sử dụng để phân tách (feature) cũng như giá trị tách (value). value cũng được sử dụng làm nơi lưu trữ cho dự đoán cuối cùng của cây quyết định. Vì chúng ta sẽ xây dựng một cây nhị phân, mỗi nút cần biết các nút con bên trái và bên phải của nó, như được lưu trữ trong left và right .

Bây giờ, hãy thực hiện việc thực hiện cây quyết định thực tế. Tôi đang làm cho nó tương thích với scikit-learning, do đó tôi sử dụng một số lớp từ sklearn.base . Nếu bạn chưa quen với điều đó, hãy xem bài viết của tôi về cách xây dựng các mô hình tương thích với scikit-learning.

Hãy thực hiện!

import numpy as np
from sklearn.base import BaseEstimator, ClassifierMixin class DecisionTreeClassifier(BaseEstimator, ClassifierMixin): def __init__(self): self.root = Node() @staticmethod def _gini(y): """Gini impurity.""" counts = np.bincount(y) p = counts / counts.sum() return (p * (1 - p)).sum() def _split(self, X, y): """Bruteforce search over all features and splitting points.""" best_information_gain = float("-inf") best_feature = None best_split = None for feature in range(X.shape[1]): split_candidates = np.unique(X[:, feature]) for split in split_candidates: left_mask = X[:, feature] split X_left, y_left = X[left_mask], y[left_mask] X_right, y_right = X[~left_mask], y[~left_mask] information_gain = self._gini(y) - ( len(X_left) / len(X) * self._gini(y_left) + len(X_right) / len(X) * self._gini(y_right) ) if information_gain > best_information_gain: best_information_gain = information_gain best_feature = feature best_split = split return best_feature, best_split def _build_tree(self, X, y): """The heavy lifting.""" feature, split = self._split(X, y) left_mask = X[:, feature] split X_left, y_left = X[left_mask], y[left_mask] X_right, y_right = X[~left_mask], y[~left_mask] if len(X_left) == 0 or len(X_right) == 0: return Node(value=np.argmax(np.bincount(y))) else: return Node( feature, split, self._build_tree(X_left, y_left), self._build_tree(X_right, y_right), ) def _find_path(self, x, node): """Given a data point x, walk from the root to the corresponding leaf node. Output its value.""" if node.feature == None: return node.value else: if x[node.feature] node.value: return self._find_path(x, node.left) else: return self._find_path(x, node.right) def fit(self, X, y): self.root = self._build_tree(X, y) return self def predict(self, X): return np.array([self._find_path(x, self.root) for x in X])

Và thế là xong! Bạn có thể làm tất cả những điều bạn yêu thích về scikit-learning ngay bây giờ:

dt = DecisionTreeClassifier().fit(X, y)
print(dt.score(X, y)) # accuracy # Output
# 1.0

Vì cây không được điều chỉnh, nên nó bị thừa rất nhiều, do đó điểm tàu ​​hoàn hảo. Độ chính xác sẽ kém hơn đối với dữ liệu chưa nhìn thấy. Chúng ta cũng có thể kiểm tra xem cây trông như thế nào thông qua

print(dt.root) # Output (prettified manually):
# Node(
# feature=1,
# value=-0.14963454032767076,
# left=Node(
# feature=0,
# value=0.04575851730144607,
# left=Node(
# feature=None,
# value=0,
# left=None,
# right=None
# ),
# right=Node(
# feature=None,
# value=1,
# left=None,
# right=None
# )
# ),
# right=Node(
# feature=None,
# value=0,
# left=None,
# right=None
# )
# )

Như một bức tranh, nó sẽ là thế này:

Hình ảnh của Tác giả

Trong bài viết này, chúng ta đã xem chi tiết cách thức hoạt động của cây quyết định. Chúng tôi bắt đầu với một số ý tưởng mơ hồ nhưng trực quan và biến chúng thành các công thức và thuật toán. Cuối cùng, chúng tôi đã có thể triển khai cây quyết định từ đầu.

Mặc dù vậy, một lời cảnh báo: Cây quyết định của chúng tôi chưa thể được chuẩn hóa. Thông thường, chúng tôi muốn chỉ định các tham số như

• độ sâu tối đa
• kích thước lá
• và đạt được thông tin tối thiểu

trong số nhiều người khác. May mắn thay, những điều này không quá khó để thực hiện nên đây là một bài tập về nhà hoàn hảo dành cho bạn. Ví dụ: nếu bạn chỉ định leaf_size=10 làm tham số, thì các nút chứa hơn 10 mẫu sẽ không được phân chia nữa. Ngoài ra, việc thực hiện này là không hiệu quả. Thông thường, bạn sẽ không muốn lưu trữ các phần của bộ dữ liệu trong các nút mà thay vào đó chỉ lưu trữ các chỉ số. Vì vậy, tập dữ liệu (có khả năng lớn) của bạn chỉ có trong bộ nhớ một lần.

Điều tốt là bạn có thể phát điên ngay bây giờ với mẫu cây quyết định này. Bạn có thể:

• thực hiện chia tách đường chéo, tức là xᵢ + 2xⱼ = 3 Thay vì chỉ xᵢ = 3,
• thay đổi logic xảy ra bên trong các lá, tức là bạn có thể chạy hồi quy logistic trong mỗi lá thay vì chỉ bỏ phiếu theo đa số, điều này mang lại cho bạn cây tuyến tính
• thay đổi quy trình phân tách, tức là thay vì thực hiện vũ phu, hãy thử một số kết hợp ngẫu nhiên và chọn kết hợp tốt nhất, điều này mang lại cho bạn phân loại cây phụ
• và nhiều hơn nữa.

 
 
Tiến sĩ Robert Kübler là Nhà Khoa học Dữ liệu tại Publicis Media và Tác giả tại Hướng tới Khoa học Dữ liệu.

 
Nguyên. Đăng lại với sự cho phép.
 

• Phân phối nội dung và PR được hỗ trợ bởi SEO. Được khuếch đại ngay hôm nay.
• Platoblockchain. Web3 Metaverse Intelligence. Khuếch đại kiến ​​thức. Truy cập Tại đây.
• nguồn: https://www.kdnuggets.com/2023/02/understanding-implementing-decision-tree.html?utm_source=rss&utm_medium=rss&utm_campaign=understanding-by-implementing-decision-tree