摘要：在軌跡數據集有新增數據且最小支持度變更情況下，為了實現(xiàn)頻繁軌跡集能夠快速更 新以及解決軌跡數據庫占用大量存儲空間的問題，提出基于動態(tài)最小支持度的增量頻繁序列挖 掘算法。該算法能夠充分利用頻繁軌跡集信息，在有新增軌跡數據加入原始軌跡數據集且最小 支持度變更時，通過頻繁軌跡序列與頻繁 1 序列相連接生成候選序列，利用非頻繁軌跡后綴子 序列置信度來估計非頻繁軌跡支持度，實現(xiàn)動態(tài)更新頻繁項集，并且在挖掘頻繁軌跡后不再需 要保存原始軌跡數據。通過軌跡數據集的挖掘實驗，驗證了本文算法支持度估計的精度和算法 的有效性。

關鍵詞：頻繁軌跡；動態(tài)數據；最小支持度；PrefixSpan；內存開銷

中圖分類號：TP311.1

文獻標志碼：A

隨著智能化、信息化時代的來臨，數據庫中的軌 跡數據數量呈爆炸式增長，其中不僅有人們生產生 活留下的軌跡數據，也包含野生動物的遷徙路線、臺 風的移動軌跡等數據，挖掘軌跡數據中蘊含的信息 可以幫助人們更好地生活和進行生產活動[1]。軌跡 數據具有數據量大、空間范圍大、數據信息密度小等 特點，對軌跡數據的分析有多個研究方向，頻繁軌跡 挖掘是其中一種重要的方法，主要應用于挖掘軌跡 數據的頻繁模式和異常模式。

常 用 的 頻 繁 項 挖 掘 算 法 有 Apriori 算 法 [2]、 PrefixSpan 算法[3] 以及 FP-Growth 算法[4] 等，本文選 擇 PrefixSpan 算法進行頻繁軌跡挖掘。PrefixSpan 算 法通過遞歸構造頻繁前綴序列的投影數據庫來不斷 縮小搜索空間，因此與 Apriori 算法相比，該算法的時 間消耗大大降低。但是 PrefixSpan 算法在處理大規(guī) 模數據庫時，會生成大量重復的投影數據庫，大大影 響了算法的時間效率和存儲效率。目前已有不少學 者 提 出 相 應 改 進 措 施 ， 文 獻 [5] 提 出 AprioriAll[1]PrefixSpan 算法，利用已生成的序列模式來提高算法 效率。文獻 [6] 通過投影和局部搜索機制減少掃描 原始數據庫次數。

傳統(tǒng)的頻繁項集挖掘算法都是應用于靜態(tài)數據 集，即在數據集與最小支持度保持不變情況下挖掘 頻繁項集。面對如今爆炸式增長的數據量，靜態(tài)頻 繁項集挖掘算法已無法滿足人們的需求。在這種情 形下，動態(tài)頻繁項集挖掘算法應運而生，典型的動態(tài) 頻繁項集挖掘算法有 FUP 算法、IUA 算法及 IUAR 算法等[7]。FUP 算法[8] 用于處理最小支持度不變、有 增量數據庫情況下的頻繁項集更新問題。該算法在 增量數據庫中確定有希望和無希望的項集，從而減 少待搜索的候選項集個數和掃描原數據庫次數，但 仍需要頻繁掃描數據集且沒有解決原數據庫的存儲 空間占用問題。IUA 算法[9] 將新的頻繁項集分為 3 類，同時不考慮原頻繁項集對應的候選項集，以此 減少對數據庫的掃描次數，解決了最小支持度變更 情況下的頻繁項集更新問題。高峰等[10] 基于 IUA 算 法提出了 IUAR 算法，改進了 Apriori 算法的頻繁項 增長函數以及生成候選項集的方法，避免對已有項 集的重復掃描，解決數據庫增加且最小支持度減小 情況下的頻繁項集動態(tài)更新。針對有增量數據庫且最小支持度變更情況下的頻繁項集挖掘，研究者們 基于 FUP 算法和 IUAR 算法的思路提出了一系列改 進算法。文獻 [11] 提出 UP-IITree 算法，結合了倒排 索引技術和樹型結構，將數據庫中的記錄轉換成倒 排索引表，能夠不產生候選項集且高效計算出增量 更新后的所有頻繁項集。文獻 [12] 提出一種增量條 件模式樹，減少對原始數據庫的重復掃描次數。文 獻 [13] 針對 FUP 算法的不足提出基于倒排索引樹的 改進算法 IIBTree-FUP 算法，它通過基于 B+樹結構 實現(xiàn)的倒排索引樹結構存儲已有的項目集，并利用 牛頓插值公式估計新增后數據庫的最小支持度以此 減少對數據庫的頻繁掃描。本文充分利用頻繁項集 信息，針對原數據庫的存儲空間占用問題，提出利用 非頻繁序列的后綴子序列置信度估計其支持度，實 現(xiàn)當數據動態(tài)變化時頻繁項集的動態(tài)更新。

