劉 鳳， 戴家佳， 胡 陽

(貴州大學 數學與統(tǒng)計學院，貴陽 550025)

0 引 言

聚類是無監(jiān)督學習中一個重要的方法，它在一定意義上檢測數據集中相似的對象，并形成群集的過程，這在大數據時代是很有必要的。聚類的最主要目的是使得群集與群集之間的距離最大化，群集內的對象距離最小化。同一個簇中的對象與該簇中其他的對象是非常相似的，不同群集之間中對象彼此差異是比較大的。MacQueen[1]提出k-means算法，該算法是一種最著名的劃分聚類算法，其算法原理在聚類算法中是比較簡單的，并且易于聚類。在實際生活中聚類分析也得到比較廣泛的應用[2-4]。雖其原理簡單，但是該算法也存在一些缺點，最主要有以下幾個方面：對球狀形數據集聚類結果較好，其他的數據集聚類結果相對較差；在聚類的時候容易局部收斂；k是隨機的，需要在聚類的時候人為給定；聚類算法中初始聚類中心的選取問題；若數據集中有離群點、數據類型不一致等對聚類結果影響比較大?？紤]這些不足之處，有大量學者對其不足進行改進，Arthur和Vassilvitskii[5]對其初始聚類中心隨機性做改進，首先在數據集中隨機選擇一個數據點作為第一個初始聚類中心；其次在數據集中選擇與第一個聚類中心相對最遠的點作為第二個類簇中心，依據這種原理，直到選出k個群集質心。然而聚類中心的選擇會影響聚類數目的準確性，Alibuhtto和Mahat[6]提出了一種基于距離的k-means算法，來確定聚類中的聚類數目。Masud等[7]提出了聚類數目與聚類中心的自動選擇方法，Zhou等[8]提出了基于遺傳算法的初始聚類中心的自動選擇。大量學者也在算法中對k值進行了改進，Qi等[9]提出了層次k-means算法來確定聚類中的k值。程明暢等[10]提出了基于類簇之間分位數半徑的動態(tài)k-means算法，改進的k-means聚類方法取得了良好的聚類效果。在聚類中，數據類型不一致以及離群點等會對聚類結果起到一定的影響，因此聚類中離群點的研究是近年來一個較為熱門的課題。Zhang等[11]提出了一種加權距離測度的高斯函數優(yōu)化k-means聚類算法。Jones等[12]提出了一種新的FilterK算法，通過降低離群值的影響來改善k-means聚類的結果，Yu等[13]將剔掉離群點檢測，應用到隱私保護中，Neelima和Kumar[14]提出基于離群點檢測應用到色調映射，數據集中有離群點對聚類的結果影響都比較大，基于離群點對數據集在聚類中影響比較大。

以上這些學者對k-means算法進行改進，使得k-means算法在聚類過程中k值的隨機性得到一定的解決，并提供了類簇中心選擇方法，但是對于數據集中的離群值對聚類過程產生較大的影響，筆者對數據集使用局部密度離群點LOF檢測方法對數據集進行處理，將離群值從數據集中剔除之后再使用k-means算法聚類。

1 k-means算法與局部密度離群點檢測方法

1.1 k-means算法

k-means算法是一種迭代算法，它是將數據集劃分為k個預先定義的不重疊的群集。在這種情況下，每個數據點都屬于一個群集。將數據集點分配到k個群集中，使數據點與群集的質心之間距離的平方之和達到最小。

k-means算法的5個主要步驟如下：

輸入：數據集D={x1，x2，…，xn}，類簇數為k。

輸出：k個類簇數C={C1，C2，…，Ck}。

Step1從數據集D中隨機選擇k個對象作為聚類中的初始中心。

Step2計算數據集D中的每一個對象到選取的k個對象之間的距離。

Step3根據Step 2將數據集D中的每一個對象劃分到距離最近的類簇中，即滿足下式：

dist(xi，Cj)=min{dist(xi，Cj)，i=1，2，…，n；j=1，2，…，k}

Step4重新更新每個群集的聚類中心，即

其中，Nj表示為第j個類簇中對象個數。

Step5反復進行Step 2、Step 3、Step 4，直到群集質心不再發(fā)生變化或者達到預先給定最大迭代次數，算法終止。

1.2 局部密度離群點檢測法(Local Outlier Factor，LOF)[15]

先給出幾個局部密度離群點檢測LOF方法的相關定義：d(X，Y)表示對象X與對象Y的距離。對象X的第k_距離(k_distance)：對給定的正整數k，在樣本空間Ω中，它與對象X之間的距離d(X，Ω)。樣本空間Ω中最遠的對象W與對象X的距離，不包括對象X，即k_distance(X)=d(X，W)。對象X的第k_距離鄰域(Nk(X))：

Nk(X)={Y|d(X，Y)≤k_distance(X)}

可達距離(Reach Distance)：數據集中X與Y之間的可達距離為

