Clustering And Classication Algorithms For Data Stream

In modern society, more and more data is generated in streaming format. The maindi?erences between data stream model and traditional static data model are growingand concept drifting. These characteristics make the data mining algorithms designedfor static data model are not valid for streaming model anymore. Therefore, some spe-cific algorithms are proposed for data stream mining accordingly. In this thesis, severalalgorithms for data stream clustering and classification are proposed. Specifically, themain contribution of this thesis is as follows:1. This thesis proposes an algorithm to handle the heterogeneous stream clusteringproblem. A Poisson model is used to describe the arriving process of the samples in thestream. The distance metric between heterogeneous samples is defined by consideringboth continuous and categorical attributes simultaneously. Based on such definition, atwo-step clustering algorithm containing online and o?-line steps is realized.2. This thesis proposes an algorithm for the probabilistic outputs of Support VectorMachines (SVM) using generative model. A univariate normal distribution model isused to approximate the within class density of the unthresholded outputs of SVM.According to this model, the output of the classifier on the test set is adjusted in orderto make up the decrease of the classification accuracy caused by the disparity betweenthe class priors on the training set and the test set. The proposed algorithm achievedhigher classification accuracy on some data sets than the classic algorithm.3. This thesis proposes a general classifier adjusting algorithm to deal with theclass priors evolution over the data stream. The algorithm uses exponential smooth-ing and AR model to forecast the class priors along the data stream dynamically, andadjusts the outputs of the classifier accordingly. Experimental results show that theproposed algorithm can handle the changing class priors problem well. Besides, thealgorithm is modified to make use of the periodicity in the seasonal class priors evolu-tion. The modified algorithm has been successfully applied to the vehicle classification problem in a smart video tra?c surveillance system.4. This thesis proposes an incremental linear classifier updating algorithm for thegeneral concept drift problem. Under the self-training framework, the second orderTaylor expansion is used to approximate the logarithmic conditional likelihood of thenew observed samples described by logistic regression model. Based on such approx-imation, the approximated log conditional likelihood can be updated incrementally.Then the parameter of the classifier is solved by maximizing the approximated logconditional likelihood. Comparing to the self-training method based on the gradientdescent algorithm optimizing the log conditional likelihood directly, the proposed al-gorithm is more robust when handling sophisticated concept drift.