基于模糊C均值聚类算法的时序自动机模型

魏秀娟 房亮

（中国电子科技集团公司第二十七研究所 河南省郑州市 450047）

数据关联是将传感器中可能属于目标的数据通过关联算法进行分类，使得每一类观测都形成各自轨迹，并对应着某一目标的运动。由于传感器量测过程中量测误差的存在与目标所处的复杂多变的外界环境，传感器的观测结果不可避免地存在各种不确定性。目标环境先验知识的缺乏通常使目标的数目不能预先确知，同样地，观测数据的真实来源也无法判定。其次，为了有效观测一些采取防止电磁或者红外信号反射和漏射措施后的目标，传感器的观测门限通常设置得较低，这极大可能直接导致量测数据中混杂有大量的虚假量测。观测过程中可能混有的大量漏检或虚假观测情形使得数据关联的准确性成为了工程实践中的困难项。

数据关联是所有跟踪、侦查系统的关键部分。把当前观测数据和已形成的某个轨迹联系起来这一过程需要根据收集数据的传感器的特性，借助已获得的目标数据对新获得数据分组、标记。由于新数据的引入可能会改变关联规则，所以当某组数据不合适地添加进一本不属于该组的错误数据时可能会严重地损害关联过程的准确性。

与传统的数据关联方法最近邻域法、PDA（或JPDA）相比，极大似然法、序贯贝叶斯随机方法和最优贝叶斯方法将模糊判定引入临近观测，继而进行独立估计，这些算法使得关联的准确性大大提高。论文[1]在模糊判定的基础上引入了模糊综合隶属度的概念，用模糊综合隶属度代替经典的关联概率。目前对于模糊数据关联的研究主要集中于针对具体问题设计不同关联算法，而缺少模糊数据关联问题的形式化描述。本文依此展开研究，借助综合模糊隶属度与经典关联的概念，给出模糊时序自动机模型，即基于模糊C 均值聚类算法的时序自动机模型，对模糊数据关联问题进行建模。从形式化的方法上对模糊数据关联展开讨论。

1 基础知识

传感器从 t0=0 开始周期性地接收观测数据，第 k 个周期内的观测值集合记为 Z(k)，集合的基数用|Z(k)|。Z(k)中可能同时有来自多个目标的观测，而关联的处理就是将 Z={Z(k)}k≥1形成正确的分类，即将Z(k)中的观测并入已经确定的类中。

航迹表示为每一类目标中按照时序顺序排列的观测序列，且航迹中允许出现虚警或遗漏观测。遗漏观测用空字符 ε 表示。这里航迹与字符串的含义类似，但字符串中不会出现空字符 ε，具体内容可参考文献[2]。

文献[3]在自动机一般输入的基础上引入了时间序列的概念，使其具有时序性，提出了扩展的时序自动机模型。模型可对数据关联问题进行描述，其接收的语言 L(M) 是所有航迹的集合，因此，数据关联问题可转化为自动机接收语言的问题讨论。

图1：关联过程实例

图2：模糊航迹A2 B1 C2 D2 F3 对应的转移

本文我们形式化地描述数据关联问题。下面先简单介绍一下模糊集、模糊逻辑[4]以及模糊 C 均值聚类算法[1]的相关内容。

F(X)={A|A:X →[0,1]} 表示论域 X 上的所有模糊集合，即从 X到 [0,1]上映射的全体。A(x) 的值越大（离1 越近）表示 x 对于 A的隶属程度越高。模糊集上引入逻辑符号∨，∧表示数值间的取大取小运算，并用⋁X，⋀X 表 X 的上、下确界（最大、最小元）。

为了解决模糊 C 均值聚类算法对于孤立点的敏感性以及因聚类中心选取不同而导致的隶属度的差异问题，文献[1]运用两次模糊 C均值聚类算法，将以目标作为聚类中心和以观测作为聚类中心的两类隶属度融合，提出了模糊综合隶属度的概念。本论文就以模糊综合隶属度为基础，定义模糊数据关联意义下时序自动机的概念。

