基于相似圖片聚類的Web 文本特征算法

方 爽,殷俊杰,徐武平

(武漢大學(xué)計算機學(xué)院,武漢 430072)

1 概述

隨著互聯(lián)網(wǎng)信息爆炸式的增長,由于圖片在表達能力上相對于文字擁有的先天優(yōu)勢,已經(jīng)被越來越多應(yīng)用于信息的承載和內(nèi)容的表達[1],各大搜索引擎公司如Google,Yahoo 和百度等都推出了圖片搜索功能。

傳統(tǒng)圖像檢索方式分為2 種：一種是基于文本的圖像檢索(Text-based Image Retrieval,TBIR),如文獻[2-3]所述；另一種是基于內(nèi)容的圖像檢索(Content-based Image Retrieval,CBIR),如文獻[4]所述。因為前者技術(shù)比較成熟,所以目前主流搜索引擎均采用基于文本關(guān)鍵詞的圖像搜索技術(shù)。其在假設(shè)網(wǎng)頁圖片周邊的文本可以表達圖片本身內(nèi)容的基礎(chǔ)上,從Web 網(wǎng)頁的相關(guān)文本中提取圖像的關(guān)鍵信息,建立文本索引數(shù)據(jù)庫,用戶利用關(guān)鍵詞進行檢索[5]。然而當(dāng)網(wǎng)頁存在作弊、文本描述圖片有偏差或頁面分析對文本提取錯誤的情況下,都會出現(xiàn)圖片和索引文本項不符的問題,其產(chǎn)生的根本原因是在倒排索引中某些關(guān)鍵詞對應(yīng)的圖片鏈表中包含了實際與關(guān)鍵詞沒有相關(guān)性的圖片,并最終反映到搜索結(jié)果當(dāng)中。為解決上述問題,文獻[6]提出了一種融合文本圖像相關(guān)性關(guān)聯(lián)的Web 圖像多超圖譜聚類方法,文獻[7]提出了將基于文本的圖像檢索和基于內(nèi)容的圖像檢索相結(jié)合的方法,文獻[8-9]提出了2 種不同的圖像檢索結(jié)果重排序的方法。本文提出一種基于相似圖片聚類的Web 文本特征算法,以解決圖片和索引文本項不符的問題。

2 網(wǎng)頁聚類信息的抓取

百度和谷歌等搜索引擎的網(wǎng)絡(luò)爬蟲已經(jīng)在互聯(lián)網(wǎng)上收集了數(shù)十億張圖片,并以圖片內(nèi)容相似性作了聚類,同一聚簇中的圖片有相似的內(nèi)容,每張圖片對應(yīng)一個來源網(wǎng)頁。通過百度的以圖搜圖功能,在用戶輸入一張圖片得到相似圖片結(jié)果后,修改當(dāng)前結(jié)果頁面鏈接的URL 參數(shù)tn=baiduimagepc 為tn=baiduimagejson,即可得到一頁檢索結(jié)果的json 格式數(shù)據(jù)。通過分析結(jié)果頁面的json 格式數(shù)據(jù)可以得到本聚類的大小(imgNum),聚類中每張圖片的鏈接地址(objURLEnc),每張圖片對應(yīng)的來源網(wǎng)頁的鏈接地址(fromURLEnc),每個來源網(wǎng)頁的主站鏈接地址(fromURLHost)等聚類信息。

3 Web 文本特征分析

在獲取聚類信息中的來源網(wǎng)頁集地址(fromURLEnc)后,便可以對其中每個網(wǎng)頁進行鏈接分析和HTML 標(biāo)簽解析,網(wǎng)頁主視覺區(qū)域識別、詞素切分、詞性標(biāo)注、停用詞去除等Web 結(jié)構(gòu)分析和Web 內(nèi)容分析。

3.1 鏈接分析

在互聯(lián)網(wǎng)上,如果一個網(wǎng)頁被很多其他網(wǎng)頁所鏈接,說明它受到普遍的承認(rèn)和信賴,其質(zhì)量是有保證的(一般有專業(yè)的編輯,并且在網(wǎng)頁發(fā)布前需要經(jīng)過嚴(yán)格審核),文中把這樣的網(wǎng)頁看作“高質(zhì)量”網(wǎng)頁。而那些出現(xiàn)圖文不符情況的網(wǎng)頁,一般是故意作弊或者編輯水平較低,責(zé)任心不強的網(wǎng)頁,其受到承認(rèn)和信賴的可能性較小,文中稱其為“低質(zhì)量”網(wǎng)頁。

