個(gè)性化課程推薦中LFM自動(dòng)聚類算法研究

楊立力

個(gè)性化課程推薦中LFM自動(dòng)聚類算法研究

楊立力

為給學(xué)生推薦不同興趣粒度的課程，提出隱含語義模型（Latent Factor Model，以下簡(jiǎn)稱LFM），并將其應(yīng)用于網(wǎng)絡(luò)環(huán)境中學(xué)生對(duì)于課程學(xué)習(xí)點(diǎn)擊的隱性反饋數(shù)據(jù)集，對(duì)學(xué)生的興趣主題、行為習(xí)慣和課程類別自動(dòng)聚類，然后進(jìn)行Top-N推薦。實(shí)驗(yàn)表明，該方法是有效的，且具有較高的準(zhǔn)確度。

LFM隱含語義模型；個(gè)性化；推薦系統(tǒng)

0 引言

隨著計(jì)算機(jī)技術(shù)和互聯(lián)網(wǎng)技術(shù)的快速發(fā)展，網(wǎng)絡(luò)中的信息“超載”現(xiàn)象越來越嚴(yán)重，面對(duì)信息的“海洋”，用戶所用的信息只是滄海一粟。為了找到適合自己的信息用戶需要耗費(fèi)大量的時(shí)間與精力。在網(wǎng)絡(luò)教育中也存在此問題，學(xué)習(xí)者無法快速找到需要的學(xué)習(xí)資源，面對(duì)海量信息，無法進(jìn)行篩選。大量相似的信息使學(xué)習(xí)者在查找有效資源的過程中，產(chǎn)生“迷航”和迷茫不知所措的問題。因此在網(wǎng)絡(luò)教育中需要運(yùn)用個(gè)性化推薦技術(shù)來更好地輔助學(xué)習(xí)者的自主學(xué)習(xí)。

當(dāng)前實(shí)現(xiàn)個(gè)性化推薦應(yīng)用最廣泛的是基于用戶或者基于項(xiàng)目的協(xié)同過濾方法。然而在傳統(tǒng)的基于協(xié)同過濾方法中，主要通過尋找相似用戶或項(xiàng)目進(jìn)行推薦，無法照顧到項(xiàng)目的不同粒度。比如，對(duì)于一個(gè)用戶，他們可能有不同的興趣，就以網(wǎng)絡(luò)課程目錄為例，用戶 A會(huì)關(guān)注數(shù)學(xué)、歷史、計(jì)算機(jī)方面的課程，用戶B喜歡機(jī)器學(xué)習(xí)、編程語言、離散數(shù)學(xué)方面的課程，用戶 C喜歡大師 Sigmund Freud，Jean Piaget等人的課程，這樣在推薦的時(shí)候需要面向用戶推薦其個(gè)人感興趣的類別課程。推薦前提是要對(duì)所有item（目錄）進(jìn)行分類。由于分類雖然有統(tǒng)一標(biāo)準(zhǔn)，但其類型依然會(huì)受主觀因素影響，如對(duì)于B，他喜歡的3個(gè)類別都可以算作是計(jì)算機(jī)方面的課程，也就是說B的分類粒度要比A小。而對(duì)于離散數(shù)學(xué)，他既可以類屬于數(shù)學(xué)，也可類屬于計(jì)算機(jī)，也就是說有些 item不能簡(jiǎn)單的將其劃歸到確定的單一類別，即對(duì)于課程前期分類時(shí)應(yīng)進(jìn)行多維類別劃分。

目前，主要的推薦方法有基于內(nèi)容推薦、協(xié)同過濾推薦、基于關(guān)聯(lián)規(guī)則推薦、基于效用推薦、基于知識(shí)推薦和組合推薦。此處介紹個(gè)性化課程推薦平臺(tái)中LFM自動(dòng)聚類算法，它能夠基于用戶的行為對(duì)item進(jìn)行自動(dòng)聚類，也就是把item劃分到不同類別/主題，這些主題/類別可以理解為用戶的興趣。

1 基于LFM自動(dòng)聚類算法的推薦方法

