摘  要： 針對K-Modes算法的不足，提出了一種基于信任值的分類屬性聚類算法TrustCCluster，該算法不需預(yù)先給定聚類個數(shù)，聚類結(jié)果穩(wěn)定且不依賴于初始值的選取。在真實數(shù)據(jù)上驗證了TrustCCluster聚類算法，并與K-Modes和P-Modes算法進行了對比，實驗結(jié)果表明TrustCCluster算法是有效、可行的。
關(guān)鍵詞： 信任值；聚類；K-Modes算法；P-Modes算法

    聚類分析是一種非常重要的數(shù)據(jù)挖掘技術(shù),已經(jīng)被廣泛應(yīng)用于網(wǎng)絡(luò)入侵檢測、模式識別、圖像處理、空間數(shù)據(jù)分析等領(lǐng)域。傳統(tǒng)聚類算法可以分為基于劃分的方法(如K-Means)[1]、基于層次的方法(如AGNES)[2]、基于密度的方法(如DBSCAN)[3]、基于網(wǎng)格的方法(如STING)[4]、基于模型的方法(如SOM)[5]等。
    K-Means算法是一種基于劃分的典型算法，具有描述容易、實現(xiàn)簡單且快速等優(yōu)點。但K-Means算法只能處理數(shù)值屬性。為克服這一局限，Huang等人提出了一種適合于處理分類屬性數(shù)據(jù)的K-Modes算法[6-7]。該算法對于每個分類屬性采用取值頻度最大的屬性值——模(mode)來表示類的對應(yīng)“中心”，但這種表示難以準確反映類中對象的取值情況,導(dǎo)致距離計算不準確,并且當某個屬性取值頻度最大的屬性值多于一個時，mode值不唯一。P-Modes算法[8]基于粗糙集理論，提出了一種新的距離度量方法，該距離度量在度量同一分類屬性下兩個屬性值之間的差異時,克服了簡單0-1匹配差異法的不足，既考慮了它們本身的異同，又考慮了其他相關(guān)分類屬性對它們的區(qū)分性。
    K-Modes、P-Modes算法都是在K-Means算法基礎(chǔ)上產(chǎn)生的一種針對分類屬性的距離度量方法，和K-Means算法一樣存在以下幾點不足：(1)需要預(yù)先給定聚類個數(shù)K；(2)算法對初始值的選取依賴性極大；(3)算法容易陷入局部最優(yōu)解。針對以上算法的不足，結(jié)合P-Modes的度量方法本文提出了一種基于信任值的分類屬性聚類算法TrustCCluster，該算法無需預(yù)先給定聚類個數(shù)，聚類結(jié)果穩(wěn)定，不依賴于初始值的選取，具有更高的聚類精度。


