Mining recent high average utility patterns based on sliding window from stream data

Abstract

Utility pattern mining is a technique that finds valuable patterns from large-sized databases with each item’s importance and quantity information associated with it. The representative utility pattern mining technique, high utility pattern mining (HUPM), calculates the utilities of patterns by summating all of the item utilities in the patterns. However, such utility measures for patterns in HUPM have a drawback in whichpatterns with long lengths tend to have utilities sufficient to become high utility patterns. For these reasons, high average utility pattern mining (HAUPM) employing different utility measures has been studied in order to consider such pattern length factors. Recently, techniques for handling stream data are necessary because many data sources, e.g. sensors and POS devices, produce data in real time. However, all the existing HAUPM algorithms are unable to find up-to-date, meaningful patterns over data streams. We thus propose the first sliding window based HAUPM algorithm discovering recent high average utility patterns over data streams. Based on the sliding window model, our algorithm divides stream data into numerous batches, and keeps only recent batches in its window. Thereby, the algorithm can mine recent, important patterns over data streams. We also introduce a new strategy that enhances the performance of our algorithm by minimizing the overestimated average utilities stored in the proposed data structure. The experimental results show that our algorithm outperforms the competitors.

Keywords

Association rule mining utility pattern mining stream pattern mining sliding window model

1 Introduction

In a variety of business areas, data mining has been utilized in order to discover and analyze valuable information hidden in large-sized databases. Association rule mining [1 , 15–17] is one of the data mining approaches that finds sets of items, i.e. patterns, with relevant relationships between items. From the beginning of association rule mining, frequent pattern mining (FPM) [11 , 32] that finds frequently occurring patterns from a given database has played an important role in many data mining applications. However, FPM cannot sufficiently consider all the characteristics of the real world because it has several limitations: First, the transactional databases used in FPM represent information of items in a binary form, which is either presence or absence. However, in the real world, items can occur multiple times in one transaction. Second, the importance of items can be different from each other. Therefore, if corporations want to know which set of products creates the highest revenue in their databases through data mining applications, the quantity and profit information of each item should be considered in mining processes.

In order to overcome such limitations of FDM, utility pattern mining that considers utility information of each itemhas been widely studied in recent years. In particular, high utility pattern mining (HUPM) [19 , 31] has been researched actively in order to find patterns with utilities no less than a user-specified minimum utility. In HUPM, the utility of a pattern is defined as the summation of item utilities in the pattern. Accordingly, as the length of a pattern becomes longer, the utility of the pattern is more likely to become higher regardless of individual item utilities in the pattern. In this regard, the mining results of HUPM algorithms may include a large amount of patterns composed of numerous items with low utilities. Such patterns can be redundant information in certain business areas. This is with the assumption that we have mined two different patterns from a market database, which have equal total prices (pattern utilities) and consist of few expansive home appliances (high utility items) and many cheap daily supplies (low utility items), respectively. In the view of marketing strategies, a pattern with a small number of purchased items can be more useful information to easily maximize the revenue of a corporation compared to a pattern with a large number of items. Therefore, high average utility pattern mining (HAUPM) algorithms [13, 23] have been devised in order to find high average utility patterns (HAUPs) by considering the length factors of patterns. HAUPM defines the utility of a pattern as the summation of item utilities divided by its pattern length, which is called average utility. Through such consideration of patterns’ lengths, patterns with a large number of low utility items are less likely to be mined by HAUPM algorithms.

Influenced by developments of various real time systems in recent years, data mining in stream environments has emerged as an important issue. Therefore, researches on data mining methods for dealing with stream data have been conducted in many data mining sub-fields such as classification [8], time series data mining [22], and association rule mining. In particular, discovering only up-to-date information by focusing recent stream data can be useful in certain areas. In this regard, since the previous HAUPM algorithms are not suitable for mining recent, interesting patterns from data stream, we devise a novel HAUPM algorithm that can find only recent HAUPs from stream data. On the basis of the sliding window model, the proposed algorithm divides stream data into numerous batches according to their generation time, and considers only the recent batches in its mining process.

The major contributions of this paper can be summarized as follows.

In this paper, we introduce the new HAUPM algorithm, named SHAU (Sliding window based High Average Utility pattern mining), adopting the sliding window model in order to consider only recent stream data in its pattern mining process. In addition, we use a tree-based data structure, called SHAU-Tree (Sliding window based High Average Utility pattern Tree), that each node has an additional data structure, named batch-list, for storing average utility information of recent stream data batch by batch.

In order to decrease the number of generated candidates, we propose a new strategy named RUG (Reducing average utility Upper bound in the Global SHAU-Tree), which minimizes the values of overestimated average utilities stored in the global SHAU-Tree during the accumulation of stream data.

By investigating the experimental results of various experiments performed on real datasets, we show that SHAU has better performance compared to other algorithms in stream environments.

The rest of this paper is organized as follows. Related studies are introduced in section 2. The details of the proposed data structure and the mining process of the proposed algorithm are described in section 3. The performance evaluation of the proposed algorithm is provided in section 4. Finally, in section 5, the paper is concluded with a brief summary and suggestions of the directions for our future studies.

