[發(fā)明專利]基于平均測(cè)試代價(jià)的一維尺度決策樹構(gòu)造算法

在審

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

1.基于平均測(cè)試代價(jià)的一維尺度決策樹構(gòu)造算法，該算法涉及涉及智能服務(wù)、機(jī)器學(xué)習(xí)領(lǐng)域，其特征是：該算法的具體實(shí)施方案如下：通過原訓(xùn)練示例利用EP準(zhǔn)則得到新背景訓(xùn)練集，在每項(xiàng)測(cè)試成本、經(jīng)濟(jì)因子和完整闊值已知的情況下，綜合考慮和的值依次選擇屬性結(jié)點(diǎn)，再利用分裂抽象屬性的完整因子與給定作比較，來得到相應(yīng)的分支，在決策樹生成過程中，如遇到在一個(gè)子集或分支結(jié)點(diǎn)中的所有樣例都屬于相同類別或是在一個(gè)子集或分支結(jié)點(diǎn)中沒有待分裂的候選抽象屬性，即基于平均測(cè)試代價(jià)的一維尺度決策樹模型生成。

2.根據(jù)權(quán)利要求1所述的基于平均測(cè)試代價(jià)的一維尺度決策樹構(gòu)造算法，其特征是:該算法的具體實(shí)施步驟如下：

步驟1：定義L為類的種類，其中數(shù)為n,L_i表示第i類,上述:根據(jù)EP結(jié)點(diǎn)類的分類準(zhǔn)則得到新背景訓(xùn)練樣本集ISA

步驟2：專家根據(jù)實(shí)際情況，給出每項(xiàng)屬性進(jìn)行的測(cè)試成本；

步驟3：用戶自定義參數(shù)經(jīng)濟(jì)因子w和完整闊值ct,它們的范圍都是[0,1]；

步驟4：根據(jù)信息增益與ICF(信息成本函數(shù)）遍歷輸入的新背景訓(xùn)練樣本集的候選屬性列表，計(jì)算每個(gè)候選屬性，得出當(dāng)前選擇屬性；

步驟4.1 ：遍歷所有ISA新背景訓(xùn)練樣本集的屬性，計(jì)算每個(gè)屬性的ICF,并選擇ICF值最小的屬性作為平均測(cè)試代價(jià)的一維尺度決策樹的根結(jié)點(diǎn)；

步驟5：依據(jù)ISA層次結(jié)構(gòu)歸納準(zhǔn)則和抽象值的完整因子c與完整因子闊值的大小ct比較結(jié)果，作為基于測(cè)試代價(jià)的一維尺度決策樹的擴(kuò)展結(jié)點(diǎn)；

步驟6：根據(jù)最優(yōu)分裂屬性選擇因子ct候選的抽象屬性得到相應(yīng)的每一個(gè)屬性和觀測(cè)值，在結(jié)點(diǎn)下生成相應(yīng)的分支；每個(gè)分支的樣本集合為所有觀測(cè)值等于對(duì)應(yīng)分支的新背景訓(xùn)練屬性樣本，這樣的屬性集合個(gè)數(shù)為I；

步驟7：依次為每個(gè)抽象分裂屬性的每個(gè)屬性值產(chǎn)生一個(gè)分支類，得到相應(yīng)于該分支屬性值的子集，對(duì)各子集遞歸調(diào)用本算法，即重回步驟4.1，用同樣的方法將樣本子集分割，產(chǎn)生分支的分支，同時(shí)獲得相應(yīng)子集的子集，直到滿足以下兩條件之一則終止建樹過程，即：

條件1：在一個(gè)子集或分支結(jié)點(diǎn)中所有樣例屬性都為同一抽象屬性類別，又稱之為觀測(cè)值；

條件2：在一個(gè)子集或分支結(jié)點(diǎn)中分裂屬性為抽象屬性的集合為空。

3.根據(jù)權(quán)利要求2所述的基于平均測(cè)試代價(jià)的一維尺度決策樹構(gòu)造算法，其特征是: 所述步驟1中對(duì)于多類標(biāo)號(hào)的原數(shù)據(jù)集都可以轉(zhuǎn)化為兩類情況，基于結(jié)點(diǎn)的歸納準(zhǔn)則得出層次結(jié)構(gòu)為：

其中ISA為新的背景樣本抽象屬性，記為,為正例個(gè)數(shù)，為反例個(gè)數(shù)，抽象屬性，如性別中男女；根據(jù)類的種類分類規(guī)則得到新的訓(xùn)練樣本集，即為ISA背景訓(xùn)練樣本集；新背景訓(xùn)練樣本集葉子結(jié)點(diǎn)發(fā)生了變化。

4.根據(jù)權(quán)利要求2所述的基于平均測(cè)試代價(jià)的一維尺度決策樹構(gòu)造算法，其特征是: 所述步驟4中，候選屬性的屬性選擇因子為：

其中為總的數(shù)據(jù)信息，為不可取數(shù)據(jù)信息；

這里為屬性i信息增量，w為檢驗(yàn)經(jīng)濟(jì)標(biāo)準(zhǔn)一個(gè)變量,cost_i為屬性i的測(cè)試成本，cost_i+1>1,當(dāng)cost=0時(shí)，f(cost)有意義：ICF是信息成本函數(shù)，用來表征每一屬性的選擇。