基于聚類分析推薦是利用聚類分析技術(shù)按相似性原則將用戶劃分到不同簇中，然后再根據(jù)同一簇中的用戶評(píng)價(jià)信息對(duì)目標(biāo)用戶進(jìn)行協(xié)同推薦。采用LFM算法根據(jù)用戶的行為產(chǎn)生隱性的反饋，自動(dòng)聚類出各個(gè)用戶的興趣類與條目隱類。由于聚類過程可以離線進(jìn)行，因此聚類過程不影響推薦系統(tǒng)的響應(yīng)速度。

本方法可以解決如下幾個(gè)問題：（1）如何給對(duì)象分類。（2）如何確定用戶感興趣對(duì)象的類型，以及感興趣的程度。（3）對(duì)于一個(gè)給定的類別，選擇哪些屬于這個(gè)類的對(duì)象推薦給用戶，以及如何確定這些對(duì)象在一個(gè)類別中的權(quán)重。

1.1 數(shù)據(jù)收集與預(yù)處理

對(duì)象（各個(gè)推薦系統(tǒng)中具體指代不同）入庫(kù)的時(shí)候，系統(tǒng)會(huì)自動(dòng)為該對(duì)象分配一個(gè)惟一的對(duì)象號(hào)(也稱對(duì)象的ID或者標(biāo)識(shí))。當(dāng)用戶登錄后，系統(tǒng)會(huì)自動(dòng)把用戶與對(duì)象的交互情況記錄下來，系統(tǒng)記錄的是該用戶的用戶號(hào)、與其交互對(duì)象號(hào)以及此次交互的方式。交互行為如下表1所示：

表1 用戶行為分析

在信息獲取階段，各種交互方式分別用不同的數(shù)字來表示，其中數(shù)字0表示用戶點(diǎn)擊了該對(duì)象，數(shù)字1表示瀏覽了該對(duì)象，數(shù)字3表示用戶評(píng)論了該對(duì)象，數(shù)字4表示用戶收藏了該對(duì)象，數(shù)字5表示發(fā)布了該對(duì)象，同時(shí)不同的交互方式也代表了用戶對(duì)該對(duì)象的不同喜好程度，按照點(diǎn)擊、瀏覽、評(píng)論、收藏、發(fā)布的順序，用戶對(duì)該對(duì)象的喜好程度逐漸增強(qiáng)。

用戶對(duì)瀏覽對(duì)象的評(píng)價(jià)可以是顯式的也可以是隱式的。顯式的評(píng)價(jià)通常是用戶以數(shù)值形式對(duì)項(xiàng)目進(jìn)行評(píng)分，如果數(shù)值很高，表示用戶非常喜歡該對(duì)象，反之表示用戶不喜歡該對(duì)象。這種方式需要專門的進(jìn)行問卷調(diào)查。如果用戶希望獲得推薦系統(tǒng)的幫助，首先需要向系統(tǒng)提交他對(duì)一些對(duì)象的評(píng)價(jià)信息。隱式的評(píng)價(jià)是從數(shù)據(jù)資源中派生出來的，分析用戶在各個(gè)網(wǎng)頁(yè)的瀏覽時(shí)間、分析網(wǎng)站的日志文件、或分析用戶的定制記錄，通過分析這些隱式偏好信息，可以最終將這些信息映射為顯式評(píng)價(jià)信息。無論是顯式評(píng)價(jià)信息還是隱式評(píng)價(jià)信息，最終都可以映射為一張?jiān)u價(jià)記錄表，表2是這種表格的一個(gè)簡(jiǎn)化的示例如表2所示：

表2 用戶對(duì)對(duì)象的評(píng)價(jià)信息表

表2中的數(shù)值代表用戶給對(duì)象的評(píng)分?jǐn)?shù)值，數(shù)值越高，表示客戶越喜歡該對(duì)象。從表2中，會(huì)發(fā)現(xiàn)用戶E與用戶A的學(xué)習(xí)偏好基本是一致的，因此，可以判斷出用戶E也會(huì)喜歡對(duì)象5。

