基于模糊聚类的数据流概念漂移检测算法-陈小东.pdf
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《基于模糊聚类的数据流概念漂移检测算法-陈小东.pdf》由会员分享,可在线阅读,更多相关《基于模糊聚类的数据流概念漂移检测算法-陈小东.pdf(6页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、第43卷第4期2016年4月计算机科学Computer ScienceV0143 No4Apr 2016基于模糊聚类的数据流概念漂移检测算法陈小东1 孙力娟h2 韩崇1 郭剑12(南京邮电大学计算机学院 南京210003)1(南京邮电大学江苏省无线传感网高技术研究重点实验室 南京210003)2摘要针对数据流中可能出现的概念漂移现象,采用改进的FCM算法进行模糊聚类,提出在大小可变的滑动窗口中通过度量相邻窗口之间的差异性来判断是否发生了概念漂移,并给出了相应的处理方法。实验表明该算法能够有效地检测出数据流中的概念漂移现象,具有很好的聚类效果和很高的时间效率。关键词概念漂移,数据流,模糊聚类,可
2、变滑动窗口中图法分类号TP301 文献标识码A DOI 101 1896jissn1002137X 20164045Detecting Concept Drift of Data Stream Based on Fuzzy ClusteringCHEN Xiao-don91 SUN Li-juanl-2 HAN Chon91 GUO J Janl2(College of Computer,Nanjing University of Posts and Telecommunications,Naming 210003China)1(Jiangsu High Technology Research
3、 Key 1aboratory for Wireless Sensor Networks,Nanjing Universityof Posts and Telecommunications,Nanjing 210003,China)2Abstract The phenomena of concept drift may occur in data stream,and how to detect it is very important in many applicationsWe used the improved version of FCM algorithm tO cluster da
4、ta in variable siding window,and measured thedifference between adjacent windows to determine whether concept drift occursThe result shows that our algorithmcan detect concept drift in data stream effectively,and has great performance in clustering quality and timeKeywords Concept drift,Data stream,
5、Fuzzy clustering,Variable sliding window1 引言随着计算机、通信技术的发展以及大数据时代的到来,在过去的十几年中产生了许多无边界、连续、高速达到的数据对象,这种类型的数据一般被人们称为数据流。常见的数据流应用领域包括:网络入侵检测系统、传感器监测系统、股票交易、电子商务交易记录等1。由于数据量大、随时间连续到达等特点使得数据流很难完全放入内存进行处理,因此一般处理数据流的算法都需要满足以下两点要求2:1)实时性,在后继数据到达之前完成前驱数据的挖掘任务;2)单次遍历性,除了保存部分概要信息外,前驱数据在处理完后被丢弃,在后继数据的处理过程中无法再次被访问
6、。而在数据流的挖掘任务中不仅仅存在上述两个难题,很多流数据的模型概念常常会随着时间而发生变化,我们称之为进化的数据流。例如,消费者的购买习惯可能随着季节、可替代品的易获得性、商场促销等因素发生变化;通过路由器的IP地址分布可能随着一次潜在的网络入侵而发生改变等等。那些考虑概念漂移的挖掘算法能够使所得模型更加贴近实际的数据对象。如何有效地检测出数据流演化过程中的概念漂移现象对于及时发现异常现象、预测数据演化趋势都具有重要的意义。聚类分析是一种常见的数据挖掘方法,它将给定的一组数据对象划分到不同的簇中,依据事先指定的相似性度量方法,使得簇内对象相似度高而簇间对象相似度低。处理数据流的聚类算法需要在
7、满足时间和内存的限制下,连续、增量地聚类不断到达的数据点,并且能够快速检测出数据流的变化情况,发现何时旧簇消失、何时新簇形成。本文在研究了一系列数据流上的聚类算法和概念漂移检测算法的基础之上,提出了一种使用模糊聚类检测数据流中的概念漂移现象的算法。本文第2节介绍现有的一些数据流聚类算法和概念漂移检测算法;第3节对数据流模糊聚类中所用到的数学符号进行定义;第4节给出本文算法的核心思想框架;第5节是本文算法的实验部分;最后总结全文。2相关工作数据流中的概念漂移现象是指在不同的时间段中产生的数据点服从不同的分布模型。目前检测数据流中概念漂移现到稿151期:2015-0408返修日期:20150615
8、 本文受国家自然科学基金(61171053,61300239)教育部博士点基金(20113223110002),中国博士后科学基金(2014M551635),江苏省博士后科研资助计划项目(1302085B),南京邮电大学引进人才科研启动基金(NY214013)资助。陈小东(1992一),男,硕士生,主要研究方向为数据挖掘,Email:823265633qqcom(通信作者);孙力娟(1966一),女,博士,教授,博士生导师,主要研究方向为演化计算、无线传感器网络和数据处理等;韩崇(1985一),男博士,讲师,主要研究方向为多媒体信息处理、数据挖掘;郭剑(1978一)博士,副教授,硕士生导师,主
9、要研究方向为无线传感器网络、无线多媒体传感器网络。219万方数据象所使用的主要手段是依据数据挖掘任务中的分类算法,依靠对未知数据预测错误率的大小判断数据流是否发生了概念漂移,如文献35。但是分类算法需要预先获得一些带有类标号的对象作为训练数据集,要想在原始的、不断进化的数据流中得到类标号是很困难的。本文采用聚类的方法检测数据流的漂移现象,放宽了算法的适用条件,使其能够适应更多的应用场景。CluStream6是最早被提出来的应用于数据流的聚类算法。它将聚类过程分成两个部分:在线部分通过设定好的删除与合并原则增量更新微簇的特征向量;离线部分使用K-means7算法将微簇聚类成最终簇,通过倾斜时间窗
10、口使用户可以在不同时间粒度内发现不同的数据簇。Philip等8提出的Stream-Detect算法使用在线聚类、离线分类的方法检测进化数据流的变化情况。在线部分比较新旧簇的聚类特征(包括聚类中心的均值、标准差、簇的平均大小和最大尺寸、最小簇中心等)、测量两者之间的偏离值,如果超出预先指定的阈值,则表示数据流有新的变化。通过离线分类处理,将数据流的变化类型分配到相应的事件或现象中。文献I-9提出了一个可以聚类随时间变化的、离散的数据类型的框架。依据滑动窗口技术,通过统计前后窗口之间孤立点的个数以及不同簇的变化率,提出一种概念漂移检测算法,并能够可视化地显示出不同聚类结果之间的演化关系。但算法中所
11、使用的滑动窗El大小固定,无法适应数据流的灵活变化情况。李培培在基于聚类概念簇差异的概念漂移检测机制算法1 o中,采用每隔一个数据块调用一次聚类算法,通过比较前后两个聚类簇集合的平均距离与聚类簇半径之间的关系来判断是否发生了概念漂移。该算法与Stream-Detect的缺点一样明显,即不管数据流是否发生了漂移,每次都需要重新聚类,时间效率很低。曹付元11提出的时序分类数据的聚类算法就很好地解决了这个问题,该算法并不简单地对每个窗口进行聚类,而是对比前后窗口的数据对象,如果差异性大,则需要重新聚类,否则直接通过数据标签技术将数据划分到前一窗口最相似的簇中。文献E12提出了一种检测增量数据集上的概
12、念漂移算法。该算法对原始样本进行初始聚类,每当有一个新的数据点到达时,Ny-1断其是否发生漂移。上述文献在检测数据流的概念漂移情况时所使用的聚类算法都属于硬聚类算法,即一个数据点对象不是完全属于这个簇,就是完全属于另一个簇。这种算法是不具有一般意义的,因为在模糊逻辑中,一个数据对象可能同时属于多个簇。FCM13算法是一个完整数据集上的模糊聚类算法。该算法通过不断迭代计算簇中心和隶属度矩阵,来求解聚类误差平方和SSE的最小值。文献14提出的SWFCM算法是对FCM算法的扩展,使之应用于数据流之上。依据数据流的到达顺序将其划分成连续的数据块,每一部分使用FCM算法处理,将所得的簇中心点和该部分所有
13、数据点在该簇的隶属度之和(作为权值)传递到下一部分,依次类推,最终得到数据流上的簇中心点。文献15对刚吓M算法进行了扩展,通过对后继数据增大权值的方法来适应数据流的漂移情况。但该算法并没有考虑概念漂移的实际发生情况,只是一种减小历史数据影响的自适应调整策略,并不能达到检测概220念漂移的目的。本文提出的基于模糊聚类的数据流概念漂移检测算法,使用改进FCM算法的初始中心点的选择方式来加速聚类过程、提高聚类质量,同时依据变化的滑动窗口提供一种检测动态数据流中是否发生概念漂移的方法以及检测之后相应聚类簇的更新方式。3符号定义本节将介绍算法中使用到的一些数学符号和模型定义。定义1(数据流模型)数据流是
14、由一串连续到达的数据点组成,形如S-m,晶,其中每个数据点sj由p个属性组成,即对,豸,s?,表示该数据点的属性值。定义2(模糊簇)模糊簇Cl是数据集S。,Sz,S。的一个子集,其中每个数据点s都有一个属于C,的介于0到1之间的隶属度1 6|。定义3(隶属度矩阵) 隶属度U是一个m聍的矩阵,其每行表示一个模糊簇,每列表示一个数据点。表示第J个数据点在第i个模糊簇中的重要程度16。性质1 对于任意的数据点Sj及模糊簇C。,都有oMi1。性质2对于任意的数据点s,都有=1。定义4(模糊簇中心) 模糊簇Cl的簇中心与每个数据点在该簇中所占的比重有关:善(端X sj)理其中,61是FCM算法中的加权指
15、数,簇中心Vi也是由P个数据属性组成。定义5(目标函数) 聚类的目标函数又称为误差平方和,是评价聚类结果对数据集拟合程度的重要标准之一。模糊聚类的误差平方和表达式如下:J妍一鸸Xdist(v_,sj) (2)其中,dist(vi,sj)表示模糊簇G的中心点与数据点si的差异性,在FCM算法中使用两者之间的欧氏距离来替代,即:厂F一dist(vi,sj)一荟(讲一砖)2 (3),娅的值越小,表示数据集的拟合程度越好,聚类质量越高。为求得式(2)的最小值,结合性质2,可得到隶属度的计算式:】蛳一孺蓊 定义6(滑动窗口) 滑动窗口是用来处理数据流挖掘任务的常规方法,依据数据点到达的先后顺序,将其依次
16、划分到大小不同的窗1:3中,记为B-,Bz,玩,滑动窗口B。中数据点的个数记为N,。定义7(概念漂移) 概念漂移是指相邻窗口B。与B中的数据点差异性超过用户预先指定的阈值,即满足下式:J?fNi+、8*j瞒ENt (5)其中,口是用户指定的阈值参数,J娅是窗口Bi的目标函数,-厂7是窗口BI中的簇中心和窗口B数据点之间的误差平方和。万方数据4 基于模糊聚类的数据流概念漂移检测算法大其尺寸以减小数据流的处理时间。具体做法如表3所列。表3滑动窗口调整策略本文提出的基于模糊聚类的数据流概念漂移检测算法首先使用改进的FCM算法对初始滑动窗口进行聚类,对比随后到达的数据点与前一阶段所形成簇的差异性,测量
17、结果如果大于预先指定的阈值则判定出现了概念漂移,需要重新聚类当前窗口中的数据以形成新的簇,否则将当前窗口的数据点融合到上一窗口最相似的簇中,同时更新相关簇信息。在检测的过程中,动态改变滑动窗口的大小以适应数据流中概念漂移出现的频率。41 改进的模糊C均值算法(ImFM)FCM算法与Kmeans算法很相似,其主要思想如表1所列。表1 FCM算法2随机分配簇中每个数据点的隶属度值,要求满足性质1和性质2。3重复如下步骤直至算法收敛(即前后两次迭代误差平方和之差的绝对值不大干E其中为预先给定的灵敏度周值):依据式(1)计算每个簇的中心;对于每个数据点使用武(4)计算隶属度矩阵。FCM是一种局部优化搜
18、索算法,若初始隶属度分配不恰当。容易陷入局部最优点。本文提出了一种新的改进的FCM算法(Reform Fuzzy Clustering Method,REFCM)。相比于FCM算法,改进的FCM算法的优点主要表现在对初始中心点选择的变化上,其思想如表2所列。表2 REFCM算法1随机选择一个教据点作为第一个簇的初始中心点。2重复如下步骤。直至所有簇的初始中心点都选取完毕:计算剩余数据点与已经得到的簇中心之间的最短距离;将最短距离依据大小顺序排列,然后接轮盘的方式选出下一个簇的初始中心点,即距离越大,在轮盘上所占的面积越大,被选中的概率越大。3对于选出的初始簇中心点依据武(4)计算每个数据点的初
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 模糊 数据流 概念 漂移 检测 算法 陈小东
![提示](https://www.taowenge.com/images/bang_tan.gif)
限制150内