Tìm hiểu quy tắc phân lớp là một cách tiếp cận quan trọng cho nhiều ứng dụng khai phá dữ liệu. Mục tiêu của nó là để tìm ra một số các quy tắc trong cơ sở dữ liệu để hình thành một phân lớp đúng đắn. Quy nạp cây quyết định được coi như là một đại diện của cách tiếp cận truyền thống cho khai phá quy tắc phân loại. Quy nạp cây quyết định thực hiện tìm kiếm cục bộ dựa trên kinh nghiệm bằng cách mỗi lần thêm một thuộc tính vào các quy tắc theo một thứ tự tốt nhất. Quy nạp cây định quyết thực hiện việc rút gọn các quy tắc một cách có hệ thống. Trong đó giá trị của các quy tắc được đánh giá bằng sự đóng góp của chúng vào sự chính xác của toàn bộ quá trình phân lớp. Tính loại trừ của các quy tắc và sự phân cấp của cây tổng quát cho phép áp dụng phương pháp rút gọn cây quyết định từ dưới lên mà không phải lo lắng về sự tương tác lẫn nhau giữa các luật [6].
Tuy nhiên, quy nạp cây quyết định có thể làm mất một vài cấu trúc tiêu biểu đó là những thuộc tính chung để xác định lớp. Cây quyết định có hai hạn chế cơ bản đó là sự phân mảnh và nhân bản. Vấn đề phân mảnh là cây quyết định cần phải phân đoạn dữ liệu nhiều lần để thu được tất cả các mẫu đào tạo. Việc phân đoạn lặp lại giảm mất tính khái quát và có thể có ảnh hưởng không tốt đến tính chính xác của thuật toán phân lớp. Vấn đề nhân bản là một phần của cây con được dựng lại nhiều lần, điều đó dẫn đến cây quyết định có chiều rất sâu và khó hiểu [6].
61
Phụ thuộc hàm đã được nghiên cứu từ lâu trong thiết kế cơ sở dữ liệu quan hệ. Phụ thuộc hàm giữa các thuộc tính của một quan hệ biểu diễn một tập các ràng buộc toàn vẹn trong quan hệ, có thể sử dụng để thiết kế những quan hệ tốt trong cơ sở dữ liệu. Những ràng buộc này đảm bảo tính toàn vẹn khi thao tác dữ liệu. Phụ thuộc hàm giữa hai tập thuộc tính (X,Y), được ký hiệu bằng X Y, biểu thị giá trị của Y được quyết định hoàn bởi giá trị của X. Vì vậy, phân tích phụ thuộc hàm là quan trọng và sự phức tạp của việc phân tích thường phụ thuộc rất nhiều vào số lượng các thuộc tính của cơ sở dữ liệu.
Gần đây việc quan tâm đến vấn đề tìm ra phụ thuộc hàm được tăng lên. Cho một lược đồ quan hệ R, và một thể hiện r của lược đồ, vấn đề là xác định tất cả các phụ thuộc hàm trên toàn r. Mục tiêu của việc tìm hiểu vấn đề phụ thuộc hàm đến từ những lĩnh vực ứng dụng khác nhau đó là: quản trị và thiết kế cơ sở dữ liệu, truy vấn, kho dữ liệu, phân tích trực tuyến và khai phá dữ liệu. Một số những thuật toán có hiệu quả như Tane, Fdep, Dep-Miner và Fun đã được đề nghị để tìm ra phụ thuộc hàm trong cơ sở dữ liệu.
Một xấp xỉ phụ thuộc được hiểu gần như là một phụ thuộc hàm. Sự phụ thuộc tồn tại trong cơ sở dữ liệu khi có sự phụ thuộc tự nhiên giữa các thuộc tính, nhưng một số hàng (bản ghi) bị lỗi hoặc biểu diễn những quy tắc ngoại lệ [6]. Một vài độ đo sai số được đề xuất để đo sự xấp xỉ của một phụ thuộc hàm là chấp nhận được trong một quan hệ là số các cặp vi phạm, số các bản ghi được loại bỏ để thu được một phụ thuộc hàm thỏa mãn.
Trong phần dưới đây, chúng ta tìm hiểu một phương pháp mới để xây dựng một cây quyết định phân lớp bằng sử dụng xấp xỉ phụ thuộc hàm. Phương pháp này khác hẳn so với những cách thức truyền thống trước đây để xây dựng cây quyết định, nó tìm kiếm hỗn hợp các thuộc tính cho những đỉnh riêng biệt của một cây quyết định phân lớp, điều đó thực chất nhắm đến cây quyết định nhỏ hơn và dễ hiểu hơn, mà không có những tác động bất lợi lên độ chính xác. Đỉnh của cây quyết định với hỗn hợp các thuộc tính có thể khắc phục được hai hạn chế của cây quyết định đã đề cập ở trên [6].
62