Temporal association rules discovery algorithm based on improved index tree

Data mining is motivated by the decision support problem faced by many organisations. Among all techniques, mining association rules are able to find an interesting association or correlation relationships from a large collection of data items. It is useful to discover all such relationships for many organisations. Most of the proposed methods developed in mining frequent patterns focus on the problems with discrete data items such as customers’ buying data in a supermarket. However, there exist some problems where the data items are associated with intervals (continuous or discrete) in database transactions [1, 2]. All the previously proposed methods are not completely suitable for these problems.

First, let us take a look at some applications in the real world where the data items are associated with intervals. For example, there is a large database recording the time and number of people making phone calls with cellular phones for a telephone company. The phone usage data are usually associated with an interval with the starting and ending time. Hence, if we can mine the frequent calling intervals and thus figure out the ‘hotter’ time intervals in which customers are more likely to use their cellular phones, the cellular phone companies can be more comprehensive of the usage patterns of customers and can therefore make better marketing decisions or provide better services.

Therefore, in this article, we propose two methods to mine frequent intervals. The first method is revised from the Apriori algorithm [3]. However, because of the inefficiency with the Apriori-modified algorithm [4], we proposed the second algorithm. The algorithm uses an index tree structure, called Index-Tree, which is used to efficiently store all the intervals in a database. The new mining frequent intervals can not only provide better predictability for customer behaviour but also help organisations with better strategies and marketing decisions.

If we want to mine large itemsets in a database, we just have to generate all possible candidate itemsets and scan the whole database to verify which ones are frequent for the exact solution. But things will be different if the database is composed of many data intervals. If the intervals are within the discrete domain as in the railroad example, the situation is simpler and we can view each railroad station as an individual item. A transaction will become a set of several successive stations, then, and we may be able to use traditional methods to find frequent intervals. The major difference is that the stations in the frequent interval must be in sequential order.

However, when we are mining frequent intervals within a continuous domain such as the temporal data in the telephone company example, the main difficulty is that the number of data points in a continuous interval is infinite [5, 6]. In a huge database containing plenty of data intervals, it is impossible and unrealistic to find all possible frequent data point, just like what we do for those discrete transaction data. Therefore, what we do here is just to discretise the whole continuous domain into several equal-sized unit intervals, and then transform the original data according to these unit intervals, as shown in Figure 1. After transforming the data, we can then treat them the same way as data intervals with discrete domain as in the railroad company example.

Fig. 1

After surveying the related data mining techniques, we can see that all the previous methods focus on the problems of finding the large itemsets or finding the frequent path/segments [7, 8]. These methods are not suitable for the problems of finding the temporal association. When the data are associated with intervals, some special properties are anticipated to arise, which may facilitate us to mine frequent intervals. Therefore, we shall propose methods to mine frequent intervals in the following section.

Here an example is given as below that there is a database D has 10 transactions as illustrated in Figure 2.

Fig. 2

Although we know that the performance of the FP growth algorithm is better than the Apriori algorithm [9], our proposed methods still adopt the Apriori-modified approaches. This is because the FP growth algorithm has some problem in dealing with multi-dimensional intervals. Since the FP growth algorithm cannot intuitively and efficiently handle the multi-dimensional problems [10], whereas the concept of the Apriori algorithm does very well, we choose the Apriori algorithm for the basic approach in this article.

The first algorithm we propose to solve the problem of mining frequent intervals is revised from the Apriori algorithm. We can then directly apply the Apriori algorithm to find any frequent k intervals. The first step is to find all frequent 1 intervals and their corresponding supports by scanning the database once. Assume that F_k means the set of all frequent k intervals. Then we can generate all candidate (k + 1) intervals, C_k+1, by joining F_k with itself, denoted by F_k * F_k. However, due to the characteristic of our problem, we modify the joining approach as follows. For any two distinct frequent k intervals in F_k, say (U_s, U_e) and (U_s′, U_e′), we join them into a candidate (k + 1) interval only if s - s’ = 1. The resulting candidate interval is (U_s′, U_e). With the set of all candidate (k 1) intervals, C_k+1, we can scan the database and get the set of all frequent (k + 1) intervals, F_k+1, and their supports. The process is repeated until no new frequent interval generated. Then we can get all frequent intervals and their corresponding supports. This Apriori-modified algorithm is illustrated in Figures 3 and 4.

