基于分位數概要的KNN算法研究

王丹

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

關鍵詞：分位數；KNN

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

1 分位數

分位數又稱次序統計量，中位數是一個特例，分位數是關于數據分布的一個重要統計量。數據項完全有序數據集D的φ-quantile，就是使D中的秩（秩為數據集合的元素的個數）為φ|D|的那個元素，其中0<φ<1，一般方便起見，對于分位數問題通常假定在D中沒有重復元素。一個分位數概要包含很多信息，以便對于任何0<φ<1，可以定義一個很小的實數δ，返回一個φ′-分位數近似φ-分位數，其中φ-ε≤φ′≤φ+ε。一個分位數概要大小為0（1，ε），通過排序D，然后得到這些數據項的秩分別是ε|D|，2ε|D|，3ε|D|，……|D|。可以很容易地計算分位數。

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

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

2 KNN分析

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

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

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

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

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

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

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

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

3 多值對象的KNN研究展望

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

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

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

4 結語

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