基于文本擴展模型的網絡視頻聚類方法

劉璐，賈彩燕

伴隨著網絡多媒體技術不斷的應用和發展，網絡視頻作為一種重要的傳播媒介，憑借其豐富多彩的內容和便捷的傳播形式深受廣大網絡用戶的喜愛。網絡視頻分享應用及網站在其不斷發展中逐漸形成了獨特的特點，在這些網站上用戶可以申請上傳視頻，也可以從海量視頻中選擇觀看自己感興趣的視頻。在社會媒體平臺上廣泛存在的視頻具有如下特點：

1) 網絡視頻規模大，上傳更新速度快；

2) 通常以用戶制作內容和專業影視內容并存為主要特色，內容涉及電影、音樂、科技、汽車、親子、時尚、體育、財經、資訊等多個主題；

3) 不同于傳統圖像或文本，網絡視頻蘊含豐富的多模態信息：視頻的視覺圖像、標題、描述、標簽等文本信息，觀看用戶的評論，上傳用戶信息等；

4) 網絡視頻時長不等，剪輯水平不等。

如此規模宏大、類別眾多的網絡視頻在豐富互聯網信息，滿足用戶需求的同時，也給視頻數據的組織和管理帶來了嚴峻的挑戰。傳統的解決辦法是視頻上傳者或者網站管理員人工標注視頻的類別，然而這一方法耗時耗力，并且容易受到人為不穩定的主觀影響。有學者提出利用基于監督或半監督的視頻自動分類技術[1-2]，但是大部分分類方法仍舊需要充足的高質量訓練樣本。因此，研究人員嘗試利用無監督的機器學習模型——聚類來進一步組織網絡視頻數據，提出了多種基于文本、視覺及多模融合的視頻聚類方法[3-8]。另外，現有的視頻搜索引擎的搜索結果通常按與搜索詞的相關度進行排列，其中可能包含重復或相似視頻，為了給用戶提供更可觀、更易理解的搜索體驗，因而提出了基于文本特征、視覺特征或多特征融合的視頻搜索結果聚類方法[3-4]，便于對視頻按主題進行推薦。

