基于超圖排序和組稀疏最優(yōu)化的推薦系統(tǒng)

于 琨，孫 波，海本齋

(1.河南工學(xué)院 計(jì)算機(jī)科學(xué)與技術(shù)系，河南 新鄉(xiāng)453002；2.河南師范大學(xué) 計(jì)算機(jī)與信息工程學(xué)院，河南 新鄉(xiāng)453002)

0 引 言

社交媒體的發(fā)展引起了與圖像相關(guān)的元數(shù)據(jù)信息如標(biāo)簽和地理標(biāo)簽廣泛的研究。許多社交媒體共享平臺(tái)如各種社交網(wǎng)站、微博、微信、博客、論壇、播客等等，不僅成為人們彼此之間用來(lái)分享意見(jiàn)、見(jiàn)解、經(jīng)驗(yàn)和觀點(diǎn)的工具和平臺(tái)，還可以允許用戶(hù)注釋圖像，根據(jù)他們的觀點(diǎn)來(lái)描述內(nèi)容。由于人們之間的文化差異，所以對(duì)圖像內(nèi)容的感知可能會(huì)有所不同。圖像標(biāo)注的目的就是彌合這種語(yǔ)義差距，有利于圖像搜索和分類(lèi)。這個(gè)任務(wù)可以通過(guò)利用另一種與圖像相關(guān)的元數(shù)據(jù)信息如地理標(biāo)簽進(jìn)一步得到提高?，F(xiàn)代移動(dòng)設(shè)備如相機(jī)或智能手機(jī)能夠在它自動(dòng)拍攝的時(shí)候給一個(gè)圖像指定專(zhuān)門(mén)的地理坐標(biāo)，用這種有價(jià)值的地理信息來(lái)豐富圖像有助于圖像進(jìn)一步搜索。

標(biāo)簽是分配給一個(gè)圖像的語(yǔ)義關(guān)鍵字。圖像標(biāo)注能夠使社交媒體用戶(hù)共享平臺(tái)注釋圖像，有利于圖像搜索和內(nèi)容描述。關(guān)于該領(lǐng)域盡管已有大量的相關(guān)研究，但諸如精度或效率等問(wèn)題仍然是人們十分關(guān)注的問(wèn)題。近年來(lái)，許多研究集中于圖像標(biāo)注和利用圖像內(nèi)容。文獻(xiàn)[1]提出了一種圖像和視頻標(biāo)注模型。注釋概率的估計(jì)是基于一個(gè)多伯努利模型，同時(shí)非參數(shù)核密度估計(jì)(kernel density estimates，KDE)被用作為圖像特征；文獻(xiàn)[2]基于Markov隨機(jī)場(chǎng)(Markov random fields，MRF)提出了一種概率模型來(lái)捕捉不同特征之間的相關(guān)性；文獻(xiàn)[3]采用基于圖的方法，將多類(lèi)型相互關(guān)聯(lián)的目標(biāo)信息用于圖像特征的描述和標(biāo)注；文獻(xiàn)[4,5]分別提出對(duì)圖像進(jìn)行分割提取低層視覺(jué)特征作為圖像區(qū)域標(biāo)注和提取圖像前景與背景區(qū)域并分別進(jìn)行預(yù)處理來(lái)實(shí)現(xiàn)對(duì)圖像的自動(dòng)標(biāo)注；文獻(xiàn)[6]提出將聯(lián)合分類(lèi)和回歸模型同時(shí)用來(lái)實(shí)現(xiàn)圖像注釋和地理標(biāo)簽預(yù)測(cè)；文獻(xiàn)[7]對(duì)于地理標(biāo)簽預(yù)測(cè)問(wèn)題提出了一種基于數(shù)據(jù)驅(qū)動(dòng)場(chǎng)景匹配方法的解決方案；文獻(xiàn)[8,9]分別將基于超圖的方法用于三維目標(biāo)的檢索和估計(jì)用戶(hù)標(biāo)注圖像的相關(guān)性；文獻(xiàn)[10,11]提出了基于組稀疏(group sparsity，GS)和多核學(xué)習(xí)方法(multiple Kernel learning with group sparsity，MKLGS)先將包含多種異構(gòu)特征的非線性圖像數(shù)據(jù)映射到一個(gè)希爾伯特空間，然后利用希爾伯特空間中的核函數(shù)以及組LASSO對(duì)每個(gè)圖像類(lèi)別選擇最具區(qū)別性特征的集合，最終訓(xùn)練得到分類(lèi)模型對(duì)圖像進(jìn)行標(biāo)注；文獻(xiàn)[12]提出了一種圖正則化約束下的非負(fù)組稀疏(graph regularized non-negative group sparsity，GRNGS)模型來(lái)實(shí)現(xiàn)圖像標(biāo)注，并通過(guò)一種非負(fù)矩陣分解方法來(lái)計(jì)算其模型參數(shù)。

