Search

From web search and data mining, users’ click and purchase behaviors contain valuable information, thus numerous approaches have been proposed to identify embedded useful knowledge from them. In these real-life situations, each user may perform the same action/event multiple times, and multiple accessed events product different profit. Many utility-oriented data mining approaches thus have been extensively studied. Previous studies have the limitation that the overall utility of traditional pattern is limited since they rarely consider the inherent correlation. For example, from the purchase behavior, the low-utility patterns sometimes with a very high-utility pattern will be considered as a valuable pattern even if this behavior may be not highly correlated. A more intelligent framework that provides non-redundant and correlated behavior based on utility measure is thus desired. In this paper, we first present a novel method to extract non-redundant correlated purchase behaviors considering the utility and correlation factors. The high qualified patterns can be derived with high profit and strong correlation, which can lead to higher recall and reveal better precision. In the proposed projection-based approach, an efficient projection mechanism and a sorted downward closure property are developed to reduce the database size. Several pruning strategies are further developed to efficiently and effectively discover the desired patterns. An extensive experimental study showed that the novel non-redundant correlated high-utility pattern has more effectiveness than the previous knowledge representation. Moreover, the proposed algorithm is efficient in terms of execution time and memory usage. [ABSTRACT FROM AUTHOR]

In the field of data mining, the topic of high-utility itemset mining (HUIM) has recently gained a lot of attention from researchers as it takes many factors into account that are useful for decision-making by retail managers. In the past, many algorithms have been presented for HUIM but most of them suffer from the limitation of using a single minimum utility threshold to identify high-utility itemsets (HUIs). For real-life applications, finding itemsets using a single threshold is inadequate and unfair since each item is different. Hence, the diversity or importance of each item should be considered. This paper proposes a solution to this issue by defining the novel task of HUIM with multiple minimum utility thresholds (named as HUIM-MMU). This task lets users specify a different minimum utility threshold for each item to identify more useful and specific HUIs, which would generate more profits when compared to HUIs discovered based on a single minimum utility threshold. The HUI-MMU algorithm is designed to mine HUIs in a level-wise manner. The sorted downward closure ( SDC ) property and the least minimum utility ( LMU ) concept are developed to avoid a combinatorial explosion for identifying HUIs and to ensure the completeness and correctness of HUI-MMU for discovering HUIs. Meanwhile, two improved algorithms, namely HUI-MMU TID and HUI-MMU TE , are presented based on the TID-index and EUCP strategies. Those strategies can be used to speed up the mining performance to discover HUIs. Substantial experiments on both real-life and synthetic datasets show that the designed algorithms can efficiently and effectively discover the complete set of HUIs in databases by considering multiple minimum utility thresholds. [ABSTRACT FROM AUTHOR]

High utility itemset mining is an emerging data mining task, which consists of discovering highly profitable itemsets (called high utility itemsets) in very large transactional databases. Many algorithms have been proposed to efficiently discover high utility itemsets but most of them assume that items may only have positive unit profits. However, in real-world transactional databases, items (products) often have positive or negative unit profits. Mining high utility itemsets in a transactional database where items have positive or negative unit profits is a computationally expensive task, and it is thus desirable to design more efficient algorithms. To address this issue, we propose an efficient algorithm named FHN (Faster High-Utility itemset miner with Negative unit profits). It relies on a novel PNU-list structure (Positive-and-Negative Utility-list) structure to efficiently mine high utility itemsets, while considering both positive and negative unit profits. Moreover, several pruning strategies are introduced in FHN to reduce the number of candidate itemsets, and thus enhance the performance of FHN. Extensive experimental results on both real-life and synthetic datasets show that the proposed FHN algorithm is in general two to three orders of magnitude faster and can use up to 200 times less memory than the state-of-the-art algorithm HUINIV-Mine. Moreover, it is shown that FHN performs especially well on dense datasets. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

