Random Forest Optimization Algorithm Fusion with Approximate Markov Blanket

doi:10.3778/j.issn.1002-8331.2207-0443

Abstract

Abstract: The correlation and redundancy of features will directly affect the quality of randomly extracted features of random forests, leading to the weakened convergence of random forests and reducing the accuracy, generalization ability and performance of random forest models. Based on this, this paper proposes a random forest optimization algorithm incorporating approximate Markov blankets, which uses approximate Markov blankets to construct similar feature groups, then draws features from each similar group proportionally to form a feature subset of a single decision tree, and repeats the above process until it reaches the size of the random forest. The algorithm can improve the quality of randomly extracted features by eliminating the correlation and redundancy among features using approximate Markov blankets while ensuring the diversity of random forest features. The experimental comparison on 12 different dimensional UCI datasets shows that the random forest incorporating approximate Markov blanket can eliminate feature correlation and redundancy to a certain extent, improve various evaluation indexes of the model, enhance generalization ability, and be more suitable for high-dimensional data.

Key words: random forest, approximate Markov blanket, feature selection, high dimensional samples

摘要： 特征的相关和冗余，会直接影响随机森林随机抽取特征的质量，导致随机森林的收敛性减弱，降低随机森林模型的准确度、泛化能力及性能。基于此，提出一种融合近似马尔科夫毯的随机森林优化算法，该算法利用近似马尔科夫毯构建相似特征组，再从每个相似组中按比例抽取特征形成单棵决策树的特征子集，重复上述过程直至达到随机森林规模。该算法可以在保证随机森林特征的多样性前提下，利用近似马尔科夫毯消除特征间的相关性和冗余性，提高随机抽取特征的质量。通过在12组不同维度UCI数据集实验对比表明：融合近似马尔科夫毯的随机森林在一定程度上可以消除特征相关性和冗余性，提高模型的各项评价指标，泛化能力增强，更适用于高维数据。

关键词: 随机森林, 近似马尔科夫毯, 特征选择, 高维样本

LUO Jigen, XIONG Lingzhu, DU Jianqiang, NIE Bin, XIONG Wangping, LI Zhiqin. Random Forest Optimization Algorithm Fusion with Approximate Markov Blanket[J]. Computer Engineering and Applications, 2023, 59(20): 77-84.

罗计根, 熊玲珠, 杜建强, 聂斌, 熊旺平, 李郅琴. 一种融合近似马尔科夫毯的随机森林优化算法[J]. 计算机工程与应用, 2023, 59(20): 77-84.

References

