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

在審

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

技術領域

本發明涉及機器學習、人工智能以及數據挖掘領域。

背景技術

決策樹是數據挖掘和機器學習中的一項重要和積極的研究課題。其所提出的算法被廣泛地和成功地應用于實際問題中，如ID₃，CART和C4.5。現有算法之訓練決策樹分類器，旨在最大程度上提高分類的準確度，或最大限度地減少誤分類，但這必然會導致分類器偏向于主要的類而忽略罕見的或對精度影響較小的少數類。于是，在醫療診斷應用中，該反饋必然不符合數據挖掘的要求，因為在傳統決策樹方法的假設下，分布的類標記不平衡，并且所有分類錯誤造成的代價會被視為相同的成本。隨后，代價敏感決策樹學習算法引起了研究者們廣泛的興趣并取得了豐碩的研究成果。顯然構建一個適當的轉換不同代價單位的函數成為了挑戰，為此本文提出了一種有效的方法，此方法將減少所有不同代價所造成的代價機制和屬性的異質性。把所有不同的代價和屬性信息一起被納入分裂屬性選擇過程，并為此提供了一種異構代價敏感機制決策樹構建方法。

發明內容

針對異構代價平衡性以及各種代價單位機制不同問題，提出了一種異構代價敏感機制決策樹構建方法。

本發明所采用技術方案：屬性S的目標函數f(S)為候選分裂屬性選擇因子，選取最大的f(S)值作為該節點候選分裂屬性，分支的分裂屬性選擇由gini(S_i)確定，即選取更小的gini(S_i)分支，加上一個葉子節點。循環執行上述操作，就可以遍歷整個訓練樣本集，得到強分類能力以及低誤分類代價和測試代價的決策樹。同時本文建樹過程中考慮了并解決了不同代價因子、各代價單位機制不同以及與信息純度之間的平衡性問題，所以此決策樹適應范圍更廣泛。

本發明有益效果是：

1、構建的決策樹有更好分類準確度，加強了分類能力

2、在決策樹構建過程中，標準化了誤分類代價和測試成本代價，解決了候選屬性誤分類代價和測試代價的不同單位機制問題，避免了候選屬性分裂選擇 的偏向大數量級屬性問題。

3、建樹過程中，很好的平衡由于測試代價和誤分類代價以及信息純度之間的存在的異構難題，把屬性分類能力和各種代價共同融合進候選分裂屬性選擇，得到了高的分類精度和降低誤分類代價和測試代價。

附圖說明

圖1為異構代價敏感機制決策樹流程圖

具體實施方式

為解決異構代價平衡性以及各種代價單位機制不同的問題，最后生成的決策樹更好的規避了過度擬合問題，本發明結合圖1進行了詳細說明，其具體實施步驟如下：

步驟1：設訓練集中有X個樣本，屬性個數為n，即n＝(S₁，S₂，…S_n),同時分裂屬性S_i對應了m個類L，其中L_r∈(L₁，L₂…，L_m),i∈(1，2…，n)，r∈(1，2…，m)。相關領域用戶設定好誤分類代價矩陣C、屬性測試代價為cost_i。

步驟2：創建根節點G。

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

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

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

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

目標函數f：

averagegini(S)為信息純度函數，TCration(S)為標準化測試代價比率函數，MCration(S)為標準化誤分類代價比率函數。

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

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

(1)更小的MCration(S)

(2)更小的TCration(S)

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

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

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