基于殘差和密度網格的簇心自確認聚類算法

陳勝發，賈瑞玉

安徽大學 計算機科學與技術學院，合肥230601

1 引言

聚類算法是數據挖掘中最經典的算法之一，已經得到了許多學者的研究。聚類技術在許多領域得到了廣泛的應用。在商業領域，它可以用來分析顧客的行為，為商業營銷策略的制定提供重要的依據[1-2]。此外，在互聯網電子商務領域，它可以用來分析符合用戶瀏覽日志的相似客戶的特征，從而幫助互聯網商家提供更好的客戶服務[3]。

聚類是將樣本元素分為不同的簇，在同一簇中的元素都是具有較高的相似度，不同簇中的元素相似度低[4]。數十年來國內外專家學者對聚類算法進行了深入研究，已獲得了相當好的成果。如基于劃分的聚類算法[5]有K-means[6]、K-medoids[7]等；基于密度的聚類算法有DBSCAN[8]等；基于層次的聚類算法有CURE[9]等；基于網格的聚類算法有STING[10]等。

文獻[11]結合密度峰值，提出了一種基于密度的Canopy算法，將改進的Canopy算法作為K-means算法的預處理過程，從而提高了K-means的聚類質量。文獻[12]利用網格對數據空間劃分并使用KL散度進行相似性度量，解決了不確定數據聚類問題（存在于障礙空間），并很好提升了算法的聚類效果。CCDDG算法[13]以網格化數據集空間，用網格對象代替數據對象，大大地降低了計算復雜度，但是最終的初始聚類中心和聚類數目還需要人工來選取。SNIC_K-means算法[14]利用樣本點在數據集空間中的分布信息來確定數據集的聚類數目和初始聚類中心，但算法需要計算每個數據對象的密度值、距離值和殘差，計算復雜度非常大。

2014年6月，Laio等人在Science發表了快速搜索和發現密度峰值的聚類算法（Clustering by fast search and find of Density Peaks，DPC）[15]，該算法的思路是將具有局部較大密度且與其他密度更高的有較遠距離的數據點視為聚類中心，通過快速搜索聚類中心，將每一個非聚類中心的數據點沿著密度遞增的最近鄰方向劃分到對應的聚類中心中，實現數據劃分。該算法與傳統的聚類算法相比，具有較好的聚類效果，但存在以下的幾個問題：（1）樣本的密度取值依托于截斷間隔dc；（2）需要計算所有樣本間的距離，計算復雜度大；（3）需要通過人工監督的方式從決策圖中選取出簇心對象。

為了解決文獻[15]的三個問題，本文結合文獻[13]和文獻[14]的優點，提出了基于殘差和密度網格的簇心自確認聚類算法（Self-confirming Clustering algorithm based on Residual Error and Density Grid，REDGSC）。該算法首先將數據集空間網格化，刪除沒有任何信息的網格對象；然后計算每個網格對象的密度值ρ和距離值δ；接著通過殘差分析從計算得到的ρ和δ中決策出簇心網格對象；最后，根據一種密度距離的劃分方式來對劃分網格對象，再用與非邊緣點的距離和自變動的閾值來處理網格邊緣點和噪聲點，完成數據集的聚類。

2 REDGSC算法介紹

2.1 密度網格思想介紹

將數據的每一維進行等距離劃分，均勻劃分成相同的段數，記為fG；將數據集空間分割成若干個超矩形網格對象，刪除不含任何信息的網格對象，剩余的網格對象就是所需要的，記為G；網格對象的個數記為NG。經過多次實驗表明，當網格對象數量NG大于或等于數據集中的數據對象個數n的1/8時，算法的聚類效果最佳。圖1為二維數據集的網格化結果。網格化具體步驟如下：

步驟1將含有n個數據對象的數據集空間中每一維劃分成相同段數，記為f（初值為2），形成網格。

步驟2刪除不含任何信息的網格對象，剩余的記為N。

步驟3如果N＜n/8，則讓f=f+1，然后返回步驟1。

步驟4最后確定網格對象集G，劃分段數為fG，網格對象數NG。

圖1 二維數據集的網格化

確定網格對象集后，接下來就是如何計算網格對象的密度值ρ和距離值δ，相關定義如下：

定義1（密度值）將網格對象i中的數據元素個數作為密度值，記為ρi。

