Network Big Data: A Literature Survey on Stream Data Mining
---
paper_title: Network Big Data:Present and Future

paper_content:

Network big data refer to the massive data generated by interaction and fusion of the ternary human-machine-thing universe in the Cyberspace and available on the Internet.The increase of their scale and complexity exceeds that of the capacity of hardware characterized by the Moore law,which brings grand challenges to the architecture and the processing and computing capacity of the contemporary IT systems,meanwhile presents unprecedented opportunities on deeply mining and taking full advantage of the big value of network big data.Therefore,it is pressing to investigate the disciplinary issues and discover the common laws of network big data,and further study the fundamental theory and basic approach to qualitatively or quantitatively dealing with network big data.This paper analyzes the challenges caused by the complexity,uncertainty and emergence of network big data,and summarizes major issues and research status of the awareness,representation,storage,management,mining,and social computing of network big data,as well as network data platforms and applications.It also looks ahead to the development trends of big data science,new modes and paradigm of data computing,new IT infrastructures,and data security and privacy,etc.
---
paper_title: O(ε)-Approximation to physical world by sensor networks

paper_content:

To observe the complicate physical world by a WSN, the sensors in the WSN senses and samples the data from the physical world. Currently, most of the existing work use equi-frequency sampling methods (EFS) or EFS based sampling methods for data acquisition in sensor networks. However, the accuracies of EFS and EFS based sampling methods cannot be guaranteed in practice since the physical world usually varies continuously, and these methods does not support reconstructing of the monitored physical world. To overcome the shortages of EFS and EFS based sampling methods, this paper focuses on designing physical-world-aware data acquisition algorithms to support O(ϵ)-approximation to the physical world for any ϵ ≥ 0. Two physical-world-aware data acquisition algorithms based on Hermit and Spline interpolation are proposed in the paper. Both algorithms can adjust the sensing frequency automatically based on the changing trend of the physical world and given c. The thorough analysis on the performance of the algorithms are also provided, including the accuracies, the smooth of the outputted curves, the error bounds for computing first and second derivatives, the number of the sampling times and complexities of the algorithms. It is proven that the error bounds of the algorithms are O(ϵ) and the complexities of the algorithms are O(1/ϵ1/4). Based on the new data acquisition algorithms, an algorithm for reconstructing physical world is also proposed and analyzed. The theoretical analysis and experimental results show that all the proposed algorithms have high performance in items of accuracy and energy consumption.
---
paper_title: Enabling fast prediction for ensemble models on data streams

paper_content:

Ensemble learning has become a common tool for data stream classification, being able to handle large volumes of stream data and concept drifting. Previous studies focus on building accurate prediction models from stream data. However, a linear scan of a large number of base classifiers in the ensemble during prediction incurs significant costs in response time, preventing ensemble learning from being practical for many real world time-critical data stream applications, such as Web traffic stream monitoring, spam detection, and intrusion detection. In these applications, data streams usually arrive at a speed of GB/second, and it is necessary to classify each stream record in a timely manner. To address this problem, we propose a novel Ensemble-tree (E-tree for short) indexing structure to organize all base classifiers in an ensemble for fast prediction. On one hand, E-trees treat ensembles as spatial databases and employ an R-tree like height-balanced structure to reduce the expected prediction time from linear to sub-linear complexity. On the other hand, E-trees can automatically update themselves by continuously integrating new classifiers and discarding outdated ones, well adapting to new trends and patterns underneath data streams. Experiments on both synthetic and real-world data streams demonstrate the performance of our approach.
---
paper_title: Long-Term Incremental Web-Supervised Learning of Visual Concepts via Random Savannas

paper_content:

