HƯỚNG DẪN DOWNLOAD TÀI LIỆU

Bước 1:Tại trang tài liệu slideshare.vn bạn muốn tải, click vào nút Download màu xanh lá cây ở phía trên.

Bước 2: Tại liên kết tải về, bạn chọn liên kết để tải File về máy tính. Tại đây sẽ có lựa chọn tải File được lưu trên slideshare.vn

Bước 3: Một thông báo xuất hiện ở phía cuối trình duyệt, hỏi bạn muốn lưu . - Nếu click vào Save, file sẽ được lưu về máy (Quá trình tải file nhanh hay chậm phụ thuộc vào đường truyền internet, dung lượng file bạn muốn tải)

Có nhiều phần mềm hỗ trợ việc download file về máy tính với tốc độ tải file nhanh như: Internet Download Manager (IDM), Free Download Manager, ... Tùy vào sở thích của từng người mà người dùng chọn lựa phần mềm hỗ trợ download cho máy tính của mình

VNU Journal of Science: Comp. Science & Com. Eng., Vol. 31, No. 1 (2015) 1-21
An Efficient Tree-based Frequent Temporal Inter-object Pattern Mining Approach in Time Series Databases
Nguyen Thanh Vu, Vo Thi Ngoc Chau*
Ho Chi Minh City University of Technology, Ho Chi Minh City, Vietnam
Abstract
In order to make the most of time series present in many various application domains such as finance, medicine, geology, meteorology, etc., mining time series is performed for useful information and hidden knowledge. Discovered knowledge is very significant to help users such as data analysts and managers get fascinating insights into important temporal relationships of objects/phenomena along time. Unfortunately, two main challenges exist with frequent pattern mining in time series databases. The first challenge is the combinatorial explosion of too many possible combinations for frequent patterns with their detailed descriptions, and the second one is to determine frequent patterns truly meaningful and relevant to the users. In this paper, we propose a tree-based frequent temporal inter-object pattern mining algorithm to cope with these two challenges in a level-wise bottom-up approach. In comparison with the existing works, our proposed algorithm is more effective and efficient for frequent temporal inter-object patterns which are more informative with explicit and exact temporal information automatically discovered from a time series database. As shown in the experiments on real financial time series, our work has reduced many invalid combinations for frequent patterns and also avoided many irrelevant frequent patterns returned to the users.
© 2015 Published by VNU Journal of Science.
Manuscript communication: received 15 December 2013, revised 06 December 2014, accepted 19 January 2015 Corresponding author: Vo Thi Ngoc Chau, chauvtn@cse.hcmut.edu.vn
Keywords: Frequent Temporal Inter-Object Pattern, Temporal Pattern Tree, Temporal Pattern Mining, Support Count, Time Series Mining, Time Series Rule Mining.
third challenging problem, one of the ten
1. Introduction
An increasing popularity of time series nowadays exists in many domains such as finance, medicine, geology, meteorology, etc. The resulting time series databases possess knowledge that might be useful and valuable for users to get more understanding about behavioral activities and changes of the objects and phenomena of interest. Thus, time series
mining is an important task. Indeed, it is the
challenging problems in data mining research pointed out in [30]. In addition, [10] has shown this research area has been very active so far. Among time series mining tasks, rule mining is a meaningful but tough mining task shown in [25]. This task is performed with a process mainly including two main phases: mining frequent temporal patterns and deriving temporal rules representing temporal associations between those patterns. In this paper, our work focuses on the first phase for
frequent temporal patterns.
N.T. Vu et al. / VNU Journal of Science: Comp. Science & Com. Eng., Vol. 31, No. 1 (2015) 1-21 2
At present, we are aware of many existing by a minimum support count value. These works related to the frequent temporal pattern semantics-based temporal patterns are mining task on time series. Some that can be semantically abstracted from one or many
listed are [3, 4, 5, 9, 14, 15, 16, 18, 19, 20, 26,
27, 29]. Firstly in an overall view about these
different time series, each of which corresponds
to a time-ordered sequence of some repeating
related works, it is realized that patterns are behavioral activities of some objects or often different from work to work and phenomena of interest whose characteristic has discovered from many various time series been observed and recorded over the time in its datasets. In a few works, the sizes and shapes of respective time series. It is also necessary to patterns are fixed, and time gaps in patterns are distinguish our so-called frequent temporal pre-specified by users. In contrast, our work patterns from motifs which are repeating
would like to discover patterns of interest that
can be of any shapes with any sizes and with
continuous subsequences in an individual time
series. In contrast, a frequent temporal pattern
any time gaps able to be automatically derived being considered might contain various from time series. Secondly, there is neither data repeating meaningful continuous subsequences benchmarking nor standardized definition of the with many different temporal relationships
frequent temporal pattern mining problem on
time series. Indeed, whenever we get a mention
automatically discovered from one or many
different time series in the time series database.
of frequent pattern mining, market basket As for the second extension, we have analysis appears to be a marvelous example of reconsidered our tree-based algorithm
the traditional association rule mining problem.
Such an example is not available in the time
employing appropriate data structures such as
tree and hash table. The modified version of
series mining research area for frequent this algorithm is defined with a keen sense of
temporal patterns. Thirdly, two main challenges that need to be resolved for frequent pattern
mining in time series databases include the
reducing the number of invalid combinations generated and checked for frequent temporal
patterns. It is also capable of removing many
problem of combinatorial explosion of too irrelevant frequent patterns for the users.
many possible combinations for frequent patterns with their detailed descriptions and the problem of discovering frequent patterns truly meaningful and relevant to the users.
Based on the aforementioned motivations,
As shown in the experiments on real financial time series, our proposed algorithm is more efficient to deal with the combinatorial explosion problem. In comparison with the
existing works, our work is useful for frequent
we propose a tree-based frequent temporal temporal inter-object patterns more informative inter-object pattern mining algorithm in a level- with explicit and exact temporal information wise bottom-up approach as an extended which is automatically discovered from a time
version of the tree-based algorithm in [20]. The first extension is a generalized frequent temporal pattern mining process on time series databases with an adapted frequent temporal pattern template. As a result, a frequent temporal pattern in our work is semantics-based temporal pattern that occurs as often as or more
often than expectation from users determined
series database.
The rest of our paper is structured as follows. Section II provides an overall view of the related works to point out the differences between those works and ours. In section III, we introduce a generalized frequent temporal pattern mining process on time series databases
where our proposed algorithm is included. In
3 N.T. Vu et al. / VNU Journal of Science: Comp. Science & Com. Eng., Vol. 31, No. 1 (2015) 1-21
section IV, we propose an efficient tree-based frequent temporal inter-object pattern mining algorithm and its evaluation with many experiments is presented and discussed in section V. Finally, section VI concludes our work and states several future works.
2. Related Works
In this section, some related works [3-7, 9, 14-22, 24, 26-29] are examined in comparison with our work. Among these related works, [3-5, 7, 9, 14-16, 18-20, 22, 26, 27] are proposed for frequent temporal pattern mining in time series, [21, 24, 29] for frequent sequential pattern mining in sequential databases, and [6, 17, 28] for frequent temporal pattern mining in temporal databases.
In the most basic form, motifs can be considered as primitive patterns in time series mining. There exist many approaches to find motifs in time series named a few as [9, 15, 16, 19, 26, 27]. Our work is different from those because the scope of our algorithms does not include the phase of finding primitive patterns that might be concerned with a motif discovery algorithm. We suppose that those primitive patterns are available to our proposed algorithm. As for more complex patterns, [4] has introduced a notion of perception-based pattern in time series mining with a so-called methodology of computing with words and perceptions. [4] reviewed in details such descriptions using sign of derivatives, scaling of trends and shapes, linguistic interpretation of patterns from clustering, a pattern generation grammar, and temporal relationships between patterns. Also towards perception-based time series mining, [14] presented a duration-based linguistic trend summarization of time series using a few features such as the slope of the line, the fairness of the approximation of the original data points by line segments and the
length of a period of time comprising the trend. Differently, our work concentrates on discovering relationships among primitive patterns. It is worth noting that our proposed algorithms are not constrained by the number of pattern types as well as the meanings and shapes of primitive patterns. Moreover, [3] has recently focused on discovering recent temporal patterns from interval-based sequences of temporal abstractions with two temporal relationships: before and co-occur. Mining recent temporal patterns in [3] is one step in learning a classification model for event detection problems. Different from [3], our work belongs to the time series rule mining task. Indeed, we would like to discover more complex frequent temporal patterns in many different time series with more temporal relationships. For more applications, such patterns can be used in other time series mining tasks such as clustering, classification, and prediction in time series. Based on the temporal concepts of duration, coincidence, and partial order in interval time series, [18] defined pattern types from multivariate time series as Tone, Chord, and Phrase. Tones representing durations are labeled time intervals, which are basic primitives. Chords representing coincidence are formed by simultaneously occurring Tones. Phrases are formed by several Chords connected with a partial order which is actually the temporal relationship “before” in Allen’s terms. Support is used as a measure to evaluate discovered patterns. As compared to [18], our work supports more temporal relationships with time information able to be automatically discovered along with frequent temporal inter-object patterns. Not directly proposed for frequent temporal patterns in time series, [22] made use of Allen’s temporal relationships (before, equal, meets, overlaps, during, starts, finishes, etc.) in their so-called temporal abstractions. A temporal abstraction is simply a description of a (set of) time series through sequences of temporal intervals
N.T. Vu et al. / VNU Journal of Science: Comp. Science & Com. Eng., Vol. 31, No. 1 (2015) 1-21 4
corresponding to relevant patterns (i.e. In sequential database mining, [21, 24, 29]
behaviors or properties) detected in their time courses. These temporal abstractions can be combined together to form more complex temporal abstractions also using Allen’s temporal relationships BEFORE, MEETS, OVERLAPS, FINISHED BY, EQUALS, and STARTS. It is realized that temporal abstractions discovered from [22] are temporal patterns rather similar to our frequent temporal inter-object patterns. However, our work supports richer trend-based patterns and also provides a new efficient pattern mining algorithm as compared to [22]. For another form of patterns, [7] aimed to capture the similarities among stock market time series such that their sequence-subsequence relationships are preserved. In particular, [7] identified patterns representing collections of contiguous subsequences which shared the same shape for specific time intervals. Their patterns show pairwise similarities among sequences, called timing patterns using temporal relationships such as begin earlier, end later, and are longer. [7] also defined Support Count and Confidence measures for a relationship but these measures were not employed in any algorithms of their work. As compared to [7], our work supports more temporal relationships with explicit time. More recently, [5] has paid attention to linguistic association rules in time series which are based on fuzzy itemsets stemming from continuous subsequences in time series. Each frequent itemset in [5] can be considered as a frequent pattern discovered in time series. However, there is no consideration for temporal knowledge in their frequent fuzzy itemsets. As
are among many existing works on frequent sequential pattern mining. [24] introduced GSP algorithm to discover generalized sequential patterns in a sequential database using Apriori antimonotonic constraint. Later, [21] proposed PrefixSpan algorithm to avoid the weakness of [24] in scanning the database many times unnecessarily. Indeed, [21] can find frequent sequential patterns without generating any candidate for them. For a comparison, those frequent sequential patterns are not as rich as ours in temporal aspects hidden in time series which include interval-based relationships and their associated time. As for [29], so-called inter-sequence patterns are discovered with two proposed algorithms which are M-Apriori and EISP-Miner. The first algorithm is Apriori-like and not as efficient as the second one which is based on a tree data structure, named ISP-tree. Nevertheless, the capability of both algorithms is limited to a user-specified parameter which is maximum span, called maxspan. It is believed that it is not easy for users to provide a suitable value for this parameter as soon as their sequential database is mined. This might lead to many trial-and-error experiments for maxspan.
In temporal database mining, [6, 17, 28] worked for inter-transaction/inter-object patterns/rules which involved one or many different transactions/objects. Similarly, our discovered frequent temporal patterns are inter-object patterns. Differently, our patterns are mined in the context of time series mining where each component in our patterns is trend-
based with more degrees in change than
for [20], our work is based on their proposed “up/down” or “increasing/decreasing” and
work with several extensions to the process and tree-based algorithm in order to discover frequent temporal inter-object patterns in a time series database more efficiently.
temporal relationships automatically derived are interval-based with more time information than point-based relationships “co-
occur/before/after”.
5 N.T. Vu et al. / VNU Journal of Science: Comp. Science & Com. Eng., Vol. 31, No. 1 (2015) 1-21
To the best of our knowledge, the type of Depicted in Figure 1, the detail about the frequent temporal inter-object patterns defined pattern mining process will be mentioned in our work has not yet been taken into clearly as follows. Our process includes three consideration in the existing works. The phases mainly based on the well-accepted proposed temporal frequent inter-object pattern general knowledge discovery process [12]. mining algorithm on a set of various time series Phase 1 is responsible for preprocessing to
is designed to be a more efficient version of the tree-based algorithm in [20].
3. A Generalized Frequent Temporal Inter-object Pattern Mining Process
In this section, a generalized frequent temporal inter-object pattern mining process on a time series database is figured out to elaborate our solution to discovering so-called frequent temporal inter-object patterns from a given set of different time series. This process is mainly based on the one in [20]. Each time series is considered an object of interest which can be some phenomena or some physical objects in our real life. We refer to a notion of temporal inter-object pattern as temporal relationship among objects being considered. This notion of “inter-object” is somewhat similar to “inter-transaction” in [17, 28] and “inter-sequence” in [29]. However, our work aims to capture more temporal aspects of their relationships so that discovered patterns can be more informative and applicable to decision making support. In addition, interestingness of discovered patterns is measured by means of the degree to which they are frequent in the lifespan of these objects
in regard to a user-specified minimum threshold
prepare for semantics-based time series, phase 2 for the first step to obtain a set of repeating trend-based subsequences, and phase 3 for the primary step to fully discover frequent temporal inter-object patterns. As compared to the process in [20], our generalized process is not specific for the input of the proposed algorithm by relaxing the use of trend-based time series. Instead, so-called semantics-based symbolic time series are used so that users can have more freedom to express the meaning of each component in a resulting frequent pattern via the semantic symbols used for time series transformation in phase 1.
3.1. Phase 1 for Semantics-based Symbolic Time Series
The input of this phase is also the one of our work, which consists of a set of raw time series of the same length for simplicity. Formally, each time series TS is defined as TS = (v1, v2, …, vn). TS is a so-called univariate time series in an n-dimension space. The length of TS is n. v1, v2, …, and vn are time-ordered real numbers. Indices 1, 2, …, n correspond to points in time in our real world on a regular basis. Regarding semantics, time series is understood as the recording of a quantitative characteristic of an object or phenomenon of
called min_sup. This is because we use Support interest observed regularly over the time. Count as an objective measure with the
meaning intact in [12].
G
N.T. Vu et al. / VNU Journal of Science: Comp. Science & Com. Eng., Vol. 31, No. 1 (2015) 1-21 6
Figure 1. A generalized frequent temporal inter-object pattern mining process on a time series database.
As previously mentioned, we have The input of phase 2 is exactly the output of generalized the pattern mining process phase 1 which consists of one or many introduced in [20] for more semantics in semantics-based symbolic time series. The
resulting frequent patterns. Thus, in this paper, we do not restrict the meaning of individual
components in discovered frequent patterns to
main objective of phase 2 is to find repeating subsequences in the input symbolic time series.
Such subsequences are indeed motifs hidden in
behavioral changes of objects and the degree to these time series. Regarding semantics, motifs
which they change. Instead, we enable so-called semantics-based symbolic time series by means
of any transformation technique on time series.
themselves are frequent parts in time series. As compared to discrete point-based events in [17,
28], motifs in our work are suitable for the
For instance, each time series can be applications where the time spans of an event
transformed into a trend-based time series using
short-term and long-term moving averages in
are significant to user’s problems. For example,
it is more informative for us to know that a
[31] or into a symbolic time series using SAX stock keeps strongly increasing three technique in [16]. consecutive days denoted by BBB from
The output of this phase is a set of semantics-based time series each of which is
formally defined as (s1, s2, …, sn) where si∈Σ for i = 1..n where Σ is a discrete set of semantic
symbols derived by a corresponding transformation technique. For the technique in [31], Σ = {A, B, C, D, E, F} where A represents the time series in a weak increasing trend; B in a strong increasing trend; C starting a strong increasing trend; D starting a weak increasing trend; E in a strong decreasing trend; and F in a weak decreasing trend. For the technique in [16], Σ is the word book. If two breakpoints are used, Σ = {a, b, c} where a represents subsequences with high values, b with average values, and c with low values.
3.2. Phase 2 for Repeating Subsequences
Monday to Wednesday in comparison with a simple fact such that a stock increases. As of this moment, there are different approaches to the motif discovery task on time series as proposed in [9, 15, 16, 19, 26, 27]. This task is out of the scope of our work. In our work, we implemented a simple brute force algorithm to extract repeating subsequences which are motifs along with their counts, each of which is the number of occurrences of the subsequence in its corresponding symbolic time series. Because of our interest in frequent patterns, we consider repeating subsequences with at least two occurrences. In short, the output of this phase is a set of repeating subsequences with at least two occurrences that might stem from
different objects.
7 N.T. Vu et al. / VNU Journal of Science: Comp. Science & Com. Eng., Vol. 31, No. 1 (2015) 1-21
3.3. Phase 3 for Frequent Temporal Inter-object Patterns
Similar to phase 2, phase 3 has the input which is the output of the previous phase, a set of repeating subsequences. In addition, phase 3 also needs a minimum support count threshold, min_sup, from users to evaluate the output returned to users. As compared to [29], min_sup is a single parameter whose value is provided by the users along with the input set of time series in our process. Using min_sup and the input, phase 3 first obtains a set of primitive patterns, named L1, which includes only repeating subsequences with the counts equal or greater than min_sup. All elements in L1 are called frequent temporal inter-object patterns at level 1. At this level, there is just one object involved in each frequent pattern. Differently, level is used to refer to the number of components in a pattern which will be detailed below, not to the number of objects involved in a pattern. Secondly, phase 3 proceeds with a frequent temporal inter-object pattern mining algorithm to discover and return to users a full set of frequent temporal inter-object patterns in a set of various time series. The rest of this subsection will define a notion of frequent temporal inter-object pattern and in section 4, we will propose an extended version of the tree-based frequent temporal inter-object pattern mining algorithm that makes the frequent temporal inter-object pattern mining process more effective and efficient.
In general, we formally define a frequent temporal inter-object pattern at level k for k>1 in the following form: m1-m1.ID m2-m2.ID….mk-1-mk-1.ID< operator typek-1 : delta timek-1> mk-mk.ID.
In this form, m1, m2, …, mk-1, and mk are primitive patterns in L1 which might come from
different objects whose identifiers are m1.ID,
m2.ID, …, mk-1.ID, and mk.ID, respectively. Regarding relationships between the components of a pattern at level k, operator type1, …, operator typek-1 are Allen’s temporal operators. There are thirteen Allen’s temporal operators in [1] well-known to express interval-based relationships along the time, including precedes (p), meets (m), overlaps (o), Finished by (F), contains (D), starts (s), equals (e), Started (S), during (d), finishes (f), overlapped by (O), met by (M), preceded by (P). For their converse relationships, our work used seven Allen’s temporal operators (p, m, o, F, D, s, e) to capture temporal associations between subsequences from different objects in phase 3. That is, operator type1, …, operator typek-1 are in {p, m, o, F, D, s, e}. Moreover, we use delta time1, …, delta timek-1 to keep time information of the corresponding relationships. Regarding semantics, intuitively speaking, a frequent temporal inter-object pattern at level k for k>1 fully presents the relationships between the frequent parts of different objects of interest over the time. Hence, we believe that unlike some other related works [7, 11, 17, 18], our patterns are in a richer and more understandable form and in addition, our pattern mining algorithm is enabled to automatically discover all such frequent temporal inter-object patterns with no limitation on their relationship types and time information.
Example 1: Let us consider a frequent temporal pattern on a single object NY using the transformation technique in [31]: AA-NYBBB-NY {0, 10, 20}. This pattern enables us to know that after in a two-day weak increasing trend, NY has a three-day strong increasing trend and this fact repeats three times at positions 0, 10, and 20 in the lifetime of NY.
Its illustration is given in Figure 2.
N.T. Vu et al. / VNU Journal of Science: Comp. Science & Com. Eng., Vol. 31, No. 1 (2015) 1-21 8
Figure 2. Illustration of a frequent temporal pattern on a single object NY.
Figure 3. Illustration of a frequent temporal inter-object pattern on two objects: NY and SH.
Example 2: Let us consider a frequent temporal inter-object pattern on two objects NY and SH also using the transformation technique in [31]: AA-NYAA-SH {0, 10}. This pattern, whose illustration is presented in Figure 3, involves two objects NY and SH and presents their temporal relationship along the time. In particular, we can state about NY and SH that NY has a two-day weak increasing trend and in the same duration of time, SH does too. This fact occurs twice at positions 0 and 10 in their lifetime. It is also worth noting that we absolutely do not know whether or not NY influences SH or vice versa in real life unless
their relationships are analyzed in some depth.
algorithms were defined: brute-force and tree-based. The brute-force algorithm provides a baseline for correctness checking and the tree-based one helps speeding up the pattern mining process in the spirit of FP-Growth algorithm [13]. The two algorithms followed the level-wise bottom-up approach.
Based on [20], we extend the tree-based algorithm to a new version that enables us to deal with the combinatorial explosion problem by using an additional hash table for a detection and elimination of irrelevant frequent patterns. In particular, the modified tree-based algorithm is capable of removing the instances of potential candidates pertaining to one single pattern with overlapping parts. In the following subsections, the tree-based algorithmis detailed.
4.1.A Temporal Pattern Tree
In this paper, we remain a so-called temporal pattern tree in [20]. Nevertheless, for being self-contained, the description of a
temporal pattern tree is presented as follows.
Nonetheless, such patterns provide us with
objective data-driven evidence on the
relationships among objects of interest so that
Figure 4. The structure of a node in the temporal pattern tree.
we can make other further thorough A temporal pattern tree (TP-tree) is a tree investigations into these objects and their that has n nodes of the same structure as shown
surrounding environment.
4. The Proposed Tree-based Frequent Temporal Inter-object Pattern Mining Algorithm on Time Series Databases
As noted in [20], the type of knowledge we aim to discover from time series has not yet
been considered. Hence, in [20], two mining
in Figure 4.
A node structure of a node being considered in TP-tree is composed of the following fields:
- ParentNode: a pointer that points to a parent node of the current node.
- OperatorType: an Allen’s temporal operator in the form of

, ~~, ~~