面向大規(guī)模節(jié)點劃分的網(wǎng)格密度峰值聚類

江婧婷，鄭朝暉

(蘇州大學 計算機科學與技術(shù)學院，江蘇 蘇州 215006)

1 引 言

當前，傳統(tǒng)采用集群方式部署的分布式存儲系統(tǒng)如HDFS[1]、GFS[2]、Ceph[3]等，存儲著大量的用戶數(shù)據(jù)，這些系統(tǒng)為用戶提供個人數(shù)據(jù)的上傳與下載，對于中心節(jié)點的依賴性很強[4]，中心節(jié)點一旦癱瘓，可能會造成數(shù)據(jù)的不可逆損失.隨著對等式網(wǎng)絡(luò)的發(fā)展，IPFS[5]、Filecoin[6]等系統(tǒng)的出現(xiàn)給分布式存儲帶來了新的思路.不同于傳統(tǒng)的集群式存儲系統(tǒng)，點對點分布式存儲系統(tǒng)是一種去中心化的系統(tǒng)，系統(tǒng)不存在傳統(tǒng)意義上的中心[7]，系統(tǒng)中所有節(jié)點均為存儲節(jié)點，可通過共識算法選取有任期的節(jié)點作為臨時中心[8，9].

在點對點分布式存儲系統(tǒng)中，存儲節(jié)點調(diào)度是系統(tǒng)運行的核心，節(jié)點調(diào)度時需從不同存儲節(jié)點中擇優(yōu)調(diào)度，提前進行節(jié)點劃分有利于節(jié)點調(diào)度的進行，因此，大規(guī)模存儲節(jié)點劃分的效率決定了系統(tǒng)調(diào)度的效率[10].在多維數(shù)據(jù)點任意形狀簇劃分的技術(shù)中，常用的方法為密度峰值聚類算法[11].

密度峰值聚類是一個可以識別出任意形狀簇的聚類算法，它于2014年在《Science》上發(fā)表，該算法參數(shù)少，實現(xiàn)簡單，魯棒性強[12].該算法認為一個聚類中心比它的鄰居節(jié)點具有更高的密度，與其他更高密度節(jié)點之間有更大的距離.針對密度峰值聚類算法復(fù)雜度較高，執(zhí)行時間長等缺點，已經(jīng)有不少學者進行了研究與改進，為了減少算法的復(fù)雜度，Wu等人[13]提出了DGB算法，通過有選擇的計算網(wǎng)格單元之間的距離來代替每個節(jié)點之間的歐式距離，從而提升算法執(zhí)行時間；Xu等人[14]用網(wǎng)格思想代替原有的節(jié)點，提升了聚類時間，但其手動劃分網(wǎng)格不適用于大規(guī)模動態(tài)節(jié)點的劃分；Jiang[15]等人使用邏輯分布提升了算法聚類質(zhì)量，但在大規(guī)模節(jié)點中時間代價高；王[16]等人結(jié)合切比雪夫不等式自動獲取閾值，提升了算法質(zhì)量.

密度峰值聚類算法已經(jīng)被證明在解決非球狀簇分類問題上有顯著優(yōu)勢[16]，故而，將其應(yīng)用于任意形狀的、無明確標簽的存儲節(jié)點劃分中是一個不錯的方法，但其在解決大規(guī)模數(shù)據(jù)聚類時存在時間復(fù)雜度較高、參數(shù)無法自適應(yīng)、聚類精度容易受到手動參數(shù)調(diào)整的影響等缺點.由此本文提出一種改進的網(wǎng)格密度峰值聚類算法，通過自適應(yīng)節(jié)點個數(shù)動態(tài)調(diào)整網(wǎng)格步長、通過判斷網(wǎng)格均衡程度來提升執(zhí)行時間與網(wǎng)格距離準確度，進而提升聚類質(zhì)量、通過極大值平均選取法獲取自適應(yīng)的密度與引力閾值，進而最后得到合適的聚類中心.本文算法在不同數(shù)據(jù)集上與其他算法進行了對比實驗，實驗表明本文算法執(zhí)行時間得到一定程度上的提升，在大規(guī)模數(shù)據(jù)集上劃分結(jié)果的輪廓系數(shù)在0.42左右.

2 傳統(tǒng)的密度峰值聚類

密度峰值聚類算法提出于2014年，該算法為數(shù)據(jù)集中每個數(shù)據(jù)點定義兩個屬性：局部密度與相對距離，局部密度是指數(shù)據(jù)點截斷距離鄰域范圍內(nèi)的數(shù)據(jù)點密度，相對距離是指數(shù)據(jù)點距離高密度節(jié)點的最小距離.被選為簇中心的數(shù)據(jù)節(jié)點需要具有較高的局部密度以及較大的相對距離，算法通過構(gòu)建局部密度與相對距離的決策圖來選取簇中心[17-20].

如圖1，橫坐標代表局部密度，縱坐標代表相對距離，圖1中可見有5個數(shù)據(jù)點具有明顯較高的局部密度與相對距離，這5個數(shù)據(jù)點即為簇類中心.

