曾斯炎，周錦，黃國(guó)華

(邵陽(yáng)學(xué)院 理學(xué)與信息科學(xué)系，湖南 邵陽(yáng)，422000)

基于詞頻-逆文本頻率和社區(qū)劃分的圖書推薦算法

曾斯炎，周錦，黃國(guó)華

(邵陽(yáng)學(xué)院 理學(xué)與信息科學(xué)系，湖南 邵陽(yáng)，422000)

本文提出一種基于圖書內(nèi)容的圖書推薦算法。該算法利用詞頻-逆文本頻率抽象圖書特征向量，采用歐式距離度量圖書相似性，使用CNM算法對(duì)圖書相似性網(wǎng)絡(luò)進(jìn)行聚類，得到已知類別。當(dāng)讀者用戶閱讀、購(gòu)買某本圖書時(shí)，能夠?qū)⒃擃悇e里的其他圖書推薦給讀者用戶，方便其閱讀或購(gòu)買。

圖書推薦； 復(fù)雜網(wǎng)絡(luò)；社區(qū)發(fā)現(xiàn)；關(guān)鍵詞頻率；逆文本頻率指數(shù)；聚類

網(wǎng)上書店給人們購(gòu)書帶來(lái)了極大的便利。例如用戶只要輸入書名或作者等相關(guān)信息，就能立刻查到所要購(gòu)買的書籍。作為用戶來(lái)說(shuō)，當(dāng)選擇一本書后，希望再購(gòu)買一些類似的書籍或從眾多書籍中選擇一本最適合的購(gòu)買，但又限于不了解待購(gòu)書籍的詳細(xì)信息。在這種情況下，類似于導(dǎo)購(gòu)員的圖書推薦系統(tǒng)，無(wú)疑給用戶尋找書籍節(jié)省了大量時(shí)間。對(duì)于書店來(lái)說(shuō)，圖書推薦系統(tǒng)也能起到促進(jìn)圖書銷量的作用。同樣，圖書自動(dòng)推薦也能較好的應(yīng)用在大學(xué)圖書館的管理上。

為了提高圖書推薦的精準(zhǔn)性，研究人員近年來(lái)提出許多不同推薦算法[1-13]。這些算法可以分成三類：從用戶特征出發(fā)的算法，從圖書特征出發(fā)的算法以及從用戶與圖書特征相結(jié)合出發(fā)的算法。協(xié)同過(guò)濾算法[4,7,8,12,13]屬于從用戶特征出發(fā)的算法。該算法首先構(gòu)建用戶-圖書評(píng)分矩陣，計(jì)算目標(biāo)用戶與其它用戶的相似性；篩選出目標(biāo)用戶的k個(gè)最近鄰用戶；根據(jù)k個(gè)最近鄰用戶的圖書資源訪問(wèn)情況向目標(biāo)用戶推薦圖書。當(dāng)用戶-圖書評(píng)分矩陣稀疏時(shí)，協(xié)同過(guò)濾算法很難計(jì)算用戶-用戶相似性，從而導(dǎo)致推薦效率低下。徐文青等[14]利用用戶、圖書以及標(biāo)簽信息，融合熱門因子，改進(jìn)了基于內(nèi)容和協(xié)同過(guò)濾的圖書推薦算法。鄭祥云等[10]根據(jù)目標(biāo)用戶歷史借閱圖書與其它圖書的內(nèi)容相似性和用戶之間的相似性，提出了一種基于潛在狄利克雷分布模型的圖書推薦算法。用戶具有多方面的特征，同樣圖書也具有多方面的特征。特征選擇不同，圖書推薦的效果差別就很大。李克潮等[9]融合用戶和圖書方面的特征來(lái)探索圖書推薦算法，即使用圖書的中圖分類號(hào)、借閱時(shí)間、頁(yè)數(shù)等多特征計(jì)算圖書相似性，使用用戶的專業(yè)、年級(jí)、性別、興趣等多特征計(jì)算用戶相似性。李樹(shù)青等[11]將圖書與用戶分別當(dāng)作節(jié)點(diǎn)，利用圖書-用戶借閱關(guān)系構(gòu)建二分網(wǎng)絡(luò)，提出一種測(cè)度圖書可推薦質(zhì)量的迭代算法。關(guān)聯(lián)規(guī)則挖掘技術(shù)，如Apriori算法，在圖書推薦系統(tǒng)上也得到了廣泛應(yīng)用[15,16]。基于關(guān)聯(lián)規(guī)則的圖書推薦主要有生成頻繁項(xiàng)集和提取強(qiáng)關(guān)聯(lián)規(guī)則等步驟。就大數(shù)據(jù)而言，基于關(guān)聯(lián)規(guī)則的圖書推薦算法計(jì)算效率并不高。

