Browsing by Author "Lin, MY"

Now showing 1 - 6 of 6

Efficient mining of sequential patterns with time constraints by delimited pattern growth
(2005-05-01)
Lin, MY
;
Lee, SY
;
資訊工程學系
;
Department of Computer Science
An active research topic in data mining is the discovery of sequential patterns, which finds all frequent subsequences in a sequence database. The generalized sequential pattern (GSP) algorithm was proposed to solve the mining of sequential patterns with time constraints, such as time gaps and sliding time windows. Recent studies indicate that the pattern-growth methodology could speed up sequence mining. However, the capabilities to mine sequential patterns with time constraints were previously available only within the Apriori framework. Therefore, we propose the DELISP (delimited sequential pattern) approach to provide the capabilities within the pattern-growth methodology. DELISP features in reducing the size of projected databases by bounded and windowed projection techniques. Bounded projection keeps only time-gap valid subsequences and windowed projection saves nonredundant subsequences satisfying the sliding time-window constraint. Furthermore, the delimited growth technique directly generates constraint-satisfactory patterns and speeds up the pattern growing process. The comprehensive experiments conducted show that DELISP has good scalability and outperforms the well-known GSP algorithm in the discovery of sequential patterns with time constraints.
Fast discovery of sequential patterns through memory indexing and database partitioning
(2005-01-01)
Lin, MY
;
Lee, SY
;
資訊工程學系
;
Department of Computer Science
Sequential pattern mining is a challenging issue because of the high complexity of temporal pattern discovering from numerous sequences. Current mining approaches either require frequent database scanning or the generation of several intermediate databases. As databases may fit into the ever-increasing main memory, efficient memory-based discovery of sequential patterns is becoming possible. In this paper, we propose a memory indexing approach for fast sequential pattern mining, named MEMISP. During the whole process, MEMISP scans the sequence database only once to read data sequences into memory. The find-then-index technique is recursively used to find the items that constitute a frequent sequence and constructs a compact index set which indicates the set of data sequences for further exploration. As a result of effective index advancing, fewer and shorter data sequences need to be processed in MEMISP as the discovered patterns get longer. Moreover, we can estimate the maximum size of the total memory required, which is independent of the minimum support threshold, in MEMISP. Experimental results indicate that MEMISP outperforms both GSP and PrefixSpan (general version) without the need for either candidate generation or database projection. When the database is too large to fit into memory in a batch, we partition the database, mine patterns in each partition, and validate the true patterns in the second pass of database scanning. Experiments performed on extra-large databases demonstrate the good performance and scalability of MEMISP, even with very low minimum support. Therefore, MEMISP can efficiently mine sequence databases of any size, for any minimum support values.
Incremental update on sequential patterns in large databases
(1998)
Lin, MY
;
Lee, SY
;
資訊科學與工程研究所
;
Institute of Computer Science and Engineering
Mining of sequential patterns in a transactional database is time-consuming due to its complexity. Maintaining present patterns is a non-trivial task after database update, since appended data sequences may invalidate old patterns and create new ones. In contrast to re-mining, the key to improve mining performance in the proposed incremental update algorithm is to effectively utilize the discovered knowledge. By counting over appended data sequences instead of the entire updated database in most cases fast filtering of patterns found in last mining and successive reductions in candidate sequences together make Efficient update on sequential patterns possible.
Incremental update on sequential patterns in large databases by implicit merging and efficient counting
(2004-07-01)
Lin, MY
;
Lee, SY
;
資訊工程學系
;
Department of Computer Science
Current approaches for sequential pattern mining usually assume that the mining is performed in a static sequence database. However, databases are not static due to update so that the discovered patterns might become invalid and new patterns could be created. In addition to higher complexity, the maintenance of sequential patterns is more challenging than that of association rules owing to sequence merging. Sequence merging, which is unique in sequence databases, requires the appended new sequences to be merged with the existing ones if their customer ids are the same. Re-mining of the whole database appears to be inevitable since the information collected in previous discovery will be corrupted by sequence merging. Instead of re-mining, the proposed IncSP (Incremental Sequential Pattern Update) algorithm solves the maintenance problem through effective implicit merging and efficient separate counting over appended sequences. Patterns found previously are incrementally updated rather than re-mined from scratch. Moreover, the technique of early candidate pruning further speeds up the discovery of new patterns. Empirical evaluation using comprehensive synthetic data shows that IncSP is fast and scalable. (C) 2003 Elsevier Ltd. All rights reserved.
Interactive sequence discovery by incremental mining
(2004-10-19)
Lin, MY
;
Lee, SY
;
資訊工程學系
;
Department of Computer Science
Sequential pattern mining has become a challenging task in data mining due to its complexity. Essentially, the mining algorithms discover all the frequent patterns meeting the user specified minimum support threshold. However, it is very unlikely that the user could obtain the satisfactory patterns in just one query. Usually the user must try various support thresholds to mine the database for the final desirable set of patterns. Consequently, the time-consuming mining process has to be repeated several times. However, current approaches are inadequate for such interactive mining due to the long processing time required for each query. In order to reduce the response time for each query during the interactive process, we propose a knowledge base assisted mining algorithm for interactive sequence discovery. The proposed approach utilizes the knowledge acquired from each mining process, accumulates the counting information to facilitate efficient counting of patterns, and speeds up the whole interactive mining process. Furthermore, the knowledge base makes possible the direct generation of new candidate sets and the concurrent support counting of variable sized candidates. Even for some queries, due to the pattern information already kept in the knowledge base, database access is not required at all. The conducted experiments show that our approach outperforms GSP, a state-of-the-art sequential pattern mining algorithm, by several order of magnitudes for interactive sequence discovery. (C) 2003 Elsevier Inc. All rights reserved.
Molecular sublayers beneath the air-sea interface relative to momentum, heat and gas transports
(2003-09-27)
Tsai, WT
;
Chen, SM
;
Lin, MY
;
Hung, LP
;
土木工程學系
Numerical simulations of the wind-driven aqueous turbulent flow and the underlying heat and dissolved gas transports are conducted with sufficiently fine grid resolution to resolve the molecular sublayers immediately beneath the air-water interface. The simulated mean distributions of velocity, temperature and gas concentration all exhibit exponential profiles across the sublayers in accordance with the theoretical postulation of Liu and Businger [1975] which they derived on the basis of the conceptual surface renewal model. The numerical results identify two major coherent renewal processes within the flow: intermittent upwellings induced by uprising horseshoe-like eddies in the well-mixed region, and elongated, high-speed, cool streaks within the sublayer reflecting the cool-skin thermal structure.