資料探勘 - 基於規則的分類

IF-THEN 規則

基於規則的分類器使用一組 IF-THEN 規則進行分類。我們可以用以下形式表達規則：

讓我們考慮規則 R1：

R1: IF age = youth AND student = yes 
   THEN buy_computer = yes

要點：

• 規則的 IF 部分稱為規則前件或前提條件。

• 規則的 THEN 部分稱為規則後件。

• 前件部分的條件包含一個或多個屬性測試，這些測試透過邏輯 AND 連線。

• 後件部分包含類預測。

注意：我們也可以將規則 R1 寫成如下形式：

R1: (age = youth) ^ (student = yes))(buys computer = yes)

如果給定元組的條件為真，則前件滿足。

規則提取

在這裡，我們將學習如何透過從決策樹中提取 IF-THEN 規則來構建基於規則的分類器。

要點：

要從決策樹中提取規則：

• 為從根節點到葉節點的每條路徑建立一個規則。

• 要形成規則前件，每個分割標準都透過邏輯 AND 連線。

• 葉節點包含類預測，形成規則後件。

使用順序覆蓋演算法進行規則歸納

順序覆蓋演算法可用於從訓練資料中提取 IF-THEN 規則。我們不需要首先生成決策樹。在這個演算法中，給定類的每個規則都覆蓋該類的許多元組。

一些順序覆蓋演算法包括 AQ、CN2 和 RIPPER。根據通用策略，規則一次學習一個。每次學習規則時，都會刪除該規則覆蓋的元組，並對其餘元組繼續該過程。這是因為決策樹中到每個葉節點的路徑都對應於一個規則。

注意：決策樹歸納可以被認為是同時學習一組規則。

以下是順序學習演算法，其中規則一次學習一個類。當從類 Ci 中學習規則時，我們希望該規則僅覆蓋來自類 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;

規則剪枝

規則剪枝的原因如下：

• 質量評估是在原始訓練資料集上進行的。規則在訓練資料上可能表現良好，但在後續資料上表現不佳。這就是為什麼需要規則剪枝。

• 透過刪除合取來剪枝規則。如果規則 R 的剪枝版本比在獨立元組集上評估的質量更高，則對規則 R 進行剪枝。

FOIL 是一種簡單有效的規則剪枝方法。對於給定的規則 R：

其中 pos 和 neg 分別是 R 覆蓋的正元組和負元組的數量。

注意：此值會隨著 R 在剪枝集上的準確性而增加。因此，如果 R 的剪枝版本的 FOIL_Prune 值更高，則我們剪枝 R。