[發明專利]基于平均測試代價的一維尺度決策樹構造算法

在審

• 申請號: 201610284638.1
• 申請日: 2016-04-29
• 公開（公告）號: CN106611179A
• 公開（公告）日: 2017-05-03
• 發明（設計）人: 金平艷;胡成華
• 申請（專利權）人: 四川用聯信息技術有限公司
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 暫無信息
• 代理人: 暫無信息

所屬領域

本發明涉及智能服務、機器學習領域。

背景技術

決策樹決策方法是機器學習領域中經典算法，得到了廣泛應用。早期分類中，一般認為準確率是對分類效果很重要的衡量標準之一。以ID3算法為代表，它主要是在分裂屬性選擇方法和優化剪支策略兩方面的研究。在實際的許多分類問題中，算法ID3存在各種條件的限制。其中最主要一點是缺乏背景知識，從而限制學習過程。如一位腦腫瘤專家在判定一個患頭疼的病人時，第一次并不進行最有效果的昂貴掃描，此時專家有經濟標準。在這種簡單常見的病癥下，一開始是簡單問題測試或是一些其它更為經濟的測試。背景學習方法在進行數據分類的過程中應遵循測試成本最小化歸納規則，以適應更多實際數據分類問題，基于這種需求，本發明提出了基于平均測試代價的一維尺度決策樹構造方法。

發明內容

本發明所要解決的技術問題是決策過程中所產生經濟成本的影響，提出了一種基于測試代價的一維決策樹構造算法。

本發明所采用的技術方案是：通過原訓練示例利用EP準則得到新背景訓練集ISA，在每項測試成本、經濟因子和完整闊值已知的情況下，綜合考慮ΔI和ICF的值依次選擇屬性結點，再利用分裂抽象屬性的完整因子c與給定ct作比較，來得到相應的分支，在決策樹生成過程中，如遇到在一個子集或分支結點中的所有樣例都屬于相同類別或是在一個子集或分支結點中沒有待分裂的候選抽象屬性，即基于平均測試代價的一維尺度決策樹模型生成。

本發明的有益效果是：采用本決策樹構造算法實現了在數據分類過程中，所花費的平均測試成本低。

附圖說明

圖1表示基于平均測試代價的一維尺度決策樹構造示意圖

圖2表示ISA層次決策樹結構的生成示意圖

圖3表示屬性A進行結點分裂示意圖

具體實施方式

以下結合附圖1到3，對本發明進行詳細說明。

本算法所涉及的參數定義及說明如下。

一.ISA新背景訓練樣本集

設原訓練樣本集X中有n種類別標識L₁，L₂，…L_n，根據類(葉子結點)的分類對選擇屬性進行新的歸納得到新的訓練樣本集，即為ISA；新的屬性這里稱為抽象屬性抽象P、N。

二.測試代價

ISA新背景訓練樣本集中進行每一項屬性測試需要的費用，記為cos t，cos t_i為第i屬性測試成本，測試代價由相關專家給出。

三.經濟因子w和完整闊值ct

經濟因子w為用來校準成本花費的一個變量，其范圍為w∈[0,1]，當w＝1為最大成本花費；完整闊值ct由相關領域專家給出，其取值范圍為ct∈[0,1]。

四.信噪比函數z()

根據信息論，信噪比這一函數功能在數據分析方面得到了廣泛的應用，有下式：

有UI+NI＝TI(總信息)

得出z()＝[UI/NI]＝[TI/NI]-1

五.信息增益函數ΔT

根據上面的信噪比z()函數和ID₃決策樹算法原理，有：

ΔT＝R(TI)-R(NI)＝[2^R(TI)/2^R(NI)]

由于TI＝2^R(TI),NI＝2^R(NI)

所以

2^ΔT＝[TI/NI],2^ΔT＝[UI/NI+1]＝z()+1

所以上式信噪比函數又可寫為z()＝2^ΔT-1

六.分裂抽象屬性選擇因子c

假如Y為新背景訓練樣本集(ISA)，A為新訓練樣本集的選擇屬性之一，新訓練樣本抽象屬性的葉子結點i的種類個數為m，我們把此葉子結點稱為觀測值，其中i∈[1,2…,m]。ISA抽象屬性值j的個數為n，即原訓練樣本的葉子結點數，其中j∈[1,2…,n]。

其中,當抽象屬性第j個葉子結點中包含第i類觀測值時，h(i,j)＝1；相反如果抽象屬性第j個葉子結點中不包含第i類觀測值，即h(i,j)＝0。

當時，我們選擇這個抽象屬性進行分裂。

七、本發明的具體步驟如下：

步驟1：定義L為類的種類，其個數為n，L_i表示第i類，上述i∈(1,2,3…n)；根據EP結點類的分類準則得到新背景訓練樣本集ISA。