基于多核聚類(lèi)算法和用戶(hù)興趣模型的圖像搜索方法

（重慶第二師范學(xué)院繼續(xù)教育學(xué)院，重慶400067）

引言

隨著信息技術(shù)的發(fā)展日新月異，海量圖像信息的檢索應(yīng)用越來(lái)越廣泛。自90年代初以來(lái)，個(gè)性化圖像搜索一直是一個(gè)活躍的研究課題。近年來(lái)，在圖像搜索與跟蹤、特征提取機(jī)制以及相關(guān)的機(jī)器學(xué)習(xí)技術(shù)方面取得了一些進(jìn)展。圖像搜素已經(jīng)引起了圖像分析與處理、計(jì)算機(jī)視覺(jué)、心理學(xué)和安全等領(lǐng)域研究人員的關(guān)注。

人們通常利用搜索引擎來(lái)查詢(xún)目標(biāo)信息，但現(xiàn)有搜索引擎有兩個(gè)明顯缺陷[1]：（1）簡(jiǎn)化了圖片搜索，僅僅進(jìn)行文本檢索，而未充分考慮圖像語(yǔ)義間的相似性[2]；（2）在檢索關(guān)鍵詞的時(shí)候，所有相關(guān)的圖像都被下載到索引庫(kù)中，按照一定的排序規(guī)則反饋給用戶(hù)[3]。也就是說(shuō)，現(xiàn)有搜索引擎并不考慮個(gè)人興趣喜好，針對(duì)同一個(gè)檢索詞的操作，無(wú)法根據(jù)用戶(hù)的主觀(guān)意愿進(jìn)行相應(yīng)的個(gè)性化搜索結(jié)果[4]。比較好的解決辦法就是反饋。文獻(xiàn)[5]將最小二乘法支持向量機(jī) (Least Squares Support Vector Machines，LSSVM)引入到檢索系統(tǒng)中，但需要用戶(hù)標(biāo)記正負(fù)樣本，比較繁瑣，而且沒(méi)有解決正例樣本較少的問(wèn)題。針對(duì)以上問(wèn)題，文中提出了一種新的圖像搜索算法，根據(jù)用戶(hù)的搜索指標(biāo)，在對(duì)圖像進(jìn)行基于多核聚類(lèi)的基礎(chǔ)上，使用最小二乘支持向量機(jī)來(lái)建立用戶(hù)興趣模型，并將搜索結(jié)果呈現(xiàn)出來(lái)返回給用戶(hù)。

1 幾種聚類(lèi)算法的比較

目前，常見(jiàn)的聚類(lèi)算法包括K-means聚類(lèi)算法、FCM算法以及多核聚類(lèi)算法，下面分別詳細(xì)介紹每種算法。

1.1 基于Hadoop的多維聚類(lèi)算法K-means

K-means是一個(gè)十分簡(jiǎn)單的聚類(lèi)算法，針對(duì)客戶(hù)信息屬性多維的特點(diǎn)，以及結(jié)合Hadoop的MapReduce算法的設(shè)計(jì)，以常規(guī)的K-means算法為基礎(chǔ)，進(jìn)行多維化的擴(kuò)展。

常規(guī)的K-means算法包含以下幾個(gè)步驟：

1）從圖像對(duì)象中有針對(duì)性的選擇個(gè)圖像對(duì)象作為初始化聚類(lèi)中心；

2）設(shè)定最小距離的初步臨界值，通過(guò)計(jì)算每個(gè)圖像對(duì)象與聚類(lèi)中心的距離，進(jìn)行初步的分類(lèi)劃分；

3）根據(jù)劃分后分聚類(lèi)中心，重新計(jì)算每個(gè)聚類(lèi)的均值，這個(gè)均值是可以重新按照步驟2）進(jìn)行變化的；

4）計(jì)算每一次劃分后是否滿(mǎn)足函數(shù)收斂，如果滿(mǎn)足，則算法終止運(yùn)行，如果條件不滿(mǎn)足，則繼續(xù) 2）、3）步驟。

