Browsing by Author "Hong, Tzung-Pei"

Now showing 1 - 12 of 12

A GA-based approach for finding appropriate granularity levels of patterns from time series
(2016)
Chen, Chun-Hao
;
Tseng, Vincent S.
;
Yu, Hsieh-Hui
;
Hong, Tzung-Pei
;
Yen, Neil Y.
In our previous approach, we proposed an algorithm for finding segments and patterns simultaneously from a given time series. In that approach, because patterns were derived through clustering techniques, the number of clusters was hard to be setting. In other words, the granularity of derived patterns was not taken into consideration. Hence, an approach for deriving appropriate granularity levels of patterns is proposed in this paper. The cut points of a time series are first encoded into a chromosome. Each two adjacent cut points represents a segment. The segments in a chromosome are then divided into groups using the cluster affinity search technique with a similarity matrix and an affinity threshold. With the affinity threshold, patterns with the desired granularity level can be derived. Experiments on a real dataset are also conducted to demonstrate the effectiveness of the proposed approach.
An efficient bit-based feature selection method
(2008-05-04)
Chen, Wei-Chou
;
Tseng, Shian-Shyong
;
Hong, Tzung-Pei
;
資訊工程學系
;
Department of Computer Science
Feature selection is about finding useful (relevant) features to describe an application domain. Selecting relevant and enough features to effectively represent and index the given dataset is an important task to solve the classification and clustering problems intelligently. This task is, however, quite difficult to carry out since it usually needs a very time-consuming search to get the features desired. This paper proposes a bit-based feature selection method to find the smallest feature set to represent the indexes of a given dataset. The proposed approach originates from the bitmap indexing and rough set techniques. It consists of two-phases. In the first phase, the given dataset is transformed into a bitmap indexing matrix with some additional data information. In the second phase, a set of relevant and enough features are selected and used to represent the classification indexes of the given dataset. After the relevant and enough features are selected, they can be judged by the domain expertise and the final feature set of the given dataset is thus proposed. Finally, the experimental results on different data sets also show the efficiency and accuracy of the proposed approach. (c) 2007 Elsevier Ltd. All rights reserved.
An incremental mining algorithm for maintaining sequential patterns using pre-large sequences
(2011-06-01)
Hong, Tzung-Pei
;
Wang, Ching-Yao
;
Tseng, Shian-Shyong
;
資訊工程學系
;
Department of Computer Science
Mining useful information and helpful knowledge from large databases has evolved into an important research area in recent years. Among the classes of knowledge derived, finding sequential patterns in temporal transaction databases is very important since it can help model customer behavior. In the past, researchers usually assumed databases were static to simplify data-mining problems. In real-world applications, new transactions may be added into databases frequently. Designing an efficient and effective mining algorithm that can maintain sequential patterns as a database grows is thus important. In this paper, we propose a novel incremental mining algorithm for maintaining sequential patterns based on the concept of pre-large sequences to reduce the need for rescanning original databases. Pre-large sequences are defined by a lower support threshold and an upper support threshold that act as gaps to avoid the movements of sequences directly from large to small and vice versa. The proposed algorithm does not require rescanning original databases until the accumulative amount of newly added customer sequences exceeds a safety bound, which depends on database size. Thus, as databases grow larger, the numbers of new transactions allowed before database rescanning is required also grow. The proposed approach thus becomes increasingly efficient as databases grow. (C) 2010 Elsevier Ltd. All rights reserved.
Efficient algorithms for mining high-utility itemsets in uncertain databases
(2016-03-15)
Lin, Jerry Chun-Wei
;
Gan, Wensheng
;
Fournier-Viger, Philippe
;
Hong, Tzung-Pei
;
Tseng, Vincent S.
High-utility itemset mining (HUIM) is a useful set of techniques for discovering patterns in transaction databases, which considers both quantity and profit of items. However, most algorithms for mining high utility itemsets (HUIs) assume that the information stored in databases is precise, i.e., that there is no uncertainty. But in many real-life applications, an item or itemset is not only present or absent in transactions but is also associated with an existence probability. This is especially the case for data collected experimentally or using noisy sensors. In the past, many algorithms were respectively proposed to effectively mine frequent itemsets in uncertain databases. But mining HUIs in an uncertain database has not yet been proposed, although uncertainty is commonly seen in real-world applications. In this paper, a novel framework, named potential high-utility itemset mining (PHUIM) in uncertain databases, is proposed to efficiently discover not only the itemsets with high utilities but also the itemsets with high existence probabilities in an uncertain database based on the tuple uncertainty model. The PHUI-UP algorithm (potential high-utility itemsets upper-bound-based mining algorithm) is first presented to mine potential high-utility itemsets (PHUIs) using a level-wise search. Since PHUI-UP adopts a generate-and test approach to mine PHUIs, it suffers from the problem of repeatedly scanning the database. To address this issue, a second algorithm named PHUI-List (potential high-utility itemsets PU-list-based mining algorithm) is also proposed. This latter directly mines PHUIs without generating candidates, thanks to a novel probability-utility-list (PU-list) structure, thus greatly improving the scalability of PHUI mining. Substantial experiments were conducted on both real-life and synthetic datasets to assess the performance of the two designed algorithms in terms of runtime, number of patterns, memory consumption, and scalability. (C) 2015 Elsevier B.V. All rights reserved.
Efficient Mining of Uncertain Data for High-Utility Itemsets
(2016)
Lin, Jerry Chun-Wei
;
Gan, Wensheng
;
Fournier-Viger, Philippe
;
Hong, Tzung-Pei
;
Tseng, Vincent S.
High-utility itemset mining (HUIM) is emerging as an important research topic in data mining. Most algorithms for HUIM can only handle precise data, however, uncertainty that are embedded in big data which collected from experimental measurements or noisy sensors in real-life applications. In this paper, an efficient algorithm, namely Mining Uncertain data for High-Utility Itemsets (MUHUI), is proposed to efficiently discover potential high-utility itemsets (PHUIs) from uncertain data. Based on the probability-utility-list (PU-list) structure, the MUHUI algorithm directly mine PHUIs without candidate generation and can reduce the construction of PU-lists for numerous unpromising itemsets by using several efficient pruning strategies, thus greatly improving the mining performance. Extensive experiments both on real-life and synthetic datasets proved that the proposed algorithm significantly outperforms the state-of-the-art PHUI-List algorithm in terms of efficiency and scalability, especially, the MUHUI algorithm scales well on large-scale uncertain datasets for mining PHUIs.
Efficiently mining uncertain high-utility itemsets
(2017-06-01)
Lin, Jerry Chun-Wei
;
Gan, Wensheng
;
Fournier-Viger, Philippe
;
Hong, Tzung-Pei
;
Tseng, Vincent S.
Data mining consists of deriving implicit, potentially meaningful and useful knowledge from databases such as information about the most profitable items. High-utility itemset mining (HUIM) has thus emerged as an important research topic in data mining. But most HUIM algorithms can only handle precise data, although big data collected in real-life applications using experimental measurements or noisy sensors is often uncertain. In this paper, an efficient algorithm, named Mining Uncertain High-Utility Itemsets (MUHUI), is proposed to efficiently discover potential high-utility itemsets (PHUIs) in uncertain data. Based on the probability-utility-list (PU-list) structure, the MUHUI algorithm directly mines PHUIs without generating candidates, and can avoid constructing PU-lists for numerous unpromising itemsets by applying several efficient pruning strategies, which greatly improve its performance. Extensive experiments conducted on both real-life and synthetic datasets show that the proposed algorithm significantly outperforms the state-of-the-art PHUI-List algorithm in terms of efficiency and scalability, and that the proposed MUHUI algorithm scales well when mining PHUIs in large-scale uncertain datasets.
Fast algorithms for mining high-utility itemsets with various discount strategies
(2016-04)
Lin, Jerry Chun-Wei
;
Gan, Wensheng
;
Fournier-Viger, Philippe
;
Hong, Tzung-Pei
;
Tseng, Vincent S.
In recent years, mining high-utility itemsets (HUIs) has emerged as a key topic in data mining. It consists of discovering sets of items generating a high profit in a transactional database by considering both purchase quantities and unit profits of items. Many algorithms have been proposed for this task. However, most of them assume the unrealistic assumption that unit profits of items remain unchanged over time. But in real-life, the profit of an item or itemset varies as a function of cost prices, sales prices and sale strategies. Recently, a three-phase algorithm has been proposed to mine HUIs, while considering that each item may have different discount strategies. However, the complete set of HUIs cannot be retrieved based on the traditional TWU model with its defined discount strategies. Moreover, it suffers from the well-known drawbacks of Apriori-based algorithms such as maintaining a huge amount of candidates in memory and repeatedly performing time-consuming database scans. In this paper, a HUI-DTP algorithm for mining HUIs when considering discount strategies of items is introduced. The HUI-DTP is designed as a two-phase algorithm to mine the complete set of HUIs based on a novel downward closure property and a vertical TID-list structure. Furthermore, the HUI-DMiner is an algorithm relying on a compact data structure (Positive-and-Negative Utility-list, PNU-list) and properties of two new pruning strategies to efficiently discover HUIs without candidate generation, while considerably reducing the size of the search space. Moreover, a strategy named Estimated Utility Co-occurrence Strategy which stores the relationships between 2-itemsets is also applied in the improved HUI-DEMiner algorithm to speed up computation. An extensive experimental study carried on several real-life datasets shows that the proposed algorithms outperform the previous.best algorithm in terms of runtime, memory consumption and scalability. (C) 2016 Elsevier Ltd. All rights reserved.
HEWIN: HIGH EXPECTED WEIGHTED ITEMSET MINING IN UNCERTAIN DATABASES
(2015-01-01)
Lin, Jerry Chun-Wei
;
Gan, Wensheng
;
Hong, Tzung-Pei
;
Tseng, Vincent S.
;
資訊工程學系
In recent years, many algorithms have been proposed to discover frequent itemsets over uncertian databases or mine weighted based frequent itemsets from precisely binary databases. None of the above algorithms have been, however, designed to discover interesting patterns by considering both weight and data uncertainty constraints. In this paper, a novel knowledge called high expected weighted itemsets (HEWIs) is designed to reveal more useful and meaningful information by considering both the weight and existential probability constraints over an uncertain database. A two-phase HEWI-UTP algorithm is developed to overestimate the high upper-bound expected-weighted itemsets (HUBEWIs) based on the developed high upper-bound expected weighted downward closure property, which can be used to reduce the search space for discovering HEWIs. An extensive experimental study carried on several real-life and synthetic datasets shows the performance of the proposed algorithm.
Mining High-Utility Itemsets with Various Discount Strategies
(2015)
Lin, Jerry Chun-Wei
;
Gan, Wensheng
;
Fournier-Viger, Philippe
;
Hong, Tzung-Pei
;
Tseng, Vincent S.
In recent years, mining high-utility itemsets (HUIs) has become as a key topic in data mining. However, most of the developed algorithms assume the unrealistic situations that unit profits of items remain unchanged over time. But in real-life situations, the profit of an item or itemset varies as a function of cost prices, sales prices and sales strategies. In this paper, a novel framework for mining HUIs with two algorithms under various Discount strategies (HUID) are introduced. HUID-tp is based on various discount strategies and a novel downward closure property to mine the complete set of HUIs. HUID-Miner is an algorithm relying on a compact data structure (Positive-and-Negative Utility-list, PNU-list) and new pruning strategies to efficiently discover HUIs without candidate generation, while considerably reducing the size of the search space. Furthermore, a strategy named Estimated Utility Co-occurrence Strategy which stores the relationships between 2-itemsets is also adopted in the proposed improvement HUID-EMiner algorithm to speed up computation. An extensive experimental study carried on several real-life datasets shows the performance of the proposed algorithms.
Online generation of association rules under multi-dimensional consideration based on negative-border
(2007-01-01)
Wang, Ching-Yao
;
Tseng, Shian-Shyong
;
Hong, Tzung-Pei
;
Chu, Yian-Shu
;
資訊工程學系
Recently, some researchers have developed incremental and online mining approaches to maintain association rules without having to re-process the entire database whenever the database is updated or user specified thresholds are changed. However, they usually can not flexibly obtain association rules or patterns from portions of data, consider problems with different aspects, or provide online decision support for users. We earlier developed an online mining approach for generation of association rules under multidimensional consideration. The multidimensional online mining approach may, however, get loose upper-bound support of candidate itemsets and thus cause excessive I/O and computation costs. In this paper, we attempt to apply the concept of a negative border to enlarge the mining information in the multidimensional pattern relation to help get tighter upper-bound, and thus reduce the number of candidate itemsets to consider. Based oh the extended multidimensional pattern relation, a corresponding online mining approach called Negative-Border Online Mining (NOM) is proposed to efficiently and effectively utilize the information of negative itemset in the negative border. Experiments for heterogeneous datasets are also performed to show the effectiveness of the proposed approach.
Weighted frequent itemset mining over uncertain databases
(2016-01-01)
Lin, Jerry Chun-Wei
;
Gan, Wensheng
;
Fournier-Viger, Philippe
;
Hong, Tzung-Pei
;
Tseng, Vincent S.
Frequent itemset mining (FIM) is a fundamental research topic, which consists of discovering useful and meaningful relationships between items in transaction databases. However, FIM suffers from two important limitations. First, it assumes that all items have the same importance. Second, it ignores the fact that data collected in a real-life environment is often inaccurate, imprecise, or incomplete. To address these issues and mine more useful and meaningful knowledge, the problems of weighted and uncertain itemset mining have been respectively proposed, where a user may respectively assign weights to items to specify their relative importance, and specify existential probabilities to represent uncertainty in transactions. However, no work has addressed both of these issues at the same time. In this paper, we address this important research problem by designing a new type of patterns named high expected weighted itemset (HEWI) and the HEWI-Uapriori algorithm to efficiently discover HEWIs. The HEWI-Uapriori finds HEWIs using an Apriori-like two-phase approach. The algorithm introduces a property named high upper-bound expected weighted downward closure (HUBEWDC) to early prune the search space and unpromising itemsets. Substantial experiments on real-life and synthetic datasets are conducted to evaluate the performance of the proposed algorithm in terms of runtime, memory consumption, and number of patterns found. Results show that the proposed algorithm has excellent performance and scalability compared with traditional methods for weighted-itemset mining and uncertain itemset mining.
Weighted frequent itemset mining over uncertain databases
(2016-01)
Lin, Jerry Chun-Wei
;
Gan, Wensheng
;
Fournier-Viger, Philippe
;
Hong, Tzung-Pei
;
Tseng, Vincent S.
Frequent itemset mining (FIM) is a fundamental research topic, which consists of discovering useful and meaningful relationships between items in transaction databases. However, FIM suffers from two important limitations. First, it assumes that all items have the same importance. Second, it ignores the fact that data collected in a real-life environment is often inaccurate, imprecise, or incomplete. To address these issues and mine more useful and meaningful knowledge, the problems of weighted and uncertain itemset mining have been respectively proposed, where a user may respectively assign weights to items to specify their relative importance, and specify existential probabilities to represent uncertainty in transactions. However, no work has addressed both of these issues at the same time. In this paper, we address this important research problem by designing a new type of patterns named high expected weighted itemset (HEWI) and the HEWI-Uapriori algorithm to efficiently discover HEWIs. The HEWI-Uapriori finds HEWIs using an Apriori-like two-phase approach. The algorithm introduces a property named high upper-bound expected weighted downward closure (HUBEWDC) to early prune the search space and unpromising itemsets. Substantial experiments on real-life and synthetic datasets are conducted to evaluate the performance of the proposed algorithm in terms of runtime, memory consumption, and number of patterns found. Results show that the proposed algorithm has excellent performance and scalability compared with traditional methods for weighted-itemset mining and uncertain itemset mining.