圖1 密度峰值聚類-決策圖Fig.1 DPCA decision graph

局部密度的計算依賴于數(shù)據(jù)節(jié)點之間的距離，定義數(shù)據(jù)點i的局部密度為ρi，其計算方式見公式(1)：

ρi=∑j(dij-dc)

(1)

其中，dij表示數(shù)據(jù)點之間的歐式距離，dc表示截斷距離，截斷距離是算法中的調(diào)節(jié)參數(shù)，計算方式見公式(2)：

dc=dNd×2%

(2)

Nd表示所有數(shù)據(jù)點之間的距離升序排列后的集合，此外，若原始數(shù)據(jù)集是一組連續(xù)的值，則數(shù)據(jù)點i的局部密度ρi亦可以通過高斯核法來計算，見公式(3)：

(3)

數(shù)據(jù)點i的相對距離δi可表示為數(shù)據(jù)點距離高密度節(jié)點的最小距離，見公式(4)，而對于密度最高的數(shù)據(jù)點，則用最大的點間距離來表示，見公式(5)：

(4)

(5)

密度峰值聚類主要用于非球型簇聚類，且對聚類類別的數(shù)量無限制，有很好的魯棒性，但是該算法在計算數(shù)據(jù)點之間距離矩陣、局部密度以及相對距離時需要很大的時空代價[21-23].隨著數(shù)據(jù)集規(guī)模的上升，其計算代價隨指數(shù)增加，是一種以犧牲速度來計算每個數(shù)據(jù)點屬性從而提升聚類質(zhì)量的算法.因此，在大規(guī)模數(shù)據(jù)集中，算法的效率較低，本文將從速度以及參數(shù)自適應(yīng)兩個方面來進行對比改進.

3 本文改進的網(wǎng)格密度峰值節(jié)點劃分算法

本文算法采用根據(jù)數(shù)據(jù)集規(guī)模自適應(yīng)的網(wǎng)格邊長，對網(wǎng)格中數(shù)據(jù)點進行均衡分布判斷后，計算豪斯多夫距離值，進而提升距離準確度.在閾值獲取部分，本文算法結(jié)合網(wǎng)格局部密度，引入萬有引力計算網(wǎng)格間相對距離，采用極大值平均選取法獲取自適應(yīng)的局部密度與相對引力閾值，從而快速劃分大規(guī)模數(shù)據(jù)節(jié)點.

3.1 自適應(yīng)網(wǎng)格劃分與網(wǎng)格距離計算

3.1.1 網(wǎng)格邊長

本文算法在對數(shù)據(jù)點標準化之后，分別計算x與y兩個維度的數(shù)據(jù)長度與數(shù)值區(qū)間獲得自適應(yīng)的網(wǎng)格邊長，計算方式如下：

將含有n個節(jié)點的數(shù)據(jù)集標準化后按照x與y維度分為：A1={x1，x2，x3…xn}，A2={y1，y2，y3…yn}.

x與y維度的自適應(yīng)網(wǎng)格邊長計算如公式(6)、公式(7)所示：

(6)

(7)

其中，α為調(diào)節(jié)因子，α∈[1.0～2.0]，n表示數(shù)據(jù)集規(guī)模，MAXA1表示最大的x維度值.

3.1.2 網(wǎng)格均衡與距離計算

本文算法依據(jù)網(wǎng)格邊長劃分網(wǎng)格并映射數(shù)據(jù)節(jié)點后，將網(wǎng)格看作是一個個數(shù)據(jù)集合，通過計算網(wǎng)格之間的距離矩陣來代替?zhèn)鹘y(tǒng)密度峰值算法中數(shù)據(jù)點的距離矩陣.

1)本文算法通過豪斯多夫距離公式計算網(wǎng)格間的距離[24，25]，將兩個網(wǎng)格視為兩個封閉集合：

gridA={a1，a2…ai}，gridB={b1，b2…bj}，

其中i，j為當前網(wǎng)格經(jīng)過均衡判斷后，參與距離計算的節(jié)點總數(shù).豪斯多夫距離公式計算一個網(wǎng)格中所有有價值數(shù)據(jù)點到另一個網(wǎng)格中所有有價值數(shù)據(jù)點的最小距離的最大值，通過公式(8)與公式(9)計算分別A網(wǎng)格到B網(wǎng)格與B網(wǎng)格到A網(wǎng)格的最小最大值：

(8)

(9)

其中ai，bj為歐式距離，最后，比較兩個方向的豪斯多夫距離，選擇較大值作為網(wǎng)格間的實際距離.

