一種移動網(wǎng)絡(luò)視頻流U-vMOS分類算法

王運博，馮剛強，張詩友，韓一石

(廣東工業(yè)大學(xué)信息工程學(xué)院，廣東 廣州510080)

1 引言

隨著互聯(lián)網(wǎng)技術(shù)迅猛發(fā)展，各式各樣網(wǎng)絡(luò)視頻業(yè)務(wù)接連不斷的涌現(xiàn)，視頻流量在互聯(lián)網(wǎng)流量中的比重不斷提高?！禫isual Network Index》預(yù)測，2020年全球互聯(lián)網(wǎng)網(wǎng)絡(luò)總流量中視頻流量占比有望提高到82%，其中移動視頻數(shù)據(jù)流量將占總網(wǎng)絡(luò)流量的50%[1]。同時，視頻用戶對視頻觀看質(zhì)量也提出了更高層次的要求。據(jù)某移動運營商調(diào)研統(tǒng)計數(shù)據(jù)顯示，視頻加載時長超過2秒用戶會選擇關(guān)閉視頻，加載或卡頓時長每超過1秒，選擇關(guān)閉視頻的用戶將增加6%[2]。根據(jù)某著名咨詢公司的調(diào)查，因為對產(chǎn)品或服務(wù)不滿意，82%的用戶選擇終止該業(yè)務(wù)，并且這會引起更嚴重的連鎖反應(yīng)，平均將有另外13個人受到這種對服務(wù)不滿評價的影響[3]。因此，研究如何準確評估用戶主觀感受、定位網(wǎng)絡(luò)故障和優(yōu)化網(wǎng)絡(luò)質(zhì)量的需求日益增長[4]。過去許多研究主要集中在提高移動網(wǎng)絡(luò)視頻流的服務(wù)質(zhì)量QoS(Quanlity of Service)上。

但是上述QoS無法有效表征用戶的感知體驗。典型的QoS包括吞吐量，帶寬，延遲，抖動和損耗[5-7]等參數(shù)，工作原理是提供服務(wù)保證以增強應(yīng)用程序性能。研究發(fā)現(xiàn)，僅提供服務(wù)保證不足以提高用戶感知質(zhì)量，基于QoS的質(zhì)量評估方案在預(yù)測用戶體驗方面不適用于評估視頻質(zhì)量[8-9]。與QoS相比，用戶體驗質(zhì)量QoE(Quality of Experience)更偏向于用戶對視頻本身的主觀感受[10]，國際電信聯(lián)盟遠程通信標準化組織將QoE定義為終端用戶對應(yīng)用服務(wù)的主觀可接受程度，該指標直接反映了用戶對服務(wù)的認可程度。目前，視頻平均意見得分U-vMOS(User，Unified，Ubiquitous-Mean Opinion Score for Video)作為標準化網(wǎng)絡(luò)視頻流QoE的最新提議之一已引起廣泛關(guān)注[12][21]。U-vMOS是華為公司針對視頻用戶體驗衡量的統(tǒng)一框架，覆蓋場景從傳統(tǒng)娛樂類視頻業(yè)務(wù)(點播和直播)，到視頻監(jiān)控和視頻通話等業(yè)務(wù)，從移動終端到 PC 和 TV，其得分基本上是根據(jù)國際電信聯(lián)盟(ITU)標準化的平均意見分數(shù)(MOS)來確定的[11]，得分1到5分別表示差，較差，一般，良好和優(yōu)秀五個等級。

