劉丹青，李明勇

（1東華大學 計算機科學與技術(shù)學院，上海 201620；2上海市計算機軟件評測重點實驗室，上海 200235）

0 引 言

隨著互聯(lián)網(wǎng)的快速發(fā)展，計算機技術(shù)已滲入到社會的各種行業(yè)。因此，高維的文本、圖片、視頻等多媒體數(shù)據(jù)呈現(xiàn)爆炸式的增長趨勢［1］。傳統(tǒng)的暴力搜索方法是通過遍歷所有的數(shù)據(jù)點進行查詢，隨著數(shù)據(jù)集的增大，這種暴力搜索方法需要巨大的存儲空間，并且每次檢索的時間很長。因此，該方法只適用于小規(guī)模的數(shù)據(jù)集。針對大規(guī)模高維數(shù)據(jù)集的查詢問題，研究者們提出了近似最近鄰搜索方法，在可接受一定精度損失的情況下，查詢到盡可能精確的結(jié)果。其中，基于向量量化的近似最近鄰搜索方法是比較有效和受關(guān)注較多的方法之一。該方法可以有效地降低空間存儲，提高檢索速度。

向量量化［2］的基本思想是，僅用數(shù)據(jù)集特征向量空間中的一個有限子集，表示該數(shù)據(jù)集特征向量空間中所有數(shù)據(jù)集特征向量，因而大大減少了數(shù)據(jù)的內(nèi)存存儲。常用的向量量化方法有樹搜索向量量化方法、乘積量化方法［3］和多階段向量量化方法［4-5］等。本文著重研究多階段向量量化方法，并對基于多階段向量量化的近似最近鄰搜索方法提出改進。在訓練碼本過程中，通過優(yōu)化初始聚類中心，減小重構(gòu)向量的均方誤差，改善碼本質(zhì)量，進一步減小向量的量化誤差，以此提高實驗召回率。

1 相關(guān)工作

1.1 最近鄰搜索

最近鄰搜索在計算機視覺、多媒體搜索、機器學習等領(lǐng)域里應用非常廣泛。最近鄰檢索就是給定數(shù)據(jù)集和目標數(shù)據(jù)，根據(jù)數(shù)據(jù)的相似程度，從數(shù)據(jù)庫中查找與目標數(shù)據(jù)最接近的數(shù)據(jù)。一般情況下，可認為在空間中，兩個數(shù)據(jù)點的距離越小，其之間的相似性越高。

假設(shè)，給定一個查詢向量q，最近鄰搜索的目的，是在一個向量集合X=｛x1，x2，…，xn｝里，找到與查詢向量q距離最近的目標向量x*：

其中，d i st（x，q）是目標向量和查詢向量之間的距離。通常使用歐氏距離（Euclidean distance）定義兩向量之間的距離，即兩個數(shù)據(jù)點在空間里的直線距離。在D維空間中，兩個數(shù)據(jù)點（A1，A2，…，AD）和（B1，B2，…，BD）之間的歐式距離可以表示為：

1.2 近似最近鄰搜索

面對數(shù)據(jù)庫中巨大的高維數(shù)據(jù)，當前基于最近鄰搜索的檢索方法不能得到理想的檢索結(jié)果和可接受的檢索時間。因此，為了較好的均衡準確性和資源，人們開始關(guān)注近似最近鄰檢索方法ANN（Approximate Nearest Neighbor）［1］。

近似最近鄰搜索是給定一個查詢向量，為了用盡可能低的空間存儲成本，查找數(shù)據(jù)庫中與之最相似的向量，在犧牲可以接受的精度范圍內(nèi)，加快檢索速度。近似最近鄰查詢方法主要分為兩類，一是基于哈希的方法，另一種是基于向量量化的方法。

基于哈希的方法是將數(shù)據(jù)映射到漢明空間，即通過哈希函數(shù)，將向量x轉(zhuǎn)換成哈希碼（海明碼）b，通過二者哈希碼的漢明距離，度量兩個數(shù)據(jù)點之間的相似度，即將距離dist（x1，x2）近似成哈希碼的距離dist（b1，b2）?；诠５难芯糠较蛑饕菍W習優(yōu)化哈希函數(shù)。隨著二進制化后數(shù)據(jù)信息的減少，準確性也隨之降低。為了解決這個問題，近年來人們提出了各種基于向量量化的近似最近鄰搜索方法。

