大数据下数据流聚类挖掘算法的优化分析

2019-09-25杨涛张红梅王家乐周卓洁杜宏

物联网技术 2019年8期

杨涛张红梅王家乐周卓洁杜宏

摘要：随着IT技术的不断提升和完善，不管是在PC端，还是在移动端，人们借助互联网工具来实现的各种服务，都以数据的形式被记录下来，而这些数据不仅体量庞大、变化迅速，而且还呈现出一定的时序性。传统的数据分析已经不能适应如今庞大的数据流，同时不同的算法，最终所得到的处理结果也是不一样的，此时利用数据流相关的技术得到了重视和大规模的开发应用。鉴于此，文中通过明确数据流的概念和特点，并列举了常用的数据流聚类算法。充分考虑时间权值对数据流聚类的影响，在微簇中心点引入了时间衰减函数，提出F-Stream算法，分别对在线微聚类算法、离线宏聚类算法和数据流全局化缓存结构进行了优化设计。通过和CluStream算法进行时间效率、聚类质量和敏感参数的对比实验，发现F-Stream算法的整体性能更优，具有很好的聚类效果。

关键词：大数据;数据流;聚类;挖掘算法;时间衰减;F-Stream算法

中图分类号：TP274文献标识码：A文章编号：2095-1302（2019）08-00-03

0 引言

不论是在地质测量、气象、天文观测等方面，还是在互联网数据监控、无线网络信息传输等领域，数据流都发挥着越来越大的作用。由于数据流在时间上的积累，无法实现对海量数据进行随机访问，因此需要利用算法对数据进行“一次性扫描”。流数据聚类算法对新收到数据进行扫描，经过具体处理后，根据数据价值或人为设定对数据进行储存或者销毁。

特殊的数据处理方式使得流数据挖掘的研究及其应用越来越被关注，尤其是面向数据流的聚类分析、分类技术和频繁项集挖掘技术都具有非常重要的意义。

1 数据流概述

1.1 数据流的定义及其特点

数据流是一种具有顺序的数据序列，具有明确的起始与终止字节。在传输过程中保持实时高速地持续传输，其规模一般无法预知。当任意数据X1，X2，…，Xn，在时间序列T1，T2，…，Tn上依次到达，数据则视为具有时间属性的集合。实际处理过程中，通过对数据的时间属性进行限制，在特定的时间段对数据进行挖掘，也被称为在时间窗口内进行数据挖掘。常见的时间窗口分为：衰减窗口模型、滑动窗口模型、有界窗口模型等。实际中不同的模型对于数据挖掘结果有着重要的意义。

数据流中的数据和传统的存储在数据库中的数据有许多不同点：

（1）时序性。数据流中的数据是实时达到的，而且这些数据都是高速生成的，数据变化非常快。

（2）不可再现性。数据流中的数据变化非常快，同时这些数据又是高速实时到达的。

（3）无限性。在数据流中，陆续有新数据加入数据流中，理论上来说数据流的数据量是无限的。

1.2 数据流聚类算法

数据流挖掘是研究在数据流环境下对流数据进行数据挖掘。不同于对传统数据进行挖掘，数据流中的数据是随时间依次到达的而且是潜在无限的，因此不能被完整地保存下

来[1-2]。基于数据流挖掘的特点，要求面向流数据的挖掘算法只能一次或者有限几次访问数据，传统挖掘算法直接应用到流数据的挖掘效果会很差。

2 数据流聚类挖掘算法优化

本文提出的F-Stream算法是针对实际应用中人们对离当前时间最近一段时间内新到达的数据更加有研究兴趣的事实，对数据流中数据到达后形成的微簇赋予权值，充分考虑了时间权值对数据流聚类的影响，该算法主要包括两个阶段，即在线微聚类阶段和离线宏聚类阶段。

2.1 在線微聚类算法优化

在线微聚类算法对数据流进行聚类生成用于离线宏聚类的微簇，先给出微簇缓冲区内可以存放的最大微簇数N和初始微簇数量q（q≤N），即最多可以保留N个微簇在微簇缓冲区内。

以下为具体的算法描述。