定義2（網格對象距離）網格對象i和網格對象j之間距離為：

其中，xi和xj為網格對象i和網格對象j中的數據對象的平均值；xip(i=1,2,…,n;p=1,2,…,d)代表網格對象i的第p維屬性；d為數據的維數。

定義3（距離值）δi表示網格對象i到具有更高密度值的網格對象j的最近距離。如果網格對象i的密度值為最大值，δi定義為max(dij)；如果網格對象i的密度值不是最大值，δi被定義為min(dij)，具體定義如下：

2.2 決策圖介紹

在Rodriguez和Laio在Science期刊上提出的聚類中心在與具有更高密度值的數據對象之間具有較大的距離δ且具有較高的密度值ρ的假設下，REDGSC算法網格化數據集空間后，含有簇心的網格對象也是具有較高的密度值ρ和較大的距離值δ。通過定義1和定義3，計算出每個網格對象的密度值和距離值，構造出網格對象的δ和ρ的決策圖，如圖2所示。

通過圖2，人工很容易認為最偏離的兩個點就是含有簇心的網格對象。但是這樣人工選取的方式非常不智能化而且還比較繁瑣，所以本文引入了殘差分析的方法來自動決策出含有簇心的網格對象。

2.3 殘差分析確認簇心

圖2 ρ和δ的決策圖

從2.2節的決策圖中可以很容易地看出簇心所在的網格對象，但是這屬于人工選取，并且這也是文獻[15]的思想中的一個缺陷。為了能自動從網格對象集中獲取較大的ρi和δi的網格對象，進而引用統計學中的殘差分析和線性回歸，利用規范化殘差來自動獲取含有簇心的網格對象。相關概念如下：

概念1研究變量間函數關系是回歸分析中的一種方法。設響應變量為Y，以X1,X2,…,Xp表示預測變量，其中p是預測變量的個數，Y與X1,X2,…,Xp的關系可以用以下回歸模型來描述：

其中，ε為隨機誤差，是模型不能高精度擬合數據的緣由。函數f(X1,X2,…,Xp)描述了Y與X1,X2,…,Xp之間的關系。

概念2響應變量Y的擬合值Y*是使用擬合函數獲得的值，其表述如下：

例如，假設用以下線性模型：

來擬合某二維數據集中變量xi和yi的關系，則響應變量yi的擬合值如下所示：

概念3殘差是擬合值減去觀測值的相反數，殘差ei的定義如下：

其中，yi和分別是xi對應的觀測值和擬合值。

在回歸分析中，測定值減去由回歸方程預測出來的值所得到的值，以δ0表示。殘差δ0遵從正態分布N(0,σ2)；(δ0)/標準化殘差，稱為規范化殘差，以δ*表示；δ*服從標準正態分布N(0,1)。若某一網格對象的規范化殘差的值在(-1,1)區間之外，則該網格對象一定是異常的，這個定論在統計學的書籍[16]中有介紹過。

從決策圖中獲取具有較大的ρi和δi的網格對象，就是在決策圖中找到異常點，因此找到合適的回歸模型是非常重要的，從而求出決策圖中每個網格對象的殘差，并將殘差進行規范化，則規范化殘差的絕對值大于1的網格對象就是含有簇心的網格對象。

圖3是圖2中數據的走勢圖，從圖2中可以看出，幾乎所有網格對象對應的點都靠近ρ軸和δ軸，并且這些點分布在一條反比例曲線周圍，因此本文使用函數δ=a0+a1×(1/ρ)來擬合ρ和δ的關系。通過圖3可以看出除了可以被確認為含有簇心的網格對象外，大部分數據點都集中在反比例曲線上。運用殘差分析從決策圖中得到具有較大的ρi和δi的數據對象的步驟流程如下：

步驟1用函數δ=a0+a1×(1/ρ)來擬合決策圖中δ和ρ的函數關系。

步驟2令ρ*=1/ρ，可將步驟1中的擬合函數線性化為δ=a0+a1×ρ*。

步驟3根據步驟2中的擬合函數來擬合數據點，然后計算每個網格對象對應的數據點的殘差ei。

步驟4將步驟3獲得的殘差進行規范化。

步驟5通過比較計算得到規范化殘差的絕對值大于1的網格對象對應的數據點，這些網格對象對應的數據點就是含有簇心的網格對象。

