基于模糊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]。