资源描述：
《一种基于优化模型的演化数据流聚类方法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、中国科学:信息科学2017年第47卷第11期:1464–1482SCIENTIASINICAInformationis机器学习专题.论文一种基于优化模型的演化数据流聚类方法11,2*2杜航原,王文剑,白亮1.山西大学计算机与信息技术学院,太原0300062.计算智能与中文信息处理教育部重点实验室,太原030006*通信作者.E-mail:wjwang@sxu.edu.cn收稿日期:2017–05–16;接受日期:2017–06–19;网络出版日期:2017–11–03国家自然科学基金重点项目(批准号:61432011,U1435
2、212)、国家自然科学基金(批准号:61673249)和山西省青年科技研究基金(批准号:201701D221097)资助项目摘要本文针对数据流演化聚类问题,建立了基于模糊最大熵的优化模型,利用模糊隶属度表达类别划分的模糊性,通过信息熵描述类别划分的有效性.在此基础上定义了优化目标函数,在滑动窗口下将数据子集的聚类过程理解为一个优化问题,使聚类结果能有效描述数据内在结构特征,同时维持相邻窗口间聚类模型的连续性.将优化问题的解作为概念漂移检测的依据,保证了检测结果的有效性,有利于捕获聚类结构的变化趋势.在仿真实验中,利用人造数据集和
3、真实数据集对新算法的有效性进行了验证,并通过实验与多种演化聚类方法在聚类精度、概念漂移检测精度以及计算效率等多个方面进行了比较.仿真结果表明了该算法的有效性,在相同条件下其聚类精度和概念漂移检测精度相比其他聚类算法具有显著优势,能够同时降低计算耗费时间和存储空间.关键词数据流,演化聚类,优化模型,模糊隶属度,信息熵1引言随着计算机网络和无线传感网络的大量应用,在各个领域中大量数据以数据流的形态不断产生,例如,金融交易信息、电话呼叫记录、交通监测数据、网络访问日志、疾病监控数据等[1].相比传统的静态数据库形态,数据流已经成为一种
4、新兴且日趋重要的数据存在形式.其典型特征包括[2∼4](1)新数据不断产生,数据总量潜在无限;(2)新数据产生的速度和时间间隔可能难以确定;(3)数据高速流动,对其扫描次数仅限于单遍;(4)受多方面原因影响,数据底层分布模型可能随时间发生变化.对于这种蕴含大量信息的数据流,人们迫切需要从中获取感兴趣的知识和规律,同时新数据的不断产生和动态变化使得传统的数据挖掘方法难以取得良好效果,因此对数据流进行挖掘和分析是一项具有重要实际意义且极富挑战的工作.聚类分析作为一种能够探测数据类别结构的无监督学习方法,在数据流的模式发现和知识挖掘中
5、存在巨大潜力[5].对数据流进行聚类分析,就是在对当前到达数据进行分簇引用格式:杜航原,王文剑,白亮.一种基于优化模型的演化数据流聚类方法.中国科学:信息科学,2017,47:1464{1482,doi:10.1360/N112017-00107DuHY,WangWJ,BaiL.Anovelevolvingdatastreamclusteringmethodbasedonoptimizationmodel(inChinese).SciSinInform,2017,47:1464{1482,doi:10.1360/N112017-
6、00107⃝c2017《中国科学》杂志社www.scichina.cominfocn.scichina.com中国科学:信息科学第47卷第11期的同时,随着新数据的不断获得,对聚类结果进行动态更新和调整,以获取反映数据流内在结构的可靠聚类形态.相比静态数据的聚类分析,数据流增量更新和在线调节的特征对聚类分析方法提出了新的要求和挑战[2].研究人员针对数据流的聚类问题开展深入研究,将静态数据集上的经典聚类方法进行了改进和拓展,提出了一些全新的思路和解决方法.在早期的数据流聚类研究中,人们将数据流视为大数据集的特殊情况,假定数据流整
7、体服从某一未知分布,将数据流聚类限定为单遍扫描获得数据集的聚类结果,将传统聚类方法应用于数据流,相继提出了BIRCH算法、STREAM聚类算法、IncrementalK-Means算法、数据流网格聚类、数据流层次聚类等方法[1,6∼9].而事实上,数据流中蕴含的模型和结构可能处于不断变化中,对这些变化进行分析和了解能帮助我们对事物发展的客观规律有更好的认识.针对这一需要,有学者提出了演化数据流聚类,认为数据流中隐藏的模型是动态变化的,利用时间窗口模型对数据流进行分段处理.例如,CluStream[10]将演化聚类分为在线聚类和离
8、线分析两个步骤,在线聚类对不断到达的数据维护微簇结构,并保存在不同时间粒度的金字塔时间结构中,离线分析阶段生成特定时间段的聚类结果.SWClustering算法[11]将指数柱状图(exponentialhistogram,EH)与时间聚类特征(temporal
