原 野 田 園 黃祖源 李 輝 黃浩淼

1(云南電網(wǎng)有限責任公司信息中心 云南 昆明 650500)

2(昆明能訊科技有限責任公司 云南 昆明 650021)

0 引 言

數(shù)據(jù)智能化處理是一個長期以來研究的熱點,同時在信息物理融合系統(tǒng)(Cyber Physical Systems)的感知層中也是研究的熱點。數(shù)據(jù)集的聚類處理正在快速地發(fā)展,當前數(shù)據(jù)聚類算法分為基于網(wǎng)格聚類[1]、基于密度聚類[2]、基于層次聚類[3]和基于集成式聚類[4]等,基于網(wǎng)格聚類的算法將空間網(wǎng)格化后使連續(xù)空間離散化,從而大大地減少計算量。Nketsa等[5]提出一種基于統(tǒng)計信息的網(wǎng)格聚類算法STING,將數(shù)據(jù)空間網(wǎng)格劃分為具有層次機構的矩形單元,分別計算置信度區(qū)間反映為聚類關聯(lián)度,從而提高聚類效率,但底層單元的粒度粗降低了聚類的質(zhì)量和準確性。Mihael等[6]提出一種基于最佳網(wǎng)格的高維數(shù)據(jù)集聚類算法OptiGridS,根據(jù)密度函數(shù)得到網(wǎng)格劃分的不均勻切割平面運用數(shù)學模型使聚類效率較高,但對于高維數(shù)據(jù)集聚類質(zhì)量低。Sheikholeslami等[7]提出一種基于小波變換模型的聚類算法Wave Cluster,將多維網(wǎng)格空間劃分數(shù)據(jù),使用小波變換轉換特征空間后,得到數(shù)據(jù)密度分布信息,從而快速得到類簇中心點,但聚類準確性低。針對高維數(shù)據(jù)集處理中以上基于網(wǎng)格聚類算法的準確性較低問題,基于密度的聚類算法容易識別不同密度和形狀的類簇中心,使聚類精確率得到提高,Peng等[8]提出一種基于密度和噪聲處理的聚類算法DBSCAN,根據(jù)高密度的區(qū)域來劃分類簇,在類簇的E領域尋找密度可達的對象實現(xiàn)聚類,但算法的時間復雜度較高。Xiao等[9]提出一種基于密度分布函數(shù)的聚類算法DENCLUE,將數(shù)據(jù)空間中數(shù)據(jù)集根據(jù)數(shù)學函數(shù)模擬為所有數(shù)據(jù)點的高斯影響函數(shù)值,由全局密度確定類簇核心點,在具有噪聲的高維數(shù)據(jù)集中聚類效果較好,但算法的時間效率較高。Rodri等[10]提出一種基于密度峰值的快速聚類算法DPC,通過計算區(qū)域內(nèi)樣本的局部密度,利用決策圖快速找到密度峰值對應的類簇中心,從而確定類簇數(shù)目,然后對剩余的樣本點根據(jù)漢寧距離進行分配。為了平衡聚類的時效和準確率,研究者開始提出了基于網(wǎng)格和密度結合的聚類算法,San等[11]提出了一種基于高維數(shù)據(jù)子空間內(nèi)聚類算法CLIQUE,對數(shù)據(jù)集網(wǎng)格劃分后找到稀疏和密集單元,在高維的子空間實現(xiàn)聚類。Chen等[12]提出一種基于數(shù)據(jù)信息的子空間聚類算法SCI,首先網(wǎng)格劃分高維數(shù)據(jù)空間,得到稠密單元、稀疏單元、離群單元,通過熵定理優(yōu)化聚類效果,能夠對離群點進行檢測和簇的邊界點的處理,但參數(shù)選擇特別敏感,空間復雜度大。Goil等[13]提出一種基于子空間擴展的高維數(shù)據(jù)集聚類算法MAFIA,根據(jù)數(shù)據(jù)分布來確定網(wǎng)格單元,通過高密度的單元完成聚類,適用于高維數(shù)據(jù)集,但時間復雜度較高。Levent等[14]提出一種共享最近鄰聚類算法SNN,根據(jù)數(shù)據(jù)對象之間k-距離建立矩陣關系圖,然后通過相似度準則劃分類簇中心,完成高維數(shù)據(jù)集中不同密度對象的聚類,但對于含噪聲點的數(shù)據(jù)集聚類精度低。

