基于聚类分析的数据挖掘方法研究

黄蓉

湖南科技职业学院,湖南长沙410007

基于聚类分析的数据挖掘方法研究

黄蓉

湖南科技职业学院,湖南长沙410007

针对FCM算法的聚类效果易受其初始中心位置影响和易陷入局部最优的缺点，将灰狼优化算法和FCM结合，提出一种基于GWO优化FCM的聚类分析方法。以KDD CUP99数据集为研究对象，研究结果表明，与PSO、GA和SA算法相比较，GWO算法聚类分析的准确率和误判率更低，具有更快的收敛速度，效果更优，从而为数据聚类分析提供新的方法和途径。

聚类分析;数据挖掘

聚类分析是数据挖掘技术中一项重要技术，其根据一定规则将数据集分成若干组或者若干类的过程，同组或者同类数据具有一定相似度，不同组或不同类中的数据在划分规则上不具相似性。目前，聚类分析被广泛地应用于模式识别、图像处理、市场分析和数据分析等领域。目前聚类理论较为完善的算法为FCM算法和K-means算法。FCM算法[1]具有算法简单、收敛速度快、处理大数据集等优点，但其聚类结果易受初始中心位置影响，且结果容易陷入局部极小值。

针对FCM算法易受初始中心点位置和陷入局部最优的缺点，将灰狼优化算法[2]（Grey Wolf Optimization，GWO）和FCM算法结合，提出一种GWO优化FCM的聚类分析方法，避免FCM算法陷入局部最优。

1 FCM算法

FCM聚类分析的目标函数如公式（1）所示[3]：

若p表示样本Xj的维数，则X={X1,X2,...Xj,...XN}表示为p×N的矩阵；N表示样本数目；C表示聚类数目；uij⊆U(p×N×C)表示矢量Xj隶属于第i类的隶属度函数，满足uij∈[0,1]且；聚类中心Z={Z1,Z2,...,Zi,...ZC)表示p×C的矩阵，uij和Zi根据公式（2）进行聚类迭代更新：

对于每个模糊隶属度，由m∈(1,∞)控制模糊度的权重指数；d2(Xj,Zi)=ǁXj-Ziǁ表示相似性测度。P表示数据样本数据的维数；N表示数据点数目；Xi表示数据第i个特征；C表示聚类类别数；uij数据点i属于第j类的隶属度；Zi表示第i类聚类中心。FCM算法聚类过程如下：

Step 1：确定C和m，设定迭代停止阈值ε＞0，置迭代次数t=0，初始化聚类中心Z。

Step 2：计算隶属度矩阵：

Step 3：计算新的聚类中心：

Step 4：若║Z(k+1)-Z(k)║＜ε停止，否则k=k+1转Step 2。

2 GWO优化算法

灰狼优化算法（Grey Wolf Optimizer，GWO）是受灰狼觅食行为启发而提出的群智能算法，在GWO算法中，灰狼种群被划分成为α、β、δ、ω四类。优化过程中，狼群根据公式（1）和公式（2）更新种群位置[4,5]，其位置更新机制如图1所示，处于位置（X，Y）的灰狼可根据其附近猎物位置进行重新定位。

图1 狼群位置更新机制Fig.1 Location update mechanism for wolves

图2 GWO算法位置更新Fig.2 Location update mechanism for GWO

图1中，虽然灰狼有8个可能位置，随机参数A和C允许灰狼转移到任何位置在周围猎物附近的连续的空间内。在GWO算法中，总是假定α、β、δ是猎物最可能的位置（最优位置）。在优化过程中，到目前为止的前三个变量的最优解分别被设定为α、β、δ。之后，其他灰狼被看成ω，能够根据α、β、δ进行重新定位。重新调整狼群ω的位置的数学模型如下[5]：

Step 1：依据变量的上限和下限，随机初始化产生种群；

Step 2：计算每个灰狼的目标函数值（适应度函数值）；

Step 3：选择前三个最优灰狼，并将其保存为α、β、δ；

Step 4：根据公式（7）-公式（13），更新其他狼群（狼群ω）的位置；

Step 5：更新参数α、A、C；

Step 6：若不满足停止准则，则返回Step 2；

Step 7：返回α的位置作为最优近似解。

3 基于GWO算法优化FCM算法

为避免FCM陷入局部最优和最优聚类初始中心点的选择，适应度函数如公式（14）所示[6]：

其中，k表示常数，Jm(U,Z)表示总的类间离散度和。若聚类效果越好，则Jm(U,Z)越小，个体适应度Fitness(C,m)就越高。GWO优化FCM算法聚类流程如下：

Step 1：GWO算法参数设置，种群规模N和最大迭代次数Iteration，根据搜索空间，随机产生a、A、C；

Step 2：依据变量的上限和下限，随机初始化产生种群；

Step 3：计算每个灰狼个体适应度，并进行排序；

Step 4：根据适应度大小，选择前三个最优灰狼个体，并将其保存为α、β、δ；

Step 5：根据公式（7）-公式（13），更新其他狼群（狼群ω）的位置；

Step 6：更新参数α、A、C；

Step 7：判定算法是否满足停止准则。若满足，则终止，获得最优聚类中心；否则，返回Step 3；

