齊東升，張紅梅

(桂林電子科技大學 廣西高校云計算與復雜系統(tǒng)重點實驗室，廣西 桂林 541004)

Agrawal等[1]在1994年提出了頻繁項集和關聯(lián)規(guī)則的概念，奠定了非容錯頻繁模式的理論基礎，此后的學者在其基礎上對非容錯頻繁項集的研究做了大量的研究，提出了大量非容錯頻繁項集挖掘算法，如FP-Growth算法[2]、DHC算法[3]等。然而，在很多工程研究領域中，由于數(shù)據(jù)往往存在噪聲，這些數(shù)據(jù)中的噪聲可能是由于測量誤差、缺失值以及某些反常情形等多種原因造成的，使用傳統(tǒng)頻繁項集挖掘算法得到的結果不能完全反映實際規(guī)律，并且在不考慮噪聲影響的情況下得到的頻繁項集的長度往往小于數(shù)據(jù)實際反映的頻繁項集[2-3]。除了應用在噪聲這一背景外，傳統(tǒng)的頻繁項集挖掘都是基于候選頻繁項集是否為事務的子集來統(tǒng)計支持度，但是這種方式容易忽略一些潛在的頻繁模式。例如，商店中共有5種水果，60%的消費者會購買所有水果中的任意4種，由于這類消費者購買水果也存在差異性，采用傳統(tǒng)統(tǒng)計支持度的方式無法得到這種頻繁模式(項集)。這種傳統(tǒng)頻繁項集的局限性可通過引入松弛條件并允許在可接受范圍內(nèi)出現(xiàn)錯配來解決，該思想最早是由Yang等[4]在2001年提出的，并給出了強(弱)容錯項集(strong/weak error-tolerant itemsets，簡稱ETI)等定義，用于挖掘?qū)嶋H數(shù)據(jù)集中合理的泛化知識。2007年Poernomo等[5]提出了容錯頻繁項集(fault-tolerant frequent itemsets，簡稱FTFIs)的概念；Liu等[6]在2014年提出了一種適用于比例容錯情形下的迭代算法。在ETI、FTFIs等相關概念中通過定義容錯度來體現(xiàn)松弛條件的引入，其本質(zhì)是候選項集與其支持事務之間的差異度。容錯度是一個在區(qū)間[0,1)的小數(shù)，當事務與候選項集相同項的個數(shù)要滿足與容錯度相關的松弛條件時，該事務才能被認為是支持該候選項集的。對最大容錯頻繁項集進行挖掘的問題后經(jīng)證明屬于NP-hard問題[7]。Lu等在2018年提出了容錯塊概念，將提取容錯頻繁項集的問題看作挖掘容錯塊的問題。其提出的算法是基于Brand and Bound算法對由所有項集構造的枚舉樹進行遍歷，根據(jù)利用整數(shù)規(guī)劃設計出的上邊界函數(shù)對枚舉樹上的每個節(jié)點進行估計，估計出該節(jié)點對應容錯塊面積，該算法記作BAB-UBF算法。由于該算法采取的是遍歷搜索的方式，適應不了大型事務數(shù)據(jù)集中容錯塊挖掘。針對事務數(shù)據(jù)庫中最大容錯塊掘的問題，提出了基于PSO并行化的最大容錯塊掘方法，無需構造枚舉樹，降低了算法的空間復雜度，并利用Spark框架提高了算法的計算效率，在含有較多項的事務集中有更好的表現(xiàn)，同時算法的效率不受容錯度的影響。

1 相關定義

I={i1,i2,…,in}是n個不同項組成的集合，D為事務數(shù)據(jù)庫，其中每個交易T是一個由項組成的集合，且T?I，每個交易T都有一個唯一的標識Tid。

二進制矩陣的行代表事務數(shù)據(jù)庫中的一個事務，列代表事務數(shù)據(jù)庫中的項，二進制矩陣的元素值：1代表項出現(xiàn)在對應的事務中，0代表項未出現(xiàn)在對應的事務中。表1是事務數(shù)據(jù)庫常見表示形式，是對應的二進制項集矩陣。該示例表示有5個項，分別為a、b、c、d、e，5個事務為T1～T5。該例中較大的區(qū)域如{a,b}對應的支持事務有{T1,T2,T3}，{c,d,e}對應的支持事務有{T4,T5}，以及其他的區(qū)域等等。區(qū)域的概念由Greerts等在2004年提出[8]。

表1 事務數(shù)據(jù)庫的二進制表示

