基于模糊C均值聚類算法的時(shí)序自動(dòng)機(jī)模型

魏秀娟 房亮

（中國(guó)電子科技集團(tuán)公司第二十七研究所 河南省鄭州市 450047）

數(shù)據(jù)關(guān)聯(lián)是將傳感器中可能屬于目標(biāo)的數(shù)據(jù)通過關(guān)聯(lián)算法進(jìn)行分類，使得每一類觀測(cè)都形成各自軌跡，并對(duì)應(yīng)著某一目標(biāo)的運(yùn)動(dòng)。由于傳感器量測(cè)過程中量測(cè)誤差的存在與目標(biāo)所處的復(fù)雜多變的外界環(huán)境，傳感器的觀測(cè)結(jié)果不可避免地存在各種不確定性。目標(biāo)環(huán)境先驗(yàn)知識(shí)的缺乏通常使目標(biāo)的數(shù)目不能預(yù)先確知，同樣地，觀測(cè)數(shù)據(jù)的真實(shí)來源也無法判定。其次，為了有效觀測(cè)一些采取防止電磁或者紅外信號(hào)反射和漏射措施后的目標(biāo)，傳感器的觀測(cè)門限通常設(shè)置得較低，這極大可能直接導(dǎo)致量測(cè)數(shù)據(jù)中混雜有大量的虛假量測(cè)。觀測(cè)過程中可能混有的大量漏檢或虛假觀測(cè)情形使得數(shù)據(jù)關(guān)聯(lián)的準(zhǔn)確性成為了工程實(shí)踐中的困難項(xiàng)。

數(shù)據(jù)關(guān)聯(lián)是所有跟蹤、偵查系統(tǒng)的關(guān)鍵部分。把當(dāng)前觀測(cè)數(shù)據(jù)和已形成的某個(gè)軌跡聯(lián)系起來這一過程需要根據(jù)收集數(shù)據(jù)的傳感器的特性，借助已獲得的目標(biāo)數(shù)據(jù)對(duì)新獲得數(shù)據(jù)分組、標(biāo)記。由于新數(shù)據(jù)的引入可能會(huì)改變關(guān)聯(lián)規(guī)則，所以當(dāng)某組數(shù)據(jù)不合適地添加進(jìn)一本不屬于該組的錯(cuò)誤數(shù)據(jù)時(shí)可能會(huì)嚴(yán)重地?fù)p害關(guān)聯(lián)過程的準(zhǔn)確性。

與傳統(tǒng)的數(shù)據(jù)關(guān)聯(lián)方法最近鄰域法、PDA（或JPDA）相比，極大似然法、序貫貝葉斯隨機(jī)方法和最優(yōu)貝葉斯方法將模糊判定引入臨近觀測(cè)，繼而進(jìn)行獨(dú)立估計(jì)，這些算法使得關(guān)聯(lián)的準(zhǔn)確性大大提高。論文[1]在模糊判定的基礎(chǔ)上引入了模糊綜合隸屬度的概念，用模糊綜合隸屬度代替經(jīng)典的關(guān)聯(lián)概率。目前對(duì)于模糊數(shù)據(jù)關(guān)聯(lián)的研究主要集中于針對(duì)具體問題設(shè)計(jì)不同關(guān)聯(lián)算法，而缺少模糊數(shù)據(jù)關(guān)聯(lián)問題的形式化描述。本文依此展開研究，借助綜合模糊隸屬度與經(jīng)典關(guān)聯(lián)的概念，給出模糊時(shí)序自動(dòng)機(jī)模型，即基于模糊C 均值聚類算法的時(shí)序自動(dòng)機(jī)模型，對(duì)模糊數(shù)據(jù)關(guān)聯(lián)問題進(jìn)行建模。從形式化的方法上對(duì)模糊數(shù)據(jù)關(guān)聯(lián)展開討論。

1 基礎(chǔ)知識(shí)

傳感器從 t0=0 開始周期性地接收觀測(cè)數(shù)據(jù)，第 k 個(gè)周期內(nèi)的觀測(cè)值集合記為 Z(k)，集合的基數(shù)用|Z(k)|。Z(k)中可能同時(shí)有來自多個(gè)目標(biāo)的觀測(cè)，而關(guān)聯(lián)的處理就是將 Z={Z(k)}k≥1形成正確的分類，即將Z(k)中的觀測(cè)并入已經(jīng)確定的類中。

