[發明專利]一種基于垂直分解的并行頻繁閉序列挖掘方法

有效

• 申請號: 201611091669.1
• 申請日: 2016-12-01
• 公開（公告）號: CN106599122B
• 公開（公告）日: 2019-12-31
• 發明（設計）人: 趙宇海;印瑩;王國仁;李晨光;畢天馳
• 申請（專利權）人: 東北大學
• 主分類號: G06F16/2458
• 分類號: G06F16/2458
• 代理公司: 21109 沈陽東大知識產權代理有限公司
• 代理人: 梁焱

1.一種基于垂直分解的并行頻繁閉序列挖掘方法，其特征在于，包括以下步驟：

步驟1、對原始數據庫掃描，將數據按行進行水平分片處理，并分別發送至不同的處理器中；

步驟2、對每個處理器中的數據進行垂直分解；具體為：

在每個處理器上，并行執行以下操作：

執行一條數據與數據集中的所有數據進行兩兩相交，獲得任意兩條數據之間的公共子序列，即候選模式集；

步驟3、將獲得的所有公共子序列進行合并和去重操作，得到挖掘前的候選模式集；

步驟4、將挖掘前的候選模式集中的序列轉變成圖的存儲結構，圖中每個結點代表一個序列；

步驟5、采用基于獨立支配集約減算法對圖存儲結構中的序列進行約減，將所有處理器中保存的集合進行合并；

步驟6、采用基于閾值約減算法在合并后的集合進行約減操作，選取最具代表性的K個模式，即TopK，實現頻繁模式的壓縮；

步驟7、挖掘約減后序列中的頻繁閉序列，具體步驟如下：

步驟7-1、將步驟6獲得的所有序列分配到每臺處理器中；

步驟7-2、在每臺處理器中，枚舉固定長度的前綴序列；

具體為：設置序列的前綴固定長度范圍，所述的范圍為：1～最長序列長度值，且固定長度為整數；在設置的長度范圍內依次取前綴固定長度值，由第一條序列至最后一條序列，由左向右依次枚舉，獲得所有固定長度所對應的前綴序列；

步驟7-3、判斷所獲得的前綴序列是否包含在處理器的數據集中，若是，則將該前綴序列放入至自身投影數據庫中；否則執行下一條前綴序列的判斷；

步驟7-4、將所有處理器中相同前綴序列所對應的投影數據庫進行合并，存儲于同一個處理器中；

步驟7-5、依次判斷每個前綴序列是否為頻繁序列，若是，則執行步驟7-6，否則，削減該前綴序列，并執行步驟7-7；

步驟7-6、通過回插檢測和向后擴展檢測，判斷該前綴序列是否為頻繁閉序列，若是，則保留此頻繁閉序列，否則，削減該前綴序列；

步驟7-7、判斷該序列是否能成片削減，若是，則執行成片削減，并返回執行步驟7-5，否則，執行步驟7-8；

步驟7-8、獲得全部的頻繁閉序列。

2.根據權利要求1所述的基于垂直分解的并行頻繁閉序列挖掘方法，其特征在于，步驟4將挖掘前的候選模式集中的序列轉變成圖的存儲結構，圖中每個結點代表一個序列； 具體步驟如下：

步驟4-1、對合并去重后的序列數據進行兩兩求相似度；

步驟4-2、判斷所得相似度是否大于設定值，若是，則這兩個序列存在關聯，即在該算法中，這兩個序列所對應的兩個頂點之間存在一條邊，否則，則這兩個序列無關聯；

步驟4-3、將存在關聯的頂點之間進行連接，獲得描述序列之間關聯的頂點結構圖。

3.根據權利要求1所述的基于垂直分解的并行頻繁閉序列挖掘方法，其特征在于，步驟5所述的采用基于獨立支配集約減算法對圖存儲結構中的序列進行約減，將所有處理器中保存的集合進行合并； 具體如下：

步驟5-1、任意取一頂點，并將該頂點加入至一集合中，在頂點結構圖中將該頂點與其邊刪除；

步驟5-2、查詢與該頂點之間沒有邊但度最大的頂點，并返回執行步驟5-1，直至所找到的頂點數目達到設定值；

步驟5-3、將所有處理器中保存的集合進行合并。

4.根據權利要求1所述的基于垂直分解的并行頻繁閉序列挖掘方法，其特征在于，步驟6所述的采用基于閾值約減算法在合并后的集合中進行約減操作，選取最具代表性的K個模式，即TopK，實現頻繁模式的壓縮； 具體步驟如下：

步驟6-1、任選一條序列加入結果集合中；

步驟6-2、對于每條待插入的序列，計算該序列與結果集合中所有序列的相似度，若該序列與集合中已插入的任意一條序列的相似度大于設定的閾值，則不插入，否則插入。