針對上述U-vMOS標準，已經(jīng)有了一些視頻QoE評估方案。文獻[12]將U-vMOS用作評估DJEZZY消費者的視頻體驗的工具，并將其與基于一組專家的主觀測試進行了比較，但其僅使用基于統(tǒng)計分析的數(shù)學(xué)公式預(yù)測用戶QoE。文獻[13-14]提出基于華為U-vMOS標準的YouTube視頻流比特率機器學(xué)習(xí)估計方案，但該文獻僅研究比特率估算準確性對其HTTPS YouTube視頻流服務(wù)KPI的影響。文獻[15]提出基于移動網(wǎng)絡(luò)視頻流QoE數(shù)據(jù)的數(shù)據(jù)分析框架，研究U-vMOS與服務(wù)質(zhì)量(QoS)參數(shù)的聯(lián)系，使用K-means聚類和邏輯回歸的組合算法預(yù)測用戶QoE，但該文獻僅將用戶QoE分為好壞兩類，并未提出預(yù)測用戶U-vMOS的方案。上述工作并未考慮數(shù)據(jù)集非均衡問題，且沒有研究基于機器學(xué)習(xí)的移動視頻流U-vMOS評估方案。

為了解決上述問題，本文提出結(jié)合代價敏感思想改進AdaBoost算法用來評估用戶U-vMOS。由于用戶體驗質(zhì)量差的情況僅占極少數(shù)，U-vMOS值分布不平衡，然而大多數(shù)的機器學(xué)習(xí)算法均不適用于非均衡的數(shù)據(jù)集。目前，解決不平衡數(shù)據(jù)問題的研究主要集中在抽樣方法上[16]。與抽樣方法相比，結(jié)合代價敏感思想的改進AdaBoost算法保留所有樣本，只改變賦予樣本的權(quán)重，可以提高分類器對小類的關(guān)注，使U-vMOS分類器獲得優(yōu)秀的性能，采用完善和統(tǒng)一的U-vMOS標準評估視頻業(yè)務(wù)體驗?zāi)軌驗檫\營商和視頻產(chǎn)業(yè)鏈提升用戶體驗給出切實的指導(dǎo)建議。

2 數(shù)據(jù)說明

本文數(shù)據(jù)集來自華為建立的SpeedVideo全球運營平臺(SVGOP)，SVGOP是U-vMOS在全球移動網(wǎng)絡(luò)中的特定應(yīng)用。數(shù)據(jù)集總共包含89266個樣本。首先對數(shù)據(jù)集進行初步的統(tǒng)計分析，圖1從1到5顯示了U-vMOS得分直方圖，其中主豎直軸代表U-vMOS得分，次豎直軸代表U-vMOS得分的占比，水平軸代表U-vMOS區(qū)間。由圖1可得，96%U-vMOS值集中在3到5的范圍內(nèi)，這表明數(shù)據(jù)集非均衡，極少數(shù)的U-vMOS值非常接近“差”。

圖1 數(shù)據(jù)集U-vMOS得分

3 數(shù)據(jù)處理

數(shù)據(jù)集包含大量特征信息，直接處理比較耗費時間并且會降低算法性能[17]。特征工程可以選出最能代表SVGOP數(shù)據(jù)集特性的特征子集，去除數(shù)據(jù)集中的冗余特征，減少算法時間復(fù)雜度，提高U-vMOS預(yù)測模型性能。本節(jié)采用皮爾遜相關(guān)系數(shù)法計算數(shù)據(jù)特征和U-vMOS的相關(guān)系數(shù)，選取用于構(gòu)建U-vMOS預(yù)測模型的特征，其具體公式如下

(1)

表1 皮爾遜相關(guān)系數(shù)法計算結(jié)果

4 改進AdaBoost算法

AdaBoost算法是最重要的集成學(xué)習(xí)算法之一，具有嚴謹?shù)睦碚摶A(chǔ)和較高的預(yù)測精度，目前具有廣泛的成功應(yīng)用[18]。該算法在每一輪迭代中提高對于上一輪分類錯誤樣本的識別能力，但多次迭代后基本分類器對多數(shù)類樣本敏感，對少數(shù)類樣本分類能力降低，導(dǎo)致最終分類器在不平衡數(shù)據(jù)集中無法有效預(yù)測用戶U-vMOS。最新研究表明代價敏感方法(Cost-sensitive Method)可以有效應(yīng)用于非均衡數(shù)據(jù)集[19-20]。本文基于代價敏感思想優(yōu)化傳統(tǒng) AdaBoost 算法，接下來將介紹改進AdaBoost算法步驟。