2)由公式(8)與公式(9)可知，一般的，網(wǎng)格間豪斯多夫距離表示的是網(wǎng)格中所有數(shù)據(jù)點到另一個網(wǎng)格中所有數(shù)據(jù)點的最小最大值.現(xiàn)假設(shè)兩個網(wǎng)格如圖2(e)、圖2(f)所示，使用兩個網(wǎng)格中所有數(shù)據(jù)點計算豪斯多夫距離時，圖2(e)中所有節(jié)點到圖2(f)中所有節(jié)點的最小距離值的目標節(jié)點會集中在1號圈中，圖2(f)中所有節(jié)點到圖2(e)中所有節(jié)點的最小距離值的目標節(jié)點會集中在3號圈中.通過比較得到兩個方向的最小距離集合，其最大值分別為dis′1，dis′2.比較dis′1，dis′2大小，使用圖2(e)、圖2(f)中所有數(shù)據(jù)點計算的豪斯多夫距離結(jié)果為dis′1.

圖2(f)中dc邊界1表示的是以圖2(e)為中心，截斷距離為半徑的圓邊界，目的是要尋找圖2(e)截斷距離范圍內(nèi)的鄰域網(wǎng)格，進而計算截斷距離范圍內(nèi)的數(shù)據(jù)點密度.由圖2(e)可見，當dis′1<截斷距離，圖2(f)會成為圖2(e)的鄰域網(wǎng)格，然而圖2(f)中大部分數(shù)據(jù)點均不在截斷距離范圍內(nèi)，這會造成網(wǎng)格鄰域數(shù)據(jù)點密度的不準確，進而影響公式(10)、公式(12)的結(jié)果.

圖2 網(wǎng)格類型Fig.2 Grid type

由圖2(e)、圖2(f)可見，圖2(e)的左部數(shù)據(jù)點密度遠大于右部，圖2(f)的右部數(shù)據(jù)點密度遠大于左部，本文認為圖2(e)的右部數(shù)據(jù)點與圖2(f)的左部數(shù)據(jù)點是無價值點.在計算豪斯多夫距離時，若摒棄無價值點，則圖2(e)、圖2(f)中雙向最小距離值的目標節(jié)點會集中在2號圈與4號圈中，最終得到豪斯多夫距離值為dis1.同時，去除無價值點后，圖2(e)中心左移，dc邊界2為鄰域邊界.當dis1>截斷距離，圖2(f)不是圖2(e)的鄰域網(wǎng)格；當dis1<截斷距離，圖2(f)中數(shù)據(jù)點大部分均在截斷距離范圍內(nèi)，圖2(f)是圖2(e)的鄰域網(wǎng)格.綜上可見，摒棄無價值點，能提升網(wǎng)格鄰域數(shù)據(jù)點密度準確性，從而提升距離矩陣的正確性，并在一定程度上減少了計算量.

3)本文算法中均衡網(wǎng)格判斷方式如下：

在劃分網(wǎng)格后，空間中大致存在如圖2(a)-圖2(d)所示的4種類型的網(wǎng)格：

由圖2(a)可見，網(wǎng)格內(nèi)的數(shù)據(jù)點是相對均衡分布的，而圖2(b)-圖2(d)則是數(shù)據(jù)點分布不均衡的情況，在計算網(wǎng)格距離前，要先判斷網(wǎng)格是否均衡.將網(wǎng)格如圖2(a)劃分為L1，L2，R1，R2 4個部分，分別計算L1，L2，R1，R2 4個部分中的數(shù)據(jù)點個數(shù)，對4個部分的數(shù)據(jù)點個數(shù)進行降序排序，假設(shè)排序后4個部分密度為s1>s2>s3>s4，使用大密度區(qū)間減小密度區(qū)間：

S=si-sj，i>j，i，j∈[1，4]

如圖2(b)-圖2(d)，在遇到這3種情況時，經(jīng)過網(wǎng)格均衡判斷，圖2(b)中只有L2中的節(jié)點參與距離計算，圖2(c)中L1，L2中的節(jié)點參與距離計算，圖2(d)中L1，L2，R2中的節(jié)點參與距離計算.通過判斷網(wǎng)格均衡，使得本文算法在計算距離時避免使用無價值的數(shù)據(jù)節(jié)點.

3.1.3 基于網(wǎng)格均衡的網(wǎng)格距離算法

使用方法1(上述基于網(wǎng)格均衡的網(wǎng)格距離計算方法)以及方法2(不判斷網(wǎng)格均衡的網(wǎng)格距離計算方式)，對4K與8K兩種規(guī)模的數(shù)據(jù)集進行聚類，得到結(jié)果如表1所示.表格中，不均衡率表示不均衡網(wǎng)格占非空網(wǎng)格的比重，max_dis/ min_dis偏移量表示采用方法2 得到的最大/小網(wǎng)格間距離較方法1得到的最大/小距離的偏移量，中心偏移量表示方法2得到的簇類中心數(shù)量較方法1的偏移量.由表1可知，不判斷網(wǎng)格均衡會使得網(wǎng)格距離矩陣出現(xiàn)不同大小的偏差，從而導(dǎo)致最后聚類結(jié)果不理想.

表1 判斷&不判斷網(wǎng)格均衡的相關(guān)結(jié)果的偏移量表格Table 1 Offset table of the grid equalization related results

