CN111275132A - 一种基于sa-pfcm++算法的目标分群方法 - Google Patents

Abstract

本发明公开了一种基于SA‑PFCM++算法的目标分群方法，首先初始化参数，并求出数据集的均值，计算每个样本点与所述均值的第一带权重欧式距离，排序后利用D²采样选择出第一个初始聚类中心，然后计算每个样本点与所述聚类中心的第二带权重欧式距离，排序后利用D²采样选择出下一个所述初始聚类中心，直至所述初始聚类中心数量达到设定条件，然后根据所述初始聚类中心迭代更新对应参数，直至迭代次数值达到设定阈值或聚类成员不再变化，计算对应的Xie‑Beni‑Sun(简称XBS)指标，然后更新初始参数值，直至达到设定停止条件，对比不同聚类数目下的XBS指标，输出设定XBS指标下的簇数目和类簇。有效降低了态势评估中目标分群的难度，提高了决策效率。

Description

一种基于SA-PFCM++算法的目标分群方法

技术领域

本发明涉及目标分群技术领域，尤其涉及一种基于SA-PFCM++算法的目标分群方法。

背景技术

现代战争主要以电子化、信息化战争为主。指挥员决策所面临的主要问题不再是战场信息缺乏，而是如何从海量的信息中科学高效的挖掘出有用信息。在实际战场环境中，作战目标数量众多，敌我各类型目标交错夹杂在一起，并且具有模糊性和不确定性，这些海量复杂信息不仅增加了指挥员正确分析战场态势的复杂性，而且随着时间的增加信息量越来越多，给指挥员进行战场实时决策造成了困难，目标分群的本质是一个数据聚类问题。在目前的研究，按照类数是否需要预先设定，可以将常用的聚类方法分为类数已知算法和类数未知算法。其中，类数已知算法中典型的方法有K均值算法和模糊C均值算法。该类算法的分类结果较为依赖于初始聚类中心及聚类数目的选取，造成了聚类结果稳定性不足的问题。类数未知算法中典型的方法有迭代自组织数据分析算法(ISODATA)算法和最近邻算法。ISODATA算法是在K均值算法的基础上增加对聚类结果的合并和分裂操作实现动态分群，但其以样本与聚类中心的距离作为分群依据，适合于解决球状簇样本分群问题，而对于战场中常见的线性编队分群问题存在不足，同时ISODATA算法需要初始设置的参数较多，针对战场目标群复杂多变的情况，很难设定比较合适的初始参数值。最近邻算法通过设定阈值实现分群，简单易实现，但其作为监督学习类的算法，无法适应于战场环境，上述算法都无法降低态势评估中目标分群的难度，降低决策效率。

发明内容

本发明的目的在于提供一种基于SA-PFCM++算法的目标分群方法，有效降低了态势评估中目标分群的难度，提高了决策效率。

为实现上述目的，本发明提供了一种基于SA-PFCM++算法的目标分群方法，包括：

获取样本集并初始化参数，求出所述样本集的均值；

计算每一个样本点与所述均值的第一带权重欧式距离，排序后利用D²采样选择出第一个初始聚类中心；

计算每个样本点与所述初始聚类中心的第二带权重欧式距离，排序后利用D²采样选择出下一个所述初始聚类中心，直至所述初始聚类中心数量达到设定条件；

根据所述初始聚类中心迭代更新对应参数，直至所述迭代次数达到设定阈值或聚类成员不再变化，计算对应的XBS指标；

更新初始参数值，直至达到设定停止条件；

输出最优XBS指标下的簇数目和类簇。

其中，所述获取样本集并初始化参数，求出所述样本集的均值，包括：

获取聚类个数和包含多个数据对象的样本集，并初始化最大类别数、当前聚类数目，模糊权重、迭代次数，并计算出所述样本集的均值。

其中，计算每个样本点与所述均值的第一带权重欧式距离，排序后利用D²采样选择出第一个初始聚类中心，包括：

计算所述样本集中的每个样本点与所述均值的第一带权重欧式距离，将所述第一带权重欧式距离按升序排列后计算每个样本点被选为第一个初始聚类中心的概率值，从设定的种子采样区间内选择出概率值对应的样本点作为第一个初始聚类中心。

其中，计算每个样本点与所述初始聚类中心的第二带权重欧式距离，排序后利用D²采样选择出下一个所述初始聚类中心，直至所述初始聚类中心数量达到设定条件，包括：

