[發(fā)明專利]基于代價(jià)敏感二維尺度決策樹構(gòu)造方法

在審

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

1.基于代價(jià)敏感二維尺度決策樹構(gòu)造方法，該方法涉及人工智能、機(jī)器學(xué)習(xí)技術(shù)領(lǐng)域，其特征是：該方法應(yīng)用測(cè)試代價(jià)與誤分類代價(jià)之和最小值進(jìn)行屬性選擇，依次構(gòu)造決策樹，為了解決得出的決策樹存在過渡擬合問題，提出了后剪支方案，使得得出的決策樹在預(yù)測(cè)未知對(duì)象時(shí)更加準(zhǔn)確，本方法的具體實(shí)施步驟如下：

步驟1.設(shè)訓(xùn)練集中有個(gè)樣本，屬性個(gè)數(shù)為n，即,同時(shí)分裂屬性對(duì)應(yīng)了m個(gè)類L，其中,，相關(guān)領(lǐng)域用戶設(shè)定好誤分類代價(jià)矩陣C、測(cè)試成本 、經(jīng)濟(jì)因子w;

步驟1.1：設(shè)立誤分類代價(jià)矩陣

類別標(biāo)識(shí)個(gè)數(shù)為m，則該數(shù)據(jù)的代價(jià)矩陣方陣是：

其中表示第j類數(shù)據(jù)分為第i類的代價(jià)，如果為正確分類，則,否則為錯(cuò)誤分類，其值由相關(guān)領(lǐng)域用戶給定,這里 ;

步驟2：創(chuàng)建根節(jié)點(diǎn)G；

步驟3：如果訓(xùn)練數(shù)據(jù)集為空，則返回結(jié)點(diǎn)G并標(biāo)記失敗；

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

G；

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

步驟6：根據(jù)總代價(jià)成本目標(biāo)函數(shù)從候選屬性中選擇屬性；

總代價(jià)目標(biāo)函數(shù)為：,其中為選擇屬性S時(shí)，為測(cè)試代價(jià)指標(biāo)函數(shù), 為把選擇屬性預(yù)測(cè)為第類所引起的誤分類代價(jià)指標(biāo)函數(shù)；

當(dāng)選擇屬性滿足總代價(jià)成本目標(biāo)函數(shù)最小時(shí)，則找到標(biāo)記結(jié)點(diǎn)G；

步驟7：標(biāo)記結(jié)點(diǎn)G為屬性；

步驟8：由結(jié)點(diǎn)延伸出滿足條件為分枝；

步驟8.1：假設(shè)為訓(xùn)練數(shù)據(jù)集中的樣本集合，如果為空，加上一個(gè)葉子結(jié)點(diǎn)，標(biāo)記為訓(xùn)練數(shù)據(jù)集中最普通的類；

步驟9：非步驟8.1的情況，則遞歸調(diào)用步驟6至步驟8；

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

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

2.根據(jù)權(quán)利要求1所述的基于代價(jià)敏感二維尺度決策樹構(gòu)造方法，其特征是：所述步驟6根據(jù)總代價(jià)成本目標(biāo)函數(shù)從候選屬性中選擇屬性，需要求解總代價(jià)成本目標(biāo)函數(shù)，在求解此函數(shù)時(shí)會(huì)用到測(cè)試代價(jià)指標(biāo)函數(shù)，以及誤分類代價(jià)指標(biāo)函數(shù)，在求解時(shí)會(huì)用到信息增益函數(shù)，具體的求解過程如下：

步驟6.1：求解測(cè)試代價(jià)指標(biāo)函數(shù)

步驟6.1.1：求解信息增益函數(shù)

屬性S為測(cè)試屬性，這些子集對(duì)應(yīng)于包含集合P結(jié)點(diǎn)生長(zhǎng)出來的分支，設(shè)是子集中類的樣本數(shù)，則S劃分子集的期望信息為：

為第j個(gè)子集的權(quán)，期望值越小，子集劃分純度越高，對(duì)于給定子集：，其中，，是中樣本屬于的概率；

最后得到信息增益公式為：

步驟6.1.2：求解測(cè)試代價(jià)指標(biāo)函數(shù)

根據(jù)上述信息增益可得：

為相關(guān)領(lǐng)域用戶給定的一個(gè)經(jīng)濟(jì)因子， ； 為屬性S的測(cè)試成本，這由用戶指定，, 當(dāng)時(shí)， 是有意義的， 是標(biāo)準(zhǔn)測(cè)試代價(jià)指數(shù)，其值越小越好，用來表征每一屬性通過測(cè)試代價(jià)指標(biāo)進(jìn)行選擇；

步驟6.2：求解誤分類代價(jià)指標(biāo)函數(shù)

根據(jù)步驟1.1誤分類代價(jià)矩陣，對(duì)于任一樣例S,如果將其分為第i類，那么

可能此時(shí)屬性S的誤分類為i的代價(jià)是：

其中為將S分為第i類的預(yù)測(cè)總代價(jià)， 為在屬性S中第j類的概率， 為把j類錯(cuò)分為第i類的代價(jià)花費(fèi)；

步驟6.3：求解總代價(jià)目標(biāo)函數(shù)TOTAL，根據(jù)步驟6.1.2、步驟6.2的兩個(gè)公式，可得出：

。

3.根據(jù)權(quán)利要求1所述的基于代價(jià)敏感二維尺度決策樹構(gòu)造方法，其特征是：所述步驟10方法采用后剪支技術(shù)的原理為：如果取消當(dāng)前測(cè)試屬性可以減少?zèng)Q策樹模型的測(cè)試代價(jià)，那么就剪除當(dāng)前測(cè)試結(jié)點(diǎn)，如代價(jià)復(fù)雜性剪枝和最少描述長(zhǎng)度剪枝，代價(jià)復(fù)雜性剪枝在剪枝過程中因子樹被葉節(jié)點(diǎn)替代而增加的錯(cuò)誤分類樣本總數(shù)稱為代價(jià)，剪枝后子樹減少的葉節(jié)點(diǎn)數(shù)稱為復(fù)雜性，最少描述長(zhǎng)度剪枝根據(jù)決策樹的編碼代價(jià)大小進(jìn)行剪枝，目標(biāo)是使得訓(xùn)練樣本的大多數(shù)數(shù)據(jù)符合這棵樹，把樣本中不符合的數(shù)據(jù)作為例外編碼，使得編碼決策樹所需的比特最小和編碼例外實(shí)例所需的比特最小：

后剪支目標(biāo)函數(shù)為：

其中正數(shù)為用戶指定達(dá)到的條件，剪枝的條件首先要滿足盡可能使代價(jià)減損達(dá)到用戶指定條件，然后滿足測(cè)試代價(jià)降低到用戶要求。