国产日韩欧美一区二区三区三州_亚洲少妇熟女av_久久久久亚洲av国产精品_波多野结衣网站一区二区_亚洲欧美色片在线91_国产亚洲精品精品国产优播av_日本一区二区三区波多野结衣 _久久国产av不卡

?

基于降維和聚類(lèi)的協(xié)同過(guò)濾推薦算法

2020-04-15 02:59李玲娟
關(guān)鍵詞:降維質(zhì)心聚類(lèi)

陳 希,李玲娟

(南京郵電大學(xué) 計(jì)算機(jī)學(xué)院,江蘇 南京 210003)

0 引 言

隨著信息技術(shù)與互聯(lián)網(wǎng)的迅猛發(fā)展,人們進(jìn)入了一個(gè)信息“爆炸”的時(shí)代,如何從海量信息中找到自己感興趣的信息,如何讓自己釋放的信息脫穎而出受到關(guān)注都成為迫切需要解決的問(wèn)題[1]。個(gè)性化的推薦系統(tǒng)成為繼分類(lèi)目錄和搜索引擎后解決信息過(guò)載問(wèn)題的代表性方案。推薦系統(tǒng)不需要用戶提供明確需求,而是通過(guò)分析用戶的歷史行為記錄主動(dòng)推薦滿足用戶需求的信息。

在現(xiàn)有的推薦技術(shù)中,基于協(xié)同過(guò)濾的推薦算法使用最為廣泛,主要分為基于用戶和基于項(xiàng)目?jī)煞N協(xié)同過(guò)濾,原理都是通過(guò)用戶—項(xiàng)目評(píng)分矩陣計(jì)算相似度進(jìn)行推薦[2]??墒请S著用戶與項(xiàng)目數(shù)量的不斷增加,出現(xiàn)了評(píng)分矩陣稀疏、搜索最近鄰耗時(shí)久等問(wèn)題,導(dǎo)致傳統(tǒng)的協(xié)同過(guò)濾算法推薦質(zhì)量有所下降。為解決數(shù)據(jù)稀疏性問(wèn)題,大部分研究人員采用填充法(0,均值,眾數(shù))來(lái)補(bǔ)全缺失值,但不能從根本上解決數(shù)據(jù)稀疏性問(wèn)題;文獻(xiàn)[3]提出使用奇異值分解(SVD)來(lái)解決數(shù)據(jù)稀疏性問(wèn)題,但當(dāng)數(shù)據(jù)量龐大時(shí)SVD效率會(huì)很低;文獻(xiàn)[4-6]中都構(gòu)建了基于用戶聚類(lèi)的協(xié)同推薦算法,通過(guò)對(duì)用戶評(píng)價(jià)矩陣進(jìn)行分析,采用K-means聚類(lèi)算法把興趣和偏好相似程度較高的用戶分到同一個(gè)簇中,以減少搜索最近鄰的時(shí)間,但會(huì)因?yàn)槌跏假|(zhì)心的選取不當(dāng)導(dǎo)致推薦質(zhì)量下降;有人嘗試采用BP神經(jīng)網(wǎng)絡(luò)來(lái)預(yù)測(cè)評(píng)分[7],此方法雖然可以降低數(shù)據(jù)稀疏性所帶來(lái)的影響,但需花費(fèi)更長(zhǎng)的近鄰查找時(shí)間。

文中設(shè)計(jì)了一種基于主成分分析法(principal component analysis,PCA)和二分K-means聚類(lèi)的新算法(命名為PK-CF算法),對(duì)輸入的用戶-項(xiàng)目高維稀疏矩陣使用PCA進(jìn)行降維,提取主成分因子,并在降維后的數(shù)據(jù)上進(jìn)行二分K-means聚類(lèi),尋找當(dāng)前用戶的所屬類(lèi)別,進(jìn)而快速確定其最近鄰,最后通過(guò)最近鄰相似度加權(quán)計(jì)算出當(dāng)前用戶對(duì)未評(píng)測(cè)項(xiàng)目的預(yù)測(cè)值。

1 相關(guān)知識(shí)

1.1 基于用戶的協(xié)同過(guò)濾推薦算法

如果部分用戶對(duì)某些項(xiàng)目的感興趣程度比較類(lèi)似,則他們對(duì)其他項(xiàng)目的感興趣程度也會(huì)比較相似,可以把他們歸為同一個(gè)群體?;谟脩舻膮f(xié)同過(guò)濾推薦算法以此為前提,通過(guò)分析目標(biāo)用戶的最近鄰居(最相似的若干用戶)對(duì)某個(gè)項(xiàng)目的評(píng)分來(lái)預(yù)測(cè)目標(biāo)用戶對(duì)該項(xiàng)目的評(píng)分[8]。該算法主要包括兩個(gè)步驟:

(1)查找與目標(biāo)用戶有相似興趣的用戶集合;

(2)將用戶集合中用戶最感興趣且目標(biāo)用戶未使用的項(xiàng)目推薦給目標(biāo)用戶。

此類(lèi)算法的核心是計(jì)算用戶間的相似度,計(jì)算方法包括Jaccard、皮爾遜相關(guān)系數(shù)、歐幾里德距離和余弦距離。其中的皮爾遜相關(guān)系數(shù)方法在數(shù)據(jù)不規(guī)范時(shí)能給出更好的計(jì)算結(jié)果,具體公式如下:

(1)

文中將通過(guò)求皮爾遜相關(guān)系數(shù)來(lái)計(jì)算用戶間的相似性。

1.2 PCA降維技術(shù)

降維是應(yīng)用最為廣泛的數(shù)據(jù)預(yù)處理方法之一,這種方法通過(guò)去除高維數(shù)據(jù)中的噪聲和無(wú)關(guān)緊要的特征,提升數(shù)據(jù)處理的速度進(jìn)而節(jié)省大量的時(shí)間和成本。雖然降維造成了一定的信息損失,但在實(shí)際的應(yīng)用中,通常只需要保留數(shù)據(jù)最重要的特征,一定范圍內(nèi)的信息損失是可允許的[9]。降維的方法有線性和非線性之分,線性降維將n維的高維數(shù)據(jù)通過(guò)某種線性投影的方法映射到一個(gè)p維的低維空間,即用線性無(wú)關(guān)的p個(gè)新特征取代n個(gè)舊特征并保留數(shù)據(jù)的主成分(包含信息量最大的維度),從而實(shí)現(xiàn)在保留原數(shù)據(jù)較多特性的情況下將n維數(shù)據(jù)降到p維的目的。

PCA(主成分分析)是最常用的線性降維方法之一,經(jīng)過(guò)PCA降維后的數(shù)據(jù)將轉(zhuǎn)換到一個(gè)新的坐標(biāo)系中。新坐標(biāo)系的坐標(biāo)軸方向?yàn)閿?shù)據(jù)方差最大的方向,方差反映的是數(shù)據(jù)與其均值之間的偏離程度,通常認(rèn)為方差越大數(shù)據(jù)的信息量就越大。計(jì)算原數(shù)據(jù)中方差最大的方向,把它作為第一個(gè)坐標(biāo)軸,第二個(gè)新坐標(biāo)軸選擇的是與第一個(gè)新坐標(biāo)軸正交且方差次大的方向,重復(fù)該過(guò)程,重復(fù)次數(shù)為原始數(shù)據(jù)的特征維數(shù)[10]。在最后獲得的新坐標(biāo)系中,最先確定的坐標(biāo)軸包含了數(shù)據(jù)最具特征的維度,余下坐標(biāo)軸所包含的信息量幾乎為0,可忽略不計(jì)。因此,只保留前面幾個(gè)坐標(biāo)軸,也就實(shí)現(xiàn)了對(duì)數(shù)據(jù)特征的降維處理。PCA算法的主要步驟如下:

輸入:數(shù)據(jù)集X為m個(gè)n維的樣本x1,x2,…,xm。

Step1:將X的每一維進(jìn)行去均值化,即減去這一維的均值。

Step2:用式2計(jì)算樣本的協(xié)方差矩陣。

(2)

Step3:求出協(xié)方差矩陣特征值及對(duì)應(yīng)的特征向量。

Step4:將特征向量按對(duì)應(yīng)特征值大小從上到下按行排列成矩陣,取前s行組成矩陣P;

輸出:Y=PTX,Y即是X降到s維后的數(shù)據(jù)。

為了縮小投影的誤差,需要選取合適的s值,可用如下公式來(lái)確定s值:

(3)

其中,m表示特征的個(gè)數(shù),分子計(jì)算的是數(shù)據(jù)原始點(diǎn)與投影后的點(diǎn)距離的總和;Error表示誤差,誤差越小說(shuō)明保留的主成分越多,降維的效果越好。一般控制Error的值小于0.01,即保留原數(shù)據(jù)99%信息特征。

1.3 K-means聚類(lèi)與二分K-means聚類(lèi)

數(shù)據(jù)挖掘的主要任務(wù)之一是聚類(lèi)分析,它將物理或抽象對(duì)象的集合劃分成多個(gè)類(lèi)簇,同一個(gè)簇中的對(duì)象彼此相似,不同簇中的對(duì)象彼此相異[11]。