PrefixSpan 算法的基本過程是：第一次掃描數據 庫，根據最小支持度得到所有的頻繁 1 序列。再次掃 描序列數據庫，以每個 1 頻繁項為前綴，對序列數據 庫進行投影劃分，獲得相應的投影數據庫。然后對 投影數據庫進行掃描，得到其中所有的頻繁 1 項集。 將投影數據庫中的每個 1 頻繁項與對應的序列前綴 進行連接，可得到新的頻繁項集，即為頻繁 2 項集。 進一步將每一個新獲得的序列模式作為前綴，對投 影數據庫進行劃分，從中生成新的投影數據庫。重 復上述構建頻繁前綴投影數據庫以及挖掘投影數據 庫中頻繁 1 序列并與頻繁前綴連接的操作，直至挖掘 出序列數據庫中所有的頻繁序列模式。

2""" 基于動態(tài)最小支持度的增量頻繁序 列挖掘算法

傳統(tǒng)的頻繁項挖掘算法用于挖掘固定的數據庫 以及最小支持度保持不變情況下的頻繁項集，但在 如今大數據時代背景下，實際應用中往往面臨數據 庫新增數據的情況。同時，數據庫中序列數與最小 支持度往往相關聯(lián)，數據庫的變更可能導致原最小 支持度在更新后的數據庫上表現(xiàn)不佳，需要根據挖 掘結果調整最小支持度用于后續(xù)的頻繁軌跡挖掘， 因此本文考慮有新增數據添加到原數據庫中且最小 支持度發(fā)生變更的情況下的頻繁項集動態(tài)更新問題。

對于數據庫變更或最小支持度變更導致頻繁項 集過時的情況，最直接的更新方式是對更新后的數 據庫重新進行頻繁項集挖掘。但這種更新方式浪費 了之前得到的挖掘結果，算法的更新效率較低。本 文提出通過頻繁項集與頻繁 1 序列連接產生候選項 集，利用后綴子序列的置信度來估計候選序列支持 度，能夠在不掃描原數據庫情況下，實現(xiàn)頻繁項集動 態(tài)更新，稱為基于動態(tài)最小支持度的增量頻繁序列 挖 掘 算 法 （Dynamic" Minimum" Support" Incremental Updating PrefixSpan），簡稱 DMSIU-PrefixSpan 算法。

（3） 序 列 滿 足S 1 Traj（D） ′ ，S ? Traj（d） ′ ，通過 式 （4） 及 式 （5） 估 計 ， 結 合 sup（S ）D sup（S代 入 式（6） 計算序列 在數據庫 中的支持度。若支持 度大于 ，則將序列 及其支持度加入頻繁 序列集 。

3""" 實驗分析與比較

為了驗證 DMSIU-PrefixSpan 算法在頻繁軌跡挖 掘上的準確性和有效性，本文使用某高校實際采集 的學生軌跡數據集作為測試數據集。實驗部分首先 檢驗 PrefixSpan 算法在軌跡數據集上的有效性，然后 將數據集按時間窗劃分為原數據集和新增數據集， 分別挖掘原數據庫、新增數據庫以及全局數據庫的 頻繁軌跡集。通過前文的支持度估計算法，利用原 數據庫和新增數據庫的頻繁軌跡集得到全局數據庫 的頻繁軌跡集估計結果，比較挖掘結果與估計結果， 檢驗算法性能。最后將本文算法的運行時間與幾種 動態(tài)頻繁項集挖掘算法進行對比，包括 IUAR[10] 算 法 、UP-IITree （Updating based Inverted index Tree） 算 法[11] 以及 IIBTree-FUP （Improved FUP algorithm based on" inverted" index" B-tree） 算法[13]。本文算法全部在 Windows 10 的 64 位操作系統(tǒng)下通過 Python 語言編 程 ，硬件環(huán)境為 Intel（R） Core（TM） i5-1135 G7@2.40 GHz，16 GB 內存。

