基于描述能力的視頻標題分類*

齊全 董晶

(北京理工大學(xué)計算機學(xué)院，北京100081)

視頻作為方便高效的記錄信息的載體已廣泛地應(yīng)用于人們的日常生活中.手機、數(shù)碼相機、數(shù)碼攝錄機等視頻攝錄設(shè)備的快速普及使人們傾向于使用視頻來捕捉和記錄信息，并通過互聯(lián)網(wǎng)平臺進行分享［1］.目前，互聯(lián)網(wǎng)平臺中已出現(xiàn)大量的視頻共享網(wǎng)站，有些大型網(wǎng)站的視頻數(shù)量甚至超過千萬級的規(guī)模，如優(yōu)酷網(wǎng)和土豆網(wǎng)等.要想在海量的互聯(lián)網(wǎng)視頻中找到用戶感興趣的視頻，就需要建立有效的視頻索引和查詢機制.因此，視頻搜索引擎具有廣闊的應(yīng)用前景.目前，視頻搜索技術(shù)已成為多媒體計算、自然語言處理和搜索引擎這幾個研究領(lǐng)域的共同課題.視頻檢索技術(shù)包括基于內(nèi)容的視頻檢索和基于文本的視頻檢索(TBVR).現(xiàn)階段，由于基于內(nèi)容的視頻檢索所需的運算量過高［2］，因此基于文本的視頻檢索仍是最流行的視頻檢索技術(shù).

基于文本的視頻檢索系統(tǒng)將視頻信息轉(zhuǎn)化成文本，通過對獲得的文本建立索引來進行視頻檢索.現(xiàn)有的主流視頻搜索引擎，如百度、谷歌等都使用基于文本的視頻檢索技術(shù)，并從視頻所在網(wǎng)頁上獲取視頻的文本信息.在基于文本的視頻檢索系統(tǒng)中，標題作為視頻信息的重要組成部分對精確的視頻檢索具有舉足輕重的作用.然而對于標題本身是否能夠準確描述視頻內(nèi)容這一問題，目前尚缺乏較為深入的研究.通過對來自優(yōu)酷網(wǎng)、土豆網(wǎng)等大型視頻網(wǎng)站的視頻及其標題的分析，發(fā)現(xiàn)許多視頻的標題不能準確概括視頻的內(nèi)容.因此，對基于文本的視頻檢索系統(tǒng)而言，找出那些不能準確表達視頻內(nèi)容的標題并加以處理，以提高系統(tǒng)的檢索精度是十分必要的.文獻［3-5］中對文本標題的自動分類進行了研究，文本標題與視頻標題的處理方法有類似之處.

通過分析大型視頻網(wǎng)站中視頻標題的特點，文中根據(jù)標題對視頻內(nèi)容的描述程度將標題的描述能力定義為可描述、可理解不可描述和不可理解3個等級;將視頻標題描述能力的評估問題看成分類問題，并使用支持向量機(SVM)［6］來實現(xiàn)自動分類.支持向量機本質(zhì)上是一個兩類分類器，其目標是尋找一個最優(yōu)超平面(或最優(yōu)超曲面，OHP)，使得兩類樣本之間的間距達到最大.它對于解決小樣本、非線性和高維模式識別問題具有很多的優(yōu)勢，并且在文本分類、手寫體識別、自然語言處理等方面得到了驗證［7-8］.

由于視頻標題通常很短，如果單純依賴標題本身的信息會產(chǎn)生數(shù)據(jù)稀疏問題，因此文中提出利用標題在互聯(lián)網(wǎng)搜索引擎中的搜索結(jié)果作為標題信息的補充，使用從汽車領(lǐng)域隨機選取的5000個視頻標題作為數(shù)據(jù)集進行分類實驗，并對實驗結(jié)果進行了分析.

1 視頻標題特點分析

