Cây quyết định là một cơ chế giống cây biểu đồ luồng, trong đó mỗi nút bên trong chỉ ra một bài kiểm tra trên một thuộc tính, mỗi bộ phận xác định kết quả của bài kiểm tra và các nút lá mô tả các lớp hoặc phân phối lớp. Nút cao nhất trong cây là nút gốc.
Các thuật toán để học Cây quyết định
Thuật toán - Tạo cây quyết định từ thông tin đào tạo đã cho.
Đầu vào - Các mẫu đào tạo, mẫu, được mô tả bằng các thuộc tính có giá trị rời rạc; tập hợp các thuộc tính sinh viên, danh sách thuộc tính.
Đầu ra - Cây quyết định.
Phương pháp
-
Tạo một nút N;
-
Nếu tất cả các mẫu đều thuộc cùng một lớp, C thì
-
Trả về N dưới dạng nút lá có nhãn lớp C
-
Nếu danh sách thuộc tính là null thì
-
Trả về N dưới dạng nút lá được gắn nhãn với lớp phổ biến nhất trong các mẫu. // biểu quyết đa số
-
Chọn thuộc tính thử nghiệm, thuộc tính trong số danh sách thuộc tính có mức tăng thông tin cao nhất.
-
Gắn nhãn nút N với thuộc tính thử nghiệm.
-
Đối với mỗi giá trị đã biết ai của thuộc tính thử nghiệm // phân vùng các mẫu.
-
Phát triển một nhánh từ nút N cho thuộc tính kiểm tra điều kiện =a i .
-
Hãy để s i là tập hợp các mẫu trong các mẫu mà test-thuộc tính =a i .
-
Nếu si trống thì
-
Nó có thể kết nối một lá được gắn nhãn với lớp phổ biến nhất trong các mẫu.
-
Khác đính kèm nút được trả về bởi cây quyết định Tạo (si, thuộc tính-danh sách - thuộc tính thử nghiệm)
Cảm ứng cây quyết định
Ví dụ, việc sản xuất tự động các quy tắc quyết định được gọi là quy tắc cảm ứng hoặc quy tắc tự động. Nó có thể là tạo ra các quy tắc quyết định trong thiết kế ngầm của cây quyết định cũng thường được gọi là quy nạp quy tắc, nhưng thuật ngữ cảm ứng cây hoặc quy tắc cây quyết định được chọn liên tục.
Thuật toán cơ bản để quy nạp cây quyết định là một thuật toán tham lam. Nó được sử dụng để tạo cây quyết định theo cách phân chia và chinh phục đệ quy từ trên xuống. Thuật toán cơ bản để học cây quyết định, là một dạng của ID3, một thuật toán quy nạp cây quyết định nổi tiếng.
Các phương pháp cơ bản như sau -
-
Cây bắt đầu như một nút riêng lẻ xác định các mẫu đào tạo.
-
Nếu tất cả các mẫu đều thuộc các lớp tương tự, thì nút sẽ biến thành một lá và được gắn nhãn với lớp đó.
-
Thuật toán áp dụng một phép đo dựa trên entropy được gọi là mức tăng thông tin như một phép tính toán kinh nghiệm để chọn thuộc tính sẽ chia các mẫu thành các lớp đơn lẻ. Thuộc tính này phát triển thành thuộc tính "kiểm tra" hoặc "quyết định" tại nút. Trong dạng thuật toán này, tất cả các thuộc tính đều là phân loại, tức là có giá trị rời rạc. Các thuộc tính có giá trị liên tục nên được loại bỏ.
-
Một bộ phận được tạo cho mỗi giá trị đã biết của thuộc tính thử nghiệm và các mẫu được phân chia một cách thích hợp.
-
Thuật toán sử dụng một vòng lặp quy trình tương tự để tạo thành cây quyết định cho các mẫu ở mỗi lần phân tách. Vì một thuộc tính đã xuất hiện tại một nút nên nó không được xử lý trong một số thuộc tính con của nút đó.