MonteCloPi算法是一种基于蒙特卡洛树搜索(Monte Carlo tree search,MCTS)的任意时间子群发现算法,旨在使用MCTS策略构建非对称的最佳优先搜索树来发现高质量的多样性模式集,但是限制了目标为二值变量.为此,本文结合了数值目标的特点,通过为置信度上界(upper confidence bound,UCB)公式选取合适的C值、动态调整各个样本的拓展权重并对搜索树进行剪枝、使用自适应top-k均值更新策略,将MonteCloPi算法拓展到了数值目标.最后,在UCI数据集、全国健康与营养调查(national health and nutrition examination survey,NHANES)听力测试数据集上的实验结果表明本文的算法相比其他算法可以发现更高质量的多样性模式集,并且最优子群的可解释性也更好.
Subgroup Discovery Algorithm for Numerical Target Based on Monte Carlo Tree Search
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.
Monte Carlo tree search(MCTS)subgroup discoverynumerical targetanytime algorithm
NETL
NSTL
万方数据
