Browsing by Author "Tseng, Vincent S."

Now showing 1 - 20 of 59

A Big Data Analytical Framework for Sports Behavior Mining and Personalized Health Services
(2017-01-01)
Tseng, Vincent S.
;
Chou, Chih-Hsin
;
Yang, Kai-Qi
;
Tseng, Jerry C. C.
;
資訊工程學系
Mobile healthcare has become an important trend in medical and healthcare domains. With the rapid development of wearable and sensing technologies, various health-related information can now be recorded, forming valuable big health data. Physical activities are considered to have a great impact on heart rate, and the analysis of heart rate data now is widely used in medical/healthcare researches. The analysis of exercise records and heart rate data have been used for the research of the exercise intensity in many institutes. Heart rate patterns refers to a symbol of health status of heart, which is based on the current rate, and other physiological parameters. An effective heart rate pattern discovering is very helpful for the healthcare and cardiovascular prevention. In this work, we aim to build a big data analytics framework for sports behavior mining and personalized health services. We analyzed users' exercise data including heart rate and GPS data, which were collected in a practical sports and social platform, to discover users' periodic sports patterns and the trend of heart rate change during exercise. Since the dataset is not only very huge but also growing very quickly, we adopt Apache Spark as the development framework to address this Velocity issue in Big Data. The analytical results can serve as important core for personalized healthcare applications. Moreover, we also group the individual result to discover the clustering result, which can be further applied for advanced healthcare applications.
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.
A novel methodology for stock investment using high utility episode mining and genetic algorithm
(2017-10-01)
Lin, Yu-Feng
;
Huang, Chien-Feng
;
Tseng, Vincent S.
;
資訊工程學系
;
Department of Computer Science
In this paper, we present a novel methodology for stock investment using the technique of high utility episode mining and genetic algorithms. Our objective is to devise a profitable episode-based investment model to reveal hidden events that are associated with high utility in the stock market. The time series data of stock price and the derived technical indicators, including moving average, moving average convergence and divergence, random index and bias index, are used for the construction of episode events. We then employ the genetic algorithm for the simultaneous optimization on parameters and selection of subsets of models. The empirical results show that our proposed method significantly outperforms the state-of-the-art methods in terms of annualized returns of investment and precision. We also provide a set of Z-tests to statistically validate the effectiveness of our proposed method. Based upon the promising results obtained, we expect this novel methodology can advance the research in data mining for computational finance and provide an alternative to stock investment in practice. (C) 2017 Elsevier B.V. All rights reserved.
A Scalable Complex Event Analytical System with Incremental Episode Mining over Data Streams
(2016)
Tseng, Jerry C. C.
;
Gu, Jia-Yuan
;
Tseng, Vincent S.
;
Wang, P. F.
;
Chen, Ching-Yu
Episode pattern mining is a very powerful technique to get high-valued information for people to solve real-life cross-disciplinary problems, such as for the analysis of manufacturing, stock markets, weather records and so on. As data grows, the mining process must be re-triggered again and again to obtain the most updated information. However, periodically re-mining the full dataset is not cost-effective, and thus a number of incremental mining approaches arise for the growing data. However, to our best knowledge, there exist few studies targeted on the problem of incremental episode mining. Moreover, streaming data of complex events is more and more popular because digital sensors always collect data around us in this big data age. Now the challenge is not only mining valuable episode patterns of incremental dataset, but also mining episode patterns over data streams of complex events. To address this research problem, we adopt the Lambda Architecture to design a scalable complex event analytical system that could be used to facilitate the incremental episode mining process over complex event sequences of data streams. Apache Spark and Apache Spark Streaming are applied as the development framework of the batch layer and the speed layer, respectively. To take both the efficiency and accuracy into consideration, we develop a series of modules and three algorithms, namely, batch episode mining, delta episode mining and pattern merging. Results from the experimental validation on a real dataset show that the proposed system carries high scalability and delivers excellent performance in terms of efficiency and accuracy.
Accurate Classification of Diminutive Colorectal Polyps Using Computer-Aided Analysis
(2018-02-01)
Chen, Peng-Jen
;
Lin, Meng-Chiung
;
Lai, Mei-Ju
;
Lin, Jung-Chun
;
Lu, Henry Horng-Shing
BACKGROUND & AIMS: Narrow-band imaging is an image-enhanced form of endoscopy used to observed microstructures and capillaries of the mucosal epithelium which allows for real-time prediction of histologic features of colorectal polyps. However, narrow-band imaging expertise is required to differentiate hyperplastic from neoplastic polyps with high levels of accuracy. We developed and tested a system of computer-aided diagnosis with a deep neural network (DNN-CAD) to analyze narrow-band images of diminutive colorectal polyps. METHODS: We collected 1476 images of neoplastic polyps and 681 images of hyperplastic polyps, obtained from the picture archiving and communications system database in a tertiary hospital in Taiwan. Histologic findings from the polyps were also collected and used as the reference standard. The images and data were used to train the DNN. A test set of images (96 hyperplastic and 188 neoplastic polyps, smaller than 5 mm), obtained from patients who underwent colonoscopies from March 2017 through August 2017, was then used to test the diagnostic ability of the DNN-CAD vs endoscopists (2 expert and 4 novice), who were asked to classify the images of the test set as neoplastic or hyperplastic. Their classifications were compared with findings from histologic analysis. The primary outcome measures were diagnostic accuracy, sensitivity, specificity, positive predictive value (PPV), negative predictive value (NPV), and diagnostic time. The accuracy, sensitivity, specificity, PPV, NPV, and diagnostic time were compared among DNN-CAD, the novice endoscopists, and the expert endoscopists. The study was designed to detect a difference of 10% in accuracy by a 2-sided McNemar test. RESULTS: In the test set, the DNN-CAD identified neoplastic or hyperplastic polyps with 96.3% sensitivity, 78.1% specificity, a PPV of 89.6%, and a NPV of 91.5%. Fewer than half of the novice endoscopists classified polyps with a NPV of 90% (their NPVs ranged from 73.9% to 84.0%). DNN-CAD classified polyps as neoplastic or hyperplastic in 0.45 +/- 0.07 seconds-shorter than the time required by experts (1.54 +/- 1.30 seconds) and nonexperts (1.77 +/- 1.37 seconds) (both P < .001). DNN-CAD classified polyps with perfect intra-observer agreement (kappa score of 1). There was a low level of intra-observer and inter-observer agreement in classification among endoscopists. CONCLUSIONS: We developed a system called DNN-CAD to identify neoplastic or hyperplastic colorectal polyps less than 5 mm. The system classified polyps with a PPV of 89.6%, and a NPV of 91.5%, and in a shorter time than endoscopists. This deep-learning model has potential for not only endoscopic image recognition but for other forms of medical image analysis, including sonography, computed tomography, and magnetic resonance images.
An efficient algorithm for mining high utility itemsets with negative item values in large databases
(2009-09-15)
Chu, Chun-Jung
;
Tseng, Vincent S.
;
Liang, Tyne
;
資訊工程學系
;
Department of Computer Science
Utility itemsets typically consist of items with different values such as utilities, and the aim of utility mining is to identify the itemsets with highest utilities. In the past studies on utility mining, the values of utility itemsets were considered as positive. In some applications, however, an itemset may be associated with negative item values. Hence, discovery of high utility itemsets with negative item values is important for mining interesting patterns like association rules. In this paper, we propose a novel method, namely HUINIV (High Utility Itemsets with Negative Item Values)-Mine, for efficiently and effectively mining high utility itemsets from large databases with consideration of negative item values. To the best of our knowledge, this is the first work that considers the concept of negative item values in utility mining. The novel contribution of HUINIV-Mine is that it can effectively identify high utility itemsets by generating fewer high transaction-weighted utilization itemsets such that the execution time can be reduced substantially in mining the high utility itemsets. In this way, the process of discovering all high utility itemsets with consideration of negative item values can be accomplished effectively with less requirements on memory space and CPU I/O. This meets the critical requirements of temporal and spatial efficiency for mining high utility itemsets with negative item values. Through experimental evaluation, it is shown that HUINIV-Mine outperforms other methods substantially by generating much less candidate itemsets under different experimental conditions. (C) 2009 Elsevier Inc. All rights reserved.
An efficient algorithm for mining temporal high utility itemsets from data streams
(2008-07-01)
Chu, Chun-Jung
;
Tseng, Vincent S.
;
Liang, Tyne
;
資訊工程學系
;
Department of Computer Science
Utility of an itemset is considered as the value of this itemset, and utility mining aims at identifying the itemsets with high utilities. The temporal high utility itemsets are the itemsets whose support is larger than a pre-specified threshold in current time window of the data stream. Discovery of temporal high utility itemsets is an important process for mining interesting patterns like association rules from data streams. In this paper, we propose a novel method, namely THUI (Temporal High Utility Itemsets)-Mine, for mining temporal high utility itemsets from data streams efficiently and effectively. To the best of our knowledge, this is the first work on mining temporal high utility itemsets from data streams. The novel contribution of THUI-Mine is that it can effectively identify the temporal high utility itemsets by generating fewer candidate itemsets such that the execution time can be reduced substantially in mining all high utility itemsets in data streams. In this way, the process of discovering all temporal high utility itemsets under all time windows of data streams can be achieved effectively with less memory space and execution time. This meets the critical requirements on time and space efficiency for mining data streams. Through experimental evaluation, THUI-Mine is shown to significantly outperform other existing methods like Two-Phase algorithm under various experimental conditions. (c) 2007 Elsevier Inc. All rights reserved.
An Efficient Framework for Multirequest Route Planning in Urban Environments
(2017-04-01)
Lu, Eric Hsueh-Chan
;
Chen, Huan-Sheng
;
Tseng, Vincent S.
;
資訊工程學系
;
Department of Computer Science
In recent years, research on location-based services has received a lot of interest, in both industry and academia, due to a wide range of potential applications. Among them, one of the active topic areas is the constraint-based route planning on a point-of-interest (POI) network. Most of the previous studies on this topic primarily consider the geographic properties of the POIs in planning a route. However, we consider that the reason that a user visits a POI is that it provides some services that the user needs. In particular, in urban environments, a POI may provide various kinds of services. Hence, the user's requests should be considered. In this paper, we address a novel problem, which is called multirequest route planning, and propose a novel framework to efficiently plan a route for serving multiple user-specified requests. The framework consists of two major modules: planning module, in which four approaches with pruning and caching strategies are proposed for planning a preliminary route, and refinementmodule, in which two refinement mechanisms are proposed for further enhancing the quality of the route. To our best knowledge, this is the first work on route planning that considers multiple services provided by a POI and multiple requests specified by a user, simultaneously. Finally, we perform an extensive experimental evaluation based on three real-world POI data sets and deliver excellent performance.
An Intelligent Recommender System based on Short-term Risk Prediction for Heart Disease Patients
(2015)
Lafta, Raid
;
Zhang, Ji
;
Tao, Xiaohui
;
Li, Yan
;
Tseng, Vincent S.
In this paper, an intelligent recommender system is developed, which uses an innovative time series prediction algorithm to provide recommendations to heart disease patients in the tele-health environment. Based on analytics of each patient\'s medical tests in records, the system provides the patient with decision support for necessity of medical tests. The experimental results show that the proposed system yields satisfactory accuracy in recommendations. The system also offers a promising way for saving the workload for patients and healthcare practitioners in conducting daily medical tests. The research will help reduce the workload and cost in healthcare and help the healthcare industry transform from the traditional scenario to more a personalized paradigm in a tele-health environment.
An Interactive Healthcare System with Personalized Diet and Exercise Guideline Recommendation
(2015)
Tseng, Jerry C. C.
;
Lin, Bo-Hau
;
Lin, Yu-Feng
;
Day, Miin-Luen
;
Wang, Shyh-Chyi
Recently people pay more and more attention on how to effectively and efficiently analyze the result of regular physical examinations to provide the most helpful information for individual health management. In this paper, we design and develop an interactive system of virtual healthcare assistant to help people, especially for those who suffer from chronic diseases (e.g., metabolic syndrome) to easily understand their health conditions and then well manage it. This system analyzes the result of regular physical examination to evaluate the health risk and provide personalized healthcare services for users in terms of diet and exercise guideline recommendations. We developed some interactive ways for users to easily feedback their vital signs to the system and quickly get the suggestions for health management from the system. Besides the browser-based system, we also developed a mobile App that can regularly remind users to carry out the recommendations, which are provided by the system. To prove the system is feasible in the real-world clinical environment, we also applied the Institutional Review Board (IRB) for a human subject research to validate this system. Other than the functional features, there are also several important non-functional features of the extensibility and the convenience for use. First, we use the physical examination result as the raw data to be analyzed. It\'s very convenient for users with very low cost. Second, the system design is extendable, so it can be easily adjusted to work for any chronic ills, even other kinds of diseases. Moreover, it can be extended to provide other kinds of healthcare guideline recommendations as well. These features constitute the main contributions of this work.
DeF-GPU: Efficient and effective deletions finding in hepatitis B viral genomic DNA using a GPU architecture
(2016-12-01)
Cheng, Chun-Pei
;
Lan, Kuo-Lun
;
Liu, Wen-Chun
;
Chang, Ting-Tsung
;
Tseng, Vincent S.
Hepatitis B viral (HBV) infection is strongly associated with an increased risk of liver diseases like cirrhosis or hepatocellular carcinoma (HCC). Many lines of evidence suggest that deletions occurring in HBV genomic DNA are highly associated with the activity of HBV via the interplay between aberrant viral proteins release and human immune system. Deletions finding on the HBV whole genome sequences is thus a very important issue though there exist underlying the challenges in mining such big and complex biological data. Although some next generation sequencing (NGS) tools are recently designed for identifying structural variations such as insertions or deletions, their validity is generally committed to human sequences study. This design may not be suitable for viruses due to different species. We propose a graphics processing unit (GPU)-based data mining method called DeF-GPU to efficiently and precisely identify HBV deletions from large NGS data, which generally contain millions of reads. To fit the single instruction multiple data instructions, sequencing reads are referred to as multiple data and the deletion finding procedure is referred to as a single instruction. We use Compute Unified Device Architecture (CUDA) to parallelize the procedures, and further validate DeF-GPU on 5 synthetic and 1 real datasets. Our results suggest that DeF-GPU outperforms the existing commonly-used method Pindel and is able to exactly identify the deletions of our ground truth in few seconds. The source code and other related materials are available at https://sourceforge.net/projectsidefgpui. (C) 2016 Elsevier Inc. All rights reserved.
Detecting exact breakpoints of deletions with diversity in hepatitis B viral genomic DNA from next-generation sequencing data
(2017-10-01)
Cheng, Ji-Hong
;
Liu, Wen-Chun
;
Chang, Ting-Tsung
;
Hsieh, Sun-Yuan
;
Tseng, Vincent S.
Many studies have suggested that deletions of Hepatitis B Viral (HBV) are associated with the development of progressive liver diseases, even ultimately resulting in hepatocellular carcinoma (HCC). Among the methods for detecting deletions from next-generation sequencing (NGS) data, few methods considered the characteristics of virus, such as high evolution rates and high divergence among the different HBV genomes. Sequencing high divergence HBV genome sequences using the NGS technology outputs millions of reads. Thus, detecting exact breakpoints of deletions from these big and complex data incurs very high computational cost. We proposed a novel analytical method named VirDelect (Virus Deletion Detect), which uses split read alignment base to detect exact breakpoint and diversity variable to consider high divergence in single-end reads data, such that the computational cost can be reduced without losing accuracy. We use four simulated reads datasets and two real pair-end reads datasets of HBV genome sequence to verify VirDelect accuracy by score functions. The experimental results show that VirDelect outperforms the state-of-the-art method Pindel in terms of accuracy score for all simulated datasets and VirDelect had only two base errors even in real datasets. VirDelect is also shown to deliver high accuracy in analyzing the single-end read data as well as pair-end data. VirDelect can serve as an effective and efficient bioinformatics tool for physiologists with high accuracy and efficient performance and applicable to further analysis with characteristics similar to HBV on genome length and high divergence. The software program of VirDelect can be downloaded at https://sourceforge.net/projects/virdelect/. (C) 2017 Published by Elsevier Inc.
Discovering negative comments by sentiment analysis on web forum
(2019-05-01)
Hsu, Wei-Yun
;
Hsu, Hui-Huang
;
Tseng, Vincent S.
;
資訊工程學系
;
Department of Computer Science
Social media enables people to communicate with each other on the Internet in real-time and rich styles. In other words, there is a lot of information on the social media. If we can extract negative opinions of some brands, enterprises or politics, we can use these opinions to know the market demands and solve problems. In this paper, we propose a novel approach to extract negative-sentiment-oriented features and identify negative opinions in social media with text mining and machine learning techniques, support vector machine and neural network, as well as data collection with Web crawler. The experimental results show that our proposed methods can work effectively.
Early Classification of Multivariate Time Series on Distributed and In-Memory Platforms
(2017-01-01)
Tseng, Vincent S.
;
Huang, Huai-Shuo
;
Huang, Chia-Wei
;
Wang, Ping-Feng
;
Li, Chu-Feng
With the popularity of Internet of Things (IOT) applications, various kinds of active sensors are deployed and multivariate time series datasets are generated rapidly. Early classification of multivariate time series is an emerging topic in data mining due to the wide applications in many domains. The unique part of early classification lies in that it uses only earlier part of time series data to reach classification results with the same accuracy as by methods using complete time series information. Although a number of relevant studies have been presented recently, most of them didn't consider the issues of data scale and execution efficiency simultaneously. The main research issue of this paper falls in how to mine interpretable patterns from multivariate time series data, with which effective classification models can be constructed to ensure the accuracy as well as earliness. To take into account the issues of data scale and execution efficiency simultaneously, we explore distributed in-memory computing techniques and multivariate shapelets-based approaches to construct a Spark-based inmemory mining framework to parallelize the feature extraction process. We implement a framework with Multivariate Shapelets Detection (MSD) method as a based example. Through empirical evaluation on various kinds of sensory datasets, the scalability of the framework is evaluated in terms of efficiency while ensuring the same accuracy and reliability in early classification of multivariate time series. This work is the first one to realize multivariate time series early classification on Spark distributed in-memory computing platform, which can serve as a good base for an extension to other time series classification methods based on shapelet feature extraction.
eDRAM: Effective early disease risk assessment with matrix factorization on a large-scale medical database: A case study on rheumatoid arthritis
(2018-11-26)
Chin, Chu-Yu
;
Hsieh, Sun-Yuan
;
Tseng, Vincent S.
;
資訊科學與工程研究所
;
Institute of Computer Science and Engineering
Recently, a number of analytical approaches for probing medical databases have been developed to assist in disease risk assessment and to determine the association of a clinical condition with others, so that better and intelligent healthcare can be provided. The early assessment of disease risk is an emerging topic in medical informatics. If diseases are detected at an early stage, prognosis can be improved and medical resources can be used more efficiently. For example, if rheumatoid arthritis (RA) is detected at an early stage, appropriate medications can be used to prevent bone deterioration. In early disease risk assessment, finding important risk factors from large-scale medical databases and performing individual disease risk assessment have been challenging tasks. A number of recent studies have considered risk factor analysis approaches, such as association rule mining, sequential rule mining, regression, and expert advice. In this study, to improve disease risk assessment, machine learning and matrix factorization techniques were integrated to discover important and implicit risk factors. A novel framework is proposed that can effectively assess early disease risks, and RA is used as a case study. This framework comprises three main stages: data preprocessing, risk factor optimization, and early disease risk assessment. This is the first study integrating matrix factorization and machine learning for disease risk assessment that is applied to a nation-wide and longitudinal medical diagnostic database. In the experimental evaluations, a cohort established from a large-scale medical database was used that included 1007 RA-diagnosed patients and 921,192 control patients examined over a nine-year follow-up period (2000-2008). The evaluation results demonstrate that the proposed approach is more efficient and stable for disease risk assessment than state-of-the-art methods.
Effective Risk Assessment of Type 2 Diabetes Using Diagnostic Information Retrieval
(2018-01-01)
Chin, Chu-Yu
;
Hsieh, Sun-Yuan
;
Tseng, Vincent S.
;
交大名義發表
;
資訊工程學系
Data in electronic medical records (EMRs) have been widely employed owing to rapid advances in disease assessment technologies. Accordingly, the challenging issue of how to effectively retrieve meaningful data from large-scale medical databases for disease assessment has risen. Furthermore, the manner in which early disease risk assessment models can detect disease symptoms is an issue of concern because early detection leads to early treatment. In this paper, with the aim of detecting diseases sooner and more effectively, a novel early disease risk assessment method is proposed, and type 2 diabetes mellitus (T2DM) is used as a case study. The proposed method is to improve the quality and meaning of diagnostic data using novel features and early strategy. To apply EMRs to construct a relationship matrix between patients and diseases, a retrieval method for generalized diagnostic coded information with extracted occurrence numbers was proposed. In order to identify diseases earlier, a disease risk assessment strategy from 7, 60, and 120 days before the onset of T2DM was established. The experimental results showed that the proposed method to improve disease risk assessment achieved high accuracy in terms of AUC-ROC and AUC-PR values. These results also demonstrate that the EMR information retrieval methods play an important role for disease assessment, and assessments can be performed at an earlier stage based on large-scale diagnostic databases.
Effective Semantic Annotation by Image-to-Concept Distribution Model
(2011-06-01)
Su, Ja-Hwung
;
Chou, Chien-Li
;
Lin, Ching-Yung
;
Tseng, Vincent S.
;
資訊工程學系
Image annotation based on visual features has been a difficult problem due to the diverse associations that exist between visual features and human concepts. In this paper, we propose a novel approach called Annotation by Image-to-Concept Distribution Model (AICDM) for image annotation by discovering the associations between visual features and human concepts from image-to-concept distribution. Through the proposed image-to-concept distribution model, visual features and concepts can be bridged to achieve high-quality image annotation. In this paper, we propose to use "visual features", "models", and "visual genes" which represent analogous functions to the biological chromosome, DNA, and gene. Based on the proposed models using entropy, tf-idf, rules, and SVM, the goal of high-quality image annotation can be achieved effectively. Our empirical evaluation results reveal that the AICDM method can effectively alleviate the problem of visual-to-concept diversity and achieve better annotation results than many existing state-of-the-art approaches in terms of precision and recall.
Effective social content-based collaborative filtering for music recommendation
(2017-01-01)
Su, Ja-Hwung
;
Chang, Wei-Yi
;
Tseng, Vincent S.
;
資訊工程學系
;
Department of Computer Science
Recently, music recommender systems have been proposed to help users obtain the interested music. Traditional recommender systems making attempts to discover users' musical preferences by ratings always suffer from problems of rating diversity, rating sparsity and lack of ratings. These problems result in unsatisfactory recommendation results. To deal with traditional problems, in this paper, we propose a novel music recommender system, namely Multi-modal Music Recommender system (MMR), which integrates social and collaborative information to predict users' preferences. In this work, the playcounts are transformed into collaborative information to cope with problem of lack of rating information, while item tags and artist tags are employed as social information to cope with problems of rating diversity and rating sparsity. Through optimizing the integrated social-and-collaborative information, the users' preferences can be inferred more accurately and efficiently. The experimental results reveal that, three problems can be alleviated significantly and our proposed method outperforms other state-of-the-art recommender systems in terms of RMSE (Root Mean Square Error) and NDCG (Normalized Discount Cumulative Gain).
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 Algorithms for Mining Top-K High Utility Itemsets
(2016-01-01)
Tseng, Vincent S.
;
Wu, Cheng-Wei
;
Fournier-Viger, Philippe
;
Yu, Philip S.
;
資訊工程學系
High utility itemsets (HUIs) mining is an emerging topic in data mining, which refers to discovering all itemsets having a utility meeting a user-specified minimum utility threshold min_util. However, setting min_util appropriately is a difficult problem for users. Generally speaking, finding an appropriate minimum utility threshold by trial and error is a tedious process for users. If min_util is set too low, too many HUIs will be generated, which may cause the mining process to be very inefficient. On the other hand, if min_util is set too high, it is likely that no HUIs will be found. In this paper, we address the above issues by proposing a new framework for top-k high utility itemset mining, where k is the desired number of HUIs to be mined. Two types of efficient algorithms named TKU (mining Top-K Utility itemsets) and TKO (mining Top-K utility itemsets in One phase) are proposed for mining such itemsets without the need to set min_util. We provide a structural comparison of the two algorithms with discussions on their advantages and limitations. Empirical evaluations on both real and synthetic datasets show that the performance of the proposed algorithms is close to that of the optimal case of state-of-the-art utility mining algorithms.