在數(shù)據(jù)聚類處理過程中類簇的邊緣網(wǎng)格中包含著噪聲點,傳統(tǒng)的聚類算法不能有效識別和處理噪聲點,影響數(shù)據(jù)集進行正確的聚類。本文結合參考文獻[15]的基本思想,首先自頂向下均勻切割數(shù)據(jù)空間得到空間單元,然后計算高維子空間內(nèi)每個空間單元的密度,根據(jù)密度值劃分得到數(shù)據(jù)空間內(nèi)密度不同的網(wǎng)格,利用網(wǎng)格相對密度差來檢測類簇邊界網(wǎng)格中包含的噪聲數(shù)據(jù)點,考慮到邊界網(wǎng)格內(nèi)噪聲數(shù)據(jù)點近鄰環(huán)境的影響,避免將樣本錯分,然后改進SNN算法利用每個樣本的局部密度分布信息進行類簇分配,則高密度的數(shù)據(jù)點按照數(shù)據(jù)分布特征進行分配,而低密度的噪聲點使用樣本近鄰信息進行分配。本文算法通過局部密度對噪聲點進行分配,提高算法對非均勻密度的高維數(shù)據(jù)集聚類的準確率。

1 共享最近鄰SNN聚類算法

SNN算法根據(jù)高維數(shù)據(jù)集D中數(shù)據(jù)對象之間k-距離鄰居矩陣稀疏化建立起最近鄰居矩陣圖,若p和q兩個數(shù)據(jù)對象彼此互為最近鄰居,可以由k-最近距離建立起對象連接,連接的相似度權值即為數(shù)據(jù)對象p和q共享鄰居個數(shù),定義為:

similarity(p,q)=size(NN(p)∩NN(q))

(1)

式中:NN(p)和NN(q)分別代表數(shù)據(jù)對象p和q的最近鄰居列表。計算對象p與第k個最近鄰居的距離distance(k,p),得到:

Nk(p)={q∈D{p}|d(p,q)≤k-distance(p)}

(2)

式中:Nk(p)表示對象p的k-距離領域內(nèi)所有距離小于k-distance(p)的對象數(shù)據(jù)集合;d(p,q)表示數(shù)據(jù)對象p和q之間最短距離。根據(jù)相似度準則估計出集合中數(shù)據(jù)點的SNN區(qū)域密度,SNN區(qū)域密度定義為:

N(p)={q∈D{p}|similarity(p,q)≤SIM}

(3)

式中:N(p)表示為數(shù)據(jù)對象p相似度權重小于密度閾值SIM的對象個數(shù),設定p的領域中最小的對象個數(shù)閾值為MinPts,將大于閾值的數(shù)據(jù)對象作為類簇中心點,完成聚類。

2 基于網(wǎng)絡框架下改進的多密度SNN聚類算法

2.1 網(wǎng)格簇邊界噪聲點檢測

首先自頂向下網(wǎng)格劃分數(shù)據(jù)空間,假設d維數(shù)據(jù)集D中,數(shù)據(jù)個數(shù)為N,第i維上的值在區(qū)間Rgi=[li,hi]中,則S=Rg1×Rg2×…×Rgd為d維數(shù)據(jù)空間,然后將數(shù)據(jù)空間的每一維度均分為∏numi個網(wǎng)格單元,其中numi為數(shù)據(jù)空間在第i維上單元數(shù)目,網(wǎng)格單元均分的邊長為:

(4)

numi=[(hi-li)/length]

(5)

式中:a為網(wǎng)格控制因子。然后將每個維度網(wǎng)格單元對象X=(x1,x2,…,xd)插入網(wǎng)格索引表提升聚類效率,索引表每一維對應的下標為:

indi=[(xi-li)/length]

(6)

元組中插入的數(shù)據(jù)個數(shù)即網(wǎng)格密度,下一步計算中心密度差合并網(wǎng)格,將密度最大的網(wǎng)格作為初始網(wǎng)格g0,并計算邊界網(wǎng)格gi與初始網(wǎng)格g0的中心密度差,定義為:

(7)

(8)

式中:den(g0)為網(wǎng)格密度;λ為較小密度網(wǎng)格占比;G為數(shù)據(jù)集D劃分的網(wǎng)格數(shù)目。若agdd(g0,gi)<ε,則將兩個網(wǎng)格合并形成區(qū)域D1,否則邊界網(wǎng)格gi為包含著噪聲數(shù)據(jù)的密度稀疏網(wǎng)格,然后根據(jù)噪聲點數(shù)據(jù)分布不均勻特征得到邊界網(wǎng)格的質(zhì)心偏離度:

(9)

式中:C0和C1分別為邊界網(wǎng)絡質(zhì)心點和中心點。當dcm大于閾值則邊界網(wǎng)格中噪聲數(shù)據(jù)為不均勻特征,計算邊界網(wǎng)格中心C1與最近鄰簇網(wǎng)格中心C的距離distC,及邊界網(wǎng)格內(nèi)數(shù)據(jù)點Ni到最近鄰簇網(wǎng)格中心的距離disti(i=1,2,…,n),若disti≤distC則數(shù)據(jù)點Ni作為噪聲點標記。邊界網(wǎng)格噪聲點檢測如圖1所示。