本文在超圖排序框架內(nèi)針對(duì)同時(shí)性圖像標(biāo)注和地理位置預(yù)測(cè)提出了一種方法實(shí)現(xiàn)的推薦系統(tǒng)，并通過(guò)執(zhí)行組稀疏最優(yōu)化來(lái)使圖像標(biāo)注和地理位置預(yù)測(cè)的準(zhǔn)確性得到進(jìn)一步提高。通過(guò)從中國(guó)旅評(píng)網(wǎng)抽取出的數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果表明，本文提出的方法相比于其它方法，不僅能夠獲得更高的召回-精確率和F1測(cè)量值，而且能夠?qū)ε琶?位的地理位置獲得更高的正確預(yù)測(cè)率和累計(jì)評(píng)分。

1 基于超圖排序和組稀疏最優(yōu)化的推薦系統(tǒng)

(1)

(2)

式(2)就是一般推薦系統(tǒng)問(wèn)題的解，通過(guò)式(2)獲得的排名可用于超圖圖像標(biāo)注，但是其精確度是很低的，因?yàn)樗鼪](méi)有對(duì)標(biāo)注對(duì)象進(jìn)行細(xì)分；為了提高其精確度，我們把每個(gè)頂點(diǎn)的子集稱(chēng)為對(duì)象組，當(dāng)然每個(gè)對(duì)象組對(duì)排序過(guò)程的貢獻(xiàn)是不同的，并把超圖頂點(diǎn)分割成S個(gè)非重疊對(duì)象組(圖像、用戶(hù)、社會(huì)群體、地理標(biāo)簽和標(biāo)簽)，而且對(duì)每個(gè)對(duì)象組分配不同的權(quán)值γs(s=1,2,…,S)， 以使下列目標(biāo)函數(shù)最小化

(3)

式中：Ks為大小為 |V|×|V| 的對(duì)角矩陣，而且對(duì)于屬于第s個(gè)對(duì)象組的頂點(diǎn)來(lái)說(shuō)，其元素等于1。為簡(jiǎn)便起見(jiàn)，我們把式(3)的最小化問(wèn)題表示為

(4)

這樣，就得到由式(4)表示的經(jīng)過(guò)組稀疏最優(yōu)化的排序向量f*。

為了求解式(4)，令x=f-y， 并引入輔助變量z=x， 式(4)右端可重寫(xiě)為

(5)

這樣，式(5)的解就可以通過(guò)使增廣拉格朗日函數(shù)最小化來(lái)得到

(6)

式中：λ是拉格朗日乘子向量，并在每次迭代中被更新，μ是一個(gè)參數(shù)，調(diào)整約束以使x=z。求解式(6)的算法的偽代碼如下。

算法1：

(1)給定xt,zt和λt

(2)設(shè)置算法收斂的精度值ε并初始化μ0

(6)λt+1=λt+μt(zt+1-xt+1)

(7)μt+1=min(1.1μt,106)

(8)else

(9) returnxt+1,zt+1

(10)f=xt+1+y

(11)endif

算法求解第(3)行的xt+1得到

xt+1=(L+μtI)-1(λt+μtzt-Ly)

(7)

仔細(xì)觀察式(7)可以發(fā)現(xiàn)，在每次迭代不需要矩陣的逆，只需要一個(gè)特征值分解。事實(shí)上，令Qt=L+μtI， 則有

(8)

(9)

這樣，算法1的第(4)行所描述的最小化問(wèn)題就可表示為

(10)

通過(guò)應(yīng)用軟閾值算子[17]得到

(11)

2 算法實(shí)例

2.1 數(shù)據(jù)集描述

為了實(shí)現(xiàn)和評(píng)價(jià)本文提出的算法，收集的圖像數(shù)據(jù)集來(lái)自于中國(guó)旅評(píng)網(wǎng)[18]，它包含哈爾濱市的索菲亞大教堂地標(biāo)、防洪紀(jì)念塔和流行的俄羅斯風(fēng)情大街城市風(fēng)等景觀照片，如圖1所示，而且還下載了一大組“地理標(biāo)記”圖像以及與它們相關(guān)的有價(jià)值的信息(id、標(biāo)題、所有者、緯度、經(jīng)度、標(biāo)簽、圖像視圖)。然后，基于圖像視圖及用戶(hù)的上傳統(tǒng)計(jì)對(duì)數(shù)據(jù)集進(jìn)行過(guò)濾。假設(shè)具有多視圖的圖像通常描繪值得注意的地標(biāo)和具有許多上傳圖像的用戶(hù)是活躍群體，他們擁有許多社會(huì)關(guān)系(朋友、社交群體)，則抽取相應(yīng)的社會(huì)信息(朋友、社交群體)，而且只有來(lái)自于數(shù)據(jù)集的至少有5個(gè)用戶(hù)的群體作為成員被保留。具體基數(shù)見(jiàn)表1。

