聚类算法在舰载机加载系统设计的改进应用∗

李幸运 刘佳铭

（1.武汉数字工程研究所 武汉 430074）（2.海装舰船办 北京 100071）

1 引言

在舰载机加载系统设计中，加载点的分区、杠杆连接是其重要工作内容。在舰载机不同的加载部位上所需加载的载荷点数量是不同的，像机翼这类主要受力的部件加载面上载荷点少则几十个，多则上百个［1～3］。对此只用一个作动筒加载会造成加载系统级数过多，重量过大，不方便杠杆安装等问题，影响加载精度，因此对加载点进行合理的分区非常重要。目前设计人员大多是按照加载部件的结构切面或是根据经验来进行人工划分分区，由于分区过程没有考虑到载荷点位置和载荷的影响，得到的分区会出现配重过多、过大的情况，对杠杆加载系统的重量会产生很大的影响。

杠杆连接在杠杆加载系统设计中起着重要作用，一个合理高效的杠杆连接形式能够大幅地减少杠杆系统的配重，以及整个加载系统重量，减少安装工作量。但目前仍没有合适的方法能够精确求解杠杆连接这种复杂组合优化问题的最优解［4～6］。传统办法是设计人员用CAD软件按加载点位置和载荷大小逐级计算连接，这样不但工作量大、效率低，而且人为影响较大，结果不够理想，无法保证系统级数低、配重少的要求。边蒲亚［7］提出基于遗传算法的杠杆加载系统优化设计，然而无法避免遗传算法早熟、效率低、稳定性差的缺陷。

本文针对以上问题，结合载荷点在分区和杠杆连接过程的特点，提出改进的聚类算法，将试验加载点看作待聚类样本，其坐标位置、加载载荷等特征看作样本指标，考虑载荷点自身特征对其进行聚类，利用聚类算法的聚类特性获取载荷点的分区情况和连接顺序，以此解决加载系统设计中加载点的分区和杠杆的连接顺序的问题。

2 基本层次聚类算法

聚类（Clustering）简单地说就是把相似的东西分到一组，聚类的时候，并不关心某一类是什么，需要实现的目标只是把相似的东西聚到一起［8～9］。因此通常一个聚类算法只需要知道如何计算相似度就可以开始工作，而并不需要使用训练数据进行学习，这在机器学习中属于无监督学习算法。层次聚类是聚类算法中的一种，它采用一种迭代控制策略，使聚类逐步优化，通过计算不同类别数据点间的相似度从而形成一棵有层次的嵌套聚类树［10～11］。根据层次聚类过程是自底而上还是自顶而下进行的，层次聚类算法可以进一步分为凝聚型和分裂型两种方法。以凝聚的层次聚类法为例来介绍层次聚类算法的基本原理，其基本聚类步骤为

1）初始化，把每个样本归为一类，计算每两个类之间的距离，形成初始距离矩阵；

2）寻找各个类之间距离最近的两个类，把它们归为一类，此时类的总数减少了一个；

3）重新计算其它类与新类之间的距离，更新距离矩阵；

4）重复2）和3）直到所有样本点都归为一类，结束。

3 基于凝聚的层次聚类算法的改进及优化

3.1 改进算法的提出

聚类算法的选择与其适用的应用领域关系极大，在杠杆加载设计中，考虑到在杠杆加载中分区问题与加载点的空间位置关系紧密，同时杠杆连接时其连接结构也是层次型的，很方便通过树形图来表达，层次方法既能从空间位置关系对加载点进行划分，解决分区问题，又能通过获取聚类过程的层次结构来确定杠杆的连接顺序，与解决杠杆加载问题的需求上十分吻合，因此可针对杠杆加载中的实际问题对层次聚类算法进行适当改进，对其改进作出以下几点考虑：

1）将初始加载点看作样本点，加载点的位置、载荷信息看作样本点的指标；

2）加载点的位置指标和载荷指标对相似度计算的贡献形式并不一样，计算相似度矩阵需对相似度的计算进行相应的改进；

3）每次更新距离矩阵时，类间距离的计算同样要综合考虑类中加载点的位置及载荷信息，需要对类间距离的计算方法进行相应的改进；

