基于Hadoop的社交網(wǎng)絡(luò)服務(wù)推薦算法

李 玲, 任 青, 付 園, 陳 鶴, 梅圣民

(吉林大學(xué) 通信工程學(xué)院, 長(zhǎng)春 130012)

0 引 言

文獻(xiàn)[1]對(duì)推薦問題進(jìn)行了如下描述： 用C表示所有用戶的集合,S表示所有可能被推薦項(xiàng)目的集合；u為一個(gè)效用函數(shù), 表示項(xiàng)目s對(duì)用戶c的有效性； 對(duì)于每個(gè)用戶c′∈C, 選擇一條項(xiàng)目s′∈S使用戶c′的效用函數(shù)最大。

根據(jù)推薦方式的不同, 將推薦系統(tǒng)分為3類： 1) 基于內(nèi)容的推薦(CBR: Content-Based Recommendation), 根據(jù)用戶的歷史使用記錄推測(cè)出此用戶的偏好, 并向該用戶推薦符合其偏好的項(xiàng)目； 2) 協(xié)同過濾推薦(CFR: Collaborative Filtering Recommendation), 推測(cè)出所有用戶的偏好, 具有相似偏好的用戶之間互為鄰居, 針對(duì)特定用戶, 根據(jù)其鄰居的使用情況向其推薦相應(yīng)的項(xiàng)目； 3) 混合推薦(HR: Hybrid Recommendation), 綜合使用上述兩種推薦方法。

基于內(nèi)容的推薦最先應(yīng)用于信息檢索與信息過濾領(lǐng)域, 主要對(duì)由文本信息組成的項(xiàng)目進(jìn)行推薦。推薦之前, 通常需要提取用戶和待推薦項(xiàng)目的關(guān)鍵詞, 以描述用戶的偏好和待推薦項(xiàng)目的特征。在推薦過程中, 通過計(jì)算用戶偏好和待推薦項(xiàng)目特征之間的相似度, 決定是否向該用戶推薦該項(xiàng)目。比較典型的有TF-IDF(Term Frequency-Inverse Document Frequency)算法[2]、 Rocchio算法[3]和貝葉斯分類算法[4]。

協(xié)同過濾推薦系統(tǒng)主要應(yīng)用于電子商務(wù)中, 其算法可分成基于記憶的和基于模型的兩大類[5]。其中基于記憶的算法根據(jù)用戶的歷史評(píng)分集合預(yù)測(cè)新的評(píng)分, 使用樸素貝葉斯或皮爾遜相關(guān)進(jìn)行計(jì)算。而基于模型的算法根據(jù)所使用的模型不同, 可分為BC(Bayesian Clustering)算法、 AM(Aspect Model)算法、 JMM(Joint Mixture Model)算法、 FMM(Flexible Mixture Model)算法和DM(Decoupled Models)算法等。

然而, 基于內(nèi)容的推薦不能為新用戶提供有效的推薦, 協(xié)同過濾推薦不能將新項(xiàng)目推薦給合適的用戶。為克服上述問題, 一些研究者將這兩種方法進(jìn)行整合形成了混合推薦。通過不同的方式整合會(huì)形成不同的混合推薦方法： 1) 獨(dú)立使用基于內(nèi)容的推薦和協(xié)同過濾推薦, 整合其預(yù)測(cè)結(jié)果[6]； 2) 將基于內(nèi)容的推薦加入到協(xié)同過濾推薦模型中, 如Fab系統(tǒng)和按內(nèi)容協(xié)作方式[7]； 3) 將協(xié)同過濾推薦加入基于內(nèi)容的推薦模型中； 4) 整合兩種方式, 構(gòu)建一個(gè)通用的統(tǒng)一模型[8]。

目前推薦系統(tǒng)多在單服務(wù)器上實(shí)現(xiàn), 系統(tǒng)的容錯(cuò)性和可擴(kuò)展性較差。筆者針對(duì)社交網(wǎng)絡(luò)設(shè)計(jì)了分布式推薦算法。該推薦算法在Hadoop云平臺(tái)上實(shí)現(xiàn), 具有更好的容錯(cuò)性和可擴(kuò)展性。

1 基于Hadoop的社交網(wǎng)絡(luò)服務(wù)推薦系統(tǒng)框架

