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

来源:期刊VIP网所属分类:计算机网络发布时间:2020-05-25浏览:

  摘要:在数据挖掘中,K均值聚类算法作为最典型、最常见、实用度最广的一种聚类算法,具有简单易操作等优点。但K均值聚类算法也存在部分缺点,其在训练前需要提前设定聚类中心个数,在训练过程中容易陷入局部最优,面对多维数据样本其效果不佳,得到的聚类结果受初始聚类中心个数的设定影响较大。对k均值聚类算法的优化方案较多,本文主要针对前人提出的基于BP神经网络的K均值聚类算法和基于SOM网络改进的K均值聚类算法效果进行分析,为后续的进一步改进提供基础。

  关键词:K-means;SOM;BP;聚类算法

网络空间安全

  《网络空间安全》(原:信息安全与技术)(月刊)创刊于2010年,是由中国电子信息产业发展研究院与迪赛工业和信息化研究院有限公司主办的,是我国信息安全和信息技术领域集学术性、技术性、专业性和权威性为一体的国家级月刊。

  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。

期刊VIP网,您身边的高端学术顾问

文章名称: 基于SOM和BP网络的K均值聚类算法分析

文章地址: http://www.qikanvip.com/jisuanjiwangluo/51738.html