基于對(duì)象數(shù)量的寬度加權(quán)聚類(lèi)kNN算法

陳 輝，關(guān)凱勝，李嘉興 ，2

1.廣東工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院，廣州 510006

2.廣東省大數(shù)據(jù)分析與處理重點(diǎn)實(shí)驗(yàn)室，廣州 510006

1.School of Computer Science and Technology,Guangdong University of Technology,Guangzhou 510006,China

2.Guangdong Key Laboratory of Big Data Analysis and Processing,Guangzhou 510006,China

1 引言

k最近鄰算法廣泛用于數(shù)據(jù)挖掘和數(shù)據(jù)分析中，這種算法以一個(gè)樣本集和一個(gè)查詢對(duì)象作為輸入，能夠找出距離查詢對(duì)象最近（或相似度較高）的k個(gè)對(duì)象。kNN算法是一種經(jīng)典的方法，在不同領(lǐng)域有著廣泛的應(yīng)用[1]，例如數(shù)據(jù)分類(lèi)[2-4]、空間數(shù)據(jù)庫(kù)查詢、入侵檢測(cè)[5-6]、模式識(shí)別[7]、異常值檢測(cè)[8-10]、道路網(wǎng)絡(luò)查詢[11]、文本分類(lèi)[12]等。目前很多與kNN算法相關(guān)的研究已經(jīng)提出了許多改進(jìn)方法用于計(jì)算得到精確結(jié)果或者近似結(jié)果。在損失精度的前提下取得近似結(jié)果，這種方式效率較高。與此相反，雖然得到精確結(jié)果的算法更為復(fù)雜，但是能得到精確的結(jié)果。傳統(tǒng)計(jì)算精確結(jié)果的方法需要遍歷整個(gè)數(shù)據(jù)集，為了解決這個(gè)問(wèn)題，目前很多研究工作都集中在數(shù)據(jù)的預(yù)處理上，其目的是通過(guò)計(jì)算數(shù)據(jù)集的一部分來(lái)找到查詢對(duì)象的k個(gè)精確最近鄰（k-NNs）。

一些研究提出基于樹(shù)[13-16]的索引結(jié)構(gòu)對(duì)數(shù)據(jù)進(jìn)行預(yù)處理，其索引結(jié)構(gòu)采用二進(jìn)制分區(qū)技術(shù)對(duì)數(shù)據(jù)進(jìn)行預(yù)處理，每個(gè)樹(shù)的葉節(jié)點(diǎn)中包含距離相近的對(duì)象。kNN算法利用樹(shù)的索引結(jié)構(gòu)對(duì)數(shù)據(jù)進(jìn)行預(yù)處理并使用三角不等式修剪不包含結(jié)果的節(jié)點(diǎn)。高維數(shù)據(jù)往往具有稀疏而且不相似的特點(diǎn)，使用基于樹(shù)的索引結(jié)構(gòu)其內(nèi)部節(jié)點(diǎn)之間將會(huì)有較高的重疊度。因此三角不等式將無(wú)法修剪大多數(shù)的節(jié)點(diǎn)。為了解決上述問(wèn)題，現(xiàn)有工作使用聚類(lèi)技術(shù)將數(shù)據(jù)集劃分為一些數(shù)據(jù)集群以得到更好的聚類(lèi)結(jié)果。固定寬度聚類(lèi)（FWC）[17-18]、k-Means[19]和kNNVWC[20]這三種算法是根據(jù)特征空間直接將數(shù)據(jù)集劃分為若干個(gè)子集群，并使用產(chǎn)生的子集群有效地計(jì)算k-NNs。FWC算法生成的每個(gè)集群都有相同的半徑，這將導(dǎo)致部分集群擁有大量的對(duì)象，而部分集群對(duì)象數(shù)量則很少，這將不利于修剪數(shù)據(jù)。kNNVWC算法是對(duì)FWC算法的一個(gè)改進(jìn)，但是這種方法需要進(jìn)行復(fù)雜的寬度學(xué)習(xí)，增加聚類(lèi)的迭代次數(shù)，相應(yīng)的會(huì)導(dǎo)致預(yù)處理時(shí)間的增加。k-Means算法將稀疏分布的對(duì)象分給最接近的集群，因此生成的集群可能會(huì)有一個(gè)很大的半徑。

針對(duì)上述方法的局限性，本文提出一種新的基于對(duì)象數(shù)量的寬度加權(quán)聚類(lèi)算法用于kNN查詢（NOWCkNN）。該算法能產(chǎn)生分布較好的集群，同時(shí)建模時(shí)間會(huì)明顯的減少。本文的貢獻(xiàn)如下：

（1）提出一種新的數(shù)據(jù)聚類(lèi)算法，在不同分布的高維數(shù)據(jù)中生成較好的集群。該算法既有基于tree index聚類(lèi)算法的優(yōu)點(diǎn)，也繼承了基于flat index聚類(lèi)算法的特點(diǎn)。這樣該算法不需要經(jīng)過(guò)大量計(jì)算便可得到聚類(lèi)寬度值，更加有利于劃分?jǐn)?shù)據(jù)集，能夠有效地減少迭代次數(shù)，降低聚類(lèi)時(shí)間。

