基于改進無參數K-means算法的刀具狀態分析

吳曉勇,侯秋豐,羅 勇

(浙江向隆機械有限公司 產品開發部,浙江 寧波 315311)

0 引 言

K-means算法具有簡潔、收斂速度快、處理大規模數據集時能延展伸縮等優點[1-4]。但在對數據進行聚類分析時,需要預先知道聚類數k,而對很多數據集,初始的聚類數k難以預知; 并且K-means初始的聚類中心隨機選擇,可能導致算法的聚類結果不夠穩定,最后收斂于局部最優的情況。

針對上述問題,目前人們已經進行了許多改進。何洪磊[5]提出了一種基于密度峰值網格的K-means初始聚類中心優算法,其綜合了網格分析的高效性和密度峰分析的準確性,在人工模擬數據集和UCI(University of California,Irvine)數據集上獲得了比傳統K-means和K-means++更好的聚類效果以及更快聚類速度。王海燕等[6]提出了Canopy+_K-means算法,從閾值獲取方式和初始聚類中心的選取兩方面進行了改進。Tunali等[7]提出一種多集群球形K均值算法,其允許在K-means聚類過程將一個樣本點同時分配給多個集群,只要滿足相似比率限制參數的指定條件,即可確定分配的最大集群數。Redmond等[8]提出一種采用kd-樹確定K-means聚類中心的方法,通過kd-樹獲取數據的密度估計,然后使用距離和密度信息進行選擇,依次選擇k個聚類中心。Ismkhan[9]提出I-K-means-plus方法,該算法嘗試在K-means算法每次迭代過程中刪除一個簇,然后拆分另一個簇進行迭代,以此提高K-means的聚類精度,該方法以較小的額外時間成本為代價,提高了算法的精度。

為解決上述問題,筆者提出一種無參數K-means算法。首先,計算樣本點的局部密度和離散度,然后建立決策圖,將兩個參數組成向量,計算每個點到周圍點的距離,篩選出距離大于2倍均方差且密度大于平均密度的點作為算法的初始聚類中心,統計聚類中心個數k作為聚類個數,將初始聚類個數k以及初始聚類中心作為K-means算法的初始參數對數據進行聚類。對UCI數據集、人工建立的高斯數據集以及真實刀具振動數據集3種不同的數據集進行聚類,與傳統K-means算法、FCM(FuzzyC-means)聚類算法和GKM(GlobalK-Means)算法聚類效果對比的結果表明,所提算法保持傳統算法全局最優性,驗證了筆者提出的算法具有有效性。此外,由于K-means是一種無監督聚類方法,在獲得較優刀具狀態識別結果的同時,可減少人工數據標定,有監督訓練等工作量及運算成本,對準確實時提取數控機床刀具運行狀態具有較高的實際意義。

1 算 法

1.1 K-means聚類算法

K-means算法是一種基于距離測量的聚類分析算法。該算法的聚類過程如下:首先輸入聚類個數k,從待聚類的數據集中隨機選取k個對象作為算法的初始聚類中心,然后計算選擇的聚類中心和對象間的距離,將樣本對象分配給距其最近的聚類中心。并且初始選定的聚類中心也會隨著每個樣本的分配而被重新選定。

算法的輸入是一個無標記的數據集合{x(1),x(2),…,x(m)},因為這是無監督學習算法,所以在集合中只能看到x,沒有類標記y。K-means聚類算法是將樣本聚類成k個簇(Cluster),具體算法步驟如下:

Step 1 隨機選取k個聚類質心點(Cluster Centroids),則等于存在了k個簇c(k):

μ1,μ2,…,μk∈Rn。

(1)

Step 2 對所有x(i),分別計算質心μj和x(i)的距離,x(i)是離其最近的質心μj的簇c(j):

(2)

Step 3 對每個類c(j),重新計算該簇質心的值:

(3)

重復Step2和Step3,直到算法收斂。

1.2 基于密度峰值聚類算法

Rodriguez等[10]通過快速搜索并找到密度峰值的聚類方法(CFSFDP:Clustering by Fast Search and Find of Density Peaks),算法計算2個參數:局部密度ρi和高密度點之間的距離δi,并根據這2個參數之間的關系建立決策圖。

首先,需分別計算所有數據點i的局部密度ρi,以及與其余高密度點的距離δi,數據點間的距離dij決定了ρi,δi的值,上述數值滿足三角不等式關系時,將ρi定義為

ρ(xi)={x|d(x,xi)≤dc},

(4)

其中d(x,xi)為其他數據點和xi的距離,dc為截止距離。通常,分布于數據點xi鄰域范圍內的點的個數作為xi的局部密度ρi,鄰域的截止距離為dc,δi則表示點xi與其他高密度之間的最小距離:

(5)

對密度最大的數據點,δi用所有點之間的最大距離表示為

(6)

CFSFDP算法將相對較大的ρi、δi選為聚類中心,其他點被分到與它最近的聚類中心的類,較小的ρi、較大的δi的特征點看作噪聲。

1.3 筆者算法

