一种对数据流进行聚类的改进算法

吴 陈，孙 宏

（江苏科技大学江苏镇江212003）

一种对数据流进行聚类的改进算法

吴 陈，孙 宏

（江苏科技大学江苏镇江212003）

针对套用传统的聚类方法对数据流的聚类是行不通的这一问题，提出一种以遗传模拟退火算法为基础的模糊C均值聚类算法（SAGA_FCM）对数据流进行聚类。SAGA_FCM算法有效地避免了传统的模糊C均值聚类算法（FCM）的最终聚类结果依赖于其初始值的选取，也解决了其容易陷入局部最优解的问题。通过将SAGA_FCM算法和FCM算法聚类数据流的实验结果进行对比，得出采用SAGA_FCM算法聚类数据流会取得较好的效果。

模糊C均值算法；遗传模拟退火算法；数据流；聚类

随着互联网发展的不断深化以及大数据时代的到来，在比如网络监控、环境监测、证券交易等众多领域中出现的数据具有自身的某些特性，不同于传统的静态数据，我们称其为数据流[1-5]。数据挖掘就好比从一大堆废物中捡“宝贝”一样，它要求我们做到从繁多的数据中找到仅对我们有实际价值的信息。我们一般采用聚类分析来对数据进行分析和处理，所谓聚类就是按数据的相关性将其分到不同的簇中，同一簇中相关性尽可能极大，相反不同簇中相关性尽可能极小，可理解为“物以类聚”[6-7]。由于受到以下几点条件的制约在聚类数据流时我们不能够再照搬传统的数据挖掘方法：数据流的产生方式是动态的不停歇的，须对它进行连续性的挖掘；没有足够大的空间用来存储这无限的数据；数据流到达具有时间有序性，对其只能实现单次线性扫描；数据流的模式不断发生变化[1，8-10]。

因此在传统的聚类算法的基础人们不断地去研究如何去聚类这些类似流水一般的数据。如鼻祖Brich算法，还有如Stream算法、以及在Brich算法的基础上加以改进的CluStream算法等虽然可产生不错的聚类效果，但它们均属于硬聚类算法，硬聚类可理解“非此即彼”，但在日常生活中我们所使用的都是些模糊概念（亦此亦彼），故这些硬聚类算法压根不具有普遍意义[11-13]。

模糊C均值聚类算法（FCM）虽然是一种典型的模糊算法，但其本身是有一定缺陷存在的比如它很容易就会出现局部收敛[14]。为了避免这个问题的困扰我们可以尝试用一定的概率来接受一个相比较当前解来说不是怎么好的解，恰好遗传模拟退火算法就具备这一优点。因此文中在分析了数据流的特性以及FCM算法后，提出将基于遗传模拟退火算法的FCM算法作用于数据流上，以达到更优的聚类效果。

1 模糊C均值聚类算法

设X={x1,x2,...,xm}，其中m为样本的数据总数，FCM算法思想便是将X进行划分，划为n个不同的簇（组）（ 2≤n≤m），这n个簇分别用A={A1,A2,...,An}来进行表示，最后须求解出能够使目标函数到达最小值（记为Jmin）的每个簇里的簇中心点。

目标函数公式如式（1），且要满足下面式（2）式（3）两个约束条件：

其中μjk表示xj对于Ak的隶属度，djk是xj到Ak的中心点的欧氏距离，c(＞1)为加权参数。

用式（4）、式（5）循环迭代得到满足要求的U=[μjk]m×n和V=(v1,v2,...,vn)，其中U为相似分类的矩阵，V为各类的聚类中心。

FCM算法过程如下[15]：

步骤1设定数据集个数m，和参数c；

步骤2初始化隶属度矩阵U；

步骤3通过式（5）来计算聚类中心V；

步骤4通过式（1）来求目标函数值J，若J=Jmin则终止迭代；

步骤5利用式（4）计算新的U，转到步骤3。

FCM算法对于初始化数据的依赖极强，且容易收敛于一个局部最优解而一个好的聚类是要达到全局收敛的效果，因此要对其进行改进。