（2）基于對(duì)象數(shù)量的寬度加權(quán)聚類(lèi)算法，提出NOWCkNN算法用于kNN查詢。不同于FWC算法，該算法的寬度值是可調(diào)節(jié)的，根據(jù)其對(duì)象數(shù)量和調(diào)和系數(shù)能有效的調(diào)節(jié)寬度權(quán)值，從而減少迭代計(jì)算。

2 相關(guān)工作

在沒(méi)有數(shù)據(jù)預(yù)處理的情況下計(jì)算一個(gè)給定查詢對(duì)象的k個(gè)最近鄰需要計(jì)算整個(gè)數(shù)據(jù)集，現(xiàn)有的研究工作是為數(shù)據(jù)建立一個(gè)索引結(jié)構(gòu)以避免計(jì)算整個(gè)數(shù)據(jù)集?，F(xiàn)有的方法大致分為兩類(lèi)：近似搜索算法和精確搜索算法。

2.1 近似搜索算法

kNN近似搜索算法在處理高維數(shù)據(jù)時(shí)具有很好的性能，但是它的結(jié)果精確度較差，得到的k個(gè)鄰居中并不都是最近的。局部敏感哈希算法（LSH）[21]包含幾個(gè)哈希函數(shù)，該方法基于越緊密聯(lián)系的對(duì)象就越有可能擁有較相近的哈希值這樣一個(gè)假設(shè)?；贚SH也提出了很多方法，如多探針LSH[22]和LSH森林[23]，前者減少了哈希表的數(shù)量但是增加了存儲(chǔ)空間，而后者移除了手動(dòng)調(diào)整參數(shù)的必要性。最近以空間分區(qū)結(jié)構(gòu)為基礎(chǔ)的算法被用于kNN的近似搜索，例如隨機(jī)kd樹(shù)[24]和k-Means優(yōu)先搜索樹(shù)[25]，這些算法比LSH算法在近似查詢方面有更好的表現(xiàn)。

2.2 精確搜索算法

2.2.1 Tree-Based Index

目前有很多研究使用二叉樹(shù)[14，26-27]（例如KDTree[26]）來(lái)構(gòu)建數(shù)據(jù)集的索引結(jié)構(gòu)，每個(gè)樹(shù)的葉節(jié)點(diǎn)都包含彼此相近的對(duì)象。這些葉節(jié)點(diǎn)的集合組成父節(jié)點(diǎn)，其父節(jié)點(diǎn)都包含彼此相近的子節(jié)點(diǎn)，這個(gè)過(guò)程被遞歸的調(diào)用，直到根節(jié)點(diǎn)包含所有節(jié)點(diǎn)。kNN算法利用基于樹(shù)的索引方法，使用三角不等式來(lái)修剪不包含結(jié)果的節(jié)點(diǎn)。每個(gè)基于樹(shù)的索引以不同的遞歸調(diào)用方式構(gòu)建索引結(jié)構(gòu)，樹(shù)型索引的主要不足在于采用二進(jìn)制分割技術(shù)構(gòu)建索引結(jié)構(gòu)。該方式對(duì)于對(duì)象分布未知且維度較高的數(shù)據(jù)集并不是一個(gè)很好的解決方法。高維數(shù)據(jù)往往是比較少而且也不相似的，基于樹(shù)的索引結(jié)構(gòu)其內(nèi)部節(jié)點(diǎn)之間將會(huì)有很高的重疊度，因此使用三角不等式將無(wú)法修剪掉大多數(shù)的節(jié)點(diǎn)，kNN算法通常還是需要遍歷整個(gè)數(shù)據(jù)集（或數(shù)據(jù)集的大部分）。

2.2.2 Flat-Based Index

當(dāng)樹(shù)節(jié)點(diǎn)之間的重疊度較高時(shí)，樹(shù)結(jié)構(gòu)就失去了作用。受此啟發(fā)，一些研究提出Flat-Based Index，例如FWC[17-18]、k-Means[19]和 kNNVWC[20]算法，這些方法使用聚類(lèi)算法直接將數(shù)據(jù)集分成集群來(lái)獲取更好的分區(qū)效果，并使用這些集群來(lái)有效地計(jì)算k-NNs。

