一種移動網絡視頻流U-vMOS分類算法

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

(廣東工業大學信息工程學院，廣東 廣州510080)

1 引言

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

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

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

為了解決上述問題，本文提出結合代價敏感思想改進AdaBoost算法用來評估用戶U-vMOS。由于用戶體驗質量差的情況僅占極少數，U-vMOS值分布不平衡，然而大多數的機器學習算法均不適用于非均衡的數據集。目前，解決不平衡數據問題的研究主要集中在抽樣方法上[16]。與抽樣方法相比，結合代價敏感思想的改進AdaBoost算法保留所有樣本，只改變賦予樣本的權重，可以提高分類器對小類的關注，使U-vMOS分類器獲得優秀的性能，采用完善和統一的U-vMOS標準評估視頻業務體驗能夠為運營商和視頻產業鏈提升用戶體驗給出切實的指導建議。

2 數據說明

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

圖1 數據集U-vMOS得分

3 數據處理

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

(1)

表1 皮爾遜相關系數法計算結果

4 改進AdaBoost算法

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

圖2 改進AdaBoost算法流程圖

改進AdaBoost算法步驟如下：

1)初始化所有訓練樣本權重分布：

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

(2)

其中D1表示數據集初始權重分布，w1i表示樣本i的初始權重，N表示樣本數量。樣本權重相同即表示每個樣本在基本U-vMOS分類器G1的學習中作用相同；

2)開始迭代。使用權值分布為Dm的訓練數據集學習得到基本U-vMOS分類器Gm。計算分類器Gm的分類誤差em；

(3)

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

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

(4)

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

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

5)更新訓練數據集的權值分布，返回步驟2;

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

(5)

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

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

(6)

(7)

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

代價敏感因子Ca直接影響最終U-vMOS分類器性能，遍歷其可能取值需要大量計算，因此粒子群算法PSO(Particle Swarm Optimization)被用于調整代價敏感因子Ca參數。PSO算法結構簡單控制容易，是一種啟發式全局優化算法，通過設定適應度函數，利用群體與粒子自身的適應度來共同引導粒子向最優解進化，保證了算法的快速收斂性，個別異常不影響整體的優化粒子群算法，具有良好的魯棒性[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代表迭代次數，i=1，2，…，M，i表示第i個粒子。Vi作為粒子速度決定粒子運動方向和距離，Xi代表粒子位置，c1和c2是兩個正常數，pbesti是本輪迭代全局最優值，gbesti是歷史全局最優值。粒子群算法首先隨機產生一群代價敏感因子，然后在每輪迭代中，通過跟蹤個體極值pbest和全局極值gbest兩個極值，每個粒子根據式(1)、(2)更新位置和速度，動態調節自身的搜索方向，尋找最優代價敏感因子。

5 性能比較

從SpeedVideo獲取了三個數據集，總共包含89266個樣本。其中數據集1被用來訓練和驗證模型，數據集2和數據集3被用來測試評估模型的F-measure。F-Measure是準確率和召回率的加權調和平均，同時考慮到了少數類的準確率和召回率，因此能衡量不平衡數據集下分類器的表現。基于上述描述，選擇F-Measure作為分類器的性能指標。

粒子群優化算法被用于調整改進AdaBoost算法中的代價敏感因子Ca。圖3顯示了PSO算法在數據集1上的調參曲線。

圖3 PSO調參曲線

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

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

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

圖4 不同算法F-Measure對比

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

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

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

圖6 F-Measure隨迭代次數變化曲線

6 結束語

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