張 彤

西安財經(jīng)學院長安校區(qū)

關聯(lián)規(guī)則Apriori挖掘算法的優(yōu)化研究

張 彤

西安財經(jīng)學院長安校區(qū)

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

關聯(lián)規(guī)則 頻繁項集 Apriori算法 運算效率 優(yōu)化

一、緒論

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

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

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

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

二、關聯(lián)規(guī)則Apriori算法的分析

（一）核心算法分析

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

（二）算法的優(yōu)缺點

Apriori作為頻繁項集產(chǎn)生算法，在關聯(lián)規(guī)則的數(shù)據(jù)挖掘中扮演著很重要的角色。但它也有利弊的兩面。

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

三、關聯(lián)規(guī)則Apriori算法的優(yōu)化設計

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

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

（一）優(yōu)化的Apriori算法

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

（二）優(yōu)化后的算法的設計

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

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

表3-1 優(yōu)化前后Apriori算法程序運行時間對比表

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

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

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

四、小結(jié)

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

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

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

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

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

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