現(xiàn)有的Flat Index聚類(lèi)方法可能會(huì)產(chǎn)生分布不均的集群，其生成的集群大小差別很大，這會(huì)降低三角不等式的修剪效率。例如，k-Means將稀疏的對(duì)象分配給其最近的集群，因此這些集群的半徑會(huì)很大，與其他集群重疊度就會(huì)很高，這也就增加了kNN算法的查詢時(shí)間。同樣地，F(xiàn)WC算法生成集群中的對(duì)象數(shù)量并不均勻，該算法的時(shí)間復(fù)雜度為O(cs)，其中s為對(duì)象的數(shù)量，c為產(chǎn)生集群的數(shù)量。設(shè)置一個(gè)較小的固定寬度值可以防止較大集群的產(chǎn)生，但是這將會(huì)導(dǎo)致產(chǎn)生大量的集群，無(wú)疑會(huì)增加預(yù)處理時(shí)間。針對(duì)FWC算法的不足，Almalawi等人[20]提出一種寬度自學(xué)習(xí)聚類(lèi)算法，該算法把數(shù)據(jù)集分割成多個(gè)不同寬度大小的集群。但是這種方法在集群再次劃分時(shí)需要進(jìn)行集群寬度計(jì)算，對(duì)于生成有較多對(duì)象的集群，需要經(jīng)過(guò)多次迭代才能很好的分割數(shù)據(jù)，這會(huì)導(dǎo)致聚類(lèi)過(guò)程需要不斷的迭代進(jìn)行?；诖朔N情況，本文提出一種基于對(duì)象數(shù)量的寬度加權(quán)聚類(lèi)算法用于kNN查詢，每個(gè)集群的寬度在聚類(lèi)時(shí)根據(jù)對(duì)象數(shù)量進(jìn)行寬度自學(xué)習(xí)。

3 提出的寬度加權(quán)聚類(lèi)算法

針對(duì)上述方法的不足，本文提出一種基于對(duì)象數(shù)量的寬度加權(quán)聚類(lèi)算法，該算法是在FWC算法的基礎(chǔ)上進(jìn)一步聚類(lèi)劃分。本章首先介紹FWC的聚類(lèi)步驟，然后介紹NOWCkNN算法的兩部分：聚類(lèi)和查詢。

3.1 FWC算法

定義1待聚類(lèi)數(shù)據(jù)集DS：DS={O1,O2,…,On}，其中Oi為數(shù)據(jù)集DS的第i個(gè)對(duì)象，n為對(duì)象的個(gè)數(shù)。

定義2對(duì)象O={a1,a2,…,aj,…,am}，其中aj為對(duì)象Oi的第 j個(gè)屬性，m為每個(gè)對(duì)象屬性的個(gè)數(shù)。

定義3聚類(lèi)輸出集群集合C={C1,C2,…,Ct,…,Cn}，其中n為聚類(lèi)生成的集群數(shù)，Ct表示第t個(gè)集群。

定義4集群C={Cd,Cc,Cw}，其中Cd用來(lái)存儲(chǔ)生成集群的數(shù)據(jù)，Cc存儲(chǔ)集群的中心，Cw存儲(chǔ)集群的半徑寬度。

固定寬度聚類(lèi)（FWC）算法[17-18]是將數(shù)據(jù)集分成多個(gè)具有相同半徑的集群。算法1描述了FWC的算法步驟，表1是對(duì)算法1中一些符號(hào)和函數(shù)的定義。FWC算法每次分割一個(gè)數(shù)據(jù)集。首先把數(shù)據(jù)集中第一個(gè)對(duì)象設(shè)為第一個(gè)集群的中心（5～8行），對(duì)于下一個(gè)對(duì)象需要先計(jì)算距離其最近的一個(gè)集群did，并與固定寬度值W比較（第6行）。如果計(jì)算距離值did大于W，則需要重新創(chuàng)建一個(gè)集群并把此對(duì)象插入該集群（第8行）；若距離did不大于W ，則把此對(duì)象插入到該集群中（9～10行）。比較距離did與該集群的半徑wid，若小于半徑wid，則需要重新更新其半徑值（11～12行）。算法依次循環(huán)執(zhí)行，直到數(shù)據(jù)集中的對(duì)象都被分到不同的集群中。

表1 算法1的符號(hào)和函數(shù)定義

算法1 FWC算法

1.InputDS

2.OutputC

4.n=0

5.forOiinDS.objects

7.n=n+1

8.addOitoCnew

9.else ifdid≤W

10.addOitoCid

11.ifdid＜wid

12.setwid=did

13.returnC

FWC算法的性質(zhì)限制了它在異常檢測(cè)中的應(yīng)用，創(chuàng)建具有固定寬度的集群集合可能無(wú)法修剪大多數(shù)的數(shù)據(jù)對(duì)象。Eskin等人[17]提出的FWC算法雖然可以將數(shù)據(jù)集分解成較小的集群，并用這種方法找到查詢對(duì)象的k-NNs。然而當(dāng)數(shù)據(jù)分布不均時(shí)，這種分解效果并不是很好，雖然kNNVWC算法[20]對(duì)此進(jìn)行了改進(jìn)，但是其寬度計(jì)算量偏大，算法迭代次數(shù)較多，不能很好地控制生成集群的大小，同時(shí)該算法寬度的計(jì)算會(huì)隨著維度的升高而增加。

