鄰接矩陣在高校圖書館借閱數(shù)據(jù)挖掘中的應(yīng)用

收稿日期：2011－06－14

〔摘要〕Apriori算法是關(guān)聯(lián)規(guī)則挖掘的一個(gè)經(jīng)典算法，針對(duì)Apriori算法的不足，提出了基于鄰接矩陣的算法，該算法首先用鄰接矩陣將事務(wù)數(shù)據(jù)庫(kù)表示出來(lái)，然后基于鄰接矩陣生成頻繁k項(xiàng)集。

以高校圖書館借閱歷史數(shù)據(jù)的挖掘?yàn)槔敿?xì)描述了事務(wù)數(shù)據(jù)庫(kù)相應(yīng)的鄰接矩陣生成算法、k項(xiàng)集生成算法以及相應(yīng)的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)，算法均采用C語(yǔ)言描述。

〔關(guān)鍵詞〕Apriori算法；關(guān)聯(lián)規(guī)則；鄰接矩陣

DOI：10．3969／j．issn．1008－0821．2011．08．007

〔中圖分類號(hào)〕G252.2 〔文獻(xiàn)標(biāo)識(shí)碼〕A 〔文章編號(hào)〕1008－0821（2011）08－0025－07

Application of Adjacent-Matrix in Data Mining for University Library

Tang Jjinwen Zhang Tingxian Nie Jianguo Hu Zhenyu

（1．College of Computer Science and Technology，Qujing Normal University，Qujing 655011，China；

2．College of Physical and Electronic，Qujing Normal University，Qujing 655011，China；

3．Library，Qujing Normal University，Qujing 655011，China）

〔Abstract〕The Apriori algorithm is a classical method of association rule mining，to the deficiency of Apriori algorithm，an improved Apriori algorithm based on the adjacent matrix was put forward.This algorithm converted the affair database to adjacent matrix and operated it to find out k-frequent item sets. As an instance，the lending data of university librarys data mining of this improved algorithm was explored，which included data structure and the improved algorithm were scribed by using C programming language in detail.

〔Key words〕apriori algorithm;association rules;adjacent matrix

數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)技術(shù)、云計(jì)算、開源軟件技術(shù)、對(duì)等網(wǎng)、網(wǎng)格等技術(shù)是推動(dòng)現(xiàn)代圖書館快速發(fā)展的主要技術(shù)，要提高圖書館服務(wù)質(zhì)量的提高和水平，必須依賴這些新技術(shù)［1］。特別是圖書館個(gè)性化服務(wù)的提高，必須充分利用數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)技術(shù)。圖書館館藏?cái)?shù)量越來(lái)越大，而讀者感興趣的只是其中很少一部分，如何在浩瀚的書籍信息中找到自己感興趣的信息則是一件很頭疼的事情，如何幫助讀者高效找到所需信息資源是圖書館要研究的問題。圖書推薦服務(wù)是采取主動(dòng)的方式，向讀者提供他可能感興趣的信息，降低讀者對(duì)專業(yè)知識(shí)的要求，節(jié)約了讀者尋找資料的時(shí)間，同時(shí)提供了更豐富的信息。圖書館通過分析讀者借閱行為來(lái)分析讀者的借閱特征，發(fā)現(xiàn)讀者的興趣愛好，從而采取有個(gè)性化的服務(wù)［1］。另外，隨著圖書館數(shù)字化程度的不斷提高與數(shù)字圖書館建設(shè)的不斷發(fā)展，圖書館需要處理和提供更多、更新、更廣泛、更復(fù)雜的信息。為了避免陷入“數(shù)據(jù)豐富，但信息貧乏”的局面，圖書館有必要增強(qiáng)對(duì)海量信息的處理能力，從看似雜亂無(wú)序的信息中提取其內(nèi)在聯(lián)系，為圖書館管理提供決策支持［2］。因此，數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)技術(shù)在提升服務(wù)質(zhì)量及管理決策中具有重要作用。

數(shù)據(jù)挖掘主要是挖掘關(guān)聯(lián)規(guī)則，而關(guān)聯(lián)規(guī)則的挖掘算法主要采用經(jīng)典Apriori算法及其變形算法，如AprioriTID等。關(guān)聯(lián)規(guī)則挖掘必須建立事務(wù)數(shù)據(jù)庫(kù)，然后再應(yīng)用關(guān)聯(lián)規(guī)則挖掘算法進(jìn)行數(shù)據(jù)挖掘，本文研究事務(wù)數(shù)據(jù)庫(kù)的生成算法，然后應(yīng)用Apriori算法對(duì)高校圖書館借閱歷史數(shù)據(jù)進(jìn)行挖掘。

1 關(guān)聯(lián)規(guī)則挖掘經(jīng)典Apriori算法概述

