Thuật toán  dùng phương thức đi từ trên xuống(top−down), tìm kiếm trên toàn bộ không gian các cây quyết định có thể.

+   Mô tả thuật toán

Trong thuật toán cơ sở ID3, việc học thực hiên  nhờ xây dựng cây quyết định  từ trên xuống, bắt đầu với câu hỏi: nên kiểm tra thuộc tính nào tại gốc của cây? Để trả lời câu hỏi này,  mỗi thuộc tính mẫu được đánh giá nhờ  kiểm định thống kê để xác định xem một mình nó sẽ phân loại các mẫu huấn luyện tốt đến mức nào theo một tiêu chuẩn chọn trước (chẳng hạn thu hoạch thông tin). Thuộc tính tốt nhất được lựa chọn và dùng như làm nút gốc cây. Nút tiếp theo(nút con) của nút gốc cây sẽ được tạo ra sau đó ứng với mỗi giá trị của thuộc tính này, và các mẫu huấn luyện sẽ được sắp xếp phù hợp với các nút con (tức là, xếp vào nhánh tương ứng với giá trị của mẫu được chọn của thuộc tính này). Toàn bộ quá trình này sau đó sẽ được lặp sử dụng các mẫu huấn luyện phù hợp với mỗi một nút tiếp theo để lựa chọn thuộc tính tốt nhất cho việc kiểm tra tại đó  trên cây. Thuật toán này theo cách tìm kiếm ăn tham để tìm ra một cây quyết định chấp nhận được mà không bao giờ phải quay lại kiểm tra những lựa chọn trước đó. Một dạng đơn giản của thuật toán, dành riêng cho các hàm có giá trị bun được trình bày trong bảng 3.1.

+   Bảng 3.1.  Thuật tuán ID3  (Examples, Target Attribute, Attributes)

Tập mẫu là tập quan sát được. Thuộc tính  đích là thuộc tính mà các giá trị của chúng được dự đoán  bởi cây. Các thuộc tính là một tập các thuộc tính khác thuộc tính đích có thể được kiểm tra bởi cây quyết định đang xét. Trả về một cây quyết định phân loại đúng  các mẫu quan sát được.

________________________________________________________________

ID3.

1.Tạo nút gốc  cho cây.

2.      Nếu  các mẫu quan sát được đều là khẳng định, trả về cây một nút gốc với nhãn = +

3.      Nếu các mẫu quan sát được là phủ định, trả về cây một nút gốc có nhãn = −

4.      Nếu tập các thuộc tính  là rỗng, trả về cây một nút gốc có nhãn = giá trị phổ biến nhất của thuộc tính đích trong tập các quan sát được

5.      Trường hợp khác:

Begin

5.1.      A  thuộc tính tốt nhất[1]  trong tập mẫu quan sát được (Examples)

5.2.   Thuộc tính quyết định cho nút gốc   A

5.3.      Với mỗi giá trị có thể vi của thuộc tính A: Thêm một nhánh cây mới bên dưới nút gốc tương ứng với điều kiện A=vi

(Ký hiệu tập mẫu Examplesv là tập con của tập mẫu có giá trị vi  ở thuộc tính A)

 5.4.Nếu Examplesv là rỗng thì thêm vào dưới nhánh mới này một nút lá với nhãn = giá trị phổ biến nhất của thuộc tính đích trong tập các mẫu,

trái lại, thêm vào dưới nhánh mới một cây con theo thủ tục

                              ID3(Examplesv , TargetAttribute, Attributes −{A})

End

    6. Trở lại gốc