基于蒙特卡洛k-means聚类算法的舰船器材分类研究

吴雯雯，陈振林

(海军航空大学 岸防兵学院，山东 烟台 264001)

0 引言

仪表器材是指用于检出、测量、观察、计算各种物理量、物质成分、物性参数等的器具。舰船仪表器材按照工作原理可以分为电磁式与机械式，按照测量类型可以分为力学、电磁、热工、化学、几何量、时频等六大类。遍布舰船各个工作部位，其主要作用是监测舰船运行状态，为舰船运行提供压力、电流、舵角、温度、风速、功率等信息。仪表器材的精确化保障对舰船运行至关重要。

舰船仪表种类繁多，数量庞大，消耗规律复杂，针对每一类器材进行分类预测并不现实，对仪表器材合理分类是提高效率的重要手段，是消耗预测的基础[1-4]。目前，针对器材的分类方法有定性方法与定量方法：定性方法有ABC分类法、VED分类法等，这类方法操作简单，只需要考虑价值、关键性等一个或少数几个准则就能分类，但也存在过于粗放的问题；定量方法有基于器材消耗规律的SBC分类法、考虑多种分类因素的模糊综合评价法、层次分析法等，这些方法适用于样本容量大，影响因素复杂的情况。随着研究的不断深入，定性与定量相结合以及数据挖掘技术成为热点。

基于VED的ABC分类法将备件所属设备的重要程度等因素纳入了考虑范围[5-6]。文献[7-8]对备件品种的主要影响因素运用模糊综合评估方法进行综合评价，采用专家系统量化主要指标。基于AHP的ABC分类法，在两种方法结合的过程中，可以将定性因素和定量因素都转化成数值形式加以对比，在一定程度上能改进管理，但是备件关键性因素的确定受主观影响较大，不可避免地包含了主观性的不利影响[9-12]。

文献[13-14]采取基于属性的备件品种确定方法，将关键性、可更换性、消耗性、维修性等因素引入备件决策，利用粗糙集理论对备件属性进行因素选取，体现了定量与定性相结合的特点，有较好的工程实用性。

由英国学者Syntetos等人提出的SBC分类法[15]应用广泛。该方法基于器材消耗规律进行分类，通过两个截断值ADI和CV2(x)将需求分为4类。其中ADI(average demand interval)是需求发生时间间隔的平均值，反应的是0需求量发生的频率，ADI值越大，说明需求中0需求发生的越频繁，间断性越明显；CV(coefficient of variation)为需求量变异程度系数，反映非零序列偏离均值的严重度，值越大，序列越不稳定。图1中的A、B、C、D分别代表不稳定型消耗、块状型消耗、平稳型消耗、间断型消耗。

图1 基于SBC分类法的备件消耗类型图

SBC方法在处理大量数据时有着较为优越的解释效果，但在处理少量数据集的时候，往往容易产生较大的误差。虽然SBC方法对本文所研究的数据不太适用，但是它所包含的4种器材类型对有一定的通用指导意义。例如一部分价格昂贵、更换周期较长的仪表，就符合间断型消耗器材的特征，工作环境恶劣、大批量消耗的仪表其消耗特征也与平稳型消耗类型比较接近。

对于种类多、品种杂、消耗规律多样的器材，聚类分析作为一种定量方法，从数据分析角度，给出了更准确、细致的分类[16-17]。文献[18]运用主成分分析对分类准则进行降维，得到约简后准则再进行聚类处理。文献[19]从同一类器材中选择样本对网络进行训练，然后再用该网络对该类器材进行消耗预测，节省了训练时间。文献[20]基于器材消耗波动性进行聚类分析，采用层次划分聚类，使算法更稳定高效。

分析某型舰船仪表器材消耗数据，聚类分析方法适用性更好，主要有以下原因：1)某型舰船服役年限较短，数据量过少，器材属性、可靠性、影响因素等信息缺乏相关数据。如果采取AHP、主成分分析法、灰色关联分析、支持向量机等方法，在数据量过少时，容易产生过拟合问题；2)仪表器材长期处于高温、高湿、高盐的工作环境，变化规律比较复杂，其损耗往往具有很大的偶然性，各种不同工况的影响或者操作的失误都有可能直接或间接地产生噪声影响。作为具有多量值特征的器材，采用聚类方法对其数学特征进行分析处理会更加准确、方便、科学。

1 蒙特卡洛K-means算法

聚类分析是一种重要的数据挖掘技术，是依据“物以类聚”的思想，对样本或者指标进行分类。其目的是把大量数据点的集合分成若干类自然分组，使得组内相似度最大化，组间相似度最小化，将目标集合分成由类似的个体组成的多个类的无监督分析过程，可有效地分析数据分布，广泛应用于模式识别、机器学习、航空航天等多个领域。聚类分析的分析思路为：在一批样本的多个观测指标中，找出一个统计量，该统计量可以度量样本间或者指标间的相似程度，构成一个对称的相似性矩阵，以此为基础，将各样本逐一归类。