單純基于視頻文本(如標題)的聚類可以利用已有文本聚類的成熟技術，考慮視頻的語義特征[4]，具有簡單、易用等特點。但視頻標題作為短文本，存在文本特征高維語義極度稀疏等問題。單純使用視覺相似性的視頻聚類方法[5]由于圖像語義理解的復雜性，存在維度高、復雜度高、聚類效果欠佳等問題。網絡視頻作為一種社會化媒體數據，形式豐富、模態多樣，包含視頻視覺內容、描述單一主題的標題文本、播單信息[6]、上傳及觀看用戶等。利用文本和視覺等多模態融合的視頻聚類方法[3,7]，可以增強單一方法視頻聚類的有效性，但存在時間復雜度高、最優加權方案不確定等問題。鑒于文本挖掘技術的成熟性和易用性，本文著眼于利用社會媒體上豐富的文本信息，以改善現有短文本方法的高維、語義稀疏問題，實現高效的視頻主題聚類，提出了以視頻標題、相關查詢詞、共點擊視頻標題等多類短文本信息融合的視頻主題聚類方法，并以優酷視頻網站(http://www.youku.com)真實數據為例，驗證了本文方法的有效性。

1 相關工作

1.1 網絡視頻聚類

目前，網絡視頻聚類已經取得一些研究成果，主要有基于視覺圖像的方法、基于文本特征的方法、基于視頻其他信息(如播放列表)的方法以及多模融合的方法。

Liu等[5]使用從視頻幀序列提取的全局視頻簽名特征(ViSig)來表征視頻，提出了基于視覺圖像相似度的視頻搜索結果聚類算法。Nguyen等[4]從網絡視頻的文本元數據(視頻標題、標簽和描述)角度出發，提出了基于WordNet知識庫的文本語義相似度計算方法，可以有效提高視頻搜索結果的聚類效果。文獻[3, 7]是基于視頻的多模態特征進行主題聚類。Hindle等[3]集成網絡視頻的視覺特征和文本特征，利用有界坐標系統(BCS)模型將視頻的視覺特征用緊湊簽名來表示，然而在計算文本相似度時，該方法將文本近似視為“詞袋”，直接統計兩個文本共有詞的個數，忽略了文本信息的高級語義知識。Huang等[7]針對網絡視頻包含的豐富信息，分別計算低層視覺圖像特征、高層語義特征和文本特征的相似度，然后將各個模態融合計算網絡視頻的實際相似度，并引入近鄰傳播的聚類算法進行網絡視頻聚類分析。Zhang等[8]從視頻語音轉錄文本和視覺概念識別兩方面提取視頻特征，提出二部圖聚類算法，表明在多源數據關聯挖掘方面效果要優于常規譜聚類。研究學者還利用網絡視頻豐富的社會媒體信息展開研究。Kamie等[6]提出PVClustring方法，構建視頻–播單關聯矩陣，采用重復二分的kmeans方法進行視頻聚類；Zhang等[9]利用You-Tube的共觀看視頻進一步改進網絡視頻分類系統的性能。

由此可見，研究人員嘗試利用不同的理論方法來解決視頻聚類問題。但是當前的研究中，使用低層視覺特征僅在識別雷同視頻時有較好的效果，同時由于視頻圖像語義理解的復雜性、以及海量、高維、語義不清晰等特點，現有的利用視頻信息的多模態融合方法對視頻聚類的效果還不能滿足實際需求，缺乏有效的主題聚類方法。

1.2 短文本聚類

伴隨著Web2.0時代，短文本數據在互聯網上應用日益增多，短文本聚類的相關工作也取得了很大的進展，研究者們嘗試利用很多方法來改進短文本語義分析與處理，大體上分為兩類。一類是挖掘短文本自身內容構建特征空間，Yin等[10]提出了應用吉布斯抽樣的狄利克雷混合模型算法(GSDMM)，在聚類過程中可以自動推斷出類別數量并快速收斂，能很好地適應短文本高維稀疏的狀況；Yan等[11]結合上下文語義相關性來建立詞項關聯矩陣，避免使用了短文本中高維稀疏的詞文檔矩陣，然后應用對稱非負矩陣分解算法獲取詞項–主題矩陣進而推斷每個文檔的主題。

另一類是利用外部知識庫來擴展短文本表示，Sahami等[12]通過利用網絡搜索結果擴展短文本內容，在擴展的基礎上計算文本間相似度；Yih[13]在Sahami的基礎上通過計算詞出現的加權內積而不是TFIDF，并引入了一個學習過程來提高相似性度量的準確性；Banerjee等[14]利用從短文本中提取出的字符串檢索維基百科中最相關的前10個文檔，并用這些文檔的標題擴充每個短文本文檔的表示，再對短文本進行聚類；Gabrilovich等[15]提出了一種顯示語義分析，將每個短文本映射到最相關的維基百科和ODP(開放目錄項目)的本體概念，用概念向量擴充傳統的詞袋模型表示；Hu等[16]同時采用內部特征和外部特征(維基百科和WordNet)來對短文本文檔進行擴充，提出了一個分層的三級結構來解決原始短文本的數據稀疏問題；Hotho等[17]將WordNet集成到文本聚類的過程，在Reuters語料庫的實驗結果顯示了它的有效性；Song等[18]利用開放的網頁構建了一個概率化知識庫，進而來推斷短文本文檔中的概念表示，然后再進行聚類。這些方法已經被證明能有效地提高短文本聚類，然而利用搜索引擎的短文本擴展方法時間復雜度高，在利用外部知識庫擴展的方法中，尋找合適的外部源也十分重要，但是由于互聯網的自由開放性，網絡視頻的標題文本一般由用戶上傳視頻時自己填寫，容易出現新興詞匯和網絡用語，語言表達方式和其他長文本文檔有著較大的差異，盲目地擴充可能會影響原短文本的語義。

2 網絡視頻表示

隨著視頻分享網站的不斷應用，網絡視頻不再僅僅是單一的視頻結構，而是作為一種豐富的多媒體信息包含了多源數據。網絡視頻的播放頁面，不僅包含具體的視頻內容，還包含標題、描述、標簽等用戶提供的文本信息，以及用戶之間評論、點贊、收藏等社交互動行為。在已有的研究工作中，文獻[7]的實驗表明利用標題等文本特征在視頻聚類上有較好的效果。同時，在實際工業應用中，利用視頻的圖像特征進行視頻表征時，存在圖像存儲占空間、時間復雜度高，只適用于短視頻或視頻畫面內容較集中的視頻等多種問題。本文研究使用視頻的多源文本信息來更準確地表示視頻，包括視頻標題、視頻相關查詢詞、共點擊視頻標題，利用這些信息進行聚類能夠從語義層次上有效識別視頻聚簇。僅使用標題短文本進行特征表示時由于字數較少，不同文本間缺乏足夠的詞共現信息，因而存在高維稀疏、特征模糊、語義不清晰問題，而視頻的相關查詢詞與該視頻往往語義相關，共點擊視頻的視頻標題和該視頻標題的詞匯也語義相似，利用這些信息可以進一步擴展文本內容，豐富文本表示。因此，本文提出一種多源數據下文本擴展模型進行網絡視頻表示，為聚類研究做好準備工作，以改善短文本高維稀疏的問題，有效實現主題聚類。本文方法的框架如圖1所示。

圖1 基于文本擴展模型的網絡視頻聚類方法框架Fig. 1 Framework for web video clustering based on extended text model

2.1 多源數據

2.1.1 網絡視頻標題

視頻的元信息(meta data)包括標題、描述和標簽等文本信息，準確的文字描述可以提供最直接有效的視頻語義信息，不同于標簽具有很大的噪音、描述只在較少視頻中出現，標題作為每個視頻都具備的一種短文本信息，可以很好地概括視頻的語義內容，是描述視頻的一項重要的文本特征。

2.1.2 相關查詢詞

每個視頻會對應一系列相關的查詢詞，這些查詢詞和該視頻的標題信息通常在語義上有很大的相關性，描述相關的視頻內容。

2.1.3 共點擊視頻

用戶在視頻網站的一個會話訪問過程中，觀看的視頻內容通常與用戶當時的興趣密不可分。因此，根據全網用戶的點擊觀看行為可以將每個視頻和一系列共點擊視頻相關聯，從一定程度來講，這一系列共點擊視頻和該視頻更傾向于內容相關，它們的標題更傾向于語義相關。這類比于文檔中的詞匯關系，如果兩個詞語在很多文檔中都頻繁共同出現，則這兩個詞語有很大可能是語義相關的。

2.2 文本擴展模型

針對網絡視頻的多源數據，本文構建了一個多源數據下的文本擴展模型，將短文本擴展成較長的文本以豐富語義內容，強化詞語的共現特征。針對每個網絡視頻，我們不僅可以獲得視頻標題(T1)，還可以得到該視頻的相關查詢詞(T2)，以及該視頻的共點擊視頻所對應的視頻標題(T3)。利用文本T2和文本T3分別去擴展原視頻標題即文本T1，構成新的長文本作為該視頻的文本表示。同時，利用T1、T2和T3合并構成長文本進行實驗對比。

在表1中，給出了數據集中部分視頻標題及它們相應的擴展文本。例如第一個視頻標題通過擴展可以補充“乒乓球”、“直拍”等詞匯，豐富了原視頻短文本的語義。

表1 模型示例Table 1 Model example

3 實驗與分析

為了定量地比較不同模型的性能，應用多種文本聚類算法進行實驗，然后從準確率和標準化互信息兩個方面進行分析，進而實現網絡視頻的聚類效果評估。

3.1 數據集

實驗數據集來源于優酷視頻(http://www.youku.com)，分為兩個子集(數據集1和數據集2)，均包含視頻標題、共點擊視頻、相關查詢詞等數據。數據集1中包含親子、汽車和科技共3個類別，數據集2中涉及廣告、搞笑、電影、體育、時尚、親子、汽車、拍客、旅游和科技共10個類別，每個類下的視頻數量更貼近于實際網絡中的分布情況，表2展示兩個數據集的相關統計信息。

表2 數據描述Table 2 Description of data sets

在得到每個視頻的文本表示之后，對文本的預處理過程如下：

1) 利用jcseg方法對文本進行切詞；

2) 過濾常用停用詞，以及在視頻短文本中的常用非重要詞匯，如“視頻”、“高清”等；3) 過濾文檔頻率df值小于10的詞匯；4) 過濾包含詞匯數目小于3的文檔。

