一篇文章透徹解讀聚類分析及案例實(shí)操(一)

本文主要是介紹一下SAS的聚類案例，希望大家都動(dòng)手做一遍，很多問(wèn)題只有在親自動(dòng)手的過(guò)程中才會(huì)有發(fā)現(xiàn)有收獲有心得。這里重點(diǎn)拿常見(jiàn)的工具SAS+R語(yǔ)言+Python介紹!

1  聚類分析介紹

1.1 基本概念

聚類就是一種尋找數(shù)據(jù)之間一種內(nèi)在結(jié)構(gòu)的技術(shù)。聚類把全體數(shù)據(jù)實(shí)例組織成一些相似組，而這些相似組被稱作聚類。處于相同聚類中的數(shù)據(jù)實(shí)例彼此相同， 處于不同聚類中的實(shí)例彼此不同。聚類技術(shù)通常又被稱為無(wú)監(jiān)督學(xué)習(xí)，因?yàn)榕c監(jiān)督學(xué)習(xí)不同，在聚類中那些表示數(shù)據(jù)類別的分類或者分組信息是沒(méi)有的。

通過(guò)上述表述，我們可以把聚類定義為將數(shù)據(jù)集中在某些方面具有相似性的數(shù)據(jù)成員進(jìn)行分類組織的過(guò)程。因此，聚類就是一些數(shù)據(jù)實(shí)例的集合，這個(gè)集合中 的元素彼此相似，但是它們都與其他聚類中的元素不同。在聚類的相關(guān)文獻(xiàn)中，一個(gè)數(shù)據(jù)實(shí)例有時(shí)又被稱為對(duì)象，因?yàn)楝F(xiàn)實(shí)世界中的一個(gè)對(duì)象可以用數(shù)據(jù)實(shí)例來(lái)描 述。同時(shí)，它有時(shí)也被稱作數(shù)據(jù)點(diǎn)(Data Point)，因?yàn)槲覀兛梢杂胷 維空間的一個(gè)點(diǎn)來(lái)表示數(shù)據(jù)實(shí)例，其中r 表示數(shù)據(jù)的屬性個(gè)數(shù)。下圖顯示了一個(gè)二維數(shù)據(jù)集聚類過(guò)程，從該圖中可以清楚地看到數(shù)據(jù)聚類過(guò)程。雖然通過(guò)目測(cè)可以十分清晰地發(fā)現(xiàn)隱藏在二維或者三維的數(shù)據(jù) 集中的聚類，但是隨著數(shù)據(jù)集維數(shù)的不斷增加，就很難通過(guò)目測(cè)來(lái)觀察甚至是不可能。

1.2 算法概述

目前在存在大量的聚類算法，算法的選擇取決于數(shù)據(jù)的類型、聚類的目的和具體應(yīng)用。大體上，主要的聚類算法分為幾大類。

聚類算法的目的是將數(shù)據(jù)對(duì)象自動(dòng)的歸入到相應(yīng)的有意義的聚類中。追求較高的類內(nèi)相似度和較低的類間相似度是聚類算法的指導(dǎo)原則。一個(gè)聚類算法的優(yōu)劣可以從以下幾個(gè)方面來(lái)衡量：

(1)可伸縮性：好的聚類算法可以處理包含大到幾百萬(wàn)個(gè)對(duì)象的數(shù)據(jù)集;

(2)處理不同類型屬性的能力：許多算法是針對(duì)基于區(qū)間的數(shù)值屬性而設(shè)計(jì)的，但是有些應(yīng)用需要針對(duì)其它數(shù)據(jù)類型(如符號(hào)類型、二值類型等)進(jìn)行處理;

(3)發(fā)現(xiàn)任意形狀的聚類：一個(gè)聚類可能是任意形狀的，聚類算法不能局限于規(guī)則形狀的聚類;

(4)輸入?yún)?shù)的最小化：要求用戶輸入重要的參數(shù)不僅加重了用戶的負(fù)擔(dān)，也使聚類的質(zhì)量

難以控制;

(5)對(duì)輸入順序的不敏感：不能因?yàn)橛胁煌臄?shù)據(jù)提交順序而使聚類的結(jié)果不同;

(6)高維性：一個(gè)數(shù)據(jù)集可能包含若干維或?qū)傩裕粋€(gè)好的聚類算法不能僅局限于處理二維

或三維數(shù)據(jù)，而需要在高維空間中發(fā)現(xiàn)有意義的聚類;

(7)基于約束的聚類：在實(shí)際應(yīng)用中要考慮很多約束條件，設(shè)計(jì)能夠滿足特定約束條件且具

有較好聚類質(zhì)量的算法也是一項(xiàng)重要的任務(wù);