圖2 改進AdaBoost算法流程圖

改進AdaBoost算法步驟如下：

1)初始化所有訓(xùn)練樣本權(quán)重分布：

D1=(w11，w12，…，w1i，…，w1N)，

(2)

其中D1表示數(shù)據(jù)集初始權(quán)重分布，w1i表示樣本i的初始權(quán)重，N表示樣本數(shù)量。樣本權(quán)重相同即表示每個樣本在基本U-vMOS分類器G1的學(xué)習(xí)中作用相同；

2)開始迭代。使用權(quán)值分布為Dm的訓(xùn)練數(shù)據(jù)集學(xué)習(xí)得到基本U-vMOS分類器Gm。計算分類器Gm的分類誤差em；

(3)

分類誤差em最小化是集成學(xué)習(xí)的最終目標，也是每次迭代中學(xué)習(xí)得到基本U-vMOS分類器的準則。其中xi表示樣本i的真實U-vMOS得分，yi表示樣本i的分類器預(yù)測U-vMOS值，wmi表示第m輪迭代中第i個樣本的權(quán)重，基本U-vMOS分類器Gm的分類誤差em表示為Gm錯誤分類樣本的權(quán)重之和，由此可以推斷訓(xùn)練集權(quán)重分布Dm與基本U-vMOS分類器Gm的分類性能有直接聯(lián)系;

3)計算Gm的權(quán)值系數(shù)αm，αm表示Gm(x)在最終分類器中的重要程度：

(4)

由式(3)可以推斷當em≤0.5時，αm≥0，且基本U-vMOS分類器Gm的αm隨著em的減小而增大，表明分類誤差em越小的基本U-vMOS分類器在最終U-vMOS分類器中作用越大;

4)分類誤差em小于閾值或是達到最大迭代次數(shù)時結(jié)束迭代;

5)更新訓(xùn)練數(shù)據(jù)集的權(quán)值分布，返回步驟2;

Dm+1=(wm+1，1，…wm+1，i，…，wm+1，N)

(5)

AdaBoost算法在式(4)環(huán)節(jié)以相同的比例增加錯誤分類樣本權(quán)重，更新得到數(shù)據(jù)集的權(quán)值分布Dm+1。以代價敏感的思想改進算法，引入代價敏感因子，修改樣本權(quán)重更新公式，具體公式如下：

Gm(xi)=a;yi!=a，a=1…Y

(6)

(7)

其中Zm是規(guī)范化因子，使得Dm+1成為一個概率分布。wmi是第m次迭代樣本i的權(quán)重，wm+1，i是第m+1次迭代樣本i的權(quán)重，Ca是引入的代價敏感因子，Y表示樣本U-vMOS得分。由式(5)可知，改進AdaBoost算法在每次迭代中更新樣本權(quán)重時，在區(qū)分樣本分類正確和樣本分類錯誤兩種情況的基礎(chǔ)上，進一步分析樣本U-vMOS得分，根據(jù)錯誤分類樣本的真實U-vMOS得分xi乘以代價敏感因子Ca，使不同錯誤分類樣本以不同比例增加權(quán)重，隨著迭代次數(shù)增加，學(xué)習(xí)得到的基本分類器Gm對多數(shù)類和少數(shù)類的識別能力都有所提高，最終分類器預(yù)測U-vMOS的性能得到提升。改進算法的時間復(fù)雜度顯然與弱分類器的構(gòu)造方法有關(guān)，并且其時間復(fù)雜度和空間復(fù)雜度與已有的AdaBoost 算法一樣。改進算法基于樣本單屬性構(gòu)造基本分類器，其時間復(fù)雜度為O(mdT)，其中，m 為訓(xùn)練樣本數(shù)，d 為樣本屬性個數(shù)，T 為弱分類器個數(shù)。因此改進算法是一個比較快的算法。

