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 lớn nhất trong cây là nút gốc.
Các vấn đề xây dựng cây quyết định có thể được định nghĩa một cách đệ quy. Đầu tiên, chọn một thuộc tính để đặt ở nút gốc và tạo một nhánh cho mỗi giá trị có thể. Điều này chia tập hợp ví dụ thành các tập con, một tập cho mỗi giá trị của thuộc tính. Quy trình này có thể được lặp lại một cách đệ quy cho mọi chi nhánh, chỉ sử dụng những trường hợp đến được với bộ phận đó. Nếu một số trường hợp tại một nút có phân loại tương tự, hãy ngừng tạo phần tử đó của cây.
Phép đo độ tinh khiết mà chúng ta sẽ sử dụng được gọi là thông tin và được đo bằng đơn vị gọi là bit. Được liên kết với mỗi nút của cây, nó đại diện cho lượng thông tin dự kiến cần thiết để chỉ định liệu một phiên bản mới nên được phân loại là có hay không, với điều kiện là các phiên bản đã đến được nút đó.
Cắt tỉa là quy trình làm giảm kích thước của cây quyết định. Nó được sử dụng để giảm nguy cơ trang bị quá mức bằng cách mô tả kích thước của cây hoặc loại bỏ các khu vực của cây cung cấp ít năng lượng. Việc cắt tỉa cung cấp bằng cách cắt tỉa các bộ phận tuân theo sự bất thường trong dữ liệu đào tạo do nhiễu hoặc ngoại lệ và cung cấp cây ban đầu theo phương pháp cải thiện hiệu quả tổng quát hóa của cây.
Một số phương pháp thường sử dụng các biện pháp thống kê để loại bỏ các bộ phận kém tin cậy nhất, thường dẫn đến việc phân loại nhanh hơn và nâng cao khả năng phân loại chính xác dữ liệu thử nghiệm độc lập của cây.
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 các mẫu là một số cùng loại, thì C
-
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 thường gặp 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 giữa danh sách thuộc tính có mức tăng thông tin lớn 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, a i 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 s i trống sau đó
-
Nó có thể được liên kết vớ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 Tạo cây quyết định (s i , thuộc tính-danh sách - thuộc tính thử nghiệm)