Research Of Task-Oriented Pattern Mining Based On Multi-objective Evolutionary Algorithms

Multi-objective optimization problem frequently occurs in scientific research and engineering applications.There are some conflicting relations among the objectives in the multi-objective problems,which is different from the classical single objective optimization problem.At present,there are a lot of algorithms to solve this problem.Evolutionary algorithms exhibit good performance in solving multi-objective optimization problems due to their good parallelism,global search,and the availability of any function classes.Therefore,the multi-objective evolutionary algorithm has become one of mainstream methods in multi-objective optimization,and has attracted wide attention of scholars.As a branch of frequent pattern mining,task-oriented pattern mining has attracted more and more attention due to its wide application scenarios,such as goods match recommendation,print area recommendation and so on.In these task-oriented applications,the items in each recommended pattern work as a whole for a task,thus these patterns are called task-oriented patterns.Because of the high correlation between each sub-task in the pattern,it is necessary to guarantee the completeness of the patterns,thus to prevent user's undesirable experience.The traditional task-oriented pattern mining algorithm performs a depth-first search on the set-enumeration tree of the transaction database,and utilizes the pruning method to improve the running efficiency in the searching process.However,the method of traversing all the set-enumeration tree is difficult to carry out in practical applications,because the algorithm needs to set the parameters according to the prior knowledge of the specific problem,and different parameters have great influence on the algorithm's result.In addition,the efficiency of the algorithm is also unsatisfactory.Based on the above problems,this thesis conducts a thorough study on the task-oriented pattern mining algorithm,and proposes a multi-objective optimization approach to solve the problem.The work of this thesis is divided into two parts as follows:(1)This thesis proposes an evolutionary approach for pattern mining from a multi-objective perspective.In the task-oriented applications,the traditional algorithms require the users to set the prior parameters such as the minimum support threshold min_sup,the minimum occupancy threshold min_occ,and the relative importance preference ? between support and occupancy.However,it is very difficult for users to set optimal values for these parameters especially when they do not have any prior knowledge in real applications.In order to find the appropriate parameters,the user needs to conduct several experiments to find the best parameter,which makes the algorithm more expensive and inefficient.To overcome this challenge,this thesis transforms the task-oriented mining problem into a 3-objectives(Support,Occupancy and Area)multi-objective optimization problem.And a multi-objective evolutionary algorithm,termed MOPM,is also proposed to solve the transformed multi-objective optimization problem for task-oriented pattern mining.Experimental results on two real task-oriented applications,namely,goods match recommendation in Taobao and print area recommendation in Smart Print,and several large synthetic datasets demonstrate the promising performance of the proposed method in terms of both effectiveness and efficiency.(2)This thesis also proposes a surrogate-assisted multi-objective evolutionary algorithms.It can be found from the first study that solving the problem of task-oriented pattern mining with multi-objective optimization can solve the challenge of traditional algorithms and bring great convenience,which greatly promotes the application in practice.However,the efficiency of MOPM will be gradually reduced with the increasing of the transaction database.This is because the evolutionary algorithm needs to traverse every item in the transaction database when calculating the three object values(Support,Occupancy and Area)of the individual,so it is time consuming.To overcome this challenge,a surrogate-assisted multi-objective evolutionary algorithms is proposed to improve the efficiency of algorithm,termed SA-MOPM.SA-MOPM uses an improved K-Prototype clustering algorithm based on radial basis function network model as the surrogate model,which can be applied to discrete task-oriented problem.Finally,the effectiveness of the SA-MOPM algorithm is verified by experiments on several datasets.The results show that the SA-MOPM algorithm has higher efficiency than the MOPM algorithm in tolerable range of accuracy reduction.