Algorithms To Discover Locally Trending Patterns In A Discrete Sequence

Two pattern mining tasks,high utility itemset mining and frequent episode mining,have attracted the attention of many researchers.The former aims at finding the high utility itemsets in customer transactions,which are the sets of items that yield a high profit(utility)when purchased together.And frequent episode mining aims at finding subsequences that have a high support(occurrence frequency)in an event sequence.Both of the two patterns can be useful for decision makers.Even with several applications in both high utility itemset mining and frequent episode mining,there are two major limitations in them.First,their criterion to select patterns(constraints on the utility or support of patterns)is evaluated with respect to the whole database.But in real-life,locally interesting patterns can be very important.Second,the support or utility of a pattern may change over time.It is useful to identify trends during a time period,like an increase or decrease in utility or support for a pattern,which is ignored by traditional high utility itemset mining and frequent episode mining.In this thesis,we address these limitations by proposing a new model for discovering locally trending patterns,which show an increasing or decreasing trend during some non-predefined time periods in a discrete sequence.For example,in a supermarket,the utility(e.g.profit)generated by the sale of items and the frequency(e.g.purchase amount)of an episode may have an upward trend before Christmas rather than during the whole year.The model is instantiated in high utility itemset mining and frequent episode mining to define two new tasks,mining locally trending high utility itemsets and mining top-k frequent locally trending episodes.In the designed model,a novel measure is proposed to assess whether there is an increasing or decreasing trend for a pattern in a non-predefined time interval.To detect trends in a database,we divide the time span of the database into non-overlapping consecutive bins first to obtain a sequence of bins.This reduces the influence of small fluctuations.Then,a fixed-length sliding window is moved over the sequence,one bin at a time to look for trending patterns.This study detects trends by calculating the statistical slope of the utility or frequency of the bin sequence in each sliding window with respect to time.The task of mining locally trending high utility itemsets is first studied.It aims at discovering all itemsets that have time intervals where the itemsets have a high utility that follows an increasing or decreasing trend.An algorithm named Locally Trending High Utility Itemset Miner(LTHUI-Miner)is proposed to discover these locally trending high utility itemsets efficiently.Furthermore,the task of mining top-k frequent locally trending episodes is studied,which is to identify all frequent episodes and their non-predefined time intervals where the episodes have some increasing or decreasing trends.At the same time,a third limitation of the frequent episode mining task is also addressed in this thesis,which is that setting the minsup threshold is often difficult for users.We use k to replace the minsup threshold,so that users can set k to indicate the number of patterns they want to find directly.Thereafter,two algorithms called Top-K frequent Episode(TKE)and Top-K frequent locally Trending Episode(TKTE)are designed to discover the k most frequent episodes and top-k frequent locally trending episodes respectively.To reduce search space,pruning strategies and data structures are designed for all the proposed algorithms.Moreover,an experimental evaluation of real datasets shows the efficiency of the alogrithms.Besides,it is also proven that the optimization methods are to improve efficiency.And it is found in the evaluation that LTHUI-Miner and TKTE can discover insightful patterns not found by previous algorithms.