[發明專利]一種多維尺度的異構代價敏感決策樹構建方法

在審

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

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

步驟1：設訓練集中有X個樣本，屬性個數為n，即,同時分裂屬性對應了m個類L，其中, ，相關領域用戶設定好誤分類代價矩陣C、屬性測試代價為、資源調節因子—相對等待時間代價值

1）上述步驟1中所述的誤分類代價矩陣C具體設定如下：

相關領域用戶誤分類代價矩陣C的設定：

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

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

步驟2：創建根節點G

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

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

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

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

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

步驟8：由結點延伸出滿足條件為分支,同時利用先剪枝技術對葉子節點進行剪枝操作，一邊建樹一邊剪枝，如果滿足以下兩條件之一，就停止建樹

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

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

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

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

2.根據權利要求1中所述的一種多維尺度的異構代價敏感決策樹構建方法，其特征是，以上所述步驟6中相關的計算過程如下：

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

目標函數：

為信息純度函數，為代價效度函數

其中—代價效度函數公式為：

為誤分類損失代價減少函數，為測試代價與相對等待時間代價的總代價函數

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

2）上述步驟6求解目標函數，需要先求解—信息純度函數、—代價效度函數，具體求解過程如下：

2.1) 計算—信息純度函數的具體過程如下：

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

其中為類別在屬性值處的相對概率，當時，即在此結點處所有記錄都屬于同一類別，增加一葉子節點，即信息純度越大，

反之，最大，得到的有用信息最小，則繼續根據目標函數候選下一個屬性

根據可以得知

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

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

2.2) 求解—代價效度函數

求解—代價效度函數，需要先求解—誤分類損失代價減少函數和—測試代價與相對等待時間代價的總代價函數

2.2.1）求解—誤分類損失代價減少函數具體過程如下：

如果對事例預測的類標簽與真實類標簽相同，則分類正確，此時的誤分類代價，如果，則，在分類過程中，通常不知道事例的實際標簽，所以這里用誤分類代價的期望Emc來代替誤分類代價的值，即，把一個事例的類標簽預測為的誤分類代價的期望為：

Emc

其中，L為數據集中所有類標簽集合，為當前選擇屬性中含有類的概率，為把類誤分為類的代價花費

分裂屬性的選擇還應該以誤分類代價降低最大為基本原則，在沒有選擇屬性時有一個總的誤分類代價mc，選擇任何一個屬性進行測試，都有可能減少一定的誤分類代價，這里構造出誤分類損失代價減少函數

為還沒有選擇分裂屬性前的所有誤分類代價的總和，這個可以根據用戶設定的誤分類代價矩陣很容易求得出來

2.2.2）求解—測試代價與相對等待時間代價的總代價函數具體過程如下：

其中是個調節因子，不同資源不同，資源越多越大，反之也成立，為屬性測試代價函數，為相對等待時間代價函數，由專家確定

屬性測試代價為設定如下：

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

以下具體介紹相對等待時間代價：

等待時間代價與時間有關，即我們可以用數值來描述這些時間敏感代價，如

果結果可以馬上得到，等待時間代價為0；如果結果要幾天，就由相應專家確定一個數值，另外規定，如果一定要這個測試結果出來才能進行下一個測試，即使等待的時間不多，如半天或一天，都把這個等待時間代價設為一個很大的常數，即

等待時間同時還和當地資源有關，同時考慮時間代價和資源約束代價

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

（1）更大的

（2）更小的。

3.根據權利要求1中所述的一種多維尺度的異構代價敏感決策樹構建方法，其特征是，以上所述步驟8中相關的計算過程如下：

步驟8：由結點延伸出滿足條件為分支,同時利用先剪枝技術對葉子節點進行剪枝操作，一邊建樹一邊剪枝，如果滿足以下兩條件之一，就停止建樹

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

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

3）上述步驟8所述的先剪枝技術，其判定條件具體如下：

為一個葉子節點類的樣本數，X為訓練集總體樣本數，為用戶基于訓練集的樣本個數百分比的最小值設定的一個適當的閾值，剪枝條件首先要達到用戶指定條件。