[發(fā)明專利]一種集群目標的動態(tài)聚類方法

有效

• 申請?zhí)枺?/td>: 201210113573.6
• 申請日: 2012-04-17
• 公開（公告）號: CN102663113A
• 公開（公告）日: 2012-09-12
• 發(fā)明（設(shè)計）人: 覃征;江子能;盧正才;張海生;李鳳翔
• 申請（專利權(quán)）人: 清華大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 西安智大知識產(chǎn)權(quán)代理事務(wù)所 61215
• 代理人: 賈玉健

1.一種集群目標的動態(tài)聚類方法，其特征在于：包括以下步驟：

步驟一，加載預(yù)定義參數(shù)和目標數(shù)據(jù)；

步驟二，初始化簇；

步驟三，將已經(jīng)存在于簇中的目標進行離線處理，計算簇的速度和加速度信息以及對這些簇進行排序；

步驟四，將已經(jīng)存在于簇中的目標進行在線處理，比較簇和目標的距離然后分別進行處理，具體方法是：

首先，遍歷每一個簇中的每一個目標數(shù)據(jù)，計算數(shù)據(jù)O_i到預(yù)測位置V_p的距離L_o，如果L_o小于本簇的半徑R，則不對數(shù)據(jù)O_i進行處理，仍將數(shù)據(jù)O_i留在此簇中；

如果L_o小于本簇的半徑R，則分以下兩種情況進行處理：

如果L_o小于簇的最大距離maxDist，則將本簇的半徑R更新為L_o；

如果L_o大于簇的最大距離maxDist，則將數(shù)據(jù)O_i從簇中移除，將數(shù)據(jù)O_i加入鏈表EList中；

最后，當所有目標都處理完成時，將存儲在鏈表WDList中的目標聚類生成新簇；

步驟五，對新目標聚類生成新簇；

步驟六，將新簇和老簇進行融合：先對所有老簇按照到原點距離的大小進行排序，然后根據(jù)老簇和上一個新簇比較的結(jié)果來減少老簇和下一個新簇融合的計算量，同時更新簇信息，其中，老簇指新簇生成前就存在的簇。

2.根據(jù)權(quán)利要求1所述動態(tài)聚類方法，其特征在于，所述步驟三中計算簇的速度是以多數(shù)表決的方式來進行，假定存在一個速度V_i，如果簇中在[V_i-ξ，V_i+ξ，]范圍內(nèi)的數(shù)據(jù)最多，則V_i即為簇的速度，ξ是一個經(jīng)驗值，跟V_i的值正相關(guān)；

所述步驟三中計算簇的加速度是以多數(shù)表決的方式來進行，假定存在一個加速度a_i，如果簇中在[a_i-μ，a_i+μ，]范圍內(nèi)的數(shù)據(jù)最多，則a_i即為簇的加速度，μ是一個經(jīng)驗值，跟V_i的值正相關(guān)。

3.根據(jù)權(quán)利要求2所述動態(tài)聚類方法，其特征在于，所述排序的方法是：根據(jù)簇的速度和加速度，預(yù)測一定時間間隔后的簇的位置，然后遍歷一遍所有的簇，計算簇的預(yù)測位置V_p到原點的距離L_p，根據(jù)L_p的大小進行排序，并保存在一個鏈表中。

4.根據(jù)權(quán)利要求1所述動態(tài)聚類方法，其特征在于，在步驟六后繼續(xù)進行步驟三。

5.根據(jù)權(quán)利要求1所述動態(tài)聚類方法，其特征在于，所述步驟六中只有當簇中逃離的數(shù)據(jù)大于閾值時，才更新簇的信息。

6.根據(jù)權(quán)利要求1所述動態(tài)聚類方法，其特征在于，所述步驟六中根據(jù)老簇和上一個新簇比較的結(jié)果來減少老簇和下一個新簇融合的計算量，同時更新簇信息的規(guī)則是：

假定新簇鏈表NOList中有M個簇，分別是NC₁，NC₂，...，NC_q，NC_q+1，...，NC_m，到原點的距離分別是NL₁，NL₂，...，NL_q，NL_q+1，...，NL_m且NL₁＜NL₂＜...＜NL_q＜NL_q+1＜...＜NL_m；老簇鏈表中CList中有N個簇，分別是OC₁，OC₂，...，OC_s，OC_s+1，...，OC_n，到原點的距離分別是CL₁，CL₂，...，CL_s，CL_s+1，...，CL_n且CL₁＜CL₂＜...CL_s＜CL_s+1＜...＜CL_n；如果CL_s-NL_q＞maxDist，則簇OC_s不能和NC₁，NC₂，...，NC_q融合，簇OC_s+1，...，OC_n也不能和NC₁，NC₂，...，NC_q融合，由此相應(yīng)地較少了一個或者多個計算量。