[發明專利]基于資源約束代價敏感決策樹構建方法

在審

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

1.基于資源約束代價敏感決策樹構建方法，該方法涉及人工智能、機器學習技術領域，其特征是：利用EP準則先把訓練集多類標識為兩類，在條件下，再根據選擇屬性代價增益率為目標函數：這個準則,f越大屬性特征越好，則此屬性作為結點或是擴展結點，最后形成的決策樹，為了避免過度擬合的問題，用后剪支算法優化決策樹

其具體的實施步驟如下：

步驟1：設訓練集中X個樣本，屬性個數為n，即，同時分裂屬性對應了個類，其，，相關領域用戶設定好誤分類代價矩陣C,L利用EP準則對類進行處理得到誤分類代價矩陣；

步驟2：創建根節點G；

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

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

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

步驟6：根據屬性S的代價增益率候選屬性中選擇；

目標函數f：

為訓練集總誤分類代價，為選擇屬性S總代價函數，為選擇屬性S資源損耗代價函數；

在條件下，當選擇屬性滿足f函數越大時，則找到標記結點G;

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

步驟8：由結點延伸出滿足條件為分支；

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

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

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

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

2.根據權利要求1所述的基于資源約束代價敏感決策樹構建方法，其特征是：所述步驟1基于EP準則對類進行簡化處理方法為：

1、誤分類代價矩陣C

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

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

2、EP準則

設訓練數據集X,其類有m個，假如判定當前結點的類標號為,把判定為P例，則其他的就為N例:

其中表示該屬性中類別為樣例個數，為P例代價，為該結點產生的總P例代價;

同理可得出N例有效代價

基于EP的結點類標號判定方法為：

m個類用EP準則判定為兩類情況，如圖2，其中TN代表真正反例，TP代表真正正例，與為預測正確時產生的代價，此時假設、都等于1為誤分類代價，一般情況下，;

即得誤分類代價矩陣為：

。

3.根據權利要求1所述的基于資源約束代價敏感決策樹構建方法，其特征是：所述步驟6計算候選屬性的選擇因子—代價增益率f,需要求出總誤分類代價函數、總代價函數、資源損耗代價函數，具體計算過程如下：

步驟6.1 ：求解總誤分類代價函數

根據EP準則可以得出訓練數據集中總的（P,N）分布值，（P,N）滿足條件；決策樹正例總誤分析代價c由相關專家給出，反例總誤分析代價為,所以：

步驟6.2 ： 求解總代價函數

步驟6.2.1：求解測試代價函數

假設當前選擇屬性S的測試成本為, 由用戶根據實際情況估計，，把S屬性根據類結點劃分為三部分，已知值個數與，未知值；

屬性S的總樣例個數為：

則屬性S的測試代價函數為：

上式為第1分支正例的個數 ,為第1分支反例的個數；

為第2分支正例個數，為第2分支反例的個數；

步驟6.2.2：求解誤分類代價函數

假設屬性S第一個分支為正例結點，即; 則第二分支則為反例結點，即，第三分支未知；

從上述指標可以得出誤分類代價指標函數：

上式為第1分支FP代價，為第1分支FN代價，和用戶根據具體情況來自定義；

步驟6.3：資源損耗代價函數

這里為預測的資源測試代價，為第2分支FP代價，為第2分支

支FN代價，用戶設定。

4.根據權利要求1所述的基于資源約束代價敏感決策樹構建方法，其特征是：所述步驟10后剪支技術為：

后剪支目標函數為總測試代價減少率：

用戶自定義一個減少率因子

其中，TTC是剪支之前的初始樹的總平均測試代價，為剪支之后的總平均測試代價，當直到滿足以下條件，我們就實施剪支操作：

其中正數為用戶指定達到的條件，剪枝的條件首先要滿足盡可能使代價減損達到用戶指定條件，然后滿足測試代價降低到用戶要求。