Browsing by Author "Li, Hua-Fu"

Now showing 1 - 14 of 14

A new algorithm for maintaining closed frequent itemsets in data streams by incremental updates
(2006)
Li, Hua-Fu
;
Ho, Chin-Chuan
;
Kuo, Fang-Fei
;
Lee, Suh-Yin
;
資訊工程學系
Online mining of closed frequent itemsets over streaming data is one of the most important issues in mining data streams. In this paper, we propose an efficient one-pass algorithm, NewMoment to maintain the set of closed frequent itemsets in data streams with a transaction-sensitive sliding window. An effective bit-sequence representation of items is used in the proposed algorithm to reduce the time and memory needed to slide the windows. Experiments show that the proposed algorithm not only attain highly accurate mining results, but also run significant faster and consume less memory than existing algorithm Moment for mining closed frequent itemsets over recent data streams.
A SINGLE-SCAN ALGORITHM FOR MINING SEQUENTIAL PATTERNS FROM DATA STREAMS
(2012-03-01)
Li, Hua-Fu
;
Ho, Chin-Chuan
;
Chen, Hsuan-Sheng
;
Lee, Suh-Yin
;
資訊工程學系
Sequential pattern mining (SPAM) is one of the most interesting research issues of data mining. In this paper, a new research problem of mining data streams for sequential patterns is defined. A data stream is an unbound sequence of data elements arriving at a rapid rate. Based on the characteristics of data streams, the problem complexity of mining data streams for sequential patterns is more difficult than that of mining sequential patterns from large static databases. Therefore, mining sequential patterns from data streams is a challenging research issue of data mining and knowledge discovery. Hence, an efficient single-pass algorithm, called IncSparn (Incremental Sequential pattern mining of streaming itemset-sequences), is proposed for discovering sequential patterns from streaming itemset-sequences over extended sliding window models. In the framework of IncSpam algorithm, a new sliding window model, called CSW-BV (Customer Sliding Window with Bit-Vectors), and an extended lexicographic tree-based data structure, called LesSeq-Tree (Lexicographic Sequence Tree), are developed to reduce the time and memory needed to slide the windows over streaming data and maintain all sequential patterns of current sliding windows. Experimental results show that the proposed method is an efficient single-pass algorithm for mining sequential patterns from streaming data.
Detecting changes in user-centered Music Query Streams
(2006)
Li, Hua-Fu
;
Shan, Man-Kwan
;
Lee, Suh-Yin
;
資訊工程學系
;
Department of Computer Science
In this paper, we propose an efficient algorithm, called MQS-change (changes of Music Query. Streams), to detect the changes of maximal melody structures in user-centered music query streams. Two music melody structures (set of chord-sets and string of chord-sets) are maintained and four melody structure changes (positive burst, negative burst, increasing change and decreasing change) are monitored in a new data structure MSC-list (a list of Music Structure Changes). Experiments show that MQS-change algorithm is an online, single-pass approach to detect the changes of music melody structures over continuous music query streams.
DISCOVERING EMERGING MELODY PATTERNS FROM CUSTOMER QUERY DATA STREAMS OF MUSIC SERVICE
(2011)
Li, Hua-Fu
;
Chen, Hsuan-Sheng
;
資訊工程學系
;
Department of Computer Science
Mining melody structure patterns from music query data is one of the most interesting issues of multimedia data mining. In this paper, we introduce a new kind of melody structure pattern, called emerging melody pattern (EMP), for knowledge discovery from music query data streams. EMPs are defined as music data items with melody item-sets whose support increase significantly from one sliding window to another window from streaming melody data sequences. An efficient data mining algorithm, called MEMPA (Mining Emerging Melody Pattern Algorithm), is proposed to discover all EMPs from music query data. In the framework of MEMPA, a prefix tree-based structure, called EMP-tree (Emerging Melody Pattern tree), is developed for storing EMPs effectively from current stream sliding windows. Experimental results show that the proposed algorithm is an efficient method for discovering all EMPs from streaming melody sequences.
DSM-FI: an efficient algorithm for mining frequent itemsets in data streams
(2008-10-01)
Li, Hua-Fu
;
Shan, Man-Kwan
;
Lee, Suh-Yin
;
資訊工程學系
;
Department of Computer Science
Online mining of data streams is an important data mining problem with broad applications. However, it is also a difficult problem since the streaming data possess some inherent characteristics. In this paper, we propose a new single-pass algorithm, called DSM-FI (data stream mining for frequent itemsets), for online incremental mining of frequent itemsets over a continuous stream of online transactions. According to the proposed algorithm, each transaction of the stream is projected into a set of sub-transactions, and these sub-transactions are inserted into a new in-memory summary data structure, called SFI-forest (summary frequent itemset forest) for maintaining the set of all frequent itemsets embedded in the transaction data stream generated so far. Finally, the set of all frequent itemsets is determined from the current SFI-forest. Theoretical analysis and experimental studies show that the proposed DSM-FI algorithm uses stable memory, makes only one pass over an online transactional data stream, and outperforms the existing algorithms of one-pass mining of frequent itemsets.
DSM-PLW: Single-pass mining of path traversal patterns over streaming Web click-sequences
(2006-07-14)
Li, Hua-Fu
;
Lee, Suh-Yin
;
Shan, Man-Kwan
;
資訊工程學系
;
Department of Computer Science
Mining Web click streams is an important data mining problem with broad applications. However, it is also a difficult problem since the streaming data possess some interesting characteristics, such as unknown or unbounded length, possibly a very fast arrival rate, inability to backtrack over previously arrived click-sequences, and a lack of system control over the order in which the data arrive. In this paper, we propose a projection-based, single-pass algorithm, called DSM-PLW (Data Stream Mining for Path traversal patterns in a Landmark Window), for online incremental mining of path traversal patterns over a continuous stream of maximal forward references generated at a rapid rate. According to the algorithm, each maximal forward reference of the stream is projected into a set of reference-suffix maximal forward references, and these reference-suffix maximal forward references are inserted into a new in-memory summary data structure, called SP-forest (Summary Path traversal pattern forest), which is an extended prefix tree-based data structure for storing essential information about frequent reference sequences of the stream so far. The set of all maximal reference sequences is determined from the SP-forest by a depth-first-search mechanism, called MRS-mining (Maximal Reference Sequence mining). Theoretical analysis and experimental studies show that the proposed algorithm has gently growing memory requirements and makes only one pass over the streaming data. (c) 2005 Elsevier B.V. All rights reserved.
Fast and Memory Efficient Mining of High Utility Itemsets in Data Streams
(2008)
Li, Hua-Fu
;
Huang, Hsin-Yun
;
Chen, Yi-Cheng
;
Liu, Yu-Jiun
;
Lee, Suh-Yin
Efficient mining of high utility itemsets has become one of the most interesting data mining tasks with broad applications. In this paper, we proposed two efficient one-pass algorithms, MHUI-BIT and MHUI-TID, for mining high utility itemsets from data streams within a transaction-sensitive sliding window. Two effective representations of item information and an extended lexicographical tree-based summary data structure are developed to improve the efficiency of mining high utility itemsets. Experimental results show that the proposed algorithms outperform than the existing algorithms for mining high utility itemsets from data streams.
Fast and memory efficient mining of high-utility itemsets from data streams: with and without negative item profits
(2011-09-01)
Li, Hua-Fu
;
Huang, Hsin-Yun
;
Lee, Suh-Yin
;
資訊工程學系
;
Department of Computer Science
Mining utility itemsets from data steams is one of the most interesting research issues in data mining and knowledge discovery. In this paper, two efficient sliding window-based algorithms, MHUI-BIT (Mining High-Utility Itemsets based on BITvector) and MHUI-TID (Mining High-Utility Itemsets based on TIDlist), are proposed for mining high-utility itemsets from data streams. Based on the sliding window-based framework of the proposed approaches, two effective representations of item information, Bitvector and TIDlist, and a lexicographical tree-based summary data structure, LexTree-2HTU, are developed to improve the efficiency of discovering high-utility itemsets with positive profits from data streams. Experimental results show that the proposed algorithms outperform than the existing approaches for discovering high-utility itemsets from data streams over sliding windows. Beside, we also propose the adapted approaches of algorithms MHUI-BIT and MHUI-TID in order to handle the case when we are interested in mining utility itemsets with negative item profits. Experiments show that the variants of algorithms MHUI-BIT and MHUI-TID are efficient approaches for mining high-utility itemsets with negative item profits over stream transaction-sensitive sliding windows.
Incremental mining of closed inter-transaction itemsets over data stream sliding windows
(2011-04-01)
Chiu, Shih-Chuan
;
Li, Hua-Fu
;
Huang, Jiun-Long
;
You, Hsin-Han
;
資訊工程學系
Mining inter-transaction association rules is one of the most interesting issues in data mining research. However, in a data stream environment the previous approaches are unable to find the result of the new-incoming data and the original database without re-computing the whole database. In this paper, we propose an incremental mining algorithm, called DSM-CITI (Data Stream Mining for Closed Inter-Transaction Itemsets), for discovering the set of all frequent inter-transaction itemsets from data streams. In the framework of DSM-CITI, a new in-memory summary data structure, ITP-tree, is developed to maintain frequent inter-transaction itemsets. Moreover, algorithm DSM-CITI is able to construct ITP-tree incrementally and uses the property to avoid unnecessary updates. Experimental studies show that the proposed algorithm is efficient and scalable for mining frequent inter-transaction itemsets over stream sliding windows.
Incremental mining of sequential patterns over a stream sliding window
(2006)
Ho, Chin-Chuan
;
Li, Hua-Fu
;
Kuo, Fang-Fei
;
Lee, Suh-Yin
;
資訊工程學系
Incremental mining of sequential patterns from data streams is one of the most challenging problems in mining data streams. However, previous work of mining sequential patterns from data streams is almost focused on mining of patterns from stream of item-sequences, not stream of itemset-sequences. In this paper, we propose an efficient single-pass algorithm, called IncSPAM, to maintain the set of sequential patterns from itemset-sequence streams with a transaction-sensitive sliding window. An effective bit-sequence representation of items is used in the proposed algorithm to reduce the time and memory needed to slide the windows. Experiments show that the proposed IncSPAM algorithm is efficient for mining sequential patterns over data streams.
Mining frequent itemsets over data streams using efficient window sliding techniques
(2009-03-01)
Li, Hua-Fu
;
Lee, Suh-Yin
;
資訊工程學系
;
Department of Computer Science
Online mining of frequent itemsets over it stream sliding window is one of the most important problems in stream data mining with broad applications. It is also a difficult issue since the streaming data possess some challenging characteristics, such as unknown or unbound size, possibly a very fast arrival rate, inability to backtrack over previously arrived transactions, and a lack of system control over the order in which the data arrive. In this paper, we propose an effective bit-sequence based, one-pass algorithm, called MFI-TransSW (Mining Frequent/temsets within a Transaction-sensitive Sliding Window), to mine the set of frequent itemsets from data streams within a transaction-sensitive sliding window which consists of a fixed number of transactions. The proposed MFI-TransSW algorithm consists of three phases: window initialization, window sliding and pattern generation. First, every item of each transaction is encoded in ail effective bit-sequence representation in the window initialization phase. The proposed bit-sequence representation of item is used to reduce the time and memory needed to slide the windows in the following phases. Second, MFI-TransSW uses the left bit-shift technique to slide the windows efficiently in the window sliding phase. Finally, the complete set of frequent itemsets within the current sliding window is generated by it level-wise method in the pattern generation phase. Experimental studies show that the proposed algorithm not only attain highly accurate mining results, but also run significant faster and consume less memory than do existing algorithms for mining frequent itemsets over data streams with a sliding window. Furthermore, based oil the MFI-TransSW framework, ail extended single-pass algorithm, called MFI-TimeSW (Mining Frequent/temsets within a Time-sensitive Sliding Window) is presented to mine the set of frequent itemsets efficiently over time-sensitive sliding windows. (c) 2007 Elsevier Ltd. All rights reserved.
MINING POLYPHONIC REPEATING PATTERNS FROM MUSIC DATA USING BIT-STRING BASED APPROACHES
(2009)
Chiu, Shih-Chuan
;
Shan, Man-Kwan
;
Huang, Jiun-Long
;
Li, Hua-Fu
;
資訊工程學系
Mining repeating patterns from music data is one of the most interesting issues of multimedia data mining. However, less work are proposed for mining polyphonic repeating patterns. Hence, two efficient algorithms, A-PRPD (priori-based Polyphonic Repeating Pattern Discovery) and T-PRPD (Tree-based Polyphonic Repeating Pattern Discovery), are proposed to discover polyphonic repeating patterns from music data. Furthermore, a bit-string method is developed for improving the efficiency of the proposed algorithms. Experimental results show that the proposed algorithms, A-PRPD and T-PRPD, are both effective and efficient methods for mining polyphonic repeating patterns from synthetic music data and real data.
Mining Top-K Path Traversal Patterns over Streaming Web Click-Sequences
(2009-07-01)
Li, Hua-Fu
;
Lee, Suh-Yin
;
資訊工程學系
;
Department of Computer Science
Online, one-pass mining Web click streams poses some interesting computational issues, such as unbounded length of streaming data, possibly very fast arrival rate, and just one scan over previously arrived Web click-sequences. In this paper, we propose a new, single-pass algorithm, called DSM-TKP (Data Stream Mining for Top-K Path traversal patterns), for mining a set of top-k path traversal patterns, where k is the desired number of path traversal patterns to be mined. An effective summary data structure, called TKP-forest (a forest of Top-K Path traversal patterns), is used to maintain the essential information about the top-k path traversal patterns generated so far. Experimental studies show that the proposed DSM-TKP algorithm uses stable memory usage and makes only one pass over the streaming Web click-sequences.
Online mining of recent music query streams
(2006)
Li, Hua-Fu
;
Ho, Chin-Chuan
;
Shan, Man-Kwan
;
Lee, Suh-Yin
;
資訊工程學系
Mining multimedia data is one of the most important issues in data mining. In this paper, we propose an online one-pass algorithm to mine the set of frequent temporal patterns in online music query streams with a sliding window. An effective bit-sequence representation is used to reduce the processing time and memory needed to slide the windows. Experiments show that the proposed algorithm only needs a half of memory requirement of original music query data, and just scans the data once.