本文實驗所用的軌跡數據集是某高校真實學生 軌跡數據集，通過學生電子設備連接校園內無線網 絡接入點 （Access" Point" ，" AP） 獲得的 ，時間跨度為 2019 年 9 月 1 日至 2019 年 12 月 31 日共 4 個月，選 取 500 名軌跡記錄數大于 1000 的用戶。受到信號強 度、數據存儲方式等因素的影響，原始的時空軌跡數 據無法直接應用于頻繁軌跡挖掘，因此要先對時空 軌跡數據進行預處理。

3.1 軌跡數據集預處理

由于數據采集過程的特性，軌跡數據存在冗余 信息多、部分數據不完整、異常數據等問題。為了后 續(xù)更好利用此數據集完成頻繁軌跡的挖掘，需要對 原始學生軌跡數據進行預處理。軌跡數據預處理包 括以下幾個方面：

（1） 冗余數據清洗。學生在上網過程中大多處 于靜止狀態(tài)，例如在宿舍休息、娛樂，在教學樓上課、 自習等，因此采集到的軌跡數據有大量重復地點的 信息。根據實際需求篩選去除部分冗余軌跡點，且 保留原有軌跡的語義信息。

（2） 異常數據剔除。對于噪聲數據，例如由于無 線網絡接入設備距離太近，一個用戶同時被兩個 AP 點檢測連接，此時需要通過接收信號強度 （Received Signal Strength Indication， RSSI） 判斷出用戶所在正確 地點，剔除錯誤數據，保證同一時刻用戶只出現(xiàn)在一 個地點。

（3） 數據格式轉換。采集的原始數據不僅包含 上網的時間、連接的 AP 點，同樣包含用戶 MAC 地 址、RSSI 等信息，需要先提取出有效的數據維度并 且轉換成容易處理的格式。

（4） 劃分時間窗口。由于原始時空軌跡數據時 間跨度較長，每條軌跡序列中包含的項過多，為了提 高挖掘效率將軌跡按時間劃分。若劃分后的軌跡序 列過短，則會影響挖掘結果，使一些有效信息被隱 藏。綜合考慮下，劃分的時間窗口大小為 15 d，將每 條軌跡劃分為 8 個時間窗。

3.2 動態(tài)頻繁軌跡挖掘結果分析

3.2.1"" 頻繁軌跡挖掘結果 通過 PrefixSpan 算法，挖 掘學生軌跡數據集的頻繁軌跡。表 1 所示是記錄了 不同最小支持度情況下的頻繁軌跡挖掘結果。其中 min_sup為 最 小 支 持 度 ，time 為 算 法 運 行 時 間 ， 為挖掘得到的頻繁軌跡總數， 為頻繁軌跡序列的平均長度。

3.2.2"" 動態(tài)最小支持度的增量頻繁軌跡挖掘結果 為了驗證本文的置信度估計方法的準確性，將挖掘 結果與估計結果進行比較?？紤]到現(xiàn)實中數據庫的 更新往往不止一次且呈周期性，原數據庫中包含的 軌跡序列數逐漸增加，而每次新增數據庫中的軌跡 序列數基本保持不變，導致原數據庫的序列數與新 增數據庫的序列數比例也在不斷變化。因此本節(jié)通 過時間窗來劃分原數據庫與新增數據庫：第 次實驗 的原數據庫為前 個時間窗內軌跡數據，新增數據庫 為第 個時間窗內軌跡數據，模擬現(xiàn)實中原數據 庫不斷擴充的過程，具體劃分情況如表 2 所示。設定 原最小支持度為 0.6，隨著數據庫增加最小支持度逐漸減小。首先通過 PrefixSpan 算法，分別挖掘數據 庫 D 和 在最小支持度為 0.6 情況下的頻繁軌跡，以 及完整數據庫 在變更后的最小支持度下的頻 繁軌跡。對挖掘得到的頻繁軌跡同步估計，將估計 結果與挖掘結果比較 ，評價指標為平均相對誤差 （Mean Relative Error， MRE），計算公式如下所示。

3.3 運行時間分析

本 文 采 用 3 種 動 態(tài) 頻 繁 項 集 挖 掘 算 法 與 DMSIU-PrefixSpan 算法進行算法運行時間的比較。 圖 2 所示為在原數據庫 D 和新增數據庫 不同時間 跨度比下各算法的運行時間對比。由圖可得 ， DMSIU-PrefixSpan 算法的運行時間均最短。與改進 的動態(tài)頻繁項集挖掘算法 UP-IITree 以及 IIBTree[1]FUP 相比，DMSIU-PrefixSpan 算法在時間上也有明 顯的優(yōu)勢，表明本文改進后的算法運行效率更高。

3.4 實驗結果分析