定義1I是一個項集，D是事務數(shù)據(jù)庫，與I對應的區(qū)域定義為

tile(I)={(Tj,i)|i∈I,I?Tj}，

(1)

域的面積的定義為

area(I)=|I|×frequency(I)。

(2)

同樣以表1作為事務數(shù)據(jù)庫D，假設項集I為{d,e}，由于T3、T4和T5均包含項集I里的所有元素，項集I的區(qū)域即為項集I與事務T3、f(l)、T4和T5的共同的部分。由于該區(qū)域包含6個元素，該區(qū)域的面積為6。注意區(qū)域并不必須是由相鄰的元素組成，例如項集為{a,d}，支持它的事務為T1、T3和T4，它們共同的元素在事務數(shù)據(jù)庫中不相鄰，但是這種情況與前者是相同的。

在由二進制矩陣表示的事務數(shù)據(jù)庫中，區(qū)域的本質(zhì)是由行和列中均為1的相同部分組成的集合。在式(1)基礎上給出頻繁容錯模式的定義。

定義2容錯頻繁模式。δ為容錯度，其定義域為[0,1)，若事務ti包含容錯項集I中至少1-δ比例的元素，則可認為事務ti支持容錯項集I，可表示為

|ti∩I|≥(1-δ)|I|。

(3)

在表1中，假設δ為0.3，項集I為{b,c,d,e}，若事務包含該項集中的1～0.3比例的元素，則該事務即是容錯支持項集I的，在表1中可以找出符合該條件的事務有T1、T2、T3、T4、T5，但是在傳統(tǒng)頻繁項集計算支持度時只會計算T5。在定義中，δ是一個比例值，若一個事務包含目標項集的較多元素，則可以將該事務看作部分包含該項集。

定義3δ為容錯度，其定義域為[0,1)，I是一個項集，D為數(shù)據(jù)庫，ti為其中的一個事務，則項集I的容錯區(qū)域為

|Tj∩I|≥(1-δ)|I|}，

(4)

其對應的面積：當δ=0時為area(I)；當0<δ<1時，

(5)

也可表示為

(6)

假設δ為0.5，I為{a,b,c}，即當一個事務包含項集I中一半以上的項時就可認為該事務是容錯支持項集I的。結合示例1的數(shù)據(jù)集，可得出該數(shù)據(jù)集中的所有事務均是容錯支持項集I的。其容錯區(qū)域的面積為3+3+1+1+1=9，有最大區(qū)域面積的容錯項集為{a,b,c,d,e}，其面積大小為3+3+3+3+3=15。式(5)中的懲罰參數(shù)|ITj|表示的是元素項被項集I包含，但是不被事務Tj包含，懲罰因子為(1-δ)/δ。由式(6)可得出:在給定項集I的前提下，容錯區(qū)域的面積取決于項集I和事務相同的項元素的個數(shù)。

容錯塊是由在一定容錯度條件下支持某個項集的事務集中的有效元素組成的區(qū)域。由此可知，支持該項集的事務在某個固定的容錯度條件下支持該項集。故容錯塊的物理意義代表的不是單一的事務，而是滿足一定容錯條件的事務集合。

定理1最大容錯塊的挖掘是NP-hard問題。

證明由于最大區(qū)域的挖掘已經(jīng)證明是NP-hard問題[8]，而最大容錯塊是最大容錯區(qū)域中δ為0的特殊情況，最大容錯塊的挖掘也是NP-hard問題。

定義4稀疏矩陣。在矩陣中，若數(shù)值為0的元素遠多于非0元素，則稱該矩陣為稀疏矩陣。與之相反，若非0元素占大多數(shù)時，則稱為稠密矩陣。

稀疏矩陣具有如下特點：首先，稀疏矩陣其非零元素的個數(shù)遠遠小于0元素的個數(shù)，且這些非零元素的分布無規(guī)律；其次，稀疏因子是用于描述稀疏矩陣的非零元素的比例情況。當稀疏因子小于0.05時，可以認為該矩陣是稀疏矩陣。

2 算法描述

PSO-MFTFI算法將優(yōu)化的PSO算法[9]與Spark并行計算框架進行合理組合，在大型事務數(shù)據(jù)庫的最大容錯塊的挖掘上較整數(shù)線性規(guī)劃(ILP)類算法有更高的效率。PSO-MFTFI算法將PSO算法的種群中的每個粒子進行并行化計算，每個粒子都是一個潛在的最大容錯塊對應的項集。將每個粒子對應的容錯塊面積作為粒子的適應度，通過種群粒子的不斷尋優(yōu)，最終得到適應度最大的容錯塊。