reach_dist(X，Y)=max{k_distance(X)，dist(X，W)}

局部可達密度(Local Reach Density，LRD)：

局部密度離群值因子：

2 聚類有效性評價指標

評估聚類結果的好壞，聚類有效性指標應能提供一些關于數據集分類質量的評價。最重要的體現在“類簇間相似度比較低，類簇內相似度較高”。聚類有效性評價方法有很多，采用的聚類評價指標有：DB指標、Dunn指標和Silhouette指標。

2.1 Silhouette指標(fsilhouette)[16]

計算數據集中每一個數據點的輪廓系數如：

其中，db(i)表示為數據集中點i與其他各類簇中點距離平均值中的最小值，dw(i)表示為數據集中點i與該類簇中其他點距離的平均值。fsilhouette值在-1和1之間，若為1，則數據集中點i分配在相應的類簇是恰當的；若為-1，則數據集中點i應該分配在其他的類簇；若為0，則數據集中點i可以分配在該類簇中，也可以分配到其他類簇中。

2.2 Davies-Bouldin指標(fDB)[17]

數據集中fDB指標計算如下：

其中，σi，σj表示對應的類簇內距離的平均值，d(ci，cj)表示質心ci，cj之間的距離，指標值越小，聚類結果中類簇內部越緊密，類簇間越分離。

2.3 Dunn指標(fDunn)[18]

數據集中的Dunn指標如下：

其中,d(i，j)表示數據集中任意兩個類簇之間的距離，d(k)表示數據集中任意類簇內距離。fDunn值越大，說明數據集的聚類結果較好。

3 實驗結果及其分析

3.1 人工隨機產生的數據集

人工生成的數據集，第一組為meanx1=3，meany1=2，方差為0.25的正太分布隨機數；第二組為meanx2=3，meany2=8，方差為0.25的正太分布隨機數；第三組為meanx3=9，meany3=5，方差0.25的正太分布隨機數；第四組為meanx4=15，meany4=2，方差為0.25的正太分布隨機數；第五組為meanx5=13，meany5=7，方差為0.25的正太分布隨機數，每一組產生100個正太分布隨機數；用runif函數生成均勻分布隨機數，最小值為9，最大值為20。人工生成的數據集用來驗證去除離群點之后的數據集與原始數據集做k-means聚類比較，其聚類圖以及評價指標如圖1—圖3。

圖1 原始數據集Fig. 1 The initial data set

圖2 原始數據集聚類圖Fig. 2 The initial data set clustering diagram

圖3 去除離群值聚類圖Fig. 3 The cluster diagram of removal of outliers

圖2、圖3具體體現由表1給出，表1給出了fDB指標、fDunn指標和fSilhouette指標。原始數據集k-means算法的fDB指標為0.442 5，去除離群值k-means算法的fDB值為0.281 5，去除離群值k-means算法的fDB值比原始數據集k-means算法的fDB值小，fDB值越小表明類簇內對象之間的距離越小，同時類簇間對象之間的距離越大，說明fDB指標的值越小越好，去除離群值k-means算法相比原始數據集k-means算法較好；fDunn指標和fSilhouette指標越大表明類簇對象之間的距離越大，且類簇內對象之間的距離越小，說明這兩種指標的值越大越好，原始數據集k-means算法的fDuun值為0.414 1，fSilhouette值為0.718 8，去除離群值k-means算法的fDuun值為0.606 9，fSilhouette值為0.820 8，去除離群值k-means算法相比原始數據集k-means算法較好。表1證明了人工生成的數據集去除離群值在再用k-means得到的聚類結果比直接使用k-means聚類算法還要好。

表1 人工產生的數據集聚類評價指標Table 1 Evaluation index of manually generated data cluster

3.2 University of California Irvine(UCI)數據集

為了證明所提出的算法有效性，選了UCI數據集中的Wine和Seeds兩個數據集來進行證明。表2給出了各個數據集的量，表3給出了Wine數據集使用k-means算法以及先使用局部密度離群點LOF檢測方法剔掉離群點，再使用k-means聚類結果的3種聚類評價指標，表4為Seeds數據集使用k-means算法以及先使用局部密度離群點LOF檢測方法剔掉離群點，再使用k-means聚類結果的三種聚類評價指標。

表2 數據集各個量Table 2 Each quantity of the data set

表3 Wine數據聚類結果的3種評價指標Table 3 Three evaluation indexes of Wine data clustering results

表4 Seeds數據聚類結果的3種評價指標Table 4 Three evaluation indicators for the clustering result of Seeds data