3.2 評價函數

在實驗數據集中，每個視頻數據都已對應一個合理的類標簽，因此選取了準確率(ACC)和標準化互信息(NMI)作為評估聚類算法性能的指標。

準確率是一個普遍流行的聚類質量評價指標，指正確指派類標的文檔在所有文檔中所占的比例，定義如下：

標準化互信息用來刻畫一個數據集上的聚簇劃分結果和此數據集真實類標的相似程度，其定義如下：

3.3 實驗方法

本文對比實驗了4種網絡視頻的文本表示。

1) Title：只利用網絡視頻的標題(T1)作為該視頻的文本表示。

2) Co-query enhancement：利用網絡視頻的標題(T1)和相關查詢詞(T2)合并作為該視頻的文本表示。

3) Co-click enhancement：利用網絡視頻的標題(T1)和共點擊視頻所對應的標題序列文本(T3)合并作為該視頻的文本表示。

4) All enhancement：利用 T1、T2、T3合并作為該視頻的文本表示。

在以上文本擴展模型的基礎上，對比實驗了6種文本聚類算法，前3種方法是面向長文本設計的聚類算法，后3種是針對短文本的聚類方法：

1) latent dirichlet allocation (LDA)[19-20]：LDA 是一種文檔主題生成概率模型，本實驗采用吉布斯采樣學習LDA參數的Java實現，設置參數α為0.5，β為0.1，迭代次數為200次。

