一种融合高斯聚类的粒子滤波方法

广东石油化工学院学报

8 月 Journal of Guangdong University of Petrochemical Technology

Vol.27 No.4August 2017

一种融合高斯聚类的粒子滤波方法+

陈海亮，黎树俊，邓文天，陈珂

(广东石油化工学院计算机科学与技术系，广东茂名525000)

摘要：为了解决粒子滤波存在粒子退化、噪声干扰和计算量大等问题，提出了一种融合髙斯聚类的粒子滤波方法。将给定 粒子划分为许多类，采用使目标函数最小方法，把搜寻到的最佳隶属度和最佳粒子更新对应的位置作为聚类中心，有效地 完成数据关联融合。实验证明，与传统粒子滤波算法相比，该方法提髙了粒子滤波的运算速度，降低了计算量，具有更髙的 滤波效率和滤波精度。

关键词：目标跟踪粒子滤波算法;髙斯聚类

文献标识码

;

中图分类号：TP391

：A

文章编号

：2095 - 2562(2017)04 - 0038 - 05

目标识别与跟踪是机器人定位与导航的重要研究内容之一，也是当前运动序列数据研究中尚未完全 解决的难题。作为贝叶斯跟踪方法的代表，基于粒子滤波的跟踪方法已成为研究焦点。但该方法目前存 在一些技术难点：粒子退化、目标姿态的变化以及噪声等，导致跟踪效果较差；目标的快速移动以及多目标 跟踪要求粒子滤波采用大量粒子，算法的计算代价很大等。针对这些问题，近年来已有很多学者将聚类算 法应用于粒子滤波及目标跟踪，包括粒子滤波目标跟踪算法[1]，分布模糊聚类粒子滤波（DFCM-法[2]，模糊C均值(FCM)聚类粒子滤波算法[3]，空间域减法聚类粒子滤波算法。

虽然聚类能降低粒子数目，从而提高运算效率，但在高维情况下仍然保持较大的粒子滤波运算量，本 文把高斯聚类融合在粒子滤波中，提出了基于高斯聚类的粒子滤波方法（GC - PF)，目的是将给定的数据 划分为许多类，采用使目标函数最小的方法，将找到的最好的隶属度和最佳数据更新对应的位置作为聚类 中心。该算法有效地完成数据关联融合，提高运算速度。

RPF)方

1粒子滤波算法

粒子滤波基本思想是利用状态向量的条件分布，获取一组随机样本的集合（粒子），然后依据观测计

算，调整粒子权重与位置，从而修正原始的条件分布[4_6]。

i表亦&时刻目标％的后验概率p (%〇:&丨^11)，丨4 &，纟=〇, 1，…，aU是对应权值为丨<:&，〖=〇, 1，…，％丨的粒子集，其中=丨'，y = 〇, 1，…，w是〇,…，&时刻的状

N

已知状态先验概率；?（ ％。），I ，乂 h

态。权值归一化为3^4 = 1，则&时刻目标状态的后验概率表示为

i = 1

N

山

式中：权值用重要采样法筛选。

以（1)

若可由重要密度函数表示，则权值为 *

*

收稿日期

：2017 - 01 - 10;修回日期：2017 - 06 - 02

基金项目：广东省自然科学基金项目（2016A030307049);广东省科技计划项目（2014A010104016,2015B090903084);大学生创新创业训

练与培育项目（201611656002,201611656029,2016pyC049,2016pyA031，2016pyA033)作者简介：陈海亮（1994一），男，广东湛江人，在读本科，主要研究方向为机器人。通讯简介：陈珂（1964—），男，黑龙江牡丹江人，教授，主要研究方向为机器人、数据挖掘与机器学习。

第4期陈海亮等:一种融合高斯聚类的粒子滤波方法39

i p(x0：k ^ zi：k)Whccqn v -^(x〇i ： k \\^z i：k /) z

因为重要密度能分解为

⑵

