一种对滑动窗口数据流聚类算法的混合差分研究

高瑞华　申海燕

摘 要 传统的滑動窗口数据流聚类算法在执行中存在聚类质量较差、效率较低的缺点，而基于混合差分进化的算法，将滑动窗口数据流聚类过程进行划分，一类是在线的时序窗口数据流特征向量生成，另一类是离线的聚类优化。对于在线式滑动窗口，其数据表现为微簇聚合更新与维护，可以通过粒子群算法，以离线微簇数据进行适应度计算，并将种群划分为优势子种群和普通子种群，利用个体适应度值和平均适应度值来进行最优选择，采用迭代法来对个体进行进化，输出最优适应度值的聚类集合。

关键词 滑动窗口 数据流 混合差分进化 聚类

数据聚类分析是数据挖掘中的重要课题，也是通过对数据进行层次化模型分析，对指数级数据增长下的传统聚类算法的优化，以满足数据流处理的实时要求。比较经典的算法有CluStream，将数据流看作时序读取过程，在数据处理周期内完成聚类。数据流聚类算法是基于聚类半径的增长，数据聚类精度的提升对内存消耗过大而采用的优化算法，其优势在于构建数据流聚类在线、离线框架，满足数据入点、流出点之间数据流处理需要，但由于数据快照窗口的失效数据为实时更新，导致计算机负载过大。基于滑动窗口的数据流聚类算法，能够在占用窗口大小的次线性内存空间中，对数据记录分部展开进行聚类分析.

一、数据流聚类算法基础概念明确

对于混合差分进化下的滑动窗口数据流聚类算法的研究，主要通过在线过程的微簇生成和离线下的混合差分进化算法来实现。需要对相关概念进行界定。一是窗口快照。以某t时刻数据窗口跨度为P，在[t-p，p]时刻内的数据流为DBi为窗口B的一个快照，记作。对于时序滑动窗口，以快照窗口的数据流为顺序构成时序数据流，记为SB，则某时序i的时序滑块窗口数据为：，如果窗口数为n，则时间跨度。对于时序衰减权系数的设定，假设某时刻t的时序窗口衰减权因子为%^，则，时序衰减权系数W（t）记作：；其中，v为数据流速，为当前滑动窗口时间。对于数据流微簇的设定，将当前时序滑动窗口的微簇计作CF，则，对于数据集，（F，Q）表示为样本属性的一阶、二阶矩阵，流簇样本总数为n，则数据流达到时间为RT1，失效时间为RT2，滑动窗口大小为RW，则：；对于样本聚类权重系数的设定，当某时序数据流为SB，则待识别样本Y，隶属于类别的近邻样本总数为k，则当前样本总数为m，第j个近邻样本进行聚类时，样本聚类权重系数记作l（j），则：，其中%Z表示为幂指数。对于聚类类别的判定函数，假设某数据集样本类别为，则待识别数据为Y，数据集近邻中属于类别的样本为，近邻样本总数为N，隶属于 的近邻样本数为，待识别数据Y的第j个近邻样本的类别判别函数表示为：。

二、混合差分滑动窗口数据流聚类算法

（1）算法思想。

从时序滑动窗口数据集的定义来看，，样本类别数为c，类别标识符为，则当前数据流为DB；假设时序窗口快照的数据集为，则待识别样本为，则满足两个过程：一是窗口快照中的数据为，则记作A[i]，其中包含（n+1）个数据元组；二是时序窗口更新所涉及的快照数据，其存储和失效数据的删除满足；当快照数据流被处理完后将对A[n+1]元组进行删除，令A[j]=A[j+1]，则快照窗口的数据存储于A[j]。可见，对于混合差分算法下的滑动窗口数据流聚集算法的应用，主要从在线和离线两种过程中来完成。在不同数据流流速下，在线聚类是结合时序滑动窗口、快照窗口来对数据流的粒度和流速进行微簇特征向量存储，而离线聚类是对微簇特征向量的数据流粒度进行优化聚类。

（2）在线聚类算法研究。

对于微簇特征向量的生成主要依据DBSCAN算法来实现微簇的集合，其方法如下：一是对微簇变量设置并初始化num=0；利用DBSCAN算法，假设对象p的簇半径r

（3）离线下数据流聚类优化研究。

