李華群

(河南理工大學(xué) 圖書館，河南 焦作 484000)

關(guān)聯(lián)規(guī)則挖掘就是從大量的數(shù)據(jù)中挖掘出有價值描述數(shù)據(jù)項之間相互聯(lián)系的有關(guān)知識，作為數(shù)據(jù)挖掘中最經(jīng)典的方法之一，被廣泛應(yīng)用于各行各業(yè)中。如應(yīng)用到商業(yè)零售行業(yè)，分析顧客的購買特性來指導(dǎo)商品的排架、商品定價、商品的采購；應(yīng)用到金融和保險服務(wù)行業(yè)，通過分析大量的金融數(shù)據(jù)，為投資活動建立貿(mào)易和風(fēng)險模型，指導(dǎo)股票選擇、貨幣交易等；應(yīng)用到科學(xué)研究領(lǐng)域，可以從大量的、漫無頭緒的科學(xué)數(shù)據(jù)中提煉出有用的信息；還被應(yīng)用于電信網(wǎng)絡(luò)管理、醫(yī)療數(shù)據(jù)挖掘、制造業(yè)故障診斷等其他應(yīng)用領(lǐng)域[1]。目前高校圖書館每天會產(chǎn)生大量的圖書流通數(shù)據(jù)，運用關(guān)聯(lián)規(guī)則分析也可以從大量的讀者歷史借閱數(shù)據(jù)中挖掘出有用的信息和隱含信息來指導(dǎo)圖書館服務(wù)和管理工作。

近年來，越來越多學(xué)者將關(guān)聯(lián)規(guī)則Apriori算法應(yīng)用到圖書館數(shù)據(jù)挖掘中。張雪艷[2]將Apriori算法的關(guān)聯(lián)規(guī)則應(yīng)用到圖書館資源配置中，不僅可簡化采訪工作，還可以更好地進(jìn)行讀者導(dǎo)讀服務(wù)；陳淑英[3]等將關(guān)聯(lián)規(guī)則應(yīng)用到高校圖書館圖書推薦服務(wù)中，通過對不同專業(yè)不同用戶群體在不同年級時的圖書關(guān)聯(lián)規(guī)則分析，探索有效和有針對性的圖書推薦服務(wù)策略；高晟[4]等將關(guān)聯(lián)規(guī)則與貝葉斯網(wǎng)絡(luò)相結(jié)合的高校圖書館個性化圖書推薦服務(wù)；文芳[5]等提出基于FP-growth關(guān)聯(lián)規(guī)則的圖書館數(shù)據(jù)快速挖掘算法研究，通過改進(jìn)關(guān)聯(lián)規(guī)則算法，在運行效率方面有了明顯的提升。通過大量研究，發(fā)現(xiàn)關(guān)聯(lián)規(guī)則應(yīng)用到圖書館數(shù)據(jù)挖掘中，有明顯的實際效果和意義，但因傳統(tǒng)的關(guān)聯(lián)規(guī)則Apriori算法本身存在一些結(jié)構(gòu)缺點，如會產(chǎn)生大量的頻繁項集，每次搜索項集都要在數(shù)據(jù)庫中訪問，造成了非常大的內(nèi)存消耗和I/O過載，如果能減少數(shù)據(jù)庫掃描的次數(shù)，則可以大大提高關(guān)聯(lián)規(guī)則的運行效率?；诖?，筆者對關(guān)聯(lián)規(guī)則Apriori算法進(jìn)行改進(jìn)，將矩陣思想運用進(jìn)來，并對算法進(jìn)行優(yōu)化，減少掃描次數(shù)，優(yōu)化生成頻繁項集的步驟，以此達(dá)到提高運行效率的目的。

1 Apriori算法簡介

Apriori算法是關(guān)聯(lián)規(guī)則所需頻繁項集的基本算法。是根據(jù)有關(guān)頻繁項集特性的先驗知識而命名的。該算法利用了層次順序搜索的循環(huán)方法來完成頻繁項集的挖掘工作。具體步驟就是：首先找出頻繁1-項集，記為L1；然后利用L1來挖掘L2，得到頻繁2-項集；如此不斷循環(huán)下去直到無法發(fā)現(xiàn)更多的頻繁k項集為止，每挖掘一層都需要掃描整個數(shù)據(jù)庫一遍。