本文基于網(wǎng)格均衡的距離算法步驟如下：

輸入：網(wǎng)格信息、數(shù)據(jù)節(jié)點信息

輸出：最小與最大網(wǎng)格間距離、網(wǎng)格距離矩陣

Step 1.選取非空網(wǎng)格作為初始網(wǎng)格.

Step 2.計算并判斷網(wǎng)格均衡，將有價值的數(shù)據(jù)點標記為′y′.

Step 3.遍歷所有非空網(wǎng)格，判斷非空網(wǎng)格的標記值，網(wǎng)格為不均衡網(wǎng)格，轉(zhuǎn)Step 4;網(wǎng)格為均衡網(wǎng)格，轉(zhuǎn)Step 5，根據(jù)公式(8)、公式(9)以及獲取的網(wǎng)格中節(jié)點信息計算網(wǎng)格間距離.

Step 4.獲取數(shù)據(jù)點標記為′y′的信息.

Step 5.獲取網(wǎng)格中所有數(shù)據(jù)點信息.

Step 6.計算網(wǎng)格間距離最小與最大值.

3.2 密度閾值與引力閾值自動獲取

本文算法中，局部密度與相對引力閾值的選取直接決定了聚類中心的選擇以及聚類質(zhì)量的好壞.本文算法基于萬有引力、網(wǎng)格密度，通過計算網(wǎng)格相對引力與局部密度的乘積極大值來自動確定閾值.

3.2.1 局部密度

網(wǎng)格局部密度由當前網(wǎng)格內(nèi)數(shù)據(jù)點個數(shù)與截斷距離范圍內(nèi)的鄰域網(wǎng)格節(jié)點數(shù)組成，計算方式見公式(10)：

(10)

其中，i表示當前網(wǎng)格號，gridNodeNumi表示當前網(wǎng)格中包含的節(jié)點個數(shù)，distance[i，j]表示兩個網(wǎng)格之間的豪斯多夫距離，dc表示截斷距離，本文算法的截斷距離計算方式采用公式(2)，截斷百分比為1%.

3.2.2 相對引力

本文中相對引力由網(wǎng)格相對距離與局部密度組成，網(wǎng)格相對距離表示當前網(wǎng)格距離其較高局部密度網(wǎng)格之間的距離的最小值，計算方式采用公式(4)、公式(5)，其中dij表示網(wǎng)格之間的豪斯多夫距離值.根據(jù)牛頓萬有引力定律，任何物體之間都有吸引力，其大小與物體的質(zhì)量成正比，與物體之間的距離的平方成反比，萬有引力公式：

(11)

現(xiàn)將本文算法中的兩個網(wǎng)格分別看作是兩個不同的物體，網(wǎng)格之間距離越遠則相互吸引力越小，越近則吸引力越大.現(xiàn)將網(wǎng)格間引力比作萬有引力，物體的質(zhì)量就是網(wǎng)格局部密度，物體之間的距離就是網(wǎng)格相對距離，故而兩個網(wǎng)格之間的吸引力與網(wǎng)格局部密度成正比，與網(wǎng)格相對距離的平方成反比，將本文參數(shù)代入萬有引力公式，得到網(wǎng)格相對引力的計算方式，見公式(12)：

(12)

由公式(12)可知，網(wǎng)格的相對引力值越小，說明網(wǎng)格局部密度越小或者當前網(wǎng)格距離較高密度網(wǎng)格的最小距離越大，即該網(wǎng)格可能是離群網(wǎng)格或簇中心網(wǎng)格.

3.2.3 閾值自動選取

根據(jù)密度峰值聚類算法的思想，應(yīng)當選取局部密度較高的且相對引力更小的網(wǎng)格作為聚類中心.故對相對引力取倒數(shù)與網(wǎng)格局部密度值由高到低畫出決策圖.

圖3(a)中，橫坐標表示的是網(wǎng)格局部密度值由高到低排列對應(yīng)的值，縱坐標表示橫坐標對應(yīng)網(wǎng)格的相對引力倒數(shù)值.圖3(a)中可見橫坐標(0，20)區(qū)間和(30，50)區(qū)間均有相對引力倒數(shù)值較高的網(wǎng)格，由相對引力公式(12)可知，(0，20)區(qū)間內(nèi)存在大量引力值倒數(shù)較高網(wǎng)格的原因是網(wǎng)格局部密度小，即這些網(wǎng)格是邊緣或離群網(wǎng)格，不會成為簇中心，因此我們選取閾值應(yīng)當在(30，50)的區(qū)間內(nèi).

圖3 NPA-決策與評價函數(shù)折線圖Fig.3 NPA-decisionandevaluatefunctionline graph

本算法使用網(wǎng)格局部密度與相對引力的倒數(shù)作為決策依據(jù)，將兩者相乘：

evaluateid=localDensityid×(1/relativeGravityid)

(13)