Fig. 3

Fig. 4

The main advantage of the Apriori algorithm is simple. However, there are two drawbacks for the Apriori algorithm in finding large itemsets for association rules [11]. One is that a large number of candidate itemsets may be generated (at most 2ⁿ, n is the number of items). The other is that the times of scanning database may be the number of items in the longest large itemset.

However, when we are mining frequent intervals, the maximum number of possible candidate intervals is bound by O(m²), where m is the number of unit intervals in the domain, because of the characteristic of such a kind of mining problem [12]. This number is much smaller than O(2^m). The reason is that the total number of intervals in a domain with m unit intervals is: m+(m-1)+…+2+1=∑k=1mk=m(m+1)2=O(m2). m + (m - 1) + \ldots + 2 + 1 = \sum\limits_{k = 1}^m {k = {{m(m + 1)} \over 2}} = O({m^2}). Therefore, the problem of generating tremendous candidates in finding frequent intervals is not as serious as in the association rules mining.

But the Apriori-modified method is still not efficient enough since it may scan the database as many times as the length of the longest frequent interval. We know that in the real-world application, database D is usually very large. It is unsatisfactory to scan the whole database multiple times. Therefore, we propose the second method to improve efficiency in the next section.

Example: Consider the data shown below to ascertain the steps with which to find all the frequent intervals using the Apriori-modified algorithm, as shown in Figure 5.

Fig. 5

In this section, we compare the performance of our proposed methods for mining frequent intervals. We first synthesise 1-d interval data to evaluate these two methods. The synthetic data are generated as follows. The lengths of intervals are in Poisson distribution with mean m. Then the starting point of an interval is distributed uniformly. Four factors are dominating the performance of both methods in the 1-d case: the number of transactions (D), mean length of an interval (m), minimum support threshold (s) and the number of unit intervals (n). We freely set the values of the first three factors in the synthetic data.

In Figure 12, we compare the running time against the number of transactions for both methods. The number of transactions ranges from 10K to 100K, the number of unit intervals is 100, the mean length of each interval is 5%, and the minimum support threshold is 5%. As shown in Figure 12, the performance of the Index-Tree-Method algorithm outperforms that of the Apriori-modified algorithm. The running time of both algorithms increases as the number of transactions increases since the cost of scanning the database and that of the Index-Tree also increases.

Fig. 12

In Figure 13, we compare the running time against the mean length of each interval for both methods. The mean length of each interval ranges from 5% to 50%, the number of transactions is 10K, the number of unit intervals is 100 and the minimum support threshold is 5%. As shown in Figure 13, the running time of both algorithms increases linearly as the mean length of each interval increases. When the mean length of intervals increases, so does the number of scanning the database in the Apriori-modified algorithm and that of scanning the Index-Tree. Therefore, the running time of both methods increases when we increase the mean length of intervals. The running time of the Index-Tree-Method algorithm scales better than that of the Apriori-modified algorithm with respect to the mean length of intervals.

Fig. 13

In Figure 14, we compare the running time against the minimum support threshold for both methods. The support threshold ranges from 0.01% to 30%, the number of transactions is 100K, the number of unit intervals is 100 and the mean length of each interval is 5%. When the support threshold decreases, the number of candidate intervals increases dramatically. It also increases the number of scanning the database in the Apriori-modified algorithm as well as that of scanning the Index-Tree in the Index-Tree-Method algorithm. Therefore, the running time of both methods increases enormously when we decrease the minimum support threshold. Because the Index-Tree is more condensed than the database, the running time of the Index-Tree-Method algorithm scales better than that of the Apriori-modified algorithm with respect to the minimum support threshold.