采集樣本時(shí)遵循以下原則:（1）對(duì)于每個(gè)用戶，要保證正負(fù)樣本的平衡。（2）對(duì)于每個(gè)用戶采樣負(fù)樣本時(shí)，選取那些很熱門，而用戶卻沒有行為的對(duì)象。根據(jù)用戶行為不同，標(biāo)記行為的權(quán)重為w，則給對(duì)象i的興趣度標(biāo)記為Rui=w；對(duì)于展示給用戶u的對(duì)象i，當(dāng)用戶沒有發(fā)生過行為，就定義(u,i)為負(fù)樣本，Rui=0。

負(fù)樣本采樣算法：

def RandomSelectNegativeSample(self, items):

ret = dict()

for i in items.keys():

ret[i] = 1

n = 0

for i in range(0, len(items) * 3)

item = items_pool[random.randint(0, len(items_pool) -1)]

if item in ret:

continue

ret[item] = 0

n + = 1

if n ＞ len(items):

break

return ret ifn＞len(items):

break

returnret

在上面的偽代碼中，items_pool維護(hù)了候選對(duì)象的列表，在這個(gè)列表中，對(duì)象i出現(xiàn)的次數(shù)和對(duì)象i的流行度成正比。items是一個(gè) dict，它維護(hù)了用戶已經(jīng)有過行為的對(duì)象的集合。

1.2 用戶興趣和對(duì)象隱類自動(dòng)聚類

在可見的用戶對(duì)象中歸結(jié)出3個(gè)類別，不等于該用戶就只喜歡這3類，對(duì)其他類別的對(duì)象就一點(diǎn)興趣也沒有。也就是說，需要了解用戶對(duì)于所有類別的興趣度。對(duì)于一個(gè)給定的類來說，需要確定這個(gè)類中每個(gè)對(duì)象屬于該類別的權(quán)重。權(quán)重有助于確定推薦哪些對(duì)象給用戶。對(duì)于一個(gè)給定的用戶行為數(shù)據(jù)集（數(shù)據(jù)集包含的是所有的user，所有的item，以及每個(gè)user有過行為的item列表），使用LFM對(duì)其建模后，可以得到如圖1所示的模型：（假設(shè)數(shù)據(jù)集中有3個(gè)user,4個(gè)item,LFM建模的分類數(shù)為4）

圖 1 LFM隱類模型

R矩陣是user-item矩陣，矩陣值Rij表示的是user i對(duì)item j的興趣度，這正是要求的值。對(duì)于一個(gè)user來說，當(dāng)計(jì)算出他對(duì)所有 item的興趣度后，就可以進(jìn)行排序并作出推薦。LFM算法從數(shù)據(jù)集中抽取出若干主題，作為user和item之間連接的橋梁，將R矩陣表示為P矩陣和Q矩陣相乘。其中P矩陣是user-class矩陣，矩陣值Pij表示的是user i對(duì)class j的興趣度；Q矩陣式class-item矩陣，矩陣值Qij表示的是item j在class i中的權(quán)重，權(quán)重越高越能作為該類的代表。所以LFM根據(jù)如下公式來計(jì)算用戶u對(duì)對(duì)象i的興趣度：

接下去的問題就是如何計(jì)算矩陣p和矩陣q中參數(shù)值。本方法采用最優(yōu)化損失函數(shù)來求參數(shù)。經(jīng)過采樣之后原有的數(shù)據(jù)集得到擴(kuò)充，得到一個(gè)新的user-item集K={U,I)}，其中如果(U,I)是正樣本，則RUI=1，否則RUI=0。因此，興趣的取值范圍為[0,1]。損失函數(shù)如下所示：

迭代計(jì)算不斷優(yōu)化參數(shù)（迭代次數(shù)事先人為設(shè)置），直到參數(shù)收斂。

其中，α是學(xué)習(xí)速率，α越大，迭代下降的越快。α和λ一樣，也需要根據(jù)實(shí)際的應(yīng)用場(chǎng)景反復(fù)實(shí)驗(yàn)得到。

綜上所述，執(zhí)行LFM需要，根據(jù)數(shù)據(jù)集初始化P和Q矩陣。

確定4個(gè)參數(shù)：分類數(shù)F，迭代次數(shù)N，學(xué)習(xí)速率α，正則化參數(shù)λ。

LFM的偽代碼如下：

