基于聚类分区的多维数据流概念漂移检测方法  

Concept Drift Detection Method for Multidimensional Data Stream Based on Clustering Partition

作　　者：陈圆圆 王志海[2] CHEN Yuan-yuan;WANG Zhi-hai(School of Computer and Information Technology,Beijing Jiaotong University,Beijing 100044,China;Beijing Key Laboratory of Traffic Data Analysis and Mining,Beijing Jiaotong University,Beijing 100044,China)

机构地区：[1]北京交通大学计算机与信息技术学院,北京100044 [2]北京交通大学交通数据分析与挖掘北京重点实验室,北京100044

出　　处：《计算机科学》2022年第7期25-30,共6页Computer Science

基　　金：国家自然科学基金(61771058)。

摘　　要：对数据流中的潜在信息进行分析和利用是数据流挖掘工作的重要内容。然而,数据的分布会随着时间的推移发生变化,从而使学习假设发生更改,这就是概念漂移现象,它给数据流挖掘带来了巨大的挑战。检测数据分布的变化是一种直接且有效的概念漂移检测方法,目前,已有研究方法基于树型结构或网格结构建立直方图,实现对数据分布的描述,但是,此类方法在进行分布检测时容易产生检验盲点,其可解释性较差,并且在多维数据上的内存消耗较大。文中提出了一种基于等密度分区的概念漂移检测方法PUDC(Partition Based on Uniform Density Clusters),该方法基于改进的k-Means算法,对数据进行等密度分区,利用卡方检验对每个分区进行统计和计算,从而检测数据分布变化,以达到概念漂移检测的目的。为了验证方法的有效性,选取了4个人工数据集和3个真实数据集进行实验,对比分析了不同维度的数据下的I类错误率和II类错误率,实验结果表明,PUDC算法在多维数据流的概念漂移检测中相比几种较新的算法具有一定的优势。The analysis and utilization of potential information in data stream is an important part of data stream mining.Concept drift is a huge challenge for data stream mining that the distribution of data will change with time.Detecting changes in data distribution is a direct and effective method to detect concept drift.Currently,some concept drift detection methods use the tree structure or grid to establish a histogram to describe the data distribution.However,the tree structure is easy to produce inspection blind spots and leads to poor interpretability.While using the grid method on multi-dimensional data,the memory consumption is too much.To solve the above problems,a concept drift detection method for multi-dimensional data streams called partition based on uniform density clusters(PUDC)is proposed.The algorithm is based on the k-Means algorithm to partition the data with uniform density and uses the chi-square test for statistics and calculation of each partition to detect the concept drift.To ve-rify the validity of the method,four artificial datasets and three real datasets were selected for experiments.The type I and type II error rates of different dimensions of data were compared and analyzed.Experimental results show that PUDC algorithm is superior to several new algorithms in concept drift detection of multi-dimensional data streams.

关 键 词：数据流挖掘 概念漂移检测 K-MEANS 假设检验 直方图 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]