姚家旸 劉暢 李健行

在本文中，定義了兩個新的聚類有效性指數(shù)，通過組合類內(nèi)緊湊性和考慮近鄰的類間分離來確定聚類的數(shù)量。本文的緊湊性度量不僅考慮了對象與類中心之間的距離，還考慮了類中對象的數(shù)量和類中對象的分布，可以更好地測量類中對象的緊湊性。分離度量考慮了對象和近鄰的分布以及類中對象的數(shù)量，它們可以測量類之間的分離。本文還分析了類中對象的形成，并研究了傳統(tǒng)聚類算法中對象的局限性，這種算法只能屬于唯一類。通過三個決策思想，進(jìn)一步區(qū)分三支決策思想對類中的對象，得到豐富而有針對性的信息。因此，本文提出了一種自動三分支決策聚類方法。

1 引言

傳統(tǒng)的聚類算法是二支決策聚類的結(jié)果，即對象屬于某一類或不屬于某一類，不能很好地處理具有不確定場景的聚類任務(wù)，如社交網(wǎng)絡(luò)、生物信息處理和投資管理。這三個決策是近年來提出的一種基于人類認(rèn)知的決策模型。主要思想是將整體劃分為三個部分，并對未使用的部分采用不同的策略和方法。這三種決策思路為不確定性聚類提供了新的思路和策略。為此，我們在聚類分析中引入了三種決策思想，并提出了三種決策聚類方法來處理具有不確定情景的聚類任務(wù)。實際上，二支決策聚類是三分支聚類的特例。三個決策集群中的對象和類之間的關(guān)系不再屬于該類，或者不屬于該類，但是確定一個對象是否屬于一個類。

2 自動三支決策聚類算法描述

對象和類之間的關(guān)系

考察對象x和類C，，Xj∈Neigq（X）。其中對象x和類C，存在如下關(guān)系：

（1）如果，Xj∈C那么X∈CM;

（2）如果，那么X∈CR。

在聚類分析中，我們可以從兩個方面考慮一個類的組成：一方面，考慮類和類之間的關(guān)系，如果類中的對象只與一個類緊密相關(guān)，則對象是確定屬于這個類，屬于L類域：如果一個對象和多個類之間的關(guān)系在一定程度上緊密，那么這個對象可能同時屬于這些類，是類中的一個非典型對象，并且應(yīng)該同時屬于類中的M域。另一方面，考慮到類中對象之間的關(guān)系，類中的大多數(shù)對象密切相關(guān)，形成類的核心部分，屬于類的L域，少部分對象和類中大部分對象之間的聯(lián)系相對較弱，是類的關(guān)鍵部分，屬于該類的M域。

綜合以上考慮，受我們在文獻(xiàn)中提出的差值排序法的啟發(fā)，文中采用類中對象到類中心距離的差值，對類中對象進(jìn)一步區(qū)分?？疾閷ο髕和類C，依次計算對象到類中心的距離，并按數(shù)值從小到大排列，得到呈升序排列的序列d（X1，V）、d（X2，V）、d（X3，V）、d（Xn-1，V）、…、d（Xn，V）。然后，依次計算這些距離的差值d（X1，V）- d（X2，V）、d（X2，V）- d（X3，V）、、d（Xn-1，V）- d（Xn，V），能夠找到第一個距離差值最大的對象對，Xi-1和Xi，并把對象X1，X2…Xi-1劃分到類C的L域，把x和以后的對象劃分到類C的M域中。

3 近鄰q的確定

選擇合適的近鄰q值很關(guān)鍵。通過上文的分析可知，Ci和Cm還可以細(xì)分為和個部分。考察Ci中每個對象的個近鄰和Cm的關(guān)系，得到Ci和Cm之間聯(lián)系的緊密程度;考察Cm中每個對象的個近鄰和Ci的關(guān)系，得到Ci和Cm之間聯(lián)系的緊密程度。另外，考慮類Ci和Cm中對象數(shù)目之間的關(guān)系，防止類中數(shù)目多的對象的過度影響，類中數(shù)目少的類，近鄰q的值取兩者之間的最小值，即：

Q=min

為了防止得到不符合事實的聚類結(jié)果，近鄰q的值取和中的最小值。需要指出，文中三支決策聚類算法，不采用統(tǒng)一的q值，而是由每兩個類中數(shù)目的多少，來確定類之間q值的選取，這樣得到的結(jié)果比采取全局統(tǒng)一的q值更合理。

3.1時間復(fù)雜度分析

因此，分離性指數(shù)計算的時間復(fù)雜度近似為O（kNlogN+k2q2）。所以，一次有效性指數(shù)CVIDN的計算復(fù)雜度近似為O（kNlongN+k2q2）。

為了尋找最佳的聚類數(shù)目，聚類數(shù)目K從2遞增至，計算的復(fù)雜度O（2NT+，…，+kNT， …，+ NT），即O（N2T）。每一次聚類數(shù)目K都會計算CVIDN的值，計算復(fù)雜度近似為

O（（2NlogN+22q2）+（3NlogN+32q2）），

…，+（ NlogN+Nq2）。即O（N2llogN+q2N）。綜上所述，尋找最佳聚類數(shù)目時間的復(fù)雜度為

O（N2logN+N2T+q2N））

3.2算法描述：

輸入：數(shù)據(jù)集U、近鄰數(shù)q。

輸出：

Step1：初始化為k=2。

Step2：隨機選取k個聚類中心V1，V2，…VK。

Step3：對于類中每個對象Xi，計算到每個聚類中心VK的距離，劃分到距離最小的類。

Step4：不斷更新聚類中心V=。

Step5：如果聚類中心不發(fā)生變化，轉(zhuǎn)自Step6;否則轉(zhuǎn)至Step3。

Step6：計算CVI（CS），如果，那么K=K+1， 轉(zhuǎn)至Step2; 否則轉(zhuǎn)至Step7。

Step7：kopt=argminCVI（CS）。

Step8：考察對象x和類C、、.那么， 那么。

Step9：對于類中剩余非M域中的對象，根據(jù)排序法，找到第一個距離差值最大的對象，Xi-1和Xi，把Xi及其后的對象劃分到CM。

Step10：算法結(jié)束，會輸出結(jié)果：

。

3.3算法時間復(fù)雜度的分析

本小節(jié)主要分析聚類數(shù)目的時間，以及把二支決策聚類轉(zhuǎn)換為三支決策聚類的時間。

4 實驗結(jié)果分析

4.1類間近鄰q的確定

三支決策聚類算法在考慮不同類中對象的關(guān)系時，需要確定近鄰q的值，不同的q值會得到不同的聚類結(jié)果。文中給出了一種自動確定近鄰q的方法，結(jié)果如圖：

5.結(jié)論

實驗結(jié)果表明，三支決策聚類算法不僅可以找到類之間的重疊部分，而且可以進(jìn)一步細(xì)分類中的對象，獲得更豐富的信息。本文提出的三支決策聚類算法與比較算法相比，與傳統(tǒng)的二支決策聚類算法相比，能夠有效提高聚類精度。

指導(dǎo)老師：白斌

（作者單位：華北理工大學(xué)）