基于鞅的数据流概念漂移检测方法

Method of Concept Drifting Detection Based on Martingale in Data Stream

近年来,对数据流中概念漂移的检测成为了研究热点.本文依据统计学理论提出基于鞅的数据流概念漂移检测方法(CDDBM),首先综合考虑数据分布质心和半径改变引起概念的漂移,提出有效的相异度量方法,然后对数据流采用双向统计的方法更准确地标识数据分布并映射到均匀分布序列,最后计算双重随机幂鞅的均值,并利用停时定理来判断数据流中是否有概念漂移发生.另外,检测方法中,使用合理的阈值参数控制鞅变化的峰值,从而有效地降低了误报率和失报率,提出适当尺寸的窗口有效地应对数据流的无限性且更准确地推断漂移区间.在人工和真实数据流上的实验结果表明,该方法在数值型数据、分类型数据和混合型数据上都是有效的,并能够有效地控制错误率.

Recently the research of concept drifting in data stream has been turned into a hot topic. This paper proposes a method of concept drifting detection based on martingale （ CDDBM ） in data stream according to statistical theory, firstly proposes an effective strangeness measure considering reasons of concept drifting including the centroid and radius of the data distribution, then adopts double-sided to statistics for labeling the data distribution and mapping to the uniform distribution accurately, lastly determines wheth- er a concept drifting happens in the light of the mean of double-sided randomized power martingale and the theory of stop time. In ad- dition, the method of detection uses the suited threshold to control the peak of martingale for reducing the false alarm rate and the lost alarm rate, uses appropriate size of window to deal with the unlimited stream effectively and deduces the range of the position of con- cept drifting using the window. The experimental results in artificial and real world data sets show that the method is effective in data streams including numerical, categorical and mixed-attribute, and effectively controls the error rate.