关键词: 高效用项集挖掘, 马尔可夫网络, 位图矩阵, 吉布斯采样, 精英策略

Abstract:

To address the problems that the High Utility Itemset Mining （HUIM） algorithms based on tree and link table structures often consume search spaces of orders of magnitude， and the evolutionary type-based mining algorithms fail to fully consider the interactions between variables， an HUIM algorithm based on Markov Optimization （HUIM-MOA） was proposed. Firstly， a bitmap matrix for expressing database and expectation vector encoding were used to achieve fast scanning of the database and efficient computation of utility values， respectively. Then， the Markov Network （MN） structure was estimated by computing the mutual information among dominant individuals and new populations were generated by using Gibbs sampling according to their local characteristics. Finally， population diversity preservation strategy and elite strategy were used to prevent the algorithm from falling into local optimum too quickly and to reduce the missing of high utility itemsets， respectively. Experimental results on real datasets show that compared with Bio-inspired High Utility Itemset Framework based on Particle Swarm Optimization （Bio-HUIF-PSO） algorithm， HUIM-MOA can find all the High Utility Itemsets （HUIs） when given a larger minimum threshold， with on average 12.5% improvement in convergence speed， 2.85 percentage point improvement in mined HUI number， and 14.6% reduction in running time. It can be seen that HUIM-MOA has stronger search performance than the evolutionary HUIM algorithm， which can effectively reduce the search time and improve the search quality.

Key words: High Utility Itemset Mining (HUIM), Markov network, bitmap matrix, Gibbs sampling, elite strategy