-
摘要: 在聚类算法中，聚类中心决定聚类的最终结果，而传统的分割聚类算法不能准确定位聚类中心。根据数据场提出了数据质量聚类中心的新概念，给出数据质量聚类算法，能够一次定位聚类中心，无需迭代，也无需预置聚类个数。7组对比实验表明，提出的方法能够准确定位聚类中心，获得良好的聚类结果和稳定性，优于传统的分割聚类算法和峰值密度聚类算法。Abstract: The clustering center has a great effect on the clustering result. In this paper, a new concept of the data mass is proposed. The mass of data represents one of the inherent attributes of the data. With different view angles of data mining, the data mass maybe different. Based on the concept of data mass, a new clustering algorithm, which is clustering data with mass, is put forward. This new algorithm finds the clustering centers based on two attributes of data:the data mass and the data distance. And it can complete the clustering process with only one pass of the whole dataset. Experimental results show that the proposed algorithm can find the clustering center accurately and can get better clustering result than the same typical clustering algorithms, such as K-means, K-medoids and clustering by fast search and find of density peaks.
-
Keywords:
- data field /
- cluster /
- data mass /
- clustering center
-
随着国家海洋战略的实施，水下潜器的导航需求越来越大，对此需要进行高精度、高自主的导航条件作为辅助。现阶段，提供导航定位的方式多样化，如GPS（global positioning system）、GLONASS（global navigation satellite system）、GSNS（Galileo satellite navigation system）、BDS（BeiDou navigation satellite system）、声呐导航、天文导航[1-2]、惯性/测向测距导航系统[3]，其定位精度虽然满足水下潜器需求，但由于隐蔽性差、抗干扰能力差等原因，不利于潜艇长时间水下定位。重力辅助惯性导航作为一种不依靠人为因素，借助地球自身特性，即地球重力场信息，完成潜艇水下长航、长航距导航，具有重要的研究意义。重力辅助惯性导航具有自主、无源、高精度、高隐蔽性、抗干扰性的特点，是真正的无源导航。
利用地球独有特性进行无源导航的方式，目前已涉及地形匹配导航、地磁匹配导航[4-6]以及重力匹配导航。由于惯性导航在极区易丢失方向，地磁导航更难实施，因此亟需研究极区多源信息组合导航定位技术[7]。20世纪80年代初，美国洛克希德马丁公司在美国军方资助下研制了重力敏感器系统（gravity sensor system，GSS）。GSS是一个当地水平的稳定平台，平台上安装有一个重力仪和三个重力梯度仪。重力仪是一个垂直安装的高精度加速度计，重力梯度仪输出两组正交的梯度分量，由安装在同一转轮上的4个加速度计组成。GSS用于实时估计垂线偏差，以补偿惯性导航误差。20世纪90年代，该公司在GSS、静电陀螺导航仪（electrostatic gyro navigator，ESGN）、重力基准图和深度探测仪等技术的基础上开发无源重力辅助导航系统（gravity aided inertial navigation system，GAINS），它通过重力匹配获取导航位置坐标，以无源方式限定或修订惯性导航误差，能实现潜艇14 d精确导航[8-9]。国内对重力辅助惯性导航技术的研究开始于20世纪90年代。目前关于重力辅助导航技术及其相关技术的研究包括重力辅助导航系统组成，重力匹配导航算法，卫星测高反演重力异常，重力场对惯性导航系统精度的影响，重力图数据处理，以及重力仪、重力梯度仪的研制等方面[10]。
目前常用的匹配算法有4种，包括地形轮廓匹配算法（terrain contour matching，TERCOM）、迭代最近等值线算法（iterated closest contour point，ICCP）、桑迪亚惯性地形辅助导航算法（Sandia inertia terrain-aided navigation，SITAN）和滤波算法。TERCOM算法主要是使用重力场数据相关技术的匹配算法，其匹配精度高，受初始误差影响小，但实时性不强[11-15]。ICCP算法主要是使用刚性变换不断靠近等值线上最近点并进行配准，该算法有较高的精度，但其应用受到惯导指示位置与载体真实位置之间误差足够小的假设条件的限制，而且随着迭代次数的增加，计算量也不断增大[16]。此外，ICCP算法忽略了参考导航系统在短时间内的误差变化，应用时限制了匹配点数[17]。SITAN算法是基于扩展卡尔曼滤波技术的单点匹配算法，得到导航误差的估计值，然后把误差估值反馈回惯导系统，从而对其导航状态进行修正[18-19]；SITAN算法需要获取较为精确的初始误差，对非线性观测模型线性化敏感，线性化精度低会导致滤波发散[20]。在辅助导航中使用较多的滤波算法主要有卡尔曼滤波算法以及粒子滤波算法，卡尔曼滤波算法是将重力场数据的变化作为卡尔曼滤波器的观测量，将惯导运动的误差方程作为卡尔曼滤波器的状态量来建立卡尔曼滤波方程。
发展海洋重力匹配导航技术还存在很多核心问题，如海洋重力基准图的格网分辨率问题，实时重力仪测量值与重力地图快速匹配问题[21]。近年来，重力实时测量与匹配导航算法引起国内学者广泛关注[22-24]，如Wang等[25]研制了重力匹配惯性导航系统，并开展了相关的海试工作。不少学者在传统匹配算法的基础上，改进算法的实时性，改善匹配的精度，提高匹配的可实施性[26-29]。
传统重力匹配过程主要考虑实时重力测量值与重力场背景图之间的相关性。国内学者在进行约束改进算法时，提出了对惯导短时间内具有高精度的约束条件，进而增设轨迹位移角度判断方式，通过增加对每一段采样航距的惯导角度和待匹配轨迹对应角度一致的条件，对待匹配轨迹进行了约束，但惯导系统在短时间内的误差虽然很小，但不可忽略。对惯导设备要求苛刻，仅仅单独从每一段采样航距去进行约束，以及对每一次轨迹旋转角度进行绝对约束，不符合实际情况[30]。
本文通过结合运载体的运动速度与航向信息，提出了基于惯性导航特征相似性的约束条件匹配导航算法，用向量的形式表示轨迹的运动轨迹方向，同时计算轨迹在每一采样间隔段的航距以及总匹配航距。利用匹配约束条件对待匹配轨迹进行选择，剔除大量不符合约束条件的随机匹配轨迹，同时考虑惯导设备存在的客观误差因素，提高匹配效率，缩短匹配时间，改善匹配精度。
1 重力匹配算法原理
重力辅助匹配惯性导航系统是利用地球重力场特性，在高分辨率的重力异常图组成的基本特性信息数据库中[31]，结合惯性导航系统提供的实时输出位置，以及海洋重力仪提供的实测值，按照一定的匹配算法对惯导位置进行修正，实现高精度水下定位的一种导航技术。系统原理结构图[32]如图 1所示。
概率神经网络匹配算法主要由4个结构层构成，以此为输入层、模式层、求和层以及输出层。
在输入层中，输入样本X经过归一化后传递到模式层中。
在模式层中，需要将输入样本X与权值向量Wx做内积运算：
$$ {Z_X} = {X^{\rm{T}}}{\mathit{\boldsymbol{W}}_X}$$ (1) ZX然后对做非线性化处理，即：
$$ g\left( {{Z_X}} \right) = {\rm{exp}}\left( {\left( {{Z_X} - 1} \right)/{\sigma ^2}} \right)$$ (2) 将式（1）、式（2）经过推导等价于：
$$ g\left( x \right) = {\rm{exp}}[ - \left( {X - {W_X}{)^{\rm{T}}}\left( {X - {W_X}} \right)/2{\sigma ^2}} \right]$$ (3) 式中，σ表示概率神经网络的平滑因子。
在求和层中，将属于同类的非线性函数进行累加，以求得输入样本中属于每一类的概率ηa，一般利用Parzen窗方法来求取概率ηa，即：
$$ {\eta _a} = \frac{1}{{\left( {2{\rm{ \mathsf{ π} }}} \right)\frac{p}{2}{\sigma _p}}}\left( {\frac{1}{{{n_a}}}} \right)\mathop \sum \limits_{x = 1}^{{n_a}} g\left( {{Z_X}} \right)$$ (4) 式中，na表示求和层中属于分类a的神经元的个数；p表示输入样本的维数。
在输出层中，将求和层中利用Parzen窗方法计算而来的所有分类的概率进行比较，并求取属于某个类别的最大概率ηmax，然后以竞争方式使其输出为1。
将所有待匹配轨迹N条分为N个类别，求取实测重力序列与之对应的最大概率匹配序列作为最终匹配轨迹序列[33]。
概率神经网络通过分析实测重力数据与待匹配轨迹数据之间的属性关系，对比实测数据与各类别属性的从属关系程度，选择最大相关序列、作为最佳匹配序列。概率神经网络算法虽能较好实现重力匹配惯性导航，但其在匹配过程中仅依靠了惯导轨迹提供的单点位置信息搜索待匹配点，忽略了惯性导航所提供的连续轨迹属性信息，即航距与航向，这会导致概率神经网络匹配结果只考虑了重力数据的相似性以及顺序性，而忽略了潜艇轨迹本该具有的空间属性。
2 相关约束的重力匹配算法
相关约束的重力匹配算法的核心思想是：首先利用惯性导航系统提供的连续性方向信息构建序列矩阵，对每一条待匹配轨迹的拐点方向矩阵进行判断，排除不符合惯导轨迹方向序列的待匹配轨迹；其次，利用惯导系统提供的相邻采样距离信息和轨迹总运行距离信息，对待匹配轨迹进行约束，排除局部和整体均不符合距离约束条件的轨迹；最后利用概率神经网络算法对符合以上两步约束条件的待匹配轨迹进行分析，选择最终匹配轨迹。该算法充分利用了惯性导航输出数据的短时高精度特性和在长距离匹配背景下的方向、距离整体特征连续性，并且避免了在重力异常图分辨率较低背景下对方向角度出现错误筛选的情况，提高了匹配算法的适用性，体现了重力匹配惯性导航算法中先整体、后局部，惯导为主、重力为辅的匹配思想。
2.1 设定搜索区域
由于惯性导航系统中加速度计以及陀螺仪的固有误差，使得惯导在输出位置时出现漂移，水下潜艇的实际位置应该在以惯导输出位置为中心的一定范围内，通过对惯导数据以及时长的分析来确定对应一定时间的惯导漂移范围。
本文以10个连续惯导输出点作为一组匹配轨迹，根据惯导输出确定其在重力图中的位置，分别以其为中心，以最后一点对应的累计漂移距离λ为1/2矩阵搜索边长，确定最后两点矩阵的搜索区域，即2λ×2λ，第3至8点搜索边长为，第1至2点的搜索边长为λ/2，以此确定一组矩阵的搜索区域[34]，如图 2所示。
2.2 寻找等值点
在搜索范围内，根据重力底图，读取范围内对应格网位置的重力异常值gk，并与相应时刻重力仪实测重力值gi进行比较。根据重力仪误差情况，设定等值点范围，若$\left| {{g_i}\left( {{x_i}, {y_j}} \right) - {g_k}\left( {{x_k}, {y_k}} \right)} \right| = {\rm{\Delta }}g \le \delta $，则点k属于对应时刻惯导输出点i的重力等值点。最终在整条轨迹线中，可形成10个点聚集区。
2.3 设定约束条件
重力匹配惯性导航是一项多源综合性导航，目前大多数匹配算法在研究过程中侧重于研究待匹配重力值与实测重力值之间的相关性，忽略了惯性导航提供轨迹数据的精确性，以及对匹配导航位置关系的约束性。约束匹配流程图如图 3所示。
2.3.1 约束轨迹方向
虽然惯性导航系统中的加速度计和陀螺仪在导航中均存在漂移误差，但在机动性强、运动轨迹方向多变情况下的导航，不存在轨迹前进左右方向判别上的错误。因此，在陀螺仪不能完全精确输出轨迹转动角度的情况下，可以更为准确地输出轨迹相对运行前进方向的左右判别，这对于正确判断真实轨迹的运动起到很好的约束作用[35]。
因此，本文对待匹配轨迹的约束条件之一便是：对于一条由10个采样间隔组成的运动轨迹，判别从第3个采样点至第9个采样点处于其对应前两点构成的直线的左右方位，在判断左右方位时，首先需要判断轨迹的航向，即判断潜艇运动方向是向东还是向西，向南还是向北，其中，向东包括东南方向、东北方向以及正东方向，向西包括西北方向、西南方向以及正西方向，向北即为正北方向，向南即为正南方向。式（5）为直线表达公式，由式（6）可知，利用直线上两点坐标，可求得直线斜率。
$$ Y - y = k\left( {X - x} \right) $$ (5) $$ k = \frac{{{y_2} - {y_1}}}{{{x_2} - {x_1}}} $$ (6) 式（5）和式（6）经过推导等价于：
$$ Y = \frac{{{y_2} - {y_1}}}{{{x_2} - {x_1}}}\left( {X - {x_1}} \right) + {y_1} $$ (7) 求取第3点X轴向对应的Y轴坐标：
$$ {{y'}_3} = \frac{{{y_2} - {y_1}}}{{{x_2} - {x_1}}}\left( {{x_3} - {x_1}} \right) + {y_1} $$ (8) 判断其方向及输出：
$$ {{y'}_3} - {y_3} > 0\;\;\;\;\; - 1 $$ (9) $$ {{y'}_3} - {y_3} < 0\;\;\;\;\; + 1 $$ (10) $$ {{y'}_3} - {y_3} = 0\;\;\;\;\;\;0 $$ (11) 对于向东运动，若第3个采样点位于由第1、第2个采样点构成直线的下方，则判断其方向为-1；若位于直线上方，则判断其方向为+1；若位于直线内，则判断其方向为0。最终对惯导轨迹可输出一个由-1、0、+1组成的8×1的矩阵。
若潜艇向西运动，则输出结果与向东运动结果相反：
$$ {{y'}_3} - {y_3} > 0\;\;\;\;\; + 1 $$ (12) $$ {{y'}_3} - {y_3} < 0\;\;\;\;\; - 1 $$ (13) $$ {{y'}_3} - {y_3} = 0\;\;\;\;\;\;0 $$ (14) 若潜艇向正北方向运动，则输出结果与X值相关：
$$ {x_1} = {x_2} > {x_3}\;\;\;\; - 1 $$ (15) $$ {x_1} = {x_2} < {x_3}\;\;\;\; + 1 $$ (16) $$ {x_1} = {x_2} = {x_3}\;\;\;\;0 $$ (17) 若潜艇向正南方向运动，则输出结果与正北方向相反：
$$ {x_1} = {x_2} > {x_3}\;\;\;\; + 1 $$ (18) $$ {x_1} = {x_2} < {x_3}\;\;\;\; - 1 $$ (19) $$ {x_1} = {x_2} = {x_3}\;\;\;\;0 $$ (20) 同时，对由待匹配点任意连线构成的待匹配轨迹进行方向判断，生成一个8×N的矩阵，其中N为待匹配轨迹条数。根据惯导提供的方向矩阵，从待匹配方向矩阵中，筛选出符合惯导矩阵的对应轨迹，作为下一步待匹配轨迹，剔除不符合轨迹。
2.3.2 约束轨迹距离
通过对惯导系统在长航距中产生的误差分析，可以发现，在较短的时间间隔内，惯导输出的距离精度较高，在相邻采样间隔的输出距离上，与对应的真实运动轨迹距离相仿，因此，本文对每条待匹配轨迹的9个采样间隔段进行判断，若
$$ \begin{array}{*{20}{l}} {\;\;\left| {L\left( {A\left( {{x_t}, {y_t}} \right), B\left( {{x_{t + 1}}, {y_{t + 1}}} \right)} \right) - } \right.}\\ {\left. {L\left( {A'\left( {{x_t}, {y_t}} \right), B'\left( {{x_{t + 1}}, {y_{t + 1}}} \right)} \right)} \right| \le \lambda {\rm{}}} \end{array} $$ (21) 则认为两条线段的距离相仿[36-37]。式中，λ根据惯导元器件精度、重力图分辨率以及采样时长设定。
此外，增设约束条件：即对于由10个采样点构成的航迹，总的距离误差不是简单地由9个段误差累计和，而是有增有减，因此，对惯导轨迹的总距离和待匹配轨迹的总距离之差设定一个阈值ξ，ξ的值可根据惯导元器件的精度和采样时间间隔来确定。即：
$$ \begin{array}{l} \left| {\mathop \sum \limits_1^n \left( {\sqrt {{{({x_{n + 1}} - {x_n})}^2} + {{({y_{n + 1}} - {y_n})}^2}} - } \right.} \right.\\ \left. {\mathop \sum \limits_1^n \left. {\sqrt {{{(x_{n + 1}^{\rm{'}} - x_n^{\rm{'}})}^2} + {{(y_{n + 1}^{\rm{'}} - y_n^{\rm{'}})}^2}} } \right)} \right| \le \xi \end{array} $$ (22) 式中，根据惯导元器件精度、重力图分辨率以及轨迹时长设定。这样，不仅仅是从单个采样距离上对待匹配轨迹做出约束，而是从局部和整体两方面约束，可有效剔除符合局部条件、但不符合整体实际轨迹特征的待匹配轨迹。
3 仿真实验分析
本文基于MATLAB对实验进行编程仿真，重力异常图分辨率为，假定水下潜艇以10 m/s的速度航行，匹配算法选取概率神经网络匹配，每3 min进行一次采样，在满足匹配导航时效性的前提下，为能够尽量满足匹配导航精度条件，实验采用每10个采样点作为一次匹配序列，在同等条件下进行有无约束条件对比，实验中α设定为2 776 m，即1.5倍的格网距离，ξ设定为4 627 m，即为2.5倍的格网距离。轨迹所处背景场如图 4所示，重力异常图背景标准差为16.942 mGal，经度方向相关系数为0.769，纬度方向的相关系数为0.547。因约束条件是对概率神经网络待匹配结果进行筛选，并不在最终原有匹配结果轨迹的基础上加以修改，因此该约束算法不受背景场影响，图 4中右下点为起始点。仿真结果如图 5所示。
![]()
图 5 匹配结果及东、北误差对比图Figure 5. Comparison of Matching Results and Errors of East, North Directions由图 5可见，在经纬度方向重力异常相关系数均大于0.5的情况下，未增加约束条件的概率神经网络匹配，在匹配位置上会存在一些不符合实际运动方向、航距的情况。基于约束条件的重力匹配辅助导航算法，对轨迹的航向做出修正，真实轨迹与惯导轨迹均在第8条采样段的航向上向东北方向偏移，但未约束的概率神经网络匹配结果将第9段匹配航迹修改成向西南方向航行，明显不符合实际情况，通过约束，可将其进行正确修正。同时，算法通过剔除大量不符轨迹，大大缩短了神经网络匹配的耗时，如表 1所示，将精度由千米级提高到百米级，较好地提高了匹配位置精度。以匹配误差低于一个格网密度作为成功匹配，将成功匹配点占所有匹配点的百分比作为成功匹配率，在东、北方向，匹配率均由80%提升至100%。如表 2所示，方向正确率由62.5%提升至100%，耗时缩短50%左右，表明本文算法有效提高了运算速度，保证了匹配运算的精确性和实时性。
表 1 东、北方向距离误差/mTable 1. Distance Errors of East, North Directions/m方向 匹配条件 误差统计 最大值 最小值 平均值 均方差 北向 未约束神经网络匹配 5 852.439 0 5.502 187 1 059.555 0 1 801.611 0 约束神经网络匹配 1 620.846 4 5.502 187 591.739 2 618.789 4 东向 未约束神经网络匹配 5 156.672 0 8.035 500 1 221.924 0 1 727.069 0 约束神经网络匹配 1 442.420 2 8.035 500 361.244 1 413.000 4 表 2 航行方向结果比对Table 2. Results Comparison of Navigation Directions航向 转向 方向正确率/% 耗时/s 1 2 3 4 5 6 7 8 惯导方向 1 -1 -1 1 -1 1 1 -1 未约束轨迹方向 1 -1 -1 1 -1 -1 -1 1 62.5 0.094 约束轨迹方向 1 -1 -1 1 -1 1 1 -1 100 0.040 4 结语
基于相关约束的重力匹配算法，根据惯导元器件精度、重力图分辨率、重力仪精度的具体情况，对搜索区域进行规划，对等值点进行选取，对待匹配轨迹的方向向量进行筛选，以及相邻采样点距离和总轨迹距离进行约束，有效排除大量不符合真实轨迹特点的干扰轨迹，提高了导航效率和导航精度，增加了匹配算法的鲁棒性，避免了无可匹配点的情况。仿真结果表明，该约束算法不仅对均方差匹配和神经网络匹配的位置结果进行修正，同时对神经网络匹配的运算速度有大幅提升，提高了该匹配算法的实时性，更好地满足水下潜艇的需求。基于相关约束的重力匹配算法为进一步提高水下潜器导航的精确性和实时性提供了一条新的技术途径。
-
![]()
图 7 数据集A1、A2、A3聚类结果比较
Figure 7. Comparison of Clustering Results on Datasets A1, A2, A3
![]()
图 8 数据集S1、S2、S3、S4聚类结果比较
Figure 8. Comparison of Clustering Results on Datasets S1, S2, S3, S4
表 1 数据集A1、A2、A3实验平均准确率统计表/%
Table 1 Clustering Accuracies of Datasets A1, A2, A3/%
数据集 K-means
算法K-medoids
算法峰值密度
聚类数据质量
聚类A1 86.87 70.33 95.33 96.00 A2 76.84 79.73 96.65 96.91 A3 79.81 61.17 96.17 97.49 
下载: 导出CSV
表 2 数据集S1、S2、S3、S4聚类中心平均误差率统计/%
Table 2 Error Rate of Clustering Centers for Datasets S1, S2, S3, S4/%
数据集 K-means
算法K-medoids
算法峰值密度
聚类数据质量
聚类S1 0.37 0.49 2.81 0.14 S2 0.53 0.74 0.31 0.11 S3 0.98 1.55 0.66 0.15 S4 1.39 1.71 0.46 0.14
下载: 导出CSV
-
[1] Rodriguez A, Laio A. Clustering by Fast Search and Find of Density Peaks[J]. Science, 2014, 344(6191):1492-1496 doi: 10.1126/science.1242072
[2] Wang S L, Yuan H N. Spatial Data Mining:A Perspective of Big Data[J]. International Journal of Data Warehousing and Mining, 2014, 10(4):50-70 doi: 10.4018/IJDWM
[3] Wang S L, Chen Y. HASTA:A Hierarchical-Grid Clustering Algorithm with Data Field[J]. International Journal of Data Warehousing and Mining, 2014, 10(2):39-54 doi: 10.4018/IJDWM
[4] Aggarwal C C, Reddy C K. Data Clustering:Algorithms and Applications[M]. UK:Chapman & Hall/CRC, 2013
[5] Wang S L, Wang D K, Li Y, et al. Clustering by Fast Search and Find of Density Peaks with Data Field[J]. Chinese Journal of Electronics, 2016, 25(3):397-402 doi: 10.1049/cje.2016.05.001
[6] Li D R, Wang S L, Li D Y. Spatial Data Mining:Theory and Application[M]. Berlin:Springer, 2013
[7] Wang S L, Gan W, Li D Y, et al. Data Field for Hierarchical Clustering[J]. International Journal of Data Warehousing and Mining, 2011, 7(4):43-63 doi: 10.4018/IJDWM
[8] Fränti P, Virmajoki O. Iterative Shrinking Method for Clustering Problems[J]. Pattern Recognition, 2006, 39(5):761-765 doi: 10.1016/j.patcog.2005.09.012
-
期刊类型引用(1)
1. 陈鸿鑫，马天霆，周阳，简彦辰，高犇，戴明露. 基于CNN-GAN数据增强网络的电厂锅炉管道温度压力及健康状态预测. 电子器件. 2023(06): 1593-1600 . 
百度学术
其他类型引用(5)
计量
- 文章访问数: 1796
- HTML全文浏览量: 222
- PDF下载量: 355
- 被引次数: 6