The idea of using image and video data available in the World-Wide Web (WWW) as training data for classifier construction has received some attention in the past few years. In this paper, we present a novel incremental and scalable web-supervised learning system that continuously learns appearance models for image categories with heterogeneous appearances and improves these models periodically. Simply specifying the name of the concept that has to be learned initializes the proposed system, and there is no further supervision afterwards. Textual and visual information on web sites are used to filter out irrelevant and misleading training images. To obtain a robust, flexible, and updatable way of learning, a novel learning framework is presented that relies on clustering in order to identify visual subclasses before using an ensemble of random forests, called random savanna, for subclass learning. Experimental results demonstrate that the proposed web-supervised learning approach outperforms a support vector machine (SVM), while at the same time being simply parallelizable in the training and testing phases.
---
paper_title: Dynamic classifier ensemble model for customer classification with imbalanced class distribution

paper_content:

Customer classification is widely used in customer relationship management including churn prediction, credit scoring, cross-selling and so on. In customer classification, an important yet challenging problem is the imbalance of data distribution. In this paper, we combine ensemble learning with cost-sensitive learning, and propose a dynamic classifier ensemble method for imbalanced data (DCEID). For each test customer, it can adaptively select out the more appropriate one from the two kinds of dynamic ensemble approach: dynamic classifier selection (DCS) and dynamic ensemble selection (DES). Meanwhile, new cost-sensitive selection criteria for DCS and DES are constructed respectively to improve the classification ability for imbalanced data. We apply this method to a credit scoring dataset in UCI and a real churn prediction dataset from a telecommunication company. The experimental results show that the classification performance of DCEID is not only better than some static ensemble methods such as weighted random forests and improved balanced random forests, but also better than the existing DCS and DES strategies.
---
paper_title: Classification and Novel Class Detection in Concept-Drifting Data Streams under Time Constraints

paper_content:

Most existing data stream classification techniques ignore one important aspect of stream data: arrival of a novel class. We address this issue and propose a data stream classification technique that integrates a novel class detection mechanism into traditional classifiers, enabling automatic detection of novel classes before the true labels of the novel class instances arrive. Novel class detection problem becomes more challenging in the presence of concept-drift, when the underlying data distributions evolve in streams. In order to determine whether an instance belongs to a novel class, the classification model sometimes needs to wait for more test instances to discover similarities among those instances. A maximum allowable wait time Tc is imposed as a time constraint to classify a test instance. Furthermore, most existing stream classification approaches assume that the true label of a data point can be accessed immediately after the data point is classified. In reality, a time delay Tl is involved in obtaining the true label of a data point since manual labeling is time consuming. We show how to make fast and correct classification decisions under these constraints and apply them to real benchmark data. Comparison with state-of-the-art stream classification techniques prove the superiority of our approach.
---
paper_title: An incremental learning vector quantization algorithm for pattern classification

paper_content:

Prototype classifiers have been studied for many years. However, few methods can realize incremental learning. On the other hand, most prototype classifiers need users to predetermine the number of prototypes; an improper prototype number might undermine the classification performance. To deal with these issues, in the paper we propose an online supervised algorithm named Incremental Learning Vector Quantization (ILVQ) for classification tasks. The proposed method has three contributions. (1) By designing an insertion policy, ILVQ incrementally learns new prototypes, including both between-class incremental learning and within-class incremental learning. (2) By employing an adaptive threshold scheme, ILVQ automatically learns the number of prototypes needed for each class dynamically according to the distribution of training data. Therefore, unlike most current prototype classifiers, ILVQ needs no prior knowledge of the number of prototypes or their initial value. (3) A technique for removing useless prototypes is used to eliminate noise interrupted into the input data. Results of experiments show that the proposed ILVQ can accommodate the incremental data environment and provide good recognition performance and storage efficiency.
---
paper_title: A Semi-supervised Ensemble Approach for Mining Data Streams

paper_content:

There are many challenges in mining data streams, such as infinite length, evolving nature and lack of labeled instances. Accordingly, a semi-supervised ensemble approach for mining data streams is presented in this paper. Data streams are divided into data chunks to deal with the infinite length. An ensemble classification model E is trained with existing labeled data chunks and decision boundary is constructed using E for detecting novel classes. New labeled data chunks are used to update E while unlabeled ones are used to construct unsupervised models. Classes are predicted by a semi-supervised model Ex which is consist of E and unsupervised models in a maximization consensus manner, so better performance can be achieved by using the constraints from unsupervised models with limited labeled instances. Experiments with different datasets demonstrate that our method outperforms conventional methods in mining data streams.
---
paper_title: Exponentially Weighted Moving Average Charts for Detecting Concept Drift