(8)可解釋性：聚類的結(jié)果應(yīng)該是可理解的、可解釋的，以及可用的。

1.3 聚類應(yīng)用

在商業(yè)上，聚類分析被用來(lái)發(fā)現(xiàn)不同的客戶群，并且通過(guò)購(gòu)買(mǎi)模式刻畫(huà)不同的客戶群的特征。聚類分析是細(xì)分市場(chǎng)的有效工具，同時(shí)也可用于研究消費(fèi)者行 為，尋找新的潛在市場(chǎng)、選擇實(shí)驗(yàn)的市場(chǎng)，并作為多元分析的預(yù)處理。在生物上，聚類分析被用來(lái)動(dòng)植物分類和對(duì)基因進(jìn)行分類，獲取對(duì)種群固有結(jié)構(gòu)的認(rèn)識(shí)。在地 理上，聚類能夠幫助在地球中被觀察的數(shù)據(jù)庫(kù)商趨于的相似性。在保險(xiǎn)行業(yè)上，聚類分析通過(guò)一個(gè)高的平均消費(fèi)來(lái)鑒定汽車(chē)保險(xiǎn)單持有者的分組，同時(shí)根據(jù)住宅類 型，價(jià)值，地理位置來(lái)鑒定一個(gè)城市的房產(chǎn)分組。在因特網(wǎng)應(yīng)用上，聚類分析被用來(lái)在網(wǎng)上進(jìn)行文檔歸類來(lái)修復(fù)信息。在電子商務(wù)上，聚類分析在電子商務(wù)中網(wǎng)站建 設(shè)數(shù)據(jù)挖掘中也是很重要的一個(gè)方面，通過(guò)分組聚類出具有相似瀏覽行為的客戶，并分析客戶的共同特征，可以更好的幫助電子商務(wù)的用戶了解自己的客戶，向客戶提供更合適的服務(wù)。

2  kmeans 算法

2.1 基本思想

劃分聚類算法是根據(jù)給定的n 個(gè)對(duì)象或者元組的數(shù)據(jù)集，構(gòu)建k 個(gè)劃分聚類的方法。每個(gè)劃分即為一個(gè)聚簇，并且k ? n。該方法將數(shù)據(jù)劃分為k 個(gè)組，每個(gè)組至少有一個(gè)對(duì)象，每個(gè)對(duì)象必須屬于而且只能屬于一個(gè)組。1該方法的劃分采用按照給定的k 個(gè)劃分要求，先給出一個(gè)初始的劃分，然后用迭代重定位技術(shù)，通過(guò)對(duì)象在劃分之間的移動(dòng)來(lái)改進(jìn)劃分。

為達(dá)到劃分的全局最優(yōu)，劃分的聚類可能會(huì)窮舉所有可能的劃分。但在實(shí)際操作中，往往采用比較流行的k-means 算法或者k-median 算法。

2.2 算法步驟

k-means 算法最為簡(jiǎn)單，實(shí)現(xiàn)比較容易。每個(gè)簇都是使用對(duì)象的平均值來(lái)表示。

步驟一：將所有對(duì)象隨機(jī)分配到k 個(gè)非空的簇中。

步驟二：計(jì)算每個(gè)簇的平均值，并用該平均值代表相應(yīng)的值。

步驟三：根據(jù)每個(gè)對(duì)象與各個(gè)簇中心的距離，分配給最近的簇。

步驟四：轉(zhuǎn)到步驟二，重新計(jì)算每個(gè)簇的平均值。這個(gè)過(guò)程不斷重復(fù)直到滿足某個(gè)準(zhǔn)則函數(shù)或者終止條件。終止(收斂)條件可以是以下任何一個(gè)：沒(méi)有(或者最小數(shù)目)數(shù)據(jù)點(diǎn)被重新分配給不同的聚類;沒(méi)有(或者最小數(shù)目)聚類中心再發(fā)生變化;誤差平方和(SSE)局部最小。

其中， k 表示需要聚集的類的數(shù)目， Cj表示第j 個(gè)聚類，mj表示聚類Cj的聚類中心，

dist表示數(shù)據(jù)點(diǎn)x 和聚類中心mj之間的距離。利用該準(zhǔn)則可以使所生成的簇盡可能

的緊湊和獨(dú)立。

SAS kmeans 實(shí)現(xiàn)主要是通過(guò)proc fastclus 過(guò)程實(shí)現(xiàn)，示例如下：

proc import datafile=”E:\SAS\cars.txt” out=cars dbms=dlm replace;

delimiter=’09’x;

getnames=yes;

run;

proc print data=cars;

run;

proc standard data=cars out=stdcars mean=0 std=1;