2) Kmeans++[21]：是基于相似度的聚類模型，在Kmeans算法的基礎上解決了需要人為確定初始聚類中心的問題，它選取的原則是初始聚類中心之間的距離要盡可能遠。

3) GNMF[22]：圖正則化非負矩陣分解模型，在NMF的基礎上，構建近鄰圖來考慮數據樣本中的幾何近鄰結構。

4) TNMF[11]：是在詞關聯矩陣上應用非負矩陣分解的話題模型，分為兩個連續的子過程，即話題學習和話題推斷。在詞關聯矩陣中應用對稱非負矩陣分解方法可以有效地避免傳統詞–文檔矩陣的稀疏性。設置參數λ為1。

5) GSDMM[10]：利用吉布斯抽樣算法的狄利克雷多項混合模型，能自動推斷出集群的數量，在集群的完整性和類內同質性之間達到平衡，收斂速度較快。設置參數α為0.1，β為0.1，迭代次數為100次。

6) biterm topic model(BTM)[23]：是一種雙詞話題模型，該模型通過直接對文檔中雙詞(即共現詞對)的產生進行建模來學習話題，避免了受短文本長度過短導致的內容稀疏性影響。

對于LDA、GSDMM、TNMF、BTM、GNMF等話題模型，我們將每個文本指派到其最大隸屬度所在的話題聚簇以實現聚類劃分。

3.4 實驗結果

在上述兩個數據集中分別設置聚簇數目為3和10，并根據已有類標簽分別計算準確率和標準化互信息，對于每一個方法我們重復運行10次計算平均值。

