[發明專利]基于測試代價的決策樹分類器構造方法

在審

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

1.基于測試代價的決策樹分類器構造方法，該方法涉及智能服務、機器學習技術領域，其特征是：本發明從庫中數據流中提取最匹配的訓練示例樣本為標識示例，對新示例進行類預測，若在分類過程中為相同的類，或測試屬性為空時，則標識示例類符合此新示例，之后遵循測試成本代價最小原則構建決策樹，測試代價f作為選擇屬性標準，c作為分裂屬性標準，若在葉子結點出現未知類，同時測試成本也更優化，則更新庫，保存新示例，更優化的決策樹分類器就構成了，其具體的實施步驟如下：

步驟1：根據保存示例與新示例之間的特征差值來標識和鑒定訓練示例樣本：

其中為已有新示例第屬性值，表示它們之間相關性，取值范圍為，當沒有數值屬性時，即為0，否則就為1；當兩比較特征有至少一個值未知，就標記為0.5，當越大，則標識了更多示例，當=0時，則找到了最佳匹配訓練示例；

步驟2：專家根據實際情況，給出每項屬性進行的測試成本：

在訓練樣本集S中進行每一項屬性測試需要的費用，記為，為第X屬性測試成本，測試代價由相關專家給出；

步驟3：用戶自定義參數經濟因子,它范圍為 ，經濟因子為用來校準成本花費的一個變量，當為最大成本花費；完整閾值由相關領域專家給出，其取值范圍為 ；

步驟4：根據遍歷輸入的訓練樣本集候選屬性列表，計算每個候選屬性，得出當前選擇屬性；

步驟4.1： 遍歷所有訓練樣本集的屬性，計算每個屬性的,選擇值最大的屬性作為測試代價決策樹分類器的根結點；

候選屬性的選擇因子為：

其中為訓練示例集中屬性為X的信息增益，為屬性X的信息成本函數；

步驟5：對應于步驟4得出的最大候選屬性每一個屬性值，在結點下生成相應分支（即分裂抽象屬性）；每個分支樣本集合為所有屬性值對應分支的訓練樣本，這樣訓練樣本集為個子集，也為屬性值個數；

步驟6：將每個子集作為新的訓練樣本集，對各子集遞歸調用本算法，即重回步驟4，用同樣的方法將樣本子集分割，產生分支的分支，同時獲得相應子集的子集，直到滿足以下兩條件之一則終止建樹過程，即：

條件1：在一個子集或分支結點中所有樣例屬性都為同一類別，又稱之為觀測值；

條件2：在一個子集或分支結點中所有樣本為空；

步驟7：在葉子結點分類時出現未知類同時又有廉價的測試功能，則更新庫保存新的示例。

2.根據權利要求1所述的基于測試代價的決策樹分類器構造方法，其特征是：所述步驟4.1計算候選屬性的選擇因子，需要求出信息增益函數、信息成本函數、以及在求解過程中會用到信噪比函數，具體計算過程如下：

1>、信息成本函數

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

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

所以上式信噪比函數又可寫為 ；

2）根據信噪比函數和函數可得知：

這里為屬性信息增量，為檢驗經濟標準一個變量，的范圍為，為屬性的測試成本， ，當時， 有意義；是信息成本函數，用來表征每一屬性的選擇；

2>、信息增益函數

這里為屬性，為屬性的第i個屬性值，為類集合， 當屬性X的值為時,類為的概率，直到訓練樣本集有相同類或是屬性為空時，這個分類過程結束。

3.根據權利要求1所述的基于測試代價的決策樹分類器構造方法，其特征是：

所述步驟5分裂屬性的選擇方法為：

定義分裂抽象屬性選擇因子為c，未知示例樣本屬性的葉子結點的種類個數為，我們把此葉子結點稱為觀測值，其中，已保存訓練樣本葉子結點數為j，其中 ：

其中,當已保存示例樣本集中第個葉子結點中包含第類觀測值時， ；相反如果已保存示例樣本集第個葉子結點中不包含第類觀測值，即：

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

當 時，更新庫，保存新示例對象。