關聯規則Apriori挖掘算法的優化研究

張 彤

西安財經學院長安校區

關聯規則Apriori挖掘算法的優化研究

張 彤

西安財經學院長安校區

21世紀是海量數據的數字化時代，人們也開始習慣利用數據來分析、處理和解決問題，且數據挖掘算法日益被廣泛應用。其中，數據挖掘的研究中，各個領域活動跨度最積極的就是關聯規則Apriori挖掘算法。文章針對其兩大瓶頸之一展開研究，即研究可能形成數量較多的候選項集。在探索優化方法的同時，根據頻繁項集的性質，在原有算法基礎上得到一個候選項目集數量最小化的Apriori優化算法，最后再進行實證的應用。

關聯規則 頻繁項集 Apriori算法 運算效率 優化

一、緒論

自上世紀80年代以來，大型數據庫的普及和應用隨著科學信息技術的飛速發展應運而生，各行業、各單位甚至各國都累積了以一定的形式存儲的一定規模或海量的數據信息。面對數據分析的需求，“數據挖掘”應運而生，而主要的是關聯規則挖掘算法。關聯規則挖掘方法一開始的研究動機是由購物籃分析問題提出的，其最早是由Agrawal等人在1993年提出。次年，他們建立了項目集格空間理論，提出了著名的Apriori算法。隨著應用的深入研究，該算法存在兩個比較嚴重的問題：掃描事務數據庫的次數頻現、可能形成數量較多的候選項集。

針對Apriori算法會產生大量候選項集的問題，Park等人（1995）提出了一種依據散列技術產生頻繁項集的算法。但其中產生候選項集所花費的時間和精力是無法度量的。所以才提出了一種基于劃分的方法。與此同時，該算法會明顯的使掃描事務數據庫的次數變多，事物壓縮的方法也就隨之被提出。

綜上所述，許多算法主要注重于挖掘質量的提高，忽略了挖掘效率，因此，文章主要針對挖掘效率的提高做進一步的研究。

因此，就頻繁項集的“如果一個頻繁項目集是數據集的項目集，那么這個數據集中的所有（k-1）項目子集也一定是頻繁（k-1）-項目集”的性質，提出一種優化后的算法，取名稱作：候選項目集數量最小化的Apriori優化算法。這種方法是在Apriori算法的根基上，進一步縮減候選項集中候選項的數量，研究出優化的算法，并在R語言中進行驗證，進行比較優化前后兩者的運行算法的時間，以此來進行對比，并總結出文章的主要結論。

二、關聯規則Apriori算法的分析

（一）核心算法分析

Apriori算法主要有以下兩個步驟：（1）通過數據庫中每一項的累計結果，找出并羅列滿足minsupport（最小支持度）的項，形成頻繁1-項集，記作L1；（2）利用上一步形成的L1來形成頻繁2-項集，記為L2，利用L2再找到L3，以此類推，直到找出所有符合搜索條件的頻繁k-項集為止。

（二）算法的優缺點

Apriori作為頻繁項集產生算法，在關聯規則的數據挖掘中扮演著很重要的角色。但它也有利弊的兩面。

對于核心思想是通過候選集生成和剪枝檢測兩個階段來挖掘頻繁項集的Apriori算法，在移動通信領域以及一些高等學校教育的管理和整治中，可以有效地輔助各個領域有針對性的進行交流和督查工作，并提出一些有建設性的意見。但隨著經濟、科技的飛速發展，它的應用隨之深入，它的缺點也顯而易見，主要包括：在產生頻繁項集前會頻繁的掃描數據庫和在產生最終的頻繁項集前可能形成數量較多的候選項集。因此，文章針對Apriori算法的第二個主要缺陷，進行優化研究和分析。

三、關聯規則Apriori算法的優化設計

