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
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
- Cách tính và đánh giá điểm phân tách ứng viên trong một dữ liệu
- Cách sắp xếp các phần tách thành cấu trúc cây quyết định
- Cách áp dụng thuật toán cây phân loại và hồi quy vào bài toán thực 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ập nhật tháng 1/2017. Đã thay đổi phép tính của fold_size trong cross_validation_split[] thành luôn là một số nguyên. Khắc phục sự cố với Python 3
- Cập nhật tháng 2/2017. Đã sửa lỗi trong build_tree
- Cập nhật tháng 8/2017. Đã sửa lỗi trong tính toán Gini, thêm trọng số còn thiếu của điểm Gini nhóm theo quy mô nhóm [cảm ơn Michael. ]
- Cập nhật tháng 8/2018. Đã kiểm tra và cập nhật để hoạt động với Python 3. 6
Cách triển khai thuật toán cây quyết định từ đầu trong Python
Ảnh của Martin Cathrae, bảo lưu một số quyền
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 quy
Câ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í
- hồi quy. Hàm chi phí được tối thiểu hóa để chọn các điểm phân tách là tổng bình phương lỗi trên tất cả các mẫu đào tạo nằm trong hình chữ nhật
- phân loại. Hàm chi phí Gini được sử dụng để cung cấp chỉ báo về mức độ tinh khiết của các nút, trong đó độ tinh khiết của nút đề cập đến mức độ hỗn hợp của dữ liệu huấn luyện được gán cho mỗi nút
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ấy
Bộ 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
- phương sai của hình ảnh Biến đổi Wavelet [liên tục]
- độ lệch của hình ảnh Biến đổi Wavelet [liên tục]
- độ nhọn của hình ảnh Biến đổi Wavelet [liên tục]
- entropy của ảnh [liên tục]
- hạng [số nguyên]
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ẫn
Hướng dẫn này được chia thành 5 phần
- Chỉ số Gini
- Tạo phân chia
- Xây dựng một cây
- Làm cho một dự đoán
- Nghiên cứu điển hình về tiền giấy
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ố Gini
Chỉ 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 chia
Mộ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à
- Tách một tập dữ liệu
- Đánh giá tất cả các phần tách
Chúng ta hãy xem xét từng
2. 1. Tách một tập dữ liệu
Tá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]