聚類(lèi)產(chǎn)生較好的集群能夠有效的提高kNN算法的修剪率?；诖死碚摚枰M可能的生成效果較好的集群。數(shù)據(jù)的聚類(lèi)需要經(jīng)過(guò)大量的計(jì)算，要產(chǎn)生效果較好的集群還需要避免計(jì)算量過(guò)大。集群的大小或者集群數(shù)量都能影響聚類(lèi)的效果，集群的寬度決定集群的大小和產(chǎn)生集群的數(shù)量。因此需要調(diào)整集群寬度的大小，使其能夠產(chǎn)生質(zhì)量較好的集群。每個(gè)集群的寬度與集群中的對(duì)象數(shù)量正相關(guān)，根據(jù)對(duì)象數(shù)量調(diào)整寬度再設(shè)置一個(gè)系數(shù)調(diào)節(jié)大小，可以有效地控制不同集群寬度的產(chǎn)生。例如，超過(guò)閾值具有相同對(duì)象數(shù)量的集群，其集群寬度可能會(huì)不相同。對(duì)于寬度較大的集群，其數(shù)據(jù)相對(duì)稀疏，設(shè)置較小的系數(shù)，使寬度權(quán)值相對(duì)較大，這樣可以減少集群的數(shù)量，避免產(chǎn)生具有極少對(duì)象的集群；對(duì)于寬度較小的集群，其數(shù)據(jù)相對(duì)稠密，設(shè)置較大的系數(shù)，使寬度值相對(duì)較小，這樣可以減少迭代。

3.2 基于對(duì)象數(shù)量的寬度加權(quán)聚類(lèi)算法

3.2.1 集群寬度加權(quán)計(jì)算

令D為要進(jìn)行聚類(lèi)的數(shù)據(jù)集，s為數(shù)據(jù)集中的對(duì)象數(shù)量，函數(shù)Quotien(a,b)返回a/b的整數(shù)部分，用ωCn表示第n個(gè)集群的半徑寬度，p為調(diào)和系數(shù)。此過(guò)程中有一個(gè)變量：閾值β，這是用來(lái)限定集群大小的閾值，集群中的對(duì)象數(shù)量不能超過(guò)閾值β，其寬度表達(dá)式如下：

這里調(diào)和系數(shù) p的大小和函數(shù)Quotien的范圍將會(huì)影響到聚類(lèi)的效果，在4.2節(jié)中會(huì)分析 p的大小和函數(shù)Quotien的范圍。

3.2.2 聚類(lèi)過(guò)程

該過(guò)程將數(shù)據(jù)集劃分成多個(gè)集群，以解決在高維空間中數(shù)據(jù)對(duì)象的聚類(lèi)問(wèn)題。但是，數(shù)據(jù)集中在數(shù)據(jù)比較集中的區(qū)域可能會(huì)有大的集群產(chǎn)生，因此需要將產(chǎn)生具有較多對(duì)象的集群再次進(jìn)行劃分，直到每個(gè)集群的大小都不超過(guò)所規(guī)定的閾值（最大值）。本文在算法2中總結(jié)了聚類(lèi)過(guò)程，表2是算法2的一些符號(hào)和函數(shù)定義。

算法首先把數(shù)據(jù)集劃分為具有固定寬度的集群（第3行），初始化迭代次數(shù)為1。然后循環(huán)找出對(duì)象數(shù)量大于β的集群，把這些對(duì)象數(shù)量大于β的集群添加到MultiClusters中（5～7行），把對(duì)象數(shù)量小于 β的集群添加到LessClusters（第9行），同時(shí)標(biāo)記對(duì)象數(shù)量小于β的集群為不可再分（第10行）。對(duì)于對(duì)象數(shù)量大于β的集群需要重新計(jì)算其寬度值，用公式（1）的方法計(jì)算集群下一次聚類(lèi)時(shí)的寬度值（第13行），然后繼續(xù)對(duì)該集群進(jìn)行劃分，迭代的劃分集群直到所有集群中的對(duì)象數(shù)量都不大于β（第16～17行）。每次迭代后，迭代次數(shù)都要加1（第18行）。

表2 算法2的符號(hào)和函數(shù)定義

算法2 NOWC算法

1.Input：data

2.Input：β

3.Clusters=Algorithm1（data，W）

4.t=1

5.foreach cluster in Clusters

6.ifcluster.objects＞β

7.put cluster in Multi Cluster

8.else

9.put cluster in Less Clusters

10.LessClusters←NonCluster

11.for each cluster in Multib Clusters

12.D←cluster.data

13.w ← equation（1）

14.tmp Clusters← Algorithm1（D，w）

15.put tmp Clusters into new CLusters

16.for new Clusters

17.go to line 4

18.t+=1

19.return

