Mã Python cây quyết định
|
Chúng phổ biến vì mô hình cuối cùng rất dễ hiểu đối với các học viên cũng như các chuyên gia trong lĩnh vực. Cây quyết định cuối cùng có thể giải thích chính xác lý do tại sao một dự đoán cụ thể được đưa ra, làm cho nó rất hấp dẫn để sử dụng trong hoạt động Show Cây quyết định cũng cung cấp nền tảng cho các phương pháp tập hợp nâng cao hơn như đóng gói, rừng ngẫu nhiên và tăng cường độ dốc Trong hướng dẫn này, bạn sẽ khám phá cách triển khai thuật toán Cây phân loại và hồi quy từ đầu bằng Python Sau khi hoàn thành hướng dẫn này, bạn sẽ biết
Bắt đầu dự án của bạn với cuốn sách mới của tôi Thuật toán học máy từ đầu, bao gồm hướng dẫn từng bước và tệp mã nguồn Python cho tất cả các ví dụ Bắt đầu nào
Cách triển khai thuật toán cây quyết định từ đầu trong Python mô tảPhần này giới thiệu ngắn gọn về thuật toán Cây phân loại và hồi quy cũng như bộ dữ liệu Tiền giấy được sử dụng trong hướng dẫn này Cây phân loại và hồi quyCây phân loại và hồi quy hay viết tắt là GIỎI là một từ viết tắt do Leo Breiman giới thiệu để chỉ các thuật toán Cây quyết định có thể được sử dụng để phân loại hoặc các bài toán mô hình dự đoán hồi quy Chúng tôi sẽ tập trung vào việc sử dụng GIỎ HÀNG để phân loại trong hướng dẫn này Biểu diễn của mô hình GIỎ HÀNG là một cây nhị phân. Đây là cùng một cây nhị phân từ các thuật toán và cấu trúc dữ liệu, không có gì quá cầu kỳ (mỗi nút có thể có 0, một hoặc hai nút con) Một nút đại diện cho một biến đầu vào duy nhất (X) và một điểm phân chia trên biến đó, giả sử biến đó là số. Các nút lá (còn gọi là các nút đầu cuối) của cây chứa một biến đầu ra (y) được sử dụng để đưa ra dự đoán Sau khi được tạo, một cây có thể được điều hướng với một hàng dữ liệu mới theo sau mỗi nhánh với các phần tách cho đến khi đưa ra dự đoán cuối cùng Tạo cây quyết định nhị phân thực sự là một quá trình phân chia không gian đầu vào. Một cách tiếp cận tham lam được sử dụng để phân chia không gian được gọi là phân chia nhị phân đệ quy. Đây là một quy trình số trong đó tất cả các giá trị được xếp thẳng hàng và các điểm phân chia khác nhau được thử và kiểm tra bằng cách sử dụng hàm chi phí Phần chia có chi phí tốt nhất (chi phí thấp nhất vì chúng tôi giảm thiểu chi phí) được chọn. Tất cả các biến đầu vào và tất cả các điểm phân chia có thể được đánh giá và lựa chọn một cách tham lam dựa trên hàm chi phí
Việc phân tách tiếp tục cho đến khi các nút chứa số lượng ví dụ đào tạo tối thiểu hoặc đạt đến độ sâu cây tối đa Bộ dữ liệu tiền giấyBộ dữ liệu tiền giấy liên quan đến việc dự đoán xem một tờ tiền nhất định có phải là tiền thật hay không dựa trên một số biện pháp được thực hiện từ một bức ảnh Tập dữ liệu chứa 1.372 hàng với 5 biến số. Đó là một vấn đề phân loại với hai lớp (phân loại nhị phân) Dưới đây cung cấp danh sách năm biến trong tập dữ liệu
Dưới đây là mẫu của 5 hàng đầu tiên của tập dữ liệu 1 2 3 4 5 6 3. 6216,8. 6661,-2. 8073,-0. 44699,0 4. 5459,8. 1674,-2. 4586,-1. 4621,0 3. 866,-2. 6383,1. 9242,0. 10645,0 3. 4566,9. 5228,-4. 0112,-3. 5944,0 0. 32924,-4. 4552,4. 5718,-0. 9888,0 4. 3684,9. 6718,-3. 9606,-3. 1625,0 Sử dụng Thuật toán quy tắc 0 để dự đoán giá trị lớp phổ biến nhất, độ chính xác cơ bản của vấn đề là khoảng 50% Bạn có thể tìm hiểu thêm và tải xuống bộ dữ liệu từ Kho lưu trữ học máy của UCI Tải xuống tập dữ liệu và đặt nó vào thư mục làm việc hiện tại của bạn với tên tệp data_banknote_authentication. csv hướng dẫnHướng dẫn này được chia thành 5 phần
Các bước này sẽ cung cấp cho bạn nền tảng cần thiết để triển khai thuật toán GIỎ HÀNG từ đầu và áp dụng nó cho các vấn đề về mô hình dự đoán của riêng bạn 1. Chỉ số GiniChỉ số Gini là tên của hàm chi phí được sử dụng để đánh giá các phần tách trong tập dữ liệu Sự phân chia trong tập dữ liệu liên quan đến một thuộc tính đầu vào và một giá trị cho thuộc tính đó. Nó có thể được sử dụng để chia các mẫu đào tạo thành hai nhóm hàng Điểm Gini cho biết mức độ phân chia tốt như thế nào bằng cách trộn lẫn các lớp trong hai nhóm được tạo bởi sự phân chia. Một sự phân tách hoàn hảo dẫn đến điểm Gini là 0, trong khi sự phân chia trường hợp xấu nhất dẫn đến các lớp 50/50 trong mỗi nhóm dẫn đến điểm Gini là 0. 5 (đối với bài toán 2 lớp) Tính toán Gini được thể hiện tốt nhất với một ví dụ Chúng tôi có hai nhóm dữ liệu với 2 hàng trong mỗi nhóm. Các hàng trong nhóm đầu tiên đều thuộc loại 0 và các hàng trong nhóm thứ hai thuộc loại 1, vì vậy đây là một sự phân chia hoàn hảo Trước tiên chúng ta cần tính tỷ lệ các lớp trong mỗi nhóm 1 tỷ lệ = đếm (class_value) / đếm (hàng) Tỷ lệ cho ví dụ này sẽ là 1 2 3 4 nhóm_1_lớp_0 = 2 / 2 = 1 nhóm_1_lớp_1 = 0/2 = 0 nhóm_2_lớp_0 = 0/2 = 0 nhóm_2_lớp_1 = 2 / 2 = 1 Gini sau đó được tính cho mỗi nút con như sau 1 2 gini_index = tổng (tỷ lệ * (1. 0 - tỷ lệ)) gini_index = 1. 0 - tổng (tỷ lệ * tỷ lệ) Sau đó, chỉ số Gini cho mỗi nhóm phải được tính trọng số theo quy mô của nhóm, so với tất cả các mẫu trong nhóm gốc, e. g. tất cả các mẫu hiện đang được nhóm. Chúng ta có thể thêm trọng số này vào phép tính Gini cho một nhóm như sau 1 gini_index = (1. 0 - tổng(tỷ lệ * tỷ lệ)) * (group_size/total_samples) Trong ví dụ này, điểm Gini cho mỗi nhóm được tính như sau 1 2 3 4 5 6 Gini(nhóm_1) = (1 - (1*1 + 0*0)) * 2/4 Gini(nhóm_1) = 0. 0 * 0. 5 Gini(nhóm_1) = 0. 0 Gini(nhóm_2) = (1 - (0*0 + 1*1)) * 2/4 Gini(nhóm_2) = 0. 0 * 0. 5 Gini(nhóm_2) = 0. 0 Sau đó, điểm số được cộng trên mỗi nút con tại điểm phân tách để đưa ra điểm Gini cuối cùng cho điểm phân tách có thể được so sánh với các điểm phân tách của ứng viên khác Gini cho điểm phân chia này sau đó sẽ được tính bằng 0. 0 + 0. 0 hoặc điểm Gini hoàn hảo là 0. 0 Dưới đây là một hàm có tên gini_index() tính toán chỉ số Gini cho danh sách các nhóm và danh sách các giá trị lớp đã biết Bạn có thể thấy rằng có một số kiểm tra an toàn trong đó để tránh chia cho 0 cho một nhóm trống 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 # Tính toán chỉ số Gini cho tập dữ liệu phân tách def gini_index(nhóm, classes): # đếm tất cả các mẫu tại điểm phân tách n_instances = float(tổng([len(group) for group in groups])) # tổng chỉ số Gini có trọng số cho mỗi nhóm gini = 0. 0 cho nhóm trong nhóm. size = float(len(group)) # tránh chia cho 0 if kích thước == 0. tiếp tục điểm = 0. 0 # chấm điểm nhóm dựa trên điểm từng lớp cho class_val trong các lớp. p = [hàng[-1] for row in group].đếm(class_val) / size điểm += p * p # cân điểm số của nhóm theo quy mô tương đối của nó gini += (1. 0 - điểm) * (size / n_instances) return gini Chúng tôi có thể kiểm tra chức năng này với ví dụ đã làm việc của chúng tôi ở trên. Chúng tôi cũng có thể kiểm tra trường hợp xấu nhất là chia 50/50 trong mỗi nhóm. Ví dụ đầy đủ được liệt kê dưới đây 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 # Tính toán chỉ số Gini cho tập dữ liệu phân tách def gini_index(nhóm, classes): # đếm tất cả các mẫu tại điểm phân tách n_instances = float(tổng([len(group) for group in groups])) # tổng chỉ số Gini có trọng số cho mỗi nhóm gini = 0. 0 cho nhóm trong nhóm. size = float(len(group)) # tránh chia cho 0 if kích thước == 0. tiếp tục điểm = 0. 0 # chấm điểm nhóm dựa trên điểm từng lớp cho class_val trong các lớp. p = [hàng[-1] for row in group].đếm(class_val) / size điểm += p * p # cân điểm số của nhóm theo quy mô tương đối của nó gini += (1. 0 - điểm) * (size / n_instances) return gini
# kiểm tra giá trị Gini print(gini_index([[[1, 1], [1, 0]], [[1, 1], [1, 0]]], [0, 1])) print(gini_index([[[1, 0], [1, 0]], [[1, 1], [1, 1]]], [0, 1])) Chạy ví dụ in ra hai điểm Gini, đầu tiên là điểm cho trường hợp xấu nhất bằng 0. 5 theo sau là điểm cho trường hợp tốt nhất ở mức 0. 0 1 2 0. 5 0. 0 Bây giờ chúng ta đã biết cách đánh giá kết quả của một lần phân tách, hãy xem xét việc tạo các lần phân tách 2. Tạo phân chiaMột phần tách bao gồm một thuộc tính trong tập dữ liệu và một giá trị Chúng ta có thể tóm tắt điều này dưới dạng chỉ mục của một thuộc tính cần tách và giá trị để tách các hàng trên thuộc tính đó. Đây chỉ là cách viết tắt hữu ích để lập chỉ mục cho các hàng dữ liệu Tạo một sự phân chia bao gồm ba phần, phần đầu tiên chúng ta đã xem xét là tính điểm Gini. Hai phần còn lại là
Chúng ta hãy xem xét từng 2. 1. Tách một tập dữ liệuTách tập dữ liệu có nghĩa là tách tập dữ liệu thành hai danh sách hàng được cung cấp chỉ mục của một thuộc tính và giá trị phân tách cho thuộc tính đó Khi chúng tôi có hai nhóm, chúng tôi có thể sử dụng điểm Gini ở trên để đánh giá chi phí của việc chia tách Việc chia tách tập dữ liệu liên quan đến việc lặp lại từng hàng, kiểm tra xem giá trị thuộc tính nằm dưới hay cao hơn giá trị được chia và gán nó cho nhóm bên trái hoặc bên phải tương ứng Dưới đây là một hàm có tên test_split() thực hiện quy trình này 1 2 3 4 5 6 7 8 9 # Tách tập dữ liệu dựa trên thuộc tính và giá trị thuộc tính def test_split(index, value, dataset): trái, phải = danh sách(), list() cho hàng trong tập dữ liệu. if hàng[chỉ mục] < value: trái. chắp thêm(hàng) khác. đúng. chắp thêm(hàng) quay lại trái, phải Không có gì nhiều cho nó Lưu ý rằng nhóm bên phải chứa tất cả các hàng có giá trị tại chỉ mục ở trên hoặc bằng giá trị được phân tách 2. 2. Đánh giá tất cả các phần táchVới chức năng Gini ở trên và chức năng phân tách thử nghiệm, giờ đây chúng ta có mọi thứ cần thiết để đánh giá các lần phân tách Đưa ra một tập dữ liệu, chúng tôi phải kiểm tra mọi giá trị trên từng thuộc tính dưới dạng phân tách ứng cử viên, đánh giá chi phí phân tách và tìm cách phân tách tốt nhất có thể mà chúng tôi có thể thực hiện Sau khi tìm thấy sự phân chia tốt nhất, chúng ta có thể sử dụng nó như một nút trong cây quyết định của mình Đây là một thuật toán toàn diện và tham lam Chúng tôi sẽ sử dụng một từ điển để đại diện cho một nút trong cây quyết định vì chúng tôi có thể lưu trữ dữ liệu theo tên. Khi chọn điểm phân chia tốt nhất và sử dụng nó làm nút mới cho cây, chúng tôi sẽ lưu trữ chỉ mục của thuộc tính đã chọn, giá trị của thuộc tính đó để phân chia và hai nhóm dữ liệu được phân chia theo điểm phân chia đã chọn Mỗi nhóm dữ liệu là tập dữ liệu nhỏ của riêng nó chỉ gồm những hàng được gán cho nhóm bên trái hoặc bên phải theo quy trình phân tách. Bạn có thể tưởng tượng làm thế nào chúng ta có thể chia lại từng nhóm một cách đệ quy khi chúng ta xây dựng cây quyết định của mình Dưới đây là một hàm có tên get_split() thực hiện thủ tục này. Bạn có thể thấy rằng nó lặp qua từng thuộc tính (ngoại trừ giá trị lớp) và sau đó là từng giá trị cho thuộc tính đó, phân tách và đánh giá các phân tách khi nó diễn ra Phần tách tốt nhất được ghi lại và sau đó được trả lại sau khi hoàn tất tất cả các kiểm tra 1 2 3 4 5 6 7 8 9 10 11 # Chọn điểm phân tách tốt nhất cho tập dữ liệu def get_split(tập dữ liệu): class_values = danh sách(bộ(row[-1] for row in dataset)) b_index, b_value, b_score, b_groups = 999, 999, 999, None cho chỉ mục trong phạm vi(len(dataset[0])-1): cho hàng trong tập dữ liệu. nhóm = test_split(chỉ mục, row[index], dataset) gini = gini_index(nhóm, class_values) if gini < b_score. b_index, b_value, b_score, b_groups = index, row[index], gini, groups return {'index'. b_index, 'value'. b_value, 'nhóm'. b_groups} Chúng tôi có thể tạo ra một tập dữ liệu nhỏ để kiểm tra chức năng này và toàn bộ quá trình chia tách tập dữ liệu của chúng tôi 1 2 3 4 5 6 7 8 9 10 11 X1 X2 Y 2. 771244718 1. 784783929 0 1. 728571309 1. 169761413 0 3. 678319846 2. 81281357 0 3. 961043357 2. 61995032 0 2. 999208922 2. 209014212 0 7. 497545867 3. 162953546 1 9. 00220326 3. 339047188 1 7. 444542326 0. 476683375 1 10. 12493903 3. 234550982 1 6. 642287351 3. 319983761 1 Chúng ta có thể vẽ tập dữ liệu này bằng cách sử dụng các màu riêng biệt cho từng lớp. Bạn có thể thấy rằng sẽ không khó để chọn thủ công một giá trị X1 (trục x trên biểu đồ) để phân chia tập dữ liệu này GIỎ HÀNG Ví dụ dưới đây kết hợp tất cả những điều này lại với nhau 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 # Tách tập dữ liệu dựa trên thuộc tính và giá trị thuộc tính def test_split(index, value, dataset): trái, phải = danh sách(), list() cho hàng trong tập dữ liệu. if hàng[chỉ mục] < value: trái. chắp thêm(hàng) khác. đúng. chắp thêm(hàng) quay lại trái, phải
# Tính toán chỉ số Gini cho tập dữ liệu phân tách def gini_index(nhóm, classes): # đếm tất cả các mẫu tại điểm phân tách n_instances = float(tổng([len(group) for group in groups])) # tổng chỉ số Gini có trọng số cho mỗi nhóm gini = 0. 0 cho nhóm trong nhóm. size = float(len(group)) # tránh chia cho 0 if kích thước == 0. tiếp tục điểm = 0. 0 # chấm điểm nhóm dựa trên điểm từng lớp cho class_val trong các lớp. p = [hàng[-1] for row in group].đếm(class_val) / size điểm += p * p # cân điểm số của nhóm theo quy mô tương đối của nó gini += (1. 0 - điểm) * (size / n_instances) return gini
# Chọn điểm phân tách tốt nhất cho tập dữ liệu def get_split(tập dữ liệu): class_values = danh sách(bộ(row[-1] for row in dataset)) b_index, b_value, b_score, b_groups = 999, 999, 999, None cho chỉ mục trong phạm vi(len(dataset[0])-1): cho hàng trong tập dữ liệu. nhóm = test_split(chỉ mục, row[index], dataset) gini = gini_index(nhóm, class_values) in('X%d < %. 3fGini=%. 3f' % ((chỉ số+1), row[index], gini)) if gini < b_score. b_index, b_value, b_score, b_groups = index, row[index], gini, groups return {'index'. b_index, 'value'. b_value, 'nhóm'. b_groups}
tập dữ liệu = [[2. 771244718,1. 784783929,0], [1. 728571309,1. 169761413,0], [3. 678319846,2. 81281357,0], [3. 961043357,2. 61995032,0], [2. 999208922,2. 209014212,0], [7. 497545867,3. 162953546,1], [9. 00220326,3. 339047188,1], [7. 444542326,0. 476683375,1], [10. 12493903,3. 234550982,1], [6. 642287351,3. 319983761,1]] split = get_split(tập dữ liệu) in('Tách. [X%d < %. 3f]' % ((tách['index']+1), split['value'])) Hàm get_split() đã được sửa đổi để in ra từng điểm phân tách và đó là chỉ số Gini khi nó được đánh giá Chạy ví dụ này in tất cả điểm Gini và sau đó in điểm phân chia tốt nhất trong tập dữ liệu của X1 < 6. 642 với Chỉ số Gini bằng 0. 0 hoặc một sự phân chia hoàn hảo 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 X1 < 2. 771 Gini=0. 444 X1 < 1. 729 Gini=0. 500 X1 < 3. 678 Gini=0. 286 X1 < 3. 961 Gini=0. 167 X1 < 2. 999 Gini=0. 375 X1 < 7. 498 Gini=0. 286 X1 < 9. 002 Gini=0. 375 X1 < 7. 445 Gini=0. 167 X1 < 10. 125 Gini=0. 444 X1 < 6. 642 Gini=0. 000 X2 < 1. 785 Gini=0. 500 X2 < 1. 170 Gini=0. 444 X2 < 2. 813 Gini=0. 320 X2 < 2. 620 Gini=0. 417 X2 < 2. 209 Gini=0. 476 X2 < 3. 163 Gini=0. 167 X2 < 3. 339 Gini=0. 444 x2 < 0. 477 Gini=0. 500 X2 < 3. 235 Gini=0. 286 X2 < 3. 320 Gini=0. 375 Tách ra. [X1 < 6. 642] Bây giờ chúng ta đã biết cách tìm các điểm phân chia tốt nhất trong tập dữ liệu hoặc danh sách các hàng, hãy xem cách chúng ta có thể sử dụng nó để xây dựng cây quyết định 3. Xây dựng một câyTạo nút gốc của cây dễ dàng Chúng tôi gọi hàm get_split() ở trên bằng cách sử dụng toàn bộ tập dữ liệu Adding more nodes to our tree is more interesting Xây dựng một cây có thể được chia thành 3 phần chính
3. 1. Terminal NodesWe need to decide when to stop growing a tree Chúng ta có thể làm điều đó bằng cách sử dụng độ sâu và số lượng hàng mà nút chịu trách nhiệm trong tập dữ liệu huấn luyện
These two approaches will be user-specified arguments to our tree building procedure There is one more condition. It is possible to choose a split in which all rows belong to one group. In this case, we will be unable to continue splitting and adding child nodes as we will have no records to split on one side or another Now we have some ideas of when to stop growing the tree. When we do stop growing at a given point, that node is called a terminal node and is used to make a final prediction Điều này được thực hiện bằng cách lấy nhóm hàng được gán cho nút đó và chọn giá trị lớp phổ biến nhất trong nhóm. This will be used to make predictions Below is a function named to_terminal() that will select a class value for a group of rows. It returns the most common output value in a list of rows 1 2 3 4 # Create a terminal node value def to_terminal(nhóm): kết quả = [hàng[-1] for row in group] trả về tối đa(đặt(outcomes), key=outcomes.đếm) 3. 2. Tách đệ quyChúng tôi biết cách thức và thời điểm tạo các nút đầu cuối, bây giờ chúng tôi có thể xây dựng cây của mình Xây dựng cây quyết định liên quan đến việc gọi đi gọi lại hàm get_split() đã phát triển ở trên trên các nhóm được tạo cho mỗi nút Các nút mới được thêm vào một nút hiện có được gọi là các nút con. Một nút có thể không có nút con (nút cuối), một nút con (một bên đưa ra dự đoán trực tiếp) hoặc hai nút con. Chúng tôi sẽ gọi các nút con là trái và phải trong biểu diễn từ điển của một nút nhất định Khi một nút được tạo, chúng ta có thể tạo đệ quy các nút con trên từng nhóm dữ liệu từ quá trình phân tách bằng cách gọi lại cùng một chức năng Dưới đây là một chức năng thực hiện thủ tục đệ quy này. Nó lấy một nút làm đối số cũng như độ sâu tối đa, số mẫu tối thiểu trong một nút và độ sâu hiện tại của nút Bạn có thể tưởng tượng làm thế nào điều này có thể được gọi lần đầu tiên đi qua trong nút gốc và độ sâu của 1. Chức năng này được giải thích tốt nhất trong các bước
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 # Tạo phần tách con cho nút hoặc tạo thiết bị đầu cuối def tách(nút, max_depth, min_size, depth): trái, phải = nút['groups'] del(nút['nhóm']) # kiểm tra xem có chia không nếu không rời hoặc không right: nút['left'] = node['right'] = to_terminal(left + right) trở lại # kiểm tra độ sâu tối đa if độ sâu >= max_depth. nút['left'], node['right'] = to_terminal(left), to_terminal(right) trở lại # quá trình bỏ con if len(left) <= min_size: nút['left'] = to_terminal(left) khác. nút['left'] = get_split(left) tách(nút['trái'], max_depth, min_size, depth+1) # xử lý đúng con nếu len(đúng) <= min_size: nút['đúng'] = to_terminal(right) khác. nút['đúng'] = get_split(right) tách(nút['đúng'], max_depth, min_size, depth+1) 3. 3. Xây dựng một câyBây giờ chúng ta có thể đặt tất cả các mảnh lại với nhau Xây dựng cây liên quan đến việc tạo nút gốc và gọi hàm split(), chức năng này sau đó gọi chính nó theo cách đệ quy để xây dựng toàn bộ cây Dưới đây là hàm build_tree() nhỏ thực hiện quy trình này 1 2 3 4 5 # Xây dựng cây quyết định def build_tree(huấn luyện, max_depth, min_size): root = get_split(huấn luyện) tách(root, max_depth, min_size, 1) trả về gốc Chúng tôi có thể kiểm tra toàn bộ quy trình này bằng cách sử dụng tập dữ liệu nhỏ mà chúng tôi đã tạo ra ở trên Dưới đây là ví dụ hoàn chỉnh Ngoài ra còn có một hàm print_tree() nhỏ in đệ quy các nút của cây quyết định với một dòng trên mỗi nút. Mặc dù không nổi bật như sơ đồ cây quyết định thực, nhưng nó đưa ra ý tưởng về cấu trúc cây và các quyết định được đưa ra xuyên suốt 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 # Tách tập dữ liệu dựa trên thuộc tính và giá trị thuộc tính def test_split(index, value, dataset): trái, phải = danh sách(), list() cho hàng trong tập dữ liệu. if hàng[chỉ mục] < value: trái. chắp thêm(hàng) khác. đúng. chắp thêm(hàng) quay lại trái, phải
# Tính toán chỉ số Gini cho tập dữ liệu phân tách def gini_index(nhóm, classes): # đếm tất cả các mẫu tại điểm phân tách n_instances = float(tổng([len(group) for group in groups])) # tổng chỉ số Gini có trọng số cho mỗi nhóm gini = 0. 0 cho nhóm trong nhóm. size = float(len(group)) # tránh chia cho 0 if kích thước == 0. tiếp tục điểm = 0. 0 # chấm điểm nhóm dựa trên điểm từng lớp cho class_val trong các lớp. p = [hàng[-1] for row in group].đếm(class_val) / size điểm += p * p # cân điểm số của nhóm theo quy mô tương đối của nó gini += (1. 0 - điểm) * (size / n_instances) return gini
# Chọn điểm phân tách tốt nhất cho tập dữ liệu def get_split(tập dữ liệu): class_values = danh sách(bộ(row[-1] for row in dataset)) b_index, b_value, b_score, b_groups = 999, 999, 999, None cho chỉ mục trong phạm vi(len(dataset[0])-1): cho hàng trong tập dữ liệu. nhóm = test_split(chỉ mục, row[index], dataset) gini = gini_index(nhóm, class_values) if gini < b_score. b_index, b_value, b_score, b_groups = index, row[index], gini, groups return {'index'. b_index, 'value'. b_value, 'nhóm'. b_groups}
# Create a terminal node value def to_terminal(nhóm): kết quả = [hàng[-1] for row in group] trả về tối đa(đặt(outcomes), key=outcomes.đếm)
# Tạo phần tách con cho nút hoặc tạo thiết bị đầu cuối def tách(nút, max_depth, min_size, depth): trái, phải = nút['groups'] del(nút['nhóm']) # kiểm tra xem có chia không nếu không rời hoặc không right: nút['left'] = node['right'] = to_terminal(left + right) trở lại # kiểm tra độ sâu tối đa if độ sâu >= max_depth. nút['left'], node['right'] = to_terminal(left), to_terminal(right) trở lại # quá trình bỏ con if len(left) <= min_size: nút['left'] = to_terminal(left) khác. nút['left'] = get_split(left) tách(nút['trái'], max_depth, min_size, depth+1) # xử lý đúng con nếu len(đúng) <= min_size: nút['đúng'] = to_terminal(right) khác. nút['đúng'] = get_split(right) tách(nút['đúng'], max_depth, min_size, depth+1)
# Xây dựng cây quyết định def build_tree(huấn luyện, max_depth, min_size): root = get_split(huấn luyện) tách(root, max_depth, min_size, 1) trả về gốc
# In cây quyết định def print_tree(nút, depth=0): if isinstance(nút, dict): in('%s[X%d < %. 3f]' % ((độ sâu*' ', (node['index']+1), node['value']))) print_tree(nút['left'], depth+1) print_tree(nút['đúng'], depth+1) khác. in('%s[%s]' % ((depth*' ', node)))
tập dữ liệu = [[2. 771244718,1. 784783929,0], [1. 728571309,1. 169761413,0], [3. 678319846,2. 81281357,0], [3. 961043357,2. 61995032,0], [2. 999208922,2. 209014212,0], [7. 497545867,3. 162953546,1], [9. 00220326,3. 339047188,1], [7. 444542326,0. 476683375,1], [10. 12493903,3. 234550982,1], [6. 642287351,3. 319983761,1]] tree = build_tree(tập dữ liệu, 1, 1) print_tree(tree) Chúng ta có thể thay đổi đối số độ sâu tối đa khi chạy ví dụ này và xem hiệu ứng trên cây in Với độ sâu tối đa là 1 (tham số thứ hai trong lệnh gọi hàm build_tree()), chúng ta có thể thấy rằng cây sử dụng phép chia hoàn hảo mà chúng ta đã khám phá trong phần trước. Đây là cây có một nút, còn được gọi là gốc quyết định 1 2 3 [X1 < 6. 642] [0] [1] Tăng độ sâu tối đa lên 2, chúng tôi buộc cây phải tách ngay cả khi không yêu cầu. The X1 attribute is then used again by both the left and right children of the root node to split up the already perfect mix of classes 1 2 3 4 5 6 7 [X1 < 6. 642] [X1 < 2. 771] [0] [0] [X1 < 7. 498] [1] [1] Cuối cùng, và ngược lại, chúng ta có thể buộc thêm một mức phân tách với độ sâu tối đa là 3 1 2 3 4 5 6 7 8 9 10 11 12 13 [X1 < 6. 642] [X1 < 2. 771] [0] [X1 < 2. 771] [0] [0] [X1 < 7. 498] [X1 < 7. 445] [1] [1] [X1 < 7. 498] [1] [1] These tests show that there is great opportunity to refine the implementation to avoid unnecessary splits. Điều này còn lại như là một phần mở rộng Now that we can create a decision tree, let’s see how we can use it to make predictions on new data 4. Làm cho một dự đoánĐưa ra dự đoán với cây quyết định liên quan đến việc điều hướng cây bằng hàng dữ liệu được cung cấp cụ thể Một lần nữa, chúng ta có thể thực hiện điều này bằng cách sử dụng hàm đệ quy, trong đó quy trình dự đoán tương tự được gọi lại với các nút con bên trái hoặc bên phải, tùy thuộc vào cách phân chia ảnh hưởng đến dữ liệu được cung cấp Chúng ta phải kiểm tra xem nút con có phải là giá trị đầu cuối được trả về dưới dạng dự đoán hay không hoặc nếu đó là nút từ điển chứa cấp độ khác của cây được xem xét Dưới đây là hàm predict() thực hiện thủ tục này. Bạn có thể thấy cách chỉ mục và giá trị trong một nút nhất định Bạn có thể thấy cách chỉ mục và giá trị trong một nút nhất định được sử dụng để đánh giá liệu hàng dữ liệu được cung cấp nằm ở bên trái hay bên phải của phần tách 1 2 3 4 5 6 7 8 9 10 11 12 # Đưa ra dự đoán với cây quyết định def predict(node, row). if hàng[nút['index']] < node['value']: nếu thể hiện(nút['left'], dict): return predict(nút['left'], row) khác. return node['left'] khác. nếu thể hiện(nút['right'], dict): return predict(nút['right'], row) khác. return node['right'] Chúng tôi có thể sử dụng tập dữ liệu giả định của mình để kiểm tra chức năng này. Dưới đây là một ví dụ sử dụng cây quyết định được mã hóa cứng với một nút duy nhất phân tách dữ liệu tốt nhất (gốc quyết định) Ví dụ đưa ra dự đoán cho từng hàng trong tập dữ liệu 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 # Đưa ra dự đoán với cây quyết định def predict(node, row). if hàng[nút['index']] < node['value']: nếu thể hiện(nút['left'], dict): return predict(nút['left'], row) khác. return node['left'] khác. nếu thể hiện(nút['right'], dict): return predict(nút['right'], row) khác. return node['right']
tập dữ liệu = [[2. 771244718,1. 784783929,0], [1. 728571309,1. 169761413,0], [3. 678319846,2. 81281357,0], [3. 961043357,2. 61995032,0], [2. 999208922,2. 209014212,0], [7. 497545867,3. 162953546,1], [9. 00220326,3. 339047188,1], [7. 444542326,0. 476683375,1], [10. 12493903,3. 234550982,1], [6. 642287351,3. 319983761,1]]
# dự đoán bằng gốc cây stump = {'index'. 0, 'đúng'. 1, 'giá trị'. 6. 642287351, 'trái'. 0} cho hàng trong tập dữ liệu. dự đoán = dự đoán(gốc, row) in('Dự kiến=%d, Đã nhận=%d' % (row[-1], prediction)) Chạy ví dụ in dự đoán chính xác cho mỗi hàng, như mong đợi 1 2 3 4 5 6 7 8 9 10 Mong đợi = 0, Got = 0 Mong đợi = 0, Got = 0 Mong đợi = 0, Got = 0 Mong đợi = 0, Got = 0 Mong đợi = 0, Got = 0 Kỳ vọng = 1, Got = 1 Kỳ vọng = 1, Got = 1 Kỳ vọng = 1, Got = 1 Kỳ vọng = 1, Got = 1 Kỳ vọng = 1, Got = 1 Bây giờ chúng ta biết cách tạo cây quyết định và sử dụng nó để đưa ra dự đoán. Bây giờ, hãy áp dụng nó vào tập dữ liệu thực 5. Nghiên cứu điển hình về tiền giấyPhần này áp dụng thuật toán GIỎ HÀNG cho tập dữ liệu Tiền giấy The first step is to load the dataset and convert the loaded data to numbers that we can use to calculate split points. For this we will use the helper function load_csv() to load the file and str_column_to_float() to convert string numbers to floats We will evaluate the algorithm using k-fold cross-validation with 5 folds. This means that 1372/5=274. 4 hoặc chỉ hơn 270 bản ghi sẽ được sử dụng trong mỗi lần. Chúng tôi sẽ sử dụng các hàm trợ giúp đánh giá_algorithm() để đánh giá thuật toán bằng xác thực chéo và precision_metric() để tính toán độ chính xác của các dự đoán Một chức năng mới có tên Decision_tree() được phát triển để quản lý ứng dụng của thuật toán GIỎ HÀNG, đầu tiên tạo cây từ tập dữ liệu huấn luyện, sau đó sử dụng cây để đưa ra dự đoán trên tập dữ liệu thử nghiệm Ví dụ đầy đủ được liệt kê dưới đây 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 # GIỎ HÀNG trên bộ dữ liệu Ghi chú ngân hàng từ ngẫu nhiên nhập hạt từ ngẫu nhiên nhập xếp ngẫu nhiên từ csv nhập trình đọc
# Tải tệp CSV def load_csv(filename). tệp = mở(tên tệp, "rt") dòng = trình đọc(tệp) tập dữ liệu = danh sách(dòng) trả về tập dữ liệu
# Chuyển đổi cột chuỗi thành float def str_column_to_float(tập dữ liệu, column): cho hàng trong tập dữ liệu. hàng[cột] = float(row[column].cởi bỏ())
# Tách tập dữ liệu thành k phần def cross_validation_split(dataset, n_folds). dataset_split = danh sách() dataset_copy = list(dataset) fold_size = int(len(dataset) / n_folds) cho i trong phạm vi(n_folds): gấp = danh sách() while len(gấp) < fold_size: chỉ mục = dãy(len(dataset_copy)) gấp. chắp thêm(dataset_copy. pop(index)) dataset_split. chắp thêm(gấp) return tập dữ liệu_ tách
# Tính tỷ lệ phần trăm chính xác def accuracy_metric(thực tế, predicted): đúng = 0 cho i trong phạm vi(len(actual)): nếu thực tế[i] == predicted[i]: đúng += 1 trả về đúng / phao(len(actual)) * 100.0
# Đánh giá thuật toán bằng cách sử dụng phân tách xác thực chéo def evaluate_algorithm(tập dữ liệu, algorithm, n_folds, *args): folds = cross_validation_split(tập dữ liệu, n_folds) scores = list() cho gấp trong gấp. train_set = danh sách(gấp) train_set. xóa(gấp) train_set = sum(train_set, []) test_set = danh sách() cho hàng trong gấp. row_copy = danh sách(hàng) test_set. chắp thêm(row_copy) row_copy[-1] = None được dự đoán = thuật toán(train_set, test_set, *args) thực tế = [hàng[-1] for row in fold] độ chính xác = accuracy_metric(thực tế, predicted) điểm. chắp thêm(độ chính xác) trả về điểm
# Tách tập dữ liệu dựa trên thuộc tính và giá trị thuộc tính def test_split(index, value, dataset): trái, phải = danh sách(), list() cho hàng trong tập dữ liệu. if hàng[chỉ mục] < value: trái. chắp thêm(hàng) khác. đúng. chắp thêm(hàng) quay lại trái, phải
# Tính toán chỉ số Gini cho tập dữ liệu phân tách def gini_index(nhóm, classes): # đếm tất cả các mẫu tại điểm phân tách n_instances = float(tổng([len(group) for group in groups])) # tổng chỉ số Gini có trọng số cho mỗi nhóm gini = 0. 0 cho nhóm trong nhóm. size = float(len(group)) # tránh chia cho 0 if kích thước == 0. tiếp tục điểm = 0. 0 # chấm điểm nhóm dựa trên điểm từng lớp cho class_val trong các lớp. p = [hàng[-1] for row in group].đếm(class_val) / size điểm += p * p # cân điểm số của nhóm theo quy mô tương đối của nó gini += (1. 0 - điểm) * (size / n_instances) return gini
# Chọn điểm phân tách tốt nhất cho tập dữ liệu def get_split(tập dữ liệu): class_values = danh sách(bộ(row[-1] for row in dataset)) b_index, b_value, b_score, b_groups = 999, 999, 999, None cho chỉ mục trong phạm vi(len(dataset[0])-1): cho hàng trong tập dữ liệu. nhóm = test_split(chỉ mục, row[index], dataset) gini = gini_index(nhóm, class_values) if gini < b_score. b_index, b_value, b_score, b_groups = index, row[index], gini, groups return {'index'. b_index, 'value'. b_value, 'nhóm'. b_groups}
# Create a terminal node value def to_terminal(nhóm): kết quả = [hàng[-1] for row in group] trả về tối đa(đặt(outcomes), key=outcomes.đếm)
# Tạo phần tách con cho nút hoặc tạo thiết bị đầu cuối def tách(nút, max_depth, min_size, depth): trái, phải = nút['groups'] del(nút['nhóm']) # kiểm tra xem có chia không nếu không rời hoặc không right: nút['left'] = node['right'] = to_terminal(left + right) trở lại # kiểm tra độ sâu tối đa if độ sâu >= max_depth. nút['left'], node['right'] = to_terminal(left), to_terminal(right) trở lại # quá trình bỏ con if len(left) <= min_size: nút['left'] = to_terminal(left) khác. nút['left'] = get_split(left) tách(nút['trái'], max_depth, min_size, depth+1) # xử lý đúng con nếu len(đúng) <= min_size: nút['đúng'] = to_terminal(right) khác. nút['đúng'] = get_split(right) tách(nút['đúng'], max_depth, min_size, depth+1)
# Xây dựng cây quyết định def build_tree(huấn luyện, max_depth, min_size): root = get_split(huấn luyện) tách(root, max_depth, min_size, 1) trả về gốc
# Đưa ra dự đoán với cây quyết định def predict(node, row). if hàng[nút['index']] < node['value']: nếu thể hiện(nút['left'], dict): return predict(nút['left'], row) khác. return node['left'] khác. nếu thể hiện(nút['right'], dict): return predict(nút['right'], row) khác. return node['right']
# Thuật toán cây phân loại và hồi quy def decision_tree(huấn luyện, test, max_depth, min_size): tree = build_tree(đào tạo, max_depth, min_size) dự đoán = danh sách() cho hàng trong thử nghiệm. dự đoán = dự đoán(cây, row) dự đoán. chắp thêm(dự đoán) return(dự đoán)
# Kiểm tra GIỎ HÀNG trên tập dữ liệu Bank Note hạt(1) # tải và chuẩn bị dữ liệu tên tệp = 'data_banknote_authentication. csv' tập dữ liệu = load_csv(tên tệp) # chuyển thuộc tính chuỗi thành số nguyên cho i trong phạm vi(len(dataset[0])): str_column_to_float(tập dữ liệu, i) # đánh giá thuật toán n_folds = 5 max_depth = 5 min_size = 10 điểm = evaluate_algorithm(tập dữ liệu, decision_tree, n_folds, max_depth, min_size) in('Điểm. %s' % điểm) in('Độ chính xác trung bình. %. 3f%%' % (tổng(scores)/float(len(scores)))) Ví dụ sử dụng độ sâu cây tối đa là 5 lớp và số hàng tối thiểu trên mỗi nút là 10. Các tham số này cho GIỎ HÀNG đã được chọn bằng một thử nghiệm nhỏ, nhưng không có nghĩa là chúng tối ưu Chạy ví dụ in độ chính xác phân loại trung bình trên mỗi nếp gấp cũng như hiệu suất trung bình trên tất cả các nếp gấp Bạn có thể thấy rằng GIỎ HÀNG và cấu hình đã chọn đạt được độ chính xác phân loại trung bình khoảng 97%, tốt hơn đáng kể so với thuật toán Quy tắc 0 đạt độ chính xác 50% 1 2 Điểm số. [96. 35036496350365, 97. 08029197080292, 97. 44525547445255, 98. 17518248175182, 97. 44525547445255] Độ chính xác trung bình. 97. 299% Tiện ích mở rộngPhần này liệt kê các tiện ích mở rộng cho hướng dẫn này mà bạn có thể muốn khám phá
Bạn đã khám phá bất kỳ tiện ích mở rộng nào trong số này chưa? Xem xét lạiTrong hướng dẫn này, bạn đã khám phá cách triển khai thuật toán cây quyết định từ đầu bằng Python Cây quyết định trong Python là gì?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 học các quy tắc quyết định đơn giản được suy ra từ các tính năng dữ liệu
Cây quyết định Python chính xác đến mức nào?Độ chính xác được tính toán bằng cách so sánh giá trị tập kiểm tra thực tế và giá trị dự đoán. Có vẻ như thuật toán cây quyết định của chúng ta có độ chính xác là 67. 53% . Một giá trị cao này thường được coi là tốt. |