在云計(jì)算平臺(tái)上實(shí)現(xiàn)社交網(wǎng)絡(luò)服務(wù)推薦系統(tǒng), 可解決超大規(guī)模數(shù)據(jù)集的存儲(chǔ)問題, 可處理難題, 并能保證系統(tǒng)的可擴(kuò)展性。國(guó)際上已有一些學(xué)者在云計(jì)算平臺(tái)上進(jìn)行社交網(wǎng)絡(luò)相關(guān)的研究, 其中文獻(xiàn)[9-11]在MapReduce上進(jìn)行社交網(wǎng)絡(luò)數(shù)據(jù)分析, 文獻(xiàn)[12]在Hadoop平臺(tái)上實(shí)現(xiàn)了基于用戶的協(xié)同過濾推薦算法。借鑒以上的研究基礎(chǔ), 筆者在開源云平臺(tái)Hadoop上進(jìn)行社交網(wǎng)絡(luò)服務(wù)推薦的研究, 其系統(tǒng)框架如圖1所示。該系統(tǒng)主要包括數(shù)據(jù)采集模塊、 數(shù)據(jù)預(yù)處理模塊、 數(shù)據(jù)存儲(chǔ)模塊和服務(wù)推薦模塊。

圖1 基于Hadoop的社交網(wǎng)絡(luò)服務(wù)推薦系統(tǒng)

1.1 數(shù)據(jù)采集模塊

筆者采用新浪微博API(Application Programming Interface)采集用戶數(shù)據(jù), 客戶端需要下載SDK(Software Development Kit)包進(jìn)行開發(fā)。之后, 客戶端通過HTTP(Hypertext Transfer Protocol)協(xié)議與新浪微博服務(wù)器進(jìn)行數(shù)據(jù)交互。

1.2 數(shù)據(jù)預(yù)處理模塊

采集到用戶的微博信息后, 需要對(duì)微博進(jìn)行中文切分詞的處理, 筆者中分詞系統(tǒng)的設(shè)計(jì)原則如下：

1) 具備較強(qiáng)的學(xué)習(xí)能力, 能進(jìn)行擴(kuò)展訓(xùn)練, 便于新詞的識(shí)別；

2) 響應(yīng)速度快, 不能讓用戶感到不可忍受的延時(shí)；

3) 易于擴(kuò)展升級(jí), 便于提升分詞能力。

基于以上幾點(diǎn), 筆者選擇了復(fù)旦大學(xué)中文自然語言平臺(tái)FudanNLP[13]。FudanNLP除了具有分詞功能外, 可進(jìn)行詞性標(biāo)注, 還實(shí)現(xiàn)了基于TextRank算法的關(guān)鍵詞提取程序。由于微博中的關(guān)鍵詞多為名詞和動(dòng)詞, 筆者對(duì)經(jīng)過分詞的結(jié)果進(jìn)行詞性標(biāo)注, 提取名詞和動(dòng)詞。為驗(yàn)證筆者的分布式TF-IDF算法的有效性, 筆者利用FudanNLP中TextRank算法提取關(guān)鍵詞, 并與分布式TF-IDF算法的結(jié)果進(jìn)行對(duì)比。

1.3 數(shù)據(jù)存儲(chǔ)模塊

由于用戶頻繁更新微博, 導(dǎo)致新浪微博的用戶數(shù)據(jù)量非常大[14], 為實(shí)現(xiàn)可靠的、 可擴(kuò)展的存儲(chǔ), 筆者在HBase分布式數(shù)據(jù)庫(kù)中創(chuàng)建weiboTable表, 用于存儲(chǔ)經(jīng)過預(yù)處理的用戶數(shù)據(jù)。

為獲取更多微博數(shù)據(jù), 在實(shí)驗(yàn)過程中反復(fù)進(jìn)行微博數(shù)據(jù)的抓取。由于HBase數(shù)據(jù)庫(kù)以追加的方式寫入數(shù)據(jù), 用時(shí)間戳表示數(shù)據(jù)的不同版本, 因此, 可保證新的數(shù)據(jù)不會(huì)覆蓋舊的數(shù)據(jù)。

1.4 服務(wù)推薦模塊

