Discovering Periodic Itemsets Using Novel Periodicity Measures

INFORMATION AND COMMUNICATION TECHNOLOGIES AND SERVICES VOLUME: 17 |NUMBER: 1 |2019 |MARCH Discovering Periodic Itemsets Using Novel Periodicity Measures Philippe FOURNIER-VIGER1, Peng YANG2, Jerry Chun-Wei LIN3, Quang-Huy DUONG4, Thu-Lan DAM4, Jaroslav FRNDA5, Lukas SEVCIK6, Miroslav VOZNAK6 1School of Humanities and Social Sciences, Harbin Institute of Technology (Shenzhen), University Town of Shenzhen, Shenzhen, China 2School of Computer Science and Technology, Harbin Institute of Technology (Shenzhen), University Town of Shenzhen, Shenzhen, China 3Department of Computing, Mathematics and Physics, Faculty of Engineering and Science, Western Norway University of Applied Sciences (HVL), Inndalsveien 28, 5063 Bergen, Norway 4Department of Computer and Information Science, Faculty of Information Technology and Electrical Engineering, Norwegian University of Science and Technology, Hogskoleringen 1, 7491 Trondheim, Norway 5Department of Quantitative Methods and Economic Informatics, Faculty of Operation and Economics of Transport and Communications, University of Zilina, Univerzitna 8215/1, 010 26 Zilina, Slovak Republic 6Department of Telecommunications, Faculty of Electrical Engineering and Computer Science, VSB–Technical University of Ostrava, 17. listopadu 15, 708 00 Ostrava, Czech Republic [email protected], pengy[email protected], [email protected], h[email protected], [email protected], [email protected], luk[email protected], mirosla[email protected] DOI: 10.15598/aeee.v17i1.3185 Abstract. Discovering periodic patterns in a customer transaction database is the task of identifying itemsets (sets of items or values) that periodically appear in a sequence of transactions. Numerous methods can identify patterns exhibiting a periodic behavior. Nonetheless, a problem of these traditional approaches is that the concept of periodic behavior is defined very strictly. Indeed, a pattern is considered to be periodic if the amount of time or number of transactions between all pairs of its consecutive occurrences is less than a fixed maxPer (maximum periodicity) threshold. As a result, a pattern can be eliminated by a traditional algorithm for mining periodic patterns even if all of its periods but one respect the maxP er constraint. Consequently, many patterns that are almost always periodic are not presented to the user. But these patterns could be considered as interesting as they generally appear periodically. To address this issue, this paper suggests to use three measures to identify periodic patterns. These measures are named average, maximum and minimum periodicity, respectively. They are each designed to evaluate a different aspect of the periodic behavior of patterns. By using them together in a novel algorithm called Periodic Frequent Pattern Miner, more flexibility is given to users to select patterns meeting specific periodic requirements. The designed algorithm has been evaluated on several datasets. Results show that the proposed solution is scalable, efficient, and can identify a small sets of patterns compared to the Eclat algorithm for mining all frequent patterns in a database. Keywords Itemset mining, periodic pattern, periodicity, average periodicity. 1. Introduction Analyzing symbolic data to discover frequently co-occurring symbols is a problem called Frequent Itemset Mining (FIM) [1], [2], [3], [4], [5] and [7]. FIM is considered by many as an important data science task with various applications in different fields [7]. The input of FIM is a database consisting of a set of records described by binary attributes. A typical example of such database is a customer transaction database, where each record is a transaction and each attribute indicates whether a given item was purchased or not in each transaction. To discover frequent itemsets, a user must set a minimum frequency threshold c 2019 ADVANCES IN ELECTRICAL AND ELECTRONIC ENGINEERING 33 INFORMATION AND COMMUNICATION TECHNOLOGIES AND SERVICES VOLUME: 17 |NUMBER: 1 |2019 |MARCH called minsup. Then, a FIM algorithm outputs all sets of items (itemsets) that co-occur in more than minsup transactions. Many studies have proposed efficient techniques to enumerate all frequent itemsets from a binary database, and numerous applications of these techniques have been presented [1], [2], [3], [4], [5] and [7]. Nonetheless, these techniques are inappropriate for identifying patterns that have a periodic behavior. Analyzing the periodic behavior of patterns is desirable for some applications such as the analysis of customer shopping behavior. For instance, one could analyze a transaction database and discover that a person typically purchases some items such as wine and cheese every weekend. Finding such periodic patterns is useful for the purpose of marketing. For example, a mobile application could provide discounts on wine and cheese to that customer before every weekend, anticipating that the customer will repeat that purchase. In a shopping context, periodic patterns for multiple customers could be also discovered. For example, if a retail store identifies that some type of bread is generally sold every hour, this information can be used to improve inventory management of this product. Besides analyzing shopping data, periodic pattern mining can be used in many other applications. To identify recurring patterns in symbolic data, the concept of Periodic Frequent Patterns (PFP) was defined, and many algorithms were designed to enumerate these patterns [8], [9], [10], [11], [12], [13] and [14]. The input of a traditional PFP mining algorithm is a transaction database where transactions are ordered by time, and a parameter called maxper (maximum periodicity) is provided by the user. Then, the output is all periodic patterns, where an itemset is said to be periodic if the number of transactions between any of its consecutive occurrences (the length of its periods) is no greater or equal to maxPer. Mining such patterns was shown to be useful in previous studies. But a drawback of this definition is that it is a very strict definition of what is a periodic pattern. In fact, algorithms for mining these periodic patterns will eliminate a pattern from the result set even if all but one of its periods satisfy the maxPer constraint. Thus, many patterns that are generally periodic but not always periodic will not be presented to the user. However, such patterns still carry some interesting information. One may think that a solution to find such missing patterns is to increase the maxPer threshold. However, this can result in finding a very large number of patterns, and it is typically difficult and time-consuming for users to analyze a large pattern set. To address this issue, a novel problem is defined in this paper, which is to identify periodic patterns using three measures. Those are the average, maximum and minimum periodicity, respectively. They are each designed to each evaluate a different aspect of the periodic behavior of patterns. By using them together in a novel algorithm called PFPM (Periodic Frequent Pattern Miner), more flexibility is given to users to select patterns meeting specific periodic requirements. The contributions of this paper are as follows: •Two measures called minimum and average periodicity are defined to be used jointly with the maximum periodicity measure. These measures let the user more precisely specify requirements about the periodic behavior of patterns to be discovered. Using the average periodicity measure, patterns that are generally but not always periodic can be discovered. •To enumerate all periodic patterns satisfying constraints on the above measures, an efficient algorithm is proposed, called Periodic Frequent Pattern Miner (PFPM) - Note that an early version of this paper was published in a conference proceedings [18]. •The performance in terms of scalability, runtime and memory has been evaluated on four real datasets. It has been observed that the newly designed algorithm is scalable, efficient and can eliminate numerous patterns that are not periodic to show a small set of patterns to the user. The following sections describe relevant related work and some important preliminaries about frequent itemset mining (Sec. 2. ), present the designed minimum periodicity and average periodicity measures (Sec. 3. ), describe the proposed algorithm (Sec. 4. ), report results from the experimental evaluation (Sec. 5. ) and draw a conclusion and discusses opportunities for future work (Sec. 6. ), respectively. 2. Related Work FIM consists of analyzing a binary database (also called transaction database) to identify sets of symbols that appear together in many records. FIM was defined by Agrawal and Srikant [1] as follows. A binary database DB is a set of records (called transactions), described using several binary attributes (items). Let the set of all database attributes (items) be called A. Each record (transaction) Ris defined by the set of attributes R⊆Afor which it has positive values. A transaction database DB containing n records is denoted as DB ={R1, R2, ..., Rn}. The indice cof a record Rcin a database is also called its identifier, and it is unique. It is assumed that records in a database are ordered from the oldest one to the newest one. c 2019 ADVANCES IN ELECTRICAL AND ELECTRONIC ENGINEERING 34 INFORMATION AND COMMUNICATION TECHNOLOGIES AND SERVICES VOLUME: 17 |NUMBER: 1 |2019 |MARCH Tab. 1: A binary database containing seven records. Records Binary attributes a b c d e R1x x R2x R3x x x x x R4x x x x R5x x x R6x x x R7x x x A small binary database is depicted in Tab. 1. It contains seven records having the identifiers 1,2,3,...,7, respectively. Each record is described using five binary attributes denoted as a,b, . . . , e. Consider the first record R1. It indicates that the attributes aand chave positive values. If this database represents a shopping database, it could indicate that some products aand c were bought. The rest of this paper uses the database of Tab. 1 as running example. A pattern (also called itemset) Xis a set of positive attribute values, and is defined as X⊆A. In traditional FIM, interesting patterns are discovered on the basis of their support (occurrence frequency). For a database DB, let s(X)denote the support of Xdefined as s(X) = |{R|R∈DB ∧X⊆R}|. An alternative definition of the support is the following. For an itemset X, let the notation g(X)refer to the set of records containing X, where records are ordered by time. For a database DB containing nrecords, g(X)is formally defined as g(X) = {Rg1, Rg2..., Rgk}, where 1≤g1< g2< ... < gk≤ n. Hence, the support of Xcan be also defined as s(X) = |g(X)|. In FIM, the goal is to enumerate all frequent itemsets, given a minimum support threshold minsup, set by the user [1]. An itemset Xis said to be frequent if and only if s(x)≥minsup. For example, consider the database of Tab. 1 and that a user sets minsup = 4. In that cases, five frequent itemsets are found, which are {a}: 4,{a, c}: 4,{e}: 5,{c, e}: 4,{c}: 6, where the notation X:s(X)is used. Many algorithms have been developed to enumerate all frequent patterns in a database. Some popular algorithms are for example, FP-Growth [15], Apriori [1], LCM [3], and Eclat [4]. These algorithms all produce the same result but utilize different data structure, search strategies and optimizations. The Apriori algorithm utilizes a breadth-first search and repeatedly scan the database, which is very costly, and can generate many candidate patterns. The FP-Growth compresses the database in a compact database structure, and performs database projections to avoid generating candidates. The Eclat algorithm utilizes a vertical database representation to calculate the support of patterns to avoid repeatedly scanning the database. Although these algorithms are efficient, they are designed for finding frequent itemsets rather than identifying itemsets having a periodic behavior. To discover patterns exhibiting periodic behaviors, traditional FIM algorithms have been adapted and extended. Many algorithms were defined to identify Periodic Frequent Patterns (PFPs) in a binary attribute database [8], [9], [10], [11], [12], [13] and [14]. They generally extend FIM algorithms with the ability of calculating periodicity measures, and rely on appropriate data structures and optimizations to perform these calculations efficiently. Periodic frequent pattern mining techniques are useful for various applications [13]. Formally, the concept of PFP is defined as follows, based on a concept of periods [13]. Definition 1 (Consecutive records).Consider an itemset Xappearing in a set of records g(X) = {Rg1, Rg2, . . . , Rgk}of a binary database DB ={R1, R2, . . . , Rn}. Two records Rxand Ryare consecutive w.r.t. Xin DB if there does not exist an identifier wof a record Rwsuch that x<wand w < y. Definition 2 (Period of consecutive records of an itemset).Let there be two consecutive records Rxand Ry in g(X)for an itemset X. The period of Rxand Ry is denoted as pe(Rx, Ry), and defined as the number of records between Rxand Ry, that is pe(Rx, Ry) = y−x. Definition 3 (Periods of an itemset).The periods of an itemset Xappearing in a set of records g(X) = {Rg1, Rg2, . . . , Rgk}is defined formally as ps(X) = {g1−g0, g2−g1, g3−g2,...gk−gk−1, gk+1 −gk}, where g0= 0 and gk+1 =n. For instance, the database records containing {a, c} are R1, R3, R5,and R6in the running example. Hence, the periods of {a, c}are calculated as ps({a, c}) = {1− 0,3−1,5−3,6−5,7−6}={1,2,2,1,1}. Definition 4 (Maximum periodicity).Let there be an itemset X. Its maximum periodicity is defined as maxper(X) = max(ps(X)) [13]. Definition 5 (Periodic Frequent Pattern).Let there be an itemset Xand maxPer be a threshold set by the user. Xis said to be a periodic frequent pattern if maxper(X)< maxPer and s(X)≥minsup [13]. For instance, assume that maxPer = 2 and minsup = 4. A traditional PFP mining algorithm will enumerate all periodic frequent patterns, i.e. (4, 2), {a,c} : (4, 2), {e} : (5, 2), {c} : (6, 2), where the notation X: (s(X), maxper(X)) is used. Many algorithms have been developed to identify PFPs from a transaction database. The first algorithm, named PFP-tree [13], adopts a pattern-growth c 2019 ADVANCES IN ELECTRICAL AND ELECTRONIC ENGINEERING 35 INFORMATION AND COMMUNICATION TECHNOLOGIES AND SERVICES VOLUME: 17 |NUMBER: 1 |2019 |MARCH approach extending FP-Growth [15] to mine PFPs. Then, the MTKPP [8] algorithm was presented to discover the kmost frequent PFPs in a database, where kand maxPer are parameters that must be set by the user. MTKPP is inspired by Eclat [4]. It relies on the same vertical database representation and explores the search space in the same depth-first way. The ITL-tree algorithm [9] was then proposed. It is an approximate algorithm, which uses a tree based approach to find PFPs. Unlike previous algorithms, ITL-tree does an approximate calculation of the periodicities of itemsets. PFP mining is another algorithm for the approximate discovery of PFPs [12]. In another work, the MCPFtree algorithm [10] was proposed by extending PF-Tree to mine PFPs when considering many minsup thresholds. Another extension of the PF-Tree algorithm is MaxCPF [11], which considers multiple minper thresholds. Recently, to find PFPs common to multiple sequences of a sequence database, an algorithm named MPFPS was proposed [14]. But this algorithm is defined for a problem that is quite different from the proposed addressed in this paper as it consider multiple sequences. In summary, many papers have defined a periodic pattern as an itemset having no period greater than some maxPer threshold set by the user. A problem of this definition is that it is very strict. For example, an itemset will be discarded even if it has a single period greater than maxPer. In practice, it would be desirable to discover such patterns that are almost always periodic. 3. Two Novel Measures To provide more flexibility when searching for periodic patterns, this paper proposes to consider two novel periodicity measures, called the average and minimum periodicity, respectively. The following paragraphs present these measures and discuss their properties. Definition 6 (Average periodicity).The average periodicity of an itemset Xis the average of its periods. It is formally defined as: avgper(X) = P p∈ps(X) p |ps(X)|. For instance, for the itemset {a, c}, we have ps({a, c}) = {1,2,2,1,1}and avgper({a, c}) = 1.4. For the itemset {e}, we have ps({e}) = {2,1,1,2,1,0} and avgper({e})=1.16. It is interesting that the average periodicity measure can be calculated using the support measure, and viceversa. Lemma 1 (Correspondence between support and average periodicity).Consider a database DB. The average periodicity avgper(X)of an itemset Xcan be calculated as avgper(X) = |DB|/(s(X) + 1) = |DB|/(|g(X)|+ 1). Proof. The ordered list of records containing Xin DB is g(X) = {Rg1, Rg2, . . . , Rgk}, where g1< g2< . . . < gk. By definition, avgper(X) = P p∈ps(X) p |ps(X)|. Thus, we only need to demonstrate that P p∈ps(X) p |ps(X)|=|DB| |g(X)|+1 to prove the lemma. (1) We first show that P p∈ps(X) p=|DB|, as follows: P p∈ps(X) p= (g1−g0)+(g2−g1) + . . . + (gk+1 −gk) =g0+ (g1−g1)+(g2−g2) + . . . + (gk−gk) + gk+1 =gk+1 −g0=|DB|. (2) To demonstrate that |ps(X)|=|g(X)|+ 1, we proceed as follows: An equivalent definition of ps(X)is ps(X) = S1≤z≤k+1 (gz−gz−1). Hence, k+ 1 elements are in ps(X). Because Xis contained in krecords, sup(X) = k. Thus, it is found that |ps(X)|=|g(X)|+ 1. Because (1) and (2) have been proven, the lemma holds. Lemma 1 explains the relationship between the average periodicity and support of each itemset. From a practical perspective, this lemma is very useful as it allows to efficiently compute avgper(X)for any itemset Xof a database DB. The reason why this calculation is efficient is that the number of database records |DB|is known and can be precalculated once. Then, to calculate avgper(X), only |g(X)|+ 1 remains to be computed, and then divided by the number of database records. Doing this calculation is easier than computing avgper using Def. 6, as this later requires to sum all periods of Xand then divide by the number of periods. The average periodicity can be viewed as an interesting measure because it allows finding patterns that are on average periodic. However, this measure can be easily influenced by outliers. This is illustrated with an example. The periods of itemset {c, d, e}are ps({R3, R4}) = {3,1,4}because {c, d, e}appears in records R3and R4. Hence, avgper({R3, R4})=2.33. But it can be argued that this pattern should not be viewed as periodic since there are very large differences between its periods. To address this drawback of the average periodicity, this paper proposes to combine this measure with the maximum periodicity measure and a novel minimum periodicity measure. Using this combination ensures that the average periodicity of an itemset is not influenced by outliers. Definition 7 (Minimum periodicity).Let there be an itemset X. Its minimum periodicity is defined as minper(X) = min(ps(X)) (where the first and last periods of ps(X)are ignored). In the case where ps(X) = ∅,minper(X)is defined as ∞. c 2019 ADVANCES IN ELECTRICAL AND ELECTRONIC ENGINEERING 36 INFORMATION AND COMMUNICATION TECHNOLOGIES AND SERVICES VOLUME: 17 |NUMBER: 1 |2019 |MARCH Setting a constraint on the minimum periodicity of itemsets can be useful to eliminate itemsets that have very short periods. But if we simply defines the minimum periodicity as minper(X) = min(ps(X)), some problems occur because the first and last periods of an itemset are special cases that can greatly influence the overall minimum periodicity. For instance, consider the itemset {e}. Because {e}is contained in the last record, the last period of {e}is 0, as well as its minimum periodicity. To avoid such situations, the first and last periods are excluded from the calculation of the minimum periodicity. A second problem is that if these periods are excluded, the set of periods of an itemset may then become empty. To handle this case, the minimum periodicity is then defined as ∞. By combining the minimum, maximum and average periodicity measures to find periodic patterns, it is possible to finely evaluate the periodic behavior of patterns. Another interesting aspect of these measures is that they are easy to calculate if the set of records g(X)is known for an itemset X. This is especially useful for extending the Eclat frequent itemset mining to find periodic patterns, because Eclat already calculates g(X)for each itemset Xencountered during search space exploration. Besides, another reason why calculating these measures is efficient is that it is not necessary to calculate and store ps(X)in memory to calculate these measures. In fact, all measures can be calculated while scanning g(X)once. Based on the above discussion and novel measures, this paper defines a novel problem of mining periodic frequent itemsets with novel measures as follows. Definition 8 (Problem definition).Let there be four user-specified thresholds minAvg ≥0,maxAvg ≥0, minPer ≥0, and maxPer ≥0. An itemset Xis a periodic frequent itemset if and only if three conditions are met: (1) minper(X)≥minPer, (2) maxper(X)≤ maxPer, and (3) minAvg ≤avgper(X)≤maxAvg. For instance, consider the database of the running example and that the thresholds are set to minPer = minAvg = 1,maxP er = 3 and maxAvg = 2. Table 2 shows the eleven PFPs. To efficiently enumerate all periodic frequent itemsets from a binary database, it is necessary to avoid considering the whole search space of itemsets. For this purpose, the following paragraphs presents strategies that can be used to reduce the search space using the periodicity measures considered in this paper. Lemma 2 (Monotonicity of the average periodicity). For a database DB and any itemsets X⊂Y, the relationship avgper(Y)≥avgper(X)holds. Proof. By the definition of the average periodicity measure, we have avgper(X) = |DB| |g(X)|+1 and avgper(Y) = |DB| |g(Y)|+1 . Since Xis a subset of Y, it is clear that g(Y)⊆g(X)and thus that avgper(Y)≥ avgper(X). Lemma 3 (Monotonicity of the minimum periodicity).For a database DB and any itemsets X⊂Y, the relationship minper(Y)≥minper(X)holds. Proof. Because Yis a superset of X, it follows that g(Y)⊆g(X). Two cases are considered. In the first case (g(Y)⊂g(X)). Then, for each record Rx∈g(X)\g(Y), the corresponding periods in ps(X) will be replaced by a larger period in ps(Y). Hence, each period of ps(Y)must be greater than the corresponding period(s) in ps(X). Hence, minper(Y)≥ minper(X). In the second case, if g(Y) = g(X), then ps(X) = ps(Y)and hence minper(Y) = minper(X). Lemma 4 (Monotonicity of the maximum periodicity).For a database DB and any itemsets X⊂Y, the relationship maxper(Y)≥maxper(X)holds [13]. Based on the above lemmas, two search space pruning theorems are defined. The first one was used in previous work [13], while the second one is novel. Theorem 1 (Search space pruning using the maximum periodicity).Consider a database DB and an itemset X. If it is found that maxper(X)> maxP er, then all supersets of Xare not periodic frequent itemsets and can be ignored during further exploration of the search space [13]. Theorem 2 (Search space pruning using the average periodicity).Consider a database DB and an itemset X. If it is found that avgper(X)> maxAvg, then all supersets of Xare not periodic frequent itemsets and can be ignored during further exploration of the search space [13]. Note that the condition |g(X)|<|D| maxAvg −1 can be equivalently used for pruning. Proof. Because avgper(X)> maxAvg, the itemset Xis not a periodic frequent itemset. Moreover, by Lem. 2, it is known that avgper(Y)≥avgper(X) for any superset Yof X. The pruning condition avgper(X)> maxAvg is rewritten as: |DB| |g(X)|+1 > maxAvg. Thus, 1 |g(X)|+1 >maxAvg |DB|, which can be further rewritten as |g(X)|+ 1 <|DB| maxAvg , and as |g(X)|<|DB| maxAvg −1. 4. The PFPM Algorithm The previous section has defined the problem of mining periodic itemsets using novel measures. This section defines an efficient algorithm named Periodic Frequent c 2019 ADVANCES IN ELECTRICAL AND ELECTRONIC ENGINEERING 37 INFORMATION AND COMMUNICATION TECHNOLOGIES AND SERVICES VOLUME: 17 |NUMBER: 1 |2019 |MARCH Tab. 2: The periodic frequent itemsets for minP er =minAvg = 1,maxP er = 3 and maxAvg = 2. Itemset support s(X) minper(X) maxper(X) avgper(X) {b}3 1 3 1.75 {b, e}3 1 3 1.75 {b, c, e}3 1 3 1.75 {b, c}3 1 3 1.75 {d}3 1 3 1.75 {c, d}3 1 3 1.75 {a}4 1 2 1.4 {a, c}4 1 2 1.4 {e}5 1 2 1.17 {c, e}4 1 3 1.4 {c}6 1 2 1.0 Pattern Miner (PFPM), which extends the Eclat [4] algorithm to efficiently enumerate periodic patterns using the novel measures. As the Eclat algorithm, PFPM utilizes a structure called tid-list to annonate each potential periodic itemset Xwith the list of records g(X) where it appears. This structure is suitable for the proposed problem as it allows to quickly obtain |g(X)|to calculate the periodicity measures of each itemset X. Moreover, the minper(X)and maxper(X)values are used to annotate each itemset X. The pseudocode of the proposed PFPM algorithm is presented in Alg. 1. PFPM explores the search space of itemsets in a recursivey way by extending each itemset one item at a time. PFPM processes items following an order on items, defined as the ascending order of support values. In the following, the extensions of an itemset Xare the itemsets that can be obtained by appending an item yto Xsuch that ya,∀a∈X. The input of PFPM is four thresholds (minPer,maxP er minAvg,maxAvg) and a binary database DB, while the output is the set of all periodic itemsets. PFPM initially reads the database to compute for each item a∈A,s({a}),minper({a})and maxper({a}). Thereafter, a constant called γis calculated. This latter is used for reducing the search space based on Thm. 2. PHPM then selects items having a support no less than γand having periods no greater than maxPer. These items, called A∗, are the only items that can appear in periodic frequent itemsets according to the search space pruning Thm. 1 and Thm. 2. This set is sorted according to the order, as suggested in [4]. Thereafter, PFPM reads the database again to construct the tid-list of each item in A∗. Finally, the Search procedure is called with A∗,γ,minAvg,minPer,maxPer, and |DB|to recursively explore the search space in a depth-first way. Algorithm 2 provides the pseudo-code of the Search procedure. An itemset Pis taken as input, as well as a set of extensions of Pof the form Pz where zis an item. When the Search procedure is called for the first time, Pis the empty set and the set of extensions contains single items. Search also takes as parameters γ, Algorithm 1: Periodic Frequent Pattern Miner input : minPer,maxPer,minAvg,maxAvg, a binary database DB output: the set of periodic itemsets 1Read the database once to compute for each item a∈A:s({a}),minper({a})and maxper({a}); 2Calculate γ= (|DB|/maxAvg)−1; 3A∗← {a|a∈A∧s({a})≥γ∧maxper({a})≤ maxPer}; 4Create the tid-list of each item a∈A∗by reading the database DB; 5Search (A∗,γ, minAvg,minPer,maxPer, |DB|); and the minAvg,minPer,maxPer, and |DB|tresholds. The procedure then performs a loop to consider each extension Px of Pfrom the set received as parameter. The procedure first calculates avgper(Px)as |DB|divided by the number of elements in the tid-list of Px plus one (according to Lem. 1). Then, if the conditions (1) minAvg ≤avgper(Px)≤maxAvg, (2) minper(Px)≤minP er and (3) and maxper(P x)≤ maxPer are satisfied according to the tid-list of P x, Px is output as a periodic frequent itemset. Thereafter, if the third condition is satisfied and the tid-list of Px contains at least γrecords, the algorithm will consider extensions of Px. Otherwise, those extensions are ignored according to Thm. 1 and Thm. 2. Exploring larger extensions is done by combining two itemsets Px and Py where yxto get an itemset P xy. After obtaining an itemset Pxy, the BuildT IDList procedure (Alg. 3) is called to construct the tid-list of Pxy. This procedure takes as input the tid-lists of Px and Py and returns the tid-list of Pxy. The BuildTIDList procedure is almost identical to the tid-list join operation of Eclat. But a key difference is that periods of P xy, maxPer(P xy)and minPer(Pxy)are calculated during list construction (not shown). Finally, the Search procedure is recursively called with Pxy to explore its extension(s). Because the PFPM algorithm starts from single items and recursively explores the search space c 2019 ADVANCES IN ELECTRICAL AND ELECTRONIC ENGINEERING 38 INFORMATION AND COMMUNICATION TECHNOLOGIES AND SERVICES VOLUME: 17 |NUMBER: 1 |2019 |MARCH of patterns by appending items and only prunes the search space using Thm. 1 and Thm. 2, it can be seen that this procedure is correct and complete to discover all PFPs. Algorithm 2: Search input : ExtensionsOfP: a set of extensions of an itemset P,γ,minAvg,minPer, maxPer,|DB| output: the set of periodic frequent itemsets 1foreach itemset Px ∈ExtensionsOfP do 2avgperPx ← |DB|/(|P x.tidlist|+ 1); 3if minAvg ≤avgperPx ≤maxAvg ∧ Px.tidlist.minp ≥minPer ∧ Px.tidlist.maxp ≤maxPer then output Px; 4if avgperPx ≥γ∧Px.tidlist.maxp ≤maxP er then 5ExtensionsOfPx ← ∅; 6foreach itemset Py ∈ExtensionsOfP such that yxdo 7Pxy ←P x ∪Py; 8Pxy.tidlist ←BuildTIDList (Px, P y); 9ExtensionsOfPx ← ExtensionsOfPx ∪ {Pxy}; 10 end 11 Search (ExtensionsOfPx,γ,minAvg, minPer,maxP er,|DB|); 12 end 13 end To illustrate how the algorithm works, an example is given. Consider the database of Tab. 3 and that minAvg = 1, and maxAvg = 2,minPer = 1, and maxPer = 3. PFPM (Alg. 1) first processes single items. Consider the item {a}. By scanning the database, PFPM finds that s({a})=4,minper({a}) = 1and maxper({a})=2. PFPM calculates that γ= (|DB|/maxAvg)−1 = (7/2)−1=2.5. Since s({a})≥ γand maxper({a})is less than the maximum periodicity threshold, the item {a}will be considered during further processing (each item that does not meet the requirements is pruned). Then, the same process is repeated for the other items and a set of PFP candidates is found. Iitems are then sorted by ascending support values ({b},{d},{a},{e},{c}). The tid-lists of these candidates are built (e.g. {b}’s tid-list [T3,T4,T7] is built), and the Search procedure is called to find all PFPs (Alg. 2). The search procedure performs a loop on each extension Px of P. Consider P x ={b}. By using {b}’s tid-list, PFPM finds that avgper({b}) = 7 3+1 = 1.75,maxper({b})=3and minper({b})=1. As minAvg ≤avgper({b})≤maxAvg,minper({b})≥ minPer and maxper({b})≤maxP er, item {b} is Algorithm 3: The BuildTIDList procedure input : two extensions Px and P x of an itemset P output: the tid-list of Pxy 1TidListOfPxy ← ∅; 2foreach Tid v∈Px.tidlist such that v∈Py.tidlist do 3periodv← calculateP eriod(v, TidListOfPxy); 4Update(TidListOfP xy, periodv); 5TidListOfP xy ←TidListOfPxy ∪ {v}; 6end 7return TidListOfPxy; 1 234 5 6 7 8910 11 12 13 14 15 16 Fig. 1: The search space of the example. a PFP and it is output. The extensions of {b}are: {b, d},{b, a},{b, e}and {b, c}, which will be explored because s({b})≥γand maxper({b})≤maxPer. The tid-list of {d}is [T3,T4,T5], thus the tid-list of {b, d} is [T3,T4], obtained by joining the tid-list of {b}and {d}. Thereafter, the Search procedure is recursivelly invoked with these extensions to find larger PFPs. The search space of the algorithm is shown in Fig. 1. In that figure, itemsets that do not meet one of the constraint are colored in red and their extensions (descendant nodes) are not explored. The complete set of PFPs that is found is shown in Tab. 2. The above paragraphs have described the main idea of the PFPM algorithm. The next paragraphs presents two optimizations to enhance PFPM’s performance. Optimization 1. Estimated Average Periodicity Pruning (EAPP). During the second database scan, a structure named ESCS (Estimated Support Cooccurrence Structure) is built, which stores the support s({a, b}) = cof each pair of item aand bas a triple of the form (a, b, c). From a practical perspective, the ESCS can be implemented using vairous structure such as a hashmap of hashmaps or a triangular matrix (as shown in Fig. 2). An advantage of using a hash map is that each tuple (a, b, c)where c6= 0 may be ommitted to reduce memory usage. The EAPP optimizations consists of modifying Line 7 of the search procedure to prune an itemset Pxy if s({x, y})is less than γ(based on Thm. 2). c 2019 ADVANCES IN ELECTRICAL AND ELECTRONIC ENGINEERING 39 INFORMATION AND COMMUNICATION TECHNOLOGIES AND SERVICES VOLUME: 17 |NUMBER: 1 |2019 |MARCH TID Transactions Item a b c d e f g T1 (a,1)(c,1)(d,1) Profit 5 2 1 2 3 1 1 T2 (a,2)(c,6)(e,2)(g,5) T3 (a,1)(b,2)(c,1)(d,6),(e,1),(f,5) T4 (b,4)(c,3)(d,3)(e,1) T5 (b,2)(c,2)(e,1)(g,2) TU(T_1) = 7 TU(T_2) = 27 TU(T_3) = 30 TU(T_4) = 20 TU(T_5) = 11 TWU(a) = 65 TWU(b)= 61 TWU(c)= 96 TWU(d)=58 TWU(e)=88 TWU(f)= 30 TWU(g) = 38 TID TU Item TWU Item a b c d e f T1 8 a 65 b 30 T2 27 b 61 c 65 61 T3 30 c 96 d 38 50 58 T4 20 d 58 e 57 61 77 50 T5 11 e 88 f 30 30 30 30 30 f 30 g 27 38 38 0 38 0 g 38 support Item a b c d b 1 c 4 3 d 2 2 3 e 2 3 4 2 TW U Item a b c d b 25 c 61 54 d 33 45 53 e 47 54 76 45 Fig. 2: The Estimated Support Co-occurrence Structure. Optimization 2. Abandoning List Construction early (ALC). The ALC optimization stops the construction of an itemset’s tid-list if current calculations of its periodicity measures show that it cannot be a periodic frequent itemset. According to Thm. 2, an itemset Pxy cannot be a periodic frequent itemset if less than γ= (|DB|/maxAvg)−1records contains Pxy. The ALC strategy is obtained by first changing Line 1 of Alg. 3 to initialize a variable max as γin Line 1. Modifications are also made in the loop of Line 2. For each tuple not appearing in Py, the variable max is decremented by 1. If max becomes less than γ, ALC stops the construction of Pxy’s tid list. This can be done without compromising the algorithm’s completeness because |g(Pxy)|will not be higher than γ, and hence Pxy is not a PFP by Thm. 2, and its extensions can also be ignored. 5. Experimental Study This section presents an experimental study to assess the performance of the designed PFPM algorithm in terms of runtime, memory consumption, number of patterns found and scalability, when parameters are varied. The experimental environment is a Windows 10 computer equipped with 12 GB of RAM and a 6th gen 64 bit Core i5 processor. The designed algorithm is programmed in Java. In the experiments, the performance of PFPM is compared with that of the Eclat algorithm because it is one of the most efficient algorithm for FIM and PFPM extends the Eclat algorithm. Thus, a comparison with Eclat allows to see the cost or benefits of using PFPM to find only the periodic patterns rather than finding all frequent itemsets. Performance of the algorithms was evaluated on four datasets often used for comparing itemset mining algorithms, having varied characteristics (short or long transactions, or dense or sparse data). chainstore,retail, and foodmart are customer transaction databases. mushroom is a dataset about mushrooms. Characteristics of the four datasets are presented in Tab. 3, where |DB|,|A|and Adenote the number of records, distinct items and average record length. The experiment consisted of running the PFPM algorithm on each dataset with fixed minPer and minAvg values, while varying the maxAvg and maxPer parameters. To be able to compare PFPM with Eclat, Eclat was run with the γvalue calculated by PPFM. Execution times, memory consumption, and number of patterns found were measured for each algorithm. All memory measurements were done using the Java API. For each dataset, values for the periodicity thresholds have been found empirically for each dataset (as they are dataset specific), and were chosen to show the trade-off between the number of periodic patterns found and the execution time. Note that results for varying the minP er and minAvg values are not shown because these parameters have less influence on the number of patterns found than the other parameters. Thereafter, the notation PFPM V-W-X represents the PFPM algorithm with minPer =V,maxP er =W, and minAvg =X. Figure 3 compares the execution times of PFPM for various parameter values and Eclat. Figure 4, compares the number of PFPs found by PFPM for various parameter values, and the number of frequent itemsets found by Eclat. It can first be observed that mining PFPs using PFPM is generally much faster than mining frequent itemsets. On the retail dataset, PFPM is up to four times faster than Eclat. On the mushroom and chainstore datasets, no results are shown for Eclat because it cannot terminate whithin 1,000 seconds or ran out of memory, while PFPM terminates in less than 10 seconds. The reason is that the search space is huge for these datasets when the minimum support is set to γ. The PFPM algorithm still terminates on these datasets because it only searches for periodic patterns, and thus prunes a large part of the search space containing non periodic patterns. On the foodmart dataset, PFPM can be up to five times faster than Eclat depending on the parameters. But it can also be slightly slower in some cases. The reason is that foodmart is a sparse dataset and thus the gain in terms of pruning the search space does not always offset the cost of calculating the periodicity measures. In general, the more the periodicity thresholds are restrictive, the more the gap between the runtime of Eclat and PFPM increases. A second observation is that the number of PFPs can be much less than the number of frequent itemsets (see Fig. 4). For example, on retail, 19,836 frequent itemsets are found for maxAvg = 2,000. But only 110 frequent itemsets are PFPs for PFPM 1-1000-5, and only 7 for PFPM 1-250-5. Some of the patterns found are quite interesting as they contain several items. For example, it is found that items with product ids 32, 48 and 39 are periodically bought with an average periodicity of 16.32, a minimum periodicity of 1, and a maximum periodicity of 170. A similar reduction in terms of number of patterns is also observed on the three other datasets. This demonstrates that the PFPM algorithm is effective at filtering non periodic patterns, and that a huge amount of non periodic patterns are found in real-life datasets. c 2019 ADVANCES IN ELECTRICAL AND ELECTRONIC ENGINEERING 40 INFORMATION AND COMMUNICATION TECHNOLOGIES AND SERVICES VOLUME: 17 |NUMBER: 1 |2019 |MARCH Tab. 3: Dataset characteristics. Dataset |DB| |A|AType retail 88,162 16,470 10.30 sparse, many items mushroom 8,124 119 23.0 dense, long records chainstore 1,112,949 46,086 7.26 sparse, many records foodmart 4,141 1,559 4.4 sparse, short records 0 500 1000 1500 2000 0 500 1000 1500 2000 Runtime (ms) maxAvgPer Retail Eclat PFPM 1-1000-5 PFPM 1-500-5 PFPM 1-250-5 1 2 3 4 5 6 7 0 500 1000 1500 2000 Runtime (s) maxAvgPer Mushroom Eclat PFPM 1-1000-5 PFPM 1-500-5 PFPM 1-250-5 2000 2100 2200 2300 2400 2500 2600 - 500 1,000 1,500 2,000 Runtime (ms) maxAvgPer Chaintstore Eclat PFPM 1-2000-5 PFPM 1-1500-5 PFPM 1-1000-5 0 200 400 600 800 1,000 0 500 1000 1500 2000 Runtime (ms) maxAvgPer Foodmart Eclat PFPM 1-2000-5 PFPM 1-1000-5 PFPM 1-500-5 Fig. 3: Execution times. k k k 1k 10k 100k 0 500 1000 1500 2000 Pattern count maxAvgPer Retail Eclat PFPM 1-1000-5 PFPM 1-500-5 PFPM 1-250-5 1 21 41 61 81 101 121 141 161 181 0 500 1000 1500 2000 Pattern count maxAvgPer Mushroom Eclat PFPM 1-1000-5 PFPM 1-500-5 PFPM 1-250-5 0 5 10 15 20 25 0 500 1000 1500 2000 Pattern count maxAvgPer Chaintstore Eclat PFPM 1-2000-5 PFPM 1-1500-5 PFPM 1-1000-5 k 1k 2k 3k 4k 5k 0 500 1000 1500 2000 Pattern count maxAvgPer Foodmart Eclat PFPM 1-2000-5 PFPM 1-1000-5 PFPM 1-500-5 Fig. 4: Number of patterns found. c 2019 ADVANCES IN ELECTRICAL AND ELECTRONIC ENGINEERING 41