Natural language processing (NLP) is useful for handling text and speech, and sequence labeling plays an important role by automatically analyzing a sequence (text) to assign category labels to each part. However, the performance of these conventional models depends greatly on hand-crafted features and task-specific knowledge, which is a time consuming task. Several conditional random fields (CRF)-based models for sequence labeling have been presented, but the major limitation is how to use neural networks for extracting useful representations for each unit or segment in the input sequence. In this paper, we propose an attention segmental recurrent neural network (ASRNN) that relies on a hierarchical attention neural semi-Markov conditional random fields (semi-CRF) model for the task of sequence labeling. Our model uses a hierarchical structure to incorporate character-level and word-level information and applies an attention mechanism to both levels. This enables our method to differentiate more important information from less important information when constructing the segmental representation. We evaluated our model on three sequence labeling tasks, including named entity recognition (NER), chunking, and reference parsing. Experimental results show that the proposed model benefited from the hierarchical structure, and it achieved competitive and robust performance on all three sequence labeling tasks. [ABSTRACT FROM AUTHOR]

High-utility itemset mining (HUIM) is a major contemporary data mining issue. It is different from frequent itemset mining (FIM), which only considers the frequency factor. HUIM applies both the quantity and profit factors to be used to reveal the most profitable products. Several previous approaches have been proposed to mine high-utility itemsets (HUIs) and most of them have to handle the exponential search space for discovering HUIs when the number of distinct items and the size of the database are both very large. Therefore, two evolutionary computation (EC) techniques, genetic algorithm (GA) and particle swarm optimization (PSO), were previously proposed to mine HUIs. In these studies, GAs and PSOs also could obtain the huge amount of high-utility items in a limitation time. In this paper, a novel algorithm based on the other evolutionary computation technique, ant colony optimization (ACO), is proposed to resolve this issue. Unlike GAs and PSOs, ACOs produce a feasible solution in a constructive way. They can avoid generating unreasonable solutions as much as possible. Thus, a well-defined ACO approach can always obtain suitable solutions efficiently. An ant colony system (ACS), which is extended from ACO and consists of high-utility itemset mining by ACS (HUIM-ACS), is proposed to efficiently find HUIs. In general, an EC algorithm cannot make sure the provided solution is the global optimal solution. But the designed HUIM-ACS algorithm maps the completed solution space into the routing graph and includes two pruning processes. Therefore, it guarantees that it obtains all of the HUIs when there is no candidate edge from the starting point. In addition, HUIM-ACS does not estimate the same feasible solution again in its process in order to avoid wasting computational resource. Substantial experiments on real-life datasets show that the proposed algorithm outperforms the other heuristic algorithms for mining HUIs in terms of the number of discovered HUIs, and convergence. [ABSTRACT FROM AUTHOR]

It is uncertain whether products will be manufactured as defective products. Producing the defective products causes the waste of time and finance in the industrial fields. When the financial crisis occurs in the manufacturing plants, production lines of the less profitable products should be stopped. To overcome the financial crisis, it is required to find the production lines that manufacture the less profitable commodities and are likely to produce the faulty merchandises and remove the corresponding production lines in order to increase the profit. Erasable pattern mining has been suggested to analyze and solve the financial problems by discovering patterns with low profit. As databases become more diverse due to the environment and characteristics of data, demands for erasable pattern mining that processes the various databases increase. An uncertain database, which is one of diverse types of databases, includes the probability related to the item, such as the probability of existence and the probability of defects. Erasable pattern mining, which considers the probability of each item, can discover pattern results which are more suitable for purpose of users. Motivated by this, we propose an efficient tree-based erasable pattern mining algorithm from the uncertain database. Considering the probability of the item, the suggested algorithm extracts erasable patterns with low profits from the uncertain database. Since both profit of the product and the probability of the item are considered, the discovered patterns are more meaningful than the patterns found by the existing erasable pattern mining. Moreover, the proposed method improves the mining operations by utilizing a list structure as well as a tree structure. We performed a performance evaluation on diverse real and synthetic datasets in order to prove the proposed algorithm outperforms the existing erasable pattern mining algorithms. The differences in runtime, memory usage, and scalability are shown through the comparison of performance with other state-of-the-art algorithms and the suggested algorithm. [ABSTRACT FROM AUTHOR]

