理論與實踐： CASoRT系統(tǒng)中基于聚集特性的在線流行度預測方法
相關(guān)鏈接： 中國安全網(wǎng) 中國質(zhì)量網(wǎng) 中國論文網(wǎng) 中國資訊網(wǎng)
作者：鄭曉敏
1 引言
隨著智能手機和無線通信設(shè)備的廣泛使用，多媒體數(shù)據(jù)傳輸占用著越來越多的無線蜂窩通信資源。多媒體數(shù)據(jù)分組包括新聞、文檔、圖片和視頻等種類，其中新聞類數(shù)據(jù)無論在無線蜂窩網(wǎng)中還是互聯(lián)網(wǎng)上都是訪問最為頻繁的網(wǎng)絡數(shù)據(jù)。因此，主要針對通過無線蜂窩網(wǎng)訪問的新聞數(shù)據(jù)進行分析和研究。事實上，網(wǎng)絡新聞存在著明顯的聚集特性，主要體現(xiàn)在少數(shù)熱門新聞內(nèi)容占據(jù)著網(wǎng)站總訪問量的主體；用戶存在明顯的活躍用戶和非活躍用戶，對總訪問量的貢獻程度差別很大；用戶訪問新聞時的地理位置主要集中在少數(shù)幾個區(qū)域。通過對數(shù)據(jù)進行分析，找出其中的熱門內(nèi)容，然后將熱門內(nèi)容在適當?shù)臅r候（比如無線網(wǎng)絡比較空閑時）進行廣播，把熱門內(nèi)容提前存儲到用戶移動設(shè)備的本地存儲器。用戶在請求網(wǎng)絡數(shù)據(jù)時首先對本地存儲器進行搜索，若本地存儲器有該數(shù)據(jù)則直接讀取，未發(fā)現(xiàn)則向服務器申請傳輸該數(shù)據(jù)。這種方法可以大大地降低無線網(wǎng)絡在通信繁忙時段的通信量，還可以節(jié)省無線蜂窩通信網(wǎng)絡的傳輸資源，從而提高能效和譜效。CASoRT系統(tǒng)的無線蜂窩推送功能就是上述過程的具體實現(xiàn)。要想實現(xiàn)無線蜂窩推送，首先要找到預測熱門內(nèi)容的方法。
關(guān)于網(wǎng)絡多媒體內(nèi)容流行度預測的方法有很多，主要關(guān)注其使用的網(wǎng)絡數(shù)據(jù)流行度指標和使用的預測方法的類型。大量文獻使用了諸如評論、投票和點擊量等流行度指標和各種不同類型的預測方法，比如對數(shù)線性(linearlog)模型、恒定比例(constant scaling)模型、部分匹配(partial match)模型、對數(shù)正態(tài)分布(log-normal distribution)模型和Cox比例風險回歸(cox proportional hazardregression)模型等。這些模型中的任意一個均無法對所有的網(wǎng)絡數(shù)據(jù)進行準確的流行度預測，只能針對特定的數(shù)據(jù)集或者數(shù)據(jù)集中的一部分進行比較準確的流行度預測。
目前在流行度預測方法方面的研究主要有如下文獻，和本文類似，它們都是通過對網(wǎng)絡內(nèi)容發(fā)布后某較短時間段（即觀察時間）內(nèi)的訪問量大小來預測該網(wǎng)絡內(nèi)容的總訪問量，也就是流行度。
本文首先對從中國移動通信有限公司（以下簡稱中國移動）收集來的通過無線蜂窩網(wǎng)絡傳輸?shù)脑诰�網(wǎng)絡內(nèi)容數(shù)據(jù)集進行研究，通過該數(shù)據(jù)集的特點來反映無線網(wǎng)絡通信量的變化特征。經(jīng)過數(shù)據(jù)處理，選取鳳凰網(wǎng)(www.ifeng.com)上的新聞內(nèi)容作為其有代表性的子數(shù)據(jù)集進行分析。該網(wǎng)站的在線新聞點擊量作為流行度指標，即某新聞點擊量越多，表示該新聞越熱門。相比評論和投票，點擊量能夠更直接地反映出無線蜂窩網(wǎng)絡中通信量的變化情況。研究發(fā)現(xiàn)，該數(shù)據(jù)集除了在數(shù)據(jù)內(nèi)容、地理位置和用戶行為方面的聚集特性以外，某些熱門新聞在訪問量（即點擊量）快速上升之前，存在少量無規(guī)律訪問，這些無規(guī)律訪問會給流行度預測帶來較大的負面影響。為了減輕這種影響，使用一個在固定時間段（如6 min）內(nèi)訪問次數(shù)的門限值來改變觀察區(qū)間的起始時間點，使得該起始時間點能更加靠近誘問量快速上升的階段。在了解數(shù)據(jù)特性之后，提出了兩種流行度預測方法，即對數(shù)線性模型和恒定比例模型，兩種方法的預測準確度會因為門限值的使用而得到很大改善�；趯�(shù)據(jù)集的研究，本文給出了最佳觀察門限值，然后將兩個預測模型在使用最佳門限值時的預測準確度進行比較，仿真結(jié)果發(fā)現(xiàn)對數(shù)線性方法性能更好，因此被選定作為CASoRT系統(tǒng)的流行度預測方法。
2數(shù)據(jù)特性
本文使用的數(shù)據(jù)集是中國移動通信集團有限公司浙江分公司（以下簡稱浙江移動）一周（2014年4月19 -25日）的所有通過無線蜂窩網(wǎng)訪問的互聯(lián)網(wǎng)內(nèi)容。該數(shù)據(jù)集由大量訪問記錄組成，記錄中包含用戶識別號、訪問起始時間和終止時間、訪問頁面URL、區(qū)域位置號和小區(qū)位置號等屬性。通過訪問頁面URL過濾，篩選出鳳凰網(wǎng)上的在線網(wǎng)絡新聞作為研究子數(shù)據(jù)集。由于鳳凰網(wǎng)是我國第四大新聞門戶網(wǎng)站，擁有豐富的新聞內(nèi)容和各類不同的用戶群體，而且該網(wǎng)站的數(shù)據(jù)量大小非常適合分析和研究，因此被選定為研究對象。該子數(shù)據(jù)集的特性具有代表性，可以基本反映出所有網(wǎng)絡內(nèi)容的相關(guān)特性。圖1展示了鳳凰網(wǎng)所有網(wǎng)絡新聞的訪問量以h為單位隨時間的分布情況，可以看出該網(wǎng)站每天的總訪問量無明顯差別。同時可以發(fā)現(xiàn)，在每一天中都有明顯的訪問量尖峰和訪問量低谷，且尖峰和低谷出現(xiàn)的時間段相似。無線蜂窩推送策略需要在合適的時候?qū)衢T內(nèi)容進行廣播，如果在非訪問量高峰時段特別是低谷時廣播熱門內(nèi)容，在節(jié)省資源的同時還能達到平抑訪問量尖峰的效果。
2.1 數(shù)據(jù)聚集特性
數(shù)據(jù)的聚集特性主要體現(xiàn)在用戶行為、網(wǎng)絡內(nèi)容和地理位置3個方面。用戶的聚集特性如圖2所示�？梢钥吹�，少量的活躍用戶占據(jù)著網(wǎng)站總訪問量的主體，在前20%最活躍的用戶中，其訪問量之和占總訪問量的比例達到700/0，因此，在研究無線蜂窩推送策略時應重點關(guān)注活躍用戶。
另一個聚集特性體現(xiàn)在新聞內(nèi)容上。用戶在7天內(nèi)共點擊了鳳凰網(wǎng)上36 804個不同的新聞標題，它們代表著不同的新聞內(nèi)容。熱門的網(wǎng)絡內(nèi)容和冷門的網(wǎng)絡內(nèi)容在其總訪問量也就是流行度上的差別很大，最熱門的標題有超過3萬次訪問，而很多非熱門標題訪問量僅為1次。如圖3所示，少數(shù)熱門標題占據(jù)著網(wǎng)站總訪問量的主體。前5%最熱門的內(nèi)容的訪問量占總訪問量的88010，而前10%最熱門的標題的訪問量約占總訪問量的92%。網(wǎng)絡內(nèi)容的聚集特性非常明顯，因此，如果能從大量的網(wǎng)絡數(shù)據(jù)中預測出熱門內(nèi)容，然后進行推送，必將節(jié)省大量的無線網(wǎng)絡傳輸資源。
在地理位置方面，若從用戶整體角度來看，聚集特性并不明顯，但對于單個用戶來講，其訪問網(wǎng)絡內(nèi)容時所在地理位置存在聚集特性。用戶一般在少數(shù)幾個固定的小區(qū)內(nèi)訪問網(wǎng)絡內(nèi)容，并且其訪問量主要發(fā)生在若干個活躍小區(qū)內(nèi)。統(tǒng)計發(fā)現(xiàn)，用戶在其最活躍的小區(qū)內(nèi)平均訪問了58%的網(wǎng)絡內(nèi)容，而在其最活躍的前兩個小區(qū)內(nèi)平均訪問了超過80%的內(nèi)容。因此將熱門內(nèi)容推送給潛在用戶時，會優(yōu)先考慮向用戶的最活躍小區(qū)進行推送。
2.2數(shù)據(jù)隨時間的變化特性
除了聚集特性之外，對于任一新聞標題而言，也存在訪問量隨時間變化的特性。每個標題訪問量隨時間變化的特性各不相同，但也存在著共性。不同點主要體現(xiàn)在每個標題的訪問持續(xù)時間不同，有些標題的訪問量主要集中在24 h內(nèi)，而有些標題可能持續(xù)幾天被大量點擊。共性主要體現(xiàn)在每個標題訪問量隨時間的變化都符合圖1所示的周期，即在一天內(nèi)有明顯的訪問量高峰和低谷。在這些性質(zhì)各不相同的標題中，那些訪問量集中在某個較短時間比如24 h內(nèi)的標題，在預測其流行度時可以達到較高的準確度；而那些訪問持續(xù)時間比較長，訪問量在時間上并不集中的標題，無法比較準確地預測其流行度，即預測流行度和實際流行度之間存在比較大的偏差。
另一個影響預測準確度的特點是部分標題在訪問量迅速上升之前，存在少量的無規(guī)律點擊，這可能是由于該新聞在發(fā)布時并未第一時間放到新聞網(wǎng)站的主頁上，典型的該類型新聞標題如圖4所示。這些點擊會給預測帶來嚴重的誤差，甚至可能讓預測算法將一個熱門新聞內(nèi)容誤預測成一個非熱門內(nèi)容。使用訪問量觀察門限值來減輕該影響，即將標題觀察時間的起始點定為某時刻，該時刻為第一個其之前6 min內(nèi)的訪問量超過門限值的時間點。
3流行度預測算法
由數(shù)據(jù)特性可以推知，如果通過前若干個小時（如2h）觀測到的訪問量來預測該標題在整個訪問持續(xù)時間里的總訪問量，那么顯然存在如下一般規(guī)律：觀察時間里該標題的訪問量越多，則該標題是熱門內(nèi)容的可能性越大。因此，考慮使用線性模型作為流行度預測方法，常用的線性預測方法主要有對數(shù)線性模型和恒定比例模型。這里需要注意的是，觀測時段的起始時間點并不一定是新聞的發(fā)布時間，這主要取決于是否使用觀察門限。
3.1 預測算法
線性預測算法是一類較為簡單的流行度估計方法。在觀察時間內(nèi)的訪問量和該標題的總訪問量可能存在線性關(guān)系，但事實上該線性關(guān)系并不顯著。如果將觀察時間內(nèi)的訪問量和總訪問量置于自然對數(shù)尺度下，該線性關(guān)系會更為明顯，特別是對于具有長尾效應的數(shù)據(jù)集。本文給出兩種線性預測算法，并在隨后對其性能進行比較。
(1)對數(shù)線性模型
對數(shù)線性模型的主要目的是對變量進行對數(shù)變換，從而找出兩個變量間的線性關(guān)系。該模型下的流行度預測公式如式(1)所示：
其中，Ni為標題i的流行度預測值，而Ni(t)表示標題i在觀察時間內(nèi)的訪問量，該觀察時間長度為t。k(t)和b(t)為反映線性關(guān)系的相關(guān)參數(shù)，它們隨觀察時間長度的變化而改變，可以在訓練數(shù)據(jù)集中利用線性回歸方法找到其最優(yōu)值。
(2)恒定比例模型
恒定比例模型最初也由參考文獻[5]提出。該模型下的流行度預測公式如式(2)所示：
其中，Ni'為標題i的預測總訪問量，a(t)可通過式(3)計算得出：
3.2最佳觀察門限及算法性能比較
如前所述，門限值選取的目的是將觀察時間的起點置于訪問量快速上升之時，從而減輕偶然無規(guī)律訪問對流行度預測準確性的影響。皮爾遜相關(guān)系數(shù)( pearsoncorrelation coefficient．PCC)用來表征兩個向量的線性相關(guān)度，該值越大，表示線性相關(guān)性越強。在此對觀察時間內(nèi)的所有標題訪問量的自然對數(shù)和所有標題總訪問量（即流行度）的自然對數(shù)之間的線性相關(guān)度進行分析。如圖5所示，當觀察門限從0增加到6時，任意長度觀測時間的皮爾遜相關(guān)系數(shù)均逐漸增大，而觀察門限取8和10時，皮爾遜相關(guān)系數(shù)相比門限值為6時呈下降趨勢，其中門限值取4—10時皮爾遜系數(shù)無明顯差別。特別的，在觀察時間長度為24 h，門限值不小于4時，皮爾遜相關(guān)系數(shù)接近0.95，也就是說此情況下24 h內(nèi)的訪問量和總訪問量存在很強的線性關(guān)系，這和數(shù)據(jù)集的特征是相符的。
在選擇最佳觀察門限時，需要考慮兩個方面的因素：一是希望盡可能多地保留數(shù)據(jù)集的信息量，即被門限值排除在外的訪問量所占比例應盡量�。毫硪环矫媸侨≡撻T限值時的皮爾遜相關(guān)系數(shù)盡可能得大，線性相關(guān)性越強，預測性能也會越好。因此，選擇4作為最佳觀察門限，在取該門限時，部分冷門新聞內(nèi)容的訪問和熱門新聞內(nèi)容的無規(guī)律點擊可能不會計人觀察時間段內(nèi)的訪問量，從而造成部分信息的丟失。統(tǒng)計表明，這部分被最佳觀察門限值排除在外的訪問量占所有標題總訪問量的比例低于8%，這部分丟棄的信息基本不會對預測產(chǎn)生影響。
平均平方誤差(mean squared error，MSE)被用作兩種預測算法的性能評價指標。MSE值越小，說明該算法預測準確度越好。該指標的計算式見式(4):
如圖6所示，在未使用觀察門限時，恒定比例模型在不同觀察時間長度的MSE值均小于對數(shù)線性模型。而使用最佳觀察門限之后，兩個預測算法的性能都得到了很大提升，更重要的是，在觀察時間長度為1～8 h時，對數(shù)線性模型的MSE值小于恒定比例模型，而觀察時間長度取9～24 h時，兩個模型間的MSE值無較大差別。在能提供足夠預測準確度的前提下，如能越早預測出某新聞標題的流行度，就可以在傳輸資源節(jié)省上獲得更大收益�？紤]到數(shù)據(jù)集的特性，一般在2—6 h選擇觀察時間長度，而在此區(qū)間內(nèi)，對數(shù)線性模型有著更好的性能，因此被選作系統(tǒng)的流行度預測算法。顯然，若觀察時間長度超過24 h，再進行流行度預測就沒有意義了，因為大部分標題的訪問量都集中在24 h以內(nèi)。
4結(jié)束語
本文提出了一種基于最佳觀察門限的對數(shù)線性預測方法，該最佳觀察門限大大提高了對數(shù)線性方法的預測準確度。觀察門限的引入主要是基于對鳳凰網(wǎng)在線新聞訪問量的特點分析。了解到在線新聞不僅在內(nèi)容、用戶和地理位置方面存在著聚集特性，部分內(nèi)容還存在一些不規(guī)律的偶然訪問，濾除這些偶然訪問可以大大改善預測性能�；趯Ρ疚臄�(shù)據(jù)集進行計算和分析，確定了最佳觀察門限為4，然后對兩種預測算法使用最佳觀察門限時的性能進行比較，最后選定對數(shù)線性模型作為預測算法。
本文提出的預測算法能較好地估計網(wǎng)絡內(nèi)容的流行度，同時在線新聞的相關(guān)特性也反映出無線蜂窩網(wǎng)通信量的變化情況和使用推送策略可能帶來的能效收益。因此，本預測算法能通過前若干個小時（如2h）觀測到的訪問量估計該網(wǎng)絡內(nèi)容總訪問量從而預測該內(nèi)容是否熱門，然后將熱門內(nèi)容通過無線蜂窩推送系統(tǒng)進行廣播，不僅能降低網(wǎng)絡在高峰時段的擁塞度，還能節(jié)省大量的傳輸資源。
5摘要：
少數(shù)在線熱門內(nèi)容會在短時間內(nèi)吸引大量用戶的訪問，并占用大量的網(wǎng)絡傳輸資源。如果能預知內(nèi)容的熱門程度（即流行度）并將熱門內(nèi)容廣播給潛在用戶，將極大地節(jié)省網(wǎng)絡傳輸資源，這正是CASoRT系統(tǒng)的主要功能。通過對國內(nèi)商業(yè)蜂窩通信系統(tǒng)中收集的相關(guān)數(shù)據(jù)進行分析和研究，發(fā)現(xiàn)在用戶行為、地理位置、數(shù)據(jù)內(nèi)容等方面存在明顯的聚集特性。根據(jù)上述特性給出了兩個流行度預測算法，即對數(shù)線性和恒定比例模型，并使用最優(yōu)觀察門限改善兩算法的性能。通過對兩算法仿真結(jié)果的比較，對數(shù)線性模型表現(xiàn)更優(yōu)，被選作系統(tǒng)的在線流行度預測方法。