evaluateid代表某一網(wǎng)格對應(yīng)的決策評估值，將決策評估值通過折線圖直觀表示.如圖3(b)中橫坐標為按照降序排列的網(wǎng)格局部密度序列號，可見，決策評估值與相對引力成負相關(guān)，決策評估值的波動代表了相對引力的波動，決策評估值的升高表示相對引力值的下降，即該網(wǎng)格滿足局部密度大的同時，其與較高密度網(wǎng)格之間的距離較大，相對引力較小.

本文算法選擇決策評估值中大于決策評估值平均值的極大值作為候選中心的決策值，選取方式如下：

density_threshold=localDensity.max(idi)

(14)

distance_threshold=min(relativeGravity.idj)

(15)

公式(14)、公式(15)分別表示局部密度閾值與相對引力閾值的計算方式，其中，localDensity局部密度由公式(10)得到，relativeGravity相對引力由公式(12)得到，idj均屬于滿足公式(16)-公式(18)的網(wǎng)格編號，公式(16)-公式(18)中maximum代表公式(13)的evaluateid的所有極大值集合：

maximum={e0，e1，e3…ek}，

其中k表示決策值中滿足要求的極大值的網(wǎng)格個數(shù)，m=maximunNeed的長度，num為網(wǎng)格總數(shù).

(16)

(17)

evaluate.idi∈maximum，idi<2×?num/3」

(18)

3.2.4 閾值自動獲取算法

上述閾值自動獲取算法步驟如下：

輸入：網(wǎng)格信息、截斷距離

輸出：局部密度矩陣、相對引力矩陣、局部密度閾值、相對引力閾值.

Step 1.計算當前網(wǎng)格的本地密度，依據(jù)公式(10)計算網(wǎng)格局部密度.

Step 2.依據(jù)公式(4)、公式(5)計算網(wǎng)格相對距離.

Step 3.依據(jù)公式(12)計算網(wǎng)格相對引力以及相對引力的倒數(shù).

Step 4.依據(jù)公式(13)計算決策評估值.

Step 5.計算公式(16)-公式(18)中的決策評估值的極大值等參數(shù).

Step 6.在極大值中遍歷，尋找滿足公式(16)-公式(18)的網(wǎng)格id號.

Step 7.依據(jù)公式(14)、公式(15)計算局部密度閾值、相對引力閾值.

對3個不同規(guī)模數(shù)據(jù)集，分別進行自動獲取閾值與人工選取閾值的結(jié)果對比.如表2所示，其中圓括號內(nèi)的數(shù)值分別是局部密度閾值與相對引力倒數(shù)閾值，人工選取閾值是手動從如圖3(a)這樣的決策圖中選取.由表格中數(shù)據(jù)可見，通過本文自動閾值獲取得到的兩個閾值與人工閾值選取偏差在0.05以下，兩者得到的簇中心的坐標是一致的，說明聚類結(jié)果一致，自動獲取閾值可以隨數(shù)據(jù)集規(guī)模而自適應(yīng).

表2 自動&人工閾值獲取結(jié)果對比Table 2 Automatic & manual threshold results comparison

3.3 本文算法流程

改進的密度峰值聚類算法聚類步驟如下：

Step 1.首先對原始節(jié)點進行標準化處理，將原始數(shù)據(jù)的坐標歸一化到(0，1)區(qū)間中；

Step 2.計算原始節(jié)點的地址范圍，根據(jù)節(jié)點分布范圍劃分網(wǎng)格；

Step 3.將原始節(jié)點映射到所有網(wǎng)格中；

Step 4.判斷所有非空網(wǎng)格的均衡程度；

Step 5.計算網(wǎng)格距離矩陣與本地網(wǎng)格密度；

Step 6.生成截斷距離，計算網(wǎng)格局部密度與更高密度網(wǎng)格之間相對距離；

Step 7.根據(jù)萬有引力公式計算相對引力，根據(jù)極大值平均選取法生成密度閾值與引力閾值；

Step 8.根據(jù)閾值選擇合適的簇類中心；

Step 9.合并網(wǎng)格，得到簇類；

Step 10.評價聚類質(zhì)量.

4 實驗分析

4.1 實驗環(huán)境與數(shù)據(jù)集介紹

本文實驗算法運行環(huán)境：CPU為I7，4核，內(nèi)存為8G，操作系統(tǒng)為windows 7，實驗軟件為PyCharm，實驗所用程序語言為python3；數(shù)據(jù)節(jié)點運行環(huán)境：機器數(shù)量為100個，CPU為Celeron J1900，4核，內(nèi)存為2G，操作系統(tǒng)為windows 7.為了驗證本文算法的有效性，本文使用3類數(shù)據(jù)集，4種算法進行對比試驗.4種算法分別是：基于引力的密度峰值聚類(GDPC)、密度峰值聚類算法(DPCA)、本文中改進網(wǎng)格密度峰值的節(jié)點劃分算法(NPA)以及未判斷網(wǎng)格均衡的本文算法(NPA-WG)；3種數(shù)據(jù)集分別是：隨機生成的以不同經(jīng)緯度為基準的數(shù)據(jù)集、3個人工數(shù)據(jù)集、Vivaldi[26]生成的坐標數(shù)據(jù)集.通過這3種數(shù)據(jù)集分別從聚類時間、聚類準確性，聚類質(zhì)量3個方面對本文算法在大規(guī)模節(jié)點劃分中的性能進行了分析與評估.

