基于分位數(shù)概要的KNN算法研究

王丹

摘要：文章簡述了分位數(shù)概要的相關(guān)概念及特點，針對KNN（K最近鄰居）的算法特性及應(yīng)用進行了深入的研究，并在此基礎(chǔ)上提出了基于分位數(shù)的多值對象的KNN研究問題，為今后的算法研究奠定了基礎(chǔ)。

關(guān)鍵詞：分位數(shù)；KNN

分位數(shù)是大數(shù)據(jù)集和數(shù)據(jù)流上計算經(jīng)常使用的一種統(tǒng)計方法，通過分位數(shù)查詢能夠獲得統(tǒng)計信息以便為決策層提供數(shù)據(jù)支持。如果給出在d維空間的一組包含N個點集P及一個連續(xù)函數(shù)F且φ∈[0，1]，分位數(shù)查詢檢索在P中最小的第φN個F目標值。例如，中位數(shù)對應(yīng)于0.5-分位數(shù)，而最大值是1分位數(shù)。分位數(shù)提供了數(shù)據(jù)分布的一個簡潔的概要，主要應(yīng)用于在線決策支持、數(shù)據(jù)挖掘、選擇性估計、查詢優(yōu)化等。

1 分位數(shù)

分位數(shù)又稱次序統(tǒng)計量，中位數(shù)是一個特例，分位數(shù)是關(guān)于數(shù)據(jù)分布的一個重要統(tǒng)計量。數(shù)據(jù)項完全有序數(shù)據(jù)集D的φ-quantile，就是使D中的秩（秩為數(shù)據(jù)集合的元素的個數(shù)）為φ|D|的那個元素，其中0<φ<1，一般方便起見，對于分位數(shù)問題通常假定在D中沒有重復(fù)元素。一個分位數(shù)概要包含很多信息，以便對于任何0<φ<1，可以定義一個很小的實數(shù)δ，返回一個φ′-分位數(shù)近似φ-分位數(shù)，其中φ-ε≤φ′≤φ+ε。一個分位數(shù)概要大小為0（1，ε），通過排序D，然后得到這些數(shù)據(jù)項的秩分別是ε|D|，2ε|D|，3ε|D|，……|D|?？梢院苋菀椎赜嬎惴治粩?shù)。

定義1.1（φ-分位數(shù)）：一個包含N個數(shù)據(jù)元素的有序序列的φ-分位數(shù)（φ∈（0，1]）就是秩為的元素「φN」。分位數(shù)查詢的結(jié)果就是具有給定秩的數(shù)據(jù)元素。

例如，在圖1中顯示了一個數(shù)據(jù)流產(chǎn)生數(shù)據(jù)的樣本序列，其中每個數(shù)據(jù)元素由一個數(shù)據(jù)值表示，數(shù)據(jù)元素到達的順序為從左至右，在序列中數(shù)據(jù)元素的數(shù)量是16，序列排序后的順序為1，2，3，4，5，6，7，8，9，10，10，10，11，11，11，12。所以0.5分位數(shù)返回的是秩為8（=0.5*16）的元素，就是8；0.75分位數(shù)返回的是序列中秩為12的數(shù)據(jù)元素10。

2 KNN分析

最初的近鄰法是由cover和Hart于1968年提出的，隨后得到理論上深入的分析，是非參數(shù)法中最重要的方法之一。近鄰法的一個嚴重問題是需要存儲全部訓(xùn)練樣本，以及繁重的距離計算量。

K最近鄰（K-Nearest Neighbor，KNN）是最近鄰法的擴展，是一個理論上比較成熟的方法，也是最簡單的機器學(xué)習(xí)算法之一，是一種基于距離度量的分類方法。KNN在早期的研究策略中已被應(yīng)用于文本分類。當K=1時的一種特定的NN（Nearest Neighbor），NN強調(diào)的是最近點的重要性，而KNN則從整體考慮，是一種更為普遍的方法。K最近鄰居（KNN）查詢在計算機科學(xué)中是一個古典問題。KNN查詢目標是在數(shù)據(jù)集中找到距離查詢點q最近的K個目標點。現(xiàn)有的算法主要是基于R樹索引的查詢算法，本文所采用的KNN算法主要是在一個AR樹（聚合R樹）中進行的。

在N→∞的條件下，K-近鄰法的錯誤率低于最近鄰法，同時最近鄰法和K-近鄰法的錯誤率上下界都是在貝葉斯決策方法的1～2倍之間錯誤率的范圍內(nèi)。

KNN基本規(guī)則是：在所有N個樣本中找到與測試樣本的K個最近鄰者，其中各類別所占個數(shù)表示成與k_i，i=1，2，……，c。定義判別函數(shù)為：g_i（x）=k_i，其中i=1，2，……，c。決策規(guī)則為：argmaxg_i（x），i=1，2，……，c。與投票表決一樣，K近鄰一般采用K為奇數(shù)，這樣可以避免因2種票數(shù)相等而難以決策。

