[發(fā)明專利]多標(biāo)準(zhǔn)誤分類代價(jià)敏感決策樹構(gòu)建方法

在審

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

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

本發(fā)明涉及人工智能、數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)領(lǐng)域，具體涉及一種多標(biāo)準(zhǔn)誤分類代價(jià)敏感決策樹構(gòu)建方法。

背景技術(shù)

在歸納學(xué)習(xí)技術(shù)中如何盡量減少誤分類錯(cuò)誤是主要焦點(diǎn)，例如CART和C4.5。在歸納問題上誤分類不僅是一個(gè)錯(cuò)誤，即錯(cuò)誤分類所帶來的代價(jià)不容忽略。在代價(jià)敏感學(xué)習(xí)CLS算法中，誤分類代價(jià)為同一單位標(biāo)準(zhǔn)，但在現(xiàn)實(shí)世界的應(yīng)用程序誤分類代價(jià)通常有不同的單位。把不同單位標(biāo)準(zhǔn)的誤分類代價(jià)量化成一個(gè)唯一單位代價(jià)是非常困難的。分裂屬性選擇是決策樹構(gòu)建的一個(gè)關(guān)鍵又基本過程，最流行的屬性選擇方法側(cè)重于測(cè)量屬性的信息增益。當(dāng)錯(cuò)誤分類所引起的代價(jià)不容忽視時(shí)，很自然地把降低代價(jià)機(jī)制和屬性信息結(jié)合起來作為分裂屬性選擇標(biāo)準(zhǔn)，這樣構(gòu)成的決策樹既提高了分類精度，同時(shí)誤分類代價(jià)達(dá)到最優(yōu)，我們的目的就是得到最低的誤分類代價(jià)。這樣形成的決策樹更適合在醫(yī)療診斷過程中?；谶@種需求，本發(fā)明提出多標(biāo)準(zhǔn)誤分類代價(jià)敏感決策樹構(gòu)建方法。

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

本發(fā)明所要解決技術(shù)問題是決策過程中誤分類代價(jià)和屬性信息之間的平衡性問題、誤分類代價(jià)不同單位機(jī)制問題以及構(gòu)成的決策樹過度擬合問題，提供一種多標(biāo)準(zhǔn)誤分類代價(jià)敏感決策樹構(gòu)建方法。

為解決上述問題，本發(fā)明的是通過以下技術(shù)方案實(shí)現(xiàn)的：

多標(biāo)準(zhǔn)誤分類代價(jià)敏感決策樹構(gòu)建方法，包括如下步驟：

步驟1.設(shè)訓(xùn)練集中有X個(gè)樣本，屬性個(gè)數(shù)為n，即n＝(s₁，s₂，…s_n),同時(shí)分裂屬性s_r對(duì)應(yīng)了m個(gè)類L，其中L_i∈(L₁，L₂…，L_m),r∈(1，2…，n)，i∈(1，2…，m)。設(shè)誤分類代價(jià)矩陣為C，C由用戶指定。

步驟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é)點(diǎn)G。

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

步驟6：根據(jù)代價(jià)敏感的候選屬性選擇因子ASF候選屬性中選擇splitS。

候選屬性選擇因子ASF：

averagegain(S)為選擇屬性S的平均信息增益，reduce_mc(S)為選擇屬性S作為分裂屬性時(shí)的誤分類代價(jià)減少率。

當(dāng)選擇屬性splitS滿足目標(biāo)函數(shù)ASF(S)最小時(shí)，則找到標(biāo)記節(jié)點(diǎn)G。如果一些屬性具有相同的ASF值，為了打破平局的標(biāo)準(zhǔn)，再按照更大的reduce_mc(S)值來優(yōu)先選擇候選屬性。這樣構(gòu)建的決策樹優(yōu)先遵從誤分類代價(jià)最低的原則。

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

步驟8：由根據(jù)基尼指數(shù)gini(S_i)值延伸出滿足條件為splitS＝splitS_i分支。

8.1這里假設(shè)Y_i為訓(xùn)練數(shù)據(jù)集中splitS＝splitS_i的樣本集合。滿足以下兩條件之一，則終止建樹。

(1)如果Y_i為空，加上一個(gè)葉子節(jié)點(diǎn)，標(biāo)記為訓(xùn)練數(shù)據(jù)集中最普通的類。

(2)在一節(jié)點(diǎn)中所有例子屬于相同類。

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

步驟10：為避免決策樹中存在過渡擬合問題，利用后剪支技術(shù)對(duì)決策樹進(jìn)行剪支操作。

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

1，對(duì)屬性信息增益進(jìn)行優(yōu)化處理，避免因?qū)傩孕畔⒃鲆孢^小而忽略了屬性信息的風(fēng)險(xiǎn)。

2，把不同單位標(biāo)準(zhǔn)的誤分類代價(jià)量化為同一單位標(biāo)準(zhǔn)，降低了誤分類代價(jià)單位異質(zhì)性對(duì)分裂屬性選擇的影響。

3，考慮了誤分類代價(jià)和屬性信息之間的平衡性，在決策過程中，使得誤分類代價(jià)達(dá)到最小，同時(shí)提高了決策樹分類精度。

4，構(gòu)建多標(biāo)準(zhǔn)誤分類代價(jià)敏感決策樹有效地避免了過度擬合的問題。

附圖說明

附圖為多標(biāo)準(zhǔn)誤分類代價(jià)敏感決策樹結(jié)構(gòu)流程圖

具體實(shí)施方式

1、上述步驟1中誤分類代價(jià)矩陣C的設(shè)定過程如下：

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