以上推薦算法都沒(méi)有使用圖書的內(nèi)容來(lái)計(jì)算相似性。圖書內(nèi)容是讀者用戶判斷或歸類圖書最核心的特征。本文采用信息檢索和過(guò)濾技術(shù)中的詞頻(term frequency,TF)與逆文本頻率(Inverse Document Frequency,IDF)概念描述圖書，進(jìn)而構(gòu)建圖書相似性網(wǎng)絡(luò)，使用CNM社區(qū)劃分算法[17]聚類圖書，從而實(shí)現(xiàn)圖書推薦。

1 TF-IDF方法

詞頻-逆文本頻率(TF-IDF)是文本信息檢索中非常重要的方法。詞頻是指某一個(gè)特定詞語(yǔ)(特征詞)在某一文件或網(wǎng)頁(yè)中出現(xiàn)的頻率。逆文本頻率是衡量詞語(yǔ)重要性的指標(biāo)，可以視作特征詞的權(quán)重。Sparck Jones[18]在1972年首次提出了IDF概念，指出可以給每個(gè)特征詞賦予一個(gè)權(quán)重，而且在多個(gè)文檔中出現(xiàn)的特征詞權(quán)重應(yīng)小于在少量文檔中出現(xiàn)的特征詞權(quán)重。Salton等[19-21]進(jìn)而提出了TF-IDF的計(jì)算，闡述了TF-IDF的理論基礎(chǔ)以及在信息檢索方面的應(yīng)用。假設(shè)整個(gè)數(shù)據(jù)庫(kù)中文件的總數(shù)為M，所選用的特征詞總數(shù)為N，第j個(gè)特征詞在第i個(gè)文件中出現(xiàn)的頻率記為tfij，計(jì)算如下[19,20]：

tfij=nij/∑kniki=1…M,j=1…N

(1)

其中nij為特征詞j在該文件i中出現(xiàn)的次數(shù)。式(1)實(shí)際上是將特征詞頻數(shù)進(jìn)行歸一化。很顯然，在同一個(gè)文件中，詞頻高的特征詞比詞頻低的重要。然而，僅使用TF進(jìn)行信息檢索忽略了另一個(gè)問(wèn)題。有些特征詞高頻率出現(xiàn)在幾乎所有文件中，如一些通用的詞語(yǔ)，“應(yīng)用”，“基礎(chǔ)”，對(duì)分類不起什么作用。而另一些專業(yè)詞僅出現(xiàn)在少量相關(guān)文件中，則對(duì)文件分類有著重要作用。因此，應(yīng)該給每個(gè)特征詞賦予一個(gè)權(quán)重，逆文本頻率就相當(dāng)于這個(gè)作用，計(jì)算如下：

(2)

其中Mi表示數(shù)據(jù)庫(kù)中出現(xiàn)特征詞i的文件總數(shù)。很顯然，詞頻-逆文本頻率反映了兩方面:(a)在特定文件中高頻率出現(xiàn)的特征詞具有較強(qiáng)的分類能力；(b)特征詞的分布文件越廣，其分類能力越差。由于詞頻-逆文本頻率有效地刻畫了文件的特征，因此它在文本搜索、文獻(xiàn)分類等相關(guān)領(lǐng)域得到了廣泛應(yīng)用。在本文中，利用公式(1)與公式(2)的乘積構(gòu)造圖書的特征向量,即

Vij=tfij·idfi

(3)

2 構(gòu)造圖書相似性網(wǎng)絡(luò)

網(wǎng)絡(luò)是一種非線性結(jié)構(gòu)，由節(jié)點(diǎn)以及連接節(jié)點(diǎn)的之間的邊構(gòu)成。網(wǎng)絡(luò)，尤其是復(fù)雜網(wǎng)絡(luò)，是探索復(fù)雜系統(tǒng)(如生物系統(tǒng)，社區(qū)結(jié)構(gòu)等)的有效方法之一。本文以TF-IDF為圖書的特征向量，進(jìn)而構(gòu)建圖書相似性網(wǎng)絡(luò)。計(jì)算圖書之間的相似性：

(4)