由于K-means算法無法確定聚類個數,且前期隨機選取聚類中心易導致聚類結果陷入局部最優的問題,筆者結合CFSFDP算法得出自動確認聚類個數、中心的一種無參數K-means聚類算法。首先確定xi的鄰域U(xi),U(xi)定義為

U(xi)={xj|xj∈X&dij≤dl}(i≠j),

(7)

其中dij=d(xi,xj)為樣本點xi和xj之間的歐氏距離;dl為距離閾值,代表數據集X所有樣本點之間歐氏距離的平均值的1/10,計算公式為

(8)

(9)

(10)

筆者以樣本點xi與其他高密度點的距離衡量樣本點xi與其他高密度點的離散程度,記為δi。通常,數據集中密度最大的數據點,可默認為一個聚類中心,計算該點與數據集X中所有點的最大距離; 對剩余的數據點,計算該點與其他高密度點之間的最小距離,公式為

(11)

(12)

在計算了數據集中每個點的局部密度ρi和離散度δi后,將每個樣本點歸一化后的鄰域密度和離散度組成一個向量(ρi,δi),并將ρi作為橫坐標,δi作為縱坐標得到算法的決策圖。此時,計算數據點xi與其最近鄰的5個點的距離之和的均值:

(13)

將Di值按降序排列,篩選出Di值大于2倍均方差且局部密度大于數據集中所有點的平均密度的點,作為筆者算法篩選出的聚類中心,算法統計聚類中心的個數k作為待聚類數據集的類的個數。

在確定聚類中心值{c1,c2,…,ck}以及初始聚類數k后,將其作為K-mean算法的初始輸入參數,實現對多類數據集的無參數聚類分析。對數據集X,將其中的每個樣本分配到距離其最近的類中,并使誤差函數J達到最小,則完成聚類,則有

(14)

其中N為樣本數量,k為聚類個數,d(xi,cj)為數據集中第i個樣本xi與第j個聚類中心cj之間的歐氏距離。

綜上,筆者所提出的一種無參數K-means算法的實現步驟為:

Step 1 確定數據集中每個待聚類樣本點xi的鄰域U(xi),然后計算每個樣本點的鄰域密度ρi并歸一化;

Step 2 計算樣本點xi的離散度δi并歸一化;

Step 3 將每個樣本點歸一化后的鄰域密度和離散度組成一個向量,并以樣本點的鄰域密度ρi作為橫坐標,離散度δi作為縱坐標繪制決策圖;

Step 4 評估數據點xi是否為候選聚類中心,實現方法為計算該點與其最鄰近5個點的距離之和的均值Di,將Di值降序排列,篩選出Di值大于2倍均方差、且局部密度大于數據集中所有點的平均密度的點作為初始聚類中心,記錄聚類中心的個數k;

Step 5 將上一步得到的聚類中心點和聚類中心個數k作為K-means算法的聚類中心和聚類中心個數,對數據集進行聚類。

2 實 驗

2.1 數據集選取

為驗證筆者所提出的算法是否有效,對多個數據集進行了測試。測試過程中,選擇模擬和真實數據集分別進行檢驗。圖1為模擬數據集的空間分布形式,每個不同點的位置由不同坐標軸表示,不同數據集分別代表不同的數據分布類型。圖1a包含了5個類的數據集,每個類之間點的聚類較近,不同類之間數據點之間的距離較遠; 圖1b包含了20個類的數據集,類的數量較多,其中包含彼此距離較近的類,也包含距離較遠的類; 圖1c數據集中包含了重疊數據集; 圖1d數據集為不平衡數據集,不同數據類之間數量差別較大,分別為1 000,400,100。

圖1 高斯數據集

使用仿生傳感器對機床上的刀具振動情況進行采集后,得到振動數據集,將得到的振動數據集與UCI數據集結合組成本次實驗所需的真實數據集,表1為真實數據集的相關信息。

表1 真實數據集和UCI數據集信息

Iris數據集由3個不同類別的鳶尾花的特征組成,每個類的數量均為50個。其中有一類鳶尾花特征與其他兩類線性可分,另外兩類線性不可分。Statlog(Heart)數據集的樣本特征表征了患者是否患有心臟疾病,共包含兩類:有心臟病的類包含150個樣本,沒有心臟病的一類包含120個樣本,每個樣本包含13個特征。Ionosphere數據集為約翰霍普金斯大學電離層數據庫,預測結果為良好和不良,類的樣本個數分別為225和126,每個樣本包含34個特征。Robot_Navigation數據集為Scitos G5移動機器人的墻面導航任務,筆者選擇2個超聲傳感器采集機器人3種行為的數據集進行聚類,機器人的3種行為分別是輕微右轉、向右急轉和向前行進,類的樣本個數分別為50、54和52,包含2個樣本特征。Wine數據集包含了178個樣本,每個樣本有13個特征,其中包括了酒的化學成分。該數據集是分類問題,用于區分3種不同來源的意大利葡萄酒。Breast Cancer Wisconsin(Diagnostic)數據集包含了569個樣本,每個樣本有30個特征,用于診斷乳腺癌。該數據集是一個二分類問題,用于區分良性腫瘤和惡性腫瘤。刀具振動信號數據集涵蓋了刀具在3種類型磨損情況下不同的振動信號,包含初期磨損信號150個,中期磨損信號37個,急速磨損信號20個。