數(shù)據(jù)集信息見表3，其中，實際的坐標數(shù)據(jù)集由Vivaldi根據(jù)數(shù)據(jù)節(jié)點間產(chǎn)生的實際時延生成，節(jié)點時延與傳輸距離、傳輸介質(zhì)、數(shù)據(jù)包大小相關(guān).本實驗中，數(shù)據(jù)包大小一致，將國內(nèi)1724個網(wǎng)站的服務(wù)器地址作為節(jié)點地址與本地搭建的數(shù)據(jù)點進行排列組合，結(jié)合有線傳輸、無線傳輸、6類網(wǎng)線、5類網(wǎng)線，獲取節(jié)點的每分鐘平均時延值，將獲取到的時延值作為節(jié)點坐標更新依據(jù)，生成Vivaldi坐標數(shù)據(jù)集.

表3 3種數(shù)據(jù)集詳細信息Table 3 Details of three data sets

4.2 評價函數(shù)介紹

本文中聚類質(zhì)量的評價函數(shù)采用輪廓系數(shù)，輪廓系數(shù)是聚類效果好壞的一種評價方式，它包含內(nèi)聚度與分離度兩種因素.內(nèi)聚度表示簇內(nèi)數(shù)據(jù)點的緊湊程度，分離度表示簇與簇之間的分散程度，好的聚類結(jié)果應(yīng)該具備較高的內(nèi)聚度與分離度.

輪廓系數(shù)計算方式見公式(19)，其中a(i)表示簇內(nèi)數(shù)據(jù)點i到所有該簇中其它點的距離的平均值，b(i)表示簇內(nèi)數(shù)據(jù)點i到與距離該簇最近一簇內(nèi)所有點的平均距離的最小值[27].

(19)

輪廓系數(shù)的值一般應(yīng)介于-1-1之間，輪廓系數(shù)為-1時表示聚類結(jié)果的內(nèi)聚度低，分離度高，即簇內(nèi)數(shù)據(jù)點分散，聚類結(jié)果不好；輪廓系數(shù)為1時表示簇內(nèi)數(shù)據(jù)點之間緊湊，為0時表示存在重疊的簇類.因此，輪廓系數(shù)越大，簇內(nèi)數(shù)據(jù)點之間越緊湊，簇間的距離越大，可用于評價本文算法的聚類質(zhì)量.

4.3 實驗參數(shù)介紹

本文算法實驗所用參數(shù)以及參數(shù)釋義如表4所示.

表4 實驗參數(shù)設(shè)置與釋義Table 4 Experimental parameter setting and interpretation

4.4 實驗結(jié)果對比分析

4.4.1 算法執(zhí)行時間分析

本實驗使用表3中的隨機經(jīng)緯度數(shù)據(jù)集與Vivaldi坐標數(shù)據(jù)集，使用DPCA、GDPC、NPA、NPA-WG 4種算法分別對規(guī)模為2K-30K的數(shù)據(jù)集進行聚類.表5記錄了DPCA、GDPC、NPA、NPA-WG對5種不同規(guī)模的Vivaldi坐標數(shù)據(jù)集進行聚類的執(zhí)行時間.表5中，DPCA、GDPC兩種算法對規(guī)模為10K的數(shù)據(jù)集進行聚類時提示了內(nèi)存溢出，無法執(zhí)行算法，而NPA、NPA-WG則不受影響.

表5 不同數(shù)據(jù)集規(guī)模上的運行時間比較
Table 5 Run time comparison with different dataset sizes

數(shù)據(jù)集DPCAGDPCNPANPA-WG200036s20s18s25s400081s68s64s98s6000200s205s165s198s80001195s1123s268s364s10000內(nèi)存溢出內(nèi)存溢出335s575s

圖4(a)中通過折線圖直觀展示了DPCA、GDPC、NPA、NPA-WG 4種算法對2K-8K的Vivaldi坐標數(shù)據(jù)集聚類的執(zhí)行速度對比，其中橫坐標表示數(shù)據(jù)集規(guī)模，縱坐標表示執(zhí)行時間.可見，本文算法與DPCA、GDPC相比較，本文算法的執(zhí)行時間最短，其次是NPA-WG與GDPC，執(zhí)行時間最長的是DPCA，隨著數(shù)據(jù)集規(guī)模增長，本文算法的執(zhí)行時間增長速度最慢.因此，在算法執(zhí)行時間上，本文算法NPA在數(shù)據(jù)規(guī)模4K-8K中，執(zhí)行速度較DPCA、GDPC而言，提升區(qū)間分別為17.5%-77.57%、5.8%-76.13%，隨著數(shù)據(jù)集規(guī)模的增加，本文算法較DPCA、GDPC，速度提升比率越來越大.