軌跡數據集的動態(tài)頻繁項集挖掘實驗結果表 明：DMSIU-PrefixSpan 算法估計結果的 MRE 全部在 6% 以內，即使算法的 MRE 隨最小支持度的減小而 逐漸增大，考慮到實際應用中最小支持度并不會無 限制地降低，因此算法估計的 MRE 在可接受范圍 內。本文算法由于只需要對原數據庫和新增數據庫 各掃描一次來挖掘頻繁軌跡集，后續(xù)更新頻繁軌跡 集時不需要掃描數據庫，因此運行時間遠遠少于其 余 3 種動態(tài)頻繁項集挖掘算法。由于本文算法在后 續(xù)計算中只需要頻繁軌跡序列集中的信息，因此算 法所占內存空間的大小即為挖掘得到的頻繁軌跡序 列集的大小，而 IUAR 算法還需存儲原始軌跡數據， UP-IITree 算法以及 IIBTree-FUP 算法需要存儲生成 的倒排索引樹，因此本文算法所需內存空間最少。

4""" 總結與展望

基于軌跡數據庫數據量大以及動態(tài)更新的現(xiàn) 狀，動態(tài)頻繁項集挖掘算法應運而生。本文針對傳 統(tǒng)頻繁項集動態(tài)更新算法需要頻繁掃描數據庫問 題，首先通過頻繁軌跡序列與頻繁 1 序列相連接生成 候選序列，再利用后綴子序列的置信度估計候選序 列的支持度，并運用頻繁軌跡后綴子序列的置信度 估計非頻繁軌跡的支持度，以此實現(xiàn)頻繁軌跡集的 動態(tài)更新，并通過實驗驗證了 DMSIU-PrefixSpan 算 法的有效性和準確度。

參考文獻：

YU W H. Discovering frequent movement paths from taxi trajectory data using spatially embedded networks and asso[1]ciation rules[J]. IEEE Transactions on Intelligent Transpor[1]tation Systems， 2019， 20（3）： 855-866.

曾雷. 關聯(lián)規(guī)則挖掘中Apriori算法的研究[D]. 重慶： 重慶 交通大學， 2016.

KANG J S， BAEK J W， CHUNG K. PrefixSpan based pat[1]tern" mining" using" time" sliding" weight" from" streaming data[J]. IEEE Access， 2020， 8： 124833-124844.

范圣法， 張先梅， 虞慧群. 基于關聯(lián)規(guī)則與聚類分析的課 程評價技術[J]. 華東理工大學學報 （自然科學版）， 2022， 48（2）： 258-264.

王斌， 黃曉芳， 袁平. 基于PrefixSpan序列模式挖掘的改進 算法[J]. 西南科技大學學報， 2016， 31（4）： 68-72.

ZHANG" C" K，" DU" Z" L，" GAN" W" S， et al." TKUS：" Mining top-k high" utility" sequential" patterns[J]." Information"" Sci[1]ences， 2021， 570： 342-359.

張步忠， 江克勤， 張玉州. 增量關聯(lián)規(guī)則挖掘研究綜述[J]. 小型微型計算機系統(tǒng)， 2016， 37（1）： 18-23.

CHEUNG D W， HAN J W， NG V T， et al. Maintenance of discovered association" rules" in" large" databases：" An"" incre[1]mental updating" technique[C]//Proceedings" of" the" 12th" In[1]ternational Conference on Data Engineering. LA： New Or[1]leans， 1996： 106-114.

馮玉才， 馮劍琳. 關聯(lián)規(guī)則的增量式更新算法[J]. 軟件學 報， 1998（4）： 62-67.

高峰， 謝劍英. 發(fā)現(xiàn)關聯(lián)規(guī)則的增量式更新算法[J]. 計算 機工程， 2000（12）： 49-50，112.

徐春. 基于倒排索引的增量更新關聯(lián)挖掘算法的研究 [D]. 廣西桂林： 廣西師范學院， 2016.

THURACHON W， KREESURADEJ W. Incremental asso[1]ciation rule" mining" with" a" fast" incremental" updating"" fre[1]quent" pattern" growth" algorithm[J]. IEEE" Access，" 2021，" 9： 55726-55741.

朱櫻. 數據挖掘技術研究及其在地災系統(tǒng)中的應用[D]. 西安： 西安工業(yè)大學， 2019.

HAN J W， PEI J， YIN Y W， et al. Mining frequent patterns without candidate" generation：" A" frequent-pattern" tree"" ap[1]proach[J]. Data" Mining" and" Knowledge" Discovery，" 2004， 8（1）： 53-87.