Show
Đã đăng vào thg 8 22, 2018 3:26 CH 4 phút đọc Bài viết được dịch từ Cây quyết định là một trong những thuật toán máy học phổ biến nhất hiện nay. Nó được dùng trong cả bài toán phân lớp và hồi quy. Trong bài viết này, mình sẽ giải quyết bài toán phân lớp. Trước khi bắt đầu, mình có một câu hỏi :v
Có một vài câu trả lời nhưng mình nghĩ đến 2 câu trả lời dưới đây:
Chúng ta có thể nhìn thấy được sự logic về việc xây dựng cây quyết định. Khá đơn giản và rõ ràng.
Cây quyết định là cây mà mỗi nút biểu diễn một đặc trưng(tính chất), mỗi nhánh(branch) biểu diễn một quy luật(rule) và mỗi lá biểu biễn một kết quả (giá trị cụ thể hay một nhánh tiếp tục)
Có một vài thuật toán để tạo một cây quyết định, chúng ta sẽ nói về 2 trong số chúng:
Cùng tạo cây quyết định để giải quyết bài toán phân lớp bằng những thuật toán trên ^^
Mình sẽ dùng tập dữ liệu nổi tiếng trong ngành máy học - dữ liệu thời tiết(weather dataset) - đưa ra yes or no dựa vào thời tiết. Chúng ta có 4 X giá trị (quang cảnh - outlook, nhiệt độ-temp, độ ẩm-humidity, gió-windy) và một giá trị Y( đi chơi hay k? - yes or no ) đã được chỉ rõ. Chúng ta cần tìm sự ánh xạ giữa X và Y ( mỗi liên hệ giữa input và output) Đây là bài toán phân lớp nhị phân nên hãy dùng ID3 Để xây dựng cây, trước hết chúng ta cần nút gốc và ta biết root là một trong những đặc trưng(tính chất).
Để xác định IG chính xác, chúng ta định nghĩa một thước đo thường được dùng trong lí thuyết thông tin, gọi là entropy miêu tả độ trong sạch của một thu thập dữ liệu tùy ý. Với bài toán phân lớp:
Giờ hãy ứng dụng IG để tìm gốc: 1. Tính toán entropy cho tập dữ liệu. 2. Với tất cả đặc trưng: 1. Tính toán entropy của tất cả giá trị. 2. Tính entropy trung bình cho thuộc tính đang thực hiện. 3. Chọn đặc trưng chó IG cao nhất. 4. Lặp lại cho đến khi thu được cây như mong muốn.
Suy ra, nút gốc của ta là Outlook.!
Trên đây là cách mà cây quyết định giải quyết bài toán phân lớp bằng bài thuật toán ID3. Cảm ơn mọi người vì đã đọc bài việt All rights reserved Mô hình cây quyết định là một mô hình được sử dụng khá phổ biến và hiệu quả trong cả hai lớp bài toán phân loại và dự báo của học có giám sát. Khác với những thuật toán khác trong học có giám sát, mô hình cây quyết định không tồn tại phương trình dự báo. Mọi việc chúng ta cần thực hiện đó là tìm ra một cây quyết định dự báo tốt trên tập huấn luyện và sử dụng cây quyết định này dự báo trên tập kiểm tra. Vậy một cây quyết định sẽ được xây dựng như thế nào? Điều gì ẩn chứa sau thuật toán cây quyết định? Để trả lời cho câu hỏi này, chúng ta cùng lấy ví dụ về áp dụng mô hình cây quyết định cho bài toán phân loại giá nhà trên bộ dữ liệu boston. 8.2. Bài toán phân loại cây quyết định trên bộ dữ liệu boston¶Bộ dữ liệu được sử dụng cho bài toán này là bộ dữ liệu về giá nhà ở ở boston bao gồm 13 quan sát và 506 biến. Đọc dữ liệu: from sklearn.datasets import load_boston import numpy as np boston = load_boston() X = boston.data y = boston.target y = [1 if price > 20 else 0 for price in y] # 1 nhà giá cao, 0 nhà giá thấp y = np.array(y) print('Input features: ', ', '.join(boston.feature_names)) print(X.shape) Input features: CRIM, ZN, INDUS, CHAS, NOX, RM, AGE, DIS, RAD, TAX, PTRATIO, B, LSTAT (506, 13) /home/khanh/miniconda3/envs/deepai-book/lib/python3.9/site-packages/sklearn/utils/deprecation.py:87: FutureWarning: Function load_boston is deprecated; `load_boston` is deprecated in 1.0 and will be removed in 1.2. The Boston housing prices dataset has an ethical problem. You can refer to the documentation of this function for further details. The scikit-learn maintainers therefore strongly discourage the use of this dataset unless the purpose of the code is to study and educate about ethical issues in data science and machine learning. In this special case, you can fetch the dataset from the original source:: import pandas as pd import numpy as np data_url = "http://lib.stat.cmu.edu/datasets/boston" raw_df = pd.read_csv(data_url, sep="\s+", skiprows=22, header=None) data = np.hstack([raw_df.values[::2, :], raw_df.values[1::2, :2]]) target = raw_df.values[1::2, 2] Alternative datasets include the California housing dataset (i.e. :func:`~sklearn.datasets.fetch_california_housing`) and the Ames housing dataset. You can load the datasets as follows:: from sklearn.datasets import fetch_california_housing housing = fetch_california_housing() for the California housing dataset and:: from sklearn.datasets import fetch_openml housing = fetch_openml(name="house_prices", as_frame=True) for the Ames housing dataset. warnings.warn(msg, category=FutureWarning) Ý nghĩa của những trường dữ liệu: Các biến đầu vào:
Biến mục tiêu: Căn cứ vào giá nhà ở > 20 nghìn USD hoặc nhỏ hơn mà chúng ta phân thành nhãn 1 (giá cao) và nhãn 0 (giá thấp). Tiếp theo ta sẽ xây dựng một mô hình phân loại dự trên cây quyết định với độ sâu tối đa là 3. Độ sâu ở đây chính là số lượng tối đa các câu hỏi khi đi từ node gốc tới node lá. Chúng ta khai báo độ sâu thông qua đối số max_depth. from sklearn.tree import DecisionTreeClassifier tree_clf = DecisionTreeClassifier(max_depth=3) tree_clf.fit(X, y) DecisionTreeClassifier(max_depth=3) Tiếp theo là sử dụng hàm export_graphviz() để biểu đồ hoá cây quyết định. Trong hàm này chúng ta chỉ cần truyền vào mô hình, tên các đặc trưng đầu vào thông qua đối số feature_names và các nhãn thông qua đối số class_names. import graphviz from sklearn import tree dot_data = tree.export_graphviz(tree_clf, out_file=None, feature_names=boston.feature_names, class_names=['low', 'high'], rounded=True, filled=True) graph = graphviz.Source(dot_data, format="png") graph --------------------------------------------------------------------------- ModuleNotFoundError Traceback (most recent call last) /tmp/ipykernel_19638/2901286609.py in <module> ----> 1 import graphviz 2 from sklearn import tree 3 4 dot_data = tree.export_graphviz(tree_clf, out_file=None, 5 feature_names=boston.feature_names, ModuleNotFoundError: No module named 'graphviz' Cách dự báo từ cây quyết định? Từ cây quyết định ở trên, dựa trên việc rẽ nhánh, chúng ta suy ra được nhãn dự báo cho các quan sát. Giả sử quan sát đầu vào có giá trị: LSTAT = 10, RM = 6, DIS = 3. Khi đó xuất phát từ node gốc ta tuần tự đặt và trả lời các câu hỏi:
Để minh chứng cho nhận định trên, ta sẽ thử nghiệm dự báo cho 5 quan sát sao cho giá trị LSTAT = 10, RM = 6, DIS = 3 là cố định và những giá trị khác thay đổi ngẫu nhiên và kiểm tra kết quả dự báo. import pandas as pd # LSTAT = 10, RM = 6, DIS = 3, các giá trị khác có thể thay đổi tuỳ ý for i in range(5): CRIM = np.random.randint(0, 100) INDUS = np.random.randint(0, 100) ZN = np.random.randint(0, 100) CHAS = np.random.randint(0, 100) NOX = np.random.randint(0, 100) AGE = np.random.randint(0, 100) RAD = np.random.randint(0, 100) TAX = np.random.randint(0, 100) PTRATIO = np.random.randint(0, 100) B = np.random.randint(0, 100) x = pd.DataFrame({'CRIM':CRIM, 'ZN':ZN, 'INDUS':INDUS, 'CHAS':CHAS, 'NOX':NOX, 'RM':[6], 'AGE':AGE, 'DIS':[3], 'RAD':RAD, 'TAX':TAX, 'PTRATIO':PTRATIO, 'B':B, 'LSTAT':[10]}) y_pred = tree_clf.predict_proba(x)[0] print('probability low {}, high {}'.format(y_pred[0], y_pred[1])) print('predicted label {}'.format(tree_clf.predict(x)[0])) Chúng ta thấy dù có thay đổi các giá trị khác như thế nào, miễn là 3 giá trị LSTAT = 10, RM = 6, DIS = 3 thoả mãn thì chúng ta đều thu được dự báo có nhãn là 1. Điều này cho thấy dự báo từ cây nhị phân đã tuân theo qui luật rẽ nhánh in đậm như bên dưới: 8.3. Đường biên phân chia của cây quyết định¶Đường biên phân chia của cây quyết định sẽ dựa trên kịch bản rẽ nhánh mà chúng ta lựa chọn. Gỉa định chúng ta đi từ node (LSTAT <= 14.115) --> (RM <= 6.034) --> (DIS <= 4.714). Khi đó đường biên phân chia là những đường thẳng trong hình bên dưới đi qua ngưỡng threshold.
Chúng ta để ý thấy rằng mọi điểm nằm trong hình chữ nhật có các cạnh in đậm sẽ cùng được dự báo thuộc về nhóm high hình tròn như hình vẽ. Các cạnh in đậm của hình chữ nhật chính là đường biên phân chia của cây quyết định. Đối với những điểm nằm ngoài hình chữ nhật này thì có thể lẫn cả nhãn high và nhãn low và chúng ta cần những kịch bản rẽ nhánh khác để dự báo nhãn cho chúng. Như vậy đường biên phân chia của cây quyết định là khá đơn giản và trực quan. Chúng ta không cần giải bài toán tối ưu như SVM hay Logistic để tìm ra được đường biên phân chia này mà đơn thuần chúng chỉ là một siêu phẳng đi qua một ngưỡng threshold cố định. Những mô hình có đường biên phân chia có thể giải thích được như vậy được gọi là white box models. Trái lại, trong machine learning tồn tại những mô hình mà chúng ta không thể giải thích được vì sao mô hình lại đưa ra quyết định như vậy. Chẳng hạn như trong mạng nơ ron, mô hình có thể dễ dàng dự báo một bức ảnh là chó hay mèo nhưng ta không thể nói được vì sao mô hình lại dự báo đó là chó hoặc mèo. Kết quả dự báo căn cứ vào bao nhiêu phần trăm quyết định được đưa ra dựa trên các đặc trưng như lông, đuôi, mắt, mũi, miệng của chúng? Những mô hình như vậy được gọi là black box models. 8.4. Cách khởi tạo cây quyết định¶Để trả lời cho câu hỏi một cây quyết định được tạo ra như thế nào? Chúng ta cần biết được thứ tự câu hỏi là gì và cách đặt câu hỏi như thế nào? Thứ tự lựa chọn câu hỏi Đối với những bộ dữ liệu có số lượng biến đầu vào \(d\) lớn, việc lựa chọn biến nào sẽ được đặt ở node gốc là điều không dễ dàng. Một kịch bản lựa chọn ngẫu nhiên chỉ có xác suất đúng là \(\frac{1}{d}\) và dường như khả năng chúng ta chọn sai là rất cao. Do đó chúng ta cần phải có một tiêu chí nào đó để lựa chọn biến phù hợp. Xuất phát từ yêu cầu này, chúng ta hình thành nên các độ đo như entropy, Gini đo lường mức độ tinh khiến (purity) và vẩn đục (impurity) của một biến mà ta sẽ tìm hiểu bên dưới. 8.4.1. Tinh khiết và vẩn đục¶Giả định chúng ta đang xây dựng một cây quyết định mà tại một node quyết định chúng ta có 50 quan sát rơi vào chúng. Có ba phương án lựa chọn node lá tiếp theo tương ứng với 3 biến, chúng có kết quả thống kê tại node lá lần lượt là:
Theo bạn đâu sẽ là biến phù hợp nhất được lựa chọn tại node lá? Kịch bản lựa chọn biến 1 dường như là vô nghĩa vì nó tương đương với dự báo ngẫu nhiên nhãn 0 và 1. Kịch bản tương ứng với biến 2 có xu hướng dự báo thiên về nhãn 0 nhưng tỷ lệ dự báo sai nhãn 1 vẫn còn cao. Lựa chọn biến 3 là tuyệt vời vì chúng ta đã dự báo đúng hoàn toàn nhãn 0. Như vậy mục tiêu của chúng ta khi đối diện với việc phân loại đó là kết quả trả về tại node lá chỉ thuộc về một lớp. Chúng ta sử dụng một thuật ngữ ngắn gọn để gọi tên trường hợp này là tinh khiết (purity). Trái ngược lại với tinh khiết sẽ là khái niệm vấn đục (impurity), tức phân phối của các nhãn tại node lá còn khá mập mờ, không có xu hướng thiên về một nhãn nào cụ thể. Nếu ra quyết định phân loại dựa trên kịch bản dẫn tới node lá sẽ trả về kết quả không đáng tin cậy. 8.4.2. Thước đo cho mức độ tinh khiết (purity)¶Entropy là một khái niệm khoa học được sử dụng lần đầu tiên trong nhiệt động lực học và sau đó được phổ biến trong các lĩnh vực khác như vật lý, hoá học, y sinh, lý thuyết thông tin,… Trong nhiệt động lực học thì Entropy là một đặc tính vật lý có thể đo lường được có sự liên kết với trạng thái hỗn loạn (disorder) hoặc không chắc chắn (uncertainty). Trong thuật toán cây quyết định chúng ta sẽ sử dụng Entropy để đánh giá mức độ tinh khiết của phân phối xác suất của một sự kiện. Giả sử một sự kiện xảy ra với phân phối xác suất là \(\mathbf{p} = (p_1, p_2, \dots, p_C)\) thoả mãn \(\sum_{i=1}^{C} p_i = 1\). Khi đó hàm entropy đối với sự kiện trên là: \[\mathbf{H}(\mathbf{p}) = -\sum_{i=1}^{C}p_i \log p_i \tag{1}\] Trong trường hợp \(p_i = 0\) thì hàm entropy là không xác định do \(\log p_i\) không tồn tại, tuy nhiên căn cứ vào giá trị hội tụ thì chúng ta sẽ qui ước giá trị của entropy trong trường hợp này là 0. Trong lý thuyết thông tin thì hàm \(\log\) ở phương trình \((1)\) là hàm logarith với cơ số 2. Tuy nhiên ở đây chúng ta có thể sử dụng hàm logarith cơ số tự nhiên \(e\) mà không thay đổi bản chất do giá trị đạt được tương đương với việc nhân với một hằng số. Khảo sát hàm entropy chúng ta sẽ nhận thấy đây là một hàm không âm có giá trị tối đa đạt được khi phân phối xác suất là đồng đều trên toàn bộ các nhãn. Để đơn giản bên dưới chúng ta vẽ đồ thị và khảo sát hàm entropy đối với bài toán phân loại nhị phân. import numpy as np import matplotlib.pyplot as plt # Tính entropy theo p def _entropy(p): return -(p*np.log(p)+(1-p)*np.log((1-p))) # Khởi tạo gía trị yhat từ 0 đến 1 p = np.linspace(0.001, 0.999, 200) # Hàm visualize cross entropy def _plot_crs(p): entropy = _entropy(p) plt.figure(figsize = (12, 8)) plt.plot(p, entropy) plt.xlabel('p') plt.ylabel('entropy') plt.title('Entropy') plt.show() _plot_crs(p) Giá trị lớn nhất đạt được khi \(p_0 = p_1 = \frac{1}{2}\). Trong khi giá trị nhỏ nhất đạt được khi một trong hai xác suất bằng 1 và xác suất còn lại bằng 0. Bên dưới là lời giải cho bài toán cực trị entropy cho bạn nào thực sự quan tâm Ta dễ dàng tìm được cực trị \(\mathbf{H}(\mathbf{p})\). Thật vậy, vì \(1 \geq p_i \geq 0\) nên giá trị \(\mathbf{H}(\mathbf{p}) \geq 0\) là hiển nhiên. Đẳng thức xảy ra khi tồn tại một giá trị \(p_i = 1\) và các giá trị còn lại bằng 0. Để tìm cực đại chúng ta xét hàm \(f(x) = -x\log{x}\). Hàm này có đạo hàm bậc 2 là \(f''(x) = \frac{-1}{x} \leq 0\) nên là một hàm lõm trên khoảng \((0, 1]\). Áp dụng bất đẳng thức Jensen ta có: \[ \mathbf{H}(\mathbf{p}) = \sum_{i=1}^C f(p_1) \leq C f(\frac{\sum_{i=1}^C p_i}{C}) = C f(\frac{1}{C}) = C [-\frac{1}{C}\log \frac{1}{C}] = \log C \] Đẳng thức xảy ra khi \(p_0=p_1= \dots =p_C=\frac{1}{C}\). Kết luận giá trị entropy cực tiểu đạt được khi phân phối \(\mathbf{p}\) là tinh khiết nhất, tức phân phối hoàn toàn thuộc về một nhóm. Trái lại, entropy cực đại đạt được khi toàn bộ xác suất thuộc về các nhóm là bằng nhau. Một phân phối có entropy càng cao thì mức độ tinh khiết của phân phối đó sẽ càng thấp và ngược lại. Như vậy về bản chất thì entropy là một thước đo về độ tinh khiết của phân phối xác suất. Dựa trên entropy chúng ta có thể đánh giá tính hiệu quả của câu hỏi ở mỗi node và quyết định xem đâu là câu hỏi hiệu quả hơn (có độ tinh khiết lớn hơn, entropy nhỏ hơn). Tiếp theo chúng ta sẽ cùng tìm hiểu giải thuật tìm kiếm tham lam (greedy) theo chiều từ trên xuống để xây dựng nên cây quyết định dựa trên hàm entropy. 8.4.3. Tìm kiếm tham lam và truy hồi¶Giả sử số lượng biến của bạn là \(n\) rất lớn. Bạn muốn tạo ra một cây nhị phân với độ sâu tối đa là \(d\). Số khả năng lựa chọn \(d\) biến (có xét đến tính thứ tự) từ \(m\) biến để tạo thành một cây nhị phân là chỉnh hợp \(A_n^d = \frac{d!}{(d-n)!}\). Khi \(d\) lớn thì đây là một con số rất lớn. Do đó rất khó để chúng ta tìm được đúng cây nhị phân tối ưu ngay chỉ trong một lần. Thay vào đó, một chiến lược hợp lý và khôn ngoan hơn là đi từng bước nhỏ và tìm cách lựa chọn câu hỏi tối ưu ở mỗi node. Chiến lược như vậy được gọi là tìm kiếm tham lam. Ngoài ra quá trình lựa chọn này sẽ tiếp diễn một cách truy hồi (recursive) theo chiều từ trên xuống dưới cho đến khi đạt ngưỡng về độ sâu hoặc node cuối cùng hoàn toàn thuộc về một nhóm. Ở một số thuật toán, để hạn chế hiện tượng quá khớp chúng ta có thể dừng phân chia nếu chạm ngưỡng số lượng quan sát tối thiểu ở node lá hoặc giới hạn về độ sâu của nhánh (chúng ta sẽ làm rõ hơn điều này ở phần bên dưới). Cách xây dựng cây quyết định theo phương pháp tìm kiếm tham lam và truy hồi dựa trên thuật toán ID3 mà ta sẽ tìm hiểu bên dưới. 8.5. Thuật toán ID3 và CART¶Thuật toán ID3 (viết tắt của Iterative Dichotomiser 3) là một giải thuật khá lâu đời được tạo ra bởi Ross Quinlan nhằm xây dựng cây quyết định phù hợp từ một bộ dữ liệu. Đây là giải thuật tiền đề mà dựa trên cơ sở đó, rất nhiều những giải thuật khác liên quan tới cây quyết định được kế thừa và phá triển:
Trong khuôn khổ bài viết này chúng ta sẽ tìm hiểu về thuật toán CART. Đây là thuật toán được sử dụng phổ biến nhất trong machine learning và có thể được sử dụng trong cả hai bài toán phân loại và hồi qui. 8.5.1. Trường hợp cây nhị phân với biến liên tục¶Giả định chúng ta đang đứng ở node lá bất kỳ, các quan sát tại node này là tập \(\mathcal{S}\) có kích thước \(|\mathcal{S}|=N\). Tại node lá này thì mức độ tinh khiết được đánh giá thông qua hàm entropy được tính theo công thức: \[\mathbf{H}(\mathcal{S}) = - \sum_{i=1}^C p_i \log(p_i)\] Trong đó \(p_i\) là tỷ lệ phần trăm các quán sát thuộc về nhãn \(i\). Lưu ý nhãn dự báo tại node lá trùng với nhãn mà có tỷ lệ lớn nhất. Trong thuật toán CART, hàm mất mát được định nghĩa là tổng có trọng số của entropy trên toàn bộ các node lá. Trọng số ở đây được lấy theo tỷ lệ phần trăm quan sát trên từng node lá. Điều đó có nghĩa rằng với những node lá có số lượng quan sát lớn thì ảnh hưởng của nó lên hàm mất mát là lớn hơn so với những node lá có số lượng quan sát nhỏ. Nhận định này là hợp lý vì việc phân loại sai những node lá lớn gây hậu quả nghiêm trọng hơn so với phân loại sai node nhỏ. Để tối thiểu hoá hàm mất mát thì chúng ta phải lựa chọn biến và ngưỡng sao cho tổng giá trị của hàm mất mát là nhỏ nhất. Tại node hiện tại, một câu hỏi đặt ra là liệu tiếp tục phân chia thì có tốt hơn không? Tốt hơn được thể hiện thông qua giá trị entropy phải giảm nhiều nhất. Nếu tốt hơn thì chúng ta phải lựa chọn biến nào tiếp theo? nếu là biến liên tục thì lựa chọn ngưỡng phân chia như thế nào? Lưu ý trong thuật toán ID3 thì chúng ta chỉ áp dụng trên các biến phân loại (category). Thuật toán CART cho phép ta tuning threshold để biến đổi biến liên tục sang các đặc trưng (features). Chẳng hạn biến được lựa chọn là \(x^{(j)}\) có ngưỡng phân chia là \(t\) thì hai đặc trưng tương ứng là \(x^{(j)} > t\) và \(x^{(j)} \leq t\). Ngưỡng \(t\) giúp phân loại tập \(\mathcal{S}\) thành hai tập con tương ứng là: \[\begin{split} \begin{split} \left\{ \begin{matrix} \mathcal{S}_0 = \{ \mathbf{x}_i | x_{i}^{(j)} \leq t, \mathbf{x}_i \in \mathcal{S} \} \\ \mathcal{S}_1 = \{ \mathbf{x}_i | x_{i}^{(j)} > t, \mathbf{x}_i \in \mathcal{S} \}\end{matrix} \right.\end{split} \end{split}\] Trong đó \(\mathbf{x}_i \in \mathbb{R}^{m}\) là quan sát thứ \(i\) của tập \(\mathcal{S}\). Quan sát này bao gồm \(m\) chiều tương ứng với số lượng biến đầu vào. \(x_{i}^{(j)}\) là quan sát thứ \(i\) của biến \(x^{(j)}\). Giả sử \(N_0 = |\mathcal{S}_0|\) và \(N_1 = |\mathcal{S}_1|\). Do hai tập con \(\mathcal{S}_1, \mathcal{S}_0\) là không giao nhau nên \(N = N_0 + N_1\). Làm sao để lựa chọn được ngưỡng t tốt nhất? Kịch bản phân chia trên giúp tạo thành hai node lá. Mức độ tinh khiết sau phân chia sẽ bằng tổng có trọng số của entropy tại mỗi node lá mới. Giá trị này được gọi là entropy sau phân chia: \[\mathbf{H}(x^{(j)}, t; \mathcal{S}) = \frac{N_0}{N}\mathbf{H}(\mathcal{S}_0) + \frac{N_1}{N} \mathbf{H}(\mathcal{S}_1)\] Ngưỡng \(t\) sẽ được tuning trong miền xác định của biến \(x^{(j)}\) sao cho entropy sau phân chia đạt được là nhỏ nhất. Điều này cũng đồng nghĩa với mức độ tinh khiết thu được tại node lá là tinh khiết nhất. Đối với biến phân loại thì chúng ta không cần phải tuning ngưỡng mà có thể trực tiếp tính ngay entropy. Một kịch bản phân chia được coi là mang lại kết quả tối hơn so với không phân chia nếu như kết quả sau phân chia giúp gia tăng độ tinh khiết. Tức là giá trị entropy trước phân chia so với sau phân chia là giảm và đồng thời chúng ta muốn mức độ giảm này là tối đa để mức độ tinh khiết đạt được cải thiện nhiều nhất. Giá trị entropy giảm chính là lượng thông tin mà ta biết thêm, giúp ích cho việc phân loại, chúng ta định nghĩa chúng dưới dạng một hàm số mới gọi là hàm tin thu (information gain): \[\begin{split}\begin{eqnarray}\mathbf{G}(x^{(j)}, t; \mathcal{S}) & = & \mathbf{H}(\mathcal{S}) - \mathbf{H}(x^{(j)}, t; \mathcal{S}) \\ & = & \mathbf{H}(\mathcal{S}) - \frac{N_0}{N}\mathbf{H}(\mathcal{S}_0) - \frac{N_1}{N} \mathbf{H}(\mathcal{S}_1)\end{eqnarray}\end{split}\] Ở mỗi lượt, giải thuật tìm kiếm tham lam sẽ tìm kiếm theo thứ tự từ trên xuống dưới biến \(x^{(j)}\) và ngưỡng \(t\) tương ứng, sao cho giá trị hàm tin thu đạt cực đại. Tức là \(j, t\) là nghiệm của bài toán tối ưu: \[\hat{j}, \hat{t} = \arg \max_{j, t} \mathbf{G}(x^{(j)}, t; \mathcal{S}) \] Như vậy chiến lược lựa chọn của thuật toán CART tại mỗi bước đó là tìm ra biến và ngưỡng phân chia mà hàm tin thu là lớn nhất. Các sự việc xảy ra trước khi quyết định phân chia tiếp được xem như là sự đã rồi và chúng ta không thay đổi được. Chính vì thế có thể coi entropy trước phân chia \(\mathbf{H}(\mathcal{S})\) là không đổi. Khi đó giá trị tối đa của hàm tin thu đạt được tương đương với giá trị của entropy sau phân chia là tối thiểu. Điều này đồng nghĩa với chúng ta có thể lựa chọn câu hỏi để hàm tin thu hoặc entropy sau phân chia là lớn nhất. Giá trị dự báo cho các quan sát thuộc về một node lá sẽ chính là nhãn có xác suất xảy ra là lớn nhất. Bài tập: Cho bảng số liệu dự báo khả năng mưa (rain) dựa trên các thông tin đầu vào gồm: có mây (cloudy), có nắng (sunny), có gió (windy):
8.5.2. Trường hợp không phải cây nhị phân¶Ở trên là bài toán tối ưu cho trường hợp cây nhị phân (mỗi node quyết định chỉ gôm hai nhánh rẽ). Chúng ta có thể khái quát bài toán cho trường hợp sau rẽ nhánh tập \(\mathcal{S}\) tạo thành \(k\) tập \(\mathcal{S}_1, \mathcal{S}_2,\dots,\mathcal{S}_{k}\). Khi đó hàm entropy sau phân chia: \[\mathbf{H}(x^{(j)}, \mathbf{t}; \mathcal{S}) = \sum_{i=1}^{k}\frac{N_i}{N}\mathbf{H}(\mathcal{S}_i)\] Với \(\mathbf{t} = (t_1, t_2, \dots, t_k-1)\) là véc tơ các ngưỡng phân chia để tạo thành \(k\) tập con. và hàm tin thu: \[\begin{split}\begin{eqnarray}\mathbf{G}(x^{(j)}, \mathbf{t}; \mathcal{S}) & = & \mathbf{H}(\mathcal{S}) - \mathbf{H}(x^{(j)}, \mathbf{t}; \mathcal{S}) \\ & = & \mathbf{H}(\mathcal{S}) - \sum_{i=1}^{k}\frac{N_i}{N}\mathbf{H}(\mathcal{S}_i)\end{eqnarray}\end{split}\] Giải thuật tìm kiếm tham lam cũng thực hiện từ trên xuống dưới và truy hồi tương tự như với trường hợp nhị phân. 8.6. Chỉ số Gini¶Chỉ số Gini là một lựa chọn khác bên cạnh hàm entropy được sử dụng để đo lường mức độ bất bình đẳng trong phân phối của các lớp. Chỉ số này được tính bằng cách lấy 1 trừ đi tổng bình phương tỷ lệ phần trăm ở mỗi lớp. \[\text{Gini} = 1-\sum_{i=1}^{C} p_i^2\] Với \(\sum_{i=1}^C p_i = 1\) do \(p_i\) là xác suất tương ứng với \(p_i = p(y=i)\). Một cách khá dễ dàng ta chứng minh được giá trị của Gini dao động trong khoảng từ 0 đến \(1-\frac{1}{C}\). Thật vậy. \[\begin{split}\begin{eqnarray}(\underbrace{\sum_{i=1}^C p_i}_{1})^2 & = & \sum_{i=1}^C p_i^2 + 2\sum_{C \geq i > j \geq 1} p_i p_j \geq \sum_{i=1}^C p_i^2 \\ \leftrightarrow 1 & \geq & \sum_{i=1}^C p_i^2 \tag{1} \end{eqnarray}\end{split}\] Đẳng thức xảy ra khi phân phối xác suất \(\mathbf{p}\) hoàn toàn thuộc về một lớp, tức ta thu được một cách phân chia tại node lá là tinh khiến thuần tuý mà không bị vẩn đục. Ở khía cạnh khác, theo bất đẳng thức cauchuy-schawrz thì: \[\begin{split}\begin{eqnarray}(\sum_{i=1}^{C}p_i)^2 & \leq & C (\sum_{i=1}^{C} p_i^2) \\ \leftrightarrow & \frac{1}{C}\leq & \sum_{i=1}^{C} p_i^2 \tag{2} \end{eqnarray}\end{split}\] Đẳng thức thu được khi phân phối xác suất hoàn toàn là đồng đều giữa các lớp. Đây là trường hợp được xem là vẩn đục mà chúng ta không mong đợi xảy ra vì mục tiêu của phân chia vẫn là các quan sát bị dồn về một nhóm. Như vậy từ \((1)\) và \((2)\) ta suy ra \(0 \leq \text{Gini} \leq 1-\frac{1}{C}\). Gini thường được dùng đối với những biến rời rạc có số lượng các trường hợp là lớn vì nó có tốc độ tính toán nhanh hơn so với hàm entropy. Trong thuật toán CART của sklearn thì chỉ số gini được sử dụng thay cho hàm entropy. 8.7. Cây quyết định cho bài toán dự báo¶Chúng ta có thể áp dụng cây quyết định cho bài toán dự báo cũng tương tự như bài toán phân loại. Điểm khác biệt đó là chúng ta không sử dụng hàm tin thu mà thay vào đó là độ suy giảm của phương sai (reduction in variance). Đầu tiên chúng ta tính phương sai trước khi phân chia của biến mục tiêu \(y\) tại node \(S\). \[\text{S}(y; \mathcal{S}) = \frac{\sum_{i=1}^{N}(y_i-\bar{y})^2}{N}\] Phương sai của biến mục tiêu sau khi phân chia sẽ bằng tổng có trọng số của phương sai trên từng nhóm: \[\text{S}(y, x^{(j)}, \mathbf{t}; \mathcal{S}) = \sum_{i=1}^{k} \frac{N_i}{N}\text{S}(y;\mathcal{S_i})\] Giá trị của độ suy giảm phương sai sau phân chia: \[\text{RV}(y, x^{(j)}, \mathbf{t}; \mathcal{S}) = \text{S}(y; \mathcal{S}) - \text{S}(y, x^{(j)}, \mathbf{t}; \mathcal{S})\] Thuật toán tìm kiếm tham lam sẽ tìm cách lựa chọn \(x_i\) và ngưỡng phân chia sao cho độ suy giảm phương sai \(\text{RV}(y, x_j, \mathbf{t}; \mathcal{S})\) là lớn nhất. Điều này cũng có nghĩa rằng các quan sát được phân về cùng một node lá thì có giá trị dự báo sát nhau. Như vậy ta có thể đưa ra một ước lượng chung cho node lá bằng trung bình cộng của biến mục tiêu mà không lo lắng giá trị dự báo bị chệch. Như vậy giá trị ước lượng của một quan sát \((\mathbf{x}_i, y_i)\) thuộc về node \(\mathcal{S}_j\) sẽ bằng trung bình cộng biến mục tiêu của node: \[\hat{y}_i = \frac{1}{|S_j|}\sum_{k=1}^{|S_j|} y_k\] 8.8. Điều kiện dừng để giảm quá khớp (overfitting)¶Nếu chúng ta tiếp tục phân chia cây quyết định liên tục thì số lượng các quan sát ở mỗi node lá sẽ giảm dần. Cho tới một ngưỡng độ sâu \(p\) nào đó, số quan sát còn lại ở mỗi node lá sẽ rất nhỏ và thậm chí chỉ một vài quan sát. Các kết quả dự báo dựa trên tập mẫu rất nhỏ này không còn mang tính tổng quát và do đó hiện tượng quá khớp thường xảy ra. Để tránh hiện tượng quá khớp cũng như tiết kiệm chi phí tính toán, chúng ta sẽ dừng việc phân chia khi đạt một số điều kiện:
Ngoài các phương pháp giảm thiểu quá khớp nêu trên chúng ta còn có thể giảm thiểu quá khớp thông qua phương pháp cắt tỉa (pruning). 8.9. Cắt tỉa (pruning)¶Nội dung của phương pháp cắt tỉa đó là đầu tiên chúng ta sẽ huấn luyện mô hình cây quyết định trên tập tập huấn luyện (train dataset) sao cho toàn bộ các quan sát đều được phân loại về đúng nhãn. Sau đó loại bỏ dần các node lá ở bên dưới và chuyển node cha trực tiếp của chúng thành node lá. Các node lá chỉ bị loại bỏ khi độ chính xác dự báo trên tập kiểm định (validation dataset) được cải thiện. Quá trình sẽ dừng khi độ chính xác trên tập kiểm tra không còn tiếp tục được cải thiện. Phương pháp trên được gọi là phương pháp giảm thiểu sai số cắt tỉa (reducing error pruning). Ngoài ra còn một kỹ thuật khác sẽ tìm cách giảm thiểu mức độ cồng kềnh của cây quyết định thông qua kiểm soát số lượng node lá. Theo đó phương pháp này cộng thêm thành phần \(K\) là số lượng node lá vào hàm mất mát là tổng entropy có trọng số của các node con. Giả sử cây quyết định cuối cùng phân loại đúng toàn bộ các quan sát về \(K\) tập tại node lá là \(\mathcal{S}_1, \mathcal{S}_2, \dots , \mathcal{S}_K\): \[\mathcal{L}(\text{final_tree}) = \sum_{i=1}^{K} \frac{|\mathcal{S}_i|}{N} \mathbf{H}(\mathcal{S}_i) + \lambda K\] Trong đó \(N\) là số lượng quan sát và \(|\mathcal{S}_i|\) là kích thước của node lá. Cũng giống như các phương pháp điều chuẩn khác, chúng ta lựa chọn \(\lambda\) là một giá trị dương tương đối nhỏ đại diện cho thành phần kiểm soát. Gía trị này lớn thể hiện vai trò của số lượng node lá tác động lên hàm chi phí lớn. Ở thời điểm ban đầu để phân loại đúng toàn bộ các quan sát thì cần số lượng node lá là \(K\) tương đối lớn. Sau đó chúng ta sẽ cắt tỉa dần cây quyết định sao cho mỗi một lượt cắt tỉa hàm mất mát giảm một lượng là lớn nhất. Quá trình cắt tỉa sẽ dừng cho tới khi hàm mất mát không còn tiếp tục giảm được nữa. 8.10. Tuning siêu tham số cho mô hình cây quyết định¶Trong thuật toán cây quyết định chúng ta có thể quan tâm tới một số tham số có thể được sử dụng để tuning. Đó là những tham số chính bên dưới: DecisionTreeRegressor(*, criterion='gini', splitter='best', max_depth=None, min_samples_split=2, min_samples_leaf=1, max_features=None, max_leaf_nodes=None, min_impurity_decrease=0.0, min_impurity_split=None ) Trong đó:
from sklearn.pipeline import Pipeline from sklearn.tree import DecisionTreeClassifier from sklearn.model_selection import GridSearchCV parameters = { 'clf__max_depth':[2, 3, 4], 'clf__criterion':['gini', 'entropy'], 'clf__min_samples_split': [2, 4], 'clf__min_samples_leaf': [5, 10, 13], 'clf__max_leaf_nodes': [8, 16, 32], } pipeline = Pipeline( steps=[("clf", DecisionTreeClassifier())] ) gscv = GridSearchCV(pipeline, parameters, cv=5, n_jobs=12, scoring='accuracy', return_train_score=True, error_score=0, verbose=3) gscv.fit(X, y) 8.11. Bài tập¶
8. 12. Tài liệu tham khảo¶
|