根據關聯規則的基本性質，研究問題一般可以劃分為兩個層次：（1）發掘頻繁項目集。實際上，有需求的用戶在找到所有的頻繁項集之前，都要通過一項檢測，即：滿足支持度不小于minsupport，這樣才能更加準確的生成所需要的、可能有包含關系的項目子集。（2）關聯規則的產生。在每個最大頻繁項目集中通過置信度的指定檢驗，我們可以找到問題所真正必須的關聯規則。一般情況下，我們都認定置信度不小于minconfidence的關聯規則。

在上述兩個層面的闡述中，第二層次較首層次來說相對比較簡單、易懂，所以近幾年來，研究的重中之重必然就落到了首層面的問題上。

（一）優化的Apriori算法

在傳統的Apriori算法中，用規定的支持度讓Ck-1進行比對，那些不小于minsupport的項集被保留，其余的項集被刪除，由此生成Lk-1，并進一步結合Lk-1與Lk-1生成Ck。而提出的新的改進方法，即進一步減少候選項集的候選項的數量，其主要思想是：為了有效的減少參加結合的k-1的項目集的數量，即在Lk-1生成Ck之前，先對Lk-1的項目集進行比對和刪減的處理，由此可以減少最終的Ck中結果候選項的數量。

（二）優化后的算法的設計

1.算法的描述。根據上述的一系列說明，優化后的算法可以展示如下：（1）在掃描數據庫D產生Lk-1的過程期間，計算Lk-1中所有項出現的頻數；（2）把Lk-1中出現頻數小于（k-1）的項集完整剔除。

2.算法的優良性比對。在論述了Apriori算法、以及它優化后的算法之后，運用R語言進行算法程序的運行，并利用計算算法程序運行時間行優化前后兩者時間上的比較，得到了如下表3-1所示的比較結果。

表3-1 優化前后Apriori算法程序運行時間對比表

下面先對表中的一些專業術語進行解釋：

“用戶”是消耗在算法程序（非操作系統部分）執行的時間，“系統”是最基層算法運行系統執行（例如磁盤讀寫等）部分的時間，“流逝”是算法運行經過的總時間（可以認為是前兩者的總和）。一般優化時主要關注“用戶”的時間。

從表3-1中可以看出，優化前后的Apriori算法的用戶時間有明顯的不同，優化前算法的用戶時間比優化后算法的用戶時間長，雖然兩者的系統的時間沒有差別，但是流逝的時間總體來說是有差別的。這樣就正好證明了本篇文章所研究的主要問題——優化后的算法提升了關聯規則Apriori挖掘算法的效率，在算法運行的時間上有了比較好的提升。

四、小結

文章從原有的Apriori算法的第二個缺點入手，對原有算法進行研究并致力于創新發現一種優化后的算法——候選項目集數量最小化的Apriori優化算法，這種優化后的算法的優點可以總結為下面三個方面：（1）在從項集Lk-1中產生頻繁項集Ck時，先對Lk-1中的項的數目進行統計，根據頻繁項集的性質對Lk-1進行刪減，從而能減少參加組合頻繁項集的項集數目；（2）對優化前后算法的運行時間有明顯的區別：優化后的算法比優化前的算法所要花費的運行時間比較少，在一定程度上降低了挖掘的成本。（3）在大數據的環境中，該優化后的算法的運行效率較之前原有算法的高，優化后的算法具有明顯的優勢。

但優化后的算法也有一定的缺陷。在考慮了算法的候選項集的問題的同時，忽略了掃描數據庫次數的問題，并且在進行優化的同時，算法編寫的過程也有一定的難度，需要耗費大量的時間和精力來完成，且精度也有待進一步的提升。

［1］徐華.數據挖掘：方法與應用［N］.北京：清華大學出版社，2014：66-75.

［2］ Agrawal R，Imielinski T，Swami A.Mining association rules between sets of items in large databases.SIGMOD'93.

［3］ 胡慧蕎，王周敬.一種基于關系矩陣的關聯規則快速挖掘算法［J］.計算機應用，2005，25（7）：1577-1579.

張彤，女，漢族，陜西銅川人，碩士研究生研究方向：非線性動力學與統計學。