其中Vi，Vj代表特定圖書的節(jié)點(diǎn)，i,j∈[1,M] i≠j。若d(xi,xj)<α，則連接兩節(jié)點(diǎn)；否則不連接兩節(jié)點(diǎn)。α是相似性度量臨界值。

3 CNM算法

CNM算法是Clause等人[17]提出的一種適合大規(guī)模網(wǎng)絡(luò)社區(qū)劃分方法。CNM算法采用了模塊度度量社區(qū)之間的緊密程度。模塊度是指社區(qū)內(nèi)部節(jié)點(diǎn)的邊所占總邊數(shù)比例與外部接入社區(qū)中的邊所占的比例差值，即

(5)

eii表示社區(qū)i中內(nèi)部邊所占的比例，ai表示接入該社區(qū)的邊所占總邊數(shù)的比例。模塊度的上限值為1。模塊度越大，說(shuō)明該網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)越明顯。因此模塊度常用于社區(qū)劃分效果的標(biāo)準(zhǔn)[22]。

CNM算法步驟如下[23]：

1)初始化

(6)

2)合并

選擇最大的分量Δqij，合并相應(yīng)的社區(qū)Ci和Cj，并標(biāo)記合并后的社區(qū)為Cj，同時(shí)更新Δqij和向量A。

(7)

更新向量A：

aj=ai+aj,ai=0

(8)

更新模塊度值

Q=Q+max{Δqij}

(9)

3)迭代

重復(fù)步驟2)，直至模塊度值不增終止算法，最終得到L個(gè)社區(qū)。

4 實(shí)驗(yàn)結(jié)果

本文采集了豆瓣讀書網(wǎng)(https://book.douban.com)上《信息簡(jiǎn)史》、《愛(ài)的藝術(shù)》、《百年孤獨(dú)》、《編程珠璣》、《從零開(kāi)始做運(yùn)維》、《二手時(shí)間》、《克魯蘇神話》、《魔戒》、《殺死一只知更鳥(niǎo)》、《神經(jīng)網(wǎng)絡(luò)與機(jī)器學(xué)習(xí)》、《小王子》一共11本圖書的信息，書名如表1所示。將“信息”、“編程”、“科學(xué)”、“互聯(lián)網(wǎng)”、“數(shù)據(jù)”、“程序”、“計(jì)算機(jī)”、“算法”、“哲理”、“思索”、“奇幻”、“小說(shuō)”、“經(jīng)典”、“文學(xué)”、“名著”一共15個(gè)詞作為TF-IDF方法中的特征詞。

表1 11本圖書的書名

相似度量臨界值α=2.5，得到最終的圖書劃分結(jié)果為

只要讀者用戶選擇類別中任何一本圖書，可將同類別的其它圖書推薦給讀者。例如讀者閱讀《信息簡(jiǎn)史》時(shí)，系統(tǒng)能夠?qū)ⅰ毒幊讨榄^》、《二手時(shí)間》和《神經(jīng)網(wǎng)絡(luò)與機(jī)器學(xué)習(xí)》推薦給用戶。

5 結(jié)論

本文以詞頻與逆文本頻率刻畫圖書，從而構(gòu)建圖書相似性網(wǎng)絡(luò)?；贑NM社區(qū)劃分算法實(shí)現(xiàn)圖書推薦。相比以前的圖書推薦算法，該算法從圖書的內(nèi)容出發(fā),能夠排除部分主觀因素的影響，并能較好的反映出圖書之間存在的客觀聯(lián)系。

[1]周玲元,段隆振.個(gè)性化圖書推薦系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)——以南昌航空大學(xué)圖書館為例[J].圖書館理論與實(shí)踐， 2014，(12):106-109.

[2]楊永權(quán).基于協(xié)同過(guò)濾技術(shù)的個(gè)性化圖書推薦系統(tǒng)研究[J].河南圖書館學(xué)刊，2014，(06):119-122.

[3]王連喜.一種面向高校圖書館的個(gè)性化圖書推薦系統(tǒng)[J].現(xiàn)代情報(bào)，2015,(12):41-46.

[4]孫守義,王蔚.一種基于用戶聚類的協(xié)同過(guò)濾個(gè)性化圖書推薦系統(tǒng)[J].現(xiàn)代情報(bào),2007,(11):139-142.

[5]付凱麗.基于社會(huì)化標(biāo)簽的圖書推薦系統(tǒng)模型研究[J].情報(bào)探索,2016,(10):80-85.

