帶有周期性名義變量的混合型數據聚類分析

肖枝洪，顏 偉

(重慶理工大學 理學院， 重慶 400054)

聚類分析是研究事物分類或分組的基本方法。聚類分析的目的是把要分類的對象按一定的規則分成若干類，屬于同一類的對象在某種意義上傾向于彼此相似，而屬于不同類的對象傾向于彼此不相似，從而使人們易于從紛繁復雜的數據中發現有價值的規律。聚類算法被廣泛應用于客戶細分、圖像修復、蛋白質序列預測、模式識別等領域[1-4]。目前，國內外對單純的數值型變量的觀測進行聚類的算法[5-8]和單純的名義變量(或屬性變量)的觀測進行聚類的算法[9-12]已經較為成熟。然而在實際問題中，如金融經濟、生命科學、航空航天、汽車制造和移動通信等領域，存在大量的由數值型變量觀測和由名義變量(或屬性變量)觀測組成的混合型數據，且有的名義變量的觀測還具有某種周期性。盡管混合型數據的分類具有較高的實際應用價值，但針對此種混合型數據的相似性刻畫和以此為依據進行聚類分析的方法仍不成熟。

針對上述研究中存在的問題，對帶有周期性名義變量的混合型數據中的周期性名義變量觀測值進行合理量化，以改進周期性名義變量的觀測值之間相似性度量的不足；給出周期性名義變量的觀測值之間的距離公式，與數值型變量觀測之間的距離公式相結合，提出具有周期性名義變量的混合型數據觀測之間的新距離公式來度量樣品間的相似性，并以此為依據對該類數據進行分類。

1 樣品間距離公式以及類間距離公式

1.1 樣品間距離公式

在聚類時，假設有n個樣品，每個樣品都有p個指標，xij表示為第i個樣品的第j個指標的觀測值。那么以xij為元素的觀測數據矩陣X為：

根據X可以計算樣品之間的相似性統計量，進而將X的所有樣品進行分類。

1.1.1數值型變量觀測之間的距離

假設X為單純的數值型變量觀測所構成的觀測數據矩陣，為了不發生混淆，這里將其記為N,樣本量為n，指標(特征)個數為p。任取數據集N中的2個樣品Xi=(xi1,xi2,…,xip)和Xj=(xj1,xj2,…,xjp)，其距離定義為

(1)

1.1.2屬性變量觀測之間的距離

假設觀測數據矩陣X僅由單純的屬性變量或名義變量的觀測構成，記為C，其樣本量為n，指標(特征)個數為q。任取數據集C中的2個樣品Xi=(xi1,xi2,…,xiq)和Xj=(xj1,xj2,…,xjq)。此時用連續型數據觀測之間的距離公式來計算屬性變量觀測之間的距離已經失效，目前大多學者采用漢明距離進行計算，見式(2)。

(2)

也有研究者引入李克特量表對屬性數據進行量化，見式(3)。

(3)

依據式(3)得到初始距離矩陣為：

如前所述，按照式(2)或式(3)來計算周期性名義變量的觀測值兩兩之間的距離是不合理的，故在此引入新的方法對周期性名義變量的觀測值進行合理量化，并在此基礎上提出周期性名義變量的觀測值兩兩之間的距離公式，其具體做法如下：

假設周期性名義變量Y有k種不同的水平，分別為Y1,Y2,…,Yk，對應將復平面上的單位圓k等分，單位圓上對應點的取值分別為Y1,Y2,…,Yk，如圖1所示。

圖1 周期性名義變量的量化示意圖

基于圖1，周期性名義變量每種取值可以量化為：

(4)

(5)

初始距離矩陣為：

D(2)是一個主對角線元素為0，其余元素為1的對稱矩陣。

若按照式(3)將周期性名義變量Y的k種不同取值Y1,Y2,…,Yk依次量化為1,2,3,…,k，那么按照距離公式計算可得觀測之間的距離為dij=|i-j|,其中i=1,2,…,k,j=1,2,…,k。進而可得周期性名義變量觀測之間的距離矩陣為：

其中m=1,2,…,k,n=1,2,…,k，進而可得周期性名義變量觀測之間的距離矩陣為：

表1 依據式(5)所得觀測之間的距離矩陣

從表1可以看出，d13、d24、d35、d46的值均為1.732。若按照式(2)計算，它們之間的距離都為1。這是因為式(2)采用文獻[17]中的if-else語句來計算觀測之間的距離，例如，if(Y1=Y2) thend12=0,elsed12=1。該方法只對屬性變量的觀測值是否相同做判斷，忽略屬性變量的不同觀測值之間相似性的差異，用來計算具有周期性的名義變量觀測之間的距離并不合理。表1中，d13和d15的值均為1.732，然而按照式(3)來計算，d13=2，d15=4。這是因為式(3)所述方法將Y1,Y2,…,Y5,Y6分別量化為1,2,3,4,5,6，故用來計算具有周期性的名義變量觀測值之間的距離是不合理的。