2 Related work

2.1 Utility pattern mining

Numerous high utility pattern mining (HUPM) mining algorithms, such as Two-phase [21], IHUP [2], UP-Growth [29], have been devised in order to find patterns with utilities greater than or equal to a minimum utility from databases. The apriori-like HUPM algorithm, Two-phase, first proposed the concept of transaction weighted utilization (TWU) to maintain the downward closure property in HUPM because the traditional downward closure property [1] in FPM does not hold in HUPM. Two-phase performs the generate-and-test approach based mining process, which generates all of the potential high utility patterns, i.e. candidates, level-by-level through the multiple database scans. When the generation of candidates (phase-1) is finished, Two-phase calculates the actual utilities of candidates through a database scan (phase-2). Thereafter, the tree-based HUPM algorithms, such as IHUP and UP-Growth, were devised in order to improve the mining performance of Two-phase by reducing the number of database scans significantly. These algorithms store TWU information of transactions in their tree-based data structure within one or two database scans. Then, they generate candidate patterns by performing mining processes on the data stored in the trees. Through an additional database scan, they determine actual high utility patterns from candidates.

The concept of high average utility pattern mining (HAUPM) was proposed to overcome the limitations of the utility measure for patterns in HUPM. The first devised HAUPM algorithm, TPAU (Two-Phase Average Utility mining) [9], performs its mining process in the way similar with that of Two-phase. However, TPAU employs the overestimated average utilities of patterns, called average utility upper bounds, to maintain the downward closure property instead of TWU. Through the property, TPAU can achieve the efficient mining performance by excluding the patterns with average utility upper bounds less than a given minimum average utility from sets of candidates. However, TPAU suffers from excessive computational time and huge memory usage caused by its mining process based on the generate-and-test approach. After that, improved HAUPM algorithms, such as PBAU (Projection-Based high Average Utility mining) [12] employing a projection-based data structure and an additional hash table, and ITPAU (Incremental TPAU) [10] designed based on the FUP algorithm [7] for mining HAUPs from incremental databases, have been devised. However, any research on HAUPM methods for mining recent HAUPs over data streams has not yet been conducted.

2.2 Mining recent interesting patterns from stream data

Mining valuable patterns from recent stream data has been an interesting topic in the stream pattern mining area. To achieve that goal, the following representative stream pattern mining techniques have been primarily exploited. 1) Landmark window model 2) Damped window model 3) Sliding window model. The characteristics of these models can be summarized as follows. The algorithms based on the landmark model [18, 20] only consider the transactions generated after a user-specified time period in their mining processes. Meanwhile, the algorithms based on the damped window model [4, 6] progressively decays importance of transactions, i.e. frequency in FDM, utility in HUPM, according to their age. Therefore, it can mine patterns that have high importance in recent data by deemphasizing importance of old data. In the algorithms based on the sliding window model [3 , 28], stream data are split into multiple chunks, which are called batches. Stream data in the sliding window model can be illustrated as shown in Fig. 1. Among all the stream data, the recently generated batches are included in the range of recent stream data, called a window. Before stream data are processed, a user specifies the number of transactions contained in each batch and the number of batches contained in a window. Whenever a new batch is inputted, the window slides, and the oldest batch is excluded from the window. When an algorithm based on the model receives a mining task, the mining process is performed on only the data included in the current window, and the patterns that have high importance in the window are mined as recent patterns.

2.3 Preliminaries

In the case of a market database, each transaction in the database is information of a customer, and each item is a product purchased by the customer. In the transaction, each product has its own quantity information, called internal utility. In Table 1, the left table, Table 1(a), shows example stream data consisting of eight transactions. On the other hand, the right table, Table 1(b), shows the profit information of each item, called external utility. In Table 1(a), each transaction has a unique identifier, called TID. As mentioned earlier, in the sliding window model, stream data are divided into multiple batches. Assume that the sizes of each batch and window are set as 2 and 3 by a user, respectively. The stream data in Table 1(a) can be split into four different batches from B₁ to B₄. The initial window, W₁, contains three batches from B₁ to B₃. When B₄ is inputted as new data, the oldest batch, B₁, is replaced with B₄. Then, the currentwindow becomes W₂, which includes only B₂, B₃, and B₄.

Let D = {T₁, T₂, …, T_n} be stream data, T ={i₁, i₂, …, i_k} be a transaction, I = {i₁, i₂, …, i_l} be a set of distinct items existing in D, and X be an itemset (or pattern) generated from D where T ∈ D, T ⊆ I, and X ⊆ I.

The following definitions are used in HAUPM.

Definition 1. (Utility of an item in a transaction) The utility of each item i in T, u (i, T), is calculated by multiplying the internal utility of i in T, iu (i, T), by the external utility of i, eu (i). $u (i, T) = iu (i, T) \times eu (i)$

For example, in Table 1, the utility of Ain T₁ is u (A, T₁) =1 × 2 =2.