zl：k)q(xk\\

通过丨丨

q(x0：k\\ zl：k) = q(xk\\

那么通过I

⑶

1)求得粒子集可

I〜J求得的粒子和

以得到新的粒子集Ui hi。后验的概率密度函数为

p(x0：k I ^〇： )

p(zk I X0：k 9

P(:山 11-1)

,

p( X0：k I zl：k-]

p(zk \\ xk)p(xk \\ I )

⑷

将式(2)和式(3)代入式(4)，可得到重要性权值更新公式:

k q(^k\\ 4：^-i

如

果

p(zk \\ xl)p(zkl \\

，2：1:A;) =

I I ，A)，则重要密度函数唯一依赖于

l ^v.k-i)切k—1

i p(zk \\ xl)p(xkl \\ xl^)

, i \\ k \\q\\xk I ,zl:k)

(5)

，经计算，只存储粒子

Uhl，而

不用考虑粒子集以往的量测值调整的权值为

W ^

i

OC W ]^_ I

i p(zk \\ zl)p(xkl \\ xl^)

/ j | k \\q\\xk \\ xk_ i ^ zk)

(6)

(7)

由于粒子滤波算法搜索其易于计算的先验概率密度，从而作为重要密度函数，即

q(xkl I a；Li ,zk) = p(xkl I a；Li)

将式(7)代入式(6)，可以将重要性权值化简为

wl^piz,, I x\\)

权值W归一化

(8)

(9)

Ns

而后验概率密度

I

可表示为

p(xk \\ zvk) aj^“wkld(xk - Xlk)

粒子滤波算法过程如下：

(1)由先验概率p (〜）计算粒子群，I蚪。i粒子权值均为(2)

(10)

在&时刻，对粒子权值进行更新，并且归一化，计算A时刻的最小均方估计

N/Ns

xk = S wlxl

i = l

(11)

:〇，l，2，...，AU;

(3) 经过重采样，产生新的粒子集合

(4) 利用状态函数计算预测参数;(5)

A = A + 1 时，转到(2)。

2融合高斯聚类的粒子滤波算法（GC-PF)

本文将高斯聚类技术引入到粒子滤波，考虑到空间粒子分布合理性，对空间上邻近粒子加权聚类为若

干类，以类中质心代替该类粒子参与运算。不仅大大减少了粒子数目，而且由于对聚类的粒子的权值进行 了平滑处理，有效地解决粒子退化及粒子多样性差的问题。另外，在每次进行粒子更新之前，应用聚类算 法对粒子进行优化，这样就减少了参与迭代计算的粒子数目，从而降低了粒子滤波算法的计算量。

以多目标跟踪为例，介绍高斯聚类粒子滤波算法。首先假设〃维空间中接收到了％个观测|&，&，

…，A；mA;丨，共有（cy，y = 1，2,…，c)个目标，聚类的模糊隶属度如下：

式中：&.为观测A属于聚类中心$.的概率。

;=1

土/^• = 1，V G [〇，1]

(12)

40广东石油化工学院学报2017 年

聚类算法的代价函数定义为

E=J]±^j-d(xi,xj)2 = l,y[〇A]

i = lj = 1

(13)

式中：以^，q.)为观测值 '与聚类中心q.之间的欧式距离。

依据信息理论，借助最大熵原理，具有最大熵值的隶属度即为最小无偏地描述数据点和类中心的隶属 度。由香农熵原理，隶属度的表达为

H=H(^)= -

式（12)和式（13)作为约束条件，最大化式（14)，应用拉格朗日乘子法，定义优化目标函数为

/( t/，C) = - 2 2

式中：A

(14)

In\"。•- 2 J 2 ( ^，9 )2 + 2 A 2 (〜

1)(15)

w均为拉格朗日乘子。

exp(

2exp(

最大化式（15)可得到：

d(xi9 Cj)2

^2?d(xi9 Cj)2

,;G [i9c]

(16)

^2?\"\"\"

式（16)的隶属度&.是最小偏差估计。是高斯形式，故为高斯聚类。针对非线性动态离散系统[5]可得：

(17)

为m维的观测向量；％和w分别为系统噪声和观测噪声。