4）为了提高聚类效果，考虑每次聚类对下一步聚类的影响，需对聚类点的选取策略进行优化。

3.2 相似性度量改进

在聚类算法中，相似度矩阵用来存储各个对象两两之间的相似度，常用作计算初始距离矩阵。本文聚类分析中处理的数据对象为加载系统的初始加载点信息，因此需要计算初始加载点对象之间的距离，形成初始距离矩阵。常用的距离形式有曼哈顿距离、闵可夫斯基距离和马氏距离。对于聚类算法来说，不同距离形式的选取会直接影响着聚类的最终效果。在杠杆加载设计中，初始加载点的信息主要包括位置坐标和加载载荷，传统的欧氏距离描述的仅仅是对象间的几何距离，无法涵盖初始加载点的所有信息。

因此，针对传统的距离计算形式在表达杠杆加载中初始加载点之间的相似程度上的不足，本文进行相似性度量改进，初始加载点的位置指标和载荷指标对相似度的贡献形式并不相同，位置指标可采用欧氏距离来表现，而载荷指标则可将两对象之间的载荷的比值，即杠杆的力臂比作为权重系数参与距离的计算，这样既不存在指标间量纲不同的问题，也不需要考虑指标间的相关性，同时兼顾了加载点的位置和载荷信息。据此提出基于杠杆力臂比的加权的欧氏距离的形式来计算聚类的初始距离矩阵。

杠杆系统中，配重问题的产生是由于未考虑加载系统自身（如杠杆、连接件等）的重量而导致系统重心与载荷合力点不重合造成的，一般可通过力矩法［12］来解决。设杠杆配重ΔG，杠杆重量为G1，其单位长度重量为ρ，则在该级杠杆系统中，系统重量为

其中，n为杠杆长力臂与短力臂之比，l为杠杆长度，也可认为是杠杆两端加载点在加载平面上的几何距离。ρ可看作常量，不作考虑，因此可定义改进的欧氏距离为

其中，xi1、xi2为加载点i的前两个指标值，即该加载点在其加载平面上的两个坐标值；xi3为加载点i的第三个指标值，即该加载点的加载载荷，其载荷方向一般与坐标系中某一坐标轴平行，垂直于其加载平面。

3.3 类间距离改进

在聚类过程中，初始距离矩阵由计算相似度矩阵得到，但在之后的迭代合并新类时，聚类得到的新类所包含的对象不止一个，已经不能通过计算相似度来更新距离矩阵，对此需要定义类间距离来确定类与类之间的关系，常见的的类间距离有以下几种：1）最小距离：类间距离为两个类中所有样本之间的最短距离。2）最大距离：类间距离为两个类中所有样本之间的最远距离。3）重心距离：类间距离为两个类重心（均值）间的平方欧氏距离。4）类平均距离：类间距离为两个类中所有样本之间距离的平均距离。

图1 杠杆原理示意图

以上几种类间距离中，类平均法得到的聚类效果较好，但将它应用到杠杆加载中仍然不能反映真实的杠杆加载点之间的位置关系。在杠杆加载设计中，类间距离表示的是杠杆加载点之间的关系，杠杆加载点的位置信息是可以根据杠杆原理来确定，如图1所示。加载载荷与z轴平行时，加载平面即为xy平面，在已知加载点A、B的x、y坐标时即可根据杠杆原理确定合力点o位置。

加载点A、B的在加载平面xy上的坐标即为其前两个指标值，分别记为为该杠杆的力臂比，则合力点o位置为

在杠杆连接中，下级杠杆合力点在高一级的加载杠杆中是作为杠杆加载点进行加载。上式中，杠杆合力点是综合其两加载点的三个指标值得到的，能够代表两加载点的综合信息，因此在聚类过程中，可计算每次合并得到的新类中的合力点，即杠杆加载点，将该点看作新类的代表点，使得每次聚类得到的新类都可以由一个杠杆加载点来代表，那么类间距离只需通过计算两个类之间代表点之间的距离来确定，该距离的计算仍采用改进的欧氏距离形式，与式（2）一致，Xp、Xp分别为类p、类q代表点，则新的类间距离定义形式为

