一種基于角相似性的ｋ－最近鄰搜索算法

摘 要:k-最近鄰搜索(KNNS) 在高維空間中應用非常廣泛，但目前很多KNNS算法是基于歐氏距離對數據進行索引和搜索，不適合采用角相似性的應用。提出一種基于角相似性的k-最近鄰搜索算法(BA-KNNS)。該算法先提出基于角相似性的數據索引結構(BA-Index)，參照一條中心線和一條參照線，將數據以系列殼—超圓錐體方式進行組織并分別線性存儲;然后確定查詢對象的空間位置，有效確定一個以從原點到查詢對象的直線為中心線的超圓錐體并在其中進行搜索。實驗結果表明，BA-KNNS算法較其他k-最近鄰搜索算法有更好的性能。

關鍵詞:k-最近鄰搜索; 數據分割; 角相似性; 殼—超圓錐體

中圖分類號:TP301.6文獻標志碼:A

文章編號:1001-3695(2009)09-3296-04

doi:10.3969/j.issn.1001-3695.2009.09.027

Algorithm of KNNS based on angular similarity

YU Xiao-gao YU Xiao-peng 2，3

(1.Hubei University of Economics， Wuhan 430205， China; 2. Wuhan Institute of Technology， Wuhan 430073， China; 3.Information Resources Research Centre， Wuhan University， Wuhan 430072， China)

Abstract:The KNNS is widely used in the high dimension space. However， the current KNNS uses Euclidean distance to index dataset and retrieve the target object， which is not suitable for those applications based on angular similarity. This paper proposed the angular similarity based on KNNS (BA-KNNS). BA-KNNS firstly proposed that the indexing structure should be based on angular similarity， refered to a center line and a referenced line to organize dataset with the method of the shell- hypercone， and stored them linearly. Then it determined the space place for the target object， making a hypercone which took the line connecting the origin point and the target object as center， and searched the hypercone for the target. The experiment shows that the performance of BA-KNNS is superior to those other KNNS.

Key words:KNNS; data partitioning; angular similarity; shell-hypercone

0 引言

KNNS在文本分類[1]、推薦系統[2]、時間序列分析[3]等應用中有很大的用途，該方法對密度估計和分類都很有效。最簡單的k-最近鄰搜索算法需要計算一個查詢對象p(d維矢量)到所有其他訓練樣本之間的距離，其總的計算復雜度為O((dn)2)[4]。人們為了降低復雜度，進行了大量的研究。在眾多的算法中，數據分割方法應用比較廣泛[4~8]。該類方法的思路有共同之處，即先對數據進行索引組織，然后再將查詢空間確定在一個以查詢點p為中心、以r為半徑的d-超球(或超立方體)內進行，查詢代價為數據組織代價和查詢代價之和，但是這些方法對r值的研究不深。雖然有效設定r是很不錯的方法，但卻很難并且是非自覺能決定的[9]，r設置大了會導致搜索代價大，設置小了會導致很多空查詢[10]。文獻 [9]是在假設數據集統一服從已知分布的情況下進行研究的，很明顯這不切實際。文獻[10]也是假設在分布已知的情況下對超球半徑進行估計，并允許半徑以一個步長變量rinc逐步遞增。由于分布未知，不能在假定的情況下對超球半徑進行估計;同時，如果數據樣本很復雜，稀疏很不均勻，半徑遞增由于缺乏指導要么導致不必要的搜索(包括空搜索)數量，要么導致包含過多的樣本而增加計算復雜度，也即rinc是很難適合全部樣本的。在文獻[4]的研究中，rinc從0增加到1.1以上時效果才明顯。文獻[8]提出iDistance方法，但它也是預測確定一個最大半徑超球和固定步長的迭代的方法。文獻[11]是先采用SA-Tree組織數據集，然后再用MinMax剪枝和局部MinDist剪枝方法，其實質也是預測查詢超球的半徑。