[ = ztht(xt ,vt)式中：

为t时刻的n维状态变量；

高斯聚类粒子滤波算法如下：

(1)由先验概率p (&)获得粒子群U丨<=i，粒子权值为均1/ %。(2八时刻，计算并更新粒子权值

Wlt = — Cn J_p(zt\\ Xtl)] (i = 1,2, •••, N)(18)

式中：为归一化常数。

通过式（11)可得£时刻未知参数a;的最小均方估计。

(3) 重采样。根据重要性权值重新采样得到一组新粒子，〖=〇, 1，2,…，AU，并重新分配粒子的权 值 1^ = 1/%。

(4) 预测。利用状态方程/预测未知参数<+1。(5) 时刻n

+ 1，转到(2)。

3仿真实验及分析

文献[5]实验方法，以DR/GPS组合导航系统模型为例进行仿真，建立组合导航模型如下：

毛=

W，Zt = ZiU, + %)

(19)

式中：灸，t i = diag[

Fe _10-0

T

1 0

J

为状态转移矩阵，，圪的表达式分别为( -1 + (l

aeT+ ea^T)ae-2-)a:1

-=e_%T W

， =Fn

-10-0

T

( - 1 + (21 0

nT+e^T)an-2-(1 +en )an

e — 'a T\\ - 1

T(20)

观测矩阵和噪声矩阵分别为

h(Xt) = [xe xn Ka2「T^v2e + v2j

(21)

第4期陈海亮等:一种融合高斯聚类的粒子滤波方法41

Wt = [0 0 we

yV(0，^)分布的白噪声序列；

似然概率密度函数可近似为

0 0

wn]\\ = Vt =

v2 v3 v4]t

(22)

式中：= l/r6，am = l/r„，、r„分别东向与北向相关加速度的时间常数％ %、表7K为适应#(〇, ^ )及

心表示观测噪声，主要来自GPS信号的东向与北向，可近似成(0,5丨），（0,

^); 为陀螺漂移，近似(0，）；es是里程计观测噪声，其不是高斯噪声。

p(zt\\xt) = yexp[ - ~j(zt -

+ yexp[ -

仿真初始条件和有关参数为：T7 = 1 s，^ = (0.3m/s2)2〇

- n)T ~( -

Rlzt

+ n)T R~l (zt -

- n)]

+ n)]

(23)

Z = (0.3 mm/s2 )2，' = = 1，^ = ( 15 m)2，^ = ( 16m)2，

初始状态值、初始方差阵、初始噪声和观测噪声方差阵分别表示为& = [0 0.1 0 0 0.1 0]t，Pq =

diag(100，l，0.04，100，l，0.04)，/2。=diag(152，162,0.0052,0.72)，g。=diag(0.12 , 0.52 , 0.32 , 0.12 , 0.52 , 0.32)。

仿真时间设为500 s，且在150〜300 s内目标做东向、北向变加速度运动，加速度均为3sin & m/s2,过程噪声方差不变，均值扩大为原来的5倍;在300〜500 s时间内，目标做东向、北向匀加速运动，加速度为2

m/s2，将观测噪声协方差扩大为初始值的3倍。分别采用粒子滤波（PF)和高斯聚类粒子滤波（GC - PF)算

法进行仿真。图1和图2给出了 PF和GC-PF东向和北向误差结果的对比。

从图1、图2可以看出，针对噪声等因素的不规则变化，PF算法滤波收敛速度及稳定性不如GC - PF 算法，其原因是PF算法有粒子退化和固定粒子数等问题，而和分布形式，有效地提高了滤波收敛速度和滤波精度。

为了验证粒子数对滤波算法性能的影响，分别选用了 500个和1 000个粒子，取过程噪声方差= 10, 量测噪声方差/? = 1，以滤波效率^滤波误差(均方根误差平均值f

GC-PF算法则能够自适应的改变粒子规模

ARMSE)以及估计时间作为评价指标，对

PF和GC - PF的滤波结果进行比较，结果如表1所示。

表1

算法

不同粒子数下两种算法的仿真结果比较

估计时间/s0.556 42.062 7

算法

N

5001 000

