談改進(jìn)的Ａｐｒｉｏｒｉ關(guān)聯(lián)挖掘算法的實踐應(yīng)用

范生萬　鮑　靜

中圖分類號：TP311 文獻(xiàn)標(biāo)識碼：A

內(nèi)容摘要：本文介紹了數(shù)據(jù)挖掘技術(shù)在圖書館中的應(yīng)用，并運用改進(jìn)的Apriori關(guān)聯(lián)挖掘算法對安徽省圖書館自動化系統(tǒng)中讀者流通庫進(jìn)行挖掘，并對挖掘出的結(jié)果及其意義進(jìn)行評價，從而為圖書館讀者管理、圖書資源的采購提供決策支持。

關(guān)鍵詞：數(shù)據(jù)挖掘 Apriori算法 圖書館管理 讀者管理

數(shù)據(jù)挖掘技術(shù)在商業(yè)領(lǐng)域內(nèi)的應(yīng)用給圖書館帶來了很大的啟發(fā)。圖書館的數(shù)據(jù)庫可以運用數(shù)據(jù)挖掘技術(shù)中的關(guān)聯(lián)規(guī)則分析、聚類分析、決策樹、時間序列分析等數(shù)據(jù)挖掘方法，以找出數(shù)據(jù)庫中蘊(yùn)藏的對于圖書館管理有用的潛在規(guī)則，并且通過描述和預(yù)測，為圖書館的圖書采購、讀者服務(wù)、館藏目錄設(shè)置等管理工作提供決策支持。

關(guān)聯(lián)規(guī)則是與多數(shù)人想象的挖掘過程中最相近的一種數(shù)據(jù)挖掘形式，即尋找在同一事件中出現(xiàn)的不同項的相關(guān)性。關(guān)聯(lián)規(guī)則的研究有助于發(fā)現(xiàn)數(shù)據(jù)庫中不同商品間的聯(lián)系，找出顧客購買行為模式。在圖書館運用關(guān)聯(lián)規(guī)則分析可以細(xì)分出讀者群，根據(jù)其借閱情況提供不同的服務(wù)，為圖書館的管理決策提供參考。關(guān)聯(lián)規(guī)則的核心算法是Apriori算法。

關(guān)聯(lián)規(guī)則的基本概念及算法

挖掘流通借閱事務(wù)數(shù)據(jù)庫中所有的關(guān)聯(lián)規(guī)則的問題可以被劃分成如下兩個子問題：

找出所有具有最小支持度的項集（即頻繁項集），可用Apriori算法來找出頻繁項集。由頻繁項集產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則，對于每一個頻繁項集I，找出其中所有的非空子集，然后，對于每一個這樣的子集a，如果support（I）與support（a）的比值大于最小置信度，則存在規(guī)則a=>（I-a）。

（一）關(guān)聯(lián)規(guī)則算法

關(guān)聯(lián)規(guī)則的挖掘主要是在數(shù)據(jù)庫中找出支持用戶指定的最小支持度S和最小置信度C的關(guān)聯(lián)規(guī)則，從而指導(dǎo)人們的一些管理決策。目前，關(guān)聯(lián)規(guī)則的挖掘方法主要是找出數(shù)據(jù)庫中的頻繁項集，然后由頻繁項集產(chǎn)生關(guān)聯(lián)規(guī)則。

（二）Aprior算法

Apriori算法是一種挖掘布爾關(guān)聯(lián)規(guī)則的頻繁項集的算法，它主要是利用逐層搜索的迭代方法來尋找數(shù)據(jù)庫中頻繁出現(xiàn)的項集。主要步驟是：第一步，產(chǎn)生頻繁1-項集L₁，掃描數(shù)據(jù)庫D，出現(xiàn)在D中各個數(shù)據(jù)項的集合就是頻繁1-項候選項集C1，并統(tǒng)計出每個數(shù)據(jù)項出現(xiàn)的次數(shù)，次數(shù)大于最小支持計數(shù)（預(yù)先）定義的項的集合就是頻繁1-項集L₁；第K步，產(chǎn)生頻繁K-項集L_k，利用上一步產(chǎn)生的頻繁（K-1）-項集L_k-1，與自己連接產(chǎn)生K-項集候選集C_k，掃描數(shù)據(jù)庫事務(wù)庫，計算C_k中每個成員出現(xiàn)的次數(shù)，將小于最小支持度的候選項刪除，最后產(chǎn)生頻繁K-項集。

算法：Apriori使用根據(jù)候選生成的逐層迭代找出頻繁項集

輸入：流通借閱數(shù)據(jù)庫D；最要支持度閾值minsup

輸出：D中的頻繁項集L

算法代碼：

1）L₁一所有頻繁項集1-項目集；

