基于蒙特卡洛树搜索的数值目标子群发现算法
Subgroup Discovery Algorithm for Numerical Target Based on Monte Carlo Tree Search
关承彬 1何振峰1
作者信息
- 1. 福州大学计算机与大数据学院,福州 350108
- 折叠
摘要
MonteCloPi算法是一种基于蒙特卡洛树搜索(Monte Carlo tree search,MCTS)的任意时间子群发现算法,旨在使用MCTS策略构建非对称的最佳优先搜索树来发现高质量的多样性模式集,但是限制了目标为二值变量.为此,本文结合了数值目标的特点,通过为置信度上界(upper confidence bound,UCB)公式选取合适的C值、动态调整各个样本的拓展权重并对搜索树进行剪枝、使用自适应top-k均值更新策略,将MonteCloPi算法拓展到了数值目标.最后,在UCI数据集、全国健康与营养调查(national health and nutrition examination survey,NHANES)听力测试数据集上的实验结果表明本文的算法相比其他算法可以发现更高质量的多样性模式集,并且最优子群的可解释性也更好.
Abstract
MonteCloPi is an anytime subgroup discovery algorithm based on Monte Carlo tree search(MCTS).It aims to build an asymmetric best-first search tree to discover a diverse pattern set with high quality by MCTS policies,while it is limited to a binary target.To this end,this study combines the characteristics of the numerical target to extend the MonteCloPi algorithm to the numerical target.The study selects the appropriate C value for the upper confidence bound(UCB)formula,adjusts the expansion weight of each sample dynamically as well as prunes the search tree,and uses the adaptive top-k-mean-update policy.Finally,the experimental results on the UCI datasets and the National Health and Nutrition Examination Survey(NHANES)audiometry datasets show that the proposed algorithm outperforms other algorithms in terms of discovering diverse pattern sets with high quality and the interpretability of the best subgroup.
关键词
蒙特卡洛树搜索/子群发现/数值目标/任意时间算法Key words
Monte Carlo tree search(MCTS)/subgroup discovery/numerical target/anytime algorithm引用本文复制引用
基金项目
福建省自然科学基金(2022J01574)
出版年
2024
NETL
NSTL
万方数据