Apriori算法是1994年Agrawal等人提出的，其思路為把挖掘關(guān)聯(lián)規(guī)則分解為2個(gè)過程：（1）找出所有大于最小支持度的項(xiàng)集；（2）對(duì)于每個(gè)頻繁項(xiàng)集，產(chǎn)生所有大于最小置信度的規(guī)則。Apriori算法使用了遞推的方法來(lái)產(chǎn)生所有頻集，利用一個(gè)層次順序搜索的迭代方法來(lái)完成頻繁項(xiàng)集的挖掘工作，即利用k-項(xiàng)集來(lái)生成(k+1)-項(xiàng)集，用候選項(xiàng)集Ck找頻繁項(xiàng)集Lk。過程由連接和剪枝兩步組成，它能比較有效地產(chǎn)生關(guān)聯(lián)規(guī)則。但存在缺點(diǎn)是明顯的：數(shù)據(jù)庫(kù)掃描次數(shù)過多，每尋找一次k-項(xiàng)集(k=1，……，K)都需要掃描數(shù)據(jù)庫(kù)一次，共掃描K次；可能產(chǎn)生大量的候選項(xiàng)目集，若頻繁1-項(xiàng)集的個(gè)數(shù)為100，則將產(chǎn)生2個(gè)候選項(xiàng)集。由此可知，Apriori算法的瓶頸是找出所有頻繁數(shù)據(jù)項(xiàng)。因此人們對(duì)Apriori算法進(jìn)行了大量的改進(jìn)，提出許多Apriori算法的變形，希望能夠找出一個(gè)高效、可靠的挖掘頻繁項(xiàng)集的算法。例如AprioriTID、AprioriHybri、HASH方法、事務(wù)壓縮技術(shù)、劃分技術(shù)等，旨在提高算法挖掘規(guī)則的效率［3－4］。本文針對(duì)高校圖書館個(gè)性化服務(wù)的要求和特點(diǎn)，提出基于鄰接矩陣的事務(wù)數(shù)據(jù)庫(kù)生成算法，數(shù)據(jù)挖掘技術(shù)并給出它的算法描述。

2 鄰接矩陣的關(guān)聯(lián)規(guī)則在高校圖書館數(shù)據(jù)挖掘中應(yīng)用

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

在讀者日常借閱事務(wù)中，每天都有大量的借還記錄匯入數(shù)據(jù)庫(kù)中。讀者借閱的對(duì)象是文獻(xiàn)資源，根據(jù)讀者長(zhǎng)期的借閱歷史數(shù)據(jù)，我們會(huì)發(fā)現(xiàn)讀者對(duì)文獻(xiàn)的借閱存在著一定的關(guān)聯(lián)、不同的學(xué)科之間也存在著關(guān)聯(lián)以及不同類型的讀者對(duì)文獻(xiàn)的借閱存在著一定的模式。挖掘出這些數(shù)據(jù)之間的關(guān)聯(lián)，有利于合理配置資源和提高資源的利用率，以及提高圖書館的服務(wù)水平。

3 小 結(jié)

應(yīng)用經(jīng)典的Apriori算法進(jìn)行關(guān)聯(lián)數(shù)據(jù)挖掘，需要多次掃描事務(wù)數(shù)據(jù)庫(kù)才能得到最大頻繁k項(xiàng)集。為了減少多次掃描事務(wù)數(shù)據(jù)庫(kù)次數(shù)，提出利用鄰接矩陣代替事務(wù)數(shù)據(jù)庫(kù)，關(guān)聯(lián)規(guī)則挖掘就基于鄰接矩陣進(jìn)行，本文就高校圖書館借閱歷史數(shù)據(jù)的關(guān)聯(lián)規(guī)則挖掘設(shè)計(jì)了相應(yīng)的數(shù)據(jù)結(jié)構(gòu)，給出k項(xiàng)集生成算法步驟并使用C語(yǔ)言對(duì)算法進(jìn)行詳細(xì)的描述。由于篇幅關(guān)系，就本文給出的算法步驟及算法描述，與實(shí)際應(yīng)用之間可能存在差距，比如，基于讀者序號(hào)及圖書序號(hào)的k項(xiàng)集，將其還原為真實(shí)的索書號(hào)及讀者編號(hào)時(shí)帶來(lái)的算法描述及開銷、一個(gè)真實(shí)的高校圖書館借閱歷史記錄的導(dǎo)出方法、借閱歷史記錄的時(shí)間段、問題規(guī)模、最小支持度及最小置信度的設(shè)置等問題在本文中沒有進(jìn)一步研究，所以沒有給出實(shí)際應(yīng)用例子。但這剛好是我們下一步要完成的工作。我們的工作僅僅完成了基于鄰接矩陣的改進(jìn)算法的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)以及C語(yǔ)言算法描述。

參考文獻(xiàn)

［1］奉國(guó)和．新技術(shù)思想與數(shù)字圖書館發(fā)展研究［J］．圖書與情報(bào)，2010，（2）：69-73．

［2］錢強(qiáng)，李英．?dāng)?shù)據(jù)挖掘技術(shù)在圖書館讀者分析中的應(yīng)用［J］．圖書情報(bào)工作，2009，52（53）:121-124．

［3］汪育健，鄒攀．基于線性鏈表的關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘技術(shù)在數(shù)字圖書館中的應(yīng)用［J］．圖書館雜志．2009，（12）：52-54．

［4］陸覺民，鄭宇．基于矩陣的數(shù)據(jù)挖掘技術(shù)在數(shù)字化圖書館中的應(yīng)用［J］．現(xiàn)代情報(bào)，2007，（12）：92-93．

［5］任賢姬．關(guān)聯(lián)規(guī)則挖掘技術(shù)在圖書借閱服務(wù)中的應(yīng)用研究［J］．情報(bào)科學(xué)，2010，28（5）:729-731．

［6］百度百科．?dāng)?shù)據(jù)挖掘科技名詞定義［EB／OL］．http:∥baike.baidu.com/view/7893.htm，2011．

［7］李超，徐昭平．基于矩陣的Apriori算法改進(jìn)［J］．計(jì)算機(jī)工程與設(shè)計(jì)，2006，（32）：23．

［8］王鋒，李勇華，毋國(guó)慶．基于矩陣的改進(jìn)的Apriori算法［J］．計(jì)算機(jī)工程與設(shè)計(jì)，2009，（30）：10．