筆者利用網(wǎng)絡(luò)爬蟲從優(yōu)酷網(wǎng)、土豆網(wǎng)等大型視頻網(wǎng)站上抓取了汽車領(lǐng)域的62305個視頻(包括標題等相關(guān)信息)，并從中隨機選取5000個作為分析樣本及實驗數(shù)據(jù).所抽取的視頻相關(guān)信息包括視頻的標題、標簽、簡介、評論和類別.通過分析發(fā)現(xiàn)，在這些文字信息中，標簽、簡介、評論等所包含的視頻信息十分有限.視頻上傳者通常只提供標題而不愿意提供視頻簡介和標簽，且大量視頻的評論內(nèi)容為空，這就使得標題成為最重要的信息來源.同時，視頻標題還具有以下幾個特點.

1)視頻標題含有大量領(lǐng)域詞匯.在隨機選取的5000個視頻中，含有領(lǐng)域詞的標題有3661個.領(lǐng)域詞主要有兩個來源:汽車品牌型號等領(lǐng)域詞匯(如“寶馬X5”、“法拉利”等)和汽車部件、汽車維修及汽車運動等汽車子領(lǐng)域詞匯(如“漂移”、“燒胎”等).另外，普通人很難理解其確切含義的很多名詞術(shù)語，如“移庫”、“倒樁”等，通常也很難被完全收錄到領(lǐng)域詞庫中.

2)視頻標題普遍不長.視頻標題通常很短，且包含大量領(lǐng)域詞匯等未登錄詞，因此標題分詞結(jié)果的準確率通常不高.但分詞結(jié)果作為評估標題長度的數(shù)據(jù)仍然具有一定的參考價值.文中采用中國科學(xué)院計算機研究所開發(fā)的分詞和詞性標注工具ICTCLAS對標題進行詞切分，使用分詞結(jié)果包含的詞語數(shù)作為標題的長度.5000個標題的平均長度為5.5，最長標題的長度為40，最短的為1.

3)很多視頻標題不具有描述視頻內(nèi)容的能力.視頻標題一般是視頻內(nèi)容最簡單明了的概括，如“上海通用雪佛蘭樂風(fēng)宣傳片”.因此標題被作為視頻檢索最重要的信息來源.5000個視頻標題中大部分標題具有描述視頻內(nèi)容的能力，但有相當多的視頻標題并不具備這個能力.其原因如下:

(1)由于視頻上傳者的疏忽，標題只能表現(xiàn)視頻的一部分信息，如“寶馬”作為標題只能說明視頻和寶馬車有關(guān)，但不能傳達視頻的具體內(nèi)容.有的標題完全不能傳達視頻內(nèi)容的任何信息，如標題“團結(jié)一心”.

(2)視頻上傳者為了吸引點播者的注意而故意使用不透露視頻內(nèi)容的標題，如“史上最強”、“全定制賽道怪物”等標題.

找到并處理描述能力不足的標題對提高目前視頻搜索引擎和視頻推薦系統(tǒng)的性能至關(guān)重要.

2 標題描述能力的分級及分類

2.1 標題描述能力的分級

不管是用于視頻檢索還是視頻推薦，視頻最終是要提供給使用者，并由使用者判斷根據(jù)標題信息提供的視頻是否和標題相符.事實上，標題與視頻相符需要滿足兩個要求:一是標題包含足夠的信息，使用戶可以猜出視頻的內(nèi)容;二是標題與視頻內(nèi)容一致.文中只針對標題是否滿足第一個要求進行研究，對于標題是否滿足第二個要求則需要對視頻內(nèi)容進行分析，因此不在文中討論的范圍內(nèi).文中以模擬用戶的判斷行為作為出發(fā)點，根據(jù)視頻標題對視頻內(nèi)容的描述程度將標題描述能力分為可描述、可理解不可描述和不可理解3個等級:

1)如果用戶看過標題后可以猜出視頻內(nèi)容，那么該標題的描述能力為可描述(D)，如標題“2010北京車展”.

2)如果用戶看過標題后不能猜出任何有關(guān)視頻內(nèi)容的信息，那么該標題的描述能力為不可理解(I)，如標題“史上最牛交警”.

