聚類算法用于根據(jù)數(shù)據(jù)的特征發(fā)現(xiàn)數(shù)據(jù)項的相似性，并將相似的數(shù)據(jù)項放在同一個組中，相似性采用距離進(jìn)行描述。

K-means聚類

    簡單的說，一般流程如下：先隨機(jī)選取k個點，將每個點分配給它們，得到最初的k個分類；在每個分類中計算均值，將點重新分配，劃歸到最近的中心點；重復(fù)上述步驟直到點的劃歸不再改變。下圖是K-means方法的示意。

K-Means算法的SAS實現(xiàn)
    K-means算法可以用SAS的proc fastclus實現(xiàn)。主要涉及兩個問題。
    首先是初始點的選擇。如果指定replace=random，則系統(tǒng)隨機(jī)選取maxcluster選項指定個數(shù)的完整觀測作為凝聚點。如果分析員對研究情景比較了解，可以利用專業(yè)知識指定初始分類，那么可以在proc fastclus中設(shè)定seed=dataset選項，SAS會從dataset中讀取前k個觀測作為初始凝聚點。此外，SAS還提供了系統(tǒng)自動選擇初始凝聚點的方法，該方法需要指定maxclusters和radius選項，其中radius為凝聚點之間允許的最小距離。默認(rèn)值是maxclusters=100，radius=0，效果是選取數(shù)據(jù)集中的前100個觀測作為凝聚點。fastclus過程總是選擇第一個完整觀測作為第一個凝聚點，然后依次考察剩余觀測，與第一個凝聚點的距離大于radius指定值的觀測作為第二個凝聚點。當(dāng)凝聚點的個數(shù)未達(dá)到maxcluster，且所考察觀測與已有凝聚點間距離均大于radius指定值時，則所考察的觀測成為下一個凝聚點。如果一個觀測完整且與所有凝聚點距離均大于radius，但凝聚點個數(shù)已經(jīng)達(dá)到最大值，此時fastclus過程進(jìn)行兩種替換檢驗，檢驗?zāi)芊裼卯?dāng)前觀測替換已有凝聚點。第一個檢驗是替換距離最近兩凝聚點檢驗，如果凝聚點與當(dāng)前觀測的最小距離大于已有凝聚點的最小距離，則一個已有凝聚點將被替換，當(dāng)前觀測將替換距離最近的兩個凝聚點中的一個，使得替換后當(dāng)前觀測與最近距離兩凝聚點中未被替換的那個距離最遠(yuǎn)。第二個檢驗是替換當(dāng)前觀測最近凝聚點檢驗，如果當(dāng)前觀測到除最近凝聚點外的所有凝聚點的最小距離大于當(dāng)前觀測最近凝聚點到所有其他凝聚點的最小距離，進(jìn)行替換。如果兩種檢驗都說明該觀測不能替換已有凝聚點，則轉(zhuǎn)向下一個觀測，直到考察完數(shù)據(jù)集中的所有觀測。當(dāng)然，這種檢測可以用replace=none|part|full來控制，none表示不進(jìn)行替換檢驗，part表示只進(jìn)行第一種替換檢驗；full為默認(rèn)值，兩種替換檢驗都進(jìn)行。
    另一個問題是分類的修改方法。默認(rèn)的方法是按批修改法，即選定一批凝聚點后；將所有觀測按與其距離最近的凝聚點歸類；計算每一類重心，將重心作為新的凝聚點，若新凝聚點與舊凝聚點完全重合，則終止算法，否則重新歸類。批量修改法是全部觀測調(diào)整完畢后，才改變類的凝聚點，而逐個修改法是每個觀測一旦調(diào)整后立即改變類凝聚點，而立即改變需要算法即時驗證改變后的凝聚點集合是否仍然滿足radius的約束。如果不滿足radius的約束，SAS會將小于radius的兩類合并，計算重心，作為合并后類的凝聚點，如此往復(fù)，直到凝聚點滿足radius條件。要讓SAS執(zhí)行逐個修改法，需要聲明drift選項。

補充
    K-means聚類算法的問題是，均值的計算受異常點的干擾比較嚴(yán)重。為了克服這個問題，可以采用K中值法。

K-medoid聚類
    PAM（Partition Around Medoids）是K-medoid的基礎(chǔ)算法，基本流程如下：首先隨機(jī)選擇k個對象作為中心，把每個對象分配給離它最近的中心。然后隨機(jī)地選擇一個非中心對象替換中心對象，計算分配后的距離改進(jìn)量。聚類的過程就是不斷迭代，進(jìn)行中心對象和非中心對象的反復(fù)替換過程，直到目標(biāo)函數(shù)不再有改進(jìn)為止。非中心點和中心點替換的具體類別如下圖分析（用h替換i相對j的開銷）。

    PAM算法的問題在于伸縮性不好，需要測試所有的替換，只適用于小數(shù)據(jù)量的聚類。

    為了提高該算法的可伸縮性，有人提出了CLARAN算法，本質(zhì)如下：從總體數(shù)據(jù)中生成多個樣本數(shù)據(jù)，在每個樣本數(shù)據(jù)上應(yīng)用PAM算法得到一組K中值點；取出所有樣本中結(jié)果最好的那一組作為最后的解。CLARAN算法存在的問題是，算法的聚類質(zhì)量依賴于樣本的質(zhì)量。

    為了提高PAM和CLARAN算法的聚類質(zhì)量，有人在CLARAN算法的基礎(chǔ)上提出了CLARANS算法。與CLARAN相比，最大的區(qū)別在于沒有一個時刻算法局限于固定的一個樣本中，自始自終，算法的樣本數(shù)據(jù)都是隨機(jī)抽樣的。其算法過程如下。將每套k個中值點作為一個節(jié)點，若兩個節(jié)點之間有k-1個點相同，則成為鄰居。用戶事先指定兩個數(shù)，一是最大的鄰居數(shù)，二是最大的局部最優(yōu)點數(shù)。算法隨機(jī)選取一個當(dāng)前點，隨機(jī)地取出其中的一個鄰居，看目標(biāo)值是否有改進(jìn)，如果有改進(jìn)，則用鄰居替代當(dāng)前點，重新開始搜索鄰居的過程；若抽取了最大鄰居數(shù)的鄰居，發(fā)現(xiàn)當(dāng)前點最優(yōu)，那么就找到了一個局部最優(yōu)點。找到一個局部最優(yōu)點后，再隨機(jī)抽取一個當(dāng)前點，進(jìn)行上面的過程，直到找到了用戶指定最大數(shù)量的局部最優(yōu)點。比較每個局部最優(yōu)點的目標(biāo)值，取最優(yōu)的那個點作為結(jié)果，即可得到k個中值點，于是k個類就可以輕松得到。CLARANS算法的效果不錯，但算法復(fù)雜度更高。