同時(shí)設(shè)定其迭代上限為t（t通常小于等于3），由于迭代次數(shù)越多生成集群的數(shù)量就會(huì)相應(yīng)的增加，集群中對(duì)象的數(shù)量就會(huì)越來(lái)越少。此時(shí)進(jìn)行kNN查詢時(shí)，這會(huì)增加計(jì)算消耗。在每次迭代時(shí)，設(shè)定迭代聚類(lèi)產(chǎn)生的集群數(shù)量都不大于前一個(gè)迭代聚類(lèi)產(chǎn)生的集群數(shù)量，這樣可以防止較小集群的產(chǎn)生，提高聚類(lèi)質(zhì)量，提升kNN查詢時(shí)的修剪率。

3.3 kNN查詢過(guò)程

定義5（k-最近鄰（kNN））一個(gè)查詢對(duì)象q的k個(gè)最近鄰居到q的距離小于數(shù)據(jù)集中剩余對(duì)象到q的距離。設(shè)Uqk={X1,X2,…,Xk}是查詢對(duì)象q的k個(gè)最近鄰對(duì)象，MAXk表示查詢對(duì)象q與數(shù)據(jù)中所有對(duì)象的距離按從小到大排序的第k個(gè)距離值，則其k個(gè)最近鄰表示為：

定義6（候選集群）對(duì)于給定的查詢對(duì)象q，其中Li={O1,O2,…,Ok}是q在集群Ci的最近鄰對(duì)象，wk表示q到其k個(gè)最近鄰中最遠(yuǎn)對(duì)象的距離，wi是集群Ci的半徑寬度，C={C1,C2,…,Cn}是集群的集合，其中，如果，則集群Cm是 q的一個(gè)候選集群。

表3 算法3的符號(hào)和函數(shù)定義

算法3 NOWCkNN算法

1.Input：Clusters

2.Input：k

3.Input：q

4.Output：kNNObjects

6.CluDisID ← SortClustersByq（Clusters，q）

7.foreach{ID，Distance}in CluDisID

8.tmpCluster=getCluster（ID）

9.kNNObjects=kNNObjects∪tmpCluster.Objects

10.If|kNNObjects|＞k

11.break

12.{wk，kNNObjects}=kNNDistance（kNNObjects，q，k）

13.foreach CluDisID

14.tmpCluster← getCluster（ID）

15.if（tmpCluster.radius+wk）＞CluDisID.Distance

16.put tmpCluster.Objects in kNNObjects

17.go to line 12

18.else（tmpCluster.radius+wk）＜=CluDisID.Distance

19.continue

20.return kNNObjects

如圖1的B所示，Ci是要進(jìn)行計(jì)算的下一個(gè)集群，{O1,O2,O3,O4,O5}是集群Ci的對(duì)象，其中O1是集群Ci的中心，集群半徑radius為23.5。查詢對(duì)象q到集群中心的距離為w=32.4，以q為圓心，wk為半徑畫(huà)圓，該圓到集群中心O1的距離小于兩個(gè)圓半徑的距離之和（第15～16行），即32.4＜23.5+14.7，則此聚類(lèi)中可能存在比wk更近的對(duì)象，然后把此集群添加到候選集群表中，并把候選集群中的對(duì)象添加到候選對(duì)象表中，重新計(jì)算其k個(gè)最近鄰和到第k個(gè)鄰居的距離wk（第17行）。如圖1的A所示若兩個(gè)圓沒(méi)有相交，則說(shuō)明此集群中不存在比wk更近的對(duì)象了，此集群被修剪。算法循環(huán)遍歷每個(gè)集群，直到所有集群到查詢對(duì)象q的距離都大于其集群半徑和wk之和（如圖1的A所示），則算法停止，返回這k個(gè)最近鄰對(duì)象（第20行）。

時(shí)間復(fù)雜度分析：

4 實(shí)驗(yàn)結(jié)果與分析

本章中，在各種數(shù)據(jù)集中驗(yàn)證NOWCkNN算法的性能，實(shí)驗(yàn)從三方面分析算法的性能：（1）建模過(guò)程消耗的時(shí)間；（2）進(jìn)行距離計(jì)算的對(duì)象數(shù)量；（3）kNN查詢所用時(shí)間。將四個(gè)算法KDTree、kNNVWC、FWC、k-Means與NOWCkNN算法進(jìn)行比較，每次實(shí)驗(yàn)時(shí)將整個(gè)數(shù)據(jù)集作為訓(xùn)練集，隨機(jī)從訓(xùn)練集中選取一些對(duì)象作為測(cè)試集，所有測(cè)試對(duì)象的平均值作為總體結(jié)果。所有算法都是用Java實(shí)現(xiàn)，實(shí)驗(yàn)操作系統(tǒng)為macOS，CPU頻率為2.9 GHz，內(nèi)存為8 GB。

4.1 數(shù)據(jù)集

選用不同維度特征空間的數(shù)據(jù)集用于測(cè)試所提出算法的性能，這些被選擇的UCI公開(kāi)數(shù)據(jù)集來(lái)自各個(gè)領(lǐng)域，被廣泛地應(yīng)用于數(shù)據(jù)挖掘，只是使用它們來(lái)驗(yàn)證NOWCkNN算法在k最近鄰搜索中的性能。這些數(shù)據(jù)集的簡(jiǎn)要描述如下：