2.1 數(shù)據(jù)預處理

BAB-UBF算法在計算容錯塊時未對數(shù)據(jù)進行預處理，采用的是對事務數(shù)據(jù)庫中所有項組成的項集進行遍歷，在大型事務數(shù)據(jù)庫和稀疏事務數(shù)據(jù)庫中算法的效率出現(xiàn)了較大的性能缺陷。采用傳統(tǒng)頻繁項集挖掘中用到的支持度的定義，在事務數(shù)據(jù)庫中對每個項的支持度進行計算，設定最小支持度sup(x)=N/M，其中N表示的是項x在事務數(shù)據(jù)庫出現(xiàn)的次數(shù)，M表示事務數(shù)據(jù)庫中事務的個數(shù)，將支持度小于該閾值的項從事務數(shù)據(jù)庫中刪除。預處理后的矩陣會小于原始矩陣，但通過設置項最小支持度將事務數(shù)據(jù)庫對應的二進制矩陣的稀疏性降低，該操作并不影響最大容錯塊提取的正確性。

2.2 PSO算法

假設在n維搜索空間中，有一個由m個粒子組成的種群S={X1,X2,…,Xm}，其中第i個粒子任意時刻的狀態(tài)由2個向量表示。第1個是位置向量Xi(t)=(xi1(t),xi2(t),…,xin(t)),i=1,2,…,m；第2個是速度向量Vi(t)=(vi1(t),vi2(t),…,vin(t)),i=1,2,…,m。

將Xi(t)代入一個求解問題的函數(shù)作為適應度公式，可以計算出對應的適應度，其中位置向量對應的是n元目標函數(shù)在t時刻的決策變量組，Vi(t)是t時刻粒子速度向量，是對應決策變量的變化向量。

第i個粒子迄今為止搜索到的最優(yōu)位置被稱為個體極值，記為pbest=(pi1,pi2,…,pin),i=1,2,…,m.整個粒子群迄今為止搜索到的最優(yōu)位置被稱為全局極值，記為gbest=(pg1,pg2,…,pgn)，g=1,2,…,m。在找到以上2種最優(yōu)值后，粒子根據(jù)式(11)和式(12)對自身當前速度和位置進行更新。

Vij(t+1)=ωVij(t)+c1r1(gbestij(t)-Xij(t))+

c2r2(pbestij(t)-Xij(t))，

(7)

Xij(t+1)=Xij(t)+Vij(t+1)。

(8)

其中：ω為慣性權重；c1、c2為加速常數(shù)；r1、r2為常量。式(7)中，第1部分為粒子先前行為的慣性，第2部分為“社會”部分，表示粒子間的信息共享與相互合作，第3部分為“認知”部分，表示粒子本身的思考。

2.3 Spark

Spark是一個通用的并行計算框架，由加州伯克利大學(UCBerkeley)的AMP實驗室在2009年開發(fā)，是基于map reduce算法模式實現(xiàn)的分布式計算框架，具有Hadoop MapReduce所具有的優(yōu)點，同時也克服了Hadoop MapReduce中的諸多缺陷。Spark因其實現(xiàn)了基于內(nèi)存的方式存儲數(shù)據(jù)，具備了快速迭代數(shù)據(jù)的能力，同時可用RDD(resilient distributed datasets)技術實現(xiàn)存儲的持久化和高容錯性等優(yōu)勢，使其更適于處理大數(shù)據(jù)集的迭代式運算[10]。Spark中的RDD可看作各種數(shù)據(jù)計算模型的同一抽象，Spark的計算過程主要是RDD的迭代計算過程。RDD的迭代計算類似于管道，因此在設計Spark應用程序時應著重考慮算法中執(zhí)行步驟與RDD轉換動作的對應。RDD的計算模型如圖1所示。

圖1 RDD計算模型

從圖1可看出，數(shù)據(jù)經(jīng)過抽象轉換為對應的RDD后，可同時并行地進行計算，因此非常適合數(shù)據(jù)較大的計算模型。在考慮Spark框架與粒子群算法的融合過程時，粒子群算法種群中的粒子在每次迭代過程中，在相同的搜索范圍內(nèi)對同一個適應度函數(shù)進行計算，粒子之間在同一代游走過程中不相互影響，因此可將種群粒子設計為RDD，進而使種群粒子能夠進行并行化計算適應度值，從而提高算法的運行效率。

2.4 PSO-MFTFI算法思想

