二進制的top-k閉合頻繁模式挖掘

【摘" 要】 自從引入頻繁模式的概念以來，閉合頻繁模式挖掘和增量頻繁模式挖掘就成為很多人研究的課題。目前增量模式挖掘有兩大類，一類是基于先驗算法Apriori，另一類是基于頻繁模式樹算法FP-tree，前者挖掘時間太長，后者維護FP-tree的開銷太大。為了降低數據維護和數據挖掘的時間成本，本文提出了一種基于鏈表的比特流結構，稱為Bitlink。Bitlink算法首先選擇大于或等于指定閾值的k+Δ個項，合并計數和比特流都相同的項，從合并項中選擇k個作為候選項并按降序排序，根據這k個候選進行迭代，最終生成top-k個閉合頻繁模式。實驗使用OnlineRetail和BMSWebView兩個數據集進行模擬，對比實驗為 closed frequent patterns by considering anti-monotonic constraint算法（CFPA），實驗結果表明Bitlink比CFPA快四分之一。

【關鍵詞】 閉合頻繁模式；數據挖掘；滑動窗口；迭代；二進制

一、文獻綜述

林志杰等人在先驗算法Apriori和頻繁模式樹算法FP-Growth的基礎上提出一種數據挖掘方法；Saihua Cai等人在基于反單調約束的條件下提出一種離群點檢測方法；Meng Han等人提出一種封閉高效用項集算法，施一飛根據神經網絡的特點建立對應的神經網絡模型，通過剪枝不頻繁項加快數據挖掘速率；Jerry Chun-Wei Lin等人提出一種大規模的信息融合體系結構；Da Yan等人提出一個基于前綴投影思想的通用框-PrefixFPM；Yu等人提出CooMine算法來挖掘閉合模式；Amagata和Hara等人提出CPGraph算法來挖掘共生模式，并通過裁剪一些不必要的模式，有效地獲取模式的計數并更新答案；羅旋等人設計異常檢測方法，并驗證方法的有效性；李潔通過構建頻繁項特征并對圖數據進行特征檢測，從中提取數值屬性并建立圖數據模型。

上述討論的方法大多數是基于FP-tree算法進行改進的，而基于FP-tree的算法主要是為交互式挖掘而設計的，但是基于FP-tree改進的相關算法不一定適用于增量式挖掘。有沒有針對增量挖掘的算法？由此本文提出一種基于二進制鏈表的結構，稱為BitLink。鏈表中每個節點都包含三個部分數據，第一部分是項集，第二部分是該項集的計數，第三部分是比特流。該算法通過不同項集之間比特流的與運算來實現模式的增長，在數據的更新與刪除階段只需要簡單的對比特流的值進行簡單更新即可。

對比現有的方法本文主要有以下創新：1. 提出一種不同于FP-tree的新鏈表結構，二進制鏈表；2. 設計基于二進制鏈表結構的項比特流，比特流與運算更接近計算機底層運算；3. 對本文提出的BitLink算法進行理論分析與實驗證明該算法的可行性。

二、二進制鏈表

（一）頻繁模式的基本概念

（二）構造二進制鏈表

（三）數據挖掘與更新

選出k+Δ個項，其中Δ表示計數可能一樣的兩個項或者多個項，一共有Δ個項的計數跟其他項的計數一樣，這k+Δ個項一共有k個不同的計數值，因為其中有些項的計數是一樣的，按照支持度從大到小對這些項順序排列。

合并同源項，對選出k+Δ個項中計數和項比特流都相同的項進行合并，同源項合并完成后我們選k個計數較大的候選項集，其中這k個候選項集可以包含同源項集。根據選出來k個候選項集按照支持度進行降序排列。自頂向下進行迭代，每一次迭代得出的項集的計數都要跟第k個候選項集的計數進行比較，假如迭代項集的計數比第k個候選項集的計數要大，那么就用迭代項集將第k項候選集代替掉，第k個候選集的閾值迭代項集代替。

隨著時間的流逝，部分的數據可能失去時效性，使得對這部分的研究沒有意義，而新的數據對于研究意義的重要性更加重大，因此刪除失去時效性的數據，獲取新到來的數據。對鏈表進行一次遍歷，找到鏈表中每個項對應的事務數據流，將已經失去時效性的事務ti對應的事務數據流部分刪除，假如被刪除的比特流包含1，那么將更新相關項的計數，假如被刪除的比特流為0，那么相關項的計數不需要更新，有多少個1被刪除，相關項的計數就要減多少。為新到的事務創建相關節點信息，項與項之間按照字典遞增排序，假如該事務中包含該項，則相應的比特值為1，否則為0，并且對比特流為1的項的相關計數進行累加，對比特流為0的項不做相關操作。整個算法在執行過程中先調用算法1，再調用算法2進行數據挖掘，后期不斷地調用算法3和算法2。

（四）性能分析

三、應用實驗

（一）實驗方法

本節為BitLink算法進行實驗，硬件設備為Intel Core i7，內存容量8GB，使用Python實現，對比算法為CFPA。使用數據集OnlineRetail、BMSWebView2進行實驗，其中OnlineRetail有541909條事務2603個項，BMSWebView2有77512條事務3340個項。

（二）實驗結果

采用top-k作為指標衡量算法的性能，圖1和圖2是在窗口大小固定為200條數據，top-k從50變化到250，在OnlineRetail和BMSWebView2這兩個數據集的時間變化，在窗口大小一樣的情況下，top-k越大，要挖掘的數據就越多，所以時間會隨著top-k的變大而變大。總體來說，因為BitLink算法比CFPA算法迭代的次數少，所以BitLink所用的整體時間要更少。

四、結語

關于關聯規則的數據挖掘已經有很多成熟的算法，比如先驗算法、FP-tree算法，先驗算法需要多次掃描數據而使得挖掘效率降低，FP-tree算法需要維護一個復雜的樹結構而增加了維護成本的開銷。本文將數據以簡單的存儲形式實現，數據的存儲形式接近計算機底層，所以提高的算法的效率。對于未來的高維大數據，可以對這些數據進行降維，使得存儲實現接近計算機的一維結構，從而提高算法的效率。

參考文獻：

［1］ 林志杰，彭珍連，曹步清，等. 一種面向高校學生體測數據的模式挖掘方法［J］. 信息與電腦，2023，35（04）：184-189.

［2］ 施一飛. 分布式多維數據流頻繁模式挖掘算法設計［J］. 吉林大學學報：信息科學版，2023，41（1）：174-179.

［3］ 羅旋，羅瑋，賀增良，等. 頻繁模式的水電信號異常檢測［J］. 現代電子技術，2023，46（10）：61-65.

［4］ 李潔. 基于解耦概要圖的圖數據頻繁模式挖掘算法［J］. 內蒙古民族大學學報（自然科學版），2021，36（05）：391-395.