def LFM(user_items, F, N, alpha, lambda):

#初始化P,Q矩陣

[P, Q] = InitModel(user_items, F)

#開始迭代

For step in range(0, N):

#從數(shù)據(jù)集中依次取出user以及該user喜歡的iterms集

for user, items in user_item.iterms():

#隨機(jī)抽樣，為user抽取與items數(shù)量相當(dāng)?shù)呢?fù)樣本，并將正負(fù)樣本合并，用 于優(yōu)化計(jì)算

samples = RandSelectNegativeSamples(items)

#依次獲取item和user對(duì)該item的興趣度

for item, rui in samples.items():

#根據(jù)當(dāng)前參數(shù)計(jì)算誤差

eui = eui - Predict(user, item)

#優(yōu)化參數(shù)

for f in range(0, F):

P[user][f] += alpha * (eui * Q[f][item] - lambda * P[user][f])

Q[f][item] += alpha * (eui * P[user][f] - lambda * Q[f][item])

#每次迭代完后，都要降低學(xué)習(xí)速率。一開始的時(shí)候由于離最優(yōu)值相差甚遠(yuǎn)，因此快速下降；

#當(dāng)優(yōu)化到一定程度后，就需要放慢學(xué)習(xí)速率，慢慢的接近最優(yōu)值。

alpha *= 0.9

通過以上算法訓(xùn)練，得到表示用戶興趣課程偏好向量P以及課程隱類向量Q。

1.3 計(jì)算生成推薦結(jié)果

對(duì)于收集的顯性評(píng)價(jià)，找到和目標(biāo)用戶有類似評(píng)價(jià)的用戶集合即興趣相似的用戶，找到這個(gè)集合中的用戶喜歡的，且目標(biāo)用戶沒查詢到的對(duì)象，推薦生成初始推薦列表推薦給目標(biāo)用戶。給定用戶u和用戶v，令N(u)表示用戶u曾經(jīng)有過正反饋的對(duì)象集合。那么，可以通過余弦相似度公式計(jì)算u和v的興趣相似度：

然后提取用戶的行為日志記錄進(jìn)行樣本采集計(jì)算得到用戶的興趣偏好向量P與對(duì)象隱類向量Q，通過公式（1）計(jì)算出精確的推薦結(jié)果并與初始列表進(jìn)行合并刪除列表中已經(jīng)存在的對(duì)象，按照對(duì)象的類別進(jìn)行分組并在每組中按照權(quán)值的大小進(jìn)行排序，然后選擇Top-N寫入最終推薦列表并推送到前臺(tái)UI界面。

2 實(shí)驗(yàn)

為驗(yàn)證算法的有效性，選用 CourseLens數(shù)據(jù)集，使用LFM計(jì)算出用興趣向量p和課程向量q，然后對(duì)于每個(gè)隱類找出權(quán)重最大的課程。如表3所示：

表3 CourseLens數(shù)據(jù)集中根據(jù)LFM計(jì)算出的不同隱類中權(quán)重最高的課程

表中展示了4個(gè)隱類中排名最高（qik最大）的一些課程。結(jié)果表明，每一類的課程都是合理的，都代表了一類用戶喜歡的課程。從而說明LFM確實(shí)可以實(shí)現(xiàn)通過用戶行為將課程聚類的功能。

其次，通過實(shí)驗(yàn)對(duì)比了 LFM、UserCF（基于用戶的協(xié)同過濾算法）、ItemCF（基于物品的協(xié)同過濾算法）在TopN推薦中的性能。UserCF中的K表示K個(gè)相似的用戶，ItemCF中的K表示K個(gè)相似的物品。因此離線實(shí)驗(yàn)測(cè)量了不同K值下UserCF算法、ItemCF的性能指標(biāo)如表3所示。ItemCF在LFM中，重要的參數(shù)有4個(gè)：

（1）隱特征的個(gè)數(shù)F；

（2）學(xué)習(xí)速率alpha；

（3）正則化參數(shù)lambda；

（4）負(fù)樣本/正樣本比例ratio。

通過實(shí)驗(yàn)發(fā)現(xiàn)，ratio參數(shù)對(duì)LFM的性能影響最大。因此，固定F=100、alpha=0.02、