筆者在MapReduce模型上實(shí)現(xiàn)分布式TF-IDF算法, 利用該算法統(tǒng)計(jì)微博中每個(gè)詞的重要性, 提取微博中的關(guān)鍵詞, 并根據(jù)這些關(guān)鍵詞進(jìn)行相應(yīng)的推薦。

TF-IDF采用統(tǒng)計(jì)方法評(píng)估某一詞語在某個(gè)文件中的重要性。詞頻TF是指某個(gè)詞語在某文件中出現(xiàn)的頻率； 逆向文件頻率IDF指某個(gè)詞語在所有文件中的普遍重要性, 它可由文件總數(shù)目除以包含該詞語的文件數(shù)目再取對(duì)數(shù)得到。TF-IDF的主要思想是： 代表某一文件屬性的詞語必須具有很高的辨識(shí)度, 即這些詞語在本文件中出現(xiàn)的頻率很高, 而在其他文件中則很少出現(xiàn)。

在TF-IDF方法中, 假設(shè)N是文檔總數(shù)量, 關(guān)鍵詞ki在ni個(gè)文檔中出現(xiàn),fi,j是關(guān)鍵詞ki在文檔dj中出現(xiàn)的次數(shù), 則關(guān)鍵詞ki在文檔dj中出現(xiàn)的頻率

(1)

關(guān)鍵詞ki的Ii計(jì)算如下

(2)

文檔dj中關(guān)鍵詞ki的重要性通過TF-IDF權(quán)重wij定義,wij的計(jì)算方法如下

wi,j=Ti,j×Ii

(3)

2 TF-IDF算法MapReduce化

圖注： offset： 行偏移量; content： 每行中的內(nèi)容; filename： 文件名; word： 詞語; CiNum： filename中所有詞出現(xiàn)的次數(shù)之和; TF： word在filename中出現(xiàn)的頻率; IDF： word的逆向文件頻率; TF-IDF： word的TF_IDF權(quán)重。

在MapReduce模型中, 一個(gè)任務(wù)的執(zhí)行可分為Map和Reduce兩個(gè)過程。即執(zhí)行一個(gè)任務(wù)時(shí), 需要開發(fā)者實(shí)現(xiàn)Map和Reduce兩個(gè)函數(shù)。由于Map和Reduce函數(shù)的輸入輸出數(shù)據(jù)均為〈key, value〉對(duì)的形式, 因此需要對(duì)TF-IDF算法進(jìn)行MapReduce化的設(shè)計(jì)。筆者將TF-IDF算法分解成4個(gè)任務(wù)順序執(zhí)行(見圖2), 4個(gè)任務(wù)主要完成的工作如下所述。

Job1： 以/input目錄下的所有文件作為輸入, 統(tǒng)計(jì)每個(gè)文件中所有詞語出現(xiàn)的次數(shù)之和。

Job2： 以Job1的輸出文件作為輸入, 統(tǒng)計(jì)每個(gè)文件中每個(gè)詞語出現(xiàn)的次數(shù), 用某一詞語出現(xiàn)的次數(shù)除以該文件中所有詞語出現(xiàn)的次數(shù)之和, 得到該詞語在該文件中出現(xiàn)的頻率TF。

Job3： 以Job2的輸出文件作為輸入, 計(jì)算每個(gè)文件中每個(gè)詞語的IDF和TF-IDF。

Job4： 以Job3的輸出文件作為輸入, 將Job3的輸出結(jié)果按TF-IDF從大到小的順序進(jìn)行排序。

3 分布式TF-IDF算法與TextRank算法的對(duì)比

3.1 準(zhǔn)確性對(duì)比

為驗(yàn)證筆者的分布式TF-IDF算法的準(zhǔn)確性和有效性, 用FudanNLP對(duì)微博進(jìn)行關(guān)鍵詞提取, 作為對(duì)比, FudanNLP中使用的關(guān)鍵詞提取算法為TextRank算法。筆者從Job4的輸出結(jié)果中提取TF-IDF最大的前N個(gè)詞語, 作為某一用戶的關(guān)鍵詞； 同時(shí)用FudanNLP中的Extractor類提取N個(gè)關(guān)鍵詞作為對(duì)比。實(shí)驗(yàn)中將N分別選取為5、10、15, 具體的實(shí)驗(yàn)結(jié)果如圖3～圖5所示。其中 “〈〉”中的內(nèi)容為微博的用戶名, 后面的詞語為微博中的關(guān)鍵詞, 數(shù)字表示該關(guān)鍵詞的權(quán)重。