1.2 算法描述
    TrustCCluster算法具體步驟如下：
    (1)計算信任值
    所有數(shù)據(jù)點信任值初始值為0，遍歷數(shù)據(jù)集中所有數(shù)據(jù)點，若任意兩個數(shù)據(jù)點xi、xj(1≤i，j≤n)的距離d(xi，xj)<半徑閥值R，則xi、xj的信任值都加1，否則不變。
    (2)按信任值大小對所有數(shù)據(jù)點進行降序排序
    (3)聚類形成簇
    ①i=1(i為數(shù)據(jù)點的序號)；
    ②若xi未被訪問過，則xi作為新生成簇Cluster的中心,否則轉(zhuǎn)步驟⑥；
    ③j=i；
    ④如果d(xi，xj)<R且xj未被訪問過，則將xj加到簇Cluster中并將xj標記為已訪問過；
    ⑤j加1，若j≤n，轉(zhuǎn)步驟④；
    ⑥i加1，若i≤n，轉(zhuǎn)步驟②；
    ⑦結(jié)束。
    如圖1所示，在半徑閥值為R時，形成了3個簇，簇1的中心是信任值為4的點，一共包含5個點，簇2中心是信任值為3的點，包含3個點（不包括相交部分的點），簇3只包含1個點。
    (4)合并簇
    假設(shè)步驟(3)中，聚類形成M個簇。對于生成的M個簇，如果任意兩個簇Clusteri、Clusterj的共享信任值Share≥(Clusteri.sonNum+Clusterj.sonNum)×Q，sonNum為簇的成員數(shù)即簇包含的數(shù)據(jù)點數(shù)，Q為給定的比例閾值，0<Q≤1，則這兩個簇合并形成新的簇。可知簇合并關(guān)系R’是自反、對稱、傳遞的，最終形成的簇是關(guān)系R’對M個簇的一個等價劃分。
    如圖1所示，如果Q≤1/（5+3）=0.125，則簇1和簇2會合并成一個新的簇。
    (5)輸出聚類結(jié)果
    算法代碼如下：
    //Step 1計算信任值
    for(i=1；i<n；i++)
        for(j=i+1；j≤n；j++)
        {
            if(d(xi，xj)<R)
            {
                xi.trust++；
                xj.trust++；
            }
        }
    //Step 2按信任值排序
        sort(dataSet)；
    //Step 3聚類形成簇
    for(i=1；i≤n；i++)
    {
        if(visit[i] == false)
        {
            for(j=i；j≤n；j++)
        {  //找出生成簇的成員
            //判斷xj和簇clusterNum中心的距離是否<R
            if(!visit[j]&& d(clusterNum,xj)<R)
            {
                Cluster[clusterNum].sonNum++；
                visit[j]=true；
            }
        visit[i] = true;
    }
   }
}
    // Step 4合并簇
for(i=1; i≤clusterNum; i++)
    for(j=i+1; j≤clusterNum;j++)
{    //Matrix[M][M]為關(guān)聯(lián)矩陣，所有元素初始值為0
    if(Share>=(Cluster[i].sonNum+ Cluster[j].sonNum)*Q)
        {//共享信任值Share≥閥值，則關(guān)聯(lián)矩陣的項為1
    Matrix[i][j]=1；
    Matrix[j][i]=1；
   }
}
DFSMergeCluster();//DFS搜索求無向圖連通分量，
即進行簇合并
1.3 算法分析

    (1)TrustCCluster算法需要設(shè)定兩個參數(shù)：半徑閾值R和比例閾值Q。雖然TrustCCluster算法比K-Modes算法多了一個參數(shù)，卻可以在預(yù)先不知道聚類個數(shù)K的情況下進行聚類。
    (2)算法求出所有數(shù)據(jù)的信任值并排序，參數(shù)確定后，聚類結(jié)果也就確定，與初始數(shù)據(jù)點的選取順序無關(guān)。
    (3)信任值越大，表明數(shù)據(jù)點中心作用越大。算法求出所有數(shù)據(jù)的信任值并按信任值從大到小進行排序，聚類結(jié)果具有全局性。
    (4)算法的步驟(3)中只能發(fā)現(xiàn)一些近似球形的小簇，但在步驟(4)中進行的簇合并操作，可形成非球形的大簇。
    (5)時間復(fù)雜度分析。
    算法首先根據(jù)定義2、3計算所有屬性(假設(shè)第k個屬性)下任意兩個屬性值之間的距離d(xik，xjk)，然后將其值存到數(shù)組DisAttr[k][i][j]中，以便計算距離d(xi，xj)時使用。計算距離d(xi，xj)的時間復(fù)雜度為O(Psn+Ps2n+P2s3n)=O((Ps+Ps2+P2s3)n)，s=max|Vl|，1≤l≤P。由于對于大數(shù)據(jù)集n>>s，n>>P，所以復(fù)雜度是線性O(shè)(n)的。
    步驟(1)中計算信任值的時間復(fù)雜度為O(n(n-1)/2)，步驟(2)如果采用快速排序，則時間復(fù)雜度為O(nlgn)，步驟(3)聚類形成簇的時間復(fù)雜度為O(n(n+1)/2)，步驟(4)合并簇的時間復(fù)雜度為O(m2)，m為步驟(3)中生成的簇的個數(shù)(n>>m)。
    所以TrustCCluster算法的時間復(fù)雜度為O(n2)。
