鄧廣彪

摘 要： 高校圖書管理系統(tǒng)經(jīng)過多年運(yùn)行產(chǎn)生了大量借閱數(shù)據(jù)，為從借閱數(shù)據(jù)中發(fā)現(xiàn)讀者借閱圖書的行為模式和借閱規(guī)律，提出使用PrefixSpan算法對(duì)借閱數(shù)據(jù)進(jìn)行序列模式挖掘。為平衡序列模式中支持度和長(zhǎng)度各自的重要性，將挖掘結(jié)果進(jìn)行規(guī)范化處理，得到帶有權(quán)值的序列模式。通過對(duì)帶有權(quán)值序列模式進(jìn)行分析，可得到讀者借閱圖書的前后銜接關(guān)系和借閱規(guī)律，根據(jù)這些借閱規(guī)律可對(duì)讀者進(jìn)行借閱指導(dǎo)。

關(guān)鍵詞： 序列模式； PrefixSpan算法； 規(guī)范化； 借閱規(guī)律

中圖分類號(hào)：TP274+.2 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1006-8228（2014）04-34-03

Abstract： The operation of the college library management system has generated a large amount of borrowing data for so many years. In order to find out the behavior pattern and borrowing rules of readers， the PrefixSpan algorithm is proposed to lead data sequence pattern mining. To keep balance of importance between the support degree and the length in sequence mode， the mining results will be normalized and the sequence patterns will be given with weights. Based on the weighted sequential pattern analysis， the linking relation and the borrowing rules can be obtained， and readers may borrow based on these rules.

Key words： sequential patterns； prefixspan algorithm； normalization； borrowing rules

0 引言

數(shù)據(jù)挖掘又稱為數(shù)據(jù)中知識(shí)發(fā)現(xiàn)，是從海量數(shù)據(jù)中獲得有趣、有用、隱含在數(shù)據(jù)背后且可理解的相關(guān)知識(shí)[1]。數(shù)據(jù)挖掘中常見方法有關(guān)聯(lián)規(guī)則、分類、聚類、序列模式、Web挖掘等，這些技術(shù)在圖書館的應(yīng)用主要集中在關(guān)聯(lián)分析和聚類分析[2]兩方面，使用序列模式進(jìn)行分析的較少。

目前各高校圖書管理系統(tǒng)經(jīng)過多年運(yùn)行生成大量借閱數(shù)據(jù)，通過對(duì)這些數(shù)據(jù)直接分析可得知哪些是熱門書籍讀者借閱圖率、圖書利用率等信息，但是要發(fā)現(xiàn)借閱數(shù)據(jù)背后的規(guī)律不是直接分析數(shù)據(jù)能夠做到的。同時(shí)，圖書館是為讀者服務(wù)的部門，應(yīng)該主動(dòng)掌握讀者的借閱習(xí)慣、借閱規(guī)律和借閱傾向，主動(dòng)為讀者推薦書籍。借助于系統(tǒng)推薦圖書分兩個(gè)方面，一方面是讀者借閱某本圖書時(shí)主動(dòng)為其推薦相關(guān)書籍并給出借閱圖書的先后順序；另一方面是在讀者根本不清楚自己要閱讀什么書時(shí)，應(yīng)根據(jù)讀者專業(yè)主動(dòng)推薦相關(guān)專業(yè)圖書的借閱順序。同時(shí)還要解決以往系統(tǒng)關(guān)聯(lián)規(guī)則僅能發(fā)現(xiàn)同時(shí)被某些讀者借閱過的圖書而無法給出借閱圖書的先后順序問題。因此本文提出使用PrefixSpan算法挖掘序列模式，使用[0，1]區(qū)間規(guī)范化處理挖掘到的序列模式。

1 PrefixSpan算法

PrefixSpan算法[3]在挖掘序列模式時(shí)不需要產(chǎn)生候選項(xiàng)集，挖掘速度較快。算法的基本思想是，找出頻繁1序列后產(chǎn)生投影數(shù)據(jù)庫，根據(jù)前綴挖掘投影數(shù)據(jù)庫得到局部頻繁項(xiàng)集，將前綴與局部頻繁項(xiàng)集結(jié)合得到頻繁序列，具體挖掘步驟如下。

Step1：掃描序列數(shù)據(jù)庫S，找出滿足最小支持度的頻繁1-項(xiàng)集，即得到長(zhǎng)度為1的序列模式。

Step2：將長(zhǎng)度為1的序列模式作為前綴構(gòu)造投影數(shù)據(jù)庫。

