劉歡 胡德敏

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

關(guān)鍵詞： 數(shù)據(jù)挖掘;類不平衡;卡方距離;聚類;均勻效應

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

本文著錄格式：劉歡，胡德敏. 類不平衡數(shù)據(jù)的卡方聚類算法研究[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 ?引言

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

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

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

經(jīng)典的K-means算法是一種劃分型聚類算法，其優(yōu)化目標定義為：

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

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

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

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

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

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

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

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

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

公式（4）中以簇中均值作為簇的代表點?；跇颖靖魈卣髦g相互獨立假設(shè)，（4）式對各特征分開算。

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

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

2.2 ?聚類算法

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

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

輸入：數(shù)據(jù)集DB，簇數(shù)目K;

輸出：簇劃分C。

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

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

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

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

2.3 ?算法分析

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

2.4 ?實驗分析

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