Fig. 14

We take a different approach to generate data when evaluating the effect of the number of unit intervals. To ensure fairness, we enforce all the data are in the same distribution. That is, we first generate data with D = 10K, n = 500 and m = 5% using the procedure described previously. Then we expand the number of unit intervals by dividing each unit interval into several equal-sized unit intervals. The original interval in each transaction is also transformed according to the new unit intervals. The factor of division is varied from 1 to 10 and the result is shown in Figure 15.

Fig. 15

When the number of unit intervals increases, the number of candidate intervals increases significantly. The number of scanning the database in the Apriori-modified algorithm and that of scanning the Index-Tree in the Index-Tree-Method algorithm also increase. Therefore, the running time of both methods increases exponentially with respect to the number of unit intervals. However, the performance of the Index-Tree-Method algorithm still scales better than that of the Apriori-modified algorithm.

The next parameter is the number of dimensions. The method of generating data remains the same except that we only generate data for one dimension. The other dimensions are the same as the first dimension. This means the edges of the generated rectangles, cubes and hyper-cubes are all of equal length. The number of dimensions ranges from 1 to 5, the number of transaction is 10K, the number of unit intervals is 10, the mean length of interval is 40% and the minimal support threshold is 30%. The effect of a different number of dimensions is shown in Figure 16.

Fig. 16

When the number of dimensions increases, the number of candidate intervals increases enormously. The number of scanning the database in the Apriori-modified algorithm and that of scanning the Index-Tree in the Index-Tree-Method algorithm also increase. Although the size of the Index-Tree is large when the number of dimensions is large, the Index-Tree is more condensed than the database, and the performance of the Index-Tree-Method algorithm is better than that of the Apriori-modified algorithm.

The last experiment about mining frequent intervals is to evaluate the performance of both methods when there exists a memory constraint. We only compare the running time of scanning and joining operations in both methods, because we assume that the Index-Tree has already been constructed on the disk. We want to show that even if an Index-Tree is constructed on the disk, the cost of scanning an Index-Tree is less than that of scanning the database. The memory size ranges from 1K bytes to 5K bytes. The number of transactions is 10K, the number of unit intervals is 100, the mean lengths of intervals are 5% and the support threshold is 0.5%. The experiment result is shown in Figure 17.

Fig. 17

When the available memory decreases, we have to fetch one block of data from the database or to fetch one segment of the disk-resident Index-Tree at one time. Besides, the memory consumed by generating candidate intervals may exceed the memory available. Therefore, we have to store them on the disk and swap them to count their frequencies and supports. As a result, the less memory we have, the more input–output operations will be required. However, the Index-Tree is more condensed than the database, so the performance of the Index-Tree-Method algorithm is better than that of the Apriori-modified algorithm as shown in Figure 17.

From the results of those experiments, we can see that the Index-Tree method outperforms the Apriorimodified method for all the cases.

A compact data structure Index-Tree is proposed and used the Index-Tree to store all the needed information. The Index-Tree is an extended prefix-tree structure which is capable of storing crucial, quantitative information about the intervals. The Index-Tree is compact in the following three aspects. First, since only frequent items will play a role in the frequent mining, the Index-Tree stores the set of frequent items for each transaction. Second, if multiple transactions contain equivalent itemsets, they are stored in the Index-Tree once and a counter is used to record the number of occurrences. Third, if any two transactions share a common prefix, the prefix items are stored in the Index-Tree once.

Some future work is shown as follows. Although an Index-Tree is compact, we have to construct it each time, as and when we mine frequent intervals. If we are going to regularly mine the same database, it could be more efficient to materialise the Index-Tree for later mining. Once an Index-Tree has been constructed, we can thereafter use the same Index-Tree to reduce the cost of reconstructing it unnecessarily. The cost of constructing an Index-Tree may sometimes be a non-trivial overhead. This is an interesting research-issue which concerns the question of solving problems using the Index-Tree structure.