PageRank 算法[10]是Google 用來標(biāo)識網(wǎng)頁質(zhì)量的一種方法,并且Google 對外提供的API 可以通過輸入網(wǎng)頁URL 查詢其PageRank值,本文直接引用了Google 的PageRank值來評價網(wǎng)頁的質(zhì)量。對來自同一聚類中高質(zhì)量網(wǎng)頁(高PageRank值)的特征文本提高其權(quán)重,對于來自低質(zhì)量網(wǎng)頁(低PageRank值)的特征文本降低其權(quán)重,以使得存在圖文不符的網(wǎng)頁對最終的特征文本貢獻度很小,并且傾向于相信高質(zhì)量網(wǎng)頁中挖掘出的特征文本,一般對最終的結(jié)果有正向影響。

3.2 結(jié)構(gòu)分析

在網(wǎng)頁中,不同HTML 標(biāo)簽中的文本其權(quán)重是不同的。例如,文章標(biāo)題標(biāo)簽中的文本比正文更重要。為了區(qū)別不同HTML 標(biāo)簽中文本的權(quán)重,經(jīng)過HTML 解析后,本文將各HTML 標(biāo)簽歸為以下類型：(1)頁面標(biāo)題(title,顯示在Web 瀏覽器頂端的標(biāo)題)；(2)文章標(biāo)題(主視覺域中的標(biāo)題)；(3)圖片替換文本(Alt)；(4)導(dǎo)航位置(當(dāng)前網(wǎng)頁所處的站點路徑,例如：首頁＞學(xué)院新聞＞教務(wù))；(5)網(wǎng)頁關(guān)鍵詞(meta keywords 標(biāo)簽)；(6)精確相關(guān)文本(網(wǎng)頁主視覺域中正文文本)；(7)疑似精確相關(guān)文本(網(wǎng)頁主視覺域中非正文文本)；(8)普通相關(guān)文本(非主視覺域中文本)。

網(wǎng)頁主視覺域的識別根據(jù)瀏覽器提供的API 接口確定,本文采用文獻[11]方法抽取網(wǎng)頁的正文文本。最后賦予每種不同類型HTML 標(biāo)簽中文本不同的權(quán)重,即可區(qū)分重要信息和一般信息。

3.3 文本分析

完成HTML 解析后,便可對每個標(biāo)簽中的文本作詞素切分和詞性標(biāo)注,根據(jù)不同的粒度,切分結(jié)果有所不同。例如“中華人民共和國”,基本詞切分結(jié)果為：“中華”,“人民”,“共和”,“國”；短語切分結(jié)果為：“中華人民共和國”,“中華人民”,“人民共和國”,“共和國”。

基本詞切分結(jié)果由于切分粒度太細(xì),分析出的高相關(guān)文本一般是出現(xiàn)頻率很高但是沒有區(qū)分度的詞,往往不能反映圖片的真實文本。例如,在圖片內(nèi)容為小提琴的網(wǎng)頁中,“小提琴”這個詞在基本詞切分中會被切分為“小”和“提琴”。由于“小”是個高頻詞,最后很可能被識別為高相關(guān)文本,但是實際卻與圖片相關(guān)性很低。根據(jù)實驗對比,取混排結(jié)果(由有序的基本詞和短語構(gòu)成)和短語結(jié)果的并集效果比較好。