圖1 邊界網(wǎng)格噪聲點檢測示意圖

圖2 GSSN算法邊界網(wǎng)格內(nèi)噪聲點分配圖

2.2 改進的多密度SNN聚類算法

SNN聚類算法對不同密度的高維數(shù)據(jù)集進行聚類時,能夠自動識別出簇的數(shù)目,但對于含有噪聲點的數(shù)據(jù)集聚類精度都不高,且數(shù)據(jù)維度的可伸縮性較差,主要是因為SNN算法基于數(shù)據(jù)的全局密度分布將邊界網(wǎng)格樣本分配給距離最近鄰類簇。本文改進的SNN算法考慮每個樣本數(shù)據(jù)的局部密度峰值,找到邊界網(wǎng)格中高密度的非噪聲點分布特征進行類簇分配,對于低密度的噪聲點采用KNN最近鄰域信息進行類簇分配。

首先網(wǎng)格劃分得到的邊界網(wǎng)格后,計算樣本數(shù)據(jù)i的局部密度峰值ρj定義為:

谷城縣把解決貧困戶眼前生計問題和建設長期收益項目結合起來，因戶制宜、精準施策，資金、項目向重點貧困村傾斜，向最困難的群體傾斜，70%的資金用于37個重點貧困村，將脫貧成效作為項目安排、資金使用的重要參考因素，促使入戶政策更加完善，切實改善了貧困人口的生產(chǎn)生活條件。

(10)

式中:KNN(i)為樣本i的K個近鄰樣本構成的集合,樣本i、j之間的歐氏距離為dij。根據(jù)密度峰值將非噪聲點樣本分配到相應的類簇,從而使得分配到某一簇的樣本點跟類簇之間具有緊密聯(lián)系。對策略1中未分配的噪聲點樣本,采用分配策略2利用K近鄰信息的思想進行樣本類簇分配,樣本分配策略如下。

(1) 分配策略1:主要針對非噪聲點的分配,具體實現(xiàn)算法如下:

Step1將網(wǎng)格類簇中心合集CI中選擇一個未被訪問的核心點ci,其作為SNN算法的類簇中心,并標記ci已被訪問。

Step2計算ci點的K近鄰KNN(ci)集合的樣本后,初始化隊列Vq,再將樣本數(shù)據(jù)合并到ci所在的類簇中,若KNN(ci)中含有的非噪聲點樣本滿足dq,r≤mean{dr,j|j∈KNN(r)},就將r歸入q所屬的類簇,并且將樣本r加到隊列Vq的尾部;依次將樣本點納入隊列Vq。

Step3若隊列Vq不是空隊列,則轉Step4。

Step4若CI中還存在未被訪問的樣本點,則轉Step1,否則算法結束。

(2) 分配策略2:對邊界網(wǎng)格內(nèi)噪聲點進行分配,具體實現(xiàn)算法如下:

Step1對所有未被分配的噪聲點樣本i,統(tǒng)計其K近鄰KNN(i)中歸屬于類簇c(c=1,2,…,|CI|)的樣本得分Nc(i),得到1×|CI|的向量N(i),對全部沒有被分配的樣本點組成一個n×|CI|識別矩陣S,其中S(i,j)=Nj(i),j=1,2,…,n。

Step2根據(jù)Nk(p)=max{Nk(i),i=1,2,…,n},從識別矩陣S中選取同類樣本中最大得分對應的噪聲點樣本p,Nk(i)為每個樣本的分數(shù)組成向量。將樣本p以下分配方式歸入對應類簇中,若Nk(p)=k,則矩陣S中該同類樣本的所有噪聲點都分配到最大分數(shù)值Nk(p)所對應的簇;若0

Step3更新矩陣S,對于KNN(p)不存在分配樣本q,則令Nk(q)=Nk(q)+1,并將分配樣本p在矩陣S所對應向量N(p)置為0。

Step4若沒有未分配的噪聲點樣本,則終止算法,否則,轉到Step2。

2.3 GSSN算法流程

輸入:高維數(shù)據(jù)集D,分配樣本的近鄰數(shù)K。

輸出:聚類的結果C。

Step1數(shù)據(jù)的預處理:歸一化、有誤數(shù)據(jù)剔除及缺失數(shù)據(jù)處理。

Step2網(wǎng)格劃分數(shù)據(jù)空間,根據(jù)式(6)建立網(wǎng)格索引表。