航跡表示為每一類目標(biāo)中按照時(shí)序順序排列的觀測(cè)序列，且航跡中允許出現(xiàn)虛警或遺漏觀測(cè)。遺漏觀測(cè)用空字符 ε 表示。這里航跡與字符串的含義類似，但字符串中不會(huì)出現(xiàn)空字符 ε，具體內(nèi)容可參考文獻(xiàn)[2]。

文獻(xiàn)[3]在自動(dòng)機(jī)一般輸入的基礎(chǔ)上引入了時(shí)間序列的概念，使其具有時(shí)序性，提出了擴(kuò)展的時(shí)序自動(dòng)機(jī)模型。模型可對(duì)數(shù)據(jù)關(guān)聯(lián)問題進(jìn)行描述，其接收的語言 L(M) 是所有航跡的集合，因此，數(shù)據(jù)關(guān)聯(lián)問題可轉(zhuǎn)化為自動(dòng)機(jī)接收語言的問題討論。

圖1：關(guān)聯(lián)過程實(shí)例

圖2：模糊航跡A2 B1 C2 D2 F3 對(duì)應(yīng)的轉(zhuǎn)移

本文我們形式化地描述數(shù)據(jù)關(guān)聯(lián)問題。下面先簡(jiǎn)單介紹一下模糊集、模糊邏輯[4]以及模糊 C 均值聚類算法[1]的相關(guān)內(nèi)容。

F(X)={A|A:X →[0,1]} 表示論域 X 上的所有模糊集合，即從 X到 [0,1]上映射的全體。A(x) 的值越大（離1 越近）表示 x 對(duì)于 A的隸屬程度越高。模糊集上引入邏輯符號(hào)∨，∧表示數(shù)值間的取大取小運(yùn)算，并用?X，?X 表 X 的上、下確界（最大、最小元）。

為了解決模糊 C 均值聚類算法對(duì)于孤立點(diǎn)的敏感性以及因聚類中心選取不同而導(dǎo)致的隸屬度的差異問題，文獻(xiàn)[1]運(yùn)用兩次模糊 C均值聚類算法，將以目標(biāo)作為聚類中心和以觀測(cè)作為聚類中心的兩類隸屬度融合，提出了模糊綜合隸屬度的概念。本論文就以模糊綜合隸屬度為基礎(chǔ)，定義模糊數(shù)據(jù)關(guān)聯(lián)意義下時(shí)序自動(dòng)機(jī)的概念。

文獻(xiàn)[1]中計(jì)算所有模糊綜合隸屬度后跟初始設(shè)置的閾值作比較，模糊綜合隸屬度大于閾值的目標(biāo)和量測(cè)視為正確關(guān)聯(lián)，這里“模糊”的概念僅體現(xiàn)在隸屬度的計(jì)算上。根據(jù)隸屬度大小選取后繼時(shí)，后繼亦單點(diǎn)且分明，這一過程也并非等價(jià)于傳統(tǒng)意義上模糊的概念。為了保留關(guān)聯(lián)的不確定性，將可能的觀測(cè)（可設(shè)置閾值）均關(guān)聯(lián)上目標(biāo)，本文將時(shí)序自動(dòng)機(jī)狀態(tài)轉(zhuǎn)移的唯一性[3]進(jìn)行擴(kuò)展，并將綜合模糊隸屬度作為不同關(guān)聯(lián)后繼的“可能程度”。

2 模糊數(shù)據(jù)關(guān)聯(lián)意義下的時(shí)序自動(dòng)機(jī)模型

形式化地，我們給出模糊數(shù)據(jù)關(guān)聯(lián)意義下時(shí)序自動(dòng)機(jī)的概念。

模糊時(shí)序自動(dòng)機(jī)是一個(gè)六元組 M=(T,Q,Σ,δ,(q0,0),F)，T={ti|i∈N}為時(shí)間序列且滿足 0=t0≤t1≤…≤ti≤…且 |t1-t0|=|ti+1-ti|；Q 為有限狀態(tài)集，q0∈Q 為初始狀態(tài)；F 為模糊終止?fàn)顟B(tài)集（F(q0)=0）；Σ 為有限輸入字母表。

