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

K-means聚類(lèi)

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

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

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

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

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

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

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