[發明專利]異構代價敏感機制決策樹構建方法

在審

• 申請號: 201610437291.X
• 申請日: 2016-06-16
• 公開（公告）號: CN106611186A
• 公開（公告）日: 2017-05-03
• 發明（設計）人: 金平艷;胡成華
• 申請（專利權）人: 四川用聯信息技術有限公司
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.異構代價敏感機制決策樹構建方法，該方法涉及機器學習、人工智能以及數據挖掘領域，其特征是，包括如下步驟：

步驟1：設訓練集中有個樣本，屬性個數為，即,同時分裂屬性對應個類，其中, 相關領域用戶設定好誤分類代價矩陣C、屬性測試代價為

步驟2：創建根節點G

步驟3：如果訓練數據集為空，則返回結點G并標記失敗

步驟4： 如果訓練數據集中所有記錄都屬于同一類別，則該類型標記結點G

步驟5：如果候選屬性為空，則返回G為葉子結點，標記為訓練數據集中最普通的類

步驟6：根據屬性S的目標函數f從候選屬性中選擇

目標函數f：

為信息純度函數，為標準化測試代價比率函數，為標準化誤分類代價比率函數

當選擇屬性滿足目標函數f越大時，則找到標記結點G

當出現目標函數f相等時，為打破平局標準，則按照下面的優先順序再進行選擇：

（1）更小的

（2）更小的

步驟7：標記結點G為屬性

步驟8：根據基尼指數，由結點延伸出滿足條件為分支, 如果滿足以下兩條件之一，就停止建樹

8.1這里假設為訓練數據集中的樣本集合，如果為空，加上一個葉子結點，標記為訓練數據集中最普通的類

8.2此結點中所有例子屬于同一類

步驟9：非8.1與8.2中情況，則遞歸調用步驟6至步驟8

步驟10：利用后剪支技術解決此決策樹模型中過度擬合問題

步驟11：更新訓練數據集，保存新的示例數據。

2.根據權利要求1中所述的異構代價敏感機制決策樹構建方法，其特征是，所述步驟1中涉及到誤分類代價矩陣C、屬性測試代價為TC(S)

步驟1.1 誤分類代價矩陣C

類別標識個數為m，則該數據的代價矩陣方陣是：

其中表示第j類數據分為第i類的代價，如果為正確分類，則,否則為錯誤分類，其值由相關領域用戶給定,這里

步驟1.2屬性測試代價為TC(S)

其中為屬性測試代價，這個由用戶指定。

3.根據權利要求1中所述的異構代價敏感機制決策樹構建方法，其特征是，所述步驟6求解目標函數，即，需求解信息純度函數、標準化測試代價比率函數、標準化誤分類代價比率函數，具體求解過程如下：

步驟6.1：求解信息純度函數

基尼指數是一種不純度分裂方法，基尼指數表示為，定義為：

其中為類別在屬性值處的相對概率，當時，即在此結點處所有記錄都屬于同一類別，增加一葉子節點，即信息純度越大，反之，最大，得到的有用信息最小，則繼續根據目標函數候選下一個屬性，根據可以得知

這里屬性S有j個屬性值，即屬性值為

信息純度函數作用：可以提高決策樹的分類精度

步驟6.2：求解標準化測試代價比率函數

其中訓練集有n個候選屬性，即候選屬性為

為候選屬性測試成本

函數作用：對測試成本進行標準化，避免了決策樹在歸納學習過程中偏向數量級更大的測試屬性，另外把不同單位代價機制轉化為同一單位代價機制

步驟6.3：求解標準化誤分類代價比率函數

在分類代價基礎上，候選屬性S的標準化誤分類代價比率函數可表示為如下：

其中MC表示候選屬性分裂前的代價和，表示按候選屬性S分裂后的所有子類代價總和，其中為候選屬性S分裂后的所有類的集合，根據具體例子，MC、可以很直觀的由用戶得出

函數作用：對誤分類代價進行標準化，避免了決策樹在歸納學習過程中偏向數量級更大的測試屬性，另外把不同單位代價機制轉化為同一單位代價機制。

4.根據權利要求1中所述的異構代價敏感機制決策樹構建方法，其特征是，所述步驟10后剪支技術,具體求解過程如下：

后剪支條件為優先考慮到誤分類代價，然后考慮到測試代價，即對于用戶給

定的正數，滿足下列兩條件，則實施剪支操作

（1）

（2）

剪支條件首先要滿足盡可能的使誤分類代價比率達到用戶指定條件，然后

足測試代價低到用戶要求。