圖1 數(shù)據(jù)集采集圖像

對(duì)象記號(hào)數(shù)值圖像Im1290用戶(hù)U438用戶(hù)組Gr1646地理標(biāo)簽Geo126標(biāo)簽Ta2365

2.2 超圖的構(gòu)建

頂點(diǎn)集定義為V=Im∪U∪Gr∪Geo∪Ta。 超圖H由連接6個(gè)超邊集構(gòu)成，超邊集如表2的列所示。H的大小為5866×30920個(gè)元素，超邊集E(1)-E(6)的權(quán)值設(shè)置為1。

表2 超圖關(guān)聯(lián)矩陣H及其子矩陣的結(jié)構(gòu)

E(1)表示用戶(hù)之間的兩兩關(guān)系。超圖關(guān)聯(lián)矩陣UE(1)有大小為442×2273個(gè)元素；

E(2)表示用戶(hù)組。它包含相應(yīng)用戶(hù)的全部頂點(diǎn)以及相應(yīng)用戶(hù)組的全部頂點(diǎn)。超圖關(guān)聯(lián)矩陣UE(2)-GrE(2)有大小2080×1642個(gè)元素；

E(3)包含一個(gè)用戶(hù)和一個(gè)上傳的圖像，代表一個(gè)用戶(hù)圖像擁有的關(guān)系。每個(gè)圖像只有一個(gè)擁有者。超圖關(guān)聯(lián)矩陣的UE(3)-ImE(3)有大小為1730×1294個(gè)元素；

E(4)捕獲地理位置關(guān)系。這個(gè)超邊集包含Im、U和Geo。超圖關(guān)聯(lián)矩陣ImE(4)-UE(4)-GeoE(4)有大小1858×124個(gè)元素；

E(5)也包含Im、U和Geo。每個(gè)超邊表示一個(gè)標(biāo)記關(guān)系。超圖關(guān)聯(lián)矩陣ImE(5)-UE(5)-TaE(5)有大小4099×19124個(gè)元素；

為了構(gòu)成這部分超圖，采用全局和局部特征。首先，采用GIST描述符[19]對(duì)每個(gè)圖像的100個(gè)最近鄰居進(jìn)行確定，而且通過(guò)采用尺度不變特征變換(scaleinvariant feature transform，SIFT)[20]把它們減少到5個(gè)最相似的圖像作為參考圖像。

通過(guò)設(shè)置對(duì)應(yīng)于參考圖像im的記錄及其擁有者的u=1來(lái)使查詢(xún)向量y初始化。連接到該圖像的標(biāo)簽ta設(shè)置為A(im,ta)。對(duì)應(yīng)于gr和geo且與圖像擁有者u相關(guān)聯(lián)的對(duì)象分別設(shè)置為A(u,gr)和A(u,geo)。查詢(xún)向量y具有5866個(gè)元素的長(zhǎng)度。

通過(guò)求解式(2)或式(4)和已經(jīng)設(shè)置的查詢(xún)向量y、正則化參數(shù)?和在式(4)情形下的對(duì)象組權(quán)值γs(見(jiàn)第3節(jié))來(lái)得到排序向量f*，它與y有相同的大小和結(jié)構(gòu)。對(duì)應(yīng)于標(biāo)簽的值用于具有排名最高的標(biāo)簽(被推薦為參考圖像)的圖像標(biāo)注，對(duì)應(yīng)于geo的值用于具有僅排名前3的地理位置(即地理集群，被推薦為參考圖像)的地理位置預(yù)測(cè)。

3 算法性能仿真

