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

【關(guān)鍵詞】 閉合頻繁模式；數(shù)據(jù)挖掘；滑動(dòng)窗口；迭代；二進(jìn)制

一、文獻(xiàn)綜述

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

上述討論的方法大多數(shù)是基于FP-tree算法進(jìn)行改進(jìn)的，而基于FP-tree的算法主要是為交互式挖掘而設(shè)計(jì)的，但是基于FP-tree改進(jìn)的相關(guān)算法不一定適用于增量式挖掘。有沒(méi)有針對(duì)增量挖掘的算法？由此本文提出一種基于二進(jìn)制鏈表的結(jié)構(gòu)，稱為BitLink。鏈表中每個(gè)節(jié)點(diǎn)都包含三個(gè)部分?jǐn)?shù)據(jù)，第一部分是項(xiàng)集，第二部分是該項(xiàng)集的計(jì)數(shù)，第三部分是比特流。該算法通過(guò)不同項(xiàng)集之間比特流的與運(yùn)算來(lái)實(shí)現(xiàn)模式的增長(zhǎng)，在數(shù)據(jù)的更新與刪除階段只需要簡(jiǎn)單的對(duì)比特流的值進(jìn)行簡(jiǎn)單更新即可。

對(duì)比現(xiàn)有的方法本文主要有以下創(chuàng)新：1. 提出一種不同于FP-tree的新鏈表結(jié)構(gòu)，二進(jìn)制鏈表；2. 設(shè)計(jì)基于二進(jìn)制鏈表結(jié)構(gòu)的項(xiàng)比特流，比特流與運(yùn)算更接近計(jì)算機(jī)底層運(yùn)算；3. 對(duì)本文提出的BitLink算法進(jìn)行理論分析與實(shí)驗(yàn)證明該算法的可行性。

二、二進(jìn)制鏈表

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

（二）構(gòu)造二進(jìn)制鏈表

（三）數(shù)據(jù)挖掘與更新

選出k+Δ個(gè)項(xiàng)，其中Δ表示計(jì)數(shù)可能一樣的兩個(gè)項(xiàng)或者多個(gè)項(xiàng)，一共有Δ個(gè)項(xiàng)的計(jì)數(shù)跟其他項(xiàng)的計(jì)數(shù)一樣，這k+Δ個(gè)項(xiàng)一共有k個(gè)不同的計(jì)數(shù)值，因?yàn)槠渲杏行╉?xiàng)的計(jì)數(shù)是一樣的，按照支持度從大到小對(duì)這些項(xiàng)順序排列。

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

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

（四）性能分析

三、應(yīng)用實(shí)驗(yàn)

（一）實(shí)驗(yàn)方法

本節(jié)為BitLink算法進(jìn)行實(shí)驗(yàn)，硬件設(shè)備為Intel Core i7，內(nèi)存容量8GB，使用Python實(shí)現(xiàn)，對(duì)比算法為CFPA。使用數(shù)據(jù)集OnlineRetail、BMSWebView2進(jìn)行實(shí)驗(yàn)，其中OnlineRetail有541909條事務(wù)2603個(gè)項(xiàng)，BMSWebView2有77512條事務(wù)3340個(gè)項(xiàng)。

（二）實(shí)驗(yàn)結(jié)果

采用top-k作為指標(biāo)衡量算法的性能，圖1和圖2是在窗口大小固定為200條數(shù)據(jù)，top-k從50變化到250，在OnlineRetail和BMSWebView2這兩個(gè)數(shù)據(jù)集的時(shí)間變化，在窗口大小一樣的情況下，top-k越大，要挖掘的數(shù)據(jù)就越多，所以時(shí)間會(huì)隨著top-k的變大而變大?？傮w來(lái)說(shuō)，因?yàn)锽itLink算法比CFPA算法迭代的次數(shù)少，所以BitLink所用的整體時(shí)間要更少。

四、結(jié)語(yǔ)

關(guān)于關(guān)聯(lián)規(guī)則的數(shù)據(jù)挖掘已經(jīng)有很多成熟的算法，比如先驗(yàn)算法、FP-tree算法，先驗(yàn)算法需要多次掃描數(shù)據(jù)而使得挖掘效率降低，F(xiàn)P-tree算法需要維護(hù)一個(gè)復(fù)雜的樹(shù)結(jié)構(gòu)而增加了維護(hù)成本的開(kāi)銷。本文將數(shù)據(jù)以簡(jiǎn)單的存儲(chǔ)形式實(shí)現(xiàn)，數(shù)據(jù)的存儲(chǔ)形式接近計(jì)算機(jī)底層，所以提高的算法的效率。對(duì)于未來(lái)的高維大數(shù)據(jù)，可以對(duì)這些數(shù)據(jù)進(jìn)行降維，使得存儲(chǔ)實(shí)現(xiàn)接近計(jì)算機(jī)的一維結(jié)構(gòu)，從而提高算法的效率。

參考文獻(xiàn)：

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

［2］ 施一飛. 分布式多維數(shù)據(jù)流頻繁模式挖掘算法設(shè)計(jì)［J］. 吉林大學(xué)學(xué)報(bào)：信息科學(xué)版，2023，41（1）：174-179.

［3］ 羅旋，羅瑋，賀增良，等. 頻繁模式的水電信號(hào)異常檢測(cè)［J］. 現(xiàn)代電子技術(shù)，2023，46（10）：61-65.

［4］ 李潔. 基于解耦概要圖的圖數(shù)據(jù)頻繁模式挖掘算法［J］. 內(nèi)蒙古民族大學(xué)學(xué)報(bào)（自然科學(xué)版），2021，36（05）：391-395.