李華群

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

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

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

1 Apriori算法簡介

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

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

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

2 基于改進的Apriori算法

2.1 基本思想

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

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

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

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

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

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

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

2.2 基于改進的Apriori算法主要步驟

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

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

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

表2 初始矩陣M0

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

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

表3 新矩陣M1

第四步：對新矩陣M1中的各行進行矩陣邏輯與運算，得出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項集進行連接操作，同時掃描矩陣M1，對連接各行進行邏輯與運算，得出i1∧i2∧i3={0110，2}，i2∧i3∧i4={0011，2}，i1∧i2∧i4={0010，1}，刪除支持度≤1的項，得到頻繁3-項集L3={ABC，BCE}。生成K-項集，停止本次矩陣邏輯與運算。

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

3.1 實驗環(huán)境

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

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

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

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

3.3 算法運行

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

表5 索書號和讀者號對應關系

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

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

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

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

3.4 算法性能分析

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

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

4 結束語

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