Khai thác dữ liệu - Phân loại dựa trên quy tắc
Quy tắc IF-THEN
Bộ phân loại dựa trên quy tắc sử dụng tập hợp các quy tắc IF-THEN để phân loại. Chúng ta có thể thể hiện một quy tắc sau đây từ:
Hãy để chúng tôi xem xét một quy tắc R1,
R1: IF age = youth AND student = yes
THEN buy_computer = yesPoints to remember −
Phần IF của quy tắc được gọi là rule antecedent hoặc là precondition.
Phần THEN của quy tắc được gọi là rule consequent.
Phần tiền nghiệm điều kiện bao gồm một hoặc nhiều thử nghiệm thuộc tính và các thử nghiệm này được AND hợp lý hóa.
Phần kết quả bao gồm dự đoán lớp.
Note - Chúng ta cũng có thể viết quy tắc R1 như sau:
R1: (age = youth) ^ (student = yes))(buys computer = yes)Nếu điều kiện đúng với một bộ giá trị nhất định, thì tiền đề được thỏa mãn.
Trích xuất quy tắc
Ở đây chúng ta sẽ học cách xây dựng bộ phân loại dựa trên quy tắc bằng cách trích xuất các quy tắc IF-THEN từ cây quyết định.
Points to remember −
Để trích xuất quy tắc từ cây quyết định -
Một quy tắc được tạo cho mỗi đường dẫn từ gốc đến nút lá.
Để tạo thành một tiền đề quy tắc, mỗi tiêu chí tách được AND một cách hợp lý.
Nút lá giữ dự đoán lớp, do đó hình thành quy tắc.
Quy tắc cảm ứng sử dụng thuật toán bao phủ tuần tự
Thuật toán bao gồm tuần tự có thể được sử dụng để trích xuất các quy tắc IF-THEN tạo thành dữ liệu huấn luyện. Chúng tôi không yêu cầu tạo cây quyết định trước. Trong thuật toán này, mỗi quy tắc cho một lớp nhất định bao gồm nhiều bộ giá trị của lớp đó.
Một số Thuật toán che phủ tuần tự là AQ, CN2 và RIPPER. Theo chiến lược chung, các quy tắc được học lần lượt. Đối với mỗi quy tắc thời gian được học, một bộ được bao phủ bởi quy tắc sẽ bị xóa và quá trình tiếp tục cho phần còn lại của các bộ. Điều này là do đường dẫn đến mỗi lá trong cây quyết định tương ứng với một quy tắc.
Note - Quy nạp cây quyết định có thể coi là học đồng thời một tập các quy tắc.
Sau đây là Thuật toán học tuần tự trong đó các quy tắc được học cho một lớp tại một thời điểm. Khi học một quy tắc từ một lớp Ci, chúng ta muốn quy tắc chỉ bao gồm tất cả các bộ giá trị từ lớp C và không có tuple tạo thành bất kỳ lớp nào khác.
Algorithm: Sequential Covering
Input:
D, a data set class-labeled tuples,
Att_vals, the set of all attributes and their possible values.
Output: A Set of IF-THEN rules.
Method:
Rule_set={ }; // initial set of rules learned is empty
for each class c do
repeat
Rule = Learn_One_Rule(D, Att_valls, c);
remove tuples covered by Rule form D;
until termination condition;
Rule_set=Rule_set+Rule; // add a new rule to rule-set
end for
return Rule_Set;Quy tắc cắt tỉa
Quy tắc bị cắt bỏ là do lý do sau:
Việc đánh giá chất lượng được thực hiện trên bộ dữ liệu đào tạo gốc. Quy tắc có thể hoạt động tốt trên dữ liệu đào tạo nhưng kém hơn trên dữ liệu tiếp theo. Đó là lý do tại sao quy tắc cắt tỉa là bắt buộc.
Quy tắc được lược bớt bằng cách loại bỏ liên từ. Quy tắc R được lược bớt, nếu phiên bản R được lược bớt có chất lượng cao hơn những gì được đánh giá trên một tập hợp các bộ giá trị độc lập.
FOIL là một trong những phương pháp đơn giản và hiệu quả để cắt tỉa theo quy tắc. Đối với một quy tắc R đã cho,
trong đó pos và neg lần lượt là số bộ giá trị dương được bao phủ bởi R.
Note- Giá trị này sẽ tăng theo độ chính xác của R trên bộ cắt tỉa. Do đó, nếu giá trị FOIL_Prune cao hơn đối với phiên bản R được lược bớt, thì chúng ta sẽ lược bớt R.