類不平衡數據的卡方聚類算法研究

劉歡 胡德敏

摘 ?要： K-means型算法在處理類不平衡數據時趨向于形成大小相同的簇，是“均勻效應”。針對這一問題諸多研究者提出了不同的聚類算法，這些方法針對簇樣本數量不平衡特性，存在精度和效率問題。本文以卡方距離為基礎提出了一種類平衡數據的聚類算法，利用均值消除受簇均值水平影響的特性度量樣本相似性，解決類不平衡數據中“均勻效應”問題，給出了聚類目標函數，形成一種EM型聚類優化算法。在UCI實際數據集上進行了實驗，結果表明本文所提出的算法提高了類不平衡數據的聚類精度，降低了“均勻效應”對聚類結果的影響。

關鍵詞： 數據挖掘;類不平衡;卡方距離;聚類;均勻效應

中圖分類號： TP301 ? ?文獻標識碼： A ? ?DOI：10.3969/j.issn.1003-6970.2019.04.002

本文著錄格式：劉歡，胡德敏. 類不平衡數據的卡方聚類算法研究[J]. 軟件，2019，40（4）：0710

【Abstract】： The k-means algorithm tends to form clusters of the same size when processing class unbalanced data， which is the "uniform effect". To solve this problem， the researchers proposed different clustering algorithms， which aimed at the unbalanced characteristics of the number of cluster samples， and did not directly solve the "uniform effect" from the perspective of clustering objective function. In this paper， based on the chi-square distance， a kind of clustering algorithm for balanced data is proposed， which USES the mean value to eliminate the characteristics affected by the mean value of the cluster to measure the sample similarity， so as to solve the problem of "uniform effect" in the class unbalanced data. Experiments are carried out on the actual dataset of UCI. The results show that the algorithm proposed in this paper improves the clustering accuracy of class unbalanced data and reduces the influence of "uniform effect" on the clustering results.

【Key words】： Data mining; Class imbalance; Chi-square distance; Clustering; Uniform effect

0 ?引言

聚類分析已經廣泛的用于商務智能、圖像模式識別、生物學與安全等諸多領域。現如今的聚類算法大致可劃分為如下幾類[1，2]，基于劃分聚類算法、基于層次聚類算法、基于模糊聚類算法、基于密度聚類算法等。例如劃分算法是將數據對象集劃分成不重疊的子集（簇），使得每個數據恰在一個子集中[3]、層次聚類是對給定數據集進行層次分解，直到滿足相關條件為止。經典聚類算法能較好處理常規數據（例如球形數據），然而現實生活中業者面臨著更多復雜的數據，例如類不平衡數據。這類數據的一個典型特點是在數據集中不同簇的樣本數量有較大差異。（例如，在有兩個簇的數據集中一個簇樣本數量有5000個，另外一個簇的樣本數量有50個。）類不平衡數據的研究是當前數據挖掘領域一熱點[4，5]。

K-means作為經典的聚類算法[6]，其在對任意類不平衡數據集進行聚類分析時，將其劃分為2個簇，則兩個簇的樣本數量趨于相同，此為 K-means 算法的“均勻效應（uniform effect）”[7]。為解決類不平衡數據在聚類時產生的“均勻效應”問題，現研究者提出多種方法[8-11]，例如：基于樣本抽樣，即在聚類之前對數據集進行欠采樣或過采樣的處理，例如，HE H， GARCIA E A[8，9]等人提出的解決問題的方法即是在預處理后的數據上進行 K-means聚類的，但是該方法的過采樣是通過不斷復制少數類來使數據的規模不斷變大，由于此類方法使數據集中的樣本數量增加，從而導致計算開銷的增加、算法性能下降等問題。過采樣只是在數據集中抽取子集，從而容易導致缺失相關數據中潛在的價值信息;第二類方法在聚類中考慮不同簇的樣本量差異，例如，HARTIGAN JA， WONG MA等人[11]引入簇的樣本數量，提出了兩種改進基于迷糊聚類的目標函數的優化方案，以及借助多代表點[10]以此區分數據集中的不同的密度區域，但是該方法在低維數據和高維數據，算法的執行效率較低;針對上述方法在解決類不平衡數據的效率和精度問題，提出一種基于卡方距離的聚類算法從聚類目標函數的角度出發，解決“均勻效應”問題的方法，卡方距離在在度量相似性時候引入了樣本的均值，而均值能表征樣本的分布情況。本文針對類不平衡數據的“均勻效應”問題，用卡方距離度量數據離散程度，根據相似度度量給出了聚類目標函數（基礎），并給出一種EM型聚類優化算法，最后通過UCI實際數據集驗證，算法精度提高36%～68%。

1 ?K-means算法的“均勻效應”

經典的K-means算法是一種劃分型聚類算法，其優化目標定義為：

K-means常通過EM算法[12]進行優化，具體算法過程如下：1、首先輸入樣本;2、再選擇初始的K個簇中心點，3、標記距離簇中心最近的簇;4、將樣本劃分至距離最小的簇;5、更新簇中心點的坐標，算法重復上述3-5步驟，直到滿足停止條件算法終止，得到局部最優解的數據集簇劃分。

文獻[7]分析K-means算法的“均勻效應”問題以及其產生的原因。如下圖1、圖2示例所示：圖中兩個簇的數量以及密度均有較大的差異。