Opening range breakout (ORB) is a well-known intraday trading strategy via technical analysis. ORB lacks robustness against market uncertainties (e.g., information from contradictory sources), and does not consider all relevant market characteristics. Furthermore, the closing strategies in generic ORB are not well defined. In this study, we developed an evolutionary ORB-based model, which utilized historical data to optimize thresholds in order to enhance profitability, and developed protective closing strategies aimed at to prevent unacceptable losses. Selecting appropriate thresholds and parameters for ORB is a non-trivial task, due to the fact that the search space exceeds sixty-five thousand options. We used evolutionary computation to derive rational strategies and parameters for ORB. The proposed framework based on a genetic algorithm optimizes the parameters related to threshold selection and protective closing strategies. In experiments, this resulted in annual returns of 9.3% (representing a 2.8% improvement over the original strategy) and Sharpe ratio of 2.5 (an improvement of 1.0), while reducing the maximum drawdown by half. The proposed scheme also reduced computational overhead by 89% compared to a grid search. [ABSTRACT FROM AUTHOR]

High-utility itemset mining (HUIM) is one of the heavily studied fields of data mining, which is due to its high compatibility with real-world applications. HUIM is a process of extracting a complete set of interesting patterns by considering the importance and the quantity of each item. Incremental high-utility itemset mining (IHUIM) further increases the compatibility of HUIM by mining from a data stream instead of a static database. It does this by mining interesting patterns in a single database scan and storing prior knowledge in a compact data structure. However, there is a critical limitation, because the importance of each item has to be guaranteed to remain unchanged throughout the data stream. This limitation hinders the compatibility of IHUIM to the real-world applications, because the importance of an item changes from time to time in the real world. Conventional IHUIM approaches consequently have to use outdated information when mining interesting patterns. This paper proposes a novel problem of mining high-utility itemsets in an incremental and dynamic profit environment in order to account for the fluctuation of the item's importance. Furthermore, a novel approach to mining patterns in this type of environment is introduced using an efficient list structure and tight upper bounds. Experiments on real and synthetic datasets show that the proposed approach performs well compared to the state-of-the-art approaches in terms of the runtime and memory usage, and it scales better than the other approaches. [ABSTRACT FROM AUTHOR]

High Utility Pattern Mining is a popular task for analyzing data. It consists of discovering patterns having a high importance in databases. A popular application of high utility pattern mining is to identify high utility (profitable) patterns in customer transaction data. Though such analysis can be useful to understand data, it does not consider the cost (e.g. effort, resources, money or time) required for obtaining the utility (benefits). In this paper, we argue that to discover interesting patterns in event sequences, it is useful to consider both a utility model and a cost model. For example, to identify cost-effective ways of treating patients from medical pathways data, it is desirable to consider not only the ability of treatments to inhibit symptoms or cure a disease (utility) but also the resources consumed and the time spent (cost) to provide these treatments. Based on this perspective, this paper defines a novel task of discovering Cost-Effective Event Sequences in event logs. In this task, cost is modeled as numeric values, while utility is represented either as binary or numeric values. Measures are proposed to evaluate the trade-off and correlation between cost and utility of patterns to identify cost-effective patterns (patterns having a low cost but providing a high utility). Three efficient algorithms called CEPB, corCEPB and CEPN are designed to extract these patterns. They rely on a tight lower-bound on the cost and a memory buffering technique to find patterns efficiently. Experiments show that the proposed algorithms achieve high efficiency, that proposed optimizations improve efficiency, and that insightful cost-effective patterns are found in real-life e-learning data. [ABSTRACT FROM AUTHOR]

High utility pattern mining has been actively researched and applied to diverse applications because it can process the database by considering the quantity and importance of items. However, traditional high utility pattern mining methods aim to handle static databases, so they cannot meet the requirements of users who want to process the dynamic environments. Although methods to process incremental databases have been proposed, they have limitations that they perform the mining process on the entire database, including already processed data, whenever data are newly inserted. The pre-large concept is one of the techniques to process the dynamic database. Utilizing the pre-large technique, we can efficiently handle the transaction insertion using the extracted patterns of the previous mining process. In this paper, we propose a novel pre-large-based approach to discover high utility patterns from incremental databases. A list structure is proposed to store the utility information of patterns, so candidate patterns are not generated, and an additional database scan is not required. Performance evaluation performed on various real and synthetic datasets shows that the proposed algorithm is more efficient and effective than the latest approaches in a dynamic environment. [ABSTRACT FROM AUTHOR]