k-means聚类是最为常用的一种聚类方法，是基于原型的聚类。每一个簇都由某个中心点数据代表，这个中心点就是所谓的原型，该算法事先设置簇的个数，即k的值，k-means聚类的目标是找出各簇的质心，然后与各质心相邻的数据点聚成各簇，以实现聚类。将所有点的均值作为簇的质心。k-means聚类的优势在于对低维度数据聚类有着良好的解释效果，适用于数据的初步分析，是一种较为成熟的聚类方法。

k-means聚类实现过程非常便捷，但它的一大弊端在于，该方法对初始聚类中心的选择十分敏感，不同的初始中心点会造成聚类结果的波动。随机初始化质心是该算法的基础，之后的工作都是围绕这一基础开展的，如果更换不同的初始化设置，那么就有可能得到更好的解。对于给定的数据，局部最优解往往不是全局最优解，因此，质心初始化对k-means聚类的结果有直接影响。为了有效地克服局部最优问题，可以采取多次初始化的方法。k-means聚类在处理高维数据分类问题时，它更多表示为点的数据特性，而对多元线性的聚类列则存在缺陷，导致聚类中心散列，效果不佳。因此，本文通过引入Monte-Carlo(MC)法对质心进行多次初始化，选出最好的那一次作为最终聚类中心。

MC法亦被称作随机抽样技术，广泛应用于对物理过程或生化过程的模拟，也可以求解一些最优化问题。在利用计算机在统计抽样理论的基础上，通过有关随机变量的统计抽样检验或随机模拟，估计和描述函数的统计量、求解问题近似解的一种数值计算方法。MC法不但能够解决随机性问题，也能解决确定性问题。其基本原理是：为解决某一实际问题，首先建立与所求解问题相应的一个随机模型，形成随机变量，使随机变量的某个数字特征(如期望值等)正好是问题的解；然后按照模型进行大量的随机实验，以获得随机变量的大量抽样值，用统计方法作出所求数字特征的估计值，就得到问题的解。MC法计算程序简单，其收敛是统计意义上的收敛，收敛速度和问题维数无关。MC法误差仅与方差和样本容量有关，而与样本中元素所在的空间无关[21]。MC法具有程序结构简单、不受问题条件限制、模拟过程灵活、适于求解多维问题等优点，所以有着广泛的应用。

最终结果可表示为:

(1)

其中:SSE代表方差函数，Zt表示在时间为t年下的模型所得误差，随后引入变量j∈(1,2)，如果t+1下的模型误差比t模型下的误差更小，则替代模型为:

(2)

2 算法流程

1)对数据进行特征选择。舰船器材具有品种繁多、影响因素多、波动性大的特点，器材的消耗因为影响因素的变动会存在一定程度的波动。舰船器材因其应用目的的特殊性，其影响因素复杂多变，使得波动性表现得更加明显，主要体现在消耗的规模波动和结构波动两方面。规模波动是指需求总量的波动，包含收缩和扩张两种情况；结构波动则比较复杂，主要体现在器材品种的不断改变。SBC方法中的用到了两个波动性指标：需求发生间隔的平均值、需求量变异程度系数。但是分析本文数据可知，目前对该型舰船仪表器材的消耗数据是以年为单位进行统计，若采取SBC方法分类指标，数据过少，将会出现很大误差。因此，本文采用计算样本总体方差描述器材波动性。表达式为:

(3)

能够反应出曲线的变化规律和数据离散的分布特性，因此适用于k-means聚类。该方法的优点在于，解决了k-means处理多维数据噪声过大以及消耗器材数据时间轴数据过少无法采用合适模型的问题，同时为后期的模型更新做出了铺垫。

2)确定k值，即聚类种类。直观地看k-means就是把数据空间划分为k个区域或者划出k条边界，其中各区域以其原型为质心。通常情况下，增大k值就能减小SSE，但这种方法容易出现过拟合，失去聚类分析的意义。k值要事先指定，并且在很大程度上影响聚类结果。在先验知识不足的情况下，该参数的选取比较困难，需要进行多次试验才能找到最佳类别数。在实际应用中，往往需要与别的算法组合使用来确定合适的类别数，这些算法可能比K-means算法要复杂得多，抵消了K-means算法简便易行的优势。因此，本文根据对某型舰船机电仪表器材属性、工作原理及消耗情况的大致了解，参考SBC分类法的种类数，令聚类种类k=4，使得聚类结果更加贴合器材管理实际。