對于高效率的查詢處理，索引支持是非常重要的。盡管目前的研究在一定程度上能有效提高k-最近鄰搜索效率，但是其所采用的數據索引結構基本上都是以歐氏距離為相似性度量函數[12]，不適合使用角相似性的應用。前者是在一個超球內進行搜索，而后者的搜索只能在一個超圓錐體內進行。角相似性度量函數(如cosine)并不滿足度量函數的三角不等式。

由于幾何上的不匹配和特征空間的高維性，對于采用角相似性的文本分類、時間序列分析、推薦系統等應用來說，M-Trees存儲方式也是不可取的[13]。當前的技術要么不適用，要么性能低劣，雖然可以將數據集規范化到歐氏空間，但那樣會增大維數，導致檢索更加困難[12]。雖然文獻[12]也提出了基于角相似性的k-最近鄰搜索的思路(CS_KNNS)，但其計算復雜度偏大。因此，本文提出一種基于角相似性的k-最近鄰搜索算法(BA-KNNS)，它也屬于數據分割方法。

1 相關研究

1.1 KNNS搜索算法簡介

KNNS也就是從數據集中找出查詢對象的k個最近鄰居，其定義如下:

定義1 設數據集S={xi|1≤i≤n}，xi=[xi1，xi2，…，xid]。其中:n為樣本總數，d為數據元素的維數。給定任意樣本xi和度量函數D，xi的k(k<

p∈S′|h∈S-S′:D(xi，y)≤D(xi，h)(1)

最簡單的KNNS需要計算一個查詢點xi到所有其他訓練樣本之間的距離，然后對距離值進行排序得到其k個最近鄰居。為了縮小查詢范圍，提高效率，常用的KNNS算法是從給定查詢點xi為中心、半徑相對比較小的一個超球體內開始搜索;然后采用一個迭代方法，逐步擴充半徑，直到超球半徑超過或等于最小半徑rmin為止，此時該超球至少包含k個最近鄰居。可以發現，對于比較小的r，該算法的復雜度會隨d增長很慢。在很多的模式識別問題中，這個特性是充分的，當然r不可能假設為已知的[3]。

定義2 最小半徑rmin。xi的第k個最近鄰居到xi的距離為D(xi，neighbork)，也就是以xi為中心、包含k個最近鄰居的最小超球半徑。

1.2 相似性度量

在KNNS算法中，相似性度量是一個重要概念，其實質上是一個相似性度量函數。在度量空間S中，相似性度量函數D應滿足S×S→非負實數，使得任意的x1，x2，x3∈S同時滿足如下條件:

a)非負性。D(x1，x2)≥0，并且D(x1，x2)=0，當且僅當x1=x2。

b)對稱性。D(x1，x2)=D(x2，x1)。

c)三角不等式。D(x1，x2)+D(x1，x3)≥D(x2，x3)。

狹義上講，滿足度量的三個條件的函數才能被稱為相似性度量函數，如歐氏距離函數(Euclidean)。

D(xi，xj)=∑dl=1(xil-xjl)2(2)

但是廣義上也將許多常用的、不滿足三角不等式條件的度量函數作為相似性度量函數。角相似性度量函數就是其中之一。

在高維空間中，角相似性度量就是用向量之間的夾角來衡量它們的相似性。在應用中往往使用夾角的余弦值來表示夾角，也可以說是通常所說的余弦相似性函數等，如式(3)所示。

D(xi，xj)=(∑dl=1(xil×xjl))/(‖xi‖×‖xj‖)(3)

2 BA-KNNS算法

2.1 分析

目前KNNS研究基本上都是使用歐氏距離函數對數據進行索引和查找的。而很多應用，如文本分類、時間序列分析和推薦系統等都是根據角相似性進行k-最近鄰查找，這使得目前的研究基本上不適用。如果依然使用當前的方法，則會導致精確度或性能低下。如圖1所示，如果采用歐氏距離，則在以查詢對象p為中心的超球內就可以查詢到其k(k=8)個最近鄰居;如果采用角相似性函數，則不能在超球內進行查詢了，只能在一個超圓錐體內進行查詢，否則必然導致圖中p的鄰居p1、p2、p3等數據丟失。