paper_content:

Classifying streaming data requires the development of methods which are computationally efficient and able to cope with changes in the underlying distribution of the stream, a phenomenon known in the literature as concept drift. We propose a new method for detecting concept drift which uses an Exponentially Weighted Moving Average (EWMA) chart to monitor the misclassification rate of an streaming classifier. Our approach is modular and can hence be run in parallel with any underlying classifier to provide an additional layer of concept drift detection. Moreover our method is computationally efficient with overhead O(1) and works in a fully online manner with no need to store data points in memory. Unlike many existing approaches to concept drift detection, our method allows the rate of false positive detections to be controlled and kept constant over time.
---
paper_title: Mining time-changing data streams

paper_content:

Most statistical and machine-learning algorithms assume that the data is a random sample drawn from a stationary distribution. Unfortunately, most of the large databases available for mining today violate this assumption. They were gathered over months or years, and the underlying processes generating them changed during this time, sometimes radically. Although a number of algorithms have been proposed for learning time-changing concepts, they generally do not scale well to very large databases. In this paper we propose an efficient algorithm for mining decision trees from continuously-changing data streams, based on the ultra-fast VFDT decision tree learner. This algorithm, called CVFDT, stays current while making the most of old data by growing an alternative subtree whenever an old one becomes questionable, and replacing the old with the new when the new becomes more accurate. CVFDT learns a model which is similar in accuracy to the one that would be learned by reapplying VFDT to a moving window of examples every time a new example arrives, but with O(1) complexity per example, as opposed to O(w), where w is the size of the window. Experiments on a set of large time-changing data streams demonstrate the utility of this approach.
---
paper_title: Density Based Distribute Data Stream Clustering Algorithm

paper_content:

To solve the problem of distributed data streams clustering, the algorithm DB-DDSC (Density-Based Distribute Data Stream Clustering) was proposed. The algorithm consisted of two stages. First presented the concept of circular-point based on the representative points and designed the iterative algorithm to find the density-connected circular-points, then generated the local model at the remote site. Second designed the algorithm to generate global clusters by combining the local models at coordinator site. The DB-DDSC algorithm can find the the clusters of different shapes under the distributed data stream environment, avoid frequently sending data by using the test-update algorithm, and reduce the data transmission. The experiments show that the DB-DDSC algorithm is feasible and scale expandable.
---
paper_title: Online clustering of parallel data streams

paper_content:

In recent years, the management and processing of so-called data streams has become a topic of active research in several fields of computer science such as, e.g., distributed systems, database systems, and data mining. A data stream can roughly be thought of as a transient, continuously increasing sequence of time-stamped data. In this paper, we consider the problem of clustering parallel streams of real-valued data, that is to say, continuously evolving time series. In other words, we are interested in grouping data streams the evolution over time of which is similar in a specific sense. In order to maintain an up-to-date clustering structure, it is necessary to analyze the incoming data in an online manner, tolerating not more than a constant time delay. For this purpose, we develop an efficient online version of the classical K-means clustering algorithm. Our method's efficiency is mainly due to a scalable online transformation of the original data which allows for a fast computation of approximate distances between streams.
---
paper_title: Wavelet Synopsis Based Clustering of Parallel Data Streams

paper_content:

In many real-life applications, such as stock markets, network monitoring, and sensor networks, data are modeled as dynamic evolving time series which is continuous and unbounded in nature, and many such data streams concur usually. Clustering is useful in analyzing such paralleled data streams. This paper is interested in grouping these evolving data streams. For this purpose, a synopsis is maintained dynamically for each data stream. The construction of the synopsis is based on Discrete Wavelet Transform and utilizes the amnesic feature of data stream. By using the synopsis, a fast computation of approximate distances between streams and the cluster center can be implemented, and an efficient online version of the classical K-means clustering algorithm is developed. Experiments have proved the effectiveness of the proposed method.
---
paper_title: A Framework for Clustering Uncertain Data Streams

