融合雙聚類技術(shù)的新型協(xié)同過(guò)濾算法*

左東石

(內(nèi)蒙古農(nóng)業(yè)大學(xué) 計(jì)算機(jī)與信息工程學(xué)院，內(nèi)蒙古 呼和浩特 010018)

隨著第三方支付業(yè)務(wù)的普及，在互聯(lián)網(wǎng)交易平臺(tái)上時(shí)刻進(jìn)行著大量的交易行為.對(duì)于用戶來(lái)說(shuō)，如何選擇合適的商品/項(xiàng)目和低廉的價(jià)格，是其最關(guān)心的問題.協(xié)同過(guò)濾[1]技術(shù)是電子商務(wù)平臺(tái)廣泛采用的系統(tǒng)推薦方法，其通過(guò)數(shù)據(jù)挖掘和信息檢索技術(shù)來(lái)實(shí)現(xiàn)自動(dòng)化推薦，可以根據(jù)用戶行為智能地選擇符合客戶要求的商品.目前，協(xié)作過(guò)濾技術(shù)主要分為兩類[2]：最近鄰算法和基于模型的算法.由于最近鄰算法[3]具有更高的計(jì)算精度，因此該方法獲得了更多的關(guān)注，發(fā)展較快.文獻(xiàn)[4]研究了參數(shù)k對(duì)k-最近鄰算法性能的影響，并提出了獲取最佳預(yù)測(cè)性能的k值選取方法.文獻(xiàn)[5]將矩陣分解與用戶最近鄰點(diǎn)相結(jié)合，實(shí)現(xiàn)了用戶之間的相似度信息與矩陣模型的有機(jī)整合，大幅度提高了算法性能.文獻(xiàn)[6]分析了傳統(tǒng)協(xié)同過(guò)濾算法的數(shù)據(jù)稀松問題，設(shè)計(jì)了考慮用戶與項(xiàng)目特征的自適應(yīng)協(xié)同過(guò)濾算法，并利用評(píng)分相似模型計(jì)算出了用戶和項(xiàng)目的最近鄰集合.

本文提出一種同時(shí)考慮用戶和項(xiàng)目特性的雙聚類協(xié)同過(guò)濾算法，通過(guò)構(gòu)建雙聚類相似度來(lái)獲得推薦服務(wù)與用戶之間的局部鄰近度，并將局部度量和全局距離度量相結(jié)合，從而為每個(gè)網(wǎng)絡(luò)服務(wù)創(chuàng)建均衡排名，達(dá)到提升協(xié)同過(guò)濾精度的目的.

1 雙聚類協(xié)同過(guò)濾算法

1.1 相似度計(jì)算

皮爾森相關(guān)系數(shù)(Pearson correlation coefficient，PCC)是一種計(jì)算用戶和項(xiàng)目之間相似性的有效方法，已在許多推薦系統(tǒng)中被廣泛應(yīng)用[7].當(dāng)PPC被用來(lái)測(cè)量?jī)蓚€(gè)用戶之間的相似度時(shí)，其標(biāo)準(zhǔn)表達(dá)式為：

為了將網(wǎng)絡(luò)服務(wù)的個(gè)體屬性并入用戶相似度計(jì)算中，需要設(shè)計(jì)相應(yīng)的權(quán)重系數(shù).第i個(gè)網(wǎng)絡(luò)服務(wù)的服務(wù)質(zhì)量權(quán)重計(jì)算過(guò)程包括：服務(wù)質(zhì)量值歸一化，標(biāo)準(zhǔn)偏差計(jì)算，權(quán)重生成.

① 服務(wù)質(zhì)量歸一化.通過(guò)與最大、最小網(wǎng)絡(luò)服務(wù)值進(jìn)行比較，將用戶的第i個(gè)網(wǎng)絡(luò)服務(wù)值變換為區(qū)間[0, 1]的實(shí)數(shù).具體的歸一化計(jì)算方法為

式中：ri為第i個(gè)網(wǎng)絡(luò)服務(wù)對(duì)應(yīng)的網(wǎng)絡(luò)服務(wù)值的集合.

② 標(biāo)準(zhǔn)偏差計(jì)算.對(duì)于網(wǎng)絡(luò)服務(wù)i來(lái)說(shuō)，其網(wǎng)絡(luò)服務(wù)值歸一化的標(biāo)準(zhǔn)偏差為

在經(jīng)過(guò)以上三步后，我們提出一種基于網(wǎng)絡(luò)服務(wù)權(quán)重重構(gòu)的用戶(仍用用戶a、b來(lái)表示)間相似度的改進(jìn)方法，其計(jì)算公式為：

上式可以將網(wǎng)絡(luò)服務(wù)的個(gè)性化影響納入用戶相似度測(cè)量中，從而使得具有較大權(quán)重的網(wǎng)絡(luò)服務(wù)將對(duì)用戶間的相似性影響更大.為了實(shí)現(xiàn)協(xié)同過(guò)濾，還需采用下式所示的用戶服務(wù)質(zhì)量值的預(yù)測(cè)方法(以用戶a為例)：