根據以上分析，在常用研究不適用的情況下，研究高效率的基于角相似性的k-最近鄰搜索算法是非常必要的。

2.2 關鍵思路

對于高效率的查詢處理，索引支持非常重要。BA-KNNS首先提出索引結構(BA-Index)，將數據按照一定的索引結構進行組織，然后確定查詢對象的存儲位置以及查詢范圍，最后在該范圍內進行搜索。

2.2.1 索引結構

定義3 查詢超圓錐體HyperCone(p，θ)，簡稱HC，也就是數據對象p的k-最近鄰搜索空間，即以原點為頂點、從原點到數據對象p的直線為中心線，以2θ為圓錐角的一個超空間幾何體，如圖2(a)所示。

定義4 殼—超圓錐體Shell-HyperCone(p，θ1，θ2)，簡稱S-HC。超圓錐體HC(p，θ1)和HC(p，θ2)(θ1≤θ2)的差形成的超空間幾何體，即HC(p，θ2)-HC(p，θ1)，如圖2(b)所示。

索引結構BA-KNNS的創建思路具體如下:

a)將數據集中所有對象規范化，選擇參照點Q(實驗中選擇的是{0.51，0.52，…，0.5d})，以OQ為中心線。根據訓練集所有數據與中心線的夾角，將其組織成一系列殼—超圓錐體S-HCi(Q，θil，θih)，由內向外順序標以索引號(如圖3中的S-HC1(Q，∠QOD，∠QOC)， S-HC2(Q，∠QOB，∠QOA))。設S-HCi(Q，θil，θih)中數據集為S-HCi={shcij|1≤j≤ni}，ni為S-HCi中數據總數，i∈[1，I]，I為最大索引號。

b)從最外層殼—超圓錐體表面任意選擇一個向量ORg作為公共參照線，根據殼—超圓錐體S-HCi(Q，θil，θih)中每個向量與公共參照線ORg的夾角αij，將其中的數據對象依據αij升序線性存儲為datai，依然用αij表示shcij與ORg的夾角，則datai={(αij，shcij)|1≤j≤ni}。其截面圖如圖4所示。

c)將所有的殼—超圓錐體依據殼夾角偶對(θil，θih)用一棵二叉查找樹BSTree表示。每個節點表示一個殼—超圓錐體，具體包含指針偶對(pil，pir)、殼夾角偶對(θil，θih)和由殼—超圓錐體內數據對象及其與ORg的夾角形成的偶對。

BA-KNNS索引結構BA-Index就可以形式化描述為

BK={nodei|1≤i≤I}(4)

nodei={(pil，pir)，(θil，θih)，(αij，shcij)|1≤j≤ni}(5)

2.2.2 k-最近鄰搜索

定義5 最小圓錐角。如果查詢對象p的第k個最近鄰居與p的夾角為θ，則2θ就是最小圓錐角。

BA-KNNS算法以上述索引結構為基礎進行搜索，具體步驟如下(圖5):

a)確定查詢目標p的空間存儲位置。先根據p與中心線夾角余弦值γ，確定p所在的殼—超圓錐體S-HCi(Q，θil，θih);根據p與ORg的夾角δ確定其相應的存儲位置。

b)給定一個比較小的初始圓錐角β，確定查詢區域。

(a)建立一個以Op為中心線、以β為圓錐角的查詢超圓錐體HC(p，β)。

(b)確定與HC(p，β)相交的殼—超圓錐體。如果γ-β>0，選擇所有索引號小于i且θjh≥γ-β的S-HCj，以及所有索引號大于i且θjl≤γ+β的殼-超圓錐體S-HCj;如果γ-β≤0，則選擇所有θjl≤γ+β的S-HCj。

(c)被選的各殼—超圓錐體內與ORg夾角α在區間[δ-β，δ+β]中的數據對象就是候選對象集S。