2 實驗結(jié)果
    為了驗證本文算法的有效性，在UCIMachine Learning Repository 提供的Soybean和Congressional Vote數(shù)據(jù)集上進行了測試，并與K-Modes 、P-Modes算法進行了對比，結(jié)果表明本文算法聚精度更高。實驗所用編程環(huán)境為VC++6.0。
    為比較聚類結(jié)果，定義聚類精度r：
    

    Congressional Votes數(shù)據(jù)集記錄了美國國會1984年435個國會議員的投票情況。每條記錄為一個議員在16個屬性上的表決情況,并有一個分類標志Republican或Democrat，用以表明對應(yīng)的議員所屬黨派。每條記錄由16個屬性描述，每個屬性僅取3個值(y表示同意，n表示不同意，?表示不表態(tài))。TrustCCluster在4/5E≤R≤5/4E，3/5T≤Q≤3/2T時隨機運行100次。K-Modes、P-Modes算法的初始聚類個數(shù)為K=3，初始點隨機選取，運行100次。三種算法聚類結(jié)果比較如表2所示?？梢钥闯鲈谶m當參數(shù)下，TrustCCluster算法最大聚類精度和平均聚類精度都要高于另外兩種算法。

    本文提出了一種基于信任值的分類屬性聚類算法TrustCCluster，相對于K-Modes、P-Modes，TrustCCluster 算法具有如下優(yōu)點：不需預(yù)先給定聚類個數(shù)；聚類結(jié)果不依賴于初始值的選?。豢梢园l(fā)現(xiàn)非球形的簇；聚類精度更高。
    TrustCCluster算法的時間復(fù)雜度為O(n2)，不適合大規(guī)模數(shù)據(jù)的聚類，只支持分類屬性數(shù)據(jù)。如何使TrustCCluster算法應(yīng)用于大規(guī)模數(shù)據(jù)的聚類，并且能處理混合型數(shù)據(jù)，以及更合理地選擇參數(shù)R和Q是需進一步研究的問題。
參考文獻
[1] MACQUEEN J.Some methods for classification and analysis of multivariate observations[C].Proc 5th Berkeley Symposium Mathematics Statist and Probaility，1967：281-297.
[2] KAUFMAN J，ROUSSEEUW P J.Finding groups in data：an introduction to cluster analysis[M].New York：John Wiley&Sons，1990.
[3] ESTER M，KRIEGEL H P，SANDER J，et al.A density-based algorithm for discovering clusters in large spatial databases[C].Proc.of 1996 Intl.Conf.on Knowledge Discovery and Data Mining，Portland，OR.1996：226-231.
[4] WANG W，YANG J，MUNTZ R.STING：A statistical information grid approach to spatial data mining[C].Proc of 1997 Intl.Conf.on Very Large Databases，Athens，Greece. 1997：186-195.
[5] KOHONEN T.Self-organized formation of topologically correct feature maps[J].Biological Cybernetics，1982，43(1)：59-69.
[6] Huang Zhexue.Clustering large data sets with mixed numeric and categorical values[C].Proc of PAKDD 97.Singapore：World Scientific，1997：21-35.
[7] Huang Zhexue.Extensions to the K-means algorithm for clustering large data sets with categorical values[J].Data Mining and Knowledge Discovery，1998，2(3)：283-304.
[8] 梁吉業(yè)，白亮，曹付元.基于新的距離度量的K-Modes聚類算法[J].計算機研究與發(fā)展，2010，47(10)：1749-1755.