Step3：對(duì)每個(gè)前綴掃描所屬的投影數(shù)據(jù)庫，根據(jù)最小支持度得到相關(guān)局部頻繁項(xiàng)集，將前綴和局部頻繁項(xiàng)集結(jié)合得到頻繁序列。

Step4：繼續(xù)將得到的頻繁序列作為前綴，挖掘該前綴的投影數(shù)據(jù)庫得到局部頻繁項(xiàng)集，結(jié)合得到頻繁序列。重復(fù)該步驟直至不能發(fā)現(xiàn)更長(zhǎng)的頻繁序列，算法停止。

2 序列模式規(guī)范化處理

如何有效使用挖掘出來的序列模式成為序列模式應(yīng)用的關(guān)鍵。目前大部分使用的方法是按長(zhǎng)度降序排列，長(zhǎng)度越長(zhǎng)的越有用；也有按支持度降序排列，支持度越高的序列模式越有用。這兩種方法各有利弊，第1種方法序列模式支持度不夠大而不具有非常的普遍性，第2種方法序列模式太短而起到的指導(dǎo)作用小。為兼顧支持度和長(zhǎng)度的重要性，我們提出各自占50%的比例來計(jì)算序列模式的權(quán)值，但是各自的計(jì)量單位不同，支持度為百分比而長(zhǎng)度為整數(shù)，所以必須進(jìn)行數(shù)據(jù)變換，在此選擇規(guī)范化[4]處理，使支持度和長(zhǎng)度值變換后均在[0-1]范圍。

規(guī)范化處理是數(shù)據(jù)挖掘前的數(shù)據(jù)預(yù)處理方法，本文應(yīng)用于數(shù)據(jù)挖掘后結(jié)果處理是一種新的嘗試。規(guī)范化是將數(shù)據(jù)按比例縮放使之落入一個(gè)特定區(qū)間，有三種形式：最大-最小規(guī)范化、z-score規(guī)范化和按小數(shù)點(diǎn)定標(biāo)規(guī)范化，在此選擇“最大-最小規(guī)范化”，計(jì)算公式為：

其中，maxA和minA為屬性A的最大值和最小值，經(jīng)過處理后將A的當(dāng)前值v映射到區(qū)間[new_minA，new_maxA]中的v'。

3 PrefixSpan算法在讀者借閱行為模式挖掘的應(yīng)用

3.1 序列模式在讀者借閱行為挖掘的應(yīng)用模型

序列模式在圖書管理系統(tǒng)中讀者借閱行為挖掘及應(yīng)用主要分為三個(gè)步驟，即數(shù)據(jù)準(zhǔn)備、知識(shí)獲取和知識(shí)應(yīng)用，如圖1所示。數(shù)據(jù)準(zhǔn)備主要是保證被挖掘數(shù)據(jù)的準(zhǔn)確性、適用性和完整性，知識(shí)獲取主要是應(yīng)用序列模式挖掘算法對(duì)準(zhǔn)備好的數(shù)據(jù)進(jìn)行挖掘獲取讀者借閱行為，知識(shí)應(yīng)用主要是根據(jù)讀者借閱圖書的類別或讀者專業(yè)進(jìn)行相關(guān)圖書推薦。

3.2 數(shù)據(jù)狀態(tài)分析

本次序列模式挖掘使用廣西民族師范學(xué)院圖書管理系統(tǒng)中2009級(jí)、2010級(jí)本專科學(xué)生的借閱數(shù)據(jù)作為數(shù)據(jù)源進(jìn)行序列模式挖掘分析。廣西民族師范學(xué)院2009、2010級(jí)本?？茖W(xué)生共5823人，涉及到漢語、外語、計(jì)算機(jī)、管理等13個(gè)大類專業(yè)，為使得挖掘的序列模式能夠較好地發(fā)現(xiàn)各大類專業(yè)讀者的借閱行為習(xí)慣，整理好數(shù)據(jù)后按大類專業(yè)進(jìn)行序列模式挖掘。

圖書管理系統(tǒng)中借閱數(shù)據(jù)包含的屬性很多，在分析時(shí)只需要學(xué)號(hào)、借閱日期和索書號(hào)這3個(gè)字段的信息。廣西民族師范學(xué)院圖書管理系統(tǒng)每借閱一本書就會(huì)產(chǎn)生一條借閱記錄；在圖書管理系統(tǒng)中，同一本書的多個(gè)副本索書號(hào)相同，但同一類別的書有多本不同的書名，索書號(hào)的編碼以中圖分類號(hào)開頭，但“.”之后的比中圖分類號(hào)更詳細(xì)，“.”之后的用來區(qū)分同一大類中不同小類的書，最后加上“/……”區(qū)分該小類中不同的圖書，如TP391.413/1188表示《PHOTOSHOP蛻變：人像攝影與后期》這本書，TP391.413/1151表示《PHOTOSHOP CS5數(shù)碼人像修飾208例》這本書，TP391.414/72表示《FLASH CS6中文版從入門到精通》這本書，則TP391.413表示photoshop類的圖書等，那么在處理數(shù)據(jù)時(shí)對(duì)于索書號(hào)只用“/”之前的作為借閱書籍的標(biāo)識(shí)，這樣就可以區(qū)分每一小類的圖書。

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