Definition 2. (Average utility of an itemset in a transaction) The average utility of X in T, au (X, T), is calculated by dividing the summation of item utilities in X by the length of X, |X|. $au (X, T) = \frac{\sum_{X \subseteq T \land i \in X} u (i, T)}{| X |}$

For example, in Table 1, the average utility of the pattern, AB, in T₁ is $au (AB, T_{1}) = \frac{1 \times 2 + 3 \times 1}{2} = 2.5 .$

Definition 3. (Average utility of an itemset) The average utility of X in D, au (X), is calculated by summating the average utilities of X in all transactions included in D. $au (X) = \sum_{T \in D \land X \subseteq T} au (X, T)$

For example, in Table 1, the average utility of AB in D is au (AB) = au (AB, T₁)+ au (AB, T₃) + au (AB, T₅) + au (AB, T₆) + au (AB, T₈) =2.5 +1.5 + 1.5 + 2.5 + 1.5 = 9.5.

Definition 4. (Maximum utility of a transaction) The maximum utility of T, mu (T), becomes the utility value of the item that has the highest utility in T. $\begin{matrix} mu (T) & = & max (u (i_{1}, T), u (i_{2}, T), \\ u (i_{3}, T), \dots, u (i_{k}, T)) \end{matrix}$

For example, in Table 1, the maximal utility of T₁ is mu (T₁) = max(2, 3, 4) =4.

Definition 5. (Average utility upper bound of an itemset) The average utility upper bound of X in D, ub (X) is calculated by summating all maximum utilities of transactions containing X. $ub (X) = \sum_{T \in D} mu (T)$

For example, in Table 1, the average utility upper bound of AB in D is ub (AB) = mu (T₁) + mu (T₃) + mu (T₅) + mu (T₆) + mu (T₈) =4 + 12 + 12 + 9 +6 = 43.

Definition 6. (Minimum average utility) A minimum average utility threshold δ is given as a percentage value of U (the total utility), which is obtained by summating all item utilities in transactions containing a database. Then, the minimum average utility is computed by multiplying the minimum average utility threshold and the total utility. $minimum average utility = U \times δ$

If the average utility of a pattern is greater than or equal to the minimum average utility, the pattern is a HAUP. If the average utility upper bound of a pattern is less than a minimum average utility, all of the supersets of the pattern are not HAUPs. Therefore, the downward closure property can be maintained in HAUPM.

3 Mining high average utility patterns from recent stream data

In this section, we propose a novel algorithm, SHAU, and a tree-based data structure, SHAU-Tree, both of which are designed to mine recent HAUPs over data streams. In subsection 3.1, we provide a detailed explanation of the elements in the proposed data structure and how recent stream data can be stored in the data structure. Our algorithm differs from the previous HAUP algorithms in that old data can be deleted from the proposed data structure by performing updating processes on the data structure. These updating processes are also explained in this subsection. Then, the mining process of our algorithm is described in subsection 3.2. Various examples are also provided in the subsections in order to help understanding. Finally, we analyze the proposed algorithm in subsection 3.3. Figure 2 shows the overall process of SHAU.

3.1 Storing recent stream data by constructing the global SHAU-Tree

In order to store information of recent stream data in the global SHAU-Tree, we insert the transactions into the global SHAU-Tree arranging items in a lexicographic order. By inserting a transaction into the tree, its information can be represented as one of the paths in the tree. Each node in the tree has several elements in order to efficiently maintain information of the transactions.

Definition 7. (Elements of a node in the global SHAU-Tree) Each node n in the global SHAU-Tree consists of the following elements. 1) n . item, the identifier indicating the item of n 2) n . batch–list, an array data structure storing average utility upper bound information batch by batch. 3) n . link pointing to another node n’ in the global SHAU-Tree such that .

In traditional tree-based pattern mining algorithms, transactions with the same items can be inserted into the tree by simply sharing the same path. In the sliding window model, however, since transactions with the same items can simultaneously exist in different batches, we should store information of batches individually in order to delete only the data that belongs to the oldest batch from the tree when new data are inputted. Therefore, each node in the global SHAU-Tree has an additional data structure, called batch-list, for storing information of transactions batch by batch.

Definition 8. (Batch-lists of nodes) In order to store information of transactions batch by batch, nodes in the global SHAU-Tree have their own batch-lists which contain the same as the window size of the elements used for storing the information of transactions belong to the corresponding batches. The elements of a batch–list with k elements are denoted as batch–list [1], , batch - list [k].

Furthermore, the global SHAU-Tree has a header table that maintains average utility upper bounds of the distinct items in stream data. Each entry in the header table has the identifier of an item and the average utility upper bound of the item in the current window. The entries in header table are sorted in a lexicographic order according to the item identifiers. Meanwhile, each entry in the header table is linked with a node that has the same item as that of the entry. Since each node in the tree is also linked with another node that has the same item, the traversal of the nodes with the same item can be conducted efficiently through the link information in the corresponding entry and nodes.

3.1.1 Reducing average utility upper bounds in the global SHAU-tree