K-means聚類(lèi)算法在眾多聚類(lèi)算法中應(yīng)用最為普遍。該算法首先根據(jù)數(shù)據(jù)集大小隨機(jī)確定k個(gè)初始點(diǎn)為質(zhì)心;然后將數(shù)據(jù)集中的每一個(gè)點(diǎn)分配到一個(gè)簇中,即為每一個(gè)點(diǎn)找到距其最近的質(zhì)心,并將其分配給該質(zhì)心所對(duì)應(yīng)的簇;最后,每一個(gè)簇的質(zhì)心更新為該簇所有點(diǎn)的平均值,重復(fù)以上步驟,直到質(zhì)心不再變化[12]。K-means算法對(duì)初始質(zhì)心的選擇比較敏感,隨機(jī)生成的k個(gè)質(zhì)心可能出現(xiàn)質(zhì)心聚集的情況,導(dǎo)致聚類(lèi)效果可能是局部最優(yōu)的。

誤差平方和SSE是一種用于度量聚類(lèi)效果的指標(biāo),其值是所有簇中的全部數(shù)據(jù)點(diǎn)到簇中心的誤差距離的平方累加和。SSE公式如下:

(4)

其中,k為指定的簇?cái)?shù);ci為第i個(gè)簇的質(zhì)心;x為質(zhì)心為ci的簇中的數(shù)據(jù);dist計(jì)算的是兩個(gè)向量的歐幾里得距離。SSE的值越小,說(shuō)明全部數(shù)據(jù)點(diǎn)越靠近于它們各自所屬的簇的中心(即質(zhì)心),聚類(lèi)效果也越好。

作為K-means算法的優(yōu)化算法,二分K-means聚類(lèi)算法首先將所有數(shù)據(jù)點(diǎn)看成一個(gè)簇,然后將該簇一分為二,并選擇一個(gè)簇進(jìn)行k均值(k=2)劃分。選擇的標(biāo)準(zhǔn)是被劃分的簇能最大限度降低SSE的值,以此進(jìn)行下去,直到簇的數(shù)目等于用戶給定的數(shù)目k為止。該算法與K-means算法相比,聚類(lèi)速度更快,受初始質(zhì)心的影響更小,聚類(lèi)效果更好。

2 基于PCA和二分K-means協(xié)同過(guò)濾推薦算法設(shè)計(jì)

2.1 基本思路

針對(duì)傳統(tǒng)基于用戶的協(xié)同過(guò)濾推薦算法所存在的評(píng)分矩陣稀疏性與擴(kuò)展性的問(wèn)題,文中設(shè)計(jì)了一種高效的協(xié)同過(guò)濾推薦算法—基于PCA降維技術(shù)和二分K-means聚類(lèi)的協(xié)同過(guò)濾推薦算法PK-CF(collaborative filtering recommendation algorithm based on PCA dimension reduction and bisecting K-means clustering)。

(1)稀疏性問(wèn)題的解決思路。

利用PCA對(duì)評(píng)分矩陣進(jìn)行降維處理,保留最能代表用戶興趣的主成分,同時(shí)緩解評(píng)分矩陣高稀疏性問(wèn)題。

(2)相似度計(jì)算時(shí)耗問(wèn)題的解決思路。

協(xié)同過(guò)濾算法需要先計(jì)算每?jī)蓚€(gè)對(duì)象間的相似度,再搜索最近鄰進(jìn)行推薦,但隨著用戶和項(xiàng)目的不斷增加,相似度的計(jì)算量變得非常龐大,傳統(tǒng)算法的可擴(kuò)展性問(wèn)題也凸顯出來(lái)。為此,一些學(xué)者使用了數(shù)據(jù)挖掘中的K-means算法,根據(jù)用戶的歷史評(píng)分記錄,計(jì)算其與每個(gè)簇質(zhì)心的相似度,把目標(biāo)用戶劃歸到所屬的簇內(nèi),縮小最近鄰搜索范圍再進(jìn)行相似度的計(jì)算,減小計(jì)算量。但是K-means算法對(duì)初始質(zhì)心的敏感性可能導(dǎo)致聚類(lèi)效果是局部最優(yōu)的,會(huì)影響最終的推薦準(zhǔn)確度。