计算每个样本点与已有的所述初始聚类中心的第二带权重欧式距离，将所述第二带权重欧式距离按升值排列后计算每个样本点被选为下一个所述初始聚类中心的概率值，并从设定的种子采样区间内选择出概率值对应的样本点作为下一个初始聚类中心，若初始聚类中心数目小于当前聚类数目，则继续下一个初始聚类中心的选择，直至初始聚类中心数目达到当前聚类数目。

其中，根据所述初始聚类中心迭代更新对应参数，直至迭代次数达到设定阈值或聚类成员不再变化，计算对应的XBS指标，包括：

根据所述初始聚类中心迭代更新模糊划分矩阵、用户参数、可能性划分矩阵和聚类中心，若迭代次数未达到设定阈值且聚类成员变化，则继续更新所述参数，并每更新迭代一次，将迭代次数值加1，直至满足所述停止条件，然后计算对应的XBS指标。

其中，更新初始参数值，直至达到设定停止条件，包括：

若当前聚类数目小于最大类别数，则更新当前聚类数目加1，并重新获取聚类个数和样本集，并依次进行所述聚类中心的选择和更新对应参数，直至当前聚类数目达到设定类别数。

其中，输出设定XBS指标下的聚类数目和类簇，包括：

对比不同聚类数目下的XBS指标，输出设定XBS指标下对应的聚类数目和类簇。

本发明的一种基于SA-PFCM++算法的目标分群方法，高质量初始种子选择和自适应簇数目确定并产生更好的聚类质量。首先获取样本集并初始化参数，求出所述样本集的均值；计算每一个样本点与所述均值的第一带权重欧式距离，排序后利用D²采样选择出第一个初始聚类中心；计算每个样本点与所述初始聚类中心的第二带权重欧式距离，排序后利用D²采样选择出下一个初始聚类中心，直至所述初始聚类中心数量达到设定条件；根据所述初始聚类中心迭代更新对应参数，直至所述迭代次数达到设定阈值或聚类成员不再变化，计算对应的XBS指标；更新初始参数值，直至达到设定停止条件；输出设定XBS指标下的簇数目和类簇。该算法有效降低了态势评估中目标分群的难度，提高了决策效率。

附图说明

为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。

图1是本发明提供的一种基于SA-PFCM++算法的目标分群方法的步骤示意图。

图2是本发明提供的一种基于SA-PFCM++算法的目标分群方法的流程示意图。

具体实施方式

下面详细描述本发明的实施例，所述实施例的示例在附图中示出，其中自始至终相同或类似的标号表示相同或类似的元件或具有相同或类似功能的元件。下面通过参考附图描述的实施例是示例性的，旨在用于解释本发明，而不能理解为对本发明的限制。

请参阅图1和图2，本发明提供一种基于SA-PFCM++算法的目标分群方法，包括：

S101、获取样本集并初始化参数，求出所述样本集的均值。

具体的，输入包含n个数据对象的数据集x＝{x₁,x₂,...,x_n}，初始化最大类别数k_max、当前聚类数目k、模糊权重u、迭代次数iter，并计算出所述样本集的均值

其计算公式为：

其中，x_i为所述数据集中的样本点。

S102、计算每个样本点与所述均值的第一带权重欧式距离，排序后利用D²采样选择出第一个初始聚类中心。

具体的，计算所述数据集中的每个样本点x_i,(i＝1,2,...,n)与所述均值

的第一带权重欧式距离，用D(x)表示，其中，所述第一带权重欧式距离的定义为：

假定给定两个d维向量A(x₁₁,x₁₂,...,x_1d)与B(x₂₁,x₂₂,...,x_2d)，则它们之间的第一带权重欧式距离为：

其中，a_r∈(0,1)是特征重要程度权重系数，a_r满足约束为：

提出带权重欧式距离度量方法，主要是为了解决PFCM算法对线性编队分群存在的不足，根据特征的重要程度来调整对应特征的权重值，一般来说，对聚类结果影响较大的特征赋予较高的权重值，而影响较小的特征赋予较低的权重值，同时保证所有特征权重值累加之和为1，这样即使不同编队空间位置很接近，也能将其分别出来。

D²采样方法是首先将所述第一带权重欧式距离D(x_i)按升序排列后计算每个样本点被选为第一个聚类中心的概率值p(x_i)，计算公式为：

p_sum(x_i)＝sum(p(x₁)+p(x₂)+...+p(x_i))

然后从种子采样区间[a₁,b₁](0＜a₁＜b₁＜1，0≤w≤1，参考值a₁＝w/k，b₁＝1，w＝0.8)内均匀产生一个随机数rand，使得满足rand∈(p_sum(x_i-1),p_sum(x_i)]区间范围内对应的样本点x_i作为第一个初始聚类中心c₁。