Data mining has been actively studied, and it has become more important due to the development of information technology and the demands of diverse applications, such as the retail market, medical field, and manufacturing plants. High average-utility pattern mining is a type of data mining that finds valuable patterns by dividing the utility of a pattern by the length of the pattern. It considers the length of the pattern, so it can handle the demerits of utility pattern mining and extract more important patterns. Meanwhile, stream data is produced in real time, and the importance of the recent data gradually increases as opposed to the old data. However, most of the previous high average utility pattern mining approaches cannot find the latest valuable patterns over the data streams. Although research using a sliding window model was conducted to handle only the recent data, it has a problem due to the data structure. Since the previous work is a tree-based approach, numerous candidate patterns are generated, and an additional database scan is required to calculate the actual utilities of candidates. Creating the candidate patterns reduces the efficiency of runtime and memory and makes real-time data processing difficult. We propose an efficient algorithm that uses a list structure for sliding window-based high average-utility pattern mining in this paper. The proposed algorithm scans the stream data once, mines the complete set of the recent high average-utility patterns without generating candidates, and reduces the search space by using a novel pruning technique. The experiment results show that the proposed algorithm outperforms the state-of-the-art algorithms in terms of the runtime, memory, and scalability in real and synthetic datasets. [ABSTRACT FROM AUTHOR]

High utility pattern mining (HUPM) discovers meaningful patterns by considering features of items and utility from non-binary data. Data called stream data is continually generated over time. Various techniques based on high utility pattern mining have been suggested for processing stream data. High utility pattern mining based on a sliding window performs pattern mining using a window. Since it uses only the data stored in a window, only the latest data can be managed. However, Stream data has the property that newly created data has a higher influence than relatively old data. It is necessary to consider the importance of the data stored in a window differently. In this paper, we propose an efficient algorithm based on a sliding window approach that mines high utility patterns considering the latest data more significantly from damped stream data where new data is constantly being inserted. In other words, our technique divides the stream data into fixed-sized multiple batch data and processes differently the importance of each batch data in a window according to the added time using the decaying factor. Moreover, we conduct experiments to compare and analyze our approach with the state-of-the-art algorithms using real and synthetic datasets. The experimental results show that our proposed method outperforms the competitors in terms of run time, memory usage, and scalability test. [ABSTRACT FROM AUTHOR]

Discovering patterns in graphs has many applications such as social network, biological and chemistry data analysis. Although many algorithms were proposed to identify interesting patterns in graphs, most of them consider simple types of graphs such as static graphs or graphs having a single attribute per vertex. Recently, studies have considered discovering frequent patterns in dynamic attributed graphs. These graphs can represent not only relationships between entities but also how they evolve over time, and describe entities with multiple attributes. Algorithms for mining frequent patterns in dynamic attributed graphs select patterns based on their occurrence frequency. But a major drawback of this approach is that many frequent patterns may contain entities that are weakly correlated. Thus, numerous frequent but spurious patterns may be shown to the user. To allows discovering strongly correlated patterns in dynamic attributed graphs, this paper proposes a novel significance measure named Sequence Virtual Growth Rate. It allows evaluating if a pattern represents entities that are correlated in terms of their proximity in a graph over time. Based on this measure a novel type of graph patterns is defined called Significant Trend Sequence. To efficiently mine these patterns, two algorithms named TSeqMiner d f s − b f s and TSeqMiner d f s − d f s are proposed. They rely on a novel upper bound and pruning strategy to reduce the search space. Experimental results show that the proposed algorithms are efficient and can identify interesting patterns in real-world social network and flight data. [ABSTRACT FROM AUTHOR]