When a transaction is inserted into SHAU-Tree, the average utility upper bound information of patterns can be stored in the global SHAU-Tree by increasing the average utility upper bounds of the corresponding nodes by the maximal utility of the transaction. However, since average utility upper bounds of patterns are overestimated average utilities that can be much greater than actual average utilities of the patterns, a huge number of unnecessary candidates can be generated in the mining process. In this regard, the number of generated candidates can be dramatically reduced by minimizing average utility upper bounds in such a way that any loss of a HAUP does not occur. Through the reduction of the number of generated candidates, the performance of the proposed algorithm can be enhanced because the process for calculating the actualaverageutilities of candidates consumes enormous time. Hence, in order to minimize average utility upper bounds in the global SHAU-Tree, we employ the RUG (Reducing average utility Upper bound in the Global SHAU-Tree) strategy.

Definition 9. (RUG strategy) Let T = {i₁, i₂, …, i_n} be an ordered transaction to be inserted into the global SHAU-Tree. When we increase the average utility upper bounds of the nodes during the insertion of T, they are increased by the corresponding items’ conditional maximal utilities (CMUs) in T instead of the maximal utility of T. The CMU of i_n in T, cmu (i_n, T), is obtained as follows. $\begin{matrix} cmu (i_{n}, T) & = & max (u (i_{1}, T), \\ u (i_{2}, T), \dots, u (i_{n}, T)) \end{matrix}$

Example 3.1.Assume we insert transactions of the initial stream data (W₁) in Table 1 into the empty global SHAU-Tree. First, the transactions in B₁, T₁ and T₂, are inserted into the tree. In order to insert T₁, we calculate the CMUs of the items in T₁ according to definition 9. The CMUs are computed as follows: cmu (A, T₁) =2, cmu (B, T₁) =3, and cmu (F, T₁) =4. For inserting A, B, and F, the header table of the global SHAU-Tree is first updated. Since no entry exists in the header table, the entries with A, B, and F are created, and their average utility upper bounds are initialized to the values of the corresponding CMUs. We also create the path consisting of the nodes for A, B, and F under the root node. Each created node is linked with the corresponding entry in the header table. Since B₁ is the first batch added to the window, the values of the CMUs are added to the first elements of the batch-lists in the nodes. Next, we calculate the CMUs of the items in T₂. The CMUs are obtained as follows: cmu (B, T₂) =3, cmu (D, T₂) =6, and cmu (F, T₂) =8. T₂ is also inserted into the tree by creating a new path because the first item of T₂, B, does not exist under the root node. After two transactions, T₁ and T₂, are inserted into the global SHAU-Tree, we can construct the global SHAU-Tree asshown in Fig. 3(a).

Subsequently, we insert other batches B₂ and B₃ into the global SHAU-Tree. The CMUs of the items in T₃ and T₄ can be gained as follows: cmu (A, T₃) =2, cmu (B, T₃) =2, cmu (D, T₃) =12, cmu (E, T₃) = 12, cmu (B, T₄) =2, cmu (E, T₄)= 3, cmu (F, T₄) =4. Since the path, <A, B>, already exists under the root node, A and B in T₃ are inserted by sharing the existing nodes. The rest of the items in T₃ are inserted under the path <A, B>by creating new nodes. Since information of B₁ is stored in the first elements of batch-lists, the items are inserted by increasing the second elements of batch-lists. After T₄ is inserted in the same manner of the insertion of T₃, we obtain the global SHAU-Tree in Fig. 3(b). After T₅ and T₆ in B₃ are also inserted in the same manner, we can construct the global SHAU-Tree shown in Fig. 3(c), which maintains the information of W₁. As indicated in the figures, three batch-list elements in each node store the ub values of B₁, B₂, and B₃, respectively.

3.1.2 Updating the global SHAU-Tree

If new data is generated from a data stream and the current window is full, we need to replace the data of the oldest batch with the new data in order to make the global SHAU-Tree maintain only the recent stream data. Hence, we should perform an updating process on the global SHAU-Tree whenever the new batch is inputted. This process can be performed via the following steps. First,the information of the oldest batch is removed from all of the nodes in the global SHAU-Tree through the traversal of the tree. If any batch information does not remain in a certain node after the oldest batch is removed, the node is pruned from the tree in order to minimize the memory usage for maintaining the tree. These processes are performed by following the links in the header table in the bottom-up sequence. Since the header table is sorted in a lexicographic order, the processes are performed from the bottommost entry to the uppermost entry. During the updating processes, if a certain node is not pruned from the tree, all of its ancestors are also not pruned from the tree. Accordingly, we do not need to perform any process for merging duplicated nodes after obsoletes nodes are pruned because there are no cases in which the multiple child nodes with the same item exist under a node.

Lemma 1. If a certain node in the global SHAU-Tree is not an obsolete node, all of its ancestors are also not obsolete nodes.

Proof. Recall that the ordered transaction, t = {i₁, i₂, …, i_n}, can be expressed as one of the paths in the tree, p, consisting of the nodes, n (i₁) , n (i₂) , …, n (i_n). After information of old transactions is deleted from the tree in order to delete the oldest batch from the window, if a certain node included in p, n (i_k) (1 ≤ k ≤ n), has any batch information in its batch-list, we can obviously know that a transaction , such that , still exists in a certain batch included in the updated window. Accordingly, all the ancestors of n (i_k), n (i₁), n (i₂) , …, n (i_k-1), are also not obsolete nodes because they apparently have information of t’ in their own batch-lists. ■

