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

在審

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

技術領域

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

背景技術

決策樹研究是數據挖掘和機器學習中的一項重要和積極的研究課題。其所提出的算法被廣泛地和成功地應用于實際問題中，如ID₃，CART和C4.5，此類經典學習算法主要是研究準確率的問題，能夠得到更高準確性的決策樹。在現有的算法中，其大多數都只傾向于考慮測試代價和誤分類錯誤代價中的一種，此類算法稱為一維尺度代價敏感，其構建的決策樹在現實案例中不能夠解決綜合問題。在代價敏感學習中除了考慮測試代價和誤分類代價對分類的影響，還需考慮待時間代價對分類預測的影響，例如，患者可能存在測試代價約束，也有可能存在等待時間上的約束，根據不同類別需求人所具備的自身資源不同，所需的時間長短也不同，考慮各種代價單位機制不同的問題，另外在構建決策樹過程中，采用先剪支技術來解決決策樹中過擬合問題，為了解決這種需求，本發明在之前一維和二維尺度代價基礎上，提出了一種多維尺度的異構代價敏感決策樹構建方法。

這里所涉及的代價影響因子有三種：測試代價、相對等待時間代價以及誤分類代價，它們的單位代價機制互不相同，另外也需考慮各種代價和屬性信息之間的平衡性問題，基于在之前多維尺度的異構代價敏感決策樹構建方法的基礎上，提出了一種標準化的多維尺度代價敏感決策樹的構建方法。

發明內容

針對于解決三種代價影響因子的不同單位機制問題以及三種代價與屬性信息之間的平衡性問題，提出了一種標準化的多維尺度代價敏感決策樹構建方法。

為解決上述問題，本發明是通過以下技術方案實現的：

一種標準化的多維尺度代價敏感決策樹構建方法，包括如下步驟：

步驟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、屬性S_i測試代價為資源調節因子∝、相對等待時間代價wc(S_i)、修正系數β，判定條件閾值p、α以及γ。

步驟2：創建根節點G。

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

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

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

步驟6：根據屬性S_i的目標函數f(S_i)從候選屬性中選擇splitS_i。

目標函數f(S_i)：

averagegain(S_i)為平均信息增益函數，(ZTC(S_i))_normal為標準化總測試代價函數，Rmc(S_i)_normal為標準化的誤分類代價比率函數。當選擇屬性splitS_i滿足目標函數f(S_i)越大，則找到標記節點G。

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

(1)更小的Rmc(S_i)_normal

(2)更小的(ZTC(S_i))_normal

步驟7：標記節點G為屬性splitS_i。

步驟8：由節點延伸出滿足條件為splitS＝splitS_i分支,這里假設滿足條件的分支個數為k,此時在此節點再加一個空節點，即當前節點的分支個數為k+1,同時利用先剪枝技術對節點進行剪枝操作，一邊建樹一邊剪枝，如果滿足以下兩條件之一，就停止建樹。

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

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

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