實驗結果如表3～6所示，在LDA、Kmeans++、GNMF方法上，經過文本擴展之后的視頻聚類效果要普遍優于只采用視頻標題進行特征表征的方法，尤其體現在NMI的變化上，原因在于通過多源數據下的文本擴充，一定程度上豐富了文本的語義信息，增強了詞共現特征，使長文本聚類方法的性能發揮更好。在TNMF方法上，co-query enhancement模型和all enhancement模型的效果提高最為明顯，說明擴展相關查詢詞相比共點擊視頻標題能盡可能避免加入噪音詞匯，提高實驗結果。在GSDMM和BTM兩種短文本聚類方法上，本文提出的多源數據模型效果不突出，原因在于這兩種方法更適用于語義突出的較短文本，在利用相關查詢詞或共點擊視頻標題進行擴充后帶來了不可避免的噪音文本，影響了短文本聚類效果。然而，在這兩種方法中NMI值有所提高，也印證了增加共點擊信息對于類大小不平衡的視頻數據有較好的提升效果。

表3 數據集1算法結果（ACC）Table 3 Result of algorithms on data set 1 (ACC)

同時對實驗結果進行橫向比較，在數據集1中all enhancement模型在GNMF文本聚類方法上取得了最好的效果，在數據集2中從模型優化效果來看，co-click enhancement模型在LDA文本聚類方法上整體效果要好，體現出合理利用視頻的相關信息可以達到最佳的視頻聚類效果，并且在本文提出的模型之上，長文本聚類方法的效果優于短文本聚類方法。

在10類真實數據集中，精確度和標準化互信息數值普遍不高，原因主要在于如今的互聯網視頻中，視頻內容眾多豐富，綜合類劃分之下的視頻可以細分為多個具體內容，比如體育類包含籃球、足球、搏擊等多項運動，造成聚簇特征不明顯，影響了聚類效果。

表4 數據集1算法結果（NMI）Table 4 Result of algorithms on data set 1 (NMI)

表5 數據集2算法結果（ACC）Table 5 Result of algorithms on data set 2 (ACC)

表6 數據集2算法結果（NMI）Table 6 Result of algorithms on data set 2 (NMI)

4 結束語

隨著網絡信息的爆炸式增長，文本聚類算法在很多數據挖掘工作中都發揮著越來越重要的作用，比如話題發現、個性化推薦、有效檢索等。本文提出了利用網絡視頻的多源數據構建文本擴展模型，從視頻標題、共點擊視頻、相關查詢詞等多角度進行補充表示，最后應用文本聚類算法在對文本進行劃分的同時實現網絡視頻的聚類。在兩個數據集上的多個實驗驗證了本文方法的有效性，進一步印證了利用外部信息進行擴展可以一定程度地提高網絡視頻聚類性能。但短文本聚類方法在本文提出的模型上效果欠佳，將在今后工作中進一步研究以提高改進。同時本文局限在利用文本信息擴展進行視頻表示，在之后的研究工作中考慮將共點擊視頻的網絡結構和視頻內容相結合，展開更深層次的研究。

[1]WU X, ZHAO W L, NGO C W. Towards google challenge:combining contextual and social information for web video categorization[C]//International Conference on Multimedia 2009. Vancouver, Canada, 2009: 1109–1110.

[2]YANG L, LIU J, YANG X, et al. Multi-modality web video categorization[C]//ACM Sigmm International Workshop on Multimedia Information Retrieval. Augsburg, Germany,2007: 265–274.

[3]HINDLE A, SHAO J, LIN D, et al. Clustering Web video search results based on integration of multiple features[J].World wide web, 2011, 14(1): 53–73.

[4]NGUYEN P Q, NGUYEN-THI A T, NGO T D, et al. Using textual semantic similarity to improve clustering quality of web video search results[C]//2015 IEEE Seventh International Conference on Knowledge and Systems Engineering(KSE). Ho Chi Minh, Vietnam, 2015: 156–161.

[5]LIU S, ZHU M, ZHENG Q. Mining similarities for clustering web video clips[C]//International Conference on Computer Science and Software Engineering. Wuhan, China,2008: 759–762.