圖3 決策圖的數據走勢圖

圖4 是圖2中數據點的規范化殘差圖，以ρ*為橫軸，標準殘差δ*為縱軸。在圖4中，在兩條虛線外有兩個數據點，也就是說這兩個網格對象就是含有簇心的網格對象。

圖4 決策圖的規范化殘差圖

至此，已經較好地解決了自動選取網格對象集中含有簇心的網格對象的問題。

2.4 聚類過程

在自動選好簇心網格對象后，首先為每個簇心網格對象標上不同編號，然后根據已經計算出來的每個網格對象的密度值ρ，將剩余的網格對象的標號跟隨距離最近且密度值更高的已經標號的網格對象，這樣就可以很快地完成網格對象集的聚類，網格對象集的聚類完成也就是整個數據集的聚類完成。

2.5 邊緣點和噪聲

2.5.1 邊緣點處理

對于邊緣點的處理，首先就是選取出邊緣處的網格對象；然后計算所有非邊緣數據對象到選取出來的邊緣網格對象中每個數據對象之間的距離；接著就是將這些邊緣網格對象中的數據對象標上和它們距離最近的非邊緣數據對象一樣的編號，這樣就完成了邊緣點的處理。

2.5.2 噪聲處理

由于噪聲點一般都是離群點，網格化數據集后，噪聲點都是處于邊界網格對象內，所以對于噪聲點的處理，這里是用自動變換的閾值來代替人工設定的噪聲點閾值。首先就是找到簇與簇之間的邊界網格對象，然后將邊界網格對象中密度最大值作為閾值，記為ρb，只要是密度值低于ρb的網格對象，就視為噪聲點，將其刪除。將邊界網格對象中密度最大值作為閾值，這樣就能很好地去除大部分噪聲點，并省去人工設定閾值的麻煩，雖然這樣的設定有可能將一些有用的信息刪除，但是通過實驗證明，聚類準確度得到了很大的提高，這是因為噪聲點會對聚類精度產生很大的影響，在犧牲一些有用的信息的同時可以刪除大量的噪聲點，所以聚類準確度得到很大的提高。

3 算法流程和仿真實驗

3.1 算法流程

本文提出了一種基于殘差和密度網格的簇心自確認聚類算法。首先網格化數據集空間，刪除沒有任何信息的網格對象；然后就是通過殘差分析自動獲取含有簇心的網格對象；最后通過密度距離的劃分方式進行聚類操作。

REDGSC算法的處理流程如下：

步驟1輸入數據集D={x1,x2,…,xn}。

步驟2根據2.1節中的網格化步驟來網格化數據集空間，得到網格對象集G={X1,X2,…,Xn}。

步驟3根據定義1和定義3求出G中每個網格對象的ρi和δi。

步驟4運用線性函數δ=a0+a1×ρ*（其中ρ*=1/ρ去擬合ρi和δi的關系。

步驟5計算每個網格對象的殘差，并規范化所有殘差。

步驟6從規范化殘差中，通過計算選出殘差絕對值大于1的網格對象，這些被選出來的網格對象就是含有簇心的網格對象。

步驟7根據2.4節和2.5節，并以步驟6中獲得含有簇心的網格對象，對G中的網格對象進行聚類。

步驟8輸出聚類結果。

詳細算法流程圖如圖5所示。

3.2 仿真實驗與分析

3.2.1 性能對比

為了測試本文算法的聚類性能，實驗采用7個不同分布的人工數據集AD1、AD2、AD3、AD4、AD5、AD6和一個UCI數據集Iris，7個數據集的參數描述如表1所示。本文算法使用的聚類準確率R為正確分類的數據對象個數占總數據對象個數的百分比。實驗中每個算法在每個數據集上都運行10次，在這10次運算中，獲取平均算法執行時間Ta、平均聚類準確度Ra、最高聚類準確度Rmax和最低聚類準確度Rmin，在這里對于算法執行時間的計算，并沒有考慮CCDDG和DPC兩個算法的人工決策出聚類簇心的時間。

表1 7個數據集的具體描述

圖5 算法流程圖

AD1～AD6數據集的二維分布如圖6所示。AD1～AD6數據集網格化后網格對象對應的規范化殘差的ρ*和δ*分布如圖7所示，Iris對應的ρ*和δ*分布如圖8所示。