shuttle數(shù)據(jù)集有43 500個(gè)對(duì)象組成，每個(gè)對(duì)象有9個(gè)數(shù)字特征表示，它用于歐洲StatLog項(xiàng)目測(cè)試機(jī)器學(xué)習(xí)的性能；

arcene數(shù)據(jù)集通過(guò)SELDI獲得的觀測(cè)數(shù)據(jù)，用于從正常模式中辨別出癌癥，該數(shù)據(jù)集有900個(gè)對(duì)象，每個(gè)對(duì)象有1 000個(gè)特征屬性；

waveform數(shù)據(jù)集由5 000個(gè)對(duì)象組成，每個(gè)對(duì)象有40個(gè)特征，其中有一些噪音數(shù)據(jù)；

圖1 基于三角不等式的NOWCkNN查詢實(shí)例

spambase數(shù)據(jù)集有4 601個(gè)（電子郵件）對(duì)象，其中包含1 443條垃圾郵件，每個(gè)對(duì)象有57個(gè)屬性；

optdigits數(shù)據(jù)集是識(shí)別0～9的數(shù)字，optdigits數(shù)據(jù)集訓(xùn)練集有3 823個(gè)對(duì)象，測(cè)試集有1 797個(gè)對(duì)象，每個(gè)對(duì)象有65個(gè)屬性；

madelon是NIPS 2003比賽中5組數(shù)據(jù)集中的其中一組，共有數(shù)據(jù)對(duì)象4 400個(gè)，每個(gè)數(shù)據(jù)有500個(gè)屬性；

gasSensors是來(lái)自16個(gè)傳感器的13 910個(gè)對(duì)象，每個(gè)傳感器提取8個(gè)特征，這使每個(gè)對(duì)象有128個(gè)特征屬性；

DUWWTP數(shù)據(jù)集來(lái)自城市廢水處理廠的傳感器的日常測(cè)量值，由527個(gè)對(duì)象組成，每個(gè)對(duì)象有38個(gè)特征。

4.2 參數(shù)的設(shè)置

不同的算法需要不同的參數(shù)設(shè)置，對(duì)于FWC算法最重要參數(shù)的就是集群寬度，而k-Means方法最重要的參數(shù)就是k值的選擇。文獻(xiàn)[19]提出的k-Means方法證明了k值為2時(shí)效果最佳，其中s為數(shù)據(jù)集的大小。對(duì)于FWC算法，找到合適的寬度值是非常困難的，因此本文選擇產(chǎn)生集群數(shù)量盡可能接近2。本次實(shí)驗(yàn)中KDTree方法的葉子大小設(shè)置為40，該數(shù)值對(duì)于大多數(shù)的數(shù)據(jù)集能取得最佳效果。由于本文所提方法不確定所產(chǎn)生的集群數(shù)，因此測(cè)試了β的各種取值，選擇在不同維度、不同大小以及不同領(lǐng)域的數(shù)據(jù)集進(jìn)行測(cè)試。如圖2所示，橫坐標(biāo)表示生成的集群數(shù)量，調(diào)整β值改變生成的集群數(shù)量。如圖2所示，各個(gè)數(shù)據(jù)集聚類(lèi)產(chǎn)生集群數(shù)大約在到3之間時(shí)算法的性能較好，因此把生成此范圍集群數(shù)量的β值作為最優(yōu)β值。

式（1）中調(diào)和系數(shù) p的大小將會(huì)直接影響到生成集群的數(shù)量，而函數(shù)Quotient的取值范圍也會(huì)影響到算法的性能。一個(gè)較大的 p值會(huì)使每次迭代計(jì)算得到的寬度值都接近于最小寬度值，這會(huì)導(dǎo)致有大量的集群產(chǎn)生。函數(shù)Quotient的取值范圍越大則迭代的寬度值越小，其取值越小的情況下其迭代得到的寬度值越大，寬度值較小則會(huì)產(chǎn)生大量的聚類(lèi)，較大則會(huì)增加迭代次數(shù)，影響算法性能，因此產(chǎn)生較好的聚類(lèi)效果依賴于調(diào)和系數(shù)p的大小和函數(shù)Quotient取值范圍。在這次測(cè)試中選擇的數(shù)據(jù)集在維度、數(shù)據(jù)集大小和疏密度方面都有差異。用對(duì)象距離修剪率ord表示數(shù)據(jù)集的修剪效率，其計(jì)算表達(dá)式為：

其中，s為數(shù)據(jù)集的大小，Cm為在數(shù)據(jù)集中找到k個(gè)最近鄰參與計(jì)算的集群數(shù)量。