Example 3.2. Consider inserting the new batch, B₄, into the global SHAU-Tree constructed in the example 3.1. Since the global SHAU-Tree is presently full with old batches, B₁, B₂, and B₃, we need to delete the oldest batch, B₁, from the global SHAU-Tree. To delete B₁, the first elements of batch-lists in all of the nodes are set as 0. After deleting B₁, as shown in Fig. 4(a), we can observe that several nodes have zero values in all elements of their batch-lists, which are marked with dotted rectangles. Since they do not have any batch information, we prune them from the tree. Then, we can obtain the global SHAU-Tree without B₁ as shown in Fig. 4(b). Thereafter, the transactions in B-₄ are inserted into the global SHAU-Tree one by one. The transactions are inserted into the tree by increasing the average utility upper bounds in the first elements of batch-lists. The insertion is conducted in the same manner as the insertions of transactions in the example 3.1. After B₄ is inserted, we can obtain the global SHAU-Tree shown in Fig. 4(c), which maintains the information of W₂.

3.2 Mining recent high average utility patterns from stored data

To mine recent HAUPs from the data stored in the global SHAU-Tree, the mining process is performed on the basis of the pattern growth approach [11], which employs the divide-and-conquer approach and the recursive call manner. First, we select a prefix item from the header table of the global SHAU-Tree in the bottom-up sequence. Recall that the average utility upper bounds of the items in the header table signify the maximum average utilities of the patterns extended from the items. Therefore, if the average utility upper bound of the selected item in the header table is less than a minimum average utility, we do not perform any pattern growth operations for the item because any pattern extended from the item obviously has an average utility less than a minimum average utility. Otherwise, the item becomes a new prefix, and it is added to a set of candidate patterns. Thereafter, we construct the conditional tree for the prefix. To construct the conditional tree, the conditional pattern base of the prefix is first extracted from the global SHAU-Tree by traveling all of the nodes with the item. For each visited node, the path from the root node to the node is extracted and added to the conditional pattern base. Here, the maximum utility of the extracted path is set as the summation of the average utility upper bounds in the batch-list of the node. After the conditional pattern base is extracted, by summating all of the maximum utilities of the paths in the conditional pattern base for each item, we can obtain the average utility upper bound of each item. On the basis of these values, we remove the items with average utility upper bounds less than the minimum average utility from the conditional pattern base because they cannot generate any HAUP in further pattern growth operations. Based on the remaining items, the conditional tree can be constructed by inserting the paths in the conditional pattern base into the empty conditional tree. In the insertion of a certain path, average utility upper bounds of nodes are increased by the maximum utility of the path. Note that the nodes in conditional trees do not have batch-lists because we do not need to process information of batches individually in the conditional trees. After that, we recursively perform the same process for the next prefix obtained by combining the previous prefix and a new prefix item selected from the header table of the constructed conditional tree.

Example 3.3. Suppose we mine recent HAUPs from the data stored in the global SHAU-Tree constructed in Fig. 4(c), and a minimum average utility is given as 17. First, we select the bottommost item from the header table as a new prefix item. Since the bottommost item, F, has the average utility upper bound less than the minimum average utility, 17, we obviously know that any pattern generated from the pattern growth operations for F has average utility less than the minimum average utility. Therefore, we select the next bottommost item, E, without performing the pattern growth operations for F. Since E has the average utility upper bound greater than 17, the pattern E is added to a set of candidate patterns, and we perform the pattern growth operations for E. When a extracted path is denoted as <i₁, i₂, … , i_n : maximum utility >, the paths in the E’s conditional pattern base are gained from the global SHAU-Tree as follows: <A, B, C, D:6>, <A, B, D:12>, and <B:3>. Then, the average utility upper bound of each item can be calculated as follows: A = 6 + 12 = 18, B 6 + 12 + 3 = 21, C = 6, and D = 6 + 12 = 18. Since C has the average utility upper bound less than 17, C is removed from the conditional pattern base. Subsequently, by inserting the paths without C, <A, B, D:6>, <A, B, D:12>, and <B:3>, into the empty conditional tree, we can construct the E’s conditional tree as shown in Fig. 5(a). Then, we recursively perform the pattern growth operations on the basis of the conditional tree. The bottommost item in the headertable of the conditional tree, D, is selected as the next prefix item. Therefore, ED becomes a new prefix. ED is also added to a set of candidate patterns. We can construct the ED’s conditional tree shown in Fig. 5(b) in the same manner as the construction of the E’s conditional tree. After all of the pattern growth operations for E are performed, we can gain the following candidate patterns: E, E, ED, EDB, EDBA, EDA, EB, EBA, and EA. Table 2 shows the candidate patterns extended from the initial prefix items and their calculated average utilities. Note that the pattern growth operations for the prefix items, A, B, and C, are also not performed because their average utility upper bounds in the header table are less than 17. Since only the patterns D and DA have the average utilities greater than or equal to 17 in W₂, D and DA are mined as recentHAUPs.

