Searching for emerging patterns with streaming features

Master's Thesis in Computer Engineering (Artificial Intelligence)

Abstract

Extracting useful patterns from data sets is one of the challenging topics in data mining. On the other hand, in high-dimensional data, extracting a small set of emerging patterns with strong predictability is one of the important issues in creating a classifier based on emerging patterns. In the real world, features are not always fully available; Accordingly, the problem becomes more difficult when the feature set is unknown before the learning process begins. Streaming features are features that are generated online and processed at the same time as production. In this design, the features emerge one by one over time instead of all the features being ready before the learning process.

In this study, we propose a dynamic structure of the frequent pattern tree so that the tree is built as soon as new features arrive and the emerging patterns can be extracted online. DFP-SEPSF provides an efficient bottom-up method to construct an unordered dynamic recurrent pattern tree UDFP-tree and an ordered dynamic recurrent pattern tree ODFP-tree. The first method does not consider the order of items, while the second method applies the order of items.

Furthermore, the proposed framework extracts strong emerging patterns to create a robust and fast classifier that can deal with noise.

The proposed method significantly reduces the search space of emerging patterns and extracts emerging patterns with strong discriminating power by removing useless patterns.

The proposed method of patterns It simultaneously discovers emergents for each class and, in addition, guides the process of generating recurrent pattern trees efficiently in order to reduce calculations.

Evaluation of our experiences on a wide range of data shows the effectiveness of the proposed method compared to other known methods in terms of prediction accuracy, number of extracted patterns and execution time.

Keywords:

Emergent patterns, dynamic recurrent pattern, order of item tree. , flow features

Chapter One

Introduction

Classification[1] is one of the basic tasks in data mining[2], which has been widely studied in the field of machine learning[3], neural networks[4] and pattern recognition[5]. The input is a collection of training examples[6] that includes several features[7]. Features can be separated into two categories, discrete features[8] and continuous features[9], according to their range of values. In general, a clause class [10] produces a concise and meaningful description (model [11]) for each class label [12] in relation to the properties. Then, the model is used to predict the class label of unknown samples [13]. Classification is also known as supervised learning [14] where each training instance has a class label. While, unsupervised learning[15] or clustering[16] searches and categorizes homogeneous groups of objects based on their attribute values; In fact, instances do not have class tags. Classification is successfully used in a wide range of applications, including scientific experiments [17], drug detection [18], weather forecasting [19], authentication [20], customer segmentation [21], target marketing [22] and fraud detection [23].

Classification based on patterns [24] is considered a new methodology. Discovering patterns that indicate the distinction between different classes is considered one of the important topics in data mining. In this research, we extract the classification based on patterns called emerging patterns [25] (Emerging Patterns) that clearly show the distinction between classes, from the data set [26] and then, based on them, we perform the classification. to depict significant differences between classes [1]. An emerging pattern is an inflectional combination of features whose probability of presence in one class changes significantly compared to other classes [1,2]. These patterns are useful because they are able to express the distinction between classes.If the frequency [27] of any pattern in a class is significant compared to other classes, it indicates that this pattern is specifically assigned to this class, and on the other hand, these types of patterns are of particular importance for databases where there is a time limit for extracting knowledge from them. can be) greater than a threshold value. This threshold value should be chosen in such a way that the extracted patterns show the difference and distinction between different classes. These patterns are actually a set of items that express the inflectional combination between feature values ??[2]. Typically, the number of extraction patterns is very large, but only a small number of these patterns are desirable and useful for data analysis and classification. Since a large amount of these patterns are irrelevant [29] and repetitive [30], they do not provide new knowledge and therefore have an adverse effect on the accuracy of the classifier, which causes a decrease in the prediction accuracy [31]. To increase the efficiency [32] and accuracy, a procedure should be developed to remove dependent and unhelpful patterns to reduce the number of these patterns. An emerging pattern with a high probability in its own class and a low probability in its opposite class can be used to determine a test sample. The strength of this pattern is expressed by measures such as relative frequency [33] and its growth rate (probability ratio of the pattern in one class compared to other classes).

In many applied fields such as knowledge discovery from genetic data [34], image processing [35], intrusion detection [36], outlier detection [37], fraud detection [38], unbalanced data [39], data flow [40], bioinformatics [41], system proposed [42], it is necessary to detect a sudden change in the data. Emerging patterns extract sudden changes and significant differences from the data. Emergent patterns, in the field of image processing for segmentation, work in such a way that they try to introduce a new segment in the pixels that have a sudden change in intensity [43]. In the field of intrusion and fraud detection, the behavior of the data is tracked, when the behavior of the data changes suddenly, it is recognized as an intrusion. In recommender systems, the system looks for the specific behaviors of each user in order to discover the specific characteristics of each user and suggest products according to their interests and talents. Therefore, emerging patterns play a significant role in this regard.

The concept of streaming features[44]

In streaming data[45], samples are received over time while the number of features is fixed. But in streaming features, the number of learning data is fixed, but the features are generated dynamically, and the learning algorithm receives the features over time [31, 32]. In the flow features of the routine, the features are produced by feature generation methods such as statistical relational learning methods [46] and interactions between features [47]. The problems that arise after the production of features by these methods are as follows: 1) Millions or even billions of features are produced, which due to memory limitations, it is possible to store this amount of features, and on the other hand, a lot of time must be spent to start the learning process. 2) The features are produced by the queries in SQL, the execution of these queries is limited to the time of the processor [48], almost the processor executes every hundred thousand queries in 24 hours. On the other hand, many features are irrelevant and repetitive production[49]. This shows that a small number of these production features are effective in the learning process and therefore the production of features is costly [32]. Based on this, in order to overcome these problems, the concept of flow characteristics was formed and an effort was made to guide the production process of characteristics by producing the dynamics of characteristics and examining these characteristics during production and its impact on the learning process.

To deal with the challenges raised, the learning process must be able to respond to flow characteristics. In fact, the learning routine should be incrementally updateable upon receiving each feature without returning to the first learning step. Therefore, in order to extract strong patterns, the features should be checked first and the features that are irrelevant should be removed, then the patterns should be extracted from the useful and strong features.