(ε,ti) 對(duì)應(yīng)于傳感器觀測(cè)過程 ti時(shí)刻的漏警。具體地，δ 定義如下：

其中表示 zs對(duì)于目標(biāo) oj的模糊綜合隸屬程度，即每步轉(zhuǎn)移的“權(quán)重”。

3 關(guān)聯(lián)過程實(shí)例分析

如圖1 所示，t=1 時(shí)，觀測(cè)值為 A1、A2；t=2 時(shí)，觀測(cè)值為B1；t=3 時(shí)，觀測(cè)值為 C1、C2；t=4 時(shí)，觀測(cè)值為 D1、D2、D3；t=5 時(shí)，觀測(cè)值為 E1、E2、E3；t=6 時(shí)，觀測(cè)值為 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}。

按照上節(jié)定義來構(gòu)造自動(dòng)機(jī)，記為 A。模糊航跡 A2B1C2D2F3被 A 識(shí)別的程度為：

若出現(xiàn)某一項(xiàng)速度的大小或者方向與前若干秒差異較大的需要剔除。注意到上式中的 d(D1,C2)?d(D2,C2)、d(D3,C2)，且明顯觀察到觀測(cè)點(diǎn) D1與前3s 運(yùn)動(dòng)軌跡不一致。由于短時(shí)間內(nèi)速度不可能產(chǎn)生巨大變化，則我們可以通過設(shè)置閾值的方式把 d(D1,C2) 項(xiàng)剔除。這樣做可以過濾掉虛警點(diǎn)，使轉(zhuǎn)移可能性更高。

模糊航跡 A2B1C2D2F3對(duì)應(yīng)的轉(zhuǎn)移如圖2 所示。

其中 r1，r2，r3，r4分別對(duì)應(yīng)于

對(duì)于識(shí)別程度非零的觀測(cè) A2B1C2D2F3，可以利用卡爾曼濾波的方法對(duì)目標(biāo)的狀態(tài)進(jìn)行更新。如有需要可參考文獻(xiàn)[5]，這里不再贅述。

根據(jù)模糊時(shí)序自動(dòng)機(jī)轉(zhuǎn)移函數(shù)的構(gòu)造可知同一目標(biāo)可對(duì)應(yīng)多條可能的航跡，每條航跡匹配有一個(gè)隸屬度。比較隸屬度的大小，識(shí)別程度最高的那條即為由 k 個(gè)周期內(nèi)觀測(cè)值集合對(duì)應(yīng)的可能性最大的航跡。若某一步出現(xiàn)錯(cuò)誤匹配并不會(huì)完全影響到全部跟蹤過程，過程依賴掃描周期內(nèi)的所有觀測(cè)值，選擇隸屬度最大的航跡作為目標(biāo)航跡可避免經(jīng)典數(shù)據(jù)關(guān)聯(lián)過程因?yàn)槟骋徊匠鲥e(cuò)而導(dǎo)致的差之千里的結(jié)果，這也體現(xiàn)了模糊概念較經(jīng)典數(shù)據(jù)關(guān)聯(lián)的優(yōu)勢(shì)。

4 小結(jié)

進(jìn)一步地，為了更好地描述現(xiàn)實(shí)世界中界限不清的模糊對(duì)象，針對(duì)論域中任意元素同時(shí)考慮隸屬度和非隸屬度，可得到直覺模糊集的概念。借助直覺模糊集可以使客觀世界的模糊性得到更加全面的描述。若將本文中模糊轉(zhuǎn)移函數(shù)的綜合模糊隸屬度替換成直覺模糊隸屬度來實(shí)現(xiàn)目標(biāo)與觀測(cè)的關(guān)聯(lián)，亦可構(gòu)造對(duì)應(yīng)的模糊時(shí)序自動(dòng)機(jī)模型。為了避免重復(fù)本文不再展開說明，更多關(guān)于直覺模糊集關(guān)聯(lián)算法的內(nèi)容可參考論文[1,6]。