S103、计算每个样本点与所述初始聚类中心的第二带权重欧式距离，排序后利用D²采样选择出下一个所述初始聚类中心，直至所述初始聚类中心数量达到设定条件。

具体的，若(c₁,c₂,...,c_k-1)为前k-1个簇的初始聚类中心，则计算每个样本点x_i,(i＝1,2,...,n)与当前已有所述初始聚类中心(c₁,c₂,...,c_k-1)的第二(最短)带权重欧式距离，即与最近的一个初始聚类中心的距离，用D(x_i)表示，将所述第二带权重欧式距离D(x_i)按升序排列后，用同样的方式得到概率p(x_i)，从种子采样区间[a_ki,b_ki](0＜a_ki＜b_ki＜1，参考值a_ki＝w/k+w*(b_ki-w/k)*(ki-1)/k，b_ki＝b₁)内选择出对应的样本点作为下一个初始聚类中心c_ki，若初始聚类中心数目ki小于当前聚类数目k，则继续选择出下一个初始聚类中心，直至初始聚类中心数目ki达到当前聚类数目k。

S104、根据所述初始聚类中心迭代更新对应参数，直至迭代次数达到设定阈值或聚类成员不再变化，计算对应的XBS指标。

具体的，根据所述初始聚类中心迭代更新模糊划分矩阵、用户参数、可能性划分矩阵和聚类中心，若迭代次数未达到设定阈值且聚类成员变化，则继续更新所述参数，并且每更新迭代一次，将迭代次数值加1，直至满足所述停止条件，然后计算对应的XBS指标。

根据所述聚类中心，定义SA-PFCM++的优化模型为：

其中，k为当前聚类数目，n为样本点总数量，m,η∈[1,+∞)为模糊聚类的模糊加权系数，决定模糊程度的高低，一般取m,η＝2，a与b分别为赋予隶属度u_ij和划分可能性t_ij的权重，为常数，同时

0≤u_ij,t_ij≤1。d_w(x_i,c_j)表示样本点x_i与聚类中心c_j之间的带权重欧式距离。γ_i为用户定义常数，建议取值为：

采用逐步迭代的方法，逐渐减小目标函数J_SA-PFCM++(X,U,T,V)的值使其收敛到最小，依次更新隶属度矩阵u_ij ^(t)、用户参数γ_j ^(t)、可能性划分矩阵t_ij ^(t)和聚类中心c_j ^(t)，并将所述迭代次数值加1。

其中，更新所述隶属度矩阵u_ij ^(t)的计算公式为：

更新所述隶可能性划分矩阵t_ij ^(t)的计算公式为：

所述聚类中心更新后的值c_j ^(t)的计算公式为：

隶属度矩阵u_ij和可能性划分矩阵t_ij之间的比例关系依赖于赋予它们的权重a与b的选择。如若a大于b，聚类中心c_j将更大程度上依赖于u_ij值；同样地，若b大于a，c_j受t_ij值的影响将会更大。因此，当在高噪声环境中，应设置较高的b减少噪声的干扰；反之，处在低噪环境中，可采用较高的a，改善聚类效果。此外，参数m和η可采用同样的控制方式。

XBS指标使用最小的类与类中心距离平方来衡量类间分离度，使用类中各点与类中心的聚类平方和来衡量类内紧密度。XBS指标是类内紧密度与类间分离度的比值，在类内紧密度与类间分离度之间寻找一个平衡点，使其达到最小，从而得到最优的聚类结果，其计算公式为：

其中，当聚类数c非常大并趋向于样本总数时，XBS指标随着聚类数增加单调递减，类间紧凑度为XBS指标计算公式的分子部分，越大越好，类内分离度XBS指标计算公式的分母部分，越小越好，XBS指标计算结果越大，聚类效果越好。

S105、更新初始参数值，直至达到设定停止条件。

具体的，若当前聚类数目k小于最大类别数k_max，则更新当前聚类数目k加1，按照以上所述步骤重新获取聚类个数和样本集，并依次进行所述聚类中心的选择和更新对应参数，进行新一轮运算，直至当前聚类数目达到最大类别数。

S106、输出设定XBS指标下的聚类数目和类簇。

具体的，对比不同聚类数目下的XBS指标，输出设定(最大)XBS指标下对应的聚类数目和类簇。

