申 丹

?

基于標(biāo)簽的推薦系統(tǒng)關(guān)聯(lián)算法研究

申 丹1、2

1.陜西省土地工程建設(shè)集團(tuán)有限責(zé)任公司，陜西 西安 710075 2.陜西地建土地工程技術(shù)研究院有限責(zé)任公司，陜西 西安 710075

推薦系統(tǒng)存在的目的就是幫助用戶快速發(fā)現(xiàn)所需信息，并結(jié)合用戶自身特點和興趣愛好，為用戶尋找高質(zhì)量高價值的資源，從而減少用戶接觸重復(fù)或無關(guān)信息帶來的不利影響，提升用戶體驗度。對基于標(biāo)簽的推薦系統(tǒng)進(jìn)行了深入了解，在傳統(tǒng)算法的基礎(chǔ)上引入關(guān)聯(lián)規(guī)則挖掘，并通過使用K-means聚類方法對標(biāo)簽集合分類來降低矩陣的數(shù)據(jù)稀疏度。通過發(fā)現(xiàn)海量用戶行為之間的隱含規(guī)律并作為推薦依據(jù)，提高推薦系統(tǒng)的準(zhǔn)確度和對結(jié)果集中項目類型的覆蓋率。

標(biāo)簽；個性化推薦；K-means聚類；關(guān)聯(lián)規(guī)則；協(xié)同過濾

引言

推薦系統(tǒng)存在的目的就是幫助用戶快速發(fā)現(xiàn)所需信息，并結(jié)合用戶自身特點和興趣愛好，為用戶尋找高質(zhì)量高價值的資源，從而減少用戶接觸重復(fù)或無關(guān)信息帶來的不利影響，提升用戶體驗度。大眾標(biāo)注法的引入帶來了推薦系統(tǒng)中對資源評價的另一種方式，標(biāo)簽簡便易用且利于傳播，它不僅能夠體現(xiàn)出資源的差異性也反映出了標(biāo)注者的行為特征與個人偏好。

1 推薦系統(tǒng)及相關(guān)技術(shù)

1.1 推薦系統(tǒng)基本理論

一直以來，推薦系統(tǒng)想要達(dá)到的理想狀態(tài)是為用戶創(chuàng)造一種具備人工智能因素的決策體系，目標(biāo)在于對廣義范圍使用者提供高效且便利的推薦[1]。對數(shù)據(jù)環(huán)境的良好適應(yīng)性和便捷訪問的特點大大增強(qiáng)了推薦的效果，通用情況會采用“三要素分割法”，即把推薦系統(tǒng)中的節(jié)點劃分為用戶、備選資源、使用的推薦邏輯方法（見圖1）。

1.2 系統(tǒng)建模技術(shù)

1.2.1 用戶建模技術(shù)

模型反映用戶的類別、喜好、特點，從而提供個性化服務(wù)[2]。整個建模的處理過程分為兩個步驟：（1）收集用戶信息，分析用戶行為；（2）系統(tǒng)建立模型，并根據(jù)用戶反應(yīng)做出預(yù)期處理。在這其中要解決的問題有：記錄用戶數(shù)據(jù)、提取用戶特征值、建立有效模型。

圖1 推薦系統(tǒng)通用模型

1.2.2 物品建模技術(shù)

物品特征的建模方法可以歸類為基于內(nèi)容和基于分類兩種。前者從物品本身的特征著手，最常使用的是加權(quán)關(guān)鍵詞矢量。這是統(tǒng)計學(xué)中用來分析文檔的方法，結(jié)果是得到文檔的特征向量。

1.3 推薦算法

推薦算法是推薦系統(tǒng)中的核心模塊。算法的效用會直接影響推薦的效率和質(zhì)量[3]。目前較為主流的推薦算法有協(xié)同過濾推薦算法、基于內(nèi)容推薦算法、基于知識推薦算法和混合推薦算法。這些算法連接User和Item的方式可以歸為3種（見圖2）。

圖2 三種推薦系統(tǒng)聯(lián)系User和Item的方式

2 標(biāo)簽中的關(guān)聯(lián)規(guī)則挖掘研究