3.3 Description of SHAU algorithm

In this subsection, we describe the procedure of the SHAU algorithm. Fig. 6 shows the overall procedure of the SHAU algorithm. The procedure receives four parameters as follows, S (stream data),δ (a minimum average utility threshold), ws (a window size), and bs (a batch size). In the beginning of the procedure, the global SHAU–Tree, SHAU - Tree, and a set of generated HAUPs, P, are initialized. The variables, b and tn, indicate the current batch number in the window and the current transaction number, respectively. They are initialized to 1. For each transaction in S, the procedure sorts it in a lexicographic order according to the item identifiers, inserts it into SHAU–Tree through the InsertBatch sub-procedure. Then, the value of tn is increased by 1. If the value of tn becomes equal to that of bs, in the other words, the current batch is full with transactions, b is increased by 1. Then, if the value of b becomes greater than that of ws, b is set as 1 because the first batch becomes the oldest batch in the window. When the first transaction of the new batch is inserted, the oldest batch is deleted from SHAU–Tree by calling the DeleteBatch sub-procedure. These processes are repeated by a loop condition until the procedure receives a mining request.

If a mining request occurs, the minimum average utility in the current window, minutil, is calculated on the basis of the current total utility U_W and the minimum average utility threshold δ given as a parameter. Thereafter, a set of generated candidates, C, is initialized to an empty set. It is used to store candidates generated in the mining process. For each item in the header table of SHAU–Tree, if the item has an average utility upper bound (denoted as ub) greater than or equal to minutil, the item is added to aset of prefix items p. Then, p is added to C as a new candidate pattern. Then, the conditional tree for the selected item is constructed. After that, by calling the mining procedure, Growth, the pattern growth operations for the prefix are performed. After all the pattern growth operations are finished, actual average utilities of candidates in C are computed in order to determine whether the candidates are HAUPs. Finally, the mined HAUPs are provided to users as mining results, and the procedure continues to process streamdata.

Figures 7 and 8 show the InsertBatch and DeleteBatch sub-procedures. InsertBatch receives a transaction t and the current batch number b as parameters. The procedure inserts the items in the transaction into SHAU-Tree one by one. In order to insert items from the root node, parent initially points to the root node. For each item in the transaction, its CMU is first calculated. Then, the header table is updated by increasing the average utility upper bound of the item by the CMU. If the node with the item does not exist under parent, a new node n is created. Then, n.item is set as the item and n.batchlist is increased by the CMU. Otherwise, the existing node n is updated by increasing n.batchlist[b]. These processes are repeated by a loop condition until there is no next item to be inserted. Figure 8 presents the DeleteBatch sub-procedure. It receives a parameter b, which is the batch number of the batch to be deleted from SHAU-Tree. In order to delete the information of the oldest batch from SHAU-Tree, the links in the header table of SHAU-Tree are traced. The b elementof each visited node n, n.batch-list[b], is set as 0. If all of the elements in the batch-list have 0, this node is pruned from the tree.

The sub-procedure for performing pattern growth operations, Growth, is shown in Fig. 9. For each item in the header table of the given conditional tree ctree, the item is checked whether its average utility upper bound is no less than minutil. If it is, any operation for the item is not performed. Otherwise, the item is selected as the next prefix item, and it is added to the previous prefix, p. Subsequently, the p is added to a set of candidates. Then, the conditional tree for the new prefix, ctree’, is constructed, and Growth is recursively called. If there is no remaining item in the header table, then the procedure is terminated.

4 Performance evaluation

4.1 Environmental settings