文献[1]中计算所有模糊综合隶属度后跟初始设置的阈值作比较，模糊综合隶属度大于阈值的目标和量测视为正确关联，这里“模糊”的概念仅体现在隶属度的计算上。根据隶属度大小选取后继时，后继亦单点且分明，这一过程也并非等价于传统意义上模糊的概念。为了保留关联的不确定性，将可能的观测（可设置阈值）均关联上目标，本文将时序自动机状态转移的唯一性[3]进行扩展，并将综合模糊隶属度作为不同关联后继的“可能程度”。

2 模糊数据关联意义下的时序自动机模型

形式化地，我们给出模糊数据关联意义下时序自动机的概念。

模糊时序自动机是一个六元组 M=(T,Q,Σ,δ,(q0,0),F)，T={ti|i∈N}为时间序列且满足 0=t0≤t1≤…≤ti≤…且 |t1-t0|=|ti+1-ti|；Q 为有限状态集，q0∈Q 为初始状态；F 为模糊终止状态集（F(q0)=0）；Σ 为有限输入字母表。

(ε,ti) 对应于传感器观测过程 ti时刻的漏警。具体地，δ 定义如下：

其中表示 zs对于目标 oj的模糊综合隶属程度，即每步转移的“权重”。

3 关联过程实例分析

如图1 所示，t=1 时，观测值为 A1、A2；t=2 时，观测值为B1；t=3 时，观测值为 C1、C2；t=4 时，观测值为 D1、D2、D3；t=5 时，观测值为 E1、E2、E3；t=6 时，观测值为 F1、F2、F3，即 Z(1)={A1,A2}，Z(2)={B1}，Z(3)={C1,C2}，Z(4)={D1,D2,D3}，Z(5)={E1,E2,E3}，Z(6)={F1,F2,F3}。

按照上节定义来构造自动机，记为 A。模糊航迹 A2B1C2D2F3被 A 识别的程度为：

若出现某一项速度的大小或者方向与前若干秒差异较大的需要剔除。注意到上式中的 d(D1,C2)≫d(D2,C2)、d(D3,C2)，且明显观察到观测点 D1与前3s 运动轨迹不一致。由于短时间内速度不可能产生巨大变化，则我们可以通过设置阈值的方式把 d(D1,C2) 项剔除。这样做可以过滤掉虚警点，使转移可能性更高。

模糊航迹 A2B1C2D2F3对应的转移如图2 所示。

其中 r1，r2，r3，r4分别对应于

对于识别程度非零的观测 A2B1C2D2F3，可以利用卡尔曼滤波的方法对目标的状态进行更新。如有需要可参考文献[5]，这里不再赘述。

根据模糊时序自动机转移函数的构造可知同一目标可对应多条可能的航迹，每条航迹匹配有一个隶属度。比较隶属度的大小，识别程度最高的那条即为由 k 个周期内观测值集合对应的可能性最大的航迹。若某一步出现错误匹配并不会完全影响到全部跟踪过程，过程依赖扫描周期内的所有观测值，选择隶属度最大的航迹作为目标航迹可避免经典数据关联过程因为某一步出错而导致的差之千里的结果，这也体现了模糊概念较经典数据关联的优势。

4 小结

进一步地，为了更好地描述现实世界中界限不清的模糊对象，针对论域中任意元素同时考虑隶属度和非隶属度，可得到直觉模糊集的概念。借助直觉模糊集可以使客观世界的模糊性得到更加全面的描述。若将本文中模糊转移函数的综合模糊隶属度替换成直觉模糊隶属度来实现目标与观测的关联，亦可构造对应的模糊时序自动机模型。为了避免重复本文不再展开说明，更多关于直觉模糊集关联算法的内容可参考论文[1,6]。