输入：微簇缓冲区内可以存放的最大微簇数N，初始微簇数量q，具有时标T1，T2，…，Tn，…的数据流S=（X1，X2，…，Xn，…）;

输出：以金字塔时间框架方式存储的微簇。

（1）初始化微簇缓冲区为空。

（2）获取数据流S中第一批数据，然后利用K-means聚类算法对这些数据聚类成q个微簇（初始微簇数量q小于等于N），初始化这q个聚类微簇，并创建它们的微簇聚类特征MCF。

（3）读取数据流S中当前新到达的数据点Xi。

（4）按照公式

计算数据点Xi与微簇缓冲区中的每个聚类微簇的相似度，并将最大相似度记为S（Xi- ）。

（5）按照公式

计算微簇缓冲区中的聚类微簇与聚类微簇之间的相似度，并将最大相似度记为S（，）;

（6）如果S（Xi-）≥S（，），那么把数据点Xi加入到微簇Ci中，同时更新MCFi，否则转向步骤（7）。

//S（Xi-）≥S（，）表示数据点Xi与微簇Ci的

相似度大于微簇缓冲区内任意两个微簇之间的相似

度，所以不需要创建一个只包含数据点Xi的新的微簇

（7）如果微簇缓冲区已满，那么合并两个相似度最大的聚类微簇和同时更新微簇聚类特征MCF，并在微簇缓冲区中创建一个只包含数据点Xi的新的微簇，为其创建微簇聚类特征MCF;否则直接在微簇缓冲区中为数据点Xi单独创建一个新的微簇并为其创建微簇聚类特征MCFi。

（8）如果出现离线聚类请求，那么结束算法进入离线宏聚类阶段;否则转向步骤（3）。在线微聚类算法是数据流聚类算法的基础，在整个数据流聚类阶段中起着关键性作用。

2.2 离线宏聚类算法优化

在离线宏聚类算法中，把在线微聚类阶段产生的每个微簇Ci（i=1，2，…，N）看作一个数据点Pi，并且这个数据点具有时间权值wi，其中数据点的时间权值wi与对应微簇Ci的微簇中心点权值相等，然后利用相对密度的聚类算法进行聚类。

在介绍算法前，先假设D=（P1，P2，…，PN），数据点X，Y是集合D内的元素，wx和wy是数据点X与Y的时间权值，xi和yi是数据点X，Y的第i维属性值（i=1，2，…，d），并给出如下定义：

（1）数据点X与Y的相异度计算公式为：

（2）数据点X的k近邻集合Nk（X）={X1，X2，…，Xd}，即X到D-{X}中每一点Xi的相异度d（Xi，X）按非递减方式排序得到集合。

（3）数据点X的k近邻密度计算公式为：

（4）数据点X关于其k近邻集合Nk（X）的相对密度，简称为X的k近邻相对密度，其计算公式为：

（5）核心对象。假设阈值ε（0<ε<1），X∈D，如果|rdk（X）-1|<ε，那么称数据点X是核心对象。

（6）直接密度可达。如果X，Y∈D，X是核心对象，同时Y∈Nk（X），那么有对象Y关于核心对象X是直接密度可达的。

（7）密度可达。给定集合D，阈值ε（0<ε<1），当存在一个对象链X1，X2，…，Xn，X=X1，Y=Xn，对于任意一个Xi（i=1，2，…，n-1），如果存在Xi～Xi+1直接密度可达的，那么称X关于Y是密度可达的。

以下为详细算法步骤。

输入：数据集D、近邻个数k和阈值ε（0<ε<1）;

输出：主要是基于相对密度的聚类C={C1，C2，…，Cr}。

（1）初始化聚类C为空。

（2）从数据集D中抽取一个未处理过的点Xv。

（3）如果Xv是核心对象，且Xv不在聚类C的任何簇中，那么将Xv初始化成簇Cv，并将从Xv出发密度可达的所有对象归入簇Cv中;否则，跳转至步骤（2）。

（4）处理完D中所有对象。

（5）输出聚类C={C1，C2，…，Cr}。

3 实验结果与分析

通过F-Stream算法与经典数据流聚类算法CluStream进行对比，来验证F-Stream算法的性能。

3.1 实验数据集