為了評(píng)價(jià)本文提出的算法性能，一方面，我們把經(jīng)過(guò)組稀疏最優(yōu)化處理的式(4)獲得的排名、通過(guò)式(2)獲得的排名以及文獻(xiàn)[3]采用簡(jiǎn)單的基于圖的方法獲得的排名進(jìn)行比較(為簡(jiǎn)便起見(jiàn)，把本文提出的方法即式(4)的算法稱(chēng)為方法1，式(2)的算法稱(chēng)為方法2，文獻(xiàn)[3]采用簡(jiǎn)單的基于圖的方法稱(chēng)為方法(3))，性能指標(biāo)為平均召回-精確率和F1測(cè)量值；另一方面，把本文提出的方法1獲得的地理位置正確預(yù)測(cè)率、通過(guò)式(2)方法即方法2獲得的地理位置正確預(yù)測(cè)率以及將圖像地理坐標(biāo)之間的距離(即地面真實(shí)距離)與地理名稱(chēng)相關(guān)聯(lián)的距離通過(guò)采用“半正矢公式”進(jìn)行計(jì)算得到的地理位置正確預(yù)測(cè)率(稱(chēng)為方法4)進(jìn)行比較；最后我們還比較了在相同的數(shù)據(jù)集上前3種方法關(guān)于平均召回率和平均精確率的收斂特性。

為了計(jì)算召回率和精確率，把排名最高的15個(gè)標(biāo)簽推薦給任意測(cè)試圖像，5個(gè)不同對(duì)象組(圖像、用戶(hù)、用戶(hù)組、地理標(biāo)簽和標(biāo)簽)的權(quán)值分別設(shè)置為0.9、0.9、0.6、0.2和0.2，μ0、ε和?的典型值分別為10-6、10-8和2。圖2 所示為3種方法得到的平均召回-精確率曲線，曲線是對(duì)至少4個(gè)標(biāo)簽的1180個(gè)圖像的召回-精確率取平均值得到的。從圖2可見(jiàn)，本文提出的方法1的排名的平均召回-精確率性能得到了顯著提高，方法2次之，文獻(xiàn)[3]采用簡(jiǎn)單的基于圖的方法獲得的排名的平均召回-精確率是最差的；表3所示為對(duì)應(yīng)于5種不同的排名位置時(shí)3種方法得到的平均F1測(cè)量值。從表3可見(jiàn)，顯然本文提出的方法1取得了較好的F1測(cè)量值，明顯優(yōu)于其它2種方法。

圖2 3種不同方法的平均召回-精確率曲線比較

算法@1的F1@2的F1@6的F1@10的F1@16的F1方法10.4020.6310.7110.5670.441方法20.3090.4600.5320.4480.367方法30.2890.4110.4930.4010.323

表4所示為對(duì)應(yīng)于排名前3位元素時(shí)3種方法得到的地理位置正確預(yù)測(cè)率。從表4可見(jiàn)，本文提出的方法1不僅能夠獲得全部排名較好的位置預(yù)測(cè)率，而且排名前3位的元素的正確預(yù)測(cè)率達(dá)到了87%，總評(píng)分明顯高于其它2種方法，分別平均高24%和61%，說(shuō)明基于組稀疏最優(yōu)化處理后的效果是很明顯的。

表4 3種方法得到的排名前3的位置預(yù)測(cè)率及累計(jì)評(píng)分

圖3所示為相同數(shù)據(jù)集上得到的前3種方法的平均召回率和精確率的收斂過(guò)程。從圖3可見(jiàn)，隨著迭代次數(shù)的增加，3種方法的平均召回率和精確率都在不斷增加，但本文提出的方法1的增加速度明顯高于另外2種方法，平均召回率大約高31%和42%，平均精確率大約高29%和41%。這不僅有利于快速獲取圖像標(biāo)注的時(shí)效性，而且也大大提高了圖像標(biāo)注的準(zhǔn)確性和可靠性。

圖3 平均召回率和平均精確率的收斂特性

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

在本文中，提出了一種有效的同時(shí)性圖像標(biāo)注和地理位置預(yù)測(cè)算法。方法基于超圖學(xué)習(xí)，充分利用了圖像內(nèi)容、背景和社交媒體信息，而且通過(guò)執(zhí)行組稀疏優(yōu)化使得算法性能得到進(jìn)一步提高；采用哈爾濱地標(biāo)圖像集合通過(guò)仿真實(shí)驗(yàn)對(duì)本文所提出的算法性能進(jìn)行了評(píng)價(jià)和比較，結(jié)果表明，本文提出的算法在召回-精確率、平均F1測(cè)量值和位置正確預(yù)測(cè)率方面都是有效和可行的；本文提出的算法還可以適用于標(biāo)注任何多媒體(如音樂(lè)和視頻場(chǎng)景)以及它們之間的融合，對(duì)諸如基于圖像和地理坐標(biāo)的旅游指南系統(tǒng)或基于查詢(xún)的推薦觀光目的地系統(tǒng)的應(yīng)用也有啟發(fā)和借鑒意義。