[1] LOUREN?O P，GODINHO S，SOUSA A.Estimating tree aboveground biomass using multispectral satellite-based data in Mediterranean agroforestry system using random forest algorithm[J].Remote Sensing Applications：Society and Environment，2021（23）：100560.
[2] 郑小敏，李翔宇.随机森林手势识别算法的高效嵌入式软件实现[J].计算机工程，2021，47（7）：218-225.
ZHENG X M，LI X Y.Efficient software implementation of random forest gesture recognition algorithm in embedded system[J].Computer Engineering，2021，47（7）：218-225.
[3] 李凌，顾晓梅，刘子豪.多子域随机森林在情境感知推荐中的应用研究[J].计算机工程与应用，2020，56（22）：132-141.
LI L，GU X M，LIU Z H.Application research of multi-subdomain random forest in context-aware recommendation[J].Computer Engineering and Applications，2020，56（22）：132-141.
[4] YAQOOB M，ALI S，BILAL M，et al.ResNet based deep features and random forest classifier for diabetic retinopathy detection[J].Sensors，2021，21（11）：3883.
[5] WU Q Y，YE Y M，LIU Y，et al，SNP selection and classification of genome-wide SNP data using stratified sampling random forests[J].IEEE Transactions on Nanobioscience，2012，11（3）：216-227.
[6] 姚登举.面向医学数据的随机森林特征选择及分类方法研究[D].哈尔滨：哈尔滨工程大学，2016.
YAO D J.Research on feature selection and classification method based on random forest for medical datasets[D].Harbin：Harbin Engineerring University，2016.
[7] 冯盼峰，温永仙.基于随机森林算法的两阶段变量选择研究[J].系统科学与数学，2018，38（1）：119-130.
FENG P F，WEN Y X.Two-stage stepwise variable selection based on random forests[J].Journal of Systems Science and Mathematical Sciences，2018，38（1）：119-130.
[8] AMARATUNGA D，CABRERA J，LEE Y S.Enriched random forests[J].Bioinformatics，2008，24（18）：2010-2014.
[9] SVETNIK V，LIAW A，TONG C，et al.Application of Breiman’s random forest to modeling structure[D].Berlin，Heidelberg：Springer，2004.
[10] GENUER R，POGGI J M，TULEAU-MALOT C.Variable selection using random forests[J].Pattern Recognition Letters，2016，31（14）：2225-2236.
[11] URIARTE D R，DE ANDRéS S A.Gene selection and classification of microarray data using random forest[J].BMC Bioinformatics，2006，7（1）：1-13.
[12] 李郅琴，杜建强，聂斌，等.特征选择方法综述[J].计算机工程与应用，2019，55（24）：10-19.
LI Z Q，DU J Q，NIE B，et al.Summary of feature selection methods[J].Computer Engineering and Applications，2019，55（24）：10-19.
[13] 张俐，王枞，郭文明.利用近似马尔科夫毯的最大相关最小冗余特征选择算法[J].西安交通大学学报，2018，52（10）：141-145.
ZHANG L，WANG C，GUO W M.A feature selection algorithm for maximum relevance minimum redundancy using approximate Markov blanket[J].Journal of Xi’an Jiaotong University，2018，52（10）：141-145.
[14] JOHN G H，KOHAVI R，PFLEGER K.Irrelevant features and the subset selection problem[J].Machine Learning Proceedings，1994：121-129.
[15] KOLLER D，SAHAMI M.Toward optimal feature selection[C]//Proceedings of Int Conf on Machine Learning，Bari，1996：284-292.
[16] YU L，LIU H.Efficient feature selection via analysis of relevance and tedundancy[J].Journal of Machine Learning Research，2004，5（10）：1205-1224.
[17] GUO Z，YU B，HAO M Y，et al.A novel hybrid method for flight departure delay prediction using random forest regression and maximal information coefficient[J].Aerospace Science and Technology，2021，116：1-10.
[18] 李顺勇，王改变，余曼.基于相似性特征聚类的加权无监督特征选择算法[J].贵州师范大学学报（自然科学版），2021，39（1）：49-57.
LI S Y，WANG G B，YU M.Weighted unsupervised feature selection algorithm based on similarity feature clustering[J].Journal of Guizhou Normal University（Natural Sciences），2021，39（1）：49-57.
[19] 罗计根，杜建强，聂斌，等.一种聚类欠采样策略的随机森林优化方法[J].计算机工程与应用，2020，56（22）：166-172.
LUO J G，DU J Q，NIE B，et al.Random forest optimization method based on cluster under-sampling strategy[J].Computer Engineering and Applications，2020，56（22）：166-172.
[20] 徐久成，冯森，穆辉宇.基于信噪比与随机森林的肿瘤特征基因选择[J].河南师范大学学报（自然科学版），2017，45（2）：87-92.
XU J C，FENG S，MU H Y.Tumor feature gene selection based on SNR and random forest[J].Journal of Henan Normal University（Natural Science Edition），2017，45（2）：87-92.
[21] SHAO F，LI K，XU X.Railway accidents analysis based on the improved algorithm of the maximal information coefficient[J].Intelligent Data Analysis，2016，20（3）：597-613.
[22] 马春来，单洪，马涛，等.随机森林改进算法在LBS用户社会关系推断中的应用[J].小型微型计算机系统，2016，37（12）：2708-2712.
MA C L，SHAN H，MA T，et al.An improved random forests algorithm with application to social ties inferring of LBS users[J].Journal of Chinese Computer Systems，2016，37（12）：2708-2712.