【作者】 杨春宇；

【导师】 周杰；

【作者基本信息】 清华大学 ， 控制科学与工程， 2009， 博士

【摘要】 在现代社会中,越来越多的数据以数据流的形式出现。数据流与传统静态数据的区别在于其规模的无限增长以及其中蕴含概念的不断演化,这些特点使得许多根据静态数据模型设计的数据挖掘算法不再适用,因此针对数据流的数据挖掘算法研究成为一个重要的研究方向。本文对演化数据流的聚类与分类问题进行了研究,完成了如下工作:1.提出了一种处理混合属性数据流的聚类算法。该算法利用泊松过程对数据流的产生进行建模,并将数据流中样本的连续属性与离散属性统一考虑,定义了混合属性条件下样本之间的距离。在上述定义的基础上实现了一种包含在线与离线两个阶段的数据流聚类算法。2.提出了基于产生式模型的支持向量机输出概率化算法。该算法利用正态分布模型对支持向量机原始输出值的类条件概率密度进行建模,实现了批量式分类问题中测试集上的分类器输出调整,以解决训练集与测试集中类先验概率存在差异的问题。实验表明,该算法比已有经典算法更适合于分类器输出调整。3.针对存在类先验演化现象的数据流,提出了分类器输出调整算法。该算法利用时间序列分析中的指数平滑算法以及AR模型进行数据流上类先验概率的预测,并利用预测结果进行分类器的输出调整。实验表明,该算法可以很好的处理类先验演化这种特殊的概念漂移问题。此外,针对周期性的类先验演化提出了改进的类先验概率预测算法,并成功地用于智能视频交通监控中的车辆分类。4.提出了一种处理一般概念漂移问题的线性分类器增量更新算法。针对逻辑斯蒂回归模型,在自训练的框架下用二阶泰勒展开来近似数据流的对数条件似然函数,实现了近似对数条件似然函数的增量更新,并以此为基础进行分类器参数求解。与采用梯度下降的自训练方法相比,本文提出的算法在处理复杂的概念漂移问题时更为鲁棒。更多还原

【Abstract】 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.更多还原