如圖3所示，較高維度的數(shù)據(jù)集arcene中寬度值較大，數(shù)據(jù)較為分散，p值越大其聚類(lèi)寬度值在迭代時(shí)減小的越快，而產(chǎn)生聚類(lèi)的對(duì)象數(shù)量很難影響函數(shù)Quotient的取值。從圖3（a）中可以看出，提出算法在p=2時(shí)各個(gè)數(shù)據(jù)集都具有較高的數(shù)據(jù)修剪率，而函數(shù)Quotient范圍在QMAX=6時(shí)（即取值范圍2至6之間）效果較好。而在數(shù)據(jù)集shuttle、pendigits和spambase中，p的值為2或3時(shí)較好，函數(shù)Quotient范圍在2與6之間時(shí)其數(shù)據(jù)修剪率較高，效果最優(yōu)。因此，在聚類(lèi)時(shí)參數(shù) p的值一般設(shè)為2或3，其函數(shù)Quotient范圍為2至6。對(duì)于 p值較大時(shí)，可能也會(huì)取得較好的結(jié)果，但是這樣會(huì)導(dǎo)致一些數(shù)據(jù)集有大量的集群產(chǎn)生，這樣不利于基于三角不等式的kNN查詢。同時(shí)Quotient函數(shù)范圍小于2或者大于7時(shí)，如圖3所示算法的性能明顯下降，根據(jù)算法的時(shí)間復(fù)雜度降低迭代次數(shù)能夠有效地降低計(jì)算量。因此，當(dāng)Quotient函數(shù)范圍小于2時(shí)，寬度值減少的速率較慢，這無(wú)疑會(huì)增加迭代次數(shù)，當(dāng)范圍大于7時(shí)寬度值較小，則會(huì)產(chǎn)生大量的集群。

從圖3中可以設(shè)定Quotient(s,β)函數(shù)的范圍為2≤Quotient(s,β)≤6（即QMAX=6），Quotient函數(shù)值大于6的時(shí)候，設(shè)其值為6，特別地，Quotient函數(shù)值為0或1的時(shí)候，設(shè)其值為2。使用式（1）中寬度計(jì)算公式，設(shè)定其迭代的子集群寬度權(quán)值最小為父類(lèi)寬度值的0.4倍，最大為父類(lèi)寬度值的0.8倍。聚類(lèi)中對(duì)象數(shù)量越多其寬度值權(quán)值則越小，這樣可以減少算法迭代的次數(shù)，同時(shí)能夠減少聚類(lèi)時(shí)間。其函數(shù)范圍表示如下：

圖2 不同β值對(duì)應(yīng)生成的集群數(shù)量對(duì)算法性能的影響

圖3 不同p值和不同函數(shù)Quotient的范圍對(duì)本文算法性能的影響

4.3 性能指標(biāo)

原始kNN查詢方法的不足在于它需要一個(gè)冗長(zhǎng)的計(jì)算時(shí)間，這是由于對(duì)數(shù)據(jù)集中的每個(gè)對(duì)象都要進(jìn)行距離計(jì)算。因此現(xiàn)有的改進(jìn)kNN搜索方法的主要目標(biāo)就是減少數(shù)據(jù)集中對(duì)象的距離計(jì)算，為了衡量這種方法的效率，采用建模時(shí)間、kNN查詢時(shí)間和數(shù)據(jù)集中參與距離計(jì)算對(duì)象的數(shù)量作為評(píng)價(jià)標(biāo)準(zhǔn)。

4.3.1建模時(shí)間

這些方法都是kNN搜索之前的預(yù)處理步驟，每個(gè)方法都以自己的分解技術(shù)來(lái)構(gòu)建索引結(jié)構(gòu)。圖4顯示了這幾種方法在每個(gè)數(shù)據(jù)集上的建模時(shí)間，從圖中可以看出k-Means方法是最差的，而且會(huì)受到數(shù)據(jù)大小的影響，固定寬度算法（FWC）則是第二差的方法，相較于kNNVWC與NOWCkNN方法，F(xiàn)WC算法的建模時(shí)間通常是比較長(zhǎng)的。而KDTree方法在低維度數(shù)據(jù)集中效果較好，在高維度數(shù)據(jù)集中建模時(shí)間較長(zhǎng)。kNNVWC由于每次進(jìn)行聚類(lèi)迭代時(shí)，寬度計(jì)算都會(huì)消耗大量的時(shí)間。本文所提方法NOWCkNN建模時(shí)間相對(duì)較短，對(duì)比kNNVWC算法，NOWCkNN能減少寬度學(xué)習(xí)時(shí)的對(duì)象計(jì)算消耗，對(duì)于不同數(shù)據(jù)集都能得到較好的聚類(lèi)集群。對(duì)于高維數(shù)據(jù)，本文所提方法的建模時(shí)間相較于其他方法有明顯優(yōu)勢(shì)，建模時(shí)間低于其他方法，對(duì)于其他維度的數(shù)據(jù)也有很好的效果。

圖4 本文方法和其他方法在每個(gè)數(shù)據(jù)集上的建模時(shí)間

4.3.2查詢時(shí)間加速率

對(duì)比原始kNN算法評(píng)估所提出算法的性能，令ty表示原始kNN算法的查詢時(shí)間，tn表示運(yùn)行一個(gè)算法的kNN查詢時(shí)間，算法的查詢時(shí)間加速率sr表示為：