图3 GWO优化FCM聚类分析流程Fig.3 Clustering Analysis Process based on GWO_FCM

4 实验分析

4.1 数据来源

为了验证GWO算法优化FCM聚类分析的有效性和可靠性，计算机操作系统为Windows7，选择MATLAB2015（a）软件为聚类数据分析平台，内存4GB、处理器P4 2.4GHZ。以KDD CUP99数据集为研究对象[7]，验证算法的有效性。该数据集每一组记录数据包括41个特征属性。

4.2 评价指标

为验证聚类分析的效果，选择准确率Accuracy和误判率Falseij[7,8]为聚类分析效果的评价指标。

（1）准确率Accuracy：若正确判断的类型数目为a，实际的类型数目为b，数据类型判断的准确率为：

（2）误判率F alseij：若a为第i类数据类型的实际数目，c表示将第i类数据类型误判为第j类数据类型的数目，则数据类型判断的误判率为：

4.3 实验结果

为了验证聚类分析的可靠性和有效性，将本文算法和PSO_FCM[8]、GA_FCM[9]和SA_FCM[10]的进行对比，对比结果如表1和图4-图7所示。

表1 不同算法评价结果Table 1 Evaluation Results for Different algorithms

由表1和图4～7结果对比发现，本文算法的数据聚类分析准确率和误判率分别为98.41%和1.59%，优于PSO_FCM、GA_FCM和SA_FCM和FCM的数据误判率和诊断准确率，效果最优。通过本文算法和PSO_FCM、GA_FCM和SA_FCM和FCM的对比发现，本文算法可以有效提高数据聚类分析的准确率和降低误判率，为数据聚类分析提供新的方法和途径。

图4 GWO_FCM聚类结果Fig.4ClusteringresultsofGWO_FCM

图5 PSO_FCM聚类结果Fig.5ClusteringresultsofPSO_FCM

图6 GA_FCM聚类结果Fig.6ClusteringresultsofGA_FCM

图7 SA_FCM聚类结果Fig.7ClusteringresultsofSA_FCM

5 结论

针对FCM算法聚类效果易受其初始参数影响和易陷入局部最优的缺点，将灰狼优化算法和FCM结合，提出一种基于GWO优化FCM的聚类分析方法。以KDD CUP99数据集为研究对象，研究结果表明，与PSO、GA和SA算法相比较，GWO算法聚类分析的准确率和误判率更低，具有更快的收敛速度，效果更优，为数据聚类分析提供新的方法和途径。

[1]刘宜平,沈毅.一种FCM聚类算法的改进与优化[J].系统工程与电子技术,2000,22(4):1-3

[2]Mirjalili S,Mirjalili SM,LewisA.Grey Wolf Optimizer[J].Advances in Engineering Software,2014,69(3):46-61

[3]张少敏,赵硕,王保义.基于云计算和量子粒子群算法的电力负荷曲线聚类算法研究[J].电力系统保护与控制,2014(21):93-98

[4]MirjaliliS.HoweffectiveistheGreyWolfoptimizerintrainingmulti-layerperceptrons[J].AppliedIntelligence,2015,43(1):150-161

[5]Saremi S,Mirjalili SZ,Mirjalili SM.Evolutionary population dynamics and grey wolf optimizer[J].Neural Computing andApplications,2015,26(5):1257-1263

[6]陈寿文.基于Chebyshev映射的混沌粒子群融合FCM聚类算法[J].计算机应用与软件,2015,32(7):255-258

[7]周选林,冯晓,钟明权,等.基于遗传算法的FCM聚类分析在边坡稳定性评价中的应用[J].路基工程,2014(1):1-4

[8]张永库,尹灵雪,孙劲光.基于改进的遗传算法的模糊聚类算法[J].智能系统学报,2015(4):627-635

[9]蒋君,徐蔚鸿,潘楚.基于粒计算和模拟退火的K—medoids聚类算法[J].计算机仿真,2015,32(12):214-217

[10]任昌荣.基于MCQPSO-SA优化的KFCM算法在入侵检测中的应用[J].计算机与现代化,2015(2):90-94

Study on Data Mining Based on ClusteringAnalysis

HUANG Rong
Hunan Vocational College of Science and Technology,Changsha410007,China

Aiming to the clustering effect on FCM algorithm is easily affected by the initial location and fell into local optima, the gray optimization algorithm is applied to improving FCM to put forward a method of clustering analysis GWO_FCM. The KDD CUP99 data set as the research object,the research results showed that GWO algorithm of clustering had a accuracy and lower error rate,comparing with PSO,GA and SA algorithm,it was with faster convergence speed and better effect so as to provide a new approach for data clustering analysis.

ClusteringAnalysis;data mining

TP391.1

:A

:1000-2324(2017)01-0100-04

2016-11-12

:2016-12-16

2014年湖南省教育厅科学研究项目:基于用户兴趣挖掘技术的移动校园信息推送系统研究及应用（14C0505）;湖南科技职业学院重点科研课题:2013年基于移动终端的个性化校园信息推送系统的研究与实现(KJ13102)

黄蓉(1981-),女,硕士,讲师,主要研究方向为数据挖掘、职业教育.E-mail:ocean1205@163.com