c)k-最近鄰搜索。先求出S中各對象與p的夾角，選擇落在HC(p，β)內的數據，形成集合S′={pi|1≤i≤k′}，pS′，k′為S′中元素的數目。如果k′≥k，則用窮盡方法求出S′所有元素到p的夾角距離，則前k個鄰居{pi|1≤i≤k}就是p的k個最近鄰居集合，其中p1是p的最近鄰居;如果k′

(a)如果p的第m個鄰居的最小圓錐角θ未知或β≠θ(m比較小，一般設置1≤m≤5)，則轉向(b);否則根據假設1，將θ設為p的最小圓錐角預測值進行搜索，也即β=θ，轉向b)。

(b)根據步長Δβ(單位步長)，擴大β，轉向b)。

總是從初始圓錐角開始，根據Δβ逐步擴充p的查詢超圓錐體會導致空查詢。 文獻[6]認為綜合考慮鄰居與查詢樣本p之間的距離，要比單獨考慮單個鄰居到p的距離包含更多的信息。

假設1 給定任意一查詢樣本p，如果p的第m個最近鄰居的最小圓錐角為θ(m比較小)。若將θ作為p的查詢超圓錐體夾角，則在HC(p，θ)內p的鄰居數目k′接近k的概率比較大，即概率p{k′∈[k-ε1，k+ε2]}比較大，ε1、ε2是一個比較小的數，ε2可以比ε1稍大。

證明 設DB是空間數據集，樣本總數為n，其中數據類別為C1，C2，…，Cm，Ci={cij|1≤j≤ni}，ni為Ci中數據的數目，D為角相似性函數。從cij起遍歷Ci(j=1，2，…，ni)，并根據D(cij，cil)降序排列cij(l=1，2，…，n，j≠l)，則ci1就是cij的最近鄰居，包含ci1的k個鄰居的超圓錐體最小圓錐角為θi1。cij的查詢超圓錐體HC(cij，θi1)包含cij得到鄰居數kij接近k，即k-ε1≤kij≤k+ε2。

令cij的特征函數為ij=1 k-ε1≤kij≤k+ε20 kijk+ε2，∑mij=1ij即是頻數，而p^=(1/m)∑mi=1(∑nij=1ij/(ni-1))可以作為p的估計。根據實驗隨機采樣30次取得估計量p^有如下值:0.82，0.87，0.89，0.91，0.92，0.91，0.84，0.88，0.91，0.91，0.94，0.92，0.9，0.95，0.97，0.96，0.98，0.96，0.93，0.96，0.98，0.97，0.98，0.97，0.86，0.88，0.93，0.87，0.89，0.93。

假設檢驗如下:假設H0:p′≥0.96，則H1:p′<0.96。令隨機變量X=1 若p的估計值≥0.850 若p的估計值<0.85，X~B(1，p′)。取30個隨機樣本，X1，X2，…，X30都服從B(1，p′)，且獨立。根據中心極限定理有:當n比較大時，U=(X-p0)/p0(1-p0)/n~N(0，1)。此檢驗的拒絕域是u≤-u1-α， 取α=0.05，則-u1-α=-1.65。計算u=(28/30-0.96)/0.96×0.04/30=-0.745， 沒有落入拒絕域，接受H0:p′≥0.96。所以假設成立。證畢。

3 實驗分析

為了進一步考察算法的效果與效率， 用VC++6.0實現本文算法，在P4 2.0 GHz CPU、256 MB內存、Windows XP 環境下進行實驗，采用的Dataset1為中國科學院計算所文本分類(Txtcat)數據集，Dataset2為Jester笑話在線協同過濾推薦數據集第一部分。Dataset1包含2 816篇文檔，共分為10類。本文將1 974篇作為訓練樣本，其余842篇作為測試樣本。在實驗中首先對Dataset1各樣本進行預處理，用VSM表示各樣本，用TF/IDF表示詞語權重，d=1 000。Dataset2共包含24 983人對100個笑話的評分，分數為-10.00~+10.00;實驗之前也對所有評分作了規范化處理，d=100。