假設(shè)得到k階頻繁項集S={s1，s2...，sk}。在該項集中隨意去掉一個元素就得到了k-1個非空子集，且這些子集全部也是頻繁項集。選取其中任意兩個子集對比后可以知道它們有（k-2）項是相同的，且并集是全集。例如，選擇{s1，s2，…sn-2，sn-1}和{s1，s2，…sn-2，sn}。此外，對一個k+1階頻繁項集，其k階頻繁項集的非空子集必然是頻繁項集。由此可得，任意k+1階頻繁項集，對應(yīng)的k階頻繁項集中必定存在至少兩個集合的并集與之相等。這樣，只要對k階頻繁項集找出只有最后一項不同的集合并使之合并，就可以得到全部k+1階頻繁項集。當(dāng)然，這時得到的項集不一定全部符合頻繁項集的條件，有干擾項，需要進(jìn)行“剪枝”[4]。重復(fù)此步驟，就得到了全部的k+1階頻繁項集。得到的頻繁項集包含所有可能的規(guī)則，只要使用遍歷法就能得到規(guī)整出來的關(guān)聯(lián)規(guī)則。從1開始，依次選擇直到k的元素作為結(jié)果，其余看作前件，在一定置信度的設(shè)立下就過濾掉低頻規(guī)則。這種做法范圍廣，不會出現(xiàn)漏缺，但是時間復(fù)雜度高。若存在頻繁項目g，那么通用規(guī)則表達(dá)式為（g-β）—>β。那么這條規(guī)則的置信度=g.count/(g-β).count。

根據(jù)置信度計算公式可以確定，頻繁項目集g.count是定值。如果該規(guī)則是強(qiáng)關(guān)聯(lián)規(guī)則，那么（g-βs）—>gs也是強(qiáng)關(guān)聯(lián)規(guī)則[5]。其中βs是β的子集，因為(g-β).count 必然大于(g-βs).count。對一個給定的頻繁項目集g，如果一條強(qiáng)關(guān)聯(lián)規(guī)則的后件為β，那么所有由β的非空子集組成后件的關(guān)聯(lián)規(guī)則也是強(qiáng)關(guān)聯(lián)規(guī)則。綜上所述，邏輯處理流程就可以描述為首先找到所有后件項數(shù)為n（n>=1）的強(qiáng)關(guān)聯(lián)規(guī)則，然后再生成后件項數(shù)為n+1的強(qiáng)關(guān)聯(lián)規(guī)則，依次類推，直至生成所有的強(qiáng)關(guān)聯(lián)規(guī)則。Apriori的核心算法偽代碼如下：

{L1= {large 1-itemsets};

Ck=apriori-gen(Lk-1);//新的候選集

for all transactions t∈D do begin

Ct=subset(Ck,t); //事務(wù)t中包含的候選集

for all candidates c? Ctdo

c.count++;

end

Lk={c∈Ck|c.count≥minsup}

end

Answer=∪kLk;}

最先得到的是頻繁項集L1，之后產(chǎn)生頻繁項集L2，當(dāng)且僅當(dāng)出現(xiàn)使Lr為空的值出現(xiàn)時算法終止[6]。這是一個循環(huán)算法，當(dāng)循環(huán)進(jìn)行到第k次時，得到k-（后件項數(shù)為k）項集的集合Ck，其中每一個項集等于兩個有且僅有一個項不同的Lk-1頻繁集進(jìn)行（k-2）-連接得到的。備選頻率集合出自于Ck中的項集，最后選中的頻集Lk是Ck的某子集，Lk的元素是將Ck中的每個元素在交易事務(wù)集和中加以驗證后才確定是否并入。

綜上所述，標(biāo)簽關(guān)聯(lián)規(guī)則挖掘的實現(xiàn)步驟如下：

步驟1：挖掘目標(biāo)用戶行為日志，清理標(biāo)簽，獲得高質(zhì)量的用戶標(biāo)簽初始集合TU。

步驟2：對每一個ti∈Tui，在其標(biāo)簽集上使用K-means聚類算法，將Tui劃分為由k個核心標(biāo)簽為代表的用戶個人標(biāo)簽集合Tui*。