BAB-UBF算法在項種類較少情況下，挖掘效率很高，但當項的種類增多時，該算法的效率會嚴重降低。另外，對每個容錯塊最大面積上限進行估計來確定最大容錯塊，這種依靠定義上限函數(shù)確定面積大小的方法,無法準確計算出每個容錯塊確切的面積，易出現(xiàn)誤判。針對以上2種情形，提出以下應對措施：

1)采用并行化粒子群算法，提高算法的搜索效率。為了體現(xiàn)由于數(shù)據(jù)庫大小不同而出現(xiàn)搜索效率的不同，終止條件采用的是判斷粒子群中的粒子是否趨于收斂。若粒子群中的當前全局最優(yōu)解在某代以后，連續(xù)n代位置不發(fā)生改變，則該粒子群趨于收斂，若收斂則終止迭代，否則繼續(xù)迭代。由于PSO算法中粒子容易陷入局部最優(yōu)，會出現(xiàn)算法后期收斂速度較慢，精度也不高的現(xiàn)象。在粒子群中粒子速度更新公式中加入了高斯擾動項。粒子速度更新公式為

Vij(t+1)=ωVij(t)+c1r1(gbestij(t)-Xij(t))+

c2r2(pbestij(t)+r3gaussij(t)-

Xij(t))。

(9)

式(9)中加入了r3gauss(tij)項，即為高斯擾動項，r3為常量。需要注意的是在初始化粒子群時，每個粒子初始位置向量是一個長度與矩陣列數(shù)相同的二進制數(shù)組。

2)制定準確的適應度函數(shù)，通過比較計算出的每個容錯塊實際面積來判斷最大容錯塊的位置。由式(4)容錯塊的定義可知，計算候選項集對應容錯塊的面積可分為2個步驟：

1)在給定候選項集的條件下，需要先在二進制事務集中找出該項集的支持事務。由定義可知，候選項集與事務的交集的元素個數(shù)需要大于候選項集元素個數(shù)的δ倍。

2)在找出候選項集的所有支持事務后，同時也找到候選項集與每個支持事務的交集，統(tǒng)計這些集合的元素個數(shù)也即候選項集對應容錯塊的面積。映射到PSO算法中，每個粒子代表一個候選項集。

具體算法步驟如下：

1)給定最小支持度Supmin，取值范圍(0,1)，事務數(shù)據(jù)庫轉換為對應的二進制矩陣。

2)判斷轉換后二進制矩陣是否為稀疏矩陣，若矩陣不是稀疏矩陣，將該矩陣上傳至hdfs，并執(zhí)行后面的步驟，否則，刪除掉矩陣中支持度小于Supmin的項，將得到的矩陣上傳至hdfs。

3)初始化離散粒子群并設計粒子群算法的相關參數(shù)及計數(shù)器Same。粒子群規(guī)模根據(jù)矩陣的規(guī)?？蛇m當變化，將初始化后粒子群中的粒子并行化，即將種群轉換Spark框架中的彈性分布式數(shù)據(jù)集(RDD)。在RDD.map()中調(diào)用步驟4設計出的適應度函數(shù)，可實現(xiàn)種群中的粒子并行計算各自的適應值。

4)設計粒子群適應度函數(shù)，得到每個粒子在當前位置的適應度。

5)RDD執(zhí)行Action動作，得到種群中所有粒子當前的適應值，通過比較得到種群中所有粒子當前局部最優(yōu)值。

6)收集種群中所有粒子的局部最優(yōu)值，將其中最大值與當前全局最優(yōu)值進行比較，若大于全局最優(yōu)值，則將其替換為全局最優(yōu)值，并進行廣播全局最優(yōu)值以及計數(shù)器Same置0，跳轉至步驟5，否則，保持全局最優(yōu)值不變，并將計數(shù)器Same加1。

7)由計數(shù)器判斷算法是否滿足粒子群算法終止策略，若滿足則輸出當前全局最優(yōu)粒子位置及其適應度值，否則將當前種群轉化為新的RDD，在RDD.map()調(diào)用適應度函數(shù)，跳轉至步驟5。

算法流程如圖2所示。

圖2 算法流程圖

3 實驗結果與分析