2 遗传模拟退火算法

在群体演化的过程当中，一些极少数的个体的适应度和其他个体相比较的话大出来很多，所以经过几代人的繁衍以后，这些个体就会占据整个种群，这样就会出现过早收敛这种我们并不想让其出现的结果。遗传模拟退火算法（SAGA）这一算法是将模拟退火算法（SA）和遗传算法（GA）相融合，通过使用SA、使得GA的参数选择更加容易，SAGA通过遗传操作让子代与父辈竞争，子代遵循Metropolis准则，从而有效地避免了早熟现象，且随着个体的进化，温度T逐渐降低，从而提高了收敛的速度[7]。

Metropolis准则：设f为产生的新的个体的适应性，f,为变动阀值，当f,＞f，用新产生的个体来替代旧的个体，不然就以概率来接纳新产生的个体。这里个体适应度和最小目标函数Jmin之间是一种反比关系，即。

遗传模拟退火算法过程如图1所示。

图1 遗传模拟退火算法的流程图

遗传算法和模拟退火算法两者间通过去粗取精，有效地避免了传统的遗传算法的结果是早熟的这一现象的出现，与此同时也依据想要聚类信息的具体实际情况设计适应度函数并用最佳的方式来进行遗传编码，以使算法更加快速有效地收敛于全局最优解。

3 SAGA_FCM算法用于数据流聚类的过程

由数据流的特性知其到达有一定的时间顺序，故按其到达时间将数据流分成不同的块（主机内存决定块的大小），分别用n1,n2,...,ns来表示数据块M1,M2,...,Ms中含有数据点的总个数。该文中针对数据流聚类的方法的过程如下。

SAGA_FCM算法用于数据流聚类的过程：

步骤1初始化算法中的各个参数：种群大小size，最大迭代次数MAX，初始温度T0，终止温度Te，冷却系数α，交叉概率pc，变异概率pm；

①若q=1，随机的初始化c个聚类中心，转至步骤4；

②若q＞1，转至步骤3；

步骤3向Mq中加入Mq-1的聚类中心点，并将这些聚类中心点看作是Mq的聚类中心；

步骤4对Mq使用SAGA_FCM进行聚类

①对种群进行初始化，计算种群中每个个体适应度fk；

②设置种群迭代计数gen＝0；

③利用遗传算法对种群进行选择、交叉、变异等操作，使用式（5）和式（4）计算所产生的新个体的聚类中心和隶属度，以及每个各体的适应度fk,，若则旧的个体就会被新产生的个体替换掉，不然则以概率接受新个体；

大学里的跳蚤市场就是解决学生们的闲置物品，而跳蚤市场的时间地点由学校决定，因此有些同学不能及时参加或者是其他因素而直接放弃该次跳蚤市场。还有的是在不举行跳蚤市场的时候，有些同学又想将手中的闲置物品交易却找不到渠道出售，往往大多数同学会将其中的一些物品当作废弃品而扔进了垃圾桶里，白白浪费了资源。虽然有闲鱼、二手交易市场等网站，但那些都是所有群体的，有些小件的商品估计邮费都比不上，根本解决不了大学的闲置物品交易的需求，所以就需要一个便于校园闲置商品交易的平台。

④如果gen＜MAX，则gen＝gen＋1，转至步骤③，否则转至步骤⑤；

⑤如果Tk＜Te，该数据块聚类结束，返回聚类中心和隶属度矩阵。否则执行如下降温操作Tk+1=αTk，转至②；

步骤5如果p＝＝s，则输出全局最优解，不然则转至步骤2。

4 实验结果

本文实验是基于MATLAB平台实现，所有实验都是在一个4G内存、酷睿i5双核CPU、操作系统为Windows7的主机上运行的。

在参数设置方面，本文所提的SAGA_FCM和标准FCM中最大迭代次数MAX都设为50，目标函数J的加权指数c=3。

由于模拟退火算法的收敛结果受冷却系数以及初始温度的影响相对较大，经过试验分析，初始温度定为80，冷却系数为0.8，终止温度定位0.2。

