[發(fā)明專利]一種多維尺度的異構(gòu)代價敏感決策樹構(gòu)建方法

在審

• 申請?zhí)枺?/td>: 201610445671.8
• 申請日: 2016-06-17
• 公開（公告）號: CN106611187A
• 公開（公告）日: 2017-05-03
• 發(fā)明（設(shè)計）人: 金平艷;胡成華
• 申請（專利權(quán)）人: 四川用聯(lián)信息技術(shù)有限公司
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術(shù)領(lǐng)域

本發(fā)明涉及機器學(xué)習(xí)、人工智能以及數(shù)據(jù)挖掘領(lǐng)域。

背景技術(shù)

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

發(fā)明內(nèi)容

針對于解決同時考慮測試代價、誤分類代價以及等待時間代價影響因子來構(gòu)建多維尺度決策樹過程的問題、考慮各種代價單位機制不同的問題，提出了一種多維尺度的異構(gòu)代價敏感決策樹構(gòu)建方法。

為解決上述問題，本發(fā)明提出了以下技術(shù)方案：

一種多維尺度的異構(gòu)代價敏感決策樹構(gòu)建方法，包括如下步驟：

步驟1：設(shè)訓(xùn)練集中有X個樣本，屬性個數(shù)為n，即n＝(S₁，S₂，…S_n),同時分裂屬性S_i對應(yīng)了m個類L，其中L_r∈(L₁，L₂…，L_m),i∈(1，2…，n)，r∈(1，2…，m)。相關(guān)領(lǐng)域用戶設(shè)定好誤分類代價矩陣C、屬性S_i測試代價為cost_i、資源調(diào)節(jié)因子∝、相對等待時間代價wc(S_i)。

步驟2：創(chuàng)建根節(jié)點G。

步驟3：如果訓(xùn)練數(shù)據(jù)集為空，則返回節(jié)點G并標記失敗。

步驟4：如果訓(xùn)練數(shù)據(jù)集中所有記錄都屬于同一類別，則該類型標記節(jié)點G。

步驟5：如果候選屬性為空，則返回G為葉子結(jié)點，標記為訓(xùn)練數(shù)據(jù)集中最 普通的類。

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

目標函數(shù)f(S_i)：

averagegini(S_i)為信息純度函數(shù)，D(S_i)為各種代價效度函數(shù)。當(dāng)選擇屬性splitS_i滿足目標函數(shù)f(S_i)越大，則找到標記節(jié)點G。

當(dāng)出現(xiàn)目標函數(shù)f(S_i)相等時，為打破平局標準，則按照下面的優(yōu)先順序再進行選擇：

(1)更大的Dmc(S_i)

(2)更小的ZTC(S_i)

步驟7：標記節(jié)點G為屬性splitS_i。

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

8.1這里假設(shè)Y_i為訓(xùn)練數(shù)據(jù)集中splitS＝splitS_i的樣本集合，如果Y_i為空，加上一個葉子結(jié)點，標記為訓(xùn)練數(shù)據(jù)集中最普通的類。

8.2此結(jié)點中所有例子屬于同一類。

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

步驟10：更新訓(xùn)練數(shù)據(jù)集，保存新的示例數(shù)據(jù)。

本發(fā)明有益效果是：

1、構(gòu)建的決策樹有更好分類準確度，加強了分類能力，避免了當(dāng)類中有稀有類時，把它當(dāng)做普通類進行分類。

2、考慮了多種代價影響因子，此生成的決策樹模型應(yīng)用范圍要更廣，更符合實際的需求。

3、在決策樹構(gòu)建過程中，避免了分裂屬性信息存在因過小而被忽略的風(fēng)險。