Research On Frequent-High Utility Itemset Mining Based On Multi-Objective Evolutionary Computation

As an important area in data mining,frequent and high utility itemsets(FHUIs)mining can discover the itemsets that are frequent occurring and have high utilities.Compared with frequent itemsets mining and high utility itemsets mining,the frequent and high utility itemsets mining(FHUIM)can satisfy the need of users more properly,and is emerging for its advantage in many applications.However,the traditional algorithm may meet the difficulties of parameter setting and exponential search space.Recently,researchers have reformulated the problem of FHUIM as a multi-objective optimization problem.Then to solve the multi-objective FHUIM problem,several multi-objective evolutionary algorithms(MOEAs)have been proposed,by which the support and utility of itemsets are regarded as two different objectives and optimized simultaneously.The difficulties of huge search space and parameter setting that the traditional FHUIM algorithms encounter can be overcome by using the MOEAs.Besides,the MOEAs for mining FHUIs can obtain multiple itemsets with high support and utility value in one run within an acceptable time.Many advantages have been brought from the MOEAs in solving the task of FHUIM.However,when the number of transactions in the dataset and the number of total distinct items in the dataset are larger,the existing MOEAs for mining frequent and high utility itemsets may be inefficient for the larger search space.To the end,this paper focus on improving the efficiency of MOEAs for FHUIM,and studies more useful method for FHUIM.(1)A lot of inferior solutions are generated in existing MOEAs for FHUIM for the absence of efficient search space reducing method.To improve the efficiency of MOEAs for FHUIM,an bi-objective evolutionary algorithm for mining FHUIs named BOEA-FHUI is proposed.To reduce the search space efficiently,a pruning strategy based on the anti-monotone property of support and the downward closure property of transaction weighted utilization is proposed in BOEA-FHUI.Then based on the pruning result,an offspring repair strategy is proposed to make the offspring can jump out of the dominated area of the previous non-dominated solutions.In order to increase the proportion of high quality items in the population,an improved mutation strategy is proposed based on the sparse nature of the FHUIs in BOEA-FHUI.Then the speed of convergence is improved by using the proposed mutation strategy.The experimental result shows that,the proposed BOEA-FHUI outperforms state-of-the-art MOEAs in the task of FHUIM in terms of the convergance speed and quality of the final solutions.(2)In order to further enhance the efficiency of MOEAs for mining FHUIs,an improved bi-objective evolutionary algorithm for mining FHUIs named IBOEA-FHUI is proposed in this study.To make the initial population have a better distribution,an initialization strategy is proposed in IBOEA-FHUI,which takes the support,utility and diversity of initial population in to account.The population with high support,utility and diversity can be generated by using the proposed initialization strategy.For the purpose of generating better offspring in IBOEA-FHUI,a method for estimating the support and utility of itemsets is proposed.Then based on the estimate support and utility value,an offspring generation strategy is proposed.The estimate support and utility value of the itemset which are roughly proportional to their true values can be calculated with little computation resource by using the proposed estimate method.The proposed offspring generation strategy can compare the candidate offspring and select the individuals with higher estimated support and utility as the final offspring,by which the quality of the offspring can be better.The experimental result reveals that,compared with the state-of-the-art MOEAs for mining FHUIs including the proposed BOEA-FHUI in this study,the proposed IBOEA-FHUI has a better performance in terms of the convergance speed.To improve the efficiency of MOEAs for mining FHUIs,two MOEAs are proposed in this paper,which have designed a search space reduce strategy,an improved mutation strategy,a better population initial strategy and a novel offspring generation strategy to enhance the search ability for FHUIs and achieve better results compared with the state-of-the-art MOEAs.