通過K-means算法對上圖數據集進行聚類得到的聚類結果如圖2所示，由此可知兩個簇的樣本數量以及密度趨于相同，此現象即為K-means型算法的“均勻效應”問題。

針對均勻效應，當前的研究者給出了不同的方法，例如，KUMAR N S， RAO K N[9]等人提出以兩個簇的數據為基礎，利用特征選擇將樣本數較多的簇中部分樣本刪除掉，然后將兩個簇形成平衡數據集，最后利用K-means對處理后平衡數據集進行聚類的;LIANG J， BAI L[13]等人提出通過樣本集中進行采樣，然后利用K-means對樣本集進行聚類，給出聚類后樣本簇標號，生成相似矩陣，經過指定次數的反復處理后利用譜聚類對相似矩陣進行聚類;JAIN A K[11]指出分別以模糊c均值和模糊c-har?monic均值算法為基礎，利用簇中數據的隸屬度之和表示簇中樣本數量，然后在聚類目標函數中引入簇的樣本數量，最后給出了根據目標優化函數求解定義的算法。

綜上所述，上述研究者的算法會存在一定程度的效率和精度問題。綜上可知，上述研究者的算法多側重在解決樣本的不平衡性上，并沒有從聚類目標函數出發解決“均勻效應問題”，而聚類算法的一個重要基礎是聚類目標函數。本文以此為切入點，本文分析了ALOISE D， DESHPANDE A [14]等人在聚類研究時，利用卡方距離進行相似性度量。卡方距離在度量相似性時候引入了樣本的均值，均值能表征樣本的分布情況，而類不平衡數據的一個特點是不同簇樣本數量有較大差異。本文以卡方距離為基礎定義了聚類目標函數，新的目標函數中通過引入樣本的均值以消除均勻效應的影響，以此提高類不平衡數據聚類精度。

2 ?基于卡方距離的聚類算法

2.1 ?基于卡方距離的相似度度量

相關研究表明，卡方距離度量能夠度量數據相似性[14]，本節引入卡方距離度量類不平衡數據中相似性，以此降低“均勻效應”對聚類的影響，卡方距離如式（3）所示。

式（3）在歐式距離的基礎上引入了樣本的均值度量樣本v_ij與v_j的相似性，而v_j能表征樣本的分布信息，在度量樣本與vj的相似性時候通過引入v_j消除樣本不平衡性帶來的影響。在劃分型聚類算法中常用均值作為簇的代表點，（3）式可以看作是樣本點與簇代表點的相異度，通過引入v_j消除簇均值的影響，這才不平衡數據中可以消除樣本不平衡性帶來的影響。基于卡方距離的相似度度量公式如式（4）所示。

公式（4）中以簇中均值作為簇的代表點。基于樣本各特征之間相互獨立假設，（4）式對各特征分開算。

在本文中選取圖1的中點m，并與基于歐式距離的相似度度量公式進行比較，以此來解釋基于卡方距離的相似度度量公式的樣本點與不同簇之間的相似度。

表1為兩種不同度量公式的計算結果。傳統的K-Means聚類用歐氏距離，計算結果為||dc1||與||dc2||，樣本點d與簇中心c1的相異度小與d與c2的相異度，d被劃入到c1所代表的簇中;L（d，c1）與L（d，c2）為本文度量公式計算結果，表1中L（d，c2）小與L（d，c1），d將劃入第二個簇中。樣本點d的真實的簇標簽是第二個類，表明本文提出的相異度公式能更準確的劃分d點。

2.2 ?聚類算法

通過公式（4）提出的相似度度量公式 ，給出類不平衡數據的聚類優化目標函數如下公式（5）所示。

本文算法是一種劃分型算法，劃分型算法實質是聚類目標函數最佳值求解的過程，因此本文的目標是最小化公式（5）。公式（5）引入了卡方距離，但仍然是一種歐式距離的求解，這種聚類算法的求解是NP難問題[15]，這使得其最優值的求解是困難問題，針對這類問題研究者常用的方法是求其局部最優值。因此，本文采用了傳統的迭代法來求解目標函數的局部最優值。算法過程描述如下：

輸入：數據集DB，簇數目K;

輸出：簇劃分C。

第一步：初始化操作，隨機選取簇中心點;

第二步：利用公式（3）進行簇的更新;

第三步：利用公式（4）更新簇中心點;

第四步：迭代次數增加并判斷中心點是否變化，如果中心未變化或者迭代次數大于閾值算法停止否則返回第二步。

2.3 ?算法分析

傳統的K-Means算法每次迭代的時間復雜度為O（KND），其中k為簇數目，N為樣本數量，D為樣本維度，本文算法在結構上與k-means算法類似，假設算法經過P次迭代停止，則基于卡方距離的聚類算法時間復雜度為O（KNDP）。因為算法在每步迭代的過程中都是在求最小的歐式距離劃分，因此聚類目標函數值降低每次迭代都在降低，此外目標函數存在下界，因此在P次有限的迭代下基于卡方距離的聚類算法是收斂的。

2.4 ?實驗分析

本研究從UCI Machine Learning Repository （http：//Archive.ics.uci.edu/ml/datasets.html）數據集中選用了4個真實數據，分別是colic、ionosphere、hepatitis、sick，相關信息如表2所示。