圖4(b)中比較的是NPA、NPA-WG在2K-30K隨機數(shù)據(jù)集上的執(zhí)行時間，橫縱坐標分別表示數(shù)據(jù)規(guī)模與執(zhí)行時間.隨機數(shù)據(jù)集更分散，算法執(zhí)行的計算量更大，更能比較NPA、NPA-WG的執(zhí)行速度.由圖4(b)折線趨勢可見，進行網(wǎng)格均衡判斷后計算網(wǎng)格距離，其執(zhí)行時間始終低于未判斷網(wǎng)格均衡的NPA-WG，增長趨勢也低于NPA-WG.在2K-30K數(shù)據(jù)集規(guī)模上，NPA執(zhí)行速度較NPA-WG提升了11%- 49.24%.

圖4 算法執(zhí)行時間對比圖Fig.4 Algorithm execution time comparison graph

以上數(shù)據(jù)表明網(wǎng)格均衡判斷減少了無價值數(shù)據(jù)點加入計算，減少了網(wǎng)格距離計算量，本文算法NPA在執(zhí)行速度上能適用于大規(guī)模數(shù)據(jù)集.

4.4.2 算法準確性分析

本輪實驗中，使用表3中的人工數(shù)據(jù)集1-3分別用DPCA、GDPC、NPA 3種算法進行對比實驗.人工數(shù)據(jù)1的原始數(shù)據(jù)點分布如圖5(a)所示，顯然，該數(shù)據(jù)集有5個簇類，圖5(c)和圖5(e)分別表示NPA在α=0.5與α=1.8下的局部密度與相對引力倒數(shù)的決策圖.由公式(6)可知，調(diào)節(jié)值α的值越小，則網(wǎng)格的邊長越大，劃分出的網(wǎng)格個數(shù)越少，這就可能造成有不同簇類的數(shù)據(jù)點被劃分到同一個網(wǎng)格中，如此便直接導(dǎo)致網(wǎng)格間距離值普遍偏小，從而導(dǎo)致網(wǎng)格局部密度過于平均，相對引力的倒數(shù)偏小.如圖5(c)，決策圖中未見明顯的離群值，而圖5(e)中則可見明顯的5個離群值，離群值代表了該網(wǎng)格的局部密度在該網(wǎng)格鄰域內(nèi)相對較高，該網(wǎng)格的相對引力較小，即該網(wǎng)格可以是簇中心候選者.

在進行閾值選取時，使用公式(13)的值分別畫出圖5(d)與圖5(f).由圖5(d)可見，α為0.5的條件下，評價值的波動在全局都呈現(xiàn)無序混亂的狀態(tài)，全局方差大；而圖5(f)中可見，α為1.8的條件下，評價值在首尾區(qū)間呈現(xiàn)較大波動，而在中間段則較為平緩，這也和圖5(e)的決策圖相對應(yīng).尾部區(qū)間波動大是因為該部分的網(wǎng)格往往局部密度小，且處于簇類的邊緣地帶，而首部區(qū)間的波動則是由圖5(e)中的離群值導(dǎo)致的，該部分的網(wǎng)格局部密度大，處于簇類中心地帶，相對引力小，是中心候選區(qū)域.

圖5 人工數(shù)據(jù)集1-3 聚類過程與結(jié)果Fig.5 Artificial dataset1-3 clustering process and results

根據(jù)公式(14)、公式(15)得到本實驗的局部密度閾值與相對引力的倒數(shù)閾值分別為102.57，0.11×(1e-6)，根據(jù)得到的閾值，獲取滿足要求的網(wǎng)格作為中心.圖5(b)中所示為α為1.8的條件下的NPA聚類結(jié)果，可見有5種不同標識的簇類被劃分出來，NPA能正確的劃分出不同簇類.

表6中記錄了DPCA、GDPC、NPA1(α為1.8)、NPA2(α為0.5)在人工數(shù)據(jù)集1上執(zhí)行后的簇內(nèi)數(shù)據(jù)點個數(shù).記錄的數(shù)據(jù)表明α為1.8的NPA算法得到聚類結(jié)果與DPCA、GDPC得到的結(jié)果差距在1%-7%，而α為0.5的NPA的僅得到3個中心，聚類結(jié)果與DPCA、GDPC相差較遠，聚類結(jié)果不理想.對人工數(shù)據(jù)集2-3分別運行NPA、DPCA、GDPC算法，其結(jié)果誤差均穩(wěn)定在8%以下，其中NPA得到的結(jié)果如圖5(g)與圖5(h)所示，NPA算法能很好的識別出不同形狀的簇類.

表6 人工數(shù)據(jù)集1 聚類結(jié)果對比Table 6 Artificial dataset1 comparison of clustering results

通過本輪實驗驗證，α為1.8時NPA算法呈現(xiàn)出較好的聚類結(jié)果，在人工數(shù)據(jù)集1-3上，其聚類結(jié)果均與DPCA、GDPC相近，誤差在1%-8%之間.