paper_content:

In recent years, uncertain data management applications have grown in importance because of the large number of hardware applications which measure data approximately. For example, sensors are typically expected to have considerable noise in their readings because of inaccuracies in data retrieval, transmission, and power failures. In many cases, the estimated error of the underlying data stream is available. This information is very useful for the mining process, since it can be used in order to improve the quality of the underlying results. In this paper we will propose a method for clustering uncertain data streams. We use a very general model of the uncertainty in which we assume that only a few statistical measures of the uncertainty are available. We will show that the use of even modest uncertainty information during the mining process is sufficient to greatly improve the quality of the underlying results. We show that our approach is more effective than a purely deterministic method such as the CluStream approach. We will test the approach on a variety of real and synthetic data sets and illustrate the advantages of the method in terms of effectiveness and efficiency.
---
paper_title: Moment: maintaining closed frequent itemsets over a stream sliding window

paper_content:

This paper considers the problem of mining closed frequent itemsets over a sliding window using limited memory space. We design a synopsis data structure to monitor transactions in the sliding window so that we can output the current closed frequent itemsets at any time. Due to time and memory constraints, the synopsis data structure cannot monitor all possible itemsets. However, monitoring only frequent itemsets make it impossible to detect new itemsets when they become frequent. In this paper, we introduce a compact data structure, the closed enumeration tree (CET), to maintain a dynamically selected set of item-sets over a sliding-window. The selected itemsets consist of a boundary between closed frequent itemsets and the rest of the itemsets. Concept drifts in a data stream are reflected by boundary movements in the CET. In other words, a status change of any itemset (e.g., from non-frequent to frequent) must occur through the boundary. Because the boundary is relatively stable, the cost of mining closed frequent item-sets over a sliding window is dramatically reduced to that of mining transactions that can possibly cause boundary movements in the CET. Our experiments show that our algorithm performs much better than previous approaches.
---
paper_title: Verifying and Mining Frequent Patterns from Large Windows over Data Streams

paper_content:

Mining frequent itemsets from data streams has proved to be very difficult because of computational complexity and the need for real-time response. In this paper, we introduce a novel verification algorithm which we then use to improve the performance of monitoring and mining tasks for association rules. Thus, we propose a frequent itemset mining method for sliding windows, which is faster than the state-of-the-art methods - in fact, its running time that is nearly constant with respect to the window size entails the mining of much larger windows than it was possible before. The performance of other frequent itemset mining methods (including those on static data) can be improved likewise, by replacing their counting methods (e.g., those using hash trees) by our verification algorithm.
---
paper_title: Mining frequent itemsets in distributed and dynamic databases

paper_content:

Traditional methods for frequent itemset mining typically assume that data is centralized and static. Such methods impose excessive communication overhead when data is distributed, and they waste computational resources when data is dynamic. We present what we believe to be the first unified approach that overcomes these assumptions. Our approach makes use of parallel and incremental techniques to generate frequent itemsets in the presence of data updates without examining the entire database, and imposes minimal communication overhead when mining distributed databases. Further, our approach is able to generate both local and global frequent itemsets. This ability permits our approach to identify high-contrast frequent itemsets, which allows one to examine how the data is skewed over different sites.
---
paper_title: UDS-FIM: An Efficient Algorithm of Frequent Itemsets Mining over Uncertain Transaction Data Streams

paper_content:

In this paper, we study the problem of finding frequent itemsets from uncertain data streams. To the best of our knowledge, the existing algorithms cannot compress transaction itemsets to a tree as compact as the classical FP-Tree, thus they need much time and memory space to process the tree. To address this issue, we propose an algorithm UDS-FIM and a tree structure UDS-Tree. Firstly, UDS-FIM maintains probability values of each transactions to an array; secondly, compresses each transaction to a UDS-Tree in the same manner as an FP-Tree (so it is as compact as an FP-Tree) and maintains index of probability values of each transaction in the array to the corresponding tail-nodes; lastly, it mines frequent itemsets from the UDS-Tree without additional scan of transactions. The experimental results show that UDS-FIM has achieved a good performance under different experimental conditions in terms of runtime and memory consumption.
---
paper_title: Frequent Items Query Algorithm for Uncertain Sensing Data

paper_content:

With advances in technology,large amounts of streaming data can be generated continuously by sensors.Due to the inherited limitation of sensors,these continuous sensing data can be uncertain.This calls for stream mining of uncertain sensing data.Frequent items query is valuable in wireless sensor networks(WSNs) and it can be widely used in environmental monitoring,association rules mining,and so on.A basic algorithm which continuously maintains sliding window frequent items over WSNs is proposed.However the basic algorithm needs to maintain all items in the window.Due to this,an improved algorithm is further proposed by optimizing in two aspects:(1) the pruning rules by predicting the upper bound of items probability is developed,which can reduce the candidate set and improve the query efficiency;(2) the large amount of the same items in different window can be compressed by cp-list structure in order to minimize the memory utilization.Finally,experimental results and detailed analysis demonstrate that the high efficiency and low memory cost of the proposed algorithms in WSNs.
---
paper_title: O(ε)-Approximation to physical world by sensor networks

paper_content:

To observe the complicate physical world by a WSN, the sensors in the WSN senses and samples the data from the physical world. Currently, most of the existing work use equi-frequency sampling methods (EFS) or EFS based sampling methods for data acquisition in sensor networks. However, the accuracies of EFS and EFS based sampling methods cannot be guaranteed in practice since the physical world usually varies continuously, and these methods does not support reconstructing of the monitored physical world. To overcome the shortages of EFS and EFS based sampling methods, this paper focuses on designing physical-world-aware data acquisition algorithms to support O(ϵ)-approximation to the physical world for any ϵ ≥ 0. Two physical-world-aware data acquisition algorithms based on Hermit and Spline interpolation are proposed in the paper. Both algorithms can adjust the sensing frequency automatically based on the changing trend of the physical world and given c. The thorough analysis on the performance of the algorithms are also provided, including the accuracies, the smooth of the outputted curves, the error bounds for computing first and second derivatives, the number of the sampling times and complexities of the algorithms. It is proven that the error bounds of the algorithms are O(ϵ) and the complexities of the algorithms are O(1/ϵ1/4). Based on the new data acquisition algorithms, an algorithm for reconstructing physical world is also proposed and analyzed. The theoretical analysis and experimental results show that all the proposed algorithms have high performance in items of accuracy and energy consumption.
---
paper_title: A Compression Algorithm for Multi-streams Based on GEP

paper_content:

This paper applied the Methods which based on GEP in compress multi-streams. The contributions of this paper include: 1) giving an introduction to data function finding based on GEP(DFF-GEP), defining the main conception of Multi-Streams, and revealing the map relation in it; 2) putting forward the Compression Algorithm for Multi-Streams according to map relation lied in data between data streams; and 3)providing an experience with the real data and find that (3.1) the compression ratio of the new methods is 120?150 times as the traditional wavelets method, and 35?70 times as the wavelets and coincidence method; (3.2) the relative error of the new method is about 3?, yet maximum relative error is 0.01 by using the traditional relative error standard, the precision is improved from 7% to 15% as compared with the traditional method.
---
paper_title: Continuous privacy preserving publishing of data streams

paper_content:

Recently, privacy preserving data publishing has received a lot of attention in both research and applications. Most of the previous studies, however, focus on static data sets. In this paper, we study an emerging problem of continuous privacy preserving publishing of data streams which cannot be solved by any straightforward extensions of the existing privacy preserving publishing methods on static data. To tackle the problem, we develop a novel approach which considers both the distribution of the data entries to be published and the statistical distribution of the data stream. An extensive performance study using both real data sets and synthetic data sets verifies the effectiveness and the efficiency of our methods.
---
paper_title: Fast Clustering-Based Anonymization Algorithm for Data Streams