KNN方法的思路是：如果一個樣本在特征空間中的K個最相似（即特征空間中最近鄰）的樣本中的大多數(shù)屬于某一個類別，則該樣本也屬于這個類別。KNN算法中，所選擇的鄰居都是已經(jīng)正確分類的對象。該方法在定類決策上只依據(jù)最鄰近的一個或者幾個樣本的類別來決定待分樣本所屬的類別。KNN方法雖然從原理上也依賴于極限定理，但在類別決策時，只與極少量的相鄰樣本有關(guān)。

KNN算法也可應(yīng)用于回歸。通過在樣本中找到的K個最近鄰居，將這K個鄰居的屬性的平均值賦給該樣本，就可以得到該樣本的屬性。同時更有效的方法是將距離不同的鄰居對該樣本產(chǎn)生的影響給定不同的權(quán)值（weight），例如權(quán)值與距離成正比。

定義1.2（K-最近鄰居）：給定一個曲面散亂點集P={P_i（x_i，y_i，z_i），i=1，2，…n}，設(shè)某個點為V（x_v，y_v，z_v），則稱P中距離點V最近的K個點為點V的m鄰域點集，記為：MNB|V|=（P₁，P₂，…，P_m），稱為點V的K-近鄰，它反映了該點V的局部信息。K近鄰中的每個點稱為點V的鄰近點。

K最近鄰查找有很多應(yīng)用，包括數(shù)據(jù)挖掘、多媒體、圖像處理和監(jiān)測移動對象?？紤]一個移動電話公司已經(jīng)進行的一項調(diào)查是關(guān)于客戶對最喜歡的服務(wù)計劃的選擇。例如在圖2中，2個維度捕捉了一個月內(nèi)計劃的2個屬性（例如，價格和air-time數(shù)量）。每個白點表示客戶對這些屬性的選擇，假設(shè)公司計劃啟動一項新的計劃對應(yīng)于黑點q，為了評價q的潛在的市場流行度，管理者想要的是在q和客戶選擇之間的相似點的分布。為了這個目的，F(xiàn)可能由在q和白點之間的歐幾里德距離定義，同時檢索不同φ值的分位數(shù)。作為另一個空間形式的例子，假設(shè)在2中的點q是一個比薩店，而白點對應(yīng)的是住宅建筑，對于商店的擁有者來說這個住宅建筑距離中位數(shù)的非常有用的，它可以為比薩外賣計劃配備充足數(shù)量的員工。在圖2中的查詢是一個單源查詢，因為數(shù)據(jù)點集的排序只取決于一個源。

3 多值對象的KNN研究展望

最近鄰居（NN）查詢和K最近鄰居（KNN）查詢在數(shù)據(jù)庫研究中是非常重要的查詢類型。在不同的背景環(huán)境下，多種形式的KNN查找被研究，包括道路網(wǎng)絡(luò)、移動對象、連續(xù)查詢等。傳統(tǒng)KNN的只有一個查詢結(jié)點，實際應(yīng)用中可以有多個查詢結(jié)點，由于查詢點的數(shù)目以及它們在數(shù)據(jù)庫空間中分布的任意性，使得多值對象KNN查詢比只有一個查詢點的KNN查詢復(fù)雜得多，因此基于分位數(shù)概要的多值對象KNN是進一步研究的問題。

在許多應(yīng)用中，像分析經(jīng)濟數(shù)據(jù)，通常被看作為多值對象。例如，為了對比在幾個城市之間的家庭收入，經(jīng)常從一個城市隨機收集一組家庭集合的收入作為樣本，那么城市即對比為樣本集。在這個案例中，每一個城市都被表示為一個多值對象，每個值被看作是一個范例或是一個樣本。再比如，對研究小組的評價其中每個研究小組都是一個多值對象，每個員工的教學(xué)與研究績效評價都對應(yīng)一個范例。由于各種因素，像在不同城市中樣本有效性的不同，每個城市樣本的數(shù)量是不同的。類似的，根據(jù)范例的含義，2個研究小組的大小也可能是不同的，如，家庭的大小和員工的職位，這些范例可能有不同的權(quán)重。同樣，上述的體育實例中，每個球員都被視為一個多值對象的球員，其中球員每場比賽的統(tǒng)計（得分、助攻、籃板）都被視為具有相同權(quán)重的一個實例（其被標準化）。

上述實例包含了在一維空間的多值對象和單值點的查詢，研究覆蓋的數(shù)據(jù)對象是由在d維空間的多范例組成的，查詢對象也可以由在d維空間的多范例組成。例如，在NBA中，通過對球員的統(tǒng)計（得分、助攻、籃板、搶斷、蓋帽）來衡量每場比賽的球員的成績，都可以被看作是球員的一個范例，因此，每個球員都是一組范例。假設(shè)某個球隊想和球員A簽訂一個合同，想找出球員A的市場價值，針對球員最近比賽的成績，球隊可能想找出top-k與A“相似”的且具有存在合同的NBA球員。然后，球隊可以使用這K個球員的薪資信息來預(yù)測計劃A的薪資等級。

4 結(jié)語

本文具體分析了分位數(shù)概要數(shù)據(jù)結(jié)構(gòu)的主要特點，針對K-最近鄰居算法特性及特點進行了詳細的分析，展望了多值對象的KNN問題的主要應(yīng)用，并給出了實際的案例。