PSO-MFTFI算法采用Python語言實現(xiàn)，實驗平臺：ThinkServer TD350 Tower，操作系統(tǒng)為Windows Server2016 Datacenter 64位，CPU為Intel(R) Xeon(R) E5-2620 v4八核 @ 2.10 GHz，內(nèi)存32 GiB。虛擬機環(huán)境是：Ubuntu16.04，內(nèi)存4 GiB，Spark版本為2.3.1，節(jié)點數(shù)2。實驗所用的數(shù)據(jù)集為chess、mushroom、fire2、BMS-Webview-1、T10I4D100 K與T40I10D100 K標準數(shù)據(jù)集(下載自http://fimi.ua.ac.be/data/)。其中，chess數(shù)據(jù)集事務數(shù)為3 196，每個事務包含75個項，稀疏因子為0.493；mushroom事務數(shù)為8124，每個事務包含119個項，稀疏因子為0.193；fire2事務數(shù)為560，每個事務有325個項，稀疏因子為0.190；BMS-Webview-1事務數(shù)為59 602，每個事務有497個項，稀疏因子為0.005；T10I4D100 K與T40I10D100 K事務數(shù)為100 000，每個事務由999個項，前者稀疏因子0.010，后者為0.040?？梢钥闯觯篶hess、mushroom和fire2為稠密矩陣，BMS-Webview-1、T10I4D100 K和T40I10D100 K為稀疏矩陣。

實驗參數(shù)：PSO算法中種群的大小根據(jù)數(shù)據(jù)集的大小可以適當變化，上限為200，c1、c2均為0.5，r1、r2、r3為2，終止迭代條件中n為5，即全局最優(yōu)解有連續(xù)5代未發(fā)生變化即為滿足終止條件，為了保證實驗結果的正確性，每個數(shù)據(jù)集在相同條件下均運行5次并取其均值。實驗主要針對PSO-MFTFI算法與BAB-UBF算法在計算性能方面做出比較。

圖3是對數(shù)據(jù)集Chess進行最大容錯塊挖掘時隨容錯度變化的運行時間比較。從實驗數(shù)據(jù)對比可知，PSO-MFTFI算法在不同容錯度條件下均優(yōu)于BAB-UBF算法，且PSO-MFTFI算法運行時間幾乎不受容錯度影響，而BAB-UBF算法受容錯度影響較大。其原因在于PSO-MFTFI算法在數(shù)據(jù)集轉換為二進制矩陣后，由于同一個數(shù)據(jù)集其數(shù)據(jù)“集中”位置是確定的，不同的適應度值影響的是項集支持事務數(shù)量的變化，因此粒子群算法在參數(shù)固定的情況下，其搜索效率也是固定的，從而其運行時間基本不變，并與容錯度無關。

圖3 Chess數(shù)據(jù)集的挖掘時間

圖4 容錯度為0.05不同數(shù)據(jù)集的測驗

圖4(a)為這2種算法隨著數(shù)據(jù)庫中項的個數(shù)變化的運行時間的比較，圖4(b)為這2種算法隨著數(shù)據(jù)庫中事務個數(shù)變化的運行時間的比較。以上2組實驗結果是在容錯度為0.05的條件下，從給出的5類數(shù)據(jù)集中實驗得出的結果。從實驗數(shù)據(jù)可知，當事務數(shù)據(jù)庫較小時，2種算法的效率差別不大，當數(shù)據(jù)庫較大時，PSO-MFTFI算法的效率要明顯高于BAB-UBF算法，是因為PSO-MFTFI采用了并行計算模式，在數(shù)據(jù)量逐漸增加時，并行計算模式性能優(yōu)勢更加明顯。

4 結束語

提出了一種基于并行PSO的最大容錯塊挖掘算法，能快速挖掘大型事務數(shù)據(jù)庫中的最大容錯塊。由于容錯項集的支持度不具有單調(diào)性的特點，相較于其他頻繁模式挖掘要困難。為了解決這個問題，先將事務數(shù)據(jù)庫用二進制向量矩陣表示，將問題轉換為矩陣中容錯塊挖掘，并提出了基于并行PSO的最大容錯塊挖掘算法，為容錯頻繁項集奠定了基礎。該算法包括數(shù)據(jù)預處理，適應度函數(shù)構造，PSO算法優(yōu)化與并行化。實驗結果表明，PSO-MFTFI效率高于BAB-UBF算法，對于同一個事務數(shù)據(jù)庫算法的效率不受容錯度的影響，對于稀疏型事務數(shù)據(jù)庫的解決要優(yōu)于BAB-UBF算法。但是仍有一些問題未解決，如在存在多個相同最大容錯塊時只能找出其中一個。只是對最大容錯塊的挖掘提出了解決方法，接下來還需在此基礎上對容錯頻繁項集的挖掘做進一步的探究。