2.2 結果分析

首先,對筆者構建的具有不同特點的二維高斯分布的數據集,分別運行K-means、FCM和筆者算法,聚類結果如圖2所示。不同灰度的點代表不同的數據類,“+”代表筆者算法確定的聚類中心。

圖2 筆者算法聚類結果

通過聚類結果可以看出,K-means算法能對圖3a均勻分布的數據集和圖3c正確分類。對圖3b中20個類的分布不均勻數據集,K-means算法將右下角的2類錯分成1類,將右上部分的1個類分成2類,而且對圖3d的不平衡數據集分類結果較差。FCM算法能對分布均勻的數據集、重疊數據集和不平衡數據集較好地分類。但對圖4b的20個類的分布不均勻數據集,其將右上角的2個類錯分成1類,右上部分的1個類分成了2類,未取得正確的聚類結果。筆者算法在多類數據集、重疊數據集和不平衡數據集等不同特征數據集上,均能準確確定聚類個數,并且具有較好的聚類效果。

圖3 K-means算法聚類結果

圖4 FCM算法聚類結果

2.3 全局最優性能實驗

使用UCI數據集對本算法進行檢驗,以此判斷其全局最優性。選擇的6個數據集為Iris,Statlog(Heart),Ionosphere,Robot_Navigation,Wine和Breast Cancer Wisconsin(Diagnostic)。筆者使用3個評價指標:精確率(Precision,P)、召回率(Recall,R)和調整蘭德系數(ARI:Adjusted Rand Index)評估算法的聚類性能。精確率是真正的正樣本占預測為正例樣本的比例:

(15)

召回率是正例被預測正確的比例:

(16)

ARI的取值范圍在[-1,1]之間,ARI結果為正值時,說明聚類效果較好:

(17)

其中NTP為真陽性,NTN為真陰性,NFP為假陽性,NFN為假陰性。

為驗證筆者算法的有效性,將筆者算法與傳統K-means算法、FCM算法和GKM算法在不同UCI數據集上聚類,評價指標對比結果如表2所示。

表2 4種算法聚類結果對比

從表2可看出,筆者所提方法在不同的UCI數據集上聚類的各項評價指標效果與K-means算法、FCM算法和GKM算法相比有明顯的提升。在實驗的對比結果中,除在Statlog(Heart)數據集上的召回率不如其他3種聚類算法外,在Iris數據集、Ionosphere數據集、Robot Navigation數據集、Wine數據集和Breast Cancer Wisconsin(Diagnostic)數據集上聚類結果相較于其他3種聚類算法,在精確率、召回率及ARI評價標準上都具有明顯的優勢。因此可以證實筆者算法的有效性。由于筆者算法具體聚類過程還是依靠于K-means算法,未來可以結合筆者算法在確定聚類中心和聚類個數上的貢獻,在聚類過程中進一步提高算法聚類的準確度。

比較2種算法對刀具振動信號數據集的聚類效果,207個振動信號樣本中,K-means算法在該數據集的聚類的結果為:初期磨損信號66個,正常磨損信號125個,急劇磨損信號16個,算法最終識別準確率為75.8%。筆者算法在刀具振動信號樣本數據集上聚類結果為:初期磨損信號42個,正常磨損信號158個,急劇磨損信號7個,算法最終識別準確率為84.1%。由聚類結果可看出,筆者算法在實驗數據集上得到的聚類準確率更高,可有效用于刀具磨損狀態監測分析中。綜上,筆者算法通過在不同特征數據集上的聚類取得了理想的聚類效果,能解決K-means算法不能確定初始聚類個數和聚類中心的問題。

3 結 語

由于傳統K-means算法在聚類過程中需要事先知道聚類個數,且隨機選取初始聚類中心容易使聚類結果陷入局部最優的情況,因此筆者提出一種無參數K-means聚類算法。在高斯數據集、UCI數據集和真實刀具振動信號數據集上分別進行了聚類實驗。實驗結果表明,與其他同類算法相比,無參數K-means聚類算法既具有傳統算法的全局最優性,又在不同類型的數據集上取得了良好的聚類效果。此外,該方法可用于數控機床刀具磨損狀態的識別,由于K-means是一種無監督聚類方法,在獲得較優刀具狀態識別結果的同時,可減少人工數據標定,有監督訓練等工作量及運算成本,對準確實時提取數控機床刀具運行狀態具有較高的實際意義。由此可見,筆者無參數K-means算法彌補了K-means算法所存在的缺陷,即無法確定初始聚類個數和初始聚類中心隨機選取而導致的局部最優問題。然而,筆者算法具體聚類過程仍然依賴于K-means算法,未來可以結合本文算法在確定聚類中心和聚類個數上的貢獻,在聚類過程中進一步提高算法聚類的準確度。