var Mpg Weight Drive_Ratio Horsepower Displacement;

run;

proc fastclus data=stdcars summary maxc=5 maxiter=99

outseed=clusterseed out=clusterresult cluster=cluster least=2;

id Car;

var Mpg Weight Drive_Ratio Horsepower Displacement;

run;

2.3 算法分析

k-means 算法對(duì)于大型的數(shù)據(jù)庫(kù)是相對(duì)高效的，一般情況下結(jié)束于局部最優(yōu)解。但是，k-means 算法必須在平均值有意義的情況下才能使用，對(duì)分類變量不適用，事先還要給定生成聚類的數(shù)目，對(duì)異常數(shù)據(jù)和數(shù)據(jù)噪聲比較敏感，不能對(duì)非凸面形狀的數(shù)據(jù)進(jìn)行處 理。另外，k-means 算法在聚類過(guò)程中可能有的聚類中心沒(méi)有被分配任何數(shù)據(jù)而使得某些聚類變?yōu)榭眨@些聚類通常被稱為空聚類。為了解決空聚類問(wèn)題，我們可以選擇一個(gè)數(shù)據(jù)點(diǎn)作為 替代的聚類中心。例如，某一個(gè)含有大量數(shù)據(jù)的聚類的聚簇中心最遠(yuǎn)的數(shù)據(jù)點(diǎn)。如果算法的終止條件取決于誤差平方和，具有最大誤差平方和的聚類可以被用來(lái)尋找 另外的聚類中心。

3  層次聚類算法

3.1 基本思想

層次聚類主要有兩種類型：合并的層次聚類和分裂的層次聚類。前者是一種自底向上的層次聚類算法，從最底層開(kāi)始，每一次通過(guò)合并最相似的聚類來(lái)形成上 一層次中的聚類，整個(gè)當(dāng)全部數(shù)據(jù)點(diǎn)都合并到一個(gè)聚類的時(shí)候停止或者達(dá)到某個(gè)終止條件而結(jié)束，大部分層次聚類都是采用這種方法處理。后者是采用自頂向下的方 法，從一個(gè)包含全部數(shù)據(jù)點(diǎn)的聚類開(kāi)始，然后把根節(jié)點(diǎn)分裂為一些子聚類，每個(gè)子聚類再遞歸地繼續(xù)往下分裂，直到出現(xiàn)只包含一個(gè)數(shù)據(jù)點(diǎn)的單節(jié)點(diǎn)聚類出現(xiàn)，即每 個(gè)聚類中僅包含一個(gè)數(shù)據(jù)點(diǎn)。

層次聚類技術(shù)是一種無(wú)監(jiān)督學(xué)習(xí)的技術(shù)，因此可能沒(méi)有確定的、一致的正確答案。正是由于這個(gè)原因，并且在聚類的特定應(yīng)用的基礎(chǔ)之上，可以設(shè)計(jì)出較少或 較多數(shù)量的簇。定義了一個(gè)聚類層次，就可以選擇希望數(shù)量的簇。在極端的情況下，所有的對(duì)象都自成一簇。在這樣的情形下，聚類的對(duì)象之間非常相似，并且不同 于其他的聚類。當(dāng)然，這種聚類技術(shù)就失去了實(shí)際意義，因?yàn)榫垲惖哪康氖菍ふ覕?shù)據(jù)集中的有意義的模式，方便用戶理解，而任何聚類的數(shù)目和數(shù)據(jù)對(duì)象一樣多的聚 類算法都不能幫助用戶更好地理解數(shù)據(jù)，挖掘數(shù)據(jù)隱藏的真實(shí)含義。這樣，關(guān)于聚類的很重要的一點(diǎn)就是應(yīng)該比原先的數(shù)據(jù)的數(shù)目更少的簇。到底要形成多少個(gè)聚類 數(shù)目，要根據(jù)實(shí)際業(yè)務(wù)的理解，這是如何解釋實(shí)際項(xiàng)目的事情。層次聚類算法的好處是它可以讓用戶從這些簇中選擇所感興趣的簇，這樣更具有靈活性。

層次聚類通常被看做成一棵樹(shù)，其中最小的簇合并在一起創(chuàng)建下一個(gè)較高層次的簇，這一層次的簇再合并在一起就創(chuàng)建了再下一層次的簇。通過(guò)這樣的過(guò)程， 就可以生成一系列的聚類樹(shù)來(lái)完成聚類。單點(diǎn)聚類處在樹(shù)的最底層，在樹(shù)的底層有一個(gè)根節(jié)點(diǎn)聚類。根節(jié)點(diǎn)聚類覆蓋了全部數(shù)據(jù)節(jié)點(diǎn)，兄弟節(jié)點(diǎn)聚類則劃分了它們共 同的父節(jié)點(diǎn)中的所有的數(shù)據(jù)點(diǎn)。圖1-5是采用統(tǒng)計(jì)分析軟件SAS對(duì)Cars2數(shù)據(jù)集進(jìn)行層次聚類的層次聚類結(jié)果圖。通過(guò)該層次聚類樹(shù)，用戶可以選擇查看在 樹(shù)的各個(gè)層次上的聚類情況。

