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

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


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

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

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

    本文提出了一種基于信任值的分類屬性聚類算法TrustCCluster，相對(duì)于K-Modes、P-Modes，TrustCCluster 算法具有如下優(yōu)點(diǎn)：不需預(yù)先給定聚類個(gè)數(shù)；聚類結(jié)果不依賴于初始值的選??；可以發(fā)現(xiàn)非球形的簇；聚類精度更高。
    TrustCCluster算法的時(shí)間復(fù)雜度為O(n2)，不適合大規(guī)模數(shù)據(jù)的聚類，只支持分類屬性數(shù)據(jù)。如何使TrustCCluster算法應(yīng)用于大規(guī)模數(shù)據(jù)的聚類，并且能處理混合型數(shù)據(jù)，以及更合理地選擇參數(shù)R和Q是需進(jìn)一步研究的問(wèn)題。
參考文獻(xiàn)
[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].計(jì)算機(jī)研究與發(fā)展，2010，47(10)：1749-1755.