In order to evaluate the performance of the SHAU algorithm, several experiments on real datasets have been conducted under various experimental settings. We compared SHAU with ITPAU [10] and STPAU algorithms. As mentioned in section 2, ITPAU is the HAUPM algorithm for mining HAUPs from incremental databases. Meanwhile, STPAU is a naïve sliding window based HAUPM algorithm modified from TPAU [9]. The algorithms were made by the C++ program language. We conducted the experiments on a PC with the 3.30 GHz CPU, 8GB RAM, and Windows 7 64 bit operating system. We implemented SHAU and STPAU to perform their mining processes at each window. ITPAU was implemented to perform the first mining process on the original database containing the same data as those of the first windows of SHAU and STAU. Then, ITPAU continually increases the size of the database by the size of a batch. The real datasets, Chain-store, Retail, Mushroom, and Chess, were used to evaluate the runtime and memory usage performances of the algorithms. Chain-store was gained from NU-Minebench 2.0 (http://cucis.ece.northwestern.edu/projects/DMS/MineBench.html), and the rest of datasets were obtained from the FIMI repository (http://fimi.cs.helsinki.fi). Chain-store and Retail are the datasets containing retail market basket data. Mushroom is a dataset contains information about 23 species of mushrooms. Chess contains the data collected from a number of chess games. The information of each real dataset, the number of transactions in a dataset (|D|), the average length of transactions (|T|), and the number of distinct items (|I|), are shown in Table 3.

4.2 Performance comparison under different minimum average utility thresholds

First, we compare the performances of the algorithms under different minimum average utility thresholds. In order to show the effects on the performances of the compared algorithms caused by the changes of minimum average utility thresholds, experiments were conducted where the sizes of each batch and a window were fixed. Figures 10 and 11 present the experimental results of runtime and memory usage tests under different minimum average utility thresholds, respectively. In the figures, the values of ws and bs indicate the sizes of each batch and a window, respectively. In Fig. 10, they-axis shows the changes of the algorithms’runtimes, and the x axis signifies the decrease of a minimum average utility threshold. We determine the total runtimes of the algorithms as the summations of runtimes for mining processes at all windows. However, in the experiments on Chain-store, the algorithms only perform their mining processes at the first windows because enormous runtimes are required to finish the mining processes for the entire data of Chain-store. Moreover, since the runtimes of the apriori-like algorithms, STPAU and ITPAU, can significantly increase, if total runtimes exceed 10000 seconds during the experiments, we terminate the mining processes considering they do not normally work. Through the observation on the experimental results in Fig. 10, we can determine that the runtime performances of the compared algorithms generally become worse at low minimum average utility thresholds because the number of generated candidates is increased along with the decrease of the threshold. However, we can observe that SHAU has the highest runtime performance in all cases. Moreover, the runtimes of STPAU and ITPAU rise much faster than that of SHAU. In the experimental results, we also see that the mining processes of SHAU are completed within 50 seconds, while the mining processes of ITPAU and STPAU spend at least 150 seconds to be completed. Since the mining processes of STPAU spend over 10000 seconds at the minimum average utility thresholds lower than 0.41 % , the processes are terminated before being completed. Overall, both STPAU and ITPAU have the runtime performances much worse than that of SHAU. Meanwhile, since ITPAU utilizes the concept of the FUP algorithm in order to reduce the number of database scans in each mining process, it generally has runtime performances slightly better than those of STAPU except for the performance in Fig. 10(d).

Next, we compare the memory performances of the algorithms. Figure 11 shows the experimental results of the memory usage test under different minimum average utility thresholds. These experiments have been conducted with the same conditions as those of the runtime test in Fig. 10. However, the y-axis indicates the change of memory usage instead of the change of runtime. The memory performances of the algorithms were measured in their peak memory usage during their entire mining processes. Since the algorithms use large memory to generate a large number of candidates at low thresholds, we can observe that the memory performances of the algorithms generally worsen as the minimum average utility threshold is decreased. However, we can know that SHAU consumes much lower memory than those ITPAU and STPAU in all cases. The reason is that ITPAU and STPAU generate a huge number of potential candidates because they follow the generate-and-test approach. At the low threshold settings, ITPAU and STPAU consume memories, which are almost two times of that of SHAU. Meanwhile, ITPAU has memory performance somewhat worse than that of STPAU because ITPAU is designed to store the information of a set of HAUPs generated from the mining process in the main memory in order to utilize them in the next incremental mining process.

5 Conclusions

In this paper, we proposed the first HAUPM algorithm considering the time factors of transactions in order to find recent, important HAUPs over data streams. We devised SHAU-Tree to efficiently maintain recent stream data consisting of multiple batches. Each batch can be handled individually by employing batch-lists of nodes in the global SHAU-Tree. In addition, we suggested the RUG strategy, which minimizes the average utility upper bounds in the global SHAU-Tree. However, since stream data are rapidly generated from various applications, processing them within minimum runtimes is an important issue. Moreover, maintaining memory usage within minimum sizes is also a primary challenge because the sizes of the stream data are typically very large. Therefore, in order to achievemore efficient mining processes in stream environments, runtime and memory performances of the algorithm should be improved. In this respect, we are planning to conduct research for enhancing the performance of our algorithm in our upcoming studies.

Footnotes

Acknowledgments

This research was supported by the National Research Foundation of Korea (NRF) funded by the Ministry of Education, Science and Technology (NRF No. 20152062051, and NRF No. 20155054624), and the Business for Academic-industrial Cooperative establishments funded Korea Small and Medium Business Administration in 2015 (Grants No. C0261068).

References

Agrawal

and Srikant

, Fast Algorithms for Mining Association Rules, Proceedings of the 20th International Conference on Very Large Data Bases Bases, 1994, pp. 487–499.

Ahmed

C.F.

, Tanbeer

S.K.

, Jeong

and Lee

, Efficient tree structures for high utility pattern mining in incremental databases, IEEE Transactions on Knowledge and Data Engineering21(12) (2009), 1708–1721.

Ahmed

C.F.

, Tanbeer

S.K.

, Jeong

B.S.

and Choi

H.J.

, Interactive mining of high utility patterns over data streams, Expert Systems with Applications39(15) (2012), 11979–11991.

Chen

and Mei

, Mining frequent items in data stream using time fading model, Information Science257 (2014), 54–69.

Chen

, Shu

, Xia

and Deng

, Mining frequent patterns in a varying-size sliding window of online transactional data streams, Information Sciences215 (2012), 15–36.

Chang

J.H.

and Lee

W.S.

, Finding recently frequent itemsets adaptively over online transactional data streams, Information Systems31(8) (2006), 849–869.

Cheung

, Han

, Ng

and Wong

, Maintenance of Discovered Association Rules in Large Databases: An Incremental Updating Approach, The 12th IEEE International Conference on Data Engineering, 1996, pp. 106–114.

Ghazikhani

, Monsefi

and Yazdi

H.S.

, Online neural network model for non-stationary and imbalanced data stream classification, International Journal of Machine Learning and Cybernetics5(1) (2014), 51–62.

Hong

T.P.

, Lee

C.H.

and Wang

S.L.

, Effective utility mining with the measure of average utility, Expert Systems with Applications38(7) (2011), 8259–8265.

10.

Hong

T.P.

, Lee

C.H.

and Wang

S.L.

, An Incremental Mining Algorithm for High Average-Utility itemsets, pp, 10th International Symposium on Pervasive Systems, Algorithms, and Networks (2009), 421–425.

11.

Han

, Pei

, Yin

and Mao

, Mining frequent patterns without candidate generation: A frequent-pattern tree approach, Data Mining and Knowledge Discovery8(1) (2004), 53–87.

12.

Lan

G.C.

, Hong

T.P.

and Tseng

V.S.

, A projection-based approach for discovering high average utility itemsets, Journal of Information science and Engineering28(1) (2012), 193–209.

13.

Lan

G.C.

, Hong

T.P.

and Tseng

V.S.

, Efficiently mining high average-utility itemsets with an improved upper-bound strategy, International Journal of Information Technology and Decision Making11(5) (2012), 1009–1030.

14.

Lee

, Yun

and Ryu

, Sliding window based weighted maximal frequent pattern mining over data streams, Expert Systems with Applications41(2) (2014), 694–708.

15.

Lee

, Yun

and Ryang

, Mining weighted erasable patterns by using underestimated constraint-based pruning technique, Journal of Intelligent and Fuzzy Systems28(3) (2015), 1145–1157.

16.

Lee

, Yun

, Ryang

and Kim

, Multiple minimum support-based rare graph pattern mining considering symmetry feature-based growth technique and the differing importance of graph elements, Symmetry-Basel7(3) (2014), 1151–1163.

17.

Lee

, Yun

and Ryang

, An uncertainty-based approach: Frequent itemset mining from uncertain data with different item importance, Knowledge-Based Systems90 (2015), 239–256.

18.

, Shan

and Lee

, DSM-FI: An efficient algorithm for mining frequent itemsets in data streams, Knowledge and Information Systems17(1) (2008), 79–97.

19.

Liu

and Qu

, Mining High Utility Itemsets without Candidate Generation, The 21th ACM International Conference on Information and Knowledge Management, 2012, pp. 55–64.

20.

Liu

, Guan

and Hu

, Mining frequent closed itemsets from a landmark window over online data streams, Computers & Mathematics with Applications57(6) (2009), 927–936.

21.

Liu

, Liao

and Choudhary

, A two-phase algorithm for fast discovery of high utility itemsets, Advances in Knowledge Discovery and Data Mining3518 (2005), 689–695.

22.

, On-line and dynamic time warping for time series data mining, International Journal of Machine Learning and Cybernetics6(1) (2015), 145–153.

23.

, Vo

, Nguyen

H.T.

and Hong

T.P.

, A new method for mining high average utility itemsets, Computer Information Systems and Industrial Management8838 (2014), 33–42.

24.

Pyun

, Yun

and Ryu

, Efficient, frequent pattern mining based on linear prefix tree, Knowledge-based Systems55 (2014), 125–139.

25.

Pyun

and Yun

, Mining Top-k frequent patterns with combination reducing techniques, Applied Intelligence41(1) (2014), 76–98.

26.

Ryang

and Yun

, Top-k high utility pattern mining with effective threshold raising strategies, Knowledge-Based Systems76 (2015), 109–126.

27.

Ryang

, Yun

and Ryu

, Discovering high utility itemsets with multiple minimum supports, Intelligent Data Analysis18(6) (2014), 1027–1047.

28.

Tanbeer

S.K.

, Ahmed

C.F.

, Jeong

and Lee

, Sliding window-based frequent pattern mining over data streams, Information Sciences179(22) (2009), 3843–3865.

29.

Tseng

V.S.

, Shie

, Wu

and Yu

P.S.

, Efficient algorithms for mining high utility itemsets from transactional databases, IEEE Transactions on Knowledge and Data Engineering25(8) (2013), 1772–1786.

30.

Yun

and Ryang

, Incremental high, utility pattern mining with static and dynamic databases, Applied Intelligence42(2) (2015), 323–352.

31.

Yun

, Ryang

and Ryu

, High utility itemset mining with techniques for reducing overestimated utilities and pruning candidates, Expert Systems with Applications41(8) (2014), 3861–3878.

32.

Yun

, Lee

and Ryu

, Mining maximal frequent patterns by considering weight conditions over data streams, Knowledge-Based Systems55 (2014), 49–65.