代價敏感因子Ca直接影響最終U-vMOS分類器性能，遍歷其可能取值需要大量計算，因此粒子群算法PSO(Particle Swarm Optimization)被用于調(diào)整代價敏感因子Ca參數(shù)。PSO算法結(jié)構(gòu)簡單控制容易，是一種啟發(fā)式全局優(yōu)化算法，通過設(shè)定適應(yīng)度函數(shù)，利用群體與粒子自身的適應(yīng)度來共同引導(dǎo)粒子向最優(yōu)解進化，保證了算法的快速收斂性，個別異常不影響整體的優(yōu)化粒子群算法，具有良好的魯棒性[22-23]。具體公式如下所示

Vi(t+1)=Vi(t)+c1(pbesti-Xi)+c2(gbesti-Xi)

(8)

Xi(t+1)=Xi(t)+Vi(t+1)

(9)

式(8)(9)中t代表迭代次數(shù)，i=1，2，…，M，i表示第i個粒子。Vi作為粒子速度決定粒子運動方向和距離，Xi代表粒子位置，c1和c2是兩個正常數(shù)，pbesti是本輪迭代全局最優(yōu)值，gbesti是歷史全局最優(yōu)值。粒子群算法首先隨機產(chǎn)生一群代價敏感因子，然后在每輪迭代中，通過跟蹤個體極值pbest和全局極值gbest兩個極值，每個粒子根據(jù)式(1)、(2)更新位置和速度，動態(tài)調(diào)節(jié)自身的搜索方向，尋找最優(yōu)代價敏感因子。

5 性能比較

從SpeedVideo獲取了三個數(shù)據(jù)集，總共包含89266個樣本。其中數(shù)據(jù)集1被用來訓(xùn)練和驗證模型，數(shù)據(jù)集2和數(shù)據(jù)集3被用來測試評估模型的F-measure。F-Measure是準確率和召回率的加權(quán)調(diào)和平均，同時考慮到了少數(shù)類的準確率和召回率，因此能衡量不平衡數(shù)據(jù)集下分類器的表現(xiàn)?；谏鲜雒枋?，選擇F-Measure作為分類器的性能指標。

粒子群優(yōu)化算法被用于調(diào)整改進AdaBoost算法中的代價敏感因子Ca。圖3顯示了PSO算法在數(shù)據(jù)集1上的調(diào)參曲線。

圖3 PSO調(diào)參曲線

圖3橫軸為迭代次數(shù)，縱軸為最終分類器的F-Measure值。本文實驗采用十折交叉驗證法進行實驗，將數(shù)據(jù)集分成十份，每次輪流取其中一份為測試集，其余九份為訓(xùn)練集。實驗取十次實驗的平均值為最終結(jié)果。粒子群初始參數(shù)設(shè)置每輪生成30組隨機解，最大迭代次數(shù)為50，圖中顯示，經(jīng)過25次迭代，算法F-Measure快速上升，隨著迭代次數(shù)的增加，F(xiàn)-Measure值最終趨于平緩，說明使用PSO算法調(diào)整代價敏感因子Ca可以有效提升最終分類器性能。

為了評估改進AdaBoost算法性能，設(shè)置改進AdaBoost算法和其它經(jīng)典分類算法的對比實驗，分別使用決策樹，樸素貝葉斯和KNN等分類算法在不平衡數(shù)據(jù)集上建立模型，使用F-Measure評估模型性能，具體評估結(jié)果如圖7所示。為了評估基于代價敏感思想的改進方案，設(shè)置改進算法和常用不平衡解決方法的對比實驗，分別采用欠采樣和過采樣方法結(jié)合AdaBoost算法在不平衡數(shù)據(jù)集上建立模型，使用F-Measure評估模型性能，具體評估結(jié)果如圖8所示。此外，考慮算法迭代次數(shù)，在圖9中對比迭代次數(shù)對改進AdaBoost算法和AdaBoost算法F-Measure的影響。

