王丹

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

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

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

1 分位數(shù)

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

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

例如，在圖1中顯示了一個(gè)數(shù)據(jù)流產(chǎn)生數(shù)據(jù)的樣本序列，其中每個(gè)數(shù)據(jù)元素由一個(gè)數(shù)據(jù)值表示，數(shù)據(jù)元素到達(dá)的順序?yàn)閺淖笾劣?，在序列中?shù)據(jù)元素的數(shù)量是16，序列排序后的順序?yàn)?，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ù)法中最重要的方法之一。近鄰法的一個(gè)嚴(yán)重問題是需要存儲(chǔ)全部訓(xùn)練樣本，以及繁重的距離計(jì)算量。

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

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

KNN基本規(guī)則是：在所有N個(gè)樣本中找到與測(cè)試樣本的K個(gè)最近鄰者，其中各類別所占個(gè)數(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方法的思路是：如果一個(gè)樣本在特征空間中的K個(gè)最相似（即特征空間中最近鄰）的樣本中的大多數(shù)屬于某一個(gè)類別，則該樣本也屬于這個(gè)類別。KNN算法中，所選擇的鄰居都是已經(jīng)正確分類的對(duì)象。該方法在定類決策上只依據(jù)最鄰近的一個(gè)或者幾個(gè)樣本的類別來決定待分樣本所屬的類別。KNN方法雖然從原理上也依賴于極限定理，但在類別決策時(shí)，只與極少量的相鄰樣本有關(guān)。

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

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

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

3 多值對(duì)象的KNN研究展望

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

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

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

4 結(jié)語(yǔ)

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