paper_content:

In order to prevent the disclosure of sensitive information and protect users’ privacy,the generalization and suppression of technology is often used to anonymize the quasi-identifiers of the data before its sharing.Data streams are inherently infinite and highly dynamic which are very different from static datasets,so that the anonymization of data streams needs to be capable of solving more complicated problems.The methods for anonymizing static datasets cannot be applied to data streams directly.In this paper,an anonymization approach for data streams is proposed with the analysis of the published anonymization methods for data streams.This approach scans the data only once to recognize and reuse the clusters that satisfy the anonymization requirements for speeding up the anonymization process.Experimental results on the real dataset show that the proposed method can reduce the information loss that is caused by generalization and suppression and also satisfies the anonymization requirements and has low time and space complexity.
---
paper_title: Mining Method for Data Quality Detection Rules

paper_content:

Data quality rules are key to the database quality detection. To discover data quality rules from relational databases automatically and detect the error or abnormal data based on them,the form and evaluation measures of data quality rules are studied,and criterions of computing data quality rules are presented based on data item groups and the confidence threshold. The algorithms of mining minimal data quality rules and the main idea of detecting data errors using data quality rules are also given. The new form of data quality rules makes use of confidence mechanism of association rules and the expression of conditional functional dependencies to describe functional dependencies, conditional functional dependencies and association rules in the same format. It can be concluded that this kind of data quality rules has the properties of conciseness,objectivity,completeness and accuracy of detecting the error or abnormal data. Compared with other related research work,the proposed algorithms have lower temporal complexity,and the discovered quality rules improve the detecting rate. The effectiveness and correctness of the proposed methods are proved by the experiments.
---

Title: Network Big Data: A Literature Survey on Stream Data Mining

Section 1: INTRODUCTION
Description 1: Provide an introduction to the development of information technology, the significance of big data, and the importance and context of stream data mining in today's landscape.

Section 2: Characteristics of Stream Data Mining
Description 2: Discuss the unique characteristics of stream data mining in the environment of big data, such as usability, instantaneity, diversity of mode, multi-source heterogeneity, and high cognition.

Section 3: Challenges and Research Issues of Stream Data Mining
Description 3: Identify and elaborate on the key challenges and research issues faced in stream data mining under the big data setting.

Section 4: Research on the Pattern of Stream Data Mining
Description 4: Examine the patterns of stream data mining and propose new computational models to handle massive and high-dimensional data sets efficiently.

Section 5: Relative Issues of Stream Data Mining
Description 5: Explore various issues in stream data mining, such as efficient one-time stream data analysis, privacy mining, and mining in resource-constrained environments.

Section 6: RESEARCH PROGRESS IN BIG DATA-ORIENTED STREAM DATA MINING
Description 6: Provide the current state of research progress in big data-oriented stream data mining in several sub-fields, including classification, clustering, and frequent item mining.

Section 7: Stream Data Mining Based on Classification
Description 7: Detail methods of stream data classification, including integrated learning, incremental learning, and concept drift detection.

Section 8: Clustering Stream Data Mining
Description 8: Discuss various clustering methods and algorithms applied to stream data, addressing issues such as high-dimensional space and distributed computing environments.

Section 9: Stream Data Mining Based on Frequent Items
Description 9: Cover techniques for mining frequent items from stream data, such as transaction amount-based methods, time-related methods, and approximate methods.

Section 10: Other Mining Methods and Mining Quality Analysis
Description 10: Review additional stream data mining methods, such as data compression, privacy mining, and quality analysis, and how they contribute to improving the efficiency and effectiveness of stream data mining.

Section 11: CONCLUSION
Description 11: Summarize the main points of the paper, discuss the infancy of big data-oriented stream data mining, and suggest directions for future research.