[6]陳宇亮,沈奎林.基于讀者評(píng)論的圖書推薦系統(tǒng)研究[J].圖書情報(bào)導(dǎo)刊,2016,(09):6-9.

[7]曾慶輝,邱玉輝.一種基于協(xié)作過(guò)濾的電子圖書推薦系統(tǒng)[J].計(jì)算機(jī)科學(xué),2005,(06):147-150.

[8]安德智,劉光明,章恒.基于協(xié)同過(guò)濾的圖書推薦模型[J].圖書情報(bào)工作,2011,(01):35-38.

[9]李克潮,梁正友.基于多特征的個(gè)性化圖書推薦算法[J].計(jì)算機(jī)工程,2012,(11):34-37.

[10]鄭祥云,陳志剛,黃瑞，等.基于主題模型的個(gè)性化圖書推薦算法[J].計(jì)算機(jī)應(yīng)用，2015，(09):2569-2573.

[11]李樹(shù)青,徐俠,許敏佳.基于讀者借閱二分網(wǎng)絡(luò)的圖書可推薦質(zhì)量測(cè)度方法及個(gè)性化圖書推薦服務(wù)[J].中國(guó)圖書館學(xué)報(bào)，2013，(03):83-95.

[12]董坤.基于協(xié)同過(guò)濾算法的高校圖書館圖書推薦系統(tǒng)研究[J].現(xiàn)代圖書情報(bào)技術(shù)，2011，(11):44-47.

[13]景民昌,于迎輝.基于借閱時(shí)間評(píng)分的協(xié)同圖書推薦模型與應(yīng)用[J].圖書情報(bào)工作，2012，(03):117-120.

[14]徐文青,雙林平.融合熱門度因子基于標(biāo)簽的個(gè)性化圖書推薦算法[J].圖書情報(bào)研究，2015，(03):82-86.

[15]林郎碟,王燦輝.Apriori算法在圖書推薦服務(wù)中的應(yīng)用與研究[J].計(jì)算機(jī)技術(shù)與發(fā)展，2011，(05):22-24，28.

[16]丁雪.基于數(shù)據(jù)挖掘的圖書智能推薦系統(tǒng)研究[J].情報(bào)理論與實(shí)踐，2010，(05):107-110.

[17]Clauset A,Newman ME,Moore C.Finding community structure in very large networks[J].Physical review E,2004,70(2):066111.

[18]Sparck Jones K.A statistical interpretation of term specificity and its application in retrieval[J].Journal of documentation,1972,28(1):11-21.

[19]Salton G,Yu CT.On the construction of effective vocabularies for information retrieval[J].Acm Sigplan Notices,1973,10(1):48-60.

[20]Salton G,Fox EA,Wu H.Extended Boolean information retrieval[J].Communications of the ACM,1983,26(11):1022-1036.

[21]Salton G,Buckley C.Term-weighting approaches in automatic text retrieval[J].Information processing & management,1988,24(5):513-523.

[22]韓華,王娟,王慧.改進(jìn)的CNM算法對(duì)加權(quán)網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)的劃分[J].計(jì)算機(jī)工程與應(yīng)用,2010,(35):86-89.

[23]張震,李玉峰,王晶，等.基于復(fù)雜網(wǎng)絡(luò)挖掘的用戶行為感知機(jī)制.中國(guó)科學(xué):信息科學(xué)，2014，(09):1069-1083.

A book recommendation algorithm based on term frequency-inverse document frequency and community partition

ZENG Siyan，ZHOU Jin，HUANG Guohua

(Department of Science and Information Science,Shaoyang University,Shaoyang 422000,China)

A book recommendation algorithm based on content was proposed.The method used the term frequency-inverse document frequency to represent the books eigenvector,computed similarities between books by the Euclidean distance,clustered books via the CNM algorithm,and finally obtained the classes of books.When users read or bought books,the method could recommend other books in the same category.It is helpful for users to read and buy books.

book recommendation; complex network; community finding;term frequency;inverse document frequency; cluster.

1672-7010(2017)02-0019-05

2017-02-18

國(guó)家自然科學(xué)基金資助項(xiàng)目(61672356);湖南省自然科學(xué)基金(2017JJ2239)；湖南省教育廳優(yōu)秀青年項(xiàng)目(15B216)

黃國(guó)華(1978-)，湖南祁東人，副教授，博士，從事生物信息學(xué)、生物醫(yī)藥大數(shù)據(jù)、機(jī)器學(xué)習(xí)等研究

TP391.1

A