步驟3：在Tui*上使用Apriori算法，獲得頻繁項集，由頻繁項集推導(dǎo)強(qiáng)關(guān)聯(lián)規(guī)則。

3 實驗評測

3.1 方案設(shè)計

本小結(jié)將通過實驗設(shè)計來檢測上文所提出的標(biāo)簽關(guān)聯(lián)規(guī)則挖掘方法以及規(guī)則的推薦結(jié)果。通過處理數(shù)據(jù)集形成用戶的標(biāo)簽集合，用Tui=｛t1，t2，t3，…tn｝表示用戶ui所使用過的標(biāo)簽集合[7]。通過尋找不同用戶標(biāo)簽集合的頻繁項集，找到“凡是偏好標(biāo)簽A和B的用戶，很有可能也會喜歡標(biāo)簽C”成立的規(guī)則模型。表1為五個用戶一次事務(wù)中的標(biāo)簽集合：

表1 用戶-標(biāo)簽列表

將一個用戶所對于Tui的有效標(biāo)簽子集，規(guī)則選項卡U，Tx→Ty用于提取稱之為UTmodel規(guī)則模型。其中U代表用戶集，Tx表示子集中的某標(biāo)簽，Ty代表同一個用戶標(biāo)簽子集中所包含的其他標(biāo)簽[8]。對于每一條UT模型可以按照如下公式來定義置信度conf和支持度supp：

由此會產(chǎn)生大量規(guī)則列表集合，對此設(shè)立如下的規(guī)則選擇機(jī)制，規(guī)則按照設(shè)立順序依次滿足：

條件1：規(guī)則滿足最低的支持度和可信度閾值；

條件2：選擇最大置信度的規(guī)則；

條件3：置信度相同時，選擇具有最大支持度的規(guī)則；

條件4：當(dāng)置信度與支持度相同時，選擇首次出現(xiàn)的規(guī)則。

按照上述步驟來處理表1中所展示的“用戶-標(biāo)簽”集，可以得到例如表2中的關(guān)聯(lián)規(guī)則：

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

3.2 測試結(jié)果及分析

實驗中使用的數(shù)據(jù)集采用數(shù)據(jù)堂提供的Delicious數(shù)據(jù)集。該數(shù)據(jù)集經(jīng)過簡單的預(yù)處理，包含用戶對標(biāo)簽的使用情況記錄，數(shù)據(jù)格式為 [USER_ID, URL_ID, Tags]。部分?jǐn)?shù)據(jù)集如表3所示：

表3 預(yù)處理數(shù)據(jù)集

表3所示是原始數(shù)據(jù)，經(jīng)過標(biāo)簽清洗后，可以得到形式規(guī)整并且質(zhì)量較高的數(shù)據(jù)集合，包括對大小寫的歸并，對缺省值的過濾和對錯誤輸入的剔除。USER_ID為104的用戶的原始記錄有170條數(shù)據(jù)，經(jīng)過標(biāo)簽清洗后有153條數(shù)據(jù)，之后對該用戶使用K-means聚類后如圖3所示：

圖3 用戶104標(biāo)簽聚類

進(jìn)行關(guān)聯(lián)規(guī)則挖掘，獲得關(guān)聯(lián)規(guī)則集合。表4展示了不同規(guī)則置信度和支持度的值，對于置信度小于60%的規(guī)則予以過濾。例如規(guī)則“104，blog→music”，只有55.71%的人對blog感興趣的同時對music感興趣，因此該條規(guī)則不會作為推薦依據(jù)。而對于規(guī)則“225，games→Apple”，其支持度高達(dá)87.04%，即喜歡games的人絕大多數(shù)都對Apple產(chǎn)品有較高的關(guān)注度，那么當(dāng)一個用戶檢索跟games有關(guān)的標(biāo)簽時，Apple就會作為推薦標(biāo)簽之一推送給用戶[9]。

表4 不同規(guī)則置信度和支持度的值

由此形成的推薦列表，通過準(zhǔn)確率和召回率進(jìn)行評測后結(jié)果如表5所示，結(jié)果表明該算法有較高的準(zhǔn)確率，并且推薦列表選擇為Top-5時的效果優(yōu)于Top-3[10]。