詞性標(biāo)注模塊可以對詞素切分后的每個基本詞或短語單元標(biāo)注其在句子中的詞性。在漢語中,名詞、動詞、形容詞組成句子的主干,副詞、數(shù)詞、代詞等所代表的意義并不大,助詞、連詞、代詞、介詞、擬聲詞等虛詞只起修飾作用[12],因此,根據(jù)詞性篩選詞語是必要的。在實驗中,對詞性為語素字、數(shù)詞、介詞、前接成分、后接成分、連詞、區(qū)別詞、量詞、代詞、嘆詞、擬聲詞、習(xí)用語、標(biāo)點符號、非語素字以及英文字符串進行了過濾。本文將詞素切分后的結(jié)果標(biāo)注為下列詞性之一：形語素(形容詞性語素),形容詞,副形詞(直接作狀語的形容詞),名形詞(具有名詞功能的形容詞),區(qū)別詞,連詞,副語素(副詞性語素),副詞,嘆詞,方位詞,語素(絕大多數(shù)語素都能作為合成詞的“詞根”),前接成分,成語,簡稱略語,后接成分,習(xí)用語,數(shù)詞,名語素(名詞性語素),名詞,人名,地名,機構(gòu)團體,外文專名(一般是全角英文專名),其他專名,擬聲詞,介詞,量詞,代詞,處所詞,時語素(時間詞性語素),時間詞,助詞,動語素(動詞性語素),動詞,副動詞(直接作狀語的動詞),名動詞(指具有名詞功能的動詞),標(biāo)點符號,非語素字(非語素字只是一個符號),語氣詞,狀態(tài)詞。

通過賦予每種詞性不同的權(quán)值,例如給予名詞、人名等較高的權(quán)重,代詞、副詞等較低的權(quán)值,就能夠很好地反映語句的主干,提高文本挖掘的相關(guān)性。

停用詞的去除比較簡單,可以配一個停用詞表,對于出現(xiàn)在其中的詞或者某些特定詞性的詞,例如連詞、介詞、冠詞,直接在切詞后的結(jié)果中刪除即可。

4 特征文本的權(quán)值計算

對同一聚類中的網(wǎng)頁進行分詞,然后對分詞后的每個keyword 計算權(quán)值,再根據(jù)事先設(shè)定好的閾值或者排名的百分比,把keyword 分為高相關(guān)文本、一般相關(guān)文本以及不相關(guān)文本。

每個keyword 權(quán)值的計算主要參考以下方面：

(1)網(wǎng)頁的PageRank值,PageRank值高的網(wǎng)頁出現(xiàn)圖文不符的概率很小,這類網(wǎng)頁通常可信度更高,圖文相關(guān)性更好。

(2)詞頻(刪除停用詞后),對于同一聚類出現(xiàn)頻率較低的文本可能來自于少數(shù)低質(zhì)量頁面,與圖片相關(guān)性不高。

(3)keyword 出現(xiàn)的HTML 標(biāo)簽,同一keyword出現(xiàn)在圖片替換文本Alt 中一般比出現(xiàn)在正文中更重要。

(4)keyword 在句子中的詞性,一般名詞、形容詞在句子中比較重要權(quán)值比介詞、代詞等高。

(5)keyword 所在網(wǎng)頁的長度,網(wǎng)頁長度越長keyword 可能獲得的權(quán)重就越大,所以,keyword 的權(quán)值應(yīng)該在某種程度上受到網(wǎng)頁長度的影響。

(6)keyword 是否在主內(nèi)容塊中,一般商業(yè)頁面常帶有導(dǎo)航條和廣告等與主題無關(guān)的內(nèi)容,而主內(nèi)容塊才是與圖片較為相關(guān)的部分,可給主內(nèi)容塊中出現(xiàn)的文本更高的權(quán)值。

對整個網(wǎng)頁集中每個keyword 權(quán)值的具體算法如下：

本文從Google 公開的API 接口查詢聚類對應(yīng)的每個網(wǎng)頁的PageRank值。PageRank的取值范圍是0～10。對于Google 未收錄而導(dǎo)致查詢不到PageRank值的網(wǎng)頁,這類網(wǎng)頁一般比較新,可能是剛剛發(fā)布的新聞類網(wǎng)頁,對于這種情況文中采用一種簡單有效的方法,取其PageRank值為整個站點PageRank的平均值。Google 未收錄的原因也可能是這個網(wǎng)頁不太流行(其質(zhì)量也通常不高),對于這種情況默認(rèn)其PageRank為0。

記網(wǎng)頁j的PageRank值為PageRank(j),由于PageRank(j)的取值范圍是0～10,因此,有必要對其歸一化,經(jīng)過實驗對比,本文采用表1 的映射關(guān)系將PageRank(j)歸一化為P(j)。

表1 PageRank 值與網(wǎng)頁質(zhì)量權(quán)重系數(shù)的映射

