一种基于SOM 改进的PCM 聚类方法

2022-02-18兰雁宁郑陈达

科技创新与应用 2022年3期

兰雁宁，郑陈达

（1.上海电力大学，上海 200090；2.国网福建省电力有限公司电力科学研究院，福建福州 350007）

在大数据背景下，数据挖掘技术逐渐成为当今热门的研究课题。聚类算法作为一类重要的数据挖掘方法，被广泛地运用于无标签数据处理问题中。在机器学习领域，聚类算法是各类无监督学习方法的基础。目前已有许多不同的聚类方法被相继提出，包括顺序聚类法、层次聚类法、k 均值聚类法、模糊c 均值聚类法等。其中模糊c 均值聚类法（FCM）不同于以往聚类方法采用的“硬划分”手段，而考虑了大多数聚类对象在类属方面存在的中介性，及对象的类别划分界限并非严格分明的。模糊c 均值聚类将模糊理论引入聚类算法，聚类过程中体现了数据类别不确定的描述，从而使聚类结果更为客观。

为克服传统的模糊c 均值算法易受样本噪声影响，聚类结果具有随机性的缺点，有学者提出了可能性c 均值聚类算法（PCM）。PCM 算法在一定程度上解决了聚类过程易受样本奇异值影响的缺点，但算法本身对初始聚类中心的选取非常敏感。为此，本文借助自组织映射（SOM）网络对数据样本进行原始聚类，将得到的网络权值分布作为PCM 初始聚类中心，有效增强了聚类效果及算法效率。

1 PCM 聚类

假设有数据集X={X1，X2，...，XN}，N 为数据集样本数量。数据集中任一样本xj为包含n维数据的向量，xj=[x1，x2，...，xn]。聚类算法即根据事物之间的相似度进行类别划分，被划分到同一类的对象在某一方面的相似度最大。若数据集X 表示描述某一对象的N 个样本，每一样本包含该对象的n 个属性。那么模糊c 均值聚类算法就是根据数据集X 进行C 划分，从而将聚类对象划分进C 个类别中。隶属度μij表示聚类对象各样本与类的隶属关系，其满足的条件如式（1）所示。

模糊c 均值聚类（FCM）算法采用隶属度衡量样本数据对某个聚类的隶属程度，并将其作为权值，通过加权迭代计算使数据到聚类中心的距离最短，算法的目标函数如式（2）。式中，m为加权指数，其取值大小将影响聚类效果，通常取2；dij表示样本j到第i类聚类中心的距离；μij是样本j对聚类i的隶属度。

对目标函数求偏导，结合式（1）中的约束条件，利用拉格朗日系数法可分别得到隶属度与聚类中心的迭代公式如式（3）。

不难看出，FCM 算法的核心在于聚类中心和隶属函数反复迭代运算的过程，从给定的初始聚类中心逐步收敛至最终的聚类中心。这种迭代实质上是一种局部寻优的过程，因此计算过程可能陷入局部最优解。在工程实践中，待处理的数据样本中往往含有一定量的孤立点或噪声。根据模糊理论中针对隶属度的典型性原理，样本中的噪声等都是属于代表性较差的点，应该降低这类点对隶属度的影响以提高聚类效果。PCM 算法在模糊c 均值聚类基础上进行改进，在目标函数中引入惩罚项，同时放松了约束限制，提高了算法抗噪能力，其目标函数及约束条件为如式（4）。

式中的ηi为惩罚参数，其取值可通过式（5）计算得到。

类似于式（3）中模糊c均值的迭代公式，此时隶属度以及聚类中心可由式（6）得到。

相较于FCM 聚类，PCM 聚类方法可以受噪声数据影响小，算法鲁棒性更强，聚类结果更为合理，但是，它的缺点也很明显。传统的FCM 算法迭代过程中聚类中心位置是动态变化的，各聚类中心之间互相影响从而相互重合的概率极小。但是PCM 算法中，由于放松了限制条件，各聚类中心之间不存在耦合关系，彼此相互独立故可能产生重合的聚类中心。

