一種基于網格框架下改進的多密度SNN聚類算法

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

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

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

0 引 言

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

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

1 共享最近鄰SNN聚類算法

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

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

(1)

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

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

(2)

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

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

(3)

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

2 基于網絡框架下改進的多密度SNN聚類算法

2.1 網格簇邊界噪聲點檢測

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

(4)

numi=[(hi-li)/length]

(5)

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

indi=[(xi-li)/length]

(6)

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

(7)

(8)

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

(9)

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

圖1 邊界網格噪聲點檢測示意圖

圖2 GSSN算法邊界網格內噪聲點分配圖

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

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

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

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

(10)

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

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

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

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

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

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

(2) 分配策略2:對邊界網格內噪聲點進行分配,具體實現算法如下:

Step1對所有未被分配的噪聲點樣本i,統計其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根據Nk(p)=max{Nk(i),i=1,2,…,n},從識別矩陣S中選取同類樣本中最大得分對應的噪聲點樣本p,Nk(i)為每個樣本的分數組成向量。將樣本p以下分配方式歸入對應類簇中,若Nk(p)=k,則矩陣S中該同類樣本的所有噪聲點都分配到最大分數值Nk(p)所對應的簇;若0

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

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

2.3 GSSN算法流程

輸入:高維數據集D,分配樣本的近鄰數K。

輸出:聚類的結果C。

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

Step2網格劃分數據空間,根據式(6)建立網格索引表。

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

Step4從網格決策圖中選取恰當的類簇中心合集CI,根據式(10)得到數據樣本的局部密度峰值。

Step5按照分配策略1對除邊界網格內高密度的非噪聲點樣本進行分配。

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

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

2.4 算法時效性分析

3 實驗與結果分析

3.1 UCI非均衡數據集

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

3.2 結果分析

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

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

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

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

4 結 語

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