表1是本文实验所用的数据集，该文所使用的数据集主要来自UCI Machine Learning Repository。表2是SAGA_FCM和FCM在整个数据流上目标函数的比较

表1 本文实验所用数据集

除了为最后一个数据块分有601个数据点外其它数据块中的数据点总个数均为1 000个。

表2 SAGA_FCM和FCM在整个数据流上目标函数的比较

图2 SAGA_FCM和FCM的目标函数值折线图

从图2中可直观的看出，SAGA_FCM的聚类效果明显优于FCM，从而证实了本文所提的SAGA_FCM算法比FCM算法可以寻找的更好的全局最优解。

5 结 论

以上就是所提出的基于遗传模拟退火算法的数据流聚类算法，称为SAGA_FCM。SAGA_FCM是将数据流进行分块处理，采用一种分治的方法，且会在当前解得邻域中，以概率p选择一个非全局最优解，并继续重复下去，从而避免了FCM算法容易陷入局部最优的缺陷。接下来我们可以研究改变已有数据块的大小会对聚类效果产生怎样的影响，以及怎样更好的把握控制参数的设置，提高搜索速度。

[1]孙力娟，陈小东，韩崇，等.一种新的数据流模糊聚类方法[J].电子与信息学报，2015，37（7）:1620-1625.

[2]张博，陈光，王旭.基于数据流模型的模糊聚类[J].计算机工程与应用，2010，46（33）:124-126.

[3]郭躬德，李南，陈黎飞.一种基于混合模型的数据流概念漂移检测算法[J].计算机研究与发展，2014，51（4）:731-742.

[4]安鹏.数据流聚类算法的研究[D].哈尔滨:哈尔滨工业大学，2012.

[5]汪仁红.基于聚类分析的数据流处理算法[D].重庆:重庆交通大学.2013.

[6]程军锋.数据流挖掘技术研究[J].洛阳师范学院学报，2014，33（2）:37-39.

[7]史峰，王辉，郁磊，等.Matlab智能算法:30个案例分析[M].北京:北京航天航空大学出版社，2011:188-196.

[8]张丹丹.面向数据流挖掘的分类和聚类算法研究[D].北京:北京交通大学，2014.

[9]徐天音.数据流挖掘中的聚类方法综述[D].南京:南京大学，2010.

[10]江楠，徐秦.数据流聚类算法在数据处理中的应用[J].电子科技，2015，28（1）:155-157.

[11]李子柳.大数据实时流式聚类处理框架研究[D].广州:中山大学，2013.

[12]林辉.改进模糊聚类在数据流中的应用[J].河南科学，2012，30（9）:1243-1245.

[13]胡伟.一种改进的动态k-均值聚类算法[J].计算机系统应用，2013，22（5）:116-121.

[14]潘国涛.数据流聚类算法研究[D].浙江:浙江工业大学，2011.

[15]Jiawei H，Micheline K Jian P.范明，孟小峰.数据挖掘:概念与技术[M].3版，北京:机械工业出版社，2012.

An optimized algorithm for data stream clustering

WU Chen，SUN Hong
（Jiangsu University of Science and Technology，Zhenjiang212003，China）

Due to data stream cannot be clustered by using the traditional clustering methods，raising a data stream clustering method，which is based on Simulated Annealing Genetic Algorithm Fuzzy C Means（SAGA_FCM），is proposed.The method proposed in the current work effectively avoid the disadvantages of traditional FCM method，which relies on the initial values.The method also avoid the local optimization problems.In the current work，the data stream clustering algorithms based on SAGA_FCM and FCM are compared.Based on experimental observations，algorithm SAGA_FCM proposed in the current work achieves better clustering effects.

fuzzy C-means；simulated annealing genetic algorithm；data stream；clustering

TN0

A

1674-6236（2017）22-0023-03

2016-09-02稿件编号：201609013

吴陈（1962—），男，湖北武汉人，博士。研究方向：数据挖掘与知识发现。