在算法评价过程中，采用来自美国空军和与美国植被覆盖率有关的KDD-CUP99网络入侵检测数据集（数据集1）和Forest Cover Type森林覆盖数据集（数据集2）。

其中，数据集1由500万条左右的TCP连接记录组成，是一个模拟美国空军局域网采集的数据，时间窗口为9周，数据具有4个标志类型，9个特征。从数据集中选择10%作为聚类测试样本数据。

数据集2由58.1万条记录组成，由关于植被覆盖的真实数据组成，内涵关于土地的54个特征，其中的数据分为7种，虽然不是真正的大数据，但在实际使用中效果很好。测试中将数据集顺序输入，不改变其储存顺序。

3.2 实验数据对比

实验选取聚类时间效率、聚类质量、敏感参数三个重要指标作为对比的主要依据。通过聚类纯度评价聚类质量，利用图标直观对比。

式中：K表示簇的数量;|Cid|是在簇Ci中类标签占支配地位的数据点的个数;Ci表示簇Ci中数据点的总个数。纯度越大表明簇内的点越相似，聚类的结果也就越好。

采取聚类纯度和聚类时间速率作为对比的主要依据，分别对两个数据集利用两种算法进行处理。

在数据集1和数据集2上进行CluStream算法和F-Stream算法，在聚类纯度和聚类时间两个关键方面进行比较。

图1和图2是采用算法CluStream和F-Stream在2个数据集上所得聚类纯度，横轴表示数据流中的数据量，纵轴表示聚类纯度。从图中可以发现F-Stream算法比CluStream算法具有较高的聚类准确性。图3和图4体现了算法CluStream和F-Stream在2个数据集上的聚类时间方面的实际情况，纵轴表示算法处理数据流所消耗的时间，处理时间越短，代表聚类算法的时间效率越高、聚类速率越快。从图中可以看出F-Stream算法比CluStream算法具有更好的聚类时间效率。

本节主要介绍一种基于时间衰减的数据流聚类算法，该算法引入了时间衰减函数，降低了数据流中过往数据对聚类的影响，并且其影响因子随着时间推移持续降低。

4 结语

本文提出一种影响因子随时间降低的数据流聚类算法F-Stream。该算法针对传统的聚类算法并没有充分考虑时间权值对聚类的影响，但是实际应用中人们对离当前时间最近一段时间内新到达的数据更加有研究兴趣，在算法中引入了时间衰减函数使数据流中时间较久远的处理结果对数据流聚类的影响程度得到削弱。但是，还有很多的不足之处，仍然有一些问题需要做进一步的研究：F-Stream算法需要通过人工调整参数来对数据流实现良好的聚类效果;离线宏聚类阶段采用相对密度的方法来聚类，使得算法的时间复杂度较高，所以还需要改进。

参考文献

[1]杜航原，王文剑，白亮.一种基于优化模型的演化數据流聚类方法[J].中国科学：信息科学，2017，47（11）：1464-1482.

[2]莫徽忠.基于数据流聚类算法的网络异常检测系统设计[J].柳州职业技术学院学报，2017，17（3）：99-103.

[3]李芬田.基于滑动窗口的数据流频繁项集挖掘算法研究[D].长春：长春工业大学，2018.

[4]石秀金，蔡艺松.一种基于滑动窗口模型的数据流加权频繁模式挖掘方法[J].智能计算机与应用，2018，8（2）：63-67.

[5]郭世明，高宏.基于滑动窗口挖掘数据流高效用项集的有效算法[J].哈尔滨工程大学学报，2018，39（4）：721-729.

[6]樊超，李宏伟.利用优化的DenStream算法进行空间数据流聚类

[J].测绘与空间地理信息，2017，40（4）：73-77.

[7]傅坦坦.数据流处理系统中优化调度算法研究与实现[D].成都：电子科技大学，2017.

[8]孙宏.基于数据流的模糊聚类算法分析与优化[D].镇江：江苏科技大学，2017.

[9]周虹，富春岩，支援，等.基于硬件预处理的数据流并发连接查询优化算法[J].电脑知识与技术，2016，12（33）：25-26.

[10]马可.基于Storm的流数据聚类挖掘算法的研究[D].南京：南京邮电大学，2016.