4.4.3 算法結(jié)果質(zhì)量分析

本輪實驗中，使用表3中的Vivaldi坐標數(shù)據(jù)集1與Vivaldi坐標數(shù)據(jù)集2，對NPA、NPA-WG進行實驗對比.圖6中所示的是Vivaldi坐標數(shù)據(jù)集1與2分別用NPA、NPA-WG執(zhí)行過程中產(chǎn)生的評價值波動圖.圖6(a)、圖6(b)分別為對Vivaldi坐標數(shù)據(jù)集1使用NPA-WG與NPA運行的評價值波動，對比可見，NPA-WG的評價值在中間區(qū)域的波動較大，該區(qū)域的網(wǎng)格局部密度值往往位于平均值附近，一般不屬于簇中心或簇邊緣，而處于簇類的中間地帶，屬于簇內(nèi)普通成員.

圖6 Vivaldi坐標數(shù)據(jù)集1-2 NPA& NPA-WG評價值折線圖Fig.6 Vivaldi coordinate dataset1-2 evaluate value line graph

由公式(4)、公式(12)可知，NPA-WG在中間區(qū)域出現(xiàn)大波動是由于網(wǎng)格間距離的不準確導(dǎo)致的，不判斷網(wǎng)格均衡，使得圖2(b)-圖2(d)中的所示的所有數(shù)據(jù)點都加入距離計算，則網(wǎng)格距離受到個別離群點影響而不準確.這就使得截斷距離出現(xiàn)偏差，從而導(dǎo)致局部密度與相對距離出現(xiàn)偏差，進而影響整個聚類的結(jié)果.經(jīng)過計算，NPA-WG對Vivaldi坐標數(shù)據(jù)集1計算，最后得到的聚類結(jié)果的輪廓系數(shù)為0.2962，而NPA得到聚類結(jié)果的輪廓系數(shù)為0.4397.

同樣的，圖6(c)、圖6(d)為對Vivaldi坐標數(shù)據(jù)集2使用NPA-WG與NPA運行的評價值波動.圖6(c)、圖6(d)對比可見，NPA-WG的評價值在250附近呈現(xiàn)出明顯波動，而NPA在中間區(qū)域則無明顯區(qū)域性波動.經(jīng)過計算，NPA-WG對Vivaldi坐標數(shù)據(jù)集2計算，最后得到的聚類結(jié)果的輪廓系數(shù)為0.2427，NPA對最后得到聚類結(jié)果的輪廓系數(shù)為0.4246.

圖7中記錄了對2K-10K的Vivaldi坐標數(shù)據(jù)集執(zhí)行NPA-WG與NPA的輪廓系數(shù)值，其中橫坐標表示Vivaldi坐標數(shù)據(jù)集規(guī)模，縱坐標表示輪廓系數(shù)值.從圖7中可見，隨著數(shù)據(jù)規(guī)模的增大，NPA-WG聚類結(jié)果的輪廓系數(shù)往往低于NPA的輪廓系數(shù)，且在個別離群點多的數(shù)據(jù)集中，NPA-WG的輪廓系數(shù)會遠低于NPA，而在離群點少的數(shù)據(jù)集中，兩者則較為相近.

圖7 輪廓系數(shù)對比圖Fig.7 Silhouette coefficient comparison graph

此外，由圖7中可見，隨著坐標數(shù)據(jù)集規(guī)模的上升，NPA的輪廓系數(shù)穩(wěn)定在0.42左右，由公式(19)知，輪廓系數(shù)越接近1則說明聚類質(zhì)量越好，因此，NPA在本輪實驗結(jié)果中呈現(xiàn)較好的聚類質(zhì)量.

4 總 結(jié)

針對傳統(tǒng)的密度峰值聚類算法在大規(guī)模數(shù)據(jù)點劃分中存在執(zhí)行時間長、算法復(fù)雜度高、簇中心選取無法自適應(yīng)、簇結(jié)果易受手動參數(shù)影響等不足.本文提出一種改進網(wǎng)格密度峰值聚類算法，該算法通過自適應(yīng)網(wǎng)格邊長劃分網(wǎng)格，引入網(wǎng)格均衡，結(jié)合萬有引力，通過計算網(wǎng)格之間的相對引力得到網(wǎng)格評價值，進而通過極大值平均選取法獲取局部密度與相對引力閾值，最后得到簇類中心.在不同數(shù)據(jù)集上與其他算法的對比實驗表明，本文算法在執(zhí)行速度上較傳統(tǒng)算法最多約提升了77%，聚類結(jié)果的誤差在1%-8%之間，在大規(guī)模數(shù)據(jù)集上劃分結(jié)果的輪廓系數(shù)維持在0.42左右.上述證明了本文的改進算法能自適應(yīng)于大規(guī)模數(shù)據(jù)集劃分，對點對點分布式存儲系統(tǒng)調(diào)度的執(zhí)行效率有積極意義.