Step3根據(jù)式(7)得到中心密度值判斷邊界網(wǎng)格,式(8)對邊界網(wǎng)格中噪聲點進行檢測。

Step4從網(wǎng)格決策圖中選取恰當?shù)念惔刂行暮霞疌I,根據(jù)式(10)得到數(shù)據(jù)樣本的局部密度峰值。

Step5按照分配策略1對除邊界網(wǎng)格內(nèi)高密度的非噪聲點樣本進行分配。

Step6按照策略2,對策略1沒有分配的低密度噪聲點根據(jù)樣本K近鄰信息進行分配。

Step7若沒有未分配的樣本點,聚類結束,否則返回Step3。

2.4 算法時效性分析

3 實驗與結果分析

3.1 UCI非均衡數(shù)據(jù)集

本文選取表1的人工數(shù)據(jù)集和UCI數(shù)據(jù)集對提出的GSNN算法進行測試,根據(jù)聚類準確率ACC、蘭德指數(shù)ARI和互信息AMI指標[16]與SNN算法進行實驗比較驗證,實驗表明本文算法對高維數(shù)據(jù)集內(nèi)有效分配噪聲點,使聚類結果的魯棒性更好。本文實驗環(huán)境的處理器為Intel?i5-4210 2.60 GHz,內(nèi)存為4 GB。本文算法中網(wǎng)格控制因子取a=1.7、網(wǎng)格密度占比取λ=0.25。接下來通過實驗結果對SNN和改進后的GSNN聚類算法進行實驗分析。

3.2 結果分析

從圖3的Aggregation和圖4的Spiral數(shù)據(jù)集聚類結果可以看出,SNN算法對邊界的噪聲點識別度低,導致屬于同一簇的數(shù)據(jù)點沒有被正確分配,而GSSN算法通過邊界網(wǎng)格內(nèi)樣本點的局部密度,得到密度稀疏的噪聲點后采用K近鄰信息進行類簇分配,從圖5的Path-based數(shù)據(jù)集聚類結果可以看出,SNN算法聚類后黑色的第3類簇結果誤分嚴重,本文GSSN算法通過不同密度的網(wǎng)格得到各個類簇核心點,有效識別各種類簇的形狀,聚類效果較好。

(a) SNN算法 (b) GSNN算法

從表2的UCI真實數(shù)據(jù)集算法的聚類對比結果可以看出,在Libras movement高維數(shù)據(jù)集上,本文GSSN算法在ACC值、ARI值和AMI值相比SNN算法得到明顯提高,主要是因為數(shù)據(jù)特征數(shù)較多,SNN算法不能有效地尋找到類簇核心點,而GSSN算法根據(jù)網(wǎng)格中心密度值判斷類簇核心點,從數(shù)據(jù)的分布特征改善聚類的準確率。從Segmentation數(shù)據(jù)集聚類結果可以看出,GSSN算法在各級指標上同樣優(yōu)于SNN算法,同時大數(shù)據(jù)集Segmentation中GSNN算法耗時明顯小于SNN算法,主要因為本文算法數(shù)據(jù)集中讀取數(shù)據(jù)點根據(jù)網(wǎng)格密度來處理分配,不需要對數(shù)據(jù)進行過多處理。在Waveform數(shù)據(jù)集上存在大量的噪聲點,導致SNN算法的ARI僅為0.268,而GSSN算法有效識別邊界網(wǎng)格內(nèi)噪聲點后,采取K近鄰信息對其進行分配,達到更好的聚類效果。

表2 不同算法的G-means值對比結果

4 結 語

根據(jù)SNN算法對高維數(shù)據(jù)集進行聚類時,數(shù)據(jù)特征數(shù)較多影響類簇核心點的識別,并且不能有效處理噪聲數(shù)據(jù)點,導致聚類準確率較低。本文提出一種基于網(wǎng)絡框架下改進的多密度SNN聚類算法,即通過網(wǎng)格劃分數(shù)據(jù)空間,根據(jù)網(wǎng)格中心密度值識別出類簇核心點和邊界網(wǎng)格的噪聲點,然后計算邊界網(wǎng)格的樣本局部密度,對非噪聲點根據(jù)數(shù)據(jù)分布特征進行分配,對噪聲點使用k近鄰信息進行分配,從而減少噪聲點錯誤分配,提高聚類算法的準確率。在人工數(shù)據(jù)集合UCI的真實數(shù)據(jù)集中聚類結果表明本文算法性能更優(yōu)秀,超過了比較的SNN算法。但本文算法并沒有考慮對高維數(shù)據(jù)集中離群點的檢測和處理,下一步的研究方向是在多維網(wǎng)格結構框架下得到數(shù)據(jù)分布特征識別和處理離群點,提高聚類算法的魯棒性。