[發明專利]一種基于約束條件的隨機森林推薦算法

在審

• 申請號: 201611071464.7
• 申請日: 2016-11-29
• 公開（公告）號: CN106778836A
• 公開（公告）日: 2017-05-31
• 發明（設計）人: 喻梅;安永利;于健;高潔;徐天一;馬雄
• 申請（專利權）人: 天津大學
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 天津市北洋有限責任專利代理事務所12201
• 代理人: 李素蘭

1.一種基于約束條件的隨機森林推薦算法，其特征在于，該方法包括以下步驟：

步驟(101)、根據給定初始訓練集中的數據集、在CART算法中利用基尼指數構造二叉決策樹，基尼系數定義如公式(1)所示：

${\mathrm{Gini}}_R\left(S\right)=\frac{\left|s_1\right|}{\left|s\right|}Gini\left(S_1\right)+\frac{\left|s_2\right|}{\left|s\right|}Gini\left(S_2\right)---\left(1\right)$

其中，Gini_R(S)是集合S以特征R分裂產生的基尼系數，S₁和S₂分別是用樣本特征R分裂后得到的子集，定義基尼增益如公式(2)所示：

Gini(R)＝Gini(S)-Gini_R(S) (2)

步驟(201)、從初始訓練集抽取訓練子樣本，每個子樣本特征維度為M，每次樹進行分裂時指定一個常數m<<M作為子樣本特征個數，從m個子樣本特征中選擇最優的子樣本特征去分裂；每棵樹都最大程度的生長，組合成隨機森林；

步驟(301)、分類指的是根據樣本記錄所具有的特征將樣本映射到預先定義好的類標號。通過從精確率、召回率和F值分析訓練模型所用的時間，衡量算法時間效能，其中：

精確率定義如公式(3)所示：

$\mathrm{Pr}ecision=\frac{TP}{TP+FP}---\left(3\right)$

其中，TP表示把正類預測為正類的案例個數，FP表示把負類預測為正類的案例個數；

召回率定義如公式(4)所示：

$\mathrm{Re}call=\frac{TP+TN}{TP+FN}---\left(4\right)$

其中，FN表示把正類預測為負類的案例個數；

F值定義如公式(5)所示：

$F-Score=\frac{2\mathrm{Pr}ecision*\mathrm{Re}call}{\mathrm{Pr}ecision+\mathrm{Re}call}---\left(5\right)$

其中，Precision為精確率，Recall為召回率；

步驟(401)、以同樣的初始訓練集中的數據集，分別構造擁有10棵和100棵決策樹的隨機森林，利用該模型對測試集進行分類，即將各個記錄映射到預先定義的類標號，在訓練集占比例不同情況下研究算法性能，記錄模型訓練時間；

步驟(501)、將隨機森林算法進行改進，具體步驟如下：

假設有S₁,S₂,…S_n,n個樣本作為隨機森林n棵樹的訓練樣本，用S_i樣本建立決策樹模型，O_i為袋外數據，將O_i作為測試集進行預測，計算袋外數據誤差EO_i；對于特征F_j，將O_i中F_j的值進行噪聲化，形成新測試集new_O_i；用新測試集new_O_i進行預測，記錄新的袋外數據誤差new_EO_i，重要特征F_j重要度importance_j如公式(6)所示

${\mathrm{importance}}_j=\frac{1}{n}{\mathrm{\&Sigma;}}_{i=1}^{n}new\_{\mathrm{EO}}_i-{\mathrm{EO}}_i---\left(6\right)$

按重要性降序排列，確定刪除比例，從當前的特征中剔除相應比例排在最后的不重要特征，每次選出一個重要特征F_j，以新特征作構造隨機森林，遞歸重復上述步驟，直到剩余m個特征；依據通過上述方法所得到的各個新的重要特征構成重要特征集合和袋外數據，計算分類精確度，選取最優的作為最終特征集。