a 分布式TF-IDF算法 b TextRank算法

a 分布式TF-IDF算法 b TextRank算法

a 分布式TF-IDF算法 b TextRank算法

由圖3～圖5可看出, 筆者的分布式TF-IDF算法和TextRank算法提取的關(guān)鍵詞比較接近, 并且隨著關(guān)鍵詞數(shù)目的增加, 二者的結(jié)果變得更加接近。對(duì)比證明, 基于MapReduce的分布式TF-IDF算法是準(zhǔn)確的、 有效的。兩種算法提取關(guān)鍵詞的結(jié)果稍有不同, 主要表現(xiàn)為關(guān)鍵詞的排序不同, 這是由于算法的本質(zhì)不同所造成的。分布式TF-IDF將在筆者文檔中出現(xiàn)次數(shù)多而在其他文檔較少出現(xiàn)的詞賦予較高的權(quán)重, 即用辨識(shí)度比較高的關(guān)鍵詞描述文檔的特性； 而TextRank算法只考慮詞語在筆者文檔中的重要性, 不考慮詞語在其他文檔中的情況。通過理論分析和實(shí)踐證明, 采用筆者的分布式TF-IDF算法提取的關(guān)鍵詞更能表征用戶的個(gè)性。

3.2 可擴(kuò)展性對(duì)比

為論證基于Hadoop的分布式TF-IDF算法具有較強(qiáng)的可擴(kuò)展性, 筆者用TextRank算法作為對(duì)比, 通過實(shí)驗(yàn)觀察兩種算法處理不同大小文檔時(shí)的響應(yīng)時(shí)間。實(shí)驗(yàn)中, 筆者選取了10種不同大小的文檔集合, 針對(duì)每個(gè)文檔集合分別做5次實(shí)驗(yàn)。在5次實(shí)驗(yàn)結(jié)果中, 去掉最長(zhǎng)和最短的響應(yīng)時(shí)間, 余下的結(jié)果求平均值, 最后得出的平均響應(yīng)時(shí)間如圖6所示。

圖6 分布式TF-IDF算法和TextRank算法的響應(yīng)時(shí)間

由圖6可看出, 隨著文件大小的增加, 兩種算法的響應(yīng)時(shí)間均增加, 但分布式TF-IDF算法的增加明顯低于TextRank算法。當(dāng)文件小于0.8 MByte時(shí), 由于Hadoop集群中節(jié)點(diǎn)之間的通信需要花費(fèi)一定時(shí)間, 所以分布式TF-IDF算法的響應(yīng)時(shí)間長(zhǎng)于TextRank算法； 當(dāng)文件達(dá)到0.8 MByte時(shí), 兩者的響應(yīng)時(shí)間幾乎相當(dāng)； 隨著文件大小繼續(xù)增加, 分布式TF-IDF算法的響應(yīng)時(shí)間緩慢增加, 而TextRank算法的響應(yīng)時(shí)間急速增加。由此可見, 分布式TF-IDF算法具有良好的可擴(kuò)展性, 適合處理大型數(shù)據(jù)。

4 結(jié) 語

為處理社交網(wǎng)絡(luò)中的海量用戶數(shù)據(jù), 發(fā)現(xiàn)用戶的興趣, 并據(jù)此為用戶推薦個(gè)性化的服務(wù), 筆者設(shè)計(jì)了一種基于Hadoop的社交網(wǎng)絡(luò)服務(wù)推薦系統(tǒng), 并在MapReduce模型上實(shí)現(xiàn)了分布式的TF-IDF算法。為了驗(yàn)證筆者中分布式TF-IDF算法的有效性, 用TextRank算法對(duì)微博進(jìn)行關(guān)鍵詞提取以作為對(duì)比。結(jié)果表明, 兩種算法提取出的關(guān)鍵詞比較接近, 并且隨著關(guān)鍵詞數(shù)目的增加, 二者的結(jié)果變得更加接近, 充分證明了分布式TF-IDF算法是準(zhǔn)確、 有效的。同時(shí), 由于分布式TF-IDF算法考慮到了關(guān)鍵詞的辨識(shí)度問題, 它在提取微博關(guān)鍵詞時(shí), 較TextRank算法表現(xiàn)更優(yōu)。此外, 通過與TextRank算法進(jìn)行響應(yīng)時(shí)間的對(duì)比, 可看出, 分布式TF-IDF算法具有良好的可擴(kuò)展性。