3)利用MC法确定初始聚类中心，通过迭代，利用计算机快速运算，不断进行重复性操作，重复执行建立初始质心预测模型，在每次执行这组命令时，都从变量的原值推断出它的新值，直到各数据点不再变更自己所属的簇，或者这个变更不再显著，这样最后确定的质心就是数据内部各簇的代表或者原型。

4)选取SSE来作为误差检验指标。SSE是拟合数据和原始数据对应点的误差的平方和，计算公式为:

(4)

SSE越接近于0，则模型选择和拟合更好，数据预测也越成功。

该统计参数是预测数据和原始数据对应点误差的平方和的均值，计算公式为:

(5)

对于样本集D={xi,xi,…,xm}。K-means聚类方法将聚类划分为C={C1,C2,…,Ck}，最小平方误差为:

(6)

公式(6)刻画了簇内样本围绕簇均值向量的紧密程度，E值越小，簇内样本的相似度越高。

3 仿真试验与比较

现以某型舰船2015～2019年49种仪表器材年消耗数据为例进行分析。使用Matlab软件进行仿真试验，通过STDEVP函数计算样本总体方差，得到结果如表1所示。

表1 仪表器材年消耗数据

从表1可以看出，数据方差σ2总体偏小，在一定范围内波动，对此建立需求方差变量T= [σ12σ22…σ492]。对该变量分别进行经典k-means聚类及蒙特卡洛k-means聚类分析，对比两种方法的结果，验证本文方法的有效性和精确性。

3.1 经典k-means聚类分析

经典k-means聚类过程如下：

首先，初始化质心。随机初始化k个质心。

第二步，划分数据点，质心确定后，找出距离最近质心的数据点，形成簇，此处采取欧氏距离进行度量，有n个特征的数据点X(x1,x2,…,xn)与点C(c1,c2,…,cn)之间的欧式距离计算公式为:

(7)

各点找到相距最近的质心之后，就归属于该簇，数据空间就被划分成k个子区域。

第三步，找出该簇最有代表性的点，作为新的质心，即求解所有点到质心距离误差平方和最小化问题。

第四步，反复计算并更新质心。新的质心确定之后，更新各数据点至最近的质心，确定新簇并再一次更新质心。重复这个过程。直至各数据点所从属的簇不再变化或者变化不再显著，那么最后确定的质心就是各簇的代表，可以描述整个模型。

使用Matlab软件进行k-means聚类,所得结果见表2，聚类图如图2所示。从表2中可以看出，k-means方法针对每年数据都产生不同的聚类中心。从图2可以看出，k-means聚类无法合理处理多维数据，聚类效果不明显。

表2 最终聚类中心

图2 K-means聚类图

3.2 蒙特卡洛k-means算法

对器材消耗进行蒙特卡洛k-means 聚类分析，得到聚类结果见表3，聚类图如图3。从图3中可以看出，聚类效果显著，第2、3类消耗器材在总体样本中占比较高。

表3 最终聚类中心

图3 蒙特卡洛K-means聚类图

对比以上两种聚类结果及散点图可以看出，未进行蒙特卡洛k-means聚类结果散列，聚类图分类不明显，受时间序列的影响较大，不能够直观地分析出结果，而处理过后的数据聚类效果明显，该方法很好地将低数据量的消耗器材映射到了三维空间，同时解决了k-means算法无法处理高维数据的问题。

以(2.56,0.85,1.73,4.69)作为聚类中心得到聚类结果见表4。

表4 聚类成员

根据4种器材年消耗相对值，得出器材分类消耗折线图，如图4所示。从图中可以看出，2015～2019年4类器材消耗均呈上升趋势，这与舰船遂行任务增多以及仪表到寿更换的客观事实是吻合的。从需求间隔和需求量上看，第1类与第3类器材波动性最强，第4类次之，第2类最为平稳。

图4 器材分类消耗折线图

4 结束语

准确的分类是消耗预测的基础，利用消耗波动性对器材进行分类符合实际工作需要，具有很强的借鉴意义。本文着力研究舰船仪表器材分类问题，针对某型舰船仪表器材数据量稀疏，采取需求量变异程度系数等其他波动性指标易造成过拟合的情况，考虑利用样本方差来体现器材消耗波动性，无需计算器材内在属性，不需要对数据进行时间序列AR建模，简化了仪表器材消耗分类模型，能够有效解决数据量过少时模型建立困难的问题，避免了复杂模型放大误差。本文基于蒙特卡洛法改进了初始聚类中心的选择，有效避免了传统算法随机选择初始聚类中心导致的结果不稳定性。与多尺度最小二乘SVM模型、AHP理论相比，采用本文的方法，对数据不足的模型有着较好的适用性。后续研究将结合其他分类方法，对聚类结果进一步的量化分析。