lambda=0.01，然后研究負(fù)樣本/正樣本比例ratio對(duì)推薦結(jié)果性能的影響。

隨著負(fù)樣本數(shù)目的增加，LFM 的準(zhǔn)確率和召回率有明顯提高。不過當(dāng)ratio＞10以后，準(zhǔn)確率和召回率基本就比較穩(wěn)定了。同時(shí)，隨著負(fù)樣本數(shù)目的增加，覆蓋率不斷降低，而推薦結(jié)果的流行度不斷增加，說明 ratio參數(shù)控制了推薦算法發(fā)掘長(zhǎng)尾的能力。將LFM的結(jié)果ItemCF和UserCF算法的性能相比，可以發(fā)現(xiàn)LFM在所有指標(biāo)上都優(yōu)于UserCF和ItemCF。但是當(dāng)數(shù)據(jù)集非常稀疏時(shí)，LFM的性能會(huì)明顯下降。

3 總結(jié)

個(gè)性化課程推薦中LFM自動(dòng)聚類算法是從用戶興趣粒度多樣性的角度來進(jìn)行相應(yīng)推薦的，而且是自動(dòng)的，即用戶獲得的推薦是系統(tǒng)從用戶隱性反饋數(shù)據(jù)中獲得的，不需要用戶努力地找到適合自己興趣的推薦信息。雖然該算法解決了推薦過程中粒度差異性問題，以及提高了推薦的準(zhǔn)確性等參數(shù)。但仍存在稀疏問題(Sparsity)和可擴(kuò)展問題(Scalability)，相信這些問題在將來實(shí)際應(yīng)用過程中可以逐步的完善解決。

[1] 王春紅,張敏.隱含語義索引模型的分析與研究[J].計(jì)算機(jī)應(yīng)用,2007.

[2] 郭敏,董健全,宋智.基于 P2P的隱含語義索引模型的研究[J].計(jì)算機(jī)工程與設(shè)計(jì),2005.

[3] 馬宏偉,張光衛(wèi),李娜.協(xié)同過濾推薦算法綜述[J].小型微型計(jì)算機(jī)系統(tǒng),2009.

[4] 張玉英,孟海東.數(shù)據(jù)挖掘技術(shù)中聚類算法的改進(jìn)研究[J].包頭鋼鐵學(xué)院學(xué)報(bào),2005.

[5] Brin S, Page L. The anatomy of a large-scale hypertextual Web search engine[J]. Computer networks and ISDN systems,2011, 30(1): 107-117.

[6] Resnick P, Varian H R. Recommender systems[J]. Communications of the ACM, 2010, 40(3): 56-58.

[7] Heymann P, Garcia-Molina H. Collaborative creation of communal hierarchical taxonom ies in social tagging systems[J]. 2006.

[8] Lamere P. Social tagging and music information retrieval[J]. Journal of New Music Research, 2008, 37(2): 101-114.

[9] TrantJ,Wyman B. Investigating social tagging and folksonomy in art museums w ith steve. museum[C]//Collaborative Web Tagging Workshop at WWW 2012, Edinburgh, Scotland. 2006.

Research on Based LFM Automatic Clustering Algorithm of Personalized Course Recommendation

Yang Lili
(Nanjing Institute of Industry Technology, Nanjing 210046, China)

To recommend courses in different particle sizes of interest for students, Latent Factor Model (Hereinafter refers as LFM) is proposed in this paper, which is applied to the implicit feedback data set in the network environment that students click on the course. It automatically clusters the interest and behaviors of students and the course category and recommending Top-N items. Experiments show that the method is effective and has high accuracy.

LFM; Personalized; Recommendation System

TP311

A

2014.06.25）

江蘇省高等教育教改研究（2013JSJG356）；院級(jí)教研課題（GJ13-11）

楊立力（1978-），女，黑龍江省佳木斯市人,南京工業(yè)職業(yè)技術(shù)學(xué)院，講師，碩士研究生，CCF會(huì)員，研究方向：現(xiàn)代教育技術(shù)，南京，210046

1007-757X(2014)11-0028-04