參考文獻(xiàn)：

[1]GEDIMINAS A, ALEXANDER T. Toward the Next Generation of Recommender Systems: A Survey of the State-of-the-Art and Possible Extensions [J]. IEEE Transactions on Knowledge and Data Engineering, 2005, 17(6): 734-749.

[2]WANG Na, WANG Peng-yuan, ZHANG Bao-wei. An Improved TF-IDF Weights Function Based on Information Theory [C]∥Proceedings of the International Conference on Computer and Communication Technologies in Agriculture Engineering(CCTAE). Chengdu, China: [s.n.], 2010: 439-441.

[3]AGO Guan-yu, GAUN Sheng-xiao. Text Categorization Based on Improved Rocchio Algorithm [C]∥Proceedings of the International Conference on Systems and Informatics. Yantai, China: [s.n.], 2012: 2247-2250.

[4]HE You-quan, XIE Jian-fang, XU Cheng. An Improved Naive Bayesian Algorithm for Web Page Text Classification [C]∥Proceedings of the Eighth International Conference on Fuzzy Systems and Knowledge Discovery(FSKD). Shanghai, China: [s.n.], 2011: 1765-1768.

[5]LIN Kun-hui, ZHANG Lei-lei, DENG Xiang. Optimized Collaborative Filtering Algorithm Based on Item Rating Prediction [C]∥Proceedings of the Second International Conference on Instrumentation, Measurement, Computer, Communication and Control(IMCCC). Harbin, China: [s.n.], 2012: 648-652.

[6]BILLSUS D, PAZZANI M. User Modeling for Adaptive News Access [J]. User Modeling and User-Adapted Interaction, 2000, 10(2/3): 147-180.

[7]PAZZANI M, BILLSUS D. Learning and Revising User Profiles: The Identification of Interesting Web Sites [J]. Machine Learning, 1997, 27(3): 313-331.

[8]SCHUBIGER S, HIRSBRUNNER B. A Model for Software Configuration in Ubiquitous Computing Environments [C]∥Proceedings of the First International Conference on Pervasive Computing. Zurich, Switzerland: [s.n.], 2002: 181-194.

[9]HYEOKJU LEE, JOON HER, SUNG-RYUL KIM. Implementation of a Large-Scalable Social Data Analysis System Based on MapReduce[C]∥Proceedings of the First ACIS/JNU International Conference on Computers, Networks, Systems, and Industrial Engineering. Jeju Island, Korea: [s.n.], 2011: 228-233.

[10]LIU Guo-jun, HANG Ming, YAN Fei. Large-Scale Social Network Analysis Based on MapReduce [C]∥Proceedings of the International Conference on Computational Aspects of Social Networks. Taiyuan, China: [s.n.], 2010: 487-490.

[11]KAI Shuang, YIN Yang, BIN Cai, et al. X-RIME: Hadoop-Based Large-Scale Social Network Analysis [C]∥Proceedings of the 3rd IEEE International Conference on Broadband Network and Multimedia Technology(IC-BNMT). Beijing, China: [s.n.], 2010: 901-906.

[12]ZHAO Zhi-dan, SHANG Ming-sheng. User-Based Collaborative-Filtering Recommendation Algorithms on Hadoop [C]∥Proceedings of the Third International Conference on Knowledge Discovery and Data Mining. Phuket, Thailand: [s.n.], 2010: 478-481.

[13]NORMASLINA JAMIL, ARIFAH CHE ALHADI, SHAHRUL AZMAN NOAH. A Collaborative Names Recommendation in the Twitter Environment Based on Location [C]∥Proceedings of the International Conference on Semantic Technology and Information Retrieval. Putrajaya, Malaysia: [s.n.], 2011: 119-124.

[14]XIA Tian, CHAI Yan-mei. An Improvement to TF-IDF: Term Distribution Based Term Weight Algorithm [J]. Journal of Software, 2011, 6(3): 413-420.