表3給出了Wine數據集的fDB指標、fDunn指標和fSilhouette指標。原始數據集k-means算法的fDB指標為1.468 1，去除離群值k-means算法的fDB值為1.196 8，去除離群值k-means算法的fDB值比原始數據集k-means算法的fDB值小，fDB值越小表明類簇內對象之間的距離越小，同時類簇間對象之間的距離越大，說明fDB指標的值越小越好，去除離群值k-means算法相比原始數據集k-means算法較好；fDunn指標和fSilhouette指標越大表明類簇對象之間的距離越大，且類簇內對象之間的距離越小，說明這兩種指標的值越大越好，原始數據集k-means算法的fDunn值為0.232 3，fSilhouette值為0.284 9，去除離群值k-means算法的fDunn值為0.336 7，fSilhouette值為0.335 2，去除離群值k-means算法相比原始數據集k-means算法較好。；表4為Seeds數據集聚類結果的fDB指標、fDunn指標和fSilhouette指標。原始數據集k-means算法的fDB指標為0.884 3，去除離群值k-means算法的fDB值為0.702 0，去除離群值k-means算法的fDB值比原始數據集k-means算法的fDB值小，fDB值越小表明類簇內對象之間的距離越小，同時類簇間對象之間的距離越大，說明fDB指標的值越小越好，去除離群值k-means算法相比原始數據集k-means算法較好；fDunn指標和fSilhouette指標越大表明類簇對象之間的距離越大，且類簇內對象之間的距離越小，說明這兩種指標的值越大越好，原始數據集k-means算法的fSilhouette值為0.471 9，去除離群值k-means算法的fSilhouette值為0.527 4，去除離群值k-means算法相比原始數據集k-means算法較好。在UCI數據集上驗證了去除離群值再使用k-means算法得到的聚類結果都有明顯的改善，得到的聚類較好。

4 局部密度離群值k-means算法在實際中的應用

新型冠狀病毒疫情對經濟以及人們的生活帶來了極大的影響。選取中國部分省、市、自治區(qū)數據集(安徽省、北京市、福建省、廣東省、廣西壯族自治區(qū)、江西省、貴州省、河北省、海南省、河南省、吉林省、黑龍江省、湖南省、江蘇省、遼寧省、內蒙古自治區(qū)、山東省、山西省、陜西省、四川省、天津市、云南省、浙江省、重慶市)，這24個省、市、自治區(qū)新型冠狀病毒肺炎疫情數據，數據來源于各個省、市、自治區(qū)的衛(wèi)生健康委員會官網，表5為2020年2月18日中國24個省、市、自治區(qū)新型冠狀病毒肺炎的確診人數。

表5 2020年2月18日中國24個省、市、自治區(qū)新型冠狀病毒肺炎確診人數Table 5 The number of confirmed COVID-19 cases in 24 provinces， municipalities and autonomous regions in China on 18 February 2020

表5數據集比較大，先用scale對數據進行標準化再聚類，使用k-means聚類以及先使用局部密度離群值LOF檢測方法去除離群值，再使用k-means聚類的3個評價指標如表6所示。

表6 24個省、市、自治區(qū)新型冠狀病毒肺炎數據集聚類評價指標Table 6 COVID-19 data cluster evaluation indicators in 24 provinces, mumicipalities and autonomous regions

表6給出了24個省市以及自治區(qū)新型冠狀病毒肺炎數據集聚類的fDB指標、fDunn指標和fSilhouette指標。原始數據集k-means算法的fDB指標為0.781 5，去除離群值k-means算法的fDB值為0.583 3，去除離群值k-means算法的fDB值比原始數據集k-means算法的fDB值小，fDB值越小表明類簇內對象之間的距離越小，同時類簇間對象之間的距離越大，說明fDB指標的值越小越好，去除離群值k-means算法相比原始數據集k-means算法較好；fDunn指標和fSilhouette指標越大表明類簇對象之間的距離越大，且類簇內對象之間的距離越小，說明這兩種指標的值越大越好，原始數據集k-means算法的fDunn值為0.432 1，fSilhouette值為0.553 7，去除離群值k-means算法的fDunn值為0.665 2，fSilhouette值為0.581 4，去除離群值k-means算法相比原始數據集k-means算法較好。證明了使用局部密度離群值檢測LOF方法對數據集剔除離群值之后再使用k-means算法得到的聚類結果較好，并且使用局部密度離群值檢測LOF方法能更好地幫助分析每個地區(qū)的新型冠狀病毒肺炎疫情情況，能讓每個地區(qū)政府更好地處理醫(yī)用物資的調配以及疫情防疫問題，更好降低經濟的損失。

5 結束語

基于局部密度離群點檢測k-means算法中，通過fDB指標、fDunn指標和fSilhouette3種評價指標進行聚類結果評價：

(1) 在人工產生的數據集中，通過3種評價指標得到去除離群值之后得到的聚類結果較好。

(2) 在UCI數據集中的Wine與Seeds數據集進行驗證，使用本文選用的3種評價指標進行評價，得到的聚類結果較好。

(3) 將離群值檢測k-means算法應用到新型冠狀病毒肺炎疫情數據分析中，得到較好的聚類結果，更好幫助決策者做決策。

(4) 未來將對任意數據集的聚類以及聚類的類簇中心的選擇進行研究。