本发明的一种基于SA-PFCM++算法的目标分群方法，高质量初始种子选择和自适应簇数目确定并产生更好的聚类质量。首先获取样本集并初始化参数，求出所述样本集的均值；计算每一个样本点与所述均值的第一带权重欧式距离，排序后利用D²采样从采样区间内选择出第一个初始聚类中心；计算每个样本点与所述初始聚类中心的第二带权重欧式距离，排序后利用D²采样从采样区间内选择出下一个初始聚类中心，直至所述初始聚类中心数量达到设定条件；根据所述初始聚类中心迭代更新对应参数，直至所述迭代次数达到设定阈值或聚类成员不再变化，计算对应的XBS指标；更新初始参数值，直至达到设定停止条件；输出设定XBS指标下的簇数目和类簇。该算法有效降低了态势评估中目标分群的难度，提高了决策效率。

以上所揭露的仅为本发明一种较佳实施例而已，当然不能以此来限定本发明之权利范围，本领域普通技术人员可以理解实现上述实施例的全部或部分流程，并依本发明权利要求所作的等同变化，仍属于发明所涵盖的范围。

Claims (7)

1.一种基于SA-PFCM++算法的目标分群方法，其特征在于，包括：

获取样本集并初始化参数，求出所述样本集的均值；

计算每一个样本点与所述均值的第一带权重欧式距离，排序后利用D²采样选择出第一个初始聚类中心；

计算每个样本点与所述初始聚类中心的第二带权重欧式距离，排序后利用D²采样选择出下一个所述初始聚类中心，直至所述初始聚类中心数量达到设定条件；

根据所述初始聚类中心迭代更新对应参数，直至所述迭代次数达到设定阈值或聚类成员不再变化，计算对应的XBS指标；

更新初始参数值，直至达到设定停止条件；

输出最优XBS指标下的簇数目和类簇。

2.如权利要求1所述的一种基于SA-PFCM++算法的目标分群方法，其特征在于，所述获取样本集并初始化参数，求出所述样本集的均值，包括：

获取聚类个数和包含多个数据对象的样本集，并初始化最大类别数、当前聚类数目，模糊权重、迭代次数，并计算出所述样本集的均值。

3.如权利要求2所述的一种基于SA-PFCM++算法的目标分群方法，其特征在于，计算每个样本点与所述均值的第一带权重欧式距离，排序后利用D²采样选择出第一个初始聚类中心，包括：

计算所述样本集中的每个样本点与所述均值的第一带权重欧式距离，将所述第一带权重欧式距离按升序排列后计算每个样本点被选为第一个初始聚类中心的概率值，从设定的种子采样区间内选择出概率值对应的样本点作为第一个初始聚类中心。

4.如权利要求3所述的一种基于SA-PFCM++算法的目标分群方法，其特征在于，计算每个样本点与所述初始聚类中心的第二带权重欧式距离，排序后利用D²采样选择出下一个所述初始聚类中心，直至所述初始聚类中心数量达到设定条件，包括：

计算每个样本点与已有的所述初始聚类中心的第二带权重欧式距离，将所述第二带权重欧式距离按升值排列后计算每个样本点被选为下一个所述初始聚类中心的概率值，并从设定的种子采样区间内选择出概率值对应的样本点作为下一个初始聚类中心，若初始聚类中心数目小于当前聚类数目，则继续下一个初始聚类中心的选择，直至初始聚类中心数目达到当前聚类数目。

5.如权利要求4所述的一种基于SA-PFCM++算法的目标分群方法，其特征在于，根据所述初始聚类中心迭代更新对应参数，直至迭代次数达到设定阈值或聚类成员不再变化，计算对应的XBS指标，包括：

根据所述初始聚类中心迭代更新模糊划分矩阵、用户参数、可能性划分矩阵和聚类中心，若迭代次数未达到设定阈值且聚类成员变化，则继续更新所述参数，并每更新迭代一次，将迭代次数值加1，直至满足所述停止条件，然后计算对应的XBS指标。

6.如权利要求5所述的一种基于SA-PFCM++算法的目标分群方法，其特征在于，更新初始参数值，直至达到设定停止条件，包括：

若当前聚类数目小于最大类别数，则更新当前聚类数目加1，并重新获取聚类个数和样本集，并依次进行所述聚类中心的选择和更新对应参数，直至当前聚类数目达到设定类别数。

7.如权利要求6所述的一种基于SA-PFCM++算法的目标分群方法，其特征在于，输出设定XBS指标下的聚类数目和类簇，包括：

对比不同聚类数目下的XBS指标，输出设定XBS指标下对应的聚类数目和类簇。

Images