K-means算法的迭代是通過(guò)Map函數(shù)及Reduce函數(shù)來(lái)實(shí)現(xiàn)的，Map函數(shù)默認(rèn)的鍵值對(duì)為（Key,value）。為了便于計(jì)算，可以將圖像數(shù)據(jù)按照屬性導(dǎo)成文本形式。這里的key即當(dāng)前文本的數(shù)據(jù)相對(duì)于起始點(diǎn)的位移，value則是對(duì)應(yīng)的位移字符串。文本遍歷后，通過(guò)value值計(jì)算對(duì)象與各個(gè)中心點(diǎn)的距離，從而找到距離最短的中心簇類(lèi)。其設(shè)計(jì)的Map函數(shù)如下：

初始時(shí)解析value值得到初始值firstvalue；

距離中心聚類(lèi)的最短距離定義為minvalue,初始化時(shí)為最大值；

Dex變量作為key’;

K定義為初始聚類(lèi)中心的個(gè)數(shù)；

Dis=firstvalue;定義每一個(gè)對(duì)象與第m個(gè)聚類(lèi)中心的距離；

Key’=index;每一次map函數(shù)執(zhí)行之后將index賦值給 key’;

Value’=dis;將 dis作為 value’的值；

Reduce函數(shù)的輸入來(lái)源Map之后的分類(lèi)合并，即(key,V);這里的key是合并后聚類(lèi)的下標(biāo)，V是同一聚類(lèi)的對(duì)象值即Map函數(shù)得到的value’;通過(guò)對(duì)同一聚類(lèi)的各個(gè)對(duì)象value’值得相加除以同一聚類(lèi)的對(duì)象個(gè)數(shù)，即為新的聚類(lèi)中心的值。偽代碼如下：

SUM[];初始化數(shù)組作為每一個(gè)聚類(lèi)對(duì)象坐標(biāo)的累加值。

NUM=0;初始化變量NUM，作為同聚類(lèi)的對(duì)象個(gè)數(shù)；

While（V.hasNext()）//hasNext()用于判斷是否有下一個(gè)同聚類(lèi)對(duì)象；位移及對(duì)象個(gè)數(shù)；

數(shù)組SUM[]的每一個(gè)值與NUM相除，得到各個(gè)聚簇中心新的坐標(biāo)值；

即key變?yōu)?key’;

Value’的值即各個(gè)對(duì)象對(duì)應(yīng)的坐標(biāo)值；

重復(fù)Map函數(shù)及Reduce，直到達(dá)到收斂條件。

1.2 模糊C-均值聚類(lèi)算法FCM

FCM是比較常見(jiàn)的模糊聚類(lèi)算法，其基本思想是通過(guò)計(jì)算隸屬度表示每個(gè)數(shù)據(jù)點(diǎn)屬于某個(gè)類(lèi)的程度，并進(jìn)行約束，從而實(shí)現(xiàn)數(shù)據(jù)分類(lèi)。FCM把n個(gè)向量xi(i=1,2,…，n)分為c個(gè)模糊組，計(jì)算每組的聚類(lèi)中心，使總體非相似性指標(biāo)的價(jià)值函數(shù)達(dá)到最小，F(xiàn)CM算法最大的特點(diǎn)在于每個(gè)數(shù)據(jù)點(diǎn)隸屬度的取值被規(guī)范在0和1之間，以更直觀(guān)的確定其屬于每組的程度。

首先，定義數(shù)據(jù)集中第個(gè)樣本和第個(gè)聚類(lèi)中心之間的誤差平方：

通過(guò)隸屬度的平方加權(quán)來(lái)表示所有數(shù)據(jù)點(diǎn)與每個(gè)聚類(lèi)中心的距離，進(jìn)而得到每個(gè)聚類(lèi)內(nèi)的加權(quán)平方和目標(biāo)函數(shù)：

然后利用拉格朗日乘數(shù)法，可以得到算法的迭代公式：

1.3 多核聚類(lèi)算法