2 改进的聚类算法

SOM 网络属于竞争型神经网络，是一种基于无监督学习的神经网络重要类型。SOM 网络能够通过输入样本学会其规律性，并且根据输入样本相互之间的关系逐步调整节点连接权值，使网络结构与输入样本相适应。训练好的SOM 网络具有识别输入向量，并将相似向量靠近排列的功能。SOM 网络通过竞争层中互相靠近的神经元对相似的输入向量产生响应，并将响应结果反映在一维或二维空间上。因此，SOM 网络不但能学习输入向量的分布情况，还可以表示输入向量的拓扑结构，同时将具有相似性的数据映射到低维空间中的内邻近的区域内，实现了高维可视化功能。

SOM 网络由输入层和竞争层构成，输入层神经元与竞争层神经元全连接，负责将输入数据经连接权值传送至竞争层神经元；竞争层神经元之间两两互联，其连接权值随输入数据不断调整。输入层神经元个数由输入向量维数确定，竞争层神经元个数可人为设定。网络学习的基本思想是，比较输入向量与网络连接权值之间的距离（通常是欧氏距离），找到距离最近的竞争层神经元作为“优胜”神经元。调整“优胜”神经元及其附件的神经元的连接权值，使其更接近输入数据，不断重复以上过程直至训练结束。整个训练过程可以看成通过无监督学习发现输入数据间的相似模式并进行聚类。一个SOM 网络的竞争层神经元多被设置成六边形网格，输入网络的高维向量被映射到六边形网格组成的二维平面上，故所输入的高维数据间的距离可以通过其在二维平面上的远近直观展现出来。通常与同一个神经元毗邻的其他神经元总数越多，可以认为SOM 网络的性能越好。

利用SOM 网络将数据集X={X1，X2，...，XN} 划分为C个聚类，可以生成一个输入神经元数为n，竞争层神经元数为C的网络。网络将自动把数据集X 中相近的向量映射到同一个竞争层神经元上，实现对数据的初步聚类，聚类中心可以通过输入层与竞争层间的连接权值获得。故通过SOM 网络改进PCM 聚类算法的步骤如下：

（1）根据待处理的数据结构和聚类数初始化SOM 网络，包括生成网络的初始连接权值、初始学习效率值以及最大迭代次数等。

（2）训练SOM 网络。计算输入向量与每个竞争层神经元之间的欧式距离，得到与输入向量具有最近距离的神经元作为获胜神经元。同时修正获胜神经元及其邻近神经元的连接权值，重复训练过程直至达到预设的迭代次数。

（3）提取训练好的SOM 网络连接权值作为PCM 算法的初始聚类中心，设置PCM 聚类的最大迭代次数、聚类数以及容许误差值。

（4）根据公式（5）、（6）迭代计算隶属度及聚类中心，至运算达到最大迭代次数或目标函数值小于容许误差值后停止运算，输出并展示聚类结果。

3 算例分析

按照随机等隔分布规律生成50 个向量构成数据集，向量维度为3，数据分布如图1 所示。现需将其划分为5 个聚类，采用前文所述的算法步骤，生成3 输入神经元，5 竞争层神经元的SOM 网络。使用MATLAB 工具箱中的聚类分析模块初始化SOM 网络模型。由于SOM网络的聚类效果和设定的迭代次数直接相关，故采取逐步增加迭代次数的训练策略。当继续增加迭代次数而竞争层神经元权值不再发生变化时，认为训练的SOM 网络已经收敛，此时得到的权值即为PCM 算法的初始聚类中心。

图1 数据样本分布情况

数据划分结果以及竞争层神经元拓扑分别如图2、图3 所示，由图可见数据集按照预设的聚类数被均匀地划分进5 个聚类中，且竞争层神经元间的距离如实体现了数据集的结构特征。图4 展示了聚类算法的最终结果，其中U 符号标记的是SOM 网络得到的初始聚类中心位置⊗符号标记的是最终的聚类中心。不难看出，初始聚类中心已十分接近最终的聚类中心，经改进后的PCM 聚类效率将大幅增加。