[發(fā)明專利]一種軌跡數(shù)據(jù)參數(shù)自適應(yīng)的聚類方法

有效

• 申請?zhí)枺?/td>: 202011374727.8
• 申請日: 2020-11-30
• 公開（公告）號(hào): CN112488196B
• 公開（公告）日: 2022-07-29
• 發(fā)明（設(shè)計(jì)）人: 徐文進(jìn)
• 申請（專利權(quán)）人: 青島科技大學(xué)
• 主分類號(hào): G06K9/62
• 分類號(hào): G06K9/62;G06F16/29
• 代理公司: 青島智地領(lǐng)創(chuàng)專利代理有限公司 37252
• 代理人: 陳海濱

1.一種軌跡數(shù)據(jù)參數(shù)自適應(yīng)的聚類方法，其特征在于，包括以下步驟：

步驟1：輸入總的軌跡數(shù)據(jù)，設(shè)置參數(shù)T和α，其中，T為取數(shù)據(jù)的時(shí)間間隔，α為置信系數(shù)；

步驟2：總的軌跡數(shù)據(jù)中每隔時(shí)間間隔T的數(shù)據(jù)構(gòu)成一個(gè)數(shù)據(jù)塊S_i，其中，S₁代表第一個(gè)時(shí)間間隔T的數(shù)據(jù)塊，S₂代表第二個(gè)時(shí)間間隔T的數(shù)據(jù)塊，以此類推；

將S₁和S₂這兩個(gè)數(shù)據(jù)塊取交集，即S₁∩S₂，獲得交集數(shù)據(jù)，交集數(shù)據(jù)存入交集單元；

將S₁和S₂這兩個(gè)數(shù)據(jù)塊取并集，即S₁∪S₂，獲得并集數(shù)據(jù)，并集數(shù)據(jù)存入并集單元；

步驟3：利用交集單元中的數(shù)據(jù)獲取置信區(qū)間，獲取并集單元中落入置信區(qū)間的數(shù)據(jù)個(gè)數(shù)n，并集單元中總數(shù)據(jù)個(gè)數(shù)為N，判斷n/N是否大于等于1-α，若不滿足則執(zhí)行步驟4；若滿足則計(jì)算交集單元里的數(shù)據(jù)分布情況和并集單元里的數(shù)據(jù)分布情況，再計(jì)算分布散度；

判斷分布散度是否接近0，若滿足則執(zhí)行步驟5，若不滿足則執(zhí)行步驟4；

利用交集單元中的數(shù)據(jù)獲取置信區(qū)間的過程為：

交集單元中的數(shù)據(jù)為{A₁，......，A_k}，每個(gè)數(shù)據(jù)包括經(jīng)度值x_k和緯度值y_k；

則置信區(qū)間包括k個(gè)置信區(qū)間，分別為：

第一置信區(qū)間[x₁(1-α)，x₁(1+α)]，[y₁(1-α)，y₁(1+α)]；

……

第k置信區(qū)間[x_k(1-α)，x_k(1+α)]，[y_k(1-α)，y_k(1+α)]；

并集單元中落入置信區(qū)間的數(shù)據(jù)個(gè)數(shù)的確定過程為：

遍歷并集單元中的所有數(shù)據(jù)，找出能夠落入以上置信區(qū)間的數(shù)據(jù)的個(gè)數(shù)n；

步驟4：取下一個(gè)時(shí)間間隔T的數(shù)據(jù)塊，將下一個(gè)時(shí)間間隔T的數(shù)據(jù)塊與并集單元取交集，更新交集單元；

將下一個(gè)時(shí)間間隔T的數(shù)據(jù)塊與并集單元取并集，更新并集單元；

返回步驟3；

步驟5：將獲得的交集單元中的數(shù)據(jù)作為樣本點(diǎn)，根據(jù)樣本點(diǎn)，計(jì)算DBSCAN算法要用的參數(shù)eps和MinPts；

計(jì)算DBSCAN算法要用的參數(shù)eps的過程為：

將數(shù)據(jù)的經(jīng)度值設(shè)為x軸，緯度值設(shè)為y軸，樣本點(diǎn)擴(kuò)展為二維數(shù)據(jù)為(x_k，y_k)，找到樣本點(diǎn)中經(jīng)度值的最大值x_max和最小值x_min，緯度值的最大值y_max和最小值x_min，構(gòu)建最大值點(diǎn)(x_max，y_max)，最小值點(diǎn)(x_min，y_min)，則最大值點(diǎn)與最小值點(diǎn)的距離為l；

則

其中，k為樣本點(diǎn)的個(gè)數(shù)；

計(jì)算MinPts的過程為：

將k個(gè)樣本點(diǎn)的經(jīng)度和維度映射為矩陣，上式計(jì)算的eps取整為h，以h*h的窗口為大小，以1*1的步長進(jìn)行滑動(dòng)，計(jì)算出窗口中最多的點(diǎn)的個(gè)數(shù)與最少的點(diǎn)個(gè)數(shù)取均值就為MinPts的值；

步驟6：根據(jù)步驟5得到的eps和MinPts，利用DBSCAN算法進(jìn)行密度聚類，密度聚類后，返回步驟4，直至所有數(shù)據(jù)塊遍歷完成。

2.根據(jù)權(quán)利要求1所述的一種軌跡數(shù)據(jù)參數(shù)自適應(yīng)的聚類方法，其特征在于，計(jì)算交集單元里的數(shù)據(jù)分布情況的公式為：

其中，P_j為數(shù)據(jù)A_j在交集單元里的分布情況，代表交集單元里所有數(shù)據(jù)的均值，代表的是A_j與的歐氏距離，∑_k≠jd(A_j，A_k)代表A_j與交集單元里除去A_j本身的其它所有數(shù)據(jù)的歐氏距離的總和；

計(jì)算并集單元里的數(shù)據(jù)分布情況為計(jì)算并集單元里與交集單元重合的那部分?jǐn)?shù)據(jù)的分布情況，實(shí)際上就是交集單元的數(shù)據(jù)在并集單元里的分布情況；

公式為：

其中，Q_j為數(shù)據(jù)A_j在并集單元里的分布情況，代表交集單元里所有數(shù)據(jù)的均值，m代表交集單元的數(shù)據(jù)總數(shù)，B_m代表交集單元的所有數(shù)據(jù)，A_j∈B_m，代表的是A_j與的歐氏距離，∑_m≠jd(A_j，B_m)代表A_j與并集單元里除去A_j本身的其它所有數(shù)據(jù)的歐氏距離的總和；

分布散度計(jì)算公式為：

其中，D(P||Q)代表分布散度。