Browsing by Author "Wang, Jun-Zhe"

Now showing 1 - 7 of 7

An Efficient Algorithm for High Utility Sequential Pattern Mining
(2014-01-01)
Wang, Jun-Zhe
;
Yang, Zong-Hua
;
Huang, Jiun-Long
;
資訊工程學系
;
Department of Computer Science
High utility sequential pattern mining is to mine sequences with high utility (e. g. profits) but probably with low frequency. In some applications such as marketing analysis, high utility sequential patterns are usually more useful than sequential patterns with high frequency. In this paper, we devise two pruning strategies RSU and PDU, and propose HUS-Span algorithm based on these two pruning strategies to efficiently identify high utility sequential patterns. Experimental results show that HUS-Span algorithm outperforms prior algorithms by pruning more low utility sequences.
Incremental Mining of High Utility Sequential Patterns in Incremental Databases
(2016)
Wang, Jun-Zhe
;
Huang, Jiun-Long
;
資訊工程學系
;
Department of Computer Science
High utility sequential pattern (HUSP) mining is an emerging topic in pattern mining, and only a few algorithms have been proposed to address it. In practice, most sequence databases usually grow over time, and it is inefficient for existing algorithms to mine HUSPs from scratch when databases grow with a small portion of updates. In view of this, we propose the IncUSP-Miner algorithm to mine HUSPs incrementally. Specifically, to avoid redundant computations, we propose a tighter upper bound of the utility of a sequence, called TSU, and then design a novel data structure, called the candidate pattern tree, to maintain the sequences whose TSU values are greater than or equal to the minimum utility threshold. Accordingly, to avoid keeping a huge amount of utility information for each sequence, a set of auxiliary utility information is designed to be stored in each tree node. Moreover, for those nodes whose utilities have to be updated, a strategy is also proposed to reduce the amount of computation, thereby improving the mining efficiency. Experimental results on three real datasets show that IncUSP-Miner is able to efficiently mine HUSPs incrementally.
Incrementally Mining Temporal Patterns in Interval-based Databases
(2014)
Chen, Yi-Cheng
;
Weng, Julia Tzu-Ya
;
Wang, Jun-Zhe
;
Chou, Chien-Li
;
Huang, Jiun-Long
In several applications, sequence databases generally update incrementally with time. Obviously, it is impractical and inefficient to re-mine sequential patterns from scratch every time a number of new sequences are added into the database. Some recent studies have focused on mining sequential patterns in an incremental manner; however, most of them only considered patterns extracted from time point-based data. In this paper, we proposed an efficient algorithm, Inc_TPMiner, to incrementally mine sequential patterns from interval-based data. We also employ some optimization techniques to reduce the search space effectively. The experimental results indicate that Inc_TPMiner is efficient in execution time and possesses scalability. Finally, we show the practicability of incremental mining of interval-based sequential patterns on real datasets.
On efficiently mining high utility sequential patterns
(2016-11)
Wang, Jun-Zhe
;
Huang, Jiun-Long
;
Chen, Yi-Cheng
;
資訊工程學系
;
Department of Computer Science
High utility sequential pattern mining is an emerging topic in pattern mining, which refers to identify sequences with high utilities (e.g., profits) but probably with low frequencies. To identify high utility sequential patterns, due to lack of downward closure property in this problem, most existing algorithms first generate candidate sequences with high sequence-weighted utilities (SWUs), which is an upper bound of the utilities of a sequence and all its supersequences, and then calculate the actual utilities of these candidates. This causes a large number of candidates since SWU is usually much larger than the real utilities of a sequence and all its supersequences. In view of this, we propose two tight utility upper bounds, prefix extension utility and reduced sequence utility, as well as two companion pruning strategies, and devise HUS-Span algorithm to identify high utility sequential patterns by employing these two pruning strategies. In addition, since setting a proper utility threshold is usually difficult for users, we also propose algorithm TKHUS-Span to identify top-k high utility sequential patterns by using these two pruning strategies. Three searching strategies, guided depth-first search (GDFS), best-first search (BFS) and hybrid search of BFS and GDFS, are also proposed to improve the efficiency of TKHUS-Span. Experimental results on some real and synthetic datasets show that HUS-Span and TKHUS-Span with strategy BFS are able to generate less candidate sequences and thus outperform other prior algorithms in terms of mining efficiency.
On Incremental High Utility Sequential Pattern Mining
(2018-07-01)
Wang, Jun-Zhe
;
Huang, Jiun-Long
;
資訊工程學系
;
Department of Computer Science
High utility sequential pattern (HUSP) mining is an emerging topic in pattern mining, and only a few algorithms have been proposed to address it. In practice, most sequence databases usually grow over time, and it is inefficient for existing algorithms to mine HUSPs from scratch when databases grow with a small portion of updates. In view of this, we propose the IncUSP-Miner(+) algorithm to mine HUSPs incrementally. Specifically, to avoid redundant re-computations, we propose a tighter upper bound of the utility of a sequence, called Tight Sequence Utility (TSU), and then we design a novel data structure, called the candidate pattern tree, to buffer the sequences whose TSU values are greater than or equal to the minimum utility threshold in the original database. Accordingly, to avoid keeping a huge amount of utility information for each sequence, a set of concise utility information is designed to be stored in each tree node. To improve the mining efficiency, several strategies are proposed to reduce the amount of computation for utility update and the scopes of database scans. Moreover, several strategies are also proposed to properly adjust the candidate pattern tree for the support of multiple database updates. Experimental results on some real and synthetic datasets show that IncUSP-Miner + is able to efficiently mine HUSPs incrementally.
Team Formation with the Communication Load Constraint in Social Networks
(2014-01-01)
Teng, Yui-Chieh
;
Wang, Jun-Zhe
;
Huang, Jiun-Long
;
資訊工程學系
;
Department of Computer Science
Given a project requiring a set of skills, the team formation problem in social networks aims to find a team that can cover all the required skills and has the minimal communication cost. Previous studies considered the team formation problem with a leader and proposed efficient algorithms to address the problem. However, for large projects, a single leader is not capable of managing a team with a large number of team members. Thus, a number of leaders would be formed and organized into a hierarchy where each leader is responsible for only a limited number of team members. In this paper, we propose the team formation problem with the communication load constraint in social networks. The communication load constraint limits the number of team members a leader communicates with. To solve the problem, we design a two-phase framework. Based on the proposed framework, we first propose algorithm Opt to find an optimal team, under the communication load constraint, with minimal communication cost. For large social networks, we also propose algorithm Approx to find a nearly-optimal team. Experimental results show that algorithm Opt is able to find optimal teams and is more efficient than the brute-force algorithm. In addition, when nearly-optimal teams are acceptable, algorithm Approx is much more scalable than algorithm Opt for large social networks.
VirtualTouch: A Finger Glove to Simulate Touch Screen Commands
(2012)
Wang, Jun-Zhe
;
Wu, Chun-Hao
;
Tseng, Yu-Chee
;
資訊工程學系
;
Department of Computer Science
Touch screens have become more and more popular in many end devices. For example, Windows 7, Android, and iOS have adopted several multi-touch commands in their user interfaces. Although touching the screen of a small device is handy, it is not suitable for larger screen environments. In this paper, we propose a glove-shaped input device that can simulate screen-touching operations by hand gestures without actual need of touching the screen. The glove captures hand gestures and reports the sensing data back to a computer, which interprets the data into touch commands. We have implemented commands such as clicking, dragging, flicking, rotating, scrolling, and zooming, and we verified them on Windows 7 to understand user experiences.