1.3 向量量化

向量量化（Vector Quantization）多被應用在源編碼和信號壓縮方面［2］。向量量化是通過聚類方法，將向量集合聚類成多個類別，每一個類別里的向量都可以用其對應的類中心近似代替。換句話說，就是用其中的一個有限子集編碼，表示一個向量數(shù)據(jù)空間中的向量。相對于需要存儲原始數(shù)據(jù)的向量方法，向量量化方法只需要存儲向量對應的類中心（即碼元）的索引ID，大大減小了向量的存儲空間。另外，只根據(jù)聚類中心的ID去查找預先計算好的表格，其中存放著聚類中心與查詢向量的距離。向量的歐式距離可以通過編碼后碼元之間的距離來近似表示，減少了計算時間，使得查詢更加有效，提高了向量的檢索速度。

人們開始重點關(guān)注將向量量化技術(shù)應用到近似最近鄰搜索方向［3，5-11］。其中比較具有代表性的方法是乘積量化算法［3］。該算法的主要思想是，將高維的特征向量空間劃分成若干個低維的子空間，對每個低維子空間的子特征向量進行量化，原始高維向量的量化結(jié)果就可以通過連接這些子特征向量量化后的編碼進行表示。乘積量化是通過對每個子空間單獨量化，從而減小量化誤差。

乘積量化劃分子空間的基本假設(shè)是，不同子空間內(nèi)的向量分布是相互獨立的，不存在關(guān)聯(lián)。若子空間中數(shù)據(jù)分布之間的相關(guān)性很強，則乘積量化的性能就會下降。在實際情況中，真實的數(shù)據(jù)分布并不滿足子空間相互獨立的假設(shè)。因此，考慮到數(shù)據(jù)的分布，從而對數(shù)據(jù)進行更有效的量化。Juang和Gray等人提出了多階段向量量化（MSVQ）［4］。在數(shù)據(jù)原始維度下，通過多個低復雜度的量化器，保留每次量化產(chǎn)生的誤差，然后繼續(xù)量化誤差，使得量化誤差進一步減小，從而提高近似最近鄰檢索方法的精度。

2 多階段向量量化

多階段向量量化方法和傳統(tǒng)的向量量化方法不同，它并不是拋棄量化誤差，而是保留量化誤差，將其作為余差向量，進一步量化，從而減小量化誤差。為了減少計算和存儲，MSVQ是使用幾個階段的碼本，按順序（即逐階段）進行量化，之后連接每個階段的量化結(jié)果表示輸入向量。

多階段向量量化是在原始高維空間上處理向量，通過多個低復雜度的量化器，由粗到細的量化向量，每一個階段的輸出是上一階段量化產(chǎn)生的余差向量，將其作為下一階段的輸入再進行量化。有序的將每一階段的量化器串聯(lián)起來，每一階段對應著一個由k-means聚類算法得到的碼本。

在訓練階段，通過在訓練集X上進行k-means聚類，得到第一階段的碼本C1，將X在第一階段碼本上進行量化，得到其在C1對應的碼元向量。第一階段量化器的輸出，即為X與其量化后碼元向量的余差R1；R1作為第二階段量化器的輸入，在其上進行k-means聚類，得到第二階段的碼本C2。將R1在第二階段的碼本上進行量化，得到其在C2對應的碼元向量，第二階段量化器的輸出即R1與其量化后對應的碼元向量的余差R2。

上述過程將持續(xù)至得到M個碼本，即C=［C1，C2，…CM］。因此，原始向量可以表示為：

其中，Bi為碼元索引，RM為第M階段的余差向量，即全局量化誤差。

2.1 向量的編碼和解碼

在編碼階段，只需要存儲向量對應的類中心的索引ID。因此給定數(shù)據(jù)集向量X和碼本C1，C2，…，CM，在對應階段碼本里尋找使得當前階段編碼誤差Ei最小的碼元向量，即與當前所要量化的向量距離最近的碼元向量，其對應的索引I D為Bi，也稱為向量的編碼。原向量即可表示為：