為此,文中在基于用戶的協(xié)同過(guò)濾算法中引入二分K-means算法,首先將數(shù)據(jù)集中所有用戶—項(xiàng)目評(píng)分?jǐn)?shù)據(jù)看成一個(gè)簇,然后將簇一分為二,當(dāng)簇值小于指定的K值時(shí),以被劃分的簇能最大限度降低SSE的值為標(biāo)準(zhǔn),選擇一個(gè)簇進(jìn)行k均值(k=2)劃分,直到簇的數(shù)值等于K值時(shí),算法停止。

2.2 PK-CF算法流程

PK-CF算法的流程如下:

Step1:將評(píng)分?jǐn)?shù)據(jù)轉(zhuǎn)換成用戶—項(xiàng)目評(píng)分矩陣,然后對(duì)每行缺失值進(jìn)行填充,填充值為此行評(píng)分值的均值。

Step2:按圖1所示的流程運(yùn)用PCA算法提取數(shù)據(jù)中的主成分(保留精度為99%),得到降維后的矩陣R并記錄特征值與特征向量。

圖1 PCA降維過(guò)程

Step3:利用圖2所示的流程對(duì)降維后的矩陣R進(jìn)行二分K-means聚類(lèi),得到多個(gè)簇及各簇的質(zhì)心。

Step4:當(dāng)要預(yù)測(cè)用戶u時(shí),根據(jù)特征值與特征向量求出用戶u在主成分向量空間的坐標(biāo),并用式1計(jì)算其與各簇質(zhì)心的相似度,用戶u屬于與其相似度最高的質(zhì)心對(duì)應(yīng)的簇,再求出u與簇內(nèi)各用戶的相似度,形成一個(gè)用戶相似度矩陣X。

Step5:用基于最近鄰的預(yù)測(cè)方法[13]來(lái)預(yù)測(cè)用戶u對(duì)未評(píng)分項(xiàng)目i的評(píng)分,具體公式如下:

(5)

圖2 二分K-means聚類(lèi)過(guò)程

Step6:根據(jù)預(yù)測(cè)評(píng)分進(jìn)行TopN推薦,形成推薦列表。

3 實(shí)驗(yàn)與結(jié)果分析

3.1 數(shù)據(jù)集

實(shí)驗(yàn)使用美國(guó)明尼蘇達(dá)大學(xué)GroupLens項(xiàng)目組提供的MoviesLen數(shù)據(jù)集,該數(shù)據(jù)集包括943名用戶對(duì)1 682部電影的100 000條評(píng)分記錄,記錄包含user_id、itme_id、rating和timestamp四個(gè)字段,對(duì)應(yīng)用戶ID、電影ID、評(píng)分值和評(píng)分時(shí)間四個(gè)屬性。通過(guò)計(jì)算在整個(gè)數(shù)據(jù)集中未評(píng)分項(xiàng)目所占的比例,得出數(shù)據(jù)的稀疏程度為93.695 3%,適合檢驗(yàn)PK-CF算法在數(shù)據(jù)稀疏狀況下的推薦效果。

3.2 評(píng)判標(biāo)準(zhǔn)

實(shí)驗(yàn)采用平均絕對(duì)誤差[14](mean absolute error,MAE)作為推薦預(yù)測(cè)準(zhǔn)確度的評(píng)判標(biāo)準(zhǔn),MAE反映預(yù)測(cè)的用戶評(píng)分與實(shí)際的用戶評(píng)分之間的偏差,偏差越小推薦質(zhì)量越高。MAE計(jì)算公式如下:

(6)

TopN推薦的預(yù)測(cè)準(zhǔn)確度一般通過(guò)召回率Recall與準(zhǔn)確率Precision來(lái)度量[15]。召回率描述的是推薦正確的項(xiàng)目評(píng)分記錄數(shù)與測(cè)試集中的所有項(xiàng)目評(píng)分記錄數(shù)之比,準(zhǔn)確率描述的是推薦正確的項(xiàng)目評(píng)分記錄數(shù)與所有推薦的項(xiàng)目評(píng)分記錄數(shù)之比。推薦結(jié)果Recall和Precision越高,推薦質(zhì)量越好。召回率與準(zhǔn)確率計(jì)算公式分別如下:

(7)

(8)

其中,R(u)為對(duì)用戶u推薦的N個(gè)項(xiàng)目的集合;T(u)為用戶u在測(cè)試集上喜歡的物品的集合。

在實(shí)際應(yīng)用中,需要綜合考慮召回率與準(zhǔn)確率,最常用的方法是F-Score,它是Recall和Precision加權(quán)調(diào)和平均。F-Score得分越高,說(shuō)明推薦準(zhǔn)確度也高[16],計(jì)算公式如下:

(9)

3.3 結(jié)果分析