Apriori算法將關(guān)聯(lián)規(guī)則的挖掘問題可以分為兩個子問題：第一步是找出事務(wù)數(shù)據(jù)庫中所有大于等于用戶指定的最小支持度的數(shù)據(jù)項集；第二步是利用頻繁項集生成所需要的關(guān)聯(lián)規(guī)則，根據(jù)用戶設(shè)定的最小置信度進(jìn)行取舍，最后得到強(qiáng)關(guān)聯(lián)規(guī)則。其中第一步是最核心要解決的問題，通過迭代方法每挖掘一層都需要掃描整個數(shù)據(jù)庫來求出事務(wù)集中所有的頻繁項集[6]。

因Apriori算法采用了逐層搜索迭代的方法，雖然算法簡單明了，沒有復(fù)雜的理論推導(dǎo)，也易于實現(xiàn)，但有一些難以克服的缺點：①多次掃描事務(wù)數(shù)據(jù)庫，需要很大的I/O負(fù)載。對于第k次循環(huán)，候選集Ck中的每個元素都必須通過掃描數(shù)據(jù)庫一次來驗證其是否加入Lk。假如有一個頻繁項集包含10個項的話，那么就至少需要掃描事務(wù)數(shù)據(jù)庫10遍。 ②可能產(chǎn)生龐大的候選集。候選項集合在項目數(shù)過多時產(chǎn)生的候選集呈指數(shù)型增長。特別是頻繁2-項集，例如105的1-項集就有可能產(chǎn)生接近109個元素的2-候選集。如此大的候選集對時間和存儲空間都是一種挑戰(zhàn)，嚴(yán)重影響計算效率[7]。

2 基于改進(jìn)的Apriori算法

2.1 基本思想

Apriori算法中，事務(wù)數(shù)據(jù)存放在數(shù)據(jù)庫，為了獲取候選集，需要多次掃描事務(wù)數(shù)據(jù)庫，導(dǎo)致I/O負(fù)載過大，另外由Lk-1得到Ck的過程，會導(dǎo)致產(chǎn)生大量的沒有實際操作意義的候選集，為了改善算法的運行效率，采用矩陣方式存儲事務(wù)項和數(shù)據(jù)項。

基于矩陣的關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘算法，若事務(wù)數(shù)據(jù)庫D含有n個事務(wù)(T1，T2，…，Tn)，m個項(I1,I2,…,Im)，由事務(wù)數(shù)據(jù)庫D映射成對應(yīng)的布爾矩陣M形式如圖1[8]。

圖1 事務(wù)數(shù)據(jù)庫對應(yīng)的矩陣M

首先是將事務(wù)與數(shù)據(jù)項對應(yīng)的關(guān)系利用多維矩陣的形式表達(dá)出來，對事務(wù)項進(jìn)行量化，用1或0表示當(dāng)前事務(wù)項是否存在，若第i個項集在第j個事務(wù)中，則矩陣第i行第j列的值dij為1，否則為0。

其次是對矩陣進(jìn)行修剪、壓縮，先對每個行向量進(jìn)行求和，并依照支持度大小降序排列，其和小于最小支持度的將對應(yīng)的行向量刪除；再對每個列向量進(jìn)行求和，將一個事務(wù)小于k項的事務(wù)項刪除，得到新的矩陣M1。

然后對矩陣M1中m行任取k行形成k項集Ck={Ii1，Ii2，…，Iik}，進(jìn)行邏輯與運算，其支持度為：

最后，判斷所有支持度，將不小于支持度的項，加入頻繁項集Lk中，直到不能產(chǎn)生頻繁項集，算法至此結(jié)束，所有頻繁項集為L=∪Lk。

2.2 基于改進(jìn)的Apriori算法主要步驟

如表1，第一列分別代表事務(wù)項T100、T200、T300、T400、T500、T600、T700，第二列分別代表各事務(wù)的數(shù)據(jù)項。

表1 事務(wù)型數(shù)據(jù)庫