最后一階段的編碼誤差E可以忽略不計：

因此，多階段向量量化算法可以根據(jù)向量編碼近似地還原出原始向量，即重構(gòu)向量可以表示為所有階段對應的碼元向量之和。假設(shè)向量X的編碼為［B1，B2，...，BM］∈｛1，2，...，K｝，通過編碼找到其對應階段碼本對應的碼元向量，那么還原X的過程為：

2.2 距離計算

在查詢過程中，數(shù)據(jù)庫中的特征向量通過量化進行高效的壓縮存儲，也需要從數(shù)據(jù)庫中盡快的查找到和查詢向量相匹配的最近壓縮向量。Jegou等人提出了兩種距離計算方法［3］，分別是對稱距離計算（SDC）和非對稱距離計算（ADC）。

對稱距離計算需要將查詢向量x和數(shù)據(jù)庫向量y都進行量化，得到q（x）和q（y）后計算二者之間的距離d（q（x），q（y）），即d（x，y）=d（q（x），q（y））。非對稱距離計算，只對數(shù)據(jù)庫向量y進行量化得到q（y），則x和y的距離d（x，y）就可以用查詢向量和量化后的數(shù)據(jù)庫向量之間的距離表示，即d（x，y）=d（x，q（y））。非對稱距離計算進一步降低了量化誤差，因此本文采用非對稱距離計算。

查詢向量q與重構(gòu)向量的歐式距離為：

3 最小化均方誤差的多階段碼本訓練

本章提出在多階段向量量化方法的訓練碼本進行改進，可減小量化誤差，提高量化精度，從而提高實驗的召回率。

多階段向量量化方法在訓練碼本過程中采用經(jīng)典的k-means聚類算法。其主要思想是將空間中的k個點作為聚類中心（質(zhì)心），進行聚類過程，對與它們最相近的數(shù)據(jù)進行歸類。通過迭代更新每個類別里的質(zhì)心的值，直至得到最好的聚類結(jié)果。雖然k-means聚類算法應用廣泛，但也存在著一些缺點：如，對噪音和異常點十分敏感。在初始化時，一般是隨機選擇初始的聚類中心，如果大多數(shù)聚類中心被分配到同一個簇中，那么聚類算法很有可能不會收斂。也就是說，初始聚類中心的選取會影響到聚類的收斂效果，導致影響最終的聚類結(jié)果。

為了避免初始聚類中心的選取影響聚類結(jié)果，本文提出最小化均方誤差的多階段碼本訓練方法，盡可能地選擇相互之間距離較遠的數(shù)據(jù)點作為聚類中心。通過優(yōu)化初始聚類中心，改善訓練出的碼本質(zhì)量，從而減小向量的重構(gòu)誤差，提高檢索精度。具體實現(xiàn)步驟為：

（1）從數(shù)據(jù)集合的n個特征向量中隨機選取一個特征向量。

（2）從剩余的n-1個特征向量中按照一定概率選取聚類中心xj∈X，作為下一個聚類中心。該概率策略是數(shù)據(jù)點距離所有的聚類中心越遠，其被選取的概率越大，反之，其被選取到的概率越小。

（3）依次進行上述過程，直至得到k個聚類中心。

初始的聚類中心的選取原則是：令其相互之間的距離要盡可能的遠，逐個選取k個聚類中心，距離其它聚類中心越遠的數(shù)據(jù)點，被選作下一個聚類中心的概率越大。

本文將上述方法應用到多階段向量量化方法的訓練碼本過程中，該方法以最小化均方誤差（Mean-Square Error，MSE）為目標，使得向量量化后的重構(gòu)向量更精確。最小化均方誤差計算如式（8）所示：

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