1.1.3混合型數據樣品之間的距離

假設觀測數據矩陣X中既有由數值型變量得到的觀測,又有由屬性變量得到的觀測，指標個數為v，其中數值型指標個數為p，屬性指標個數為q。任取X中的2個樣品Xi=(xi1,…,xip,xi(p+1),…,xi(p+q))和Xj=(xj1,…,xjp,xj(p+1),…,xj(p+q))，結合距離式(1)、(2)、(3)和(5)，定義出具有周期性名義變量的混合型數據觀測的距離計算公式，它們之間的距離如下：

(6)

(7)

(8)

基于式(7)，初始距離矩陣為

基于式(8)，初始距離矩陣為

說明2在距離式(6)—(8)中，假設取ω=0，則式(6)—(8)均為式(1)。在距離公式(6)中，取ω=1，則式(6)為式(2)；距離公式(7)中，取ω=1，則式(7)為式(3)；距離公式(8)中，取ω=1，則式(8)為式(5)。式(6)—(8)是將數值型變量觀測之間的距離公式(1)和屬性變量觀測之間的距離公式(2)、(3)和(5)進行統一，在ω取值為0或1時，混合型數據樣品間的距離公式轉變為純數值型變量觀測之間的距離公式或純屬性變量觀測之間的距離公式。

1.2 類合并準則

對混合型數據的觀測應用樣品間距離公式(6)—(8)，可得初始距離矩陣D0，進而通過類間距離公式進行類間合并。在類合并過程中，確定類間距離有最短距離法、最長距離法、類平均法、重心法等。其中，最短距離法和最長距離法僅用距離最短和距離最長的2個樣品之間的距離來代表類間距離，由于不能充分利用樣品之間的信息，類間距離容易被異常值嚴重扭曲。考慮到物理學中物體可以其重心來指代，故將類與類之間的距離定義為兩類重心之間的距離。重心法在處理異常值方面相比最短距離法和最長距離法更加穩健，不容易被異常值干擾，但如何計算混合型數據類的重心是復雜和困難的。

相較于最短距離法、最長距離法和重心法，類平均法能較好利用所有樣品之間的信息。由于避免了類重心的計算，類平均法通常被認為是一種類間距離公式。本文中主要以類平均法為依據來驗證周期性名義變量觀測的量化方法和新定義的距離公式的合理性。

采用do1o2表示樣品o1與樣品o2之間的距離，用C1,C2,…表示類。定義類CP與類Cq之間的距離Dpq為類CP中各樣品與類Cq中各樣品兩兩之間距離平方的均值再開方，即

(9)

通過式(9)可以證明：在某一步將類CP與類Cq合成新的一類Cr后，Cr與某類Ck之間的距離Drk為

式中：nr和nk分別為類Cr和類Ck的樣本量，且nr=np+nq。

說明3k-prototypes算法思想首先是從混合型數據集中隨機挑選k個觀測作為初始凝聚點，根據距離公式計算各個觀測與初始凝聚點的距離，即距離矩陣。按照距離最短原則將所有的觀測劃分到相應的類中并更新每個類的類中心作為新的凝聚點，然后重新計算距離矩陣，對觀測進行劃分并更新每個類的類中心，直到誤差函數達到最小。但算法迭代過程中如何更新新的類中心始終是一個難題，即數據集中的屬性數據的類中心如何確定。系統聚類法可避免類中心更新的問題。由于式(2)本質上并沒有將名義變量的觀測進行量化，因而不能采用k-prototypes等算法進行分類，本文采用系統聚類法。

2 聚類算法

2.1 算法流程

根據式(6)—(9)編寫算法。算法具體步驟為：

步驟3根據類間距離公式(9),計算新類Cr與其他類Ck之間的距離Drk，即

2.2 算法偽代碼

算法偽代碼如下：

輸入：混合型數據集X;

輸出：聚類結果;

Step1：for iin1：nrow(X);

Step2：forjin1：nrow(X);

Step3：sqrt(sum((X[i,]-X[j,])2));

Step4：calculate initial distance matrixD0;

Step5：end for;

Step6：end for;

Step7：while(dim(D0)>1);

Step8：forsin2：nrow(D0);

Step9：fortin1：(r-1);

Step10：if(D0[s,t]==min(D0));

Step11：doCr={Cs,Ct};

Step12：end for;

Step13：end for;

Step14：forkin1：nrow(D0);

Step15：calculate the distance ofCrandCk;

Step16：add newDrkto initial distance matrixD0;