為了避免因用戶與項(xiàng)目之間的對(duì)偶性而產(chǎn)生的數(shù)據(jù)稀疏問題，需要對(duì)用戶與項(xiàng)目之間的相似性進(jìn)行優(yōu)化處理.因此，下面給出項(xiàng)目之間的相似度計(jì)算及其改進(jìn)方案.最后再對(duì)用戶、項(xiàng)目進(jìn)行聚類計(jì)算.網(wǎng)絡(luò)服務(wù)(項(xiàng)目)i、j之間的PCC計(jì)算公式為：

與用戶間服務(wù)質(zhì)量值的權(quán)重修改方法類似，項(xiàng)目間的相似度改進(jìn)計(jì)算公式為：

1.2 雙聚類技術(shù)

采用雙聚類方法實(shí)現(xiàn)用戶和服務(wù)間的協(xié)同過(guò)濾，從而實(shí)現(xiàn)網(wǎng)絡(luò)服務(wù)的有效推薦.

對(duì)于用戶x(對(duì)應(yīng)的用戶集為X)和網(wǎng)絡(luò)服務(wù)y(對(duì)應(yīng)的項(xiàng)目集為Y)，雙聚類方法包括三個(gè)基本步驟：① 將用戶x映射到最小雙聚類Z=(X,Y)上；② 搜索項(xiàng)目集Y的雙聚類近鄰，確認(rèn)其作為有效網(wǎng)絡(luò)服務(wù)的推薦候選集；③ 基于全局相似度和雙聚類鄰域相似度，評(píng)估Y中的網(wǎng)絡(luò)服務(wù).

Top-n推薦技術(shù)[8]是近年來(lái)信息服務(wù)領(lǐng)域的一個(gè)研究熱點(diǎn)，它可以從研究對(duì)象中得到所需的n個(gè)數(shù)據(jù)，并從排序列表中選取最大或最小的n個(gè)數(shù)據(jù)，從而完成推薦過(guò)程.本文將Top-n推薦與雙聚類算法相結(jié)合，用來(lái)提高推薦的準(zhǔn)確性和快速性.該方案的具體算法流程為：

1.開始；

2.設(shè)置變量：ui為用戶，M為所有數(shù)據(jù)構(gòu)成的矩陣，n為期望的網(wǎng)絡(luò)服務(wù)推薦數(shù)；

3.搜索最小雙聚類Z：減小Z的鄰域，最小化uiZ，得到用戶-項(xiàng)目集(X,Y)；

4.對(duì)Z中所有元素進(jìn)行同屬化，得到最小同屬雙聚類Zs；

5.對(duì)于所有的Zs，將Y中對(duì)應(yīng)的Ys設(shè)置為候選項(xiàng)目；

6.對(duì)于所有的包含于候選項(xiàng)中的y，計(jì)算Pm_x,y；

7.結(jié)合全局和雙聚類相似度對(duì)候選網(wǎng)絡(luò)服務(wù)進(jìn)行排列，返回Pm_x,y中的前n個(gè)網(wǎng)絡(luò)服務(wù)；

8.結(jié)束.

上述計(jì)算流程中的全局相似度和局部相似度的計(jì)算方法如下.

假設(shè)Xy、Xy′分別表示與網(wǎng)絡(luò)y、y′進(jìn)行交互的所有用戶的集合，則J(x,y)的表達(dá)式為：

雙聚類相似度的計(jì)算方法如下，令Z=(X,Y)和Z′=(X′,Y′)為兩個(gè)不同的雙聚類，這兩個(gè)雙聚類的聯(lián)合Φ和零誘導(dǎo)相似度B分別為：

式中：zeros(·)代表求取矩陣中零值的數(shù)量，零值的數(shù)量越少，Z和Z′就越相似.假設(shè)Z是初始聚類，Z′是較低的領(lǐng)域或者Z的同類聚類，則在矩陣(X∪X′)·(Y∪Y′)中至少有一個(gè)零值.

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

為驗(yàn)證算法的有效性，我們將算法與傳統(tǒng)的基于項(xiàng)目的協(xié)同過(guò)濾算法相比較.此外，實(shí)驗(yàn)中的網(wǎng)絡(luò)服務(wù)數(shù)據(jù)選取淘寶某日交易的部分?jǐn)?shù)據(jù)，該數(shù)據(jù)集包含來(lái)自400個(gè)用戶的12 000個(gè)網(wǎng)絡(luò)服務(wù)的服務(wù)質(zhì)量調(diào)用記錄.為了便于計(jì)算，將這些數(shù)據(jù)集轉(zhuǎn)換為用戶服務(wù)矩陣，用戶服務(wù)矩陣的每個(gè)項(xiàng)目是由響應(yīng)時(shí)間和吞吐量構(gòu)成的.因此，原始用戶服務(wù)矩陣可以分解成兩個(gè)更簡(jiǎn)單的矩陣，即響應(yīng)時(shí)間矩陣和吞吐量矩陣.這兩個(gè)矩陣用于計(jì)算用戶和服務(wù)的相似度.在該數(shù)據(jù)集上進(jìn)行了對(duì)比實(shí)驗(yàn)，用來(lái)驗(yàn)證所提出算法相較于傳統(tǒng)算法在精度κ和召回率σ等方面的優(yōu)勢(shì).衡量推薦算法性能的主要技術(shù)指標(biāo)(即精度和召回率)的計(jì)算方法為：