實(shí)驗(yàn)前測(cè)得最終分類(lèi)個(gè)數(shù)在12

文中共進(jìn)行4次實(shí)驗(yàn)來(lái)驗(yàn)證PK-CF算法的有效性。隨機(jī)地把數(shù)據(jù)集按照4∶1的比例分為訓(xùn)練集與測(cè)試集,每次選擇不同的訓(xùn)練集與測(cè)試集分別運(yùn)行傳統(tǒng)的基于用戶的協(xié)同過(guò)濾算法,基于K-means用戶聚類(lèi)的協(xié)同過(guò)濾算法和文中的PK-CF算法,對(duì)結(jié)果取均值。

(1)推薦預(yù)測(cè)準(zhǔn)確度測(cè)試。

實(shí)驗(yàn)結(jié)果如圖3所示。

圖3 推薦預(yù)測(cè)質(zhì)量比較

可以看出,在最近鄰個(gè)數(shù)L=25時(shí),三種算法都取得了較好的推薦質(zhì)量;而文中的PK-CF算法的MAE值在不同最近鄰個(gè)數(shù)下都比傳統(tǒng)的基于用戶的算法和基于K-means用戶聚類(lèi)的算法要小,能夠有效地提高推薦質(zhì)量。

(2)TopN推薦的預(yù)測(cè)指標(biāo)對(duì)比。

表1與表2的數(shù)據(jù)都是在最近鄰個(gè)數(shù)為25狀況下的實(shí)驗(yàn)結(jié)果。

表1 近鄰個(gè)數(shù)為25,N=10時(shí)不同算法的指標(biāo)

表2 近鄰個(gè)數(shù)為25,N=20時(shí)不同算法的指標(biāo)

可以看出,文中的PK-CF算法能有效提高推薦的召回率、準(zhǔn)確率和F-Score值,而且當(dāng)TopN推薦的N為20時(shí),基于K-means的算法和文中的PK-CF算法的F-Socre值都大于N為10時(shí)的F-Score值,所以為了提高推薦質(zhì)量可以適當(dāng)增大N的值即推薦數(shù)量。在算法運(yùn)行的時(shí)間方面,PK-CF算法和基于K-means的算法運(yùn)行時(shí)長(zhǎng)基本相同,但與傳統(tǒng)的協(xié)同過(guò)濾算法相比運(yùn)行時(shí)長(zhǎng)明顯減小很多。

4 結(jié)束語(yǔ)

文中將傳統(tǒng)協(xié)同過(guò)濾推薦算法與PCA降維和二分K-means相結(jié)合,設(shè)計(jì)出新的協(xié)同過(guò)濾推薦算法。該算法用PCA降維技術(shù)緩解數(shù)據(jù)集稀疏問(wèn)題,同時(shí)使用二分K-means聚類(lèi)方法對(duì)用戶聚類(lèi)減少查找相似用戶的時(shí)耗。實(shí)驗(yàn)結(jié)果表明,該算法能夠有效提高推薦質(zhì)量。

猜你喜歡
降維質(zhì)心聚類(lèi)
一種傅里葉域海量數(shù)據(jù)高速譜聚類(lèi)方法
混動(dòng)成為降維打擊的實(shí)力 東風(fēng)風(fēng)神皓極
重型半掛汽車(chē)質(zhì)量與質(zhì)心位置估計(jì)
基于知識(shí)圖譜的k-modes文本聚類(lèi)研究
基于數(shù)據(jù)降維與聚類(lèi)的車(chē)聯(lián)網(wǎng)數(shù)據(jù)分析應(yīng)用
基于GNSS測(cè)量的天宮二號(hào)質(zhì)心確定
一種改進(jìn)K-means聚類(lèi)的近鄰傳播最大最小距離算法
降維打擊
基于模糊聚類(lèi)和支持向量回歸的成績(jī)預(yù)測(cè)
基于近鄰穩(wěn)定性的離群點(diǎn)檢測(cè)算法
平顶山市| 乐业县| 信阳市| 平潭县| 山丹县| 岳池县| 南京市| 眉山市| 达尔| 砀山县| 罗田县| 锦屏县| 雷波县| 龙陵县| 克拉玛依市| 夏津县| 安化县| 郁南县| 简阳市| 江达县| 汝城县| 会昌县| 方山县| 阿拉尔市| 呈贡县| 巫山县| 奉贤区| 高陵县| 长春市| 塔城市| 中西区| 黑河市| 云阳县| 海伦市| 尤溪县| 思茅市| 鄯善县| 广安市| 泗水县| 淮南市| 漳州市|