Tjl%1.004 01.046 0

Earmse

0.199 30.095 6

N

5001 000

Tjl%7.968 114.706 0

Earmse

0.025 10.006 8

估计时间/s0.287 40.866 4

PFGC-PF

当粒子数均取/V = 500时，PF的滤波精度为0.199 3，GC - PF的滤波精度为0.025 1，后者的滤波精度

GC-PF的估计时间仅为PF的一半，为0.287 4,同时，GC - PF的滤波效率是PF的8 倍，这说明GC-PF用更短的时间达到了更高的滤波精度；当粒子数增加到1 000时，PF的滤波精度有多

约是前者的8倍，而

提高，但估计时间却增加了，因此滤波效率没有任何改善，这说明提高粒子滤波算法的滤波效率和滤波精 度是以估计时间的增加为代价的，而增加粒子数后，尽管GC - PF的估计时间也有所增加，但仍为PF的一 半，同时，滤波精度和滤波效率都要高出PF约4倍。

42广东石油化工学院学报2017 年

4 结语

聚类是一种常见的数据分析工具，本文融合聚类思想，将高斯聚类引入到粒子滤波算法中，包括模拟 数据划分、寻找目标函数的最小值、寻找最佳隶属度和聚类中心以及完成数据的关联融合。实验验证，融 合高斯聚类的粒子滤波算法有效缓解了粒子退化现象，降低了计算量，具有更高的滤波效率和滤波精度。

[参考文献]

[1] 李科，徐克虎.基于特征融合和聚类函数平滑采样优化的粒子滤波目标跟踪算法[J].计算机科学，

[2] 张俊根，姬红兵，采用粒子滤波和模糊聚类法的非线性多目标跟踪[J].西安电子科技大学学报（自然科学版），2010,37

(4)：636-641.

[3] 文传军，汪庆淼，詹永照，均衡模糊C均值聚类算法[J].计算机科学，2014,41(8):250-253.

[4] GORDON N J,SALMOND D J,SMITH A F M. A Novel Approach to Nonlinear and Non - Gaussian Bayesian Estimation[j] .Radar and Signal Processing, IEEE Proceedings F, 1993,140(2) ： 107 - 113.

[5] 屈耀红，凌琼，闫建国，等.无人机〇11/〇?3/1^导航中风场估计仿真[>[].系统仿真学报，2009,21(7):1822- 1825.[6] 柯文德，蔡则苏，李家兰.机器人同时定位与地图构建技术研究[J].计算机应用研究，2010,27(4):1216- 1220.

A Particle Filter Method with Gaussian Clustering

CHEN Hailiang, LI Shujun, DENG Wentian, CHEN Ke

(Department of Computer Science and Technology, Guangdong University of Petrochemical Technology, Maoming 525000，China)

Abstract: This paper proposes a particle filter method with gaussian clustering in order to solve the problems of particle? degeneracy and

noise interference existing in particle filter, and large amount of calculation in the particle filtering algorithm before. The given particles are divided into many categories, and the minimum membership function of the objective function is used as the clustering center to locate the optimum particle size. Comprehensive experimental results demonstrate that the new algorithm improves the particle filter calculation speed, reduces the computational complexity of the traditional particle filter algorithm, and highly increases the filtering efficiency and accuracy. Key words：Target tracking; Particle filter algorithm; Gaussian clustering

(责任编辑：黄容)

(上接第37页）

Research of MOOC Learners ’ Performance Prediction

Based on Relief Feature Selection

MA Cheng

(Computer Department, Bengbu College, Bengbu 233000,China)

Abstract ： Based on the edX open data, this paper divides learners，characteristics into three categories, and the Relief Algorithm is used to

select seven important features. Then several classical supervised machine learning methods are used to build a model for learners，perfor­

mance prediction. The experiments show that learners， performance is mainly determined by learners， type and learners， behavior. The comparison of the prediction results with the evaluation metrics verifies that Logistic Regression Algorithm and Support Vector Machine Algo­rithm can accurately predict learners，performance.Key words：Data Mining; MOOC; Prediction

(责任编辑：黄容)