圖4顯示了改進AdaBoost算法和其它經(jīng)典分類算法的F-Measure。改進AdaBoost算法的F-Measure在三個數(shù)據(jù)集中都在95%左右，而其它分類算法的F-Measure在三個數(shù)據(jù)集中都在80%左右。顯然，改進AdaBoost算法的F-Measure高于其它算法。結(jié)果說明，基于代價敏感思想的改進方案可使AdaBoost算法F-Measure提升20%左右，可以有效解決U-vMOS分布不平衡問題，該方案使得分類器對于少數(shù)類樣本有更高的關(guān)注，對于移動網(wǎng)絡(luò)視頻流U-vMOS的預(yù)測能力得到有效提升。

圖4 不同算法F-Measure對比

圖5顯示了基于代價敏感方法和其它常用數(shù)據(jù)不平衡解決方法的F-Measure。測試集1中代價敏感方法，欠采樣方法和過采樣方法F-Measure都在90%以上，測試集2和測試集3中代價敏感方法F-Measure和數(shù)據(jù)集1中基本相同，都在95%左右，然而欠采樣和過采樣方法F-Measure都有明顯下降，僅有80%左右。結(jié)果說明，基于代價敏感思想的改進方案具有良好的魯棒性，欠采樣方法抽取U-vMOS得分高的樣本，丟失與多數(shù)類有關(guān)的重要概念，過采樣方法克隆U-vMOS得分低的樣本，導(dǎo)致過擬合，而基于代價敏感思想的改進方案僅僅改變賦予樣本的權(quán)重，可以完整保留數(shù)據(jù)集樣本信息，提高分類器對小類的關(guān)注，使U-vMOS分類器獲得優(yōu)秀的性能。

圖5 三種非均衡解決方法F-Measure對比

圖6中，經(jīng)過5次迭代，AdaBoost算法F-Measure已經(jīng)接近穩(wěn)定值，在接下來的20次迭代中緩慢增加，然后基本保持穩(wěn)定。而改進AdaBoost算法在25次迭代中F-Measure快速增加，最后基本保持穩(wěn)定。原因在于AdaBoost算法在前五次迭代中可以快速提高對于上一輪分類錯誤樣本的識別能力，但5次迭代后，多類樣本的權(quán)重造成分類器對多類樣本敏感，接下來的20次迭代中少數(shù)類樣本分類能力提高緩慢，最終導(dǎo)致AdaBoost算法在不平衡數(shù)據(jù)集中無法有效預(yù)測用戶U-vMOS。而改進AdaBoost算法在每輪迭代中，基于樣本分類正確和樣本分類錯誤兩種情況，進一步識別分類錯誤樣本類別，對不同類別分類錯誤樣本采取不同的加權(quán)策略，提高基本分類器對于小類樣本的關(guān)注，使U-vMOS最終分類器獲得優(yōu)秀的查準率和查全率。但是改進AdaBoost算法的F-Measure曲線波動明顯大于AdaBoost算法，可能原因是迭代中不同類別樣本權(quán)重相差較大。

圖6 F-Measure隨迭代次數(shù)變化曲線

6 結(jié)束語

在本文中，討論了不平衡數(shù)據(jù)集中移動網(wǎng)絡(luò)視頻流的U-vMOS評估模型。首先實驗結(jié)果表明，在數(shù)據(jù)非均衡條件下，基于代價敏感思想的改進方案可使AdaBoost算法F-Measure提升20%左右，分類用戶U-vMOS性能明顯優(yōu)于其它算法，且具有良好的穩(wěn)健性。其次，U-vMOS評估方案具有廣泛的應(yīng)用范圍，例如 它可以用于視頻服務(wù)提供商如bilibili和AcFun，以視頻為中心的移動應(yīng)用程序如抖音和快手，視頻游戲直播服務(wù)如虎牙，斗魚和企鵝，能夠在一個完善和統(tǒng)一的評估標準下，為提升視頻業(yè)務(wù)用戶體驗給出切實的指導(dǎo)建議。最后，為了繼續(xù)優(yōu)化網(wǎng)絡(luò)視頻流U-vMOS分類器性能，需要進一步研究樣本權(quán)重關(guān)系，降低算法迭代次數(shù)，節(jié)省時間成本。