基于SOM和BP网络的K均值聚类算法分析

来源:用户上传      作者:赵文均

　　摘要：在数据挖掘中，K均值聚类算法作为最典型、最常见、实用度最广的一种聚类算法，具有简单易操作等优点。但K均值聚类算法也存在部分缺点，其在训练前需要提前设定聚类中心个数，在训练过程中容易陷入局部最优，面对多维数据样本其效果不佳，得到的聚类结果受初始聚类中心个数的设定影响较大。对k均值聚类算法的优化方案较多，本文主要针对前人提出的基于BP神经网络的K均值聚类算法和基于SOM网络改进的K均值聚类算法效果进行分析，为后续的进一步改进提供基础。
　　关键词：K-means;SOM;BP;聚类算法
　　中图分类号：TP18 文献标识码：A
　　文章编号：1009-3044（2020）09-0024-03
　　K均值聚类（K-means）算法是一种经典的动态聚类算法，在聚类分析中常被使用的一种迭代求解的无监督学习算法，该算法具有简单、高效的特点，其对大数据效率较高、可伸缩性强，因此常常被用于数据挖掘的任务中。但其缺点也较为明显，其在训练过程中容易陷入局部最优解，其初始聚类中心和聚类个数需要人为确定，初始聚类中心和聚类个数对整个K均值聚类的结果影响较大，针对此问题，许多学者提出了较多的优化算法。K均值聚类算法的改进方案主要包含以下三类：一是针对如何选取好的初始聚类中心[1-5];二是在算法中如何确定合适的K值[6-8];三是与其他算法相结合的用于确定聚类中心和K值[9-13]，其中BP-K模型和SOM-K模型较为突出。本文主要针对这两种模型进行分析，为后续的改进提供基础。
　　1 K均值聚类算法
　　K均值聚类（K-means）算法是数据挖掘中常用的聚类算法，把N的数据对象根据他们的属性分为K个簇（K
　　（1）从输入样本集中任意选择K个对象作为初始聚类中心;
　　（2）根据每个聚类样本的均值，计算每个样本与这些聚类中心的距离，并根据最小距离重新对相应对象进行划分;
　　（3）对距离较大的重新计算每个聚类的聚类中心;
　　（4）计算标准测度函数，当满足一定条件，如函数收敛时，则算法终止;如果条件不满足则回到步骤（2）。
　　主要局限于平均值被定义的情况下才能使用，不适合部分分类样本;必须事先给出要生成的聚类中心数目K，对初值K的选定敏感，对于不同的初始值，可能会导致不同的聚类结果;样本集中的少量数据能够对最终的聚类效果产生极大影响。
　　2 SOM和BP神经网络
　　2.1 SOM网络
　　自组织映射神经网络是由1981年芬兰Helsink大学的T.Kohonen教授提出一种自组织特征映射网，缩写为SOM，又称Kohonen网。SOM网络属于无导师学习网络，具有良好的自组织性和可视化等特征。SOM神经网络的整体结构由输入层和竞争层构成，输入层主要负责接受外界信息，将输入的数据向竞争层传递，竞争层主要对数据进行整理训练并根据训练次数和邻域的选择将数据划分为不同的类。SOM神经网络的典型拓扑结构如图1所示。
　　SOM网络的训练过程可以概括为：第一步，确定拓扑结构，根据样本类型和部分经验确定网络竞争层维数、神经元个数和神经元的拓扑结构。第二步，样本归一化。第三步，初始化网络参数，初始化学习率、权向量和邻域函数。第四步，输入样本竞争学习，据欧氏距离相似度或余弦相似度规则寻找获胜神经元，并对邻域内节点分配一个更新权重。第五步，根据一定的规则更新节点参数。第六部，重复训练直到收敛。
　　2.2 BP神经网络
　　BP神经网络是1986年由Rumelhart和McCelland为首的科研小组提出，BP神经网络是按照误差逆向传播的多层网络。BP神经网络训练分为两个过程：第一步是输入样本的正向传播，从输入层经隐藏层到达输出层;第二步是误差的反向传播，计算期望与实际输出的误差，将误差从输出层传回隐藏层，再传回输入层，根据代价函数调节隐藏层到输出层的权重和偏置，输入层到隐藏层的权重和偏置，因此其又被称为误差反向传播网络。BP网络为多层网络，层数最小三层，其主要由输入层、隐含层和输出层构成，隐含层可以包含多层网络，如图2所示。
　　BP神经网络学习过程主要包含正向传播和反向传播两个阶段，在正向传播的过程中训练样本从输入层逐层处理传到输出层，将输出结果与期望值比较计算误差，若误差较大将误差按学习规则反向逐层分摊到各节点，训练过程中正向传播和误差反向传播交替进行，层与层之间存在激励函数、权值矩阵、偏置矩阵、代价函数和损失函数，激励函数是控制网络输出的重要函数，误差在反向传播的过程中，激励函数的倒数是求解误差梯度的重要参数。
　　3 基于BP网络改进的K均值聚类算法
　　3.1 BP-K模型简介
　　K均值聚类算法的聚类中心和个数常常结合其他算法来确定。在文献[9]中提出了一种基于BP网络的改进方案，通过对K均值聚类算法初次训练得到的聚类中心和权值引入到BP网络进行训练从而得到新的聚类中心，由于BP-K模型较为复杂，在结合实验后，在这里对该模型的基本步骤整理为：
　　（1）输入样本集P，确定初始簇的聚类中心数K（K应为一个较大的值，例如：n/5，n为样本个数），并随即选择初始聚类中心H={Hl，H2，-HK}。
　　（2）利用K-menas聚类。产生K个簇和各个簇的聚类中心H={H1，H2，-HK}，l司时将各个聚类中心和样本点到其聚类中心的距离保存下来，得到距离矩阵dpi（p=l，…，n，i=l，…，K）。其聚类结果满足K-Means聚类规则，当前聚类结果设为R（t），t=t+l。如果R[t-1]的效果相比于R[t]更好，算法结束并输出R[t]，衡量聚类效果的标准是所有聚类之间的距离差异概率。
　　（3）初始化BP网络的参数[9]，设置如下：系统误差为0，学习率为0.01，惰性因子为0.075，训練次数为1000，初始化集合S和L为空，循环次数为0。 　　（4）构造BP神经网络，主要结构为三层，以样本集为输入层，K个聚类中心作为隐藏层节点，网络的期望输出为K-Means划分结果。根据集合H中的节点序列给每个隐节点编号，0=（01，02，…，OH}。选择双曲线（
　　）作为隐层节点的激励函数。并初始化隐节点的阈值。
　　（5）利用（2）中得到的样本点到聚类中心的距离初始化网络的权值矩阵：
　　（6）计算各隐节点的输出值。
　　（7）如果隐节点i和i符合删除规则，则删除i，把i的编号存人集合S中，如过节点i和j符合合并规则，则将i和j合并为一个节点，把i的编号存入集合L中。
　　（8）重复正向计算、后向传播、修改权值直到系统误差足够小，如果一次循环中训练次数超过规定次数则退出算法并输出R[t]。
　　（9）如果一次循环后集合L不为空，则修改聚类中心：H=H-L， K=K-ILI，如果S非空，则随机选择其他中心点C，修改初始聚类中心：H={H-S}uc，ICI=ISI，K不变，如果S和L都为空，则退出并输出R[t]，否则转向步骤（3）。
　　在（7）中所提到的删除规则定义如下：
　　3.2 BP-K聚类模型分析
　　在BP-K-means模型中主要利用BP神经网络对初始聚类中心进行训练从而得到下一次的聚类中心初始参数。上述的步骤、相关度和发散度是在原BP-K模型基础上结合实验f实验数据集为iris数据集）的基础上进行参数调整和公式改进的基础上所得到的。在后面，将会与SOM-K模型进行对比。
　　在对BP-k的验证实验过程中也发现其模型对BP网络的依赖性较高，整个模型效率和K均值算法的初始聚类个数选择成正相关，选择的K值越接近最终聚类个数，模型的时间消耗越低。BP神经网络在BP-K模型中主要对聚类中心进行训练，BP神经网络的训练在整个模型中占大部分，其训练效率较低，在整个BP-K模型中，BP神经网络的误差反向传递过程主要存在于我们的输入层和隐含层，引入的K均值聚类的初始聚类权值也主要作用在输入层和隐含层。BP-K模型在将K均值算法的初步聚類中心和距离矩阵作为BP神经网络输入和权值矩阵的做法为后续的聚类优化模型具有一定的启发式意义。
　　4 基于SOM改进的K均值聚类算法分析
　　4.1 SOM-K模型介绍
　　在文献[12-13]中引入SOM网络对K均值聚类算法进行该进，其思路主要是SOM网络和K均值聚类算法的串联来改进K-means算法。类似的文献较多，但总体思路如下：第一步，先利用SOM获得初始聚类中心和中心个数，第二步，将SOM训练得到的聚类中心带人K均值聚类算法。其思路是利用SOM网络的自组织性来获取K均值聚类算法的初始聚类中心，模型应用范围较广，其效率相较于独立的两个网络确有较大的提升，SOM-K模型步骤如图3所示。
　　在图中可以清楚地看到，SOM-K模型实质上是一种利用SOM先聚类，聚类输出用于K-means二次聚类的串联模型。其应用在入侵检测中可以明显提高检测率，降低聚类的误探率。
　　4.2 SOM-K模型分析
　　SOM-K模型只是将SOM网络与K均值聚类算法简单的串联在一起，虽然在一定程度上优化了K均值聚类算法，受限于两个网络的简单串联，其模型仍然存在部分缺陷，特别是SOM网络容易出现死结点，进行聚类分析时其效率不是很理想、训练结果受训练次数的影响较大等。
　　在面对类似于网络入侵这类在同一时间产生的多种数据样本的环境中，其更容易陷入死结点，部分可能出现聚类混乱的情况，此时SOM的改进显得尤为重要，一定程度上，虽然SOM在SOM-k模型中发挥了巨大作用，但SOM网络本身的缺陷也为SOM-K模型带来了隐患。
　　5 总结与展望
　　在前文中分别分析了基于SOM和基于BP神经网络的K均值聚类算法。可以发现，BP-K模型是对K均值聚类算法的内部改进，BP神经网络在模型中主要作用于K均值聚类算法的K值变化中去，初始的K值仍需要提前确定，在面对大量数据样本的情况下，其应用效果不理想。SOM-K模型是在传统的K均值聚类算法前引入SOM网络，SOM网络的主要作用是在K均值聚类算法前确定K值，在一定程度上有利于聚类，但SOM-K模型只是对SOM和K均值聚类算法的简单串联，其无法避免SOM网络的部分缺陷。文中的BP-K模型具有一定的启发式意义，SOM-K模型多数应用在其他领域中，但在两类改进方案中，仍然存在着各自网络的部分缺陷，这是后续改进的重点。
　　参考文献：
　　[1]邢长征，谷浩，基于平均密度优化初始聚类中心的k-means算法[J].计算机工程与应用，2014，50（20）：135-138.
　　[2]谢娟英，王艳娥.最小方差优化初始聚类中心的K-means算法[J].计算机工程，2014，40（8）：205-211，223.
　　[3]傅德胜，周辰.基于密度的改进K均值算法及实现[J].计算机应用，2011，31（2）：432-434.
　　[4] Goyal M，Kumar S.Improving the initial centroids of k-meansclustering algorithm to generalize its applicability[J].Journal ofthe Institution of Engineers （lndia）： Series B，2014， 95（4）：345-350+
　　[5] Zhu M， Wang W， Huang J.Improved initial cluster center se-lection in K-means clustering[Jl. Engineering Computations，2014，31（8）：1661-1667.
　　[6] Dalal M A.Harale N D，Kulkami U L.An iterative improvedK-means clustering[Jl.lnternational Journal of Network Securi-ty，201 1，2（3）：25-28.
　　[7]刘广聪，黄婷婷，陈海南，改进的二分K均值聚类算法[J].计算机应用与软件，2015，32（2）：261-263，277.
　　[8] 2alik K R.An efficient k'-means clustering algorithm[J].Pat-tern Recognition Letters，2008，29（9）：1385-1391.
　　[9]王银辉，熊忠阳，使用BP网络改进K-means聚类效果[J].计算机科学，2006，33（3）：194-196.
　　[10]唐哲.一种基于遗传算法的k均值聚类分析[D].长沙：长沙理工大学，2014.
　　[11]寇磊.基于SOM算法改进的K-medoids算法及其研究【Dl.太原：太原理工大学，2017.
　　[12]袁正，基于SOM及K均值聚类方法的分布式入侵检测模型的研究[D].天津：天津理工大学，2009.
　　[13]汪海涛，余松森.分布式SOM结合K-均值聚类的软件定义网络泛洪攻击检测方法[J].计算机应用研究，2019，36（11）：3423-3427.
　　[14]回珥婷，夏懿嘉，陈紫荷，等，基于Synonyms、k-means的短文本聚类算法[Jl-电脑知识与技术，2019，15（1）：5-6.
　　【通联编辑：唐一东】
　　作者简介：赵文均（1994-），男，四川南充人，西华师范大学计算机学院2017届在读硕士研究生，研究方向：数据挖掘、深度学习。
转载注明来源:https://www.xzbu.com/8/view-15209592.htm