本文以CCDDG算法、DPC算法、SNIC_K-means算法和REDGSC算法，在給出的7個數據集上進行對比實驗，以測試本文算法的聚類性能，實驗結果如表2所示。

3.2.2 算法執行時間分析

由表2的實驗結果可知，使用網格化數據集空間的REDGSC算法和CCDDG算法在7個數據集上的平均執行時間都小于DPC算法和SNIC_K-means算法，其中當數據量相對較大（達到2 000以上）的時候，執行時間下降了30倍以上。對于REDGSC算法在執行時間上大于CCDDG算法，這是因為本文算法添加了殘差分析來自動確認簇心和對于邊緣點和噪聲的處理，這兩個操作增加了本文算法的執行時間。

圖6 6個數據集的二維分布圖

圖7 6個數據集的網格對象對應的規范化殘差ρ*和δ*分布圖

圖8 Iris對應的ρ*和δ*分布圖

表2 4種算法在7個數據集的實驗結果

3.2.3 算法復雜度分析

設聚類數據集是一個含有n個m維的數據集，首先算法對數據集進行網格化并得到網格對象的密度值，這個過程的計算復雜度為O()；然后計算每個網格對象的距離需要的計算代價為O((N2-N)/2)，算法進行一次距離密度的劃分完成聚類，其計算代價為O(N lg N+N/2)；接著就是邊緣點和噪聲處理的過程的計算代價為O(bn+aN)，其中b表示邊緣點的個數，a表示簇與簇之間的邊界網格對象個數；最后就是線性回歸和殘差分析的計算代價O(N2+N)。因此REDGSC算法的算法時間復雜度為O(+N lg N+3N2/2+N+bn)。

由表3可以分析得到：相比SNIC_K-means和DPC，REDGSC算法有著較低的時間復雜度，所以在執行速度方面，REDGSC算法相比前兩個算法，有著較快的表現；而相比CCDDG算法，REDGSC算法有著較高的時間復雜度，這是因為線性回歸和殘差分析的過程中消耗了部分時間。但REDGSC算法的優勢：（1）能夠自動確定簇心而不是人工選??；（2）確定含有簇心的網格對象后，利用一種密度距離的劃分方式進行類簇的劃分，這就使得REDGSC算法對于任意形狀分布的數據集都有著較好的聚類效果。

表3 算法時間復雜度對比表

3.2.4 實驗結果分析

綜上7個數據集的實驗結果，可以看出REDGSC算法在聚類準確度和時間復雜度上都優于SNIC_K-means算法，這是因為REDGSC算法網格化數據集，將網格對象作為聚類對象，大大地降低計算復雜度，而且還進行了邊緣點和噪聲的處理，從而提高了聚類準確度。相比于CCDDG算法，REDGSC算法解決了CCDDG算法需要人工選取聚類中心的弊端，并在聚類準確度上高于CCDDG算法，這是因為REDGSC算法在網格化數據集后，在聚類的過程中進行了邊緣點和噪聲的處理。

對于REDGSC算法在聚類準確度上稍微低于DPC算法，是因為網格化數據集空間時，會有可能將不同簇的數據對象分到一個網格對象中，雖然REDGSC算法在后續操作中進行了邊緣點和噪聲的處理，但是這樣的處理并不能處理所有的情況，所以在聚類準確度上會有所降低，但是REDGSC算法很好地解決了DPC算法的三個缺陷（依賴截斷距離dc、計算復雜度高和需要人工選取聚類中心）。

4 結語

本文提出了一種基于殘差和密度網格的簇心自確認聚類算法。該算法將數據對象映射到網格上，用網格對象替換數據對象進行聚類計算，這樣大大減少了聚類過程中的計算量，加快了算法的執行速度。在算法聚類的過程中，采用一種密度距離的方式來劃分網格對象，這樣使得本文算法對于任意形狀分布的數據集都有著較好的聚類效果。而且在網格化數據集空間后的聚類過程中，對邊緣點和噪聲進行了處理，很好地提高了聚類準確性。通過實驗表明本文算法在保持著聚類準確度的前提下，很好地解決了DPC算法的三個缺陷。

由于本文算法在聚類準確性上低于DPC算法，因此，未來的研究就是提高算法的聚類準確性。