新的类间距离形式不仅能够表现杠杆连接中杠杆加载点之间的相关性，还将聚类算法中相似度和类间距离两种不同概念在形式上统一化，使算法更易于理解，同时反映了初始加载点和杠杆加载点在本质上的一致性，更符合杠杆加载设计的实际情况。

3.4 待聚类点选取策略优化

在基本的层次聚类算法中，每次聚类都是选择距离矩阵中距离最短的两个类，为避免算法过早地陷入局部最优，减小合并新类对后续聚类产生的不利影响，对待合并的聚类点选取策略进行适当优化，确定影响较小、结果更优的两个待合并类。优化过程如下：

1）聚类开始时寻找距离矩阵中距离最短的两个类，记录其编号i、j及其包含加载点个数Ni、Nj，计算连接i、j时力臂比 nij；

2）根据距离矩阵寻找除类j以外与类i距离最近的类m及其包含的加载点个数Nm，计算力臂比nim；

3）根据距离矩阵寻找除类i以外与类j距离最近的类，记录其编号为n及其包含的加载点个数Nn，计算力臂比njn；

4）考虑连接i、j后再连接 m时，力臂比则在这种连接顺序下的总力臂比为同理计算连接i、j后再连接n时，总力臂比连接i、m后再连接j时，总力臂比连接 j、n后再连接i时，总力臂比

3.5 改进算法流程

通过以上对算法的改进及优化，形成本文改进的层次聚类算法，其具体步骤如下：

1）获取初始加载点信息数据，存入数据矩阵data中；

2）根据改进欧氏距离计算初始数据两两之间相似度，得到初始距离矩阵distmatrix；

3）查找距离矩阵distmatrix中距离最小值对应的两个类 i、j；

4）利用优化的聚类点选取策略确定最终待聚类的两个类is、js；

5）将类is、js合并为一个新类，更新数据矩阵，采用改进的类间距离公式重新计算其它类与新类的类间距离，更新距离矩阵；

图2 改进算法流程图

6）重复步骤3）～5）直至所有数据处理完毕，此时所有加载点都被合并到一个类中，得到描述整个聚类过程的聚类树；

7）获取分区个数k，将聚类树剪切为k个类簇，获取每个类簇的子聚类树，即可得到相应分区内所有加载点的连接顺序，输出k个分区及其连接层次结构，聚类结束。

算法流程图如图2所示。

4 聚类实验对比

为了验证改进算法的有效性和准确性，进行聚类对比实验：在常规层次聚类算法中，类平均法是效率较高的一种算法，因此本次实验选择类平均法与本文改进的层次聚类算法进行对比，对某部件一加载切面上6个加载点进行杠杆连接设计。使用上述两种算法分别对上表中加载点进行聚类分析，所得结果分别如图3、图4所示。

图3 类平均法杠杆连接示意图

图4 改进算法杠杆连接示意图

从上图可看出，两种算法得到的杠杆连接形式不同：类平均法每次都是将平均距离最短的两个加载点合并，但没有考虑加载点载荷的影响，会使得类簇之间载荷相差较大，如将类1_7与类1_8合并为类2_10再将类2_10与类1_9合并为类3_10后，会因为两个类载荷相差较大而产生配重偏大的问题。而改进算法能够避免这种不合理情况发生，使聚类顺序和聚类点的选取更加合理，如将类1_8与加载点11011合并为类2_9，类1_7与加载点11012合并为类2_10，两者合力相近，使得最后合并这两个类时力臂比趋向于1，减小配重。相较于类平均法，改进算法更加有效地减少杠杆系统的配重和总重量。

5 结语

本文针对舰载机加载系统中加载点区分、杠杆连接等问题，综合考虑初始加载点位置、载荷等指标，对凝聚的层次聚类算法进行改进和优化，提出一种适用于杠杆加载的改进聚类算法。改进的聚类算法不仅能够很好地解决杠杆加载中存在的问题，还能够更加有效地减少杠杆系统的配重，快速完成加载点分区、杠杆连接的工作，得到满意的结果，解决传统加载设计方法中工作量大、效率低以及设计精度低等问题，大大缩短加载系统设计周期和成本，提高设计效率。