表5 通過準(zhǔn)確率和召回率進(jìn)行評測后的推薦列表

4 結(jié)束語

本文針對標(biāo)簽所具有的特性以及對用戶興趣的建模，主要從以下兩個方面進(jìn)行了深入研究：從數(shù)據(jù)層面解析用戶標(biāo)記過程，提取并處理用戶的歷史標(biāo)注行為。將用戶標(biāo)簽通過臟數(shù)據(jù)清理，聚類形成極具個性化的用戶標(biāo)簽社區(qū)。并將關(guān)聯(lián)規(guī)則引入標(biāo)簽系統(tǒng)中，利用數(shù)據(jù)挖掘技術(shù)讓隱含于標(biāo)簽集之間的聯(lián)系顯現(xiàn)出來。盡可能多的檢測頻繁項集，在大量數(shù)據(jù)中定義出可推理的關(guān)聯(lián)規(guī)則。將這種規(guī)則運用到推薦流程中，幫助優(yōu)化用戶體驗并提升算法效能。

[1]劉建國，周濤，汪秉宏.個性化系統(tǒng)研究進(jìn)展[J].自然學(xué)進(jìn)展，2009，19（1）：1-15.

[2]Ricci F，Rokach L，Shapira B. Introduction to Recommender Systems Handbook[J].Recommender Systems Handbook，2010：1-35.

[3]Chen H，Joshi A，F(xiàn)inin T. Dynamic Service Discovery for Mobile Computing: Intelligent Agents Meet Jini in the Aether[J].Cluster Computing，2001，4（4）：343-354.

[4]GANZHA V G，MAYR E W，VOROZHTSOV E V. Computer algebra in scientific computing: CASC 2000: proceedings of the Third Workshop on Computer Algebra in Scientific Computing, Samarkand, October 5-9, 2000[C]. Berlin: Springer, c2000.

[5]Schmidt B. Service to recommend opening an information object based on task similarity: US, doi:US20140019975 A1[P]. 2015.

[6]朱澤宇. 社會標(biāo)簽系統(tǒng)挖掘研究[J]. 江蘇科技信息，2015（23）：26-27.

[7]Adomavicius A，Tuzhilin Gediminas. Toward the Next Generation of Recommender Systems: A Survey of the State-of-the-Art and Possible Extensions[J]. IEEE Transactions on Knowledge & Data Engineering，2005，17（6）：734-749.

[8]Younghoon Kim，KyuseokShim. TWILITE：A recommendation system for Twitter using a probabilistic model based on latent Dirichlet allocation[J]. Information Systems，2013.

[9]王國霞，劉賀平. 個性化推薦系統(tǒng)綜述[J]. 計算機(jī)工程與應(yīng)用，2012（7）：66-76.

[10]A Zapata，V H Menéndez，M.E. Prieto，C Romero. A framework for recommendation in learning object repositories: An example of application in civil engineering[J]. Advances in Engineering Software，2013，56.

Research on Association Algorithm of Label Based Recommendation System

Shen Dan1,2

1. Shaanxi Provincial Land Engineering Construction Group Co., Ltd., Shaanxi Xi’an 710075 2. Institute of Land Engineering and Technology, Shaanxi Provincial Land Engineering Construction Group Co., Ltd., Shaanxi Xi’an 710075

The recommendation system’s purpose is to help users quickly find the required information, and combined with the user’s own characteristics and interests, find the resources of high quality and high value for the users, thereby reducing user contact of redundant or irrelevant information brings adverse effect, enhance the user experience. The paper makes a deep understanding of the recommendation system based on the tags, the association rules is introduced based on the traditional algorithm in mining, and through the collection of classification label using K-means clustering method to reduce the data sparseness matrix. Through the discovery of the hidden rules between the massive users’ behavior as the basis for recommendation, improve the accuracy of the recommendation system and the coverage of the project type.

Tag; K-means clustering; personalized recommendation; association rules; collaborative filtering

TP391.3

A

1009-6434（2017）9-0056-04

申丹（1989—），女，漢族，陜西漢中人，當(dāng)前職務(wù)為科研輔助，當(dāng)前職稱為初級工程師，碩士研究生學(xué)歷，研究方向為情報學(xué)。