第一步：首先將此表構(gòu)造成一個矩陣M0，掃描該事務(wù)數(shù)據(jù)庫，存在數(shù)據(jù)項被初始化為1，否則為0；如表2。

表2 初始矩陣M0

第二步：行壓縮，刪除矩陣中出現(xiàn)次數(shù)小于最小支持度的單個數(shù)據(jù)項。設(shè)定最小支持度為1。因關(guān)聯(lián)規(guī)則里的頻繁項集的所有非空子集必然也是頻繁項集，因此可以對出現(xiàn)次數(shù)小于等于最小支持度的數(shù)據(jù)項進(jìn)行刪除。分別對以上矩陣的每個行向量進(jìn)行求和，并依照支持度大小降序排序，得到數(shù)據(jù)項D出現(xiàn)次數(shù)≤1，刪除數(shù)據(jù)項D，對矩陣進(jìn)行修剪壓縮。

第三步：列壓縮，刪除矩陣中事務(wù)數(shù)量少于等于(k-1)的事務(wù)，設(shè)K=3，因為一個事務(wù)不足K個項，他不可能包含k-頻繁項集，所以刪除事務(wù)T500、T600、T700后形成的新矩陣M1如表3。

表3 新矩陣M1

第四步：對新矩陣M1中的各行進(jìn)行矩陣邏輯與運算，得出i1∧i2={1110，3}，i2∧i3={0111，3}，i1∧i3={0110，2}，i2∧i4={0011，2}，i1∧i4={0010，1}，i3∧i4={0010，1}，并依照支持度降序，刪除支持度≤1的項，得到頻繁2-項集L2={AB，BC，AC，BE}。

第五步：根據(jù)頻繁項集的所有非空子集都必須是頻繁的，將頻繁2項集進(jìn)行連接操作，同時掃描矩陣M1，對連接各行進(jìn)行邏輯與運算，得出i1∧i2∧i3={0110，2}，i2∧i3∧i4={0011，2}，i1∧i2∧i4={0010，1}，刪除支持度≤1的項，得到頻繁3-項集L3={ABC，BCE}。生成K-項集，停止本次矩陣邏輯與運算。

3 改進(jìn)Apriori算法在圖書館數(shù)據(jù)挖掘中應(yīng)用

3.1 實驗環(huán)境

為了對文中提出的改進(jìn)的Apriori算法進(jìn)行分析和驗證， 進(jìn)行了仿真測試。硬件環(huán)境為： Intel Core i5-4590，8G Hz 處理器，4G 內(nèi)存，1T 硬盤。軟件環(huán)境為： Windows 7操作系統(tǒng)，MatlabR2016b仿真軟件。

3.2 數(shù)據(jù)預(yù)處理

本實驗采用了某高校圖書管理系統(tǒng)中的數(shù)據(jù)集。該數(shù)據(jù)集包含2019年的計算機(jī)類專業(yè)1 200名本科生4 365條圖書借閱歷史日志記錄。首先對原始數(shù)據(jù)進(jìn)行數(shù)據(jù)預(yù)處理，僅保留有用數(shù)據(jù)列，如讀者號、索書號、題名、年級等，數(shù)據(jù)清理和集成后數(shù)據(jù)入表4。

表4 處理后圖書館借閱數(shù)據(jù)記錄

3.3 算法運行

筆者依據(jù)改進(jìn)關(guān)聯(lián)規(guī)則的算法步驟，對讀者借閱圖書的索書號與借閱圖書的索書號進(jìn)行數(shù)據(jù)挖掘關(guān)聯(lián)規(guī)則分析，經(jīng)過反復(fù)試驗，設(shè)置最小支持度為0.5%，最小置信度為10%，K=3。首先將讀者號和借閱書籍的索書號對應(yīng)關(guān)系如表5，生成相應(yīng)的布爾矩陣，行矩陣代表索書號，列矩陣代表每個讀者號。

表5 索書號和讀者號對應(yīng)關(guān)系

再在計算生成頻繁項集之前，先對矩陣進(jìn)行修剪和壓縮，減少隱含信息量少的記錄，保留蘊(yùn)含有重要信息的行向量和列向量，減少數(shù)據(jù)的存儲，獲得需要較小存儲空間的新矩陣，再對任意各行向量之間求邏輯與，生成候選項集，最后得到滿足條件的頻繁項集如表6。