多核聚類(lèi)算法是指在傳統(tǒng)的模糊聚類(lèi)算法的基礎(chǔ)上融入多核，引入動(dòng)態(tài)核的權(quán)重，通過(guò)多核的方式可以有效地解決K-means算法、FCM算法的不足。對(duì)于選定的多核函數(shù)，根據(jù)權(quán)重的組合，可以滿(mǎn)足不同的圖像對(duì)核函數(shù)的偏好，最終得出最佳的匹配權(quán)重值。算法如下：

輸出：wl,uij,vi及圖像分類(lèi)結(jié)果。

第一步：隨機(jī)初始化第j個(gè)樣本xi隸屬于第i類(lèi)的典型值為ti(0)，設(shè)置迭代次數(shù)為，最大迭代次數(shù)為tmax；令t的初始值為1；第t次迭代的隸屬度矩陣為U(t)；第t次迭代的聚類(lèi)中心為Vk(t)；

其中，uij為第j個(gè)樣本隸屬于第i類(lèi)的隸屬度值的大小，tij為第j個(gè)樣本屬于第i個(gè)類(lèi)的可能性隸屬度值，Φ為非線(xiàn)性映射函數(shù)，為原始空間的樣本點(diǎn)。

第三步：利用下式獲得第t次迭代的第j個(gè)樣本隸屬于第i類(lèi)的隸屬度值Vij(t)；

第四步：利用下式計(jì)算第t次迭代的第j個(gè)樣本隸屬于第類(lèi)的典型值tij(t)；

其中，σ2為協(xié)方差矩陣。

第五步：根據(jù)下式更新權(quán)重wl；

第七步：輸出各個(gè)參數(shù)以及最終結(jié)果，結(jié)束。

1.4 比較結(jié)果

在K-means算法中，K需提前擬定，且K值的選定較難。在進(jìn)行算法前，應(yīng)根據(jù)初始聚類(lèi)中心來(lái)確定一個(gè)初始劃分，再對(duì)其進(jìn)行優(yōu)化。若初始值未選定合適，則可能得到無(wú)效的聚類(lèi)結(jié)果。另外，K-means算法需要多次調(diào)整樣本分類(lèi)方式，并重新計(jì)算聚類(lèi)中心，因此當(dāng)圖像數(shù)據(jù)較多時(shí)，會(huì)耗費(fèi)較多的時(shí)間成本。

對(duì)于FCM算法，若一個(gè)類(lèi)的樣本容量很大，而其他類(lèi)樣本容量較小，有可能導(dǎo)致當(dāng)輸入一個(gè)新樣本時(shí)，該樣本的K個(gè)鄰居中大容量類(lèi)的樣本占多數(shù)。同時(shí)，F(xiàn)CM算法只計(jì)算“最近的”鄰居樣本，使得某一類(lèi)的樣本數(shù)量很大，最終可能導(dǎo)致該類(lèi)樣本不能接近目標(biāo)樣本。此外，F(xiàn)CM算法的計(jì)算量也較大。

多核聚類(lèi)算法能夠規(guī)避其他算法對(duì)于核函數(shù)選擇的不確定性。對(duì)于選取的多種核函數(shù)，憑借權(quán)重組合能夠滿(mǎn)足不同圖像對(duì)于各種核函數(shù)的興趣需求。綜上以上算法的優(yōu)缺點(diǎn)，本文選擇多核聚類(lèi)算法。

2 局部特征和全局特征的提取

提取圖像中的關(guān)鍵特征是準(zhǔn)確描述圖像和提高圖像搜索準(zhǔn)確性的前提和基礎(chǔ)。圖像中包含的信息眾多，不同用戶(hù)根據(jù)自身關(guān)注點(diǎn)的不同對(duì)圖像有不同的理解，即使對(duì)同一幅圖像也會(huì)產(chǎn)生多種不同的特征描述。本文選取了局部顏色直方圖[6]和全局紋理特征這兩種底層的視覺(jué)特性進(jìn)行計(jì)算。

在提取圖像局部顏色特征部分，本文將圖像分割成9個(gè)子塊，分割方法如圖1所示，而后將圖像變換到HSV顏色空間中再進(jìn)行相應(yīng)的特征提取。

圖1 將圖像劃分若干塊

