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

有效

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

本發(fā)明公開了一種軌跡數(shù)據(jù)參數(shù)自適應(yīng)的聚類方法，首先設(shè)置參數(shù)T和α，再根據(jù)時間維度取數(shù)據(jù)中的交集的部分作為將要處理的樣本點(diǎn)，引入置信區(qū)間和分布散度為評價標(biāo)準(zhǔn)，保證了樣本點(diǎn)數(shù)據(jù)的有效性和準(zhǔn)確性，從而減少了處理數(shù)據(jù)量。之后，利用交集的數(shù)據(jù)引入一種點(diǎn)密度的度量的方法解決eps值設(shè)定問題，并根據(jù)滑動窗口的方式找出單位最大樣本個數(shù)與單位最小樣本個數(shù)，取其均值的操作來作為MinPts的設(shè)置值。本發(fā)明提供的軌跡數(shù)據(jù)參數(shù)自適應(yīng)的聚類方法不僅解決了DBSCAN聚類算法本身只能處理小量數(shù)據(jù)的缺點(diǎn)，還能自適應(yīng)的設(shè)定DBSCAN聚類算法中的eps和MinPts值，解決現(xiàn)有技術(shù)中只能根據(jù)經(jīng)驗(yàn)人工設(shè)定，導(dǎo)致的聚類效果不理想的問題。

技術(shù)領(lǐng)域

本發(fā)明涉及數(shù)據(jù)聚類算法領(lǐng)域，具體涉及一種軌跡數(shù)據(jù)參數(shù)自適應(yīng)的聚類方法。

背景技術(shù)

如今的數(shù)據(jù)熱點(diǎn)聚類的算法，主要是使用一種DBSCAN算法，DBSCAN算法作為一種密度聚類被學(xué)者廣泛的應(yīng)用于數(shù)據(jù)的挖掘與分析中，該算法衡量其密度大小取決于單位超球里樣本數(shù)量，不僅在聚類時可以聚類出不同形狀的簇，而且可以探索出離群點(diǎn)。但DBSCAN算法在使用之前必須設(shè)置兩個參數(shù)EPS和MinPts，這兩個參數(shù)是根據(jù)自己的經(jīng)驗(yàn)人工設(shè)定，而且聚類效果的好壞直接取決于設(shè)置參數(shù)的是否適用于自己的數(shù)據(jù)集，在不知數(shù)據(jù)規(guī)模和數(shù)據(jù)分布的境況下設(shè)置算法參數(shù)基本無依據(jù)可依。另外，DBSCAN算法本身只能處理小量數(shù)據(jù)，在大數(shù)據(jù)聚類上效果不佳。

現(xiàn)有技術(shù)中，有的學(xué)者對DBSCAN算法進(jìn)行了改進(jìn)，其主要的思路為：初始化時設(shè)置MinPts的值為常數(shù)4，然后算法運(yùn)行觀察EPS的變化在此過程中優(yōu)化MinPts的值。雖然給了很好的一般性參數(shù)設(shè)定值，但是整個過程還是需要人工的干預(yù)。有的學(xué)者嘗試引入了簇之間的鏈接信息來降低原始算法對參數(shù)的過分敏感性，但是也未成改變輸入?yún)?shù)的問題。或者提出了一種逐漸細(xì)化的方法來完成聚類操作，在每次完成聚類時，算法自動的調(diào)整參數(shù)，但是其初始化參數(shù)還是需要指定。其中在學(xué)術(shù)屆比較認(rèn)可的是使用K-dist圖的思想，首先對于每個樣本進(jìn)行K個最近距離排序，然后確定Eps的值，但是MinPts值的大小還需要指定。或者提出的I-DBSCAN算法分析數(shù)據(jù)的特征信息來完成對DBSCAN參數(shù)的優(yōu)化，但是在大型的數(shù)據(jù)集中并不適合。或者提出使用非參數(shù)核密度方法去估計數(shù)據(jù)樣本的分布特征從而確定參數(shù)值，但是其在運(yùn)行過程中核密度函數(shù)會出現(xiàn)很多的峰值，在取樣時導(dǎo)致參數(shù)設(shè)置不合適，聚類效果不理想。

發(fā)明內(nèi)容

針對現(xiàn)有DBSCAN聚類方法存在的問題，本發(fā)明提供了一種軌跡數(shù)據(jù)參數(shù)自適應(yīng)的聚類方法。

本發(fā)明采用以下的技術(shù)方案：

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

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

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

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

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

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

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