表6 關(guān)聯(lián)規(guī)則

由此得出的關(guān)聯(lián)規(guī)則可知，借閱了Java類書和C、C++語言基礎(chǔ)書的，有29.4%的學(xué)生都借閱了HTML+Java網(wǎng)頁制作類書；借閱了Java類的書有27.8%的學(xué)生都借閱了Python學(xué)習(xí)類書籍，有30%學(xué)生還借閱了Android程序設(shè)計與開發(fā)類書；借閱了C語言基礎(chǔ)類書的有23.8%的學(xué)生還借閱了敘事類故事性強(qiáng)的文學(xué)書，而且學(xué)生大多分布在大一大二年級。依據(jù)此分析結(jié)果特性，我們可根據(jù)不同年級推薦相應(yīng)感興趣的書籍，在大一大二期間，主要以基礎(chǔ)計算機(jī)語言學(xué)習(xí)和休閑類書籍為主，大三大四更以專業(yè)性針對性很強(qiáng)的計算機(jī)類書籍為主，主要集中在熱門的Java類、python、網(wǎng)頁設(shè)計、Android程序設(shè)計為主。

通過以上分析，改進(jìn)的Apriori算法可以對讀者的歷史借閱圖書的索書號進(jìn)行數(shù)據(jù)挖掘關(guān)聯(lián)分析，挖掘出讀者需求的隱含信息，可以指導(dǎo)圖書館人員提供主動化、個性化圖書借閱服務(wù)，方便讀者依據(jù)自己的愛好和習(xí)慣快速找到符合需求的書籍，避免盲目“逛館”的情況。

3.4 算法性能分析

使用相同的最小支持度和置信度， 隨著事務(wù)數(shù)不斷增加的情況下，比較傳統(tǒng)的關(guān)聯(lián)規(guī)則Apriori算法和基于改進(jìn)的關(guān)聯(lián)規(guī)則Apriori算法執(zhí)行時間，如圖2所示，可知，當(dāng)事務(wù)數(shù)比較小時，兩者算法運行時間相差無幾， 但當(dāng)事務(wù)數(shù)逐漸增多時，因傳統(tǒng)算法每次產(chǎn)生頻繁項集時都需要重新對數(shù)據(jù)庫都掃描一遍，而改進(jìn)算法僅在生成矩陣時掃描一次數(shù)據(jù)庫，這樣其效率大大提高，明顯優(yōu)于傳統(tǒng)的關(guān)聯(lián)規(guī)則算法。

圖2 不同事務(wù)數(shù)兩種算法執(zhí)行時間對比

4 結(jié)束語

筆者利用高效圖書館的歷史借閱數(shù)據(jù)，結(jié)合改進(jìn)的關(guān)聯(lián)規(guī)則Apriori算法，從中挖掘出不同讀者對借閱書籍索書號的關(guān)聯(lián)規(guī)則，發(fā)現(xiàn)了一些借閱書籍的共同喜好，分析出的關(guān)聯(lián)規(guī)則不僅可以快速幫忙讀者獲取自己喜好和符合需求的書籍，還可以幫助圖書館工作人員采取主動化、個性化推薦信息服務(wù)。讀者在檢索圖書時，可以優(yōu)先推薦強(qiáng)關(guān)聯(lián)規(guī)則的圖書，快速確定符合自己需求的書籍，縮短借閱時間，也提高了熱門書籍的借閱率。筆者分析了改進(jìn)的單維關(guān)聯(lián)規(guī)則，對讀者借閱的圖書索書號與索書號之間進(jìn)行了關(guān)聯(lián)挖掘分析，挖掘出的信息還是有限的，在后續(xù)的研究中，應(yīng)從多維的角度，比如借閱的時間與借閱分類號之間的關(guān)聯(lián)分析等多個因素加入進(jìn)行更全面關(guān)聯(lián)分析，以此來深入挖掘圖書館更多復(fù)雜數(shù)據(jù)信息，為讀者提供更快捷、更符合需求的服務(wù)，為圖書館個性化推薦服務(wù)提供更多的理論指導(dǎo)。