[發(fā)明專(zhuān)利]一種改進(jìn)的多維尺度異構(gòu)代價(jià)敏感決策樹(shù)構(gòu)建方法

在審

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

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

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

背景技術(shù)

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

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

對(duì)于解決同時(shí)考慮測(cè)試代價(jià)、誤分類(lèi)代價(jià)以及等待時(shí)間代價(jià)影響因子來(lái)構(gòu)建多維尺度決策樹(shù)過(guò)程的問(wèn)題，以及為使測(cè)試成本更低、所構(gòu)成的決策樹(shù)擴(kuò)展性更好、代價(jià)不同單位機(jī)制的問(wèn)題，提出了一種改進(jìn)的多維尺度異構(gòu)代價(jià)敏感決策樹(shù)構(gòu)建方法。

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

一種改進(jìn)的多維尺度異構(gòu)代價(jià)敏感決策樹(shù)構(gòu)建方法，包括如下步驟：

步驟1：設(shè)訓(xùn)練集中有X個(gè)樣本，屬性個(gè)數(shù)為n，即n＝(S₁，S₂，…S_n)，同時(shí)分裂屬性S_i對(duì)應(yīng)了m個(gè)類(lèi)L，其中L_r∈(L₁，L₂…，L_m)，i∈(1，2…，n)，r∈(1，2…，m)。相關(guān)領(lǐng)域用戶設(shè)定好誤分類(lèi)代價(jià)矩陣C、屬性S_i、測(cè)試代價(jià)cost_i、相對(duì)等待時(shí)間代價(jià)wc(S_i)、修正系數(shù)β，以及判定條件閾值p、q。

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

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

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

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

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

目標(biāo)函數(shù)f(S_i)：f(S_i)＝averagegain(S_i)·D(S_i)

averagegain(S_i)為平均信息增益函數(shù)，D(S_i)為各種代價(jià)效度函數(shù)。當(dāng)選擇屬性splitS_i滿足目標(biāo)函數(shù)f(S_i)越大，則找到標(biāo)記節(jié)點(diǎn)G。

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

(1)更大的Dmc(S_i)

(2)更小的ZTC(S_i)

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

步驟8：由節(jié)點(diǎn)延伸出滿足條件為splitS＝splitS_i分支，這里假設(shè)滿足條件的分支個(gè)數(shù)為k，此時(shí)在此節(jié)點(diǎn)再加一個(gè)空節(jié)點(diǎn)，即當(dāng)前節(jié)點(diǎn)的分支個(gè)數(shù)為k+1，同時(shí)利用先剪枝技術(shù)對(duì)節(jié)點(diǎn)進(jìn)行剪枝操作，一邊建樹(shù)一邊剪枝，如果滿足以下兩條件之一，就停止建樹(shù)。

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

8.2 此結(jié)點(diǎn)中所有例子屬于同一類(lèi)。

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

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

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

1、構(gòu)建的決策樹(shù)有更好的分類(lèi)準(zhǔn)確度，加強(qiáng)了分類(lèi)能力，避免了將稀有類(lèi)作為普通類(lèi)分類(lèi)的情況。