离线下的微簇数据集聚类优化，主要采用混合差分进化算法来提升可执行性。先以粒子群算法为例，就进化算法进行改进。粒子群算法是粒子在空间维度下以特定速度飞行，其位置是动态调整的。假设某粒子群规模为M，空间维度为D，则第i个粒子在第d维空间的位置集合表示为：；粒子速度集合为：；个体位置优化集合：；种群全局位置优化集合为：；则粒子i在第（t+1）时刻的速度及位置更新策略为：；对于表示为粒子的加速系数，对于表示为[0，1]区间内的随机数。从粒子群算法中进行全局最优迭代计算时，因计算量较大，粒子变化趋势变化趋缓，导致粒子活动降低，出现计算收敛难度；利用惯性系数来导入粒子群算法，从全局最优调节中来提升算法效率，其粒子速度更新机制为；利用最优算法，主要是满足对粒子速度求解是否最优进行判定，当前适应度函数值与上一时刻进行比较，若趋于更优则对当前数值进行更新；利用粒子惯性函数进行赋值，若为线性递减，则极限点未必是真正的动态极限点，从而对当前粒子速度带来偏离影响，需要从粒子权值上进行改进。

（4）差分进化算法研究。

从粒子群算法来进行数据聚类应用，仅仅是从权系数上来调整，因本身算法的局限，无法避免适应度值的最终趋向一致的结果。尽管在种群活性上进行改进，但由于更新机制中受到个体学习认知能力制约，仍然存在局部极值点缺陷问题。为此，混合差分进化算法，将差分进化算法作为基础，并从遗传算法中借助于单纯行算法进行差分变异算子，使其获得更优的性能和稳定性。在探讨混合差分进化算法之前，需要对差分进化算子进行说明，差分进化算子主要有变异、交叉和选择，用DE/x/y/z来标记。对于式中的x表示为基向量类型；y表示为变异操作差分向量个数；z表示为交叉操作类型。在本文中对混合差分进化算法的运用，首先是利用粒子群算法来进行种群分析，依照不同个体的平均适应度值进行划分，对于适应度低的子种群采用粒子群算法进行优化；对于适应度值高的个体采用差分进化算法，即：

（5）混合差分进化聚类算法优化。

从离线下聚类算法的优化主要采用混合差分进化算法，其实施步骤为：首先读取内存中的微簇数据；然后对微簇mc半径内的特征向量进行随机初始化，并计算其位置和速度；再次对待识别的数据对象进行计算，包括微簇中粒子对应的聚类中心距离，计算粒子环境权系数，以进行粒子速度、粒距分类；然后对各粒距聚集度权重进行计算并更新；对各种群进行適应度值计算，依据；对于表示为第i个聚类中心，对于表示为聚类间距的调整权重；通过计算各平均适应度值，对种群进行分类，对于大于平均适应度值的个体采用差分进化算法优化；对于小于平均适应度值的个体，采用粒子群算法进行优化；最后根据个体适应度值的比较来进行个体极值、全局极值的更新，保存最新解，依次迭代进行聚类优化获得最终聚类集合。

三、结语

通过对数据流聚类算法的研究，对于滑动窗口下数据信息进行混合差分进化算法优化，主要集中在离线阶段，而对于在线阶段，以数据流微簇特征向量和粒度信息微簇生成、更新和存储即可。通过对滑动窗口模型的分段划分，避免了数据流规模较大时带来的执行效率问题；同时，利用混合差分进化算法，在一定程度上改进了算法能力，也对聚类算法提升了执行效率，减少了对内存的过度依赖，确保每次迭代算法中实现最优的搜索能力。

参考文献：

[1]朱琳，刘晓东，朱参世.基于衰减滑动窗口数据流聚类算法研究[J]. 计算机工程与设计，2012（07）.

[2]刘燕驰，高学东，国宏伟，武森.应用分类方法进行聚类评价[J].计算机应用研究，2011（10） .

[3]吴学雁，黄道平.基于形态特征的数据流聚类方法研究[J].计算机工程， 2011（13）.

[4] Lisa M. Sweeney，Ann Parker，Lynne T. Haber，C. Lang Tran，Eileen D. Kuempel.Application of Markov chain Monte Carlo analysis to biomathematical modeling of respirable dust in US and UK coal miners[J]. Regulatory Toxicology and Pharmacology ， 2013 （1）.

[5]于彦伟，王沁，邝俊，何杰.一种基于密度的空间数据流在线聚类算法[J].自动化学报，2012（06）.

（作者单位：河南财政税务高等专科学校）