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

范生萬(wàn)　鮑　靜

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

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

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

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

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

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

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

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

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

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

（二）Aprior算法

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

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

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

輸出：D中的頻繁項(xiàng)集L

算法代碼：

1）L₁一所有頻繁項(xiàng)集1-項(xiàng)目集；

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

Apriori-gen過(guò)程

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

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的每個(gè)包含k-1個(gè)項(xiàng)目的子集s）{

If（s不屬于F_k-1）

從C_k中刪除C；

}

Return（C_k）；

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

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

（一）算法思想

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

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

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

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

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

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

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

a） 如果頻繁項(xiàng)集A 和 B 最后一項(xiàng)不同的時(shí)候不能連接。

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

c） 頻繁項(xiàng)集也不能和自身連接。

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

e） 其它情況可以連接。

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

本算法主要改進(jìn)是步驟6， 這是經(jīng)典的Apriori算法沒(méi)有的。其他的連接過(guò)程可以參閱Apriori的連接。本文通過(guò)設(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項(xiàng)集

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

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

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

patterns.clear（）；

}

}

生成K項(xiàng)候選頻繁集：

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

vector&candidates）

{

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

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項(xiàng)集， 保存到輸出列表

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

}

}

（三）算法評(píng)價(jià)

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

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

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

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

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

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

參考文獻(xiàn)：

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

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