[發明專利]一種基于改進PrefixSpan算法的交易數據頻繁序列模式挖掘方法

在審

• 申請號: 202110777271.8
• 申請日: 2021-07-09
• 公開（公告）號: CN113505156A
• 公開（公告）日: 2021-10-15
• 發明（設計）人: 何新;王子龍;陳琛
• 申請（專利權）人: 南京榮新智能科技有限公司
• 主分類號: G06F16/2458
• 分類號: G06F16/2458;G06F16/242;G06F16/2453;G06F16/215;G06F16/22;G06Q30/02
• 代理公司: 北京科億知識產權代理事務所(普通合伙) 11350
• 代理人: 李興林

本發明公開了一種基于改進PrefixSpan算法的交易數據頻繁序列模式挖掘方法，包括步驟：對商品交易數據進行預處理，得到商品交易數據集，并存入交易序列數據庫中；掃描交易序列數據庫，對每個單項進行計數，得到每個單項的序列支持度并降序排列，選出前μ項且滿足最小支持度的單項作為初始前綴；采取深度優先遍歷，對第一個初始前綴的位置進行計算，并保存在前綴位置信息表中，生成商品交易投影數據庫；再對其進行迭代，直至無法生成新的商品交易投影數據庫，保存每個商品交易投影數據庫生成的頻繁序列模式集合；從第二個初始前綴開始，重復上一步驟，直至所有初始前綴均計算完畢。本發明用于減少交易數據頻繁序列模式挖掘的時間/空間消耗，提高執行效率。

技術領域

本發明涉及交易數據挖掘技術領域，特別是涉及一種基于改進PrefixSpan算法的交易數據頻繁序列模式挖掘方法。

背景技術

大型連鎖超市的交易數據有一系列的用戶事務數據庫，每一條記錄包括用戶的ID，事務發生的時間和事務涉及的項目，如果能在其中挖掘涉及事務間關聯關系的模式，即用戶幾次購買行為間的聯系，可以采取更有針對性的營銷措施。

目前，在交易數據頻繁序列模式挖掘算法中，各專家、學者花費了大量的時間和精力提出了不少典型的方法，如GSP、SPADE、PrefixSpan算法等。其中，GSP算法減少了需要掃描候選序列的數量和多余無用模式的產生，但針對大規模序列數據庫會產生大量的候選序列模式，且需要對序列數據庫進行循環掃描；SPADE算法掃描數據庫次數降低僅為3次，但在原始數據巨大的情況下會產生大量垂直數據庫；PrefixSpan算法的優點是不用產生候選序列，相比于其它兩種算法，其內存消耗相對穩定，而且效率更高，但其可能會出現重復投影數據庫問題，從而導致對重復的投影數據庫進行挖掘劃分，造成一定的重復計算，增大了時間/空間消耗。因此，一種基于改進PrefixSpan算法的交易數據頻繁序列模式挖掘方法亟待研究。

發明內容

本發明的目的是提供一種基于改進PrefixSpan算法的交易數據頻繁序列模式挖掘方法，用于減少交易數據頻繁序列模式挖掘的時間/空間消耗，提高執行效率。

為實現上述目的，本發明提供了如下方案：

一種基于改進PrefixSpan算法的交易數據頻繁序列模式挖掘方法，包括以下步驟：

S1)對獲取的商品交易數據進行預處理，得到商品交易數據集，并存入交易序列數據庫D中；

S2)掃描交易序列數據庫D，對每個長度為1的單項進行計數，得到每個單項的序列支持度sup并降序排列，選出前μ項且滿足最小支持度min_sup的單項作為初始前綴；

S3)采取深度優先遍歷，對第一個初始前綴的位置進行計算，并保存在前綴位置信息表中，生成商品交易投影數據庫；再對其進行迭代，直至無法生成新的商品交易投影數據庫，保存每個商品交易投影數據庫生成的頻繁序列模式集合；

S4)從第二個初始前綴開始，重復步驟S3)，直至所有初始前綴均計算完畢；

其中，所述步驟S4)具體包括：

S401)生成第二個初始前綴的商品交易投影數據庫；如果該商品交易投影數據庫為空，則遞歸返回；

S402)掃描商品交易投影數據庫，對單項進行計數；如果所有單項的序列支持度sup都低于最小支持度min_sup，則遞歸返回；

S403)將滿足最小支持度min_sup的各個單項和當前的前綴進行合并，得到若干新的前綴，并計算新前綴的前綴位置；若前綴位置信息表存在與之前前綴位置相等的前綴，則直接返回前綴位置信息表中前綴所產生的頻繁序列模式集合，并返回步驟S3)；否則，前綴位置信息表保存新的前綴位置信息，并生成新的商品交易投影數據，返回步驟S401)。