圖6描述了查詢對象預測圓錐體內鄰居數目。由于Dataset1被分為訓練集和測試集，查詢對象p的最近鄰居有可能屬于訓練集，所以設置m=5。而對于Dataset2，必須求出所有數據對象的k個最近鄰居，所以設置m=1，同時可以采用深度遍歷查詢。從圖6可以看出，一個查詢對象在預測超圓錐體內的鄰居數k′<

圖7描述了查詢超圓錐體擴充次數，可見根據假設1，查詢超圓錐體的擴充次數明顯低于根據圓錐角步長逐步擴充的次數，這勢必大大降低空查詢的次數，提高效率。其實假設1的正確性和作用很直觀，因為在預測的查詢超圓錐體內，只要k′≥k且k′<

圖8顯示了不同k值的情況下找到所有數據對象k個最近鄰居的向量相似性計算的平均數?？梢钥闯?，在不同的k值情況下BA-KNNS的向量相似性計算平均數均比CS-KNNS要小，這意味著BA-KNNS有更高的搜索性能。

4 結束語

本文分析了目前KNNS研究在角相似性搜索應用中的不足，并提出一種基于角相似性的k-最近鄰搜索算法。該算法先參照一條中心線和一條參照線，將數據以系列殼—超圓錐體方式進行組織;然后根據查詢對象與中心線和參照線的夾角確定其空間位置，有效確定一個超圓錐體并在其中進行搜索。BA-KNNS有效縮小了查詢范圍，提高了查詢效率。實驗結果表明，BA-KNNS算法較其他k-最近鄰搜索算法有更好的性能。

參考文獻:

[1]BELL D A， GUAN J W， BI Ya-xin. On combining classifier mass functions for text categorization[J]. IEEE Trans on Knowledge and Data Engineering， 2005， 17(10):1307-1319.

[2]GEORGE T， MERUGU S. A scalable collaborative filtering framework based on co-clustering[C]//Proc of the 5th IEEE International Conference on Data Mining. 2005:625-628.

[3]KEOGH E， CHAKRABARTI K， MEHROTRA S. Locally adaptive dimensionality reduction for indexing large time series databases[J]. ACM Trans on Database Systems， 2002， 27(2):188-228.

[4]YU Cui. Indexing the relative distance:an efficient approach to KNN search [J]. High-Dimensional Indexing， 2002，23(41):85-108.

[5]YU Xiao-gao， JIAN Yin. A new clustering algorithm based on KNN and DENCLUE[C]//Proc of ICMLC. 2005:2033-2038.

[6]YU Xiao-gao， YU Xiao-peng. The research on an adaptive K-nearest neighbors classifier[C]//Proc of ICMLC. 2006:1241-1246.

[7]KUAN J， LEWIS P. Fast k-nearest neighbor search for R-Tree family[C]//Proc of International Conference on Information， Communications and Signal Processing. 1997:9-12.

[8]SAMET H. Depth-First k-nearest neighbor finding using the MaxNearestDist estimator[C]//Proc of the 12th International Conference on Image Analysis and Processing. 2003:486-491.

[9]NNEN S A， NAYAR S K. A simple algorithm for nearest neighbor search in high dimensions[J].IEEE Trans on Pattern Analysis and Machine Intelligence，1997，19(9):989-1013.

[10]CHAKRABARTI K， MEHROTRA S. A new approach to indexing high dimensional space[C]//Proc of the 26th International Confe-rence on Very Large Data Bases. 2000:89-100.

[11]AGHBARI Z A. Array-index:a plug search k-nearest neighbors method for high-dimensional data[J]. Data Knowledge Engineering， 2005，52(3):333-352.

[12]APAYDIN T， FERHATOSMANOGLU H. Access structures for angular similarity queries[J]. IEEE Trans on Knowledge and Data Engineering， 2006， 18(11):1512-1525.

[13]CIACCIA P， PATELLA M， ZEZULA P. M-Tree:an efficient access method for similarity search in metric space[C]//Proc of the 3rd International Conference on Very Large Data Bases. 1997:426-435.