Step17：delete rowsandt,delete colsandt;

Step18：gain transition matrixD1;

Step19：doD0=D1;

Step20：end for;

Step21：if(dim(D0)==1) break;

Step22：end;

3 實驗

3.1 實驗環境與數據

為了驗證距離公式(8)的有效性，用式(8)在數據集Algae和Absence上進行驗證，并與距離公式(1)、(6)和(7)的實驗結果進行比較分析。采用R3.5.1數據分析軟件編程進行實驗，實驗數據為帶有周期性名義變量的混合型數據，均來源于UCI機器學習數據庫。數據集描述見表2。

表2 數據集描述

采用Accuracy值、G-mean值作為聚類效果的評價指標,其中T1、T2、T3、T4和T5分別表示聚類后類C1、C2、C3、C4和C5中正確分類的樣品數量，F1、F2、F3、F4和F5分別表示聚類后類C1、C2、C3、C4和C5中錯誤分類的樣品數量，評價指標Accuracy和G-mean分別定義為：

(10)

(11)

3.2 Algae數據集實驗結果

Algae數據集的樣本量為122，變量(指標)數為11,其中數值型特征數為8，屬性特征數為3。數據集共分為5類，各個類的實際樣本量分別為28、21、25、23、25。以式(1)、式(6)、式(7)和距離公式(8)為依據進行分類，得到分類后的混淆矩陣如表3所示。依據各距離公式分類的Accuracy值(準確率)、G-mean值(平均準確率)、Time(s)(算法運行時間)和O(T(n))(算法時間復雜度)見表4。

表3 依據各距離公式分類后的混淆矩陣

表4 依據各距離公式分類的準確率

3.3 Absence數據集實驗結果

Absence數據集的樣本量為96，變量(指標)數為10,其中數值型變量數為5，屬性變量數為5。數據集共分為5類，各個類的實際樣本量分別為23、24、13、26、10。以式(1)、式(6)、式(7)和本文新的距離公式(8)為依據進行分類，得到分類后的混淆矩陣如表5所示。依據各距離公式分類得到的Accuracy值、G-mean值、Time(s)(算法運行時間)和O(T(n))(算法時間復雜度)見表6。

表5 依據各距離公式分類后的混淆矩陣

表6 依據各距離公式分類的準確率

3.4 實驗結果對比分析

為了更直觀地比較以式(1)、式(6)、式(7)和距離公式(8)為依據得到的聚類效果，直方圖2顯示了各距離公式分類的準確率。

圖2 各距離公式分類的準確率直方圖

從圖2(a)和圖2(b)可以看出，依據距離公式(8)在數據集Algae和Absence上進行分類得到的Accuracy值和G-mean值均優于采用式(1)、式(6)和式(7)時,驗證了距離公式(8)的有效性。這種有效性來源于對混合型數據中的周期性名義變量的觀測值進行合理量化，并定義出周期性名義變量的觀測值之間的距離公式。另外，根據式(1)在數據集Algae和Absence上分別進行分類得到的Accuracy值和G-mean值均低于其他3種距離公式的Accuracy值和G-mean值。這是因為根據式(1)對數據集進行分類時只用到了混合數據中的數值型變量數據，并沒有考慮屬性變量數據，對數據集的信息利用度低。這也意味著數據集中的屬性變量在聚類中重要程度高，對聚類結果有較大的影響。比較式(6)和式(8)在2個數據集上進行分類得到的Accuracy值和G-mean值可以發現，根據式(8)進行分類得到的Accuracy值和G-mean值均高于根據式(6)進行分類得到的Accuracy值和G-mean值。比較式(7)與式(8)在2個數據集上進行分類分別得到的Accuracy值和G-mean值可以發現，根據式(8)進行分類得到的Accuracy值和G-mean值高于根據式(7)進行分類得到的Accuracy值和G-mean值，這也說明將式(2)和式(3)用于計算周期性名義變量觀測之間的距離是不合理的。

綜上，基于新的距離公式(8)得到的聚類精度優于其他3種距離公式，驗證了對周期性名義變量的觀測值采用式(4)量化的合理性和新的距離公式(8)的有效性。

4 結論

對帶有周期性名義變量的混合型數據中的周期性名義變量的觀測值進行合理量化，以改進周期性名義變量的觀測值之間相似性度量的不足。給出周期性名義變量的觀測值之間的新的距離公式，有效地解決了該問題，并以此為依據對具有周期性名義變量的混合數據進行分類。各距離公式的實驗結果表明所提出的新的距離公式(8)對混合型數據分類有較明顯的優勢。

新算法在計算海量混合型數據時存在運算速度過慢的問題，因此，研究適用于海量混合型數據的動態聚類法中新類的類中心計算，使算法更具普適性是下一步研究的方向。