實驗選用近似最近鄰搜索最常用的一個公開數(shù)據(jù)集來進行實驗性能評估，即SIFT1M數(shù)據(jù)集［3］。數(shù)據(jù)集包含3個子集：訓練集、數(shù)據(jù)庫集、查詢集。SIFT1M中的訓練數(shù)據(jù)集是從Flicker圖片［12］分享網(wǎng)站上公開圖像數(shù)據(jù)中提取的局部特征描述符，其數(shù)據(jù)集中的每一個特征向量都是128維；樣本數(shù)據(jù)集和查詢數(shù)據(jù)集是由INRIA Holidays［12］數(shù)據(jù)庫中的圖像數(shù)據(jù)提取的特征描述符。訓練數(shù)據(jù)集用于訓練學習得到碼本，樣本數(shù)據(jù)集和查詢數(shù)據(jù)集用于評估最近鄰搜索的性能。本文主要采用召回率R1＠100作為性能指標，即查詢準確率，表示在查詢階段查詢到的向量與驗證數(shù)據(jù)集中的前100個做對比得到的結(jié)果。數(shù)據(jù)集具體信息見表1。

表1 SIFT1M數(shù)據(jù)集Tab.1 SIFT1M dataset

實驗設(shè)置碼本數(shù)目為6，7，8，9，聚類中心數(shù)目K為16，64，256。SIFT1M數(shù)據(jù)集上的碼本數(shù)目-均方誤差的實驗曲線如圖1所示。可以看出，本文提出的最小化均方誤差多階段碼本訓練方法曲線（IMSVQ），始終保持在多階段向量量化方法曲線（MSVQ）的下方。表明本文方法可以進一步降低向量編碼的量化誤差，使得向量量化更精確。

圖1 碼本數(shù)目-均方誤差（SIFT1M）Fig.1 M-MSE（SIFT1M）

由于碼本數(shù)目和碼本中聚類中心數(shù)目是影響實驗的重要因素。通過實驗可以看出，在碼本聚類中心數(shù)目保持不變的情況下，隨著碼本數(shù)目的增加，向量編碼的均方誤差逐漸降低。在碼本數(shù)目保持不變的情況下，隨著碼本聚類中心數(shù)目的增加，向量編碼的量化誤差逐漸降低。因此選取合適的碼本數(shù)目和碼本中聚類中心數(shù)目可以提高實驗性能。

SIFT1M數(shù)據(jù)集上的實驗迭代次數(shù)-召回率曲線如圖2所示。實驗結(jié)果表明，在不同迭代次數(shù)下，本文提出的最小化均方誤差的多階段碼本訓練方法，性能優(yōu)于多階段向量量化方法。隨著實驗迭代次數(shù)的增加，從整體上看實驗召回率逐漸增加。最小化均方誤差的訓練碼本方法實驗曲線始終保持在多階段向量量化方法曲線上方，表明本文提出的方法可以有效地提高實驗召回率。圖3是在SIFT1M數(shù)據(jù)集上的碼本數(shù)目-召回率曲線。可以看出，優(yōu)化初始聚類中心后的方法召回率高于多階段向量量化方法。

圖2 迭代次數(shù)-召回率（SIFT1M）Fig.2 Iterations-Recall（SIFT1M）

圖3 碼本數(shù)目-召回率（SIFT1M）Fig.3 M-Recall（SIFT1M）

綜上所述，優(yōu)化初始聚類中心，可以減小向量的量化誤差，從而提高查詢的召回率，證明本文提出的最小化均方誤差的多階段訓練碼本方法具有可行性和有效性。

5 結(jié)束語

本文在多階段向量量化方法的訓練碼本過程中，提出了一種新的碼本訓練方法。原始訓練碼本的方法通過隨機選擇初始聚類中心，導致大多數(shù)聚類中心被分配到同一個類別中，向量量化后的重構(gòu)向量不夠精確，與原始向量相比誤差較大，影響訓練得到碼本的質(zhì)量。因此，為了減小隨機選取初始聚類中心對訓練得到碼本質(zhì)量產(chǎn)生的影響，本文采取選擇距離較遠的數(shù)據(jù)點原則，各個類別中的聚類中心差異度明顯。以最小化均方誤差為目標，通過優(yōu)化初始聚類中心，減小向量編碼的量化誤差，有效地提高了聚類結(jié)果的準確性。通過在公開數(shù)據(jù)集SIFT1M上的實驗結(jié)果表明，在近似最近鄰搜索應用中，本文提出的最小化均方誤差多階段碼本訓練方法優(yōu)于多階段向量量化方法，可以進一步地減小向量編碼的量化誤差，提高查詢精度，證明了該方法的可行性和有效性。