3)如果用戶看過標題后能猜出視頻的一部分信息，但不能確定視頻的具體內(nèi)容，那么該標題的描述能力為可理解不可描述(IC)，如標題“豐田凱美瑞”.

2.2 視頻標題類型

按照標題描述能力的不同，將視頻標題分為3類:如果標題的描述能力為可描述，那么該標題屬于可描述類(D類);如果標題的描述能力為不可理解，那么該標題屬于不可理解類(I類);如果標題的描述能力為可理解不可描述，那么該標題屬于可理解不可描述類(IC類).

按照上述分類，采用人工方式對汽車領(lǐng)域的5000個視頻進行分類:指定3名標注人員分別標注5000個視頻標題.標注人員首先需要了解汽車領(lǐng)域的一些基礎(chǔ)知識，避免出現(xiàn)由于領(lǐng)域知識不足造成錯誤的分類結(jié)果.對于3人的標注結(jié)果采用以下的方式處理:(1)如果3人對同一標題標注的類別相同，則該標題屬于該類別;(2)如果3人對同一標題標注的類別不同，則由3人商議后決定該標題所屬類別.

5000個視頻標題的人工分類結(jié)果如下:550個無效視頻標題因標題重復(fù)以及含有亂碼等原因而無法用于評價;2455個視頻標題具有描述視頻內(nèi)容的能力，這也體現(xiàn)了視頻上傳者的視頻命名習(xí)慣，同時說明了搜索引擎利用視頻標題檢索視頻的合理性;1478個視頻標題不能描述視頻內(nèi)容;517個視頻標題的描述能力不足，如果把這些視頻標題直接用于檢索，視頻搜索和視頻推薦的準確度和用戶滿意度會受到極大的影響.

3 SVM分類器的構(gòu)造

SVM的基本思想是通過事先選擇的非線性映射(核函數(shù))將輸入向量x映射到一個高維特征空間，在這個空間中構(gòu)造最優(yōu)分類超平面，以期將兩類樣本無錯誤地分開(訓(xùn)練錯誤率為0)，而且要使兩類(標記為y，y∈{－1，1})的分類空隙最大，前者保證經(jīng)驗風(fēng)險最小，后者使推廣性的界中的置信范圍最小(即分類器的結(jié)構(gòu)風(fēng)險最小)，這樣可使在原始空間非線性可分的問題變?yōu)楦呔S空間中線性可分的問題［7］.

SVM的目標是尋找特征空間劃分的最優(yōu)超平面及其支持向量(SV)，首先需求出SV，然后求OHP.由于SV是到OHP:w·x+b=0的距離最近的樣本點，并且同一類的SV到OHP的距離完全相等，不同類的SV到OHP的距離不一定相等.因此，給定m個訓(xùn)練樣本(x1，y1)，(x2，y2)，…，(x m，ym)，要求一個分類超平面，關(guān)鍵在于求出分割超平面的法向量w和參數(shù)b.由于支持向量機理論要求分類超平面具有分類誤差小、推廣能力強的特點，這樣分類超平面必須滿足最優(yōu)分類超平面的以下兩個條件:

其中非線性函數(shù)φ(w)用于將數(shù)據(jù)從輸入空間映射到高維空間.為了找到最優(yōu)的分類超平面，可根據(jù)最優(yōu)化理論，借助Lagrange函數(shù)將原問題轉(zhuǎn)化為求解標準二次規(guī)劃問題:

多數(shù)樣本對應(yīng)的αi為0，少數(shù)不為0的αi(αi＞0)對應(yīng)的樣本即為支持向量，而相應(yīng)的最優(yōu)分類超平面(即分類決策函數(shù))為

式中:α=(α1，α2，…，αm)，每個αi為Lagrange乘數(shù);K(x i，x j)為核函數(shù)，用于計算一對輸入向量在高維空間中的內(nèi)積.求最優(yōu)平面的關(guān)鍵在于求出可以滿足αi＞0的αi以及

標題分類是一個多值分類問題，多值分類問題通常使用多個二值支持向量機的組合來解決，主要有一對多組合模式和一對一組合模式，其中一對一組合模式已經(jīng)被證明其性能優(yōu)于一對多組合模式［9］，因此文中選用一對一組合模式，采用LIBSVM［10］軟件包實現(xiàn)標題分類器的構(gòu)建.

4 標題分類中的特征選取

特征選取就是針對特定的目標或任務(wù)為模型選擇恰當?shù)奶卣骷?在人工標注的過程中，標注人員發(fā)現(xiàn)上傳者通常更愿意在標題中使用熟悉的詞匯描述視頻內(nèi)容，例如“測評”、“發(fā)布會”等.因此，視頻主題相近的標題所使用的詞語也十分相近.文中只使用詞作為SVM的特征.詞根據(jù)來源分為兩類:第一類是標題的分詞結(jié)果及分詞個數(shù);第二類是標題的搜索結(jié)果中所包含的領(lǐng)域詞.

4.1 分詞結(jié)果特征

分詞結(jié)果是將標題用分詞工具進行分詞后得到的分詞集合.文中使用中國科學(xué)院計算機研究所開發(fā)的ICTCLAS作為分詞工具，并在分詞詞庫中導(dǎo)入了汽車領(lǐng)域的詞匯，如汽車商標、型號、配件等.分詞結(jié)果中的停用詞是不作為特征使用的.

一般來講，越長的標題所含的關(guān)于視頻的信息量越多，標注人員越容易將它標成可描述類，因此文中將標題長度作為特征之一.如前所述，雖然分詞準確度不高，但作為度量標題長度的手段，分詞結(jié)果包含的詞語數(shù)仍具有參考價值.因此文中將標題通過分詞工具得到的分詞個數(shù)(不包含停用詞)作為標題的長度.

4.2 標題搜索結(jié)果特征

由于標題本身的特點和視頻上傳者在命名標題時常常使用簡寫和新詞，因此分詞結(jié)果的準確率不是很高.在隨機抽取的200個標題的分詞結(jié)果中，只有113個結(jié)果完全正確.其中，大部分錯誤是由于汽車領(lǐng)域詞沒有被正確切分識別引起的，比較典型的錯誤是詞語被錯誤地切開，如將“測評”分為“測”和“評”.為彌補分詞的不足，文中利用視頻標題在搜索引擎中的搜索結(jié)果來發(fā)現(xiàn)標題中未被正確切分的領(lǐng)域詞.

互聯(lián)網(wǎng)存放著大量有價值的信息，是一個重要的動態(tài)的信息來源.而搜索引擎作為搜索互聯(lián)網(wǎng)信息的重要工具也常常被用來作為抽取信息的工具［11-12］.

首先，將視頻標題作為查詢條件送到互聯(lián)網(wǎng)搜索引擎中，搜索結(jié)果作為和標題最相關(guān)的文本保存下來.為保證返回文檔和查詢的相關(guān)性，只有排名靠前的文檔被保存下來.如圖1所示，文中使用百度搜索引擎作為查詢工具，只保留返回文檔的標題.

圖1 視頻標題的搜索結(jié)果示例Fig.1 Examples of searching results of video title