[6]KAMIE M, HASHIMOTO T, KITAGAWA H. Effective web video clustering using playlist information[C]//Proceedings of the 27th Annual ACM Symposium on Applied Computing. Trento, Italy, 2012: 949–956.

[7]HUANG H, LU Y, ZHANG F, et al. A multi-modal clustering method for web videos[J]. Communications in computer and information science, 2013, 320: 163–169.

[8]ZHANG D Q, LIN C Y, CHANG S F, et al. Semantic video clustering across sources using bipartite spectral clustering[C]//IEEE International Conference on Multimedia and Expo. Taipei, China, 2004: 117–120.

[9]ZHANG J R, SONG Y, LEUNG T. Improving video classification via youtube video co-watch data[C]//Proceedings of the 2011 ACM Workshop on Social and Behavioural Networked Media Access. Scottsdale, USA, 2011: 21–26.

[10]YIN J, WANG J. A dirichlet multinomial mixture modelbased approach for short text clustering[C]//Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, USA,2014: 233–242.

[11]YAN X, GUO J, LIU S, et al. Learning topics in short texts by non-negative matrix factorization on term correlation matrix[C]//Proceedings of the 2013 SIAM International Conference on Data Mining. Austin, USA, 2013: 749–757.

[12]SAHAMI M, HEILMAN T D. A Web-based kernel function for measuring the similarity of short text snippets[C]//International Conference on World Wide Web, WWW 2006. Edinburgh, Scotland, UK, 2006: 377–386.

[13]YIH W, MEEK C. Improving similarity measures for short segments of text[J]. Proceedings of artificial intelligence,Pune, India, 2007: 1489–1494.

[14]BANERJEE S, RAMANATHAN K, GUPTA A. Clustering short texts using wikipedia[C]//SIGIR 2007: Proceedings of the, International ACM SIGIR Conference on Research and Development in Information Retrieval. Amsterdam, the Netherlands, 2007: 787–788.

[15]GABRILOVICH E, MARKOVITCH S. Feature generation for text categorization using world knowledge[C]//International Joint Conference on Artificial Intelligence.Morgan Kaufmann Publishers Inc, 2005: 1048–1053.

[16]HU X, SUN N, ZHANG C, et al. Exploiting internal and external semantics for the clustering of short texts using world knowledge[C]//ACM Conference on Information and Knowledge Management 2009. Hong Kong, China,2009: 919–928.

[17]HOTHO A, STAAB S, STUMME G. Wordnet improves text document clustering[C]//Proceedings of Semantic Web Workshop, the 26th annual International ACM SIGIR Conference. Toronto, Canada, 2003: 541–544.

[18]SONG Y, WANG H, WANG Z, et al. Short text conceptualization using a probabilistic knowledgebase[C]//Proceedings of the, International Joint Conference on Artificial Intelligence. Barcelona, Spain, 2011: 2330–2336.

[19]BLEI D M, NG A Y, JORDAN M I. Latent dirichlet allocation[J]. Journal of machine learning research, 2003, 3:993–1022.

[20]YANG L, QIU M, GOTTIPATI S, et al. CQArank: jointly model topics and expertise in community question answering[C]//Proceedings of the 22nd ACM International Conference on Information and Knowledge Management. San Francisco, USA, 2013:99–108.

[21]ARTHUR D, VASSILVITSKII S. k-means++:the advantages of careful seeding[C]//Eighteenth Acm-Siam Symposium on Discrete Algorithms 2007. New Orleans, USA,2007: 1027–1035.

[22]CAI D, HE X, HAN J, et al. Graph regularized nonnegative matrix factorization for data representation[J]. IEEE transactions on pattern analysis and machine intelligence,2010, 33(8): 1548–1560.

[23]YAN X, GUO J, LAN Y, et al. A biterm topic model for short texts[C]//International Conference on World Wide Web. Rio, Brazil, 2013: 1445–1456.