本次挖掘從圖書管理系統(tǒng)中獲取238145條借閱記錄，經(jīng)過索書號(hào)處理后得到148236條記錄。然后以學(xué)號(hào)作為序列ID，以一天內(nèi)所借閱書籍作為序列中的一個(gè)元素，按照時(shí)間的遞增順序編排，得到每個(gè)學(xué)生借閱圖書的序列，如表1所示，最終得到的序列數(shù)據(jù)庫S有4938條序列。

3.4 序列模式挖掘

序列模式挖掘的目的是尋找序列數(shù)據(jù)庫中按照某種順序出現(xiàn)的規(guī)律[5]，但在高校讀者借閱規(guī)律中，并不是每個(gè)規(guī)律對(duì)所有專業(yè)的讀者都適用，必須要分門別類對(duì)不同專業(yè)進(jìn)行挖掘得到對(duì)應(yīng)專業(yè)的借閱規(guī)律，才能給對(duì)應(yīng)類別專業(yè)的學(xué)生進(jìn)行借閱圖書指導(dǎo)，如計(jì)算機(jī)類專業(yè)的規(guī)律不能應(yīng)用于化學(xué)類，化學(xué)類的規(guī)律對(duì)外語類學(xué)生指導(dǎo)借閱順序是沒有意義的。因此，將序列數(shù)據(jù)庫中的序列分為外語、漢語、物理、化學(xué)、數(shù)學(xué)、通信、計(jì)算機(jī)、金融、營(yíng)銷、管理、美術(shù)、音樂、體育等13個(gè)大類專業(yè)，分別對(duì)每個(gè)大類專業(yè)進(jìn)行序列模式挖掘。

本次序列模式挖掘在Win7操作系統(tǒng)、Myeclipse 8.5平臺(tái)下使用Java語言實(shí)現(xiàn)PrefixSpan算法，序列數(shù)據(jù)庫經(jīng)過處理后保存在Microsoft SQL Server 2008數(shù)據(jù)庫中，本次挖掘設(shè)置最小支持度為5%，對(duì)挖掘得到的結(jié)果中選取計(jì)算機(jī)類專業(yè)的部分序列模式，如表2所示。本次序列模式挖掘結(jié)果刪除長(zhǎng)度為1的序列模式，因?yàn)樵撃Ｊ綄?duì)獲取讀者的借閱規(guī)律沒有指導(dǎo)意義。

3.5 結(jié)果分析

根據(jù)上述挖掘結(jié)果，從圖書管理系統(tǒng)中尋找相關(guān)索書號(hào)所屬的圖書類別，得到計(jì)算機(jī)類專業(yè)第1條序列模式中圖書類別如下：

TP312C：C語言類

H319.34：大學(xué)英語四級(jí)類

TP311.138：數(shù)據(jù)庫類

TP312JA：JAVA基礎(chǔ)語言類

TP311.5：軟件工程類

TP391.413：PHOTOSHOP圖像處理類

TP312.25：JAVA項(xiàng)目開發(fā)類

TP312UM：UML建模類

TP311.55：軟件測(cè)試類

G642.477：畢業(yè)論文撰寫類

由此可知該序列為計(jì)算機(jī)類專業(yè)中軟件工程學(xué)生的借書模式，借閱圖書的基本規(guī)律：基礎(chǔ)C語言—>數(shù)據(jù)庫—>Java語言—>軟件工程—>項(xiàng)目開發(fā)—>軟件測(cè)試等，在學(xué)習(xí)的過程中穿插大學(xué)英語四級(jí)以及圖像處理的書籍。對(duì)上述挖掘結(jié)果中第2條序列模式進(jìn)行分析，可知是計(jì)算機(jī)類專業(yè)中網(wǎng)絡(luò)工程學(xué)生借閱圖書的模式。

3.6 應(yīng)用分析

為能夠更好地體現(xiàn)讀者的借閱規(guī)律，充分利用序列模式中支持度和長(zhǎng)度的重要性，將挖掘到的序列模式進(jìn)行[0，1]規(guī)范化處理。處理后計(jì)算每條序列模式的權(quán)值計(jì)算公式為：