基于層次的聚類算法方法比較簡(jiǎn)單，但是缺乏伸縮性，一旦一個(gè)合并或者分裂被執(zhí)行，就不能撤銷。為了改進(jìn)層次聚類的效果，可以將層次聚類算法和其他聚類算法結(jié)合使用，形成多階段的聚類算法。

3.2 算法步驟

層次聚類(hierarchical clustering)算法遞歸的對(duì)對(duì)象進(jìn)行合并或者分裂，直到滿足某一終止條件為止。層次聚類分為兩種，按自底向上層次分解稱為聚合的層次聚類，反之， 稱為分解的層次聚類。層次聚類算法的計(jì)算復(fù)雜度為O(n2)，適合小型數(shù)據(jù)集的分類。

CURE、ROCK、BIRCH和CHAMELEON是聚合層次聚類中最具代表性的方法。CURE(Clustering Using REpresentatives)算法采用了抽樣和分區(qū)的技術(shù)，選擇數(shù)據(jù)空間中固定數(shù)目的、具有代表性的一些點(diǎn)來(lái)代表相應(yīng)的類，這樣就可以識(shí)別具有復(fù)雜形 狀和不同大小的聚類，從而很好的過(guò)濾孤立點(diǎn)。ROCK(RObust Clustering using linKs)算法是對(duì)CURE算法的改進(jìn)，除了具有CURE算法的一些優(yōu)良特性外，還適用于類別屬性的數(shù)據(jù)。BIRCH(Balanced Iterative Reducing and Clustering using Hierarchy)算法首次提出了通過(guò)局部聚類對(duì)數(shù)據(jù)庫(kù)進(jìn)行預(yù)處理的思想。CHAMELEON是Karypis等人1999年提出的，它在聚合聚類的過(guò) 程中利用了動(dòng)態(tài)建模技術(shù)。

SAS實(shí)例

options nocenter nodate pageno=1 linesize=132;

title h = 1 j = l ‘File: cluster.mammalsteeth.sas’;

title2 h = 1 j = l ‘Cluster Analysis of Mammals” teeth data’;

data teeth;

input mammal $ 1-16

@wf0007 (v1-v8) (1.);

label v1=’Top incisors’

v2=’Bottom incisors’

v3=’Top canines’

v4=’Bottom canines’

v5=’Top premolars’

v6=’Bottom premolars’

v7=’Top molars’

v8=’Bottom molars’;

cards;

BROWN BAT 23113333

MOLE 32103333

SILVER HAIR BAT 23112333

PIGMY BAT 23112233

HOUSE BAT 23111233

RED BAT 13112233

PIKA 21002233

RABBIT 21003233

BEAVER 11002133

GROUNDHOG 11002133

GRAY SQUIRREL 11001133

HOUSE MOUSE 11000033

PORCUPINE 11001133

WOLF 33114423

BEAR 33114423

RACCOON 33114432

MARTEN 33114412

WEASEL 33113312

WOLVERINE 33114412

BADGER 33113312

RIVER OTTER 33114312

SEA OTTER 32113312

JAGUAR 33113211

COUGAR 33113211

FUR SEAL 32114411

SEA LION 32114411

GREY SEAL 32113322

ELEPHANT SEAL 21114411

REINDEER 04103333

ELK 04103333

DEER 04003333

MOOSE 04003333

;

proc princomp data=teeth out=teeth2;

var v1-v8;

run;

proc cluster data=teeth2 method=average outtree=ttree

ccc pseudo rsquare;

var v1-v8;

id mammal;

run;

proc tree data=ttree out=ttree2 nclusters=4;

id mammal;

run;

proc sort data=teeth2;

by mammal;

run;

proc sort data=ttree2;

by mammal;

run;

data teeth3;

merge teeth2 ttree2;

by mammal;

run;

symbol1 c=black f=, v=’1′;

symbol2 c=black f=, v=’2′;

symbol3 c=black f=, v=’3′;

symbol4 c=black f=, v=’4′;

proc gplot;

plot prin2*prin1=cluster;

run;

proc sort;

by cluster;

run;

proc print;

by cluster;

var mammal prin1 prin2;

run;