Apriori算法的改進及實例

劉建花

摘要：本文對Aprior算法簡介進行闡述，對這種算法進行改進，并以案例驗證改進的合理性。

[關鍵詞]Aprior 算法 改進實例

1Apriori算法概況

1.1Apriori算法簡介

Apriori算法是一種數據挖據的經典算法，此算法具有關聯規則模型。在1994年，由R.Agrawal等人通過研究AIS算法，在這種算法的基礎上提出的一種改進算法，這種算法是以一種挖掘數據問題為主要內容。在關聯規則問題上，這種算法的影響力非常大。

Apriori算法隸屬于寬度優先算法，即在關聯規則中應用寬度優先。其核心就是對數據庫進行掃描，由此產生出候選集，每一次掃描的時間只需要考慮同一個長度的候選集。同時還要逐級監測這個過程的頻繁項集。在多次掃描結束后，會生成比較多頻繁項目集。

1.2Apriori算法概念

對某個事件A與B：

（1）支持度：幾個事件關聯出現的概率。P（A∩B），在同一時間發生A事件與B事件的概率。

（2）置信度：事件的條件概率。

P（B|A），如果事件A已經發生了，同時發生B的概率，可以為P（AB）P（A）。

比如：對購物車的分析：其中有貨物為泳鏡和泳衣。

[假如支持度為1%;而置信度為60%支持度1%：表示同時購買泳鏡與泳衣只有2%。

置信度60%：表示客戶購買泳衣的，能夠購買泳鏡占據60%。

Apriori算法構思和操作都相對比較簡單，易于實現。這種算法采用了逐層搜索迭代法。算法目的是找到最大的頻繁項集，使用“K-1項集”來搜集“K項集”。

首先，從中尋找出數據庫頻繁的集合，此處為“1項集"，采用L作為集合標志位。通過L1，就能夠從中搜尋出頻繁項，即為“2項集"的L2，通過相同的方法得出L3，直到無法尋找出“K項集"。在整個實施運行過程中，每次迭代找出一個Lr，都需要重新掃描一次數據庫。

在Apriori算法中，最重要的是連接與剪枝;連接步即為自動連接（將LK與LK連接起來），連接規則就能夠確保每個項前K-2為相同項。按照這個步驟順向連接，其中剪枝就是從頻繁項集中產生所有的非空子集，不讓這些子集參與其中。如果非空子集成為非頻繁項，一定會讓候選集成為非頻繁，這樣就可以把它從Cr中刪除掉，產生出Lk。簡而言之，對頻繁項集計算過程進行歸納，其步驟為：掃描，計數，比較，出現頻繁項集，連接與剪枝，然后生成為候選項集。

雖然Apriori算法極大提高了計算優勢，但是從計算過程方面來看，也顯示出一些缺點，每次尋找出一個頻繁項集，必然需要對整個原始數據庫進行一次完整掃描;如果數據庫中的數據量非常巨大，那么在運行過程中必定會產生出非常龐大的候選項集。當數據結構比較簡單時，可通過Apriori算法對運算進行執行，但是對于數據比較大的時候，Apriori算法就比較復雜，而且運行次數會很多。例如頻繁集{X1，X2，X3，....X500}的長度為500，必然會產生出10000個候選項集。因此，要想真正顯示出Apriori算法的優勢，就要先對Apriori算法進行改進。

2Apriori算法的改進

隨著大數據不斷深入發展，Apriori算法暴露的缺陷非常明顯。在大數據時代，所有的數據幾乎都成為海量，都以PB為基準，自然數據信息比較龐大，如果還是采用Apriori算法，復雜性可想而知。因此按照Apriori算法具有的基本特征，就應該對其算法進行改進。總體而言，其改進主要從兩個方面進行：

（1）對自連接與剪枝步驟上，應該采用更為優越的策略。

（2）對數據庫自身進行簡化，目的是降低Apriori算法復雜度。

本文對Apriori算法改進主要從數據庫中著手，Apriori算法每執行一遍就要掃描一次數據庫，事實上可以對這個過程進行優化，在計算CK支持度過程中，應該將CK中所包含各種事物均標記出來，掃描時不用再考慮標記事物，這樣優化后，會產生實際候選集的支持度中各種數據庫必須要比真實數據庫小，隨K值增大，差值自然隨著增大，可有效降低掃描的時間，降低計算速度，提高效率。對Apriori算法進行改進后，步驟如下：

（1）從其中選擇最小的支持度，掃描原始數據庫，由此計算得出各個1項集度，從而得出1-項集L1。

（2）連接剪枝（此項步驟不變）

（3）對Ck中未標記元素進行標記，將已經標志的元素刪除掉，由此可獲取出新數據庫DK，然后對DK進行重新掃描，計算出CK-1中各元素支持度。

（4）將CK進行搜索，要刪除掉其中無法滿足的最小項集，從而形成一個新項集LK;

采用②-④，一直到無法產生出新的頻繁項集時，就終止此項操作。采用實例數據進行對比。

當上面流程來看，篩選C3時，數據庫經過簡化后就變成D1，而商品從10項減為9項，接下來經過執行后，數據庫D2減少成7項，在這個過程中能夠有效減少掃描所需時間。采用這種方法，對于數據量較大時非常節約時間，由此可見這種改進，其操作性比較強，但是雖然算法改進了，又會產生出一些新數據庫，新產生的數據庫需要占用時間和資源，因此改進算法仍需要不斷提高。

3Apriori算法改進后案例分析

隨著計算機網絡快速發展，電子商務的地位越來越重要，對于各種繁雜的商品，在實際應用中電商平臺要如何給客戶推薦，如何滿足客戶所需，如何吸引更多的客戶，這些都是投資者、經營者需要考慮的內容。

在電商平臺應用Apriori改進算法;平臺必須要依據用戶的消費習慣，將相關商品設置成關聯度，才能為用戶進行推薦，才能幫助客戶在整個購物過程中減少對購買物品的搜索時間，使購物變得高效來吸引客戶。

本文通俗易懂的介紹了Apriori算法，之后對經典Apriori算法進行了改進，而且運用改進算法對電商平臺進行運用，有效降低了客戶選擇所需商品花費的時間，達到增加經濟效益的目的。

參考文獻

[1]劉尚輝，王露.Apriori關聯規則在甲狀腺結節病案分析中的應用[J].中國衛生統計，2018（02）.

[2]范明等譯.Pang-NingTan，MichealeSteinbach，VipinKumar.數據挖掘導論[M].人民郵電出版社，2011.

[3]屈展，陳雷。一種改進的Apriori算法在電子商務中的應用[J].西安石油大學學報：自然科學版，2012（01）.