權(quán)值=支持度×50%+長(zhǎng)度×50%

最后將挖掘得到的序列模式按照權(quán)值的降序排列以供對(duì)讀者進(jìn)行借閱推薦時(shí)使用。表3為挖掘到每大類專業(yè)的序列模式情況。

從表3可知，外語類序列模式數(shù)量較多，主要是外語類包括了英語、越南語、泰語這三類專業(yè)的借閱模式，因?yàn)楦鲗I(yè)中書籍類別不同，所以產(chǎn)生模式較多。本次序列模式挖掘結(jié)果大部分序列的支持度在5%-8.5%之間，因?yàn)樾蛄心Ｊ街惺亲畲蟮念l繁序列，最大頻繁序列的支持度一般不會(huì)很大。各大類專業(yè)中權(quán)值最大的序列一般是長(zhǎng)度較長(zhǎng)（不一定是最長(zhǎng)）且支持度在6.5%以上，這些序列具有學(xué)習(xí)的連續(xù)性和相對(duì)普遍性；權(quán)值最小的序列，一般長(zhǎng)度和支持度較小的，主要出現(xiàn)在該大類專業(yè)中少部分同學(xué)喜歡借閱其他類別專業(yè)的圖書。

在給讀者進(jìn)行借書模式推薦時(shí)，根據(jù)讀者當(dāng)前借閱的圖書，從按權(quán)值排序的序列模式中從上到下尋找當(dāng)前借閱圖書所在的序列模式，找到模式后，從該讀者的借閱歷史庫中尋找該讀者是否已經(jīng)借閱模式中當(dāng)前借閱圖書類別之前的圖書類別，若沒有，則詢問讀者是否已經(jīng)閱讀過相關(guān)圖書類別，如果沒閱讀過則推薦先閱讀相關(guān)圖書類別后再借閱當(dāng)前這本書，如果已閱讀過則推薦閱讀完當(dāng)前圖書后繼續(xù)閱讀序列模式中該圖書之后的圖書類別；若序列模式中所借閱圖書之前的圖書類別該讀者均已借閱過，則直接推薦讀者閱讀當(dāng)前所借閱圖書后，繼續(xù)閱讀序列模式中該圖書之后的圖書類別。另外，有部分讀者很茫然，不知道要閱讀什么圖書，這時(shí)可根據(jù)讀者的專業(yè)，主動(dòng)為其推薦該專業(yè)中權(quán)值最大的三個(gè)借閱模式，滿足學(xué)生個(gè)性發(fā)展的需要。

4 結(jié)束語

通過本文的研究表明，使用序列模式挖掘能從讀者借閱歷史數(shù)據(jù)中找到讀者的借閱模式和借閱規(guī)律，通過挖掘到的借閱規(guī)律可以對(duì)其他讀者借閱圖書時(shí)進(jìn)行相關(guān)圖書推薦，避免讀者借閱圖書的盲目性和隨意性，同時(shí)能提高圖書館圖書的借閱率，提高讀者對(duì)圖書館的滿意度。但是本文提出的方法僅靜態(tài)地對(duì)當(dāng)前存在的歷史借閱數(shù)據(jù)挖掘發(fā)現(xiàn)讀者借閱圖書的序列模式，而圖書館的借閱數(shù)據(jù)經(jīng)過一段時(shí)間后增加很多記錄，那么讀者的借閱規(guī)律可能會(huì)發(fā)生改變，接下來，如何快速發(fā)現(xiàn)增量數(shù)據(jù)后的借閱模式將是我們研究的方向。

參考文獻(xiàn)：

[1] 王海峰，張健，黃曉亞.數(shù)據(jù)挖掘技術(shù)及其在漁情預(yù)報(bào)中的應(yīng)用[J].計(jì)算機(jī)時(shí)代，2007.11：52-53

[2] 馮研，王馨.國(guó)內(nèi)圖書館數(shù)據(jù)挖掘技術(shù)實(shí)踐應(yīng)用進(jìn)展分析[J].圖書館學(xué)研究，2011.20：2-4

[3] J.Pei， J.Han， B.Mortazavi-Asl，et al.PrefixSpan： Mining Sequential

Patterns efficiently by prefix-projected pattern growth. In Proc of the 17th Intl. Conf. on Data Engineering， Heidelberg，Germany， April 2001.

[4] （加）Jiawei Han，MichelineKamber（著），范明，孟小峰（譯）.數(shù)據(jù)挖掘概念與技術(shù)[M].機(jī)械工業(yè)出版，2010.

[5] 王虎，丁世飛.序列模式挖掘研究與發(fā)展[J].計(jì)算機(jī)科學(xué)，2009.36（12）：14-17