式中：D為待檢索文檔；D′為被成功檢索的文檔；si(·)代表求取文檔中所有元素對(duì)應(yīng)的分?jǐn)?shù)之和.

圖1、圖2為推薦數(shù)量分別取不同的值時(shí)，基于項(xiàng)目的服務(wù)質(zhì)量值預(yù)測(cè)的方法和基于雙聚類的方法在精度和召回率方面的性能比較結(jié)果.由實(shí)驗(yàn)結(jié)果可知，隨著推薦數(shù)量的增加，兩種算法的精度和召回率都在增加，而提出的方法在這兩項(xiàng)指標(biāo)上明顯優(yōu)于傳統(tǒng)的方法.

除了精度和召回率，算法占用的CPU運(yùn)算時(shí)間也是評(píng)價(jià)算法優(yōu)劣的重要指標(biāo)：較大的CPU運(yùn)算時(shí)間所對(duì)應(yīng)的算法的用戶數(shù)量也比較大；CPU運(yùn)算時(shí)間越大，其所對(duì)應(yīng)的算法效率越低.對(duì)兩種算法的CPU占用時(shí)間進(jìn)行對(duì)比，其結(jié)果如圖3所示.由該圖可知，本文提出的方法具有更低的CPU占用時(shí)間，表明提出的方法具有更高的計(jì)算效率.

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

提出了一種基于雙聚類技術(shù)和Top-n推薦的新型協(xié)同過(guò)濾算法.當(dāng)使用網(wǎng)絡(luò)服務(wù)數(shù)據(jù)集對(duì)所提算法進(jìn)行測(cè)試時(shí)，基于雙聚類技術(shù)的協(xié)同過(guò)濾算法推薦準(zhǔn)確率較高.此外，提出的協(xié)同過(guò)濾方法具備更好的計(jì)算性能，在處理數(shù)據(jù)集時(shí)具有更高的靈活性，這是因?yàn)樘岢龅碾p聚類協(xié)同過(guò)濾算法既涉及用戶屬性，又涉及項(xiàng)目特征.由此可知，與已有的方法相比，雙聚類協(xié)同過(guò)濾算法可以緩解稀疏問題，大幅度提高了網(wǎng)絡(luò)服務(wù)的推薦質(zhì)量.

參考文獻(xiàn)

[1] 占淵, 肖蓉, 繆仲凱,等. 基于改進(jìn)的協(xié)同過(guò)濾相似性度量算法研究[J]. 計(jì)算機(jī)測(cè)量與控制, 2017, 25(9): 287-290.

[2] HUANG Z,ZENG D,CHEN H. A comparison of collaborative-filtering algorithms for ecommerce[J]. Intelligent Systems IEEE, 2015, 22(5): 68-78.

[3] 趙喜玲, 張曉惠. 基于動(dòng)態(tài)特征和靜態(tài)特征融合的步態(tài)識(shí)別方法[J]. 湘潭大學(xué)自然科學(xué)學(xué)報(bào), 2017, 39(4): 89-91.

[4] VIMALKUMAR B,HIMALAY H P. Optimization of the neighbor parameter of k-nearest neighbor algorithm for collaborative filtering[C]//International Conference on Communication and Networks, 2017: 87-93.

[5] WANG Z,YU N,WANG J. Collaborative filtering recommendation algorithm based on matrix factorization and user nearest neighbors[C]//Asian Simulation Conference, 2016: 199-207.

[6] PENG Y,CHENG X P. A collaborative filtering recommendation algorithm based on adaptive nearest neighbor selection[J]. Computer Knowledge & Technology, 2016, 16(4): 33-41.

[7] LY A,MARSMAN M,WAGENMAKERS E J. Analytic posteriors for Pearson’s correlation coefficient[J]. Statistica Neerlandica, 2017, 12(3): 108-116.

[8] 劉云, 王穎, 亓國(guó)濤, 等. 時(shí)間上下文的協(xié)同過(guò)濾Top-N推薦算法[J]. 計(jì)算機(jī)技術(shù)與發(fā)展, 2017, 27(7): 79-82.

[9] NITOBE T,YASUNO T,KANEKO S. Firearm classification based on extensive jaccard index of 3D cross-sectioned shape of firing pin impression on fired cartridge cases[J]. Journal of the Japan Society for Precision Engineering, 2017, 83(4): 355-360.