張 彤

西安財(cái)經(jīng)學(xué)院長安校區(qū)

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

張 彤

西安財(cái)經(jīng)學(xué)院長安校區(qū)

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

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

一、緒論

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

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

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

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

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

（一）核心算法分析

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

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

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

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

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

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

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

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

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

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

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

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

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

下面先對(duì)表中的一些專業(yè)術(shù)語進(jìn)行解釋：

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

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

四、小結(jié)

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

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

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

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

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

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