兩幅圖像x,y所對(duì)應(yīng)的局部顏色直方圖γ，Ψ間的視覺(jué)相似性使用核函數(shù)（8）計(jì)算，來(lái)描述不同圖像視覺(jué)間的差異：

其中ui和vi是兩副圖像顏色直方圖的分量。

本文使用頻譜法進(jìn)行紋理特征提取，采用2DGabor小波提取圖像的紋理特征[7]，對(duì)于形狀變化或者旋轉(zhuǎn)都有較好的識(shí)別魯棒性，如圖2中所示。2DGabor小波變換采用圖像卷積來(lái)表征：

其中Gabor濾波器定義為：

其中z=(x,y)，k代表波向量，滿(mǎn)足以下關(guān)系：

圖2 Gabor特征提取示意圖

使用公式（13）可以計(jì)算兩幅圖像的紋理相似性：

其中,σ=［σ1，…，σm］,表示 x2所有圖像距離的平均值，x2均值的計(jì)算使用公式（9）。

3 建立模型

3.1 基于多核動(dòng)態(tài)聚類(lèi)工作流程

本文算法融合多核相似性與動(dòng)態(tài)聚類(lèi)，引入基于核函數(shù)的聚類(lèi)方法。工作流程如下：

步驟一:設(shè)定參數(shù)聚類(lèi)類(lèi)別數(shù)C，以及允許誤差Emax，確定初始化聚類(lèi)中心Wi(k)， i=1，…，C;

步驟二:采用公式（8）和公式（13），將輸入空間的特征向量映射到高維特征空間中；

步驟三:第i個(gè)子類(lèi)的散度矩陣計(jì)算公式如下：

其中

由于使用散度矩陣的跡度量散度矩陣大小是一種有效的方法，它在最小化類(lèi)內(nèi)散度矩陣跡的同時(shí)，也最大化了類(lèi)間散度矩陣跡，反映了聚集和分離程度。故求出trSi，并比較幾個(gè)子類(lèi)?ài)E的大小，將跡最大的子類(lèi)劃分，按照相似度準(zhǔn)則的標(biāo)準(zhǔn)進(jìn)行二次聚類(lèi)。直到實(shí)現(xiàn)預(yù)定的聚類(lèi)數(shù)目，這時(shí)候得到新的聚類(lèi)號(hào)[8]。

3.2 建立用戶(hù)興趣模型

3.2.1 最小二乘支持向量機(jī)模型

最小二乘支持向量機(jī)模型可以解決分類(lèi)問(wèn)題和函數(shù)估計(jì)問(wèn)題，其數(shù)學(xué)模型的建立過(guò)程如下：

其中，ω為超平面方向向量，φ(xi)為映射函數(shù)，ei為xi的松弛系數(shù)，γ為邊際系數(shù)。公式（16）的解可由對(duì)應(yīng)的公式（17）所示的拉格朗日函數(shù)給出：

式中ai為拉格朗日乘子。根據(jù)公式（17）求得：

合并上式，可通過(guò)求解公式（18）的線(xiàn)性方程組得出ai和b的值。

公式（18）中，Ω為n維對(duì)稱(chēng)方陣，I為n維單位陣，E為元素全為1的n維列向量，其元素為，，是核函數(shù)，因此，表示為Ω的元素（i行j列）。令可得到公式（18）的變形式：

求解以上變形式，得到ai和b后，即可得LS-SVM 分類(lèi)函數(shù)，見(jiàn)公式（19）：

可以看出，計(jì)算LS-SVM分類(lèi)模型時(shí)，無(wú)需考慮函數(shù)φ（·）的具體形式，只計(jì)算各個(gè)訓(xùn)練樣本與待測(cè)樣本之間的核函數(shù)k(xi,x)即可，待判模式向量的類(lèi)別，由如下判別函數(shù)決定，見(jiàn)公式（20）：

其中 sgn(·)為符號(hào)函數(shù)。若 y(x)≥0，則 x 被判為正類(lèi)，否則x被判為負(fù)類(lèi)。

3.2.2 建立用戶(hù)興趣模型流程

建立用戶(hù)興趣模型流程如下：