經(jīng)過HTML 解析和詞素切分后,文中將每個關(guān)鍵詞i根據(jù)其來源的HTML 標(biāo)簽,賦予不同的權(quán)重,記為T(i),通過多組實驗對比,算法中采用的HTML標(biāo)簽權(quán)重系數(shù)如表2 所示。

表2 HTML 標(biāo)簽的權(quán)重系數(shù)

同樣在句子中不同語法成分對于句子意思表達的作用也是不同的,對切詞后的每個詞素單元i根據(jù)其不同的詞性賦予不同的詞性權(quán)重系數(shù),記為S(i)。所以,關(guān)鍵詞i在特定網(wǎng)頁中的每次出現(xiàn),其權(quán)值Wkw(i)計算公式為：

其中,α+β=1。通過上式,可以獲得每個關(guān)鍵詞在網(wǎng)頁中每次出現(xiàn)的權(quán)值。假設(shè)關(guān)鍵詞i在網(wǎng)頁j中出現(xiàn)了n次,每次出現(xiàn)的權(quán)值分別為Wkw(i),那么其總的權(quán)值W′kw(i)計算公式為：

對于一個網(wǎng)頁,應(yīng)用上式對每個關(guān)鍵詞進行權(quán)值計算是合理的。但是,考慮到相同的關(guān)鍵詞可以出現(xiàn)在不同的網(wǎng)頁中,而不同的網(wǎng)頁長度不同,對于越長的網(wǎng)頁關(guān)鍵詞可能獲得的權(quán)值也就越高。所以,一個關(guān)鍵詞的權(quán)值在某種程度上受到網(wǎng)頁長度的影響,文中用下面的公式表示網(wǎng)頁長度對于關(guān)鍵詞權(quán)值的影響：

其中,W′kw(i,j)表示處理后的網(wǎng)頁j中關(guān)鍵詞i的權(quán)值；Lmax表示可索引最大網(wǎng)頁的文本長度；L(j)表示當(dāng)前網(wǎng)頁j的可索引文本長度。對其歸一化處理：

其中,W′kwmax(i,j)為當(dāng)前網(wǎng)頁j中關(guān)鍵詞i總權(quán)值的最大值。

結(jié)合PageRank值可以進一步得到一個關(guān)鍵詞在一張網(wǎng)頁中獲得最終的權(quán)值Wweb(i,j),其由基本權(quán)值Wkw(i,j)和鏈接權(quán)值P(j)按一定的比例重新構(gòu)成：

上式中2 種因素都起到了影響關(guān)鍵詞權(quán)值的作用,同時又把各自的影響限定到一定的范圍內(nèi),其系數(shù)γ+δ=1,本文取γ=0.7。

假設(shè)聚類k中有m張相似圖片,即有m張對應(yīng)的網(wǎng)頁,對每張網(wǎng)頁計算上式就可以求得一個關(guān)鍵詞i在本聚類中的權(quán)值：

計算出一個聚類中所有關(guān)鍵詞的權(quán)值,并歸一化處理可得：

其中,W′clustermax(i)為本聚類中最大的關(guān)鍵詞權(quán)值。這樣就可以根據(jù)一定的閾值或者權(quán)值的百分比排名來劃分高相關(guān)文本,一般相關(guān)文本以及低相關(guān)文本。

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

本文隨機選取了15 個圖片聚類,圖片內(nèi)容包含娛樂明星、電影海報、政治人物、動物、建筑、風(fēng)景、數(shù)碼產(chǎn)品、運動、游戲、熱點事件、樂器。設(shè)定高相關(guān)文本的權(quán)重閾值為0.8,一般相關(guān)文本的權(quán)重閾值為0.4,權(quán)重低于0.4 的為低相關(guān)文本。表3 和表4 分別給出了百度、谷歌和本文算法得到的高相關(guān)文本和關(guān)鍵詞權(quán)值計算結(jié)果。