查詢時(shí)間加速率反應(yīng)了改進(jìn)算法對(duì)于原始kNN算法的影響程度，即查詢時(shí)間加速率為2說(shuō)明該算法相較于原始kNN算法提高了1倍，加速率為0.5說(shuō)明算法比原始kNN慢了1倍。同時(shí)，當(dāng)加速率為1時(shí)說(shuō)明，該算法和原始kNN查詢時(shí)間相同，也就是說(shuō)對(duì)數(shù)據(jù)進(jìn)行預(yù)處理后并沒(méi)有減少查詢時(shí)間，反而有可能增加查詢時(shí)間。因此把sr=1作為一個(gè)分界點(diǎn)，大于1說(shuō)明該方法效果較好，能夠減少kNN查詢的時(shí)間；不大于1時(shí)表示數(shù)據(jù)的建模沒(méi)有減少查詢時(shí)間，說(shuō)明該數(shù)據(jù)集不用預(yù)處理即可實(shí)現(xiàn)查詢。

在kNN查詢時(shí)，把k值設(shè)為5種不同的取值，分別為10、20、50、100、200，圖5顯示了不同方法在不同數(shù)據(jù)集以及不同k值的查詢時(shí)間加速率。從圖中可以看出KDTree方法在高維數(shù)據(jù)中效果不佳，但是在維度較低時(shí)能夠得到較好的結(jié)果。在一些大的數(shù)據(jù)集中（如shuttle、gasSensors），雖然FWC、kNNVWC、NOWCkNN、k-Means方法得到了很好的結(jié)果，但是綜合來(lái)說(shuō)NOWCkNN是最有效的方法。對(duì)于一些中等數(shù)據(jù)集KDTree方法效果較差，k-Means方法受到數(shù)據(jù)集分布的影響表現(xiàn)出稍差的結(jié)果。在高維數(shù)據(jù)集（如arcene、madelon）中，數(shù)據(jù)量較小時(shí)，NOWCkNN與kNNVWC其查詢時(shí)間加速率都能大于1，本文方法相比kNNVWC能夠提高10%，而且NOWCkNN在建模時(shí)間上明顯小于kNNVWC。在中等維度的數(shù)據(jù)集中，數(shù)據(jù)量較大時(shí)（gasSensors），KDTree查詢效率較低，而k-Means受到數(shù)據(jù)分布的影響每次查詢時(shí)間并不固定，并且大部分的查詢時(shí)間加速率都低于FWC，kNNVWC能把數(shù)據(jù)集分成更小的聚類(lèi)，其查詢時(shí)間加速率優(yōu)于FWC算法。但是NOWCkNN能根據(jù)聚類(lèi)數(shù)量的大小設(shè)定寬度值的范圍，這能得到效果更好的集群，因此其查詢時(shí)間加速率要略優(yōu)于其他幾種方法。因此在高緯度數(shù)據(jù)集中，本文方法的查詢時(shí)間加速率要明顯優(yōu)于其他方法。

5 結(jié)束語(yǔ)

圖5 本文方法與其他方法在不同k值上的查詢時(shí)間加速率

本文針對(duì)kNN算法計(jì)算量大的問(wèn)題，提出一種基于基于對(duì)象數(shù)量的寬度加權(quán)聚類(lèi)算法用于kNN的查詢（NOWCkNN）。該算法基于集群內(nèi)的對(duì)象數(shù)量和調(diào)和系數(shù)計(jì)算寬度權(quán)值，然后迭代的將集群再次劃分，這種方法能使集群的分離效果更加優(yōu)化，在不同維度的數(shù)據(jù)集中分離出效果較好的集群，分類(lèi)的結(jié)果能夠在kNN查詢時(shí)，使用三角不等式最大化地修剪不太可能的對(duì)象。在實(shí)驗(yàn)中，使用8個(gè)UCI公開(kāi)數(shù)據(jù)集驗(yàn)證所提出方法，實(shí)驗(yàn)結(jié)果顯示，與現(xiàn)有方法相比所提出的算法能夠減少聚類(lèi)迭代的次數(shù)，減少建模時(shí)間，增加kNN查詢的修剪率，特別是在高維度、數(shù)據(jù)量較大的數(shù)據(jù)集中效果更好。同時(shí)本文所提方法具有通用性，在不同維度、不同分布的數(shù)據(jù)集中都有較好的實(shí)驗(yàn)結(jié)果。在今后的工作中，將重點(diǎn)關(guān)注聚類(lèi)的改進(jìn)，進(jìn)一步減少預(yù)處理的成本和查詢時(shí)間，會(huì)使用并行計(jì)算以降低預(yù)處理時(shí)間，同時(shí)還會(huì)選取新穎的距離（相似度）計(jì)算公式；同時(shí)將會(huì)分級(jí)控制產(chǎn)生的集群，以便獲取更好聚類(lèi)結(jié)果用于kNN查詢。