2）for（k=2；L_k≠φ，k++）{

3）C_k=apriori_gen(L_k-1，minsupport）

4）for all C∈C_tdo{

5）C_t=Subset（C_k，T）

6）For all c∈C_tdo

7）c.count++；

8）}

9）L_k={c∈C_k|support（c）>=minsup}

10）}

11）return L={所有的L_k}

Apriori算法的第1步找出頻繁1-項集的集合L₁。在第2~10步中，L_k-1用于產(chǎn)生候選C_k，以找出L_k。Apriori過程產(chǎn)生候選，第3步使用Apriori性質(zhì)刪除那些具有非頻繁子集的候選，第4步掃描數(shù)據(jù)庫，第5步使用subset函數(shù)找出事務(wù)中的候選的所有子集，第6步和第7步對每個這樣的候選累加計數(shù)。最后，所有滿足最小支持度的候選會形成頻繁項集L。

Apriori-gen過程

Apriori-gen過程由L_k-1產(chǎn)生第K次迭代時的候選項集C_k，該過程描述如下：

For each itemset I₁∈L_k-1

For each itemset I₂∈L_k-1

If （I₁[1]=I₂[1]）∧(I₁[2]=I₂[2]∧…∧（I₁[K-2]=I₂[K-2]）∧（I₁[K-1 ]=I₂[K-2]）∧（I₁[K-I]=I₂[K-1]）

Then {c=I[1]，I₁[2]，…I₁[K-I]，I₂[K-1]）；

C_k=C_kU c；

For（c的每個包含k-1個項目的子集s）{

If（s不屬于F_k-1）

從C_k中刪除C；

}

Return（C_k）；

改進(jìn)的Apriori算法在圖書館的具體實現(xiàn)

以安徽省圖書館某年度讀者借閱事務(wù)庫為例，可從圖書館借閱記錄中挖掘出形如“讀者-圖書”強(qiáng)關(guān)聯(lián)規(guī)則。首先要進(jìn)行數(shù)據(jù)清洗，只保留屬性概念中分層最低層的屬性項，將同一個讀者的所有借閱記錄合并為一條記錄。

（一）算法思想

在讀者借閱記錄關(guān)聯(lián)規(guī)則挖掘過程中有一些特殊的性質(zhì)，因為每一個讀者借閱記錄的長度是固定的，即含有五個單項，前四個是屬性值，最后一個是圖書分類號，并且要挖掘的規(guī)則最后一項必須是圖書分類號，且不能出現(xiàn)沖突的屬性值或圖書分類號。基于這些特殊性質(zhì)，在數(shù)據(jù)挖掘中對Apriori改進(jìn)算法如下：

1）把壓縮過的事務(wù)集讀入內(nèi)存；

2）掃描事務(wù)集，找到每一類頻繁單項：即頻繁的年齡段、頻繁的學(xué)歷、頻繁的職稱、頻繁的職業(yè)、頻繁的圖書分類。

3） 把各類頻繁的屬性單項和頻繁的圖書分類單項連接成 2 - 候選頻繁項集， k = 2。即生成年齡-圖書類，學(xué)歷-圖書類，職業(yè)-圖書類，職稱-圖書類，分別生成頻繁2項集。

4） 檢查k-候選頻繁項集，記錄其支持度和前件的支持度。頻繁項集的連接條件是前n項是為讀者屬性項，且讀者的屬性項內(nèi)容各不相同，最后一項為相同的圖書分類項。

5） 輸出置信度和支持度達(dá)到要求的頻繁 k - 頻繁項集。置信度為支持度除以前件的支持度。

6） 用得到k - 頻繁項集互相連接得到k+1 - 候選頻繁項集。通過剪枝，可減少連接的頻繁項集的個數(shù)，提高程序運行的效率。下面的是剪枝連接的規(guī)則：

a） 如果頻繁項集A 和 B 最后一項不同的時候不能連接。

b） 含有屬于同一屬性類別的不同單項，則不能連接。

c） 頻繁項集也不能和自身連接。

d） 如果用conf代表前件支持度，那么當(dāng)min （ A.conf， B.conf）/最小支持度<最小置信度時，不能連接 A，B。

e） 其它情況可以連接。

7） k ++， 如果生成的候選頻繁項集數(shù)目不為0，轉(zhuǎn)4），否則結(jié)束。

本算法主要改進(jìn)是步驟6， 這是經(jīng)典的Apriori算法沒有的。其他的連接過程可以參閱Apriori的連接。本文通過設(shè)置最小置信度閾值以找出強(qiáng)關(guān)聯(lián)規(guī)則，令圖書類型為每條規(guī)則后件，讀者屬性為每條規(guī)則前件，最后得到關(guān)聯(lián)規(guī)則。

（二）程序?qū)崿F(xiàn)

// apriori算法的程序

void Apriori::Do（）

{

vector candidates；

vector patterns；

generate2candidates（candidates）； // 生成候選2項集

while（!candidates.empty（）） // 當(dāng)候選項集為空時中止

{ verify_candidate（candidates， patterns）；// 過濾候選k-1項集， 返回用于連接生成候選k項集的列表，同時輸出滿足所有條件的規(guī)則

generate_k_candidates（patterns，candidates）； // 連接生成候選k項集， 準(zhǔn)備下一次循環(huán)

patterns.clear（）；

}

}

生成K項候選頻繁集：

inline void Apriori：：generate_k_candidates（const vector&patterns，

vector&candidates）

{

for（int i = 0； i < patterns.size（）； ++i）// 遍歷過濾后的候選k-1項集， 兩兩連接

for（int j = i+1； j < patterns.size（）； ++j）

if（Items_method：：Is_compatible_Items（patterns[i].items_，patterns[j].items_））// 首先判斷能否連接

if（（double）min（patterns[i].freq_，patterns[j].freq_） / minSupport_ >= minConf_）

{Items items = Items_method：：join_Items（patterns[i].items_，patterns[j].items_）；// 連接得到k項集， 保存到輸出列表

candidates.push_back（ItemsCounter（items，0，0））；

}

}

（三）算法評價

通過上述的介紹，可以看到本算法的思路基本上與Apriori算法保持一致，即它們的共同之處是通過掃描數(shù)據(jù)得到那些支持度不小于用戶給定的最小支持度的頻繁項集，但是又有不同之處就是在掃描數(shù)據(jù)庫之前就進(jìn)行了剪枝，在剪枝后再重新連接掃描數(shù)據(jù)庫，減少了掃描的次數(shù)。

在算法效率上，通過數(shù)據(jù)壓縮可將挖掘的數(shù)據(jù)一次性掃描進(jìn)入內(nèi)存中，避免了重復(fù)磁盤I/O操作，沒有壓縮的數(shù)據(jù)不可能一次性讀入內(nèi)存，從而提高了計算效率；另通過數(shù)據(jù)壓縮減少了每一項字符長度，特別是在比較兩項是否相同的時候，需比較的字符數(shù)就少了很多，可以提高運算速度。通過使用數(shù)據(jù)壓縮的方式，節(jié)省了內(nèi)存，減少了候選集比較的時間，從而生成頻繁項集速度將更快，同時加入了同屬性列只能出現(xiàn)一次和后件必須相同的約束，使得連接次數(shù)大大減少，計算復(fù)雜度也降低了。在對圖書館這樣的大型數(shù)據(jù)庫而言，這種節(jié)省對數(shù)據(jù)挖掘效率提高的作用就顯而易見。

（四）關(guān)聯(lián)規(guī)則挖掘結(jié)果分析

根據(jù)以上關(guān)聯(lián)規(guī)則挖掘結(jié)果分析，可以看到這種算法改進(jìn)具有一定的實際意義：

通過研究讀者群體的特征和關(guān)系，可以按年齡、學(xué)歷、職業(yè)等因素對讀者群體進(jìn)行分類，也可以進(jìn)行聚類，把讀者群體細(xì)分，可以更清楚地了解讀者的特點和需求；通過以上挖掘出的規(guī)則，進(jìn)一步了解讀者的特點，提高圖書館的吸引力，改進(jìn)讀者服務(wù)和提高讀者的滿意度；可以統(tǒng)計出讀者的借閱頻率、書籍流通趨勢和周期，通過更科學(xué)地規(guī)劃館藏，提高圖書的借閱率；通過分類，對重要的讀者提供更優(yōu)質(zhì)的服務(wù)，從而使讀者忠誠度更高；提高圖書館管理效率，提高決策水平，改進(jìn)服務(wù)流程，使圖書館的服務(wù)流程更合理，最終提高管理效率；提高讀者興趣度，改善采購水平和質(zhì)量，購進(jìn)讀者需要的書籍；通過科學(xué)規(guī)劃館藏目錄，提高館藏借閱率。

總之，Apriori算法能有效地進(jìn)行關(guān)聯(lián)規(guī)則的數(shù)據(jù)挖掘。本文根據(jù)圖書數(shù)據(jù)挖掘中最后一項是固定的圖書分類的特點，提出的改進(jìn)Apriori算法，是根據(jù)圖書館數(shù)據(jù)特點進(jìn)行連接和剪枝，生成頻繁項集，進(jìn)一步縮小了挖掘的范圍，提高了數(shù)據(jù)挖掘的效率，使得到的規(guī)則更加科學(xué)合理。

參考文獻(xiàn)：

1.朱小棟，鄭誠等.關(guān)聯(lián)規(guī)則的哈希修剪算法研究.安徽大學(xué)學(xué)報（自然科學(xué)版），2005（7）

2.佟強(qiáng)，周園春，閻保平.關(guān)聯(lián)規(guī)則挖掘算法.微電子學(xué)與計算機(jī)，2005（6）