自動三支決策聚類研究及拓展

姚家旸 劉暢 李健行

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

1 引言

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

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

對象和類之間的關系

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

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

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

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

綜合以上考慮，受我們在文獻中提出的差值排序法的啟發，文中采用類中對象到類中心距離的差值，對類中對象進一步區分。考查對象x和類C，依次計算對象到類中心的距離，并按數值從小到大排列，得到呈升序排列的序列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值很關鍵。通過上文的分析可知，Ci和Cm還可以細分為和個部分。考察Ci中每個對象的個近鄰和Cm的關系，得到Ci和Cm之間聯系的緊密程度;考察Cm中每個對象的個近鄰和Ci的關系，得到Ci和Cm之間聯系的緊密程度。另外，考慮類Ci和Cm中對象數目之間的關系，防止類中數目多的對象的過度影響，類中數目少的類，近鄰q的值取兩者之間的最小值，即：

Q=min

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

3.1時間復雜度分析

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

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

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

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

O（N2logN+N2T+q2N））

3.2算法描述：

輸入：數據集U、近鄰數q。

輸出：

Step1：初始化為k=2。

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

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

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

Step5：如果聚類中心不發生變化，轉自Step6;否則轉至Step3。

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

Step7：kopt=argminCVI（CS）。

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

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

Step10：算法結束，會輸出結果：

。

3.3算法時間復雜度的分析

本小節主要分析聚類數目的時間，以及把二支決策聚類轉換為三支決策聚類的時間。

4 實驗結果分析

4.1類間近鄰q的確定

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

5.結論

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

指導老師：白斌

（作者單位：華北理工大學）