自動(dòng)三支決策聚類研究及拓展

姚家旸 劉暢 李健行

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

1 引言

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

2 自動(dòng)三支決策聚類算法描述

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

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

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

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

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

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

3 近鄰q的確定

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

Q=min

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

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

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

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

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

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

O（N2logN+N2T+q2N））

3.2算法描述：

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

輸出：

Step1：初始化為k=2。

Step2：隨機(jī)選取k個(gè)聚類中心V1，V2，…VK。

Step3：對(duì)于類中每個(gè)對(duì)象Xi，計(jì)算到每個(gè)聚類中心VK的距離，劃分到距離最小的類。

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

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

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

Step7：kopt=argminCVI（CS）。

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

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

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

。

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

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

4 實(shí)驗(yàn)結(jié)果分析

4.1類間近鄰q的確定

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

5.結(jié)論

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

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

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