步驟一:線(xiàn)性組合公式（8）和公式（13），使用公式（15）計(jì)算每幅圖像間的相似性，將得到相似度矩陣作為多核動(dòng)態(tài)聚類(lèi)算法的輸入；

其中，ai≥0，m表示核函數(shù)的個(gè)數(shù)。

步驟二:通過(guò)多核動(dòng)態(tài)聚類(lèi)算法完成數(shù)據(jù)庫(kù)樣本圖像的聚類(lèi)；

步驟三:根據(jù)用戶(hù)的搜索指標(biāo)進(jìn)行相關(guān)顯示，如果實(shí)驗(yàn)結(jié)果不達(dá)標(biāo)，則利用手動(dòng)方式來(lái)人工選擇感興趣圖片，然后，將聚類(lèi)圖像作為正例樣本輸送到最小二乘支持向量機(jī)網(wǎng)絡(luò)中進(jìn)行訓(xùn)練，從而確定分類(lèi)面，構(gòu)建個(gè)性化用戶(hù)興趣模型[9]。訓(xùn)練完成后，再一次查詢(xún)樣本庫(kù)，將用戶(hù)興趣優(yōu)先級(jí)高的實(shí)驗(yàn)結(jié)果進(jìn)行優(yōu)先選擇，完成個(gè)性化搜索[10]。

圖3實(shí)驗(yàn)結(jié)果與分析

實(shí)驗(yàn)中我們選取了Corel圖像庫(kù)進(jìn)行測(cè)試，Corel圖像庫(kù)分成25個(gè)種類(lèi)，每類(lèi)含有100幅總共2500幅圖像。選擇的關(guān)鍵詞，包括典型的大象、非洲、馬、恐龍、花、家具6組。每組關(guān)鍵詞選取60幅圖像，這里選取360幅圖像進(jìn)行實(shí)驗(yàn)測(cè)試，圖3為實(shí)驗(yàn)結(jié)果。實(shí)驗(yàn)中采用查全率與查準(zhǔn)率進(jìn)行系統(tǒng)評(píng)價(jià)，公式定義如下：

其中β表示檢索出的相關(guān)圖片，ω表示檢索出來(lái)的不相關(guān)圖片，η表示未檢索出的相關(guān)圖片實(shí)驗(yàn)結(jié)果如表1所示。

表1 傳統(tǒng)檢索方法與本文算法的比較

由表1所示，傳統(tǒng)檢索方法不能針對(duì)用戶(hù)的需求建立興趣模型，查詢(xún)效果相對(duì)比較差，而本文提出的檢索方法建立了用戶(hù)興趣模型，使得用戶(hù)的主觀(guān)需求參與檢索，可以解決底層視覺(jué)特征與高層語(yǔ)義間的不匹配。通過(guò)對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行平均查全率和查準(zhǔn)率的比較評(píng)估，本文提出的新方法比單一顏色特征的搜索算法分別提高了8.2%和11.42%，比單一紋理特征方法分別提高了19.7%和26.08%，改進(jìn)效果明顯。

4 結(jié)論

針對(duì)現(xiàn)有的搜索引擎算法不能完整地評(píng)價(jià)用戶(hù)的查詢(xún)目的同時(shí)代價(jià)較高的問(wèn)題，本文提出的一種新的基于聚類(lèi)和用戶(hù)模型的搜索算法，該算法與傳統(tǒng)的基于Hadoop的多維聚類(lèi)算法K-means以及模糊C-均值聚類(lèi)算法FCM相比，改進(jìn)了傳統(tǒng)最小二乘支持向量機(jī)需要過(guò)多用戶(hù)參與的問(wèn)題，將聚類(lèi)結(jié)果作為正例樣本送入最小二乘支持向量機(jī)網(wǎng)絡(luò)進(jìn)行訓(xùn)練，不斷調(diào)整分類(lèi)面，將該分類(lèi)面重新應(yīng)用于數(shù)據(jù)庫(kù)的圖像檢索，通過(guò)實(shí)驗(yàn)可以看出，構(gòu)建了用戶(hù)模型的搜索方式可以更加準(zhǔn)確全面地查找用戶(hù)感興趣的圖片。