標題的分詞結(jié)果中領(lǐng)域詞被分錯的主要原因是領(lǐng)域詞被錯誤地切開，因此識別領(lǐng)域詞的任務(wù)變?yōu)檎业奖徽`切開的領(lǐng)域詞并將其重新合并起來.文中利用分詞結(jié)果中的相鄰詞在搜索結(jié)果中共現(xiàn)的次數(shù)來計算相鄰詞的相關(guān)度，相關(guān)度高的詞序列對視為候選領(lǐng)域詞.隨后，計算候選詞在汽車領(lǐng)域視頻標題中出現(xiàn)的次數(shù)，出現(xiàn)次數(shù)多的被認為是領(lǐng)域詞.這些領(lǐng)域詞將作為視頻標題的特征用于標題分類.

同時，為了避免特征向量過于稀疏，并利用返回結(jié)果的相關(guān)性，文中將返回文檔的標題中出現(xiàn)的汽車領(lǐng)域的詞語作為標題的補充信息，并作為SVM的特征向量.

4.3 特征值的提取過程

由于SVM分類器所使用的特征都是數(shù)字型，為此需要將特征編碼為數(shù)字，并提取相應(yīng)特征項的特征值.

文中將詞語的詞頻作為詞語的特征.對于分詞結(jié)果特征，詞語的詞頻是該詞出現(xiàn)在所在標題中的次數(shù).對于標題搜索結(jié)果特征，詞語分為兩種:(1)存在于標題中但沒有被分詞工具識別出的詞語，對于這種詞語，文中將詞語在視頻標題中出現(xiàn)的次數(shù)作為特征;(2)返回的搜索結(jié)果中標題包含的領(lǐng)域詞，對于這種詞語，文中使用詞語在同一視頻標題的搜索結(jié)果中出現(xiàn)的次數(shù)作為特征.為了降低模型的訓(xùn)練時間，文中對特征向量進行了降維:如果一個分量在所有特征向量中非0的次數(shù)小于C，則在所有特征向量中刪除該分量.實驗中取C=2.

經(jīng)過過濾，分詞結(jié)果特征數(shù)為3976，其中包含標題長度特征;標題搜索結(jié)果特征數(shù)為2017.全部特征數(shù)為5993.

5 實驗及結(jié)果分析

使用2.2節(jié)中人工標注的5000個視頻標題作為實驗數(shù)據(jù)集，其中可描述類(D類)標題有2 455個，不可理解類(I類)標題有1478個，可理解不可描述類(IC類)標題有517個，無效標題有550個.對于有效的4 450個視頻標題，將每個視頻標題送到百度搜索引擎中進行查詢，將前30個返回結(jié)果的標題保存下來作為視頻標題的補充信息.4450個視頻標題隨機分成數(shù)目相等的5組，其中4組作為訓(xùn)練集，1組作為測試集.測試集中，D類標題有537個，I類標題有290個，IC類標題有63個.

為了測試使用不同的特征集對分類效果的影響，文中采用了兩組特征集:特征集1只包含分詞結(jié)果特征;特征集2包含分詞結(jié)果特征和標題搜索結(jié)果特征.

為了評價不同分類器的標題分類效果，分別使用學(xué)習(xí)記憶模型(MBL)、樸素貝葉斯(NB)、SVM 3種分類方法進行實驗.其中，SVM核函數(shù)選取RBF函數(shù).

對分類性能進行評估時，采用常用的3個評測指標:準確率(P)、召回率(R)、綜合指標F值(F):

其中F值是綜合評價P和R的指標，β是用來表明實驗側(cè)重于P還是R，本實驗中β設(shè)定為1.

文中分別在兩種特征集上測試了不同分類方法的分類效果，結(jié)果如表1－3所示.

表1 D類標題的分類結(jié)果對比Table 1 Comparison of classification results for D titles%

表2 IC類標題的分類結(jié)果對比Table 2 Comparison of classification results for IC titles%

表3 I類標題的分類結(jié)果對比Table 3 Comparison of classification results for I titles%

從表1－3中可以看到，對于IC類標題，3種分類方法的P、R和F很低;對于D類標題，SVM在特征集2上的P、R、F值分別達到了84%、73%和79%，較高的準確率確保了通過文中方法獲得的可描述標題的可靠性.通過分析IC類標題，發(fā)現(xiàn)該類標題中的詞語也常在可描述類標題中出現(xiàn)，例如“寶馬X5”屬于可理解不可描述類，但“寶馬X5試駕”及“寶馬X5測評”等屬于可描述類的標題.表4為使用SVM和特征集2得到的混淆矩陣.在計算相似度時，IC類標題更傾向于被標成D類.而IC類的標題數(shù)量較少也影響了該類標題的分類效果.因此，文中只關(guān)注D類和I類的實驗結(jié)果.

表4使用特征集2和SVM得到的混淆矩陣Table 4 Confusion matrix based on feature set2 and SVM

通過比較特征集1和2的分類效果，發(fā)現(xiàn)在使用標題搜索結(jié)果特征后，3種分類方法對D類和I類識別的P、R和F值都有所提升，其中SVM對D類和I類識別的F值都提高了3%.由此可以認為，標題搜索結(jié)果特征可以提升分類的效果.

兩個特征集上的實驗結(jié)果(表1－3)都表明:3種分類方法中，SVM對于D類和I類的分類效果均優(yōu)于MBL、NB.因此，可以認為SVM對視頻標題的分類效果優(yōu)于MBL、NB.

6 結(jié)語

文中根據(jù)視頻標題對視頻內(nèi)容的刻畫程度將標題的描述能力分為可描述、可理解不可描述和不可理解3個等級.通過自動分類的方法實現(xiàn)對標題描述能力的評估.為豐富視頻標題的信息，文中引入了標題在搜索引擎中的搜索結(jié)果作為標題信息的補充.由于SVM對小樣本分類問題有很好的識別效果，因此文中將SVM作為分類模型.實驗結(jié)果表明，SVM的分類性能優(yōu)于NB和MBL;搜索結(jié)果作為標題補充可以提升分類的效果.進一步的研究將在以下兩個方面進行:(1)分析視頻標題的語義信息并將其應(yīng)用于分類技術(shù)中;(2)標題在搜索引擎中的返回結(jié)果與標題本身的相關(guān)性.

［1］張鹿.基于內(nèi)容的視頻搜索結(jié)果優(yōu)化［D］.合肥:中國科技大學(xué)計算機學(xué)院，2010:1.

［2］Mu Xiang-ming.Content-based video retrieval:does video's semantic visual featurematter?［C］∥Proceedings of the 29th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval.Washington:ACM，2006:679.

［3］戰(zhàn)學(xué)鋼，姚天順.基于語義分析的標題分類方法［C］∥中文信息處理國際會議論文集.北京:清華大學(xué)出版社，1998:321-324.

［4］陳磊.基于HNC語義分析的中文標題分類方法［C］∥全國第五屆計算機語言聯(lián)合學(xué)術(shù)會議論文集.北京:清華大學(xué)出版社，1999:371-375.

［5］Song D，Lau R Y K，Bruza PD，et al.An intelligent information agent for document title classification and filtering in document-intensive domains［J］.Decision Support Systems，2007，44(1):251-265.

［6］Kotsiantis S B.Supervised machine learning:a review of classification techniques［J］.Informatica，2007，31(3):249-268.

［7］張學(xué)工.關(guān)于統(tǒng)計學(xué)習(xí)理論與支持向量機［J］.自動化學(xué)報，2000，26(1):32-42.Zhang Xue-gong.Introduction statistical learing theory and support vectormachine［J］.Acta Automatica Sinica，2000，26(1):32-42.

［8］Li Lishuang，Mao Tingting，Huang Degen，et al.Hybrid models for Chinese named entity recognition［C］∥Proceedings of the Fifth SIGHANWorkshop on Chinese Language Processing.Sydney:Association for Computational Linguistics，2006:72-78.

［9］Hsu CW，Lin C J.A comparison of methods for multiclass support vectormachines［J］.IEEE Transactions on Neutral networks，2002，13(23):415-425.

［10］Chang C，Lin C.LIBSVM:a library for support vector machines［EB/OL］.(2001-05-15)［2011-04-01］.http:∥www.csie.ntu.edu.tw/～cjlin/libsvm.

［11］Bollegala D，Matsuo Y，Ishizuk M.Measuring semantic similarity between words usingWeb search engines［C］∥Proceedings of the 16th International Conference on World Wide Web.New York:ACM，2007:757-766.

［12］Sahami M，Heilman T.AWeb based kernel function for measuring the similarity of short text snippets［C］∥Proceedings of the 15th International World Wide Web Conference.Scotland:ACM，2006:377-386.