通過對比圖片內(nèi)容的人工評估以及對比百度識圖文本猜測和谷歌文本猜測可以看出,本文提出的基于相似圖片聚類的Web 文本特征計算算法的結(jié)果是令人滿意的。其中15 個圖片聚類中百度搜索結(jié)果出現(xiàn)圖文不符的有3 項,分別是第2 項、第3 項、第14 項；谷歌搜索結(jié)果中圖文不符的有2 項,分別是第4 項和第11 項,而且第13 項結(jié)果也不準(zhǔn)確,并且谷歌搜索部分結(jié)果中如第8 項、第10 項、第13 項給出的中文形式最相關(guān)文本詞語內(nèi)部有分隔符,容易使表達結(jié)果出現(xiàn)歧義,如第10 項結(jié)果中倩女和幽魂與第12 項的桂綸鎂和線人意義是完全不一樣的,前者只能作為一個完整詞語才有意義,而后者是2 個毫不相關(guān)的詞語。本文算法中只有一個聚類(序號5)的高相關(guān)文本分析結(jié)果不是很理想,人工評估這種圖片的內(nèi)容是“戰(zhàn)斗機”或者“AC-130”等,但是算法計算出的高相關(guān)文本卻是“壁紙”。造成這種情況的原因是由于大量引用這張圖片的網(wǎng)頁出現(xiàn)“壁紙”關(guān)鍵詞導(dǎo)致其權(quán)重很高。對于這種情況,可以對高頻出現(xiàn),但是沒有區(qū)分度的關(guān)鍵詞降低權(quán)重。對于這個聚類,權(quán)值大于0.2的相關(guān)文本見表5。

表3 隨機選取15 個聚類的文本分析結(jié)果

表4 每個聚類前5 位關(guān)鍵詞權(quán)值及歸一化結(jié)果

表5 聚類權(quán)值

6 結(jié)束語

本文給出解決現(xiàn)有圖片搜索引擎中圖文不符問題的新思路,在現(xiàn)有文本特征分析方法的基礎(chǔ)上,提出了一種基于相似圖片聚類的Web 文本特征算法。實驗結(jié)果表明,該算法能夠有效提高圖片搜索結(jié)果的相關(guān)性。同時通過在建立倒排索引的過程中提高高相關(guān)文本的權(quán)重,降低低相關(guān)文本的權(quán)重,不僅可以進一步提高圖片搜索質(zhì)量,還可以給出以圖搜圖功能的文本提示,即猜測用戶輸入圖片的內(nèi)容。下一步工作是針對不同類型網(wǎng)頁在內(nèi)容組織上的差異,將網(wǎng)頁類型因素加入到特征文本分析過程中,通過建立不同的HTML 標(biāo)簽權(quán)重解析模型,進一步提升特征文本分析的準(zhǔn)確性。

[1]吳 昆.基于視覺特征的垂直搜索研究[D].武漢：華中科技大學(xué),2009.

[2]謝 同.基于文本的Web 圖片搜索引擎的研究與實現(xiàn)[D].成都：電子科技大學(xué),2007.

[3]謝東升.基于文本的圖片搜索引擎的研究[D].上海：同濟大學(xué),2007.

[4]邵 剛.基于內(nèi)容的圖像檢索技術(shù)研究與系統(tǒng)實現(xiàn)[D].大連：大連理工大學(xué),2005.

[5]郭 軍.Web 搜索[M].北京：高等教育出版社,2009.

[6]Wu Fei,Han Yahong,Zhuang Yueting.Multiple Hypergraph Clustering of Web Images by Mining Word2Image Correlations [J].Journal of Computer Science and Technology,2010,25(4)：750-760.

[7]Zhang Xiaoming,Li Zhoujun,Chao Wenhan,et al.Improving Image Tags by Exploiting Web Search Results[J].Multimedia Tools and Applications,2013,62(3)：601-631.

[8]Duan Lixin,Li Wen,Tsang I W H.et al.Improving Web Image Search by Bag-based Reranking [ J].IEEE Transactions on Image Processing,2011,20(11)：3280-3290.

[9]Yang Linjun,Hua Xiansheng.Prototype-based Image Search Reranking[J].IEEE Transactions on Multimedia,2012,14(3)：871-882.

[10]Brin S,Page L.The Anatomy of a Large-scale Hypertextual Web Search Engine[J].Computer Networks and ISDN Systems,1998,30(1-7)：107-117.

[11]王志琪,王永成.HTML 文件的文本信息預(yù)處理技術(shù)[J].計算機工程,2006,32(5)：46-48.

[12]石春剛.中文文本聚類中的特征提取[D].天津：南開大學(xué),2006.