商務(wù)智能ppt第五章 聚類分析

第五章聚類分析【學(xué)習(xí)目標(biāo)】

理解聚類的基本概念掌握距離計(jì)算的不同方式掌握聚類的不同方法5.1聚類的基本概念“物以類聚，人以群分”，在自然科學(xué)和社會(huì)科學(xué)中，存在著大量的分類問(wèn)題。例如，市場(chǎng)營(yíng)銷中的市場(chǎng)細(xì)分和客戶細(xì)分問(wèn)題。大型購(gòu)物網(wǎng)站收集到客戶人口特征、消費(fèi)行為和喜好方面的數(shù)據(jù)，并希望對(duì)這些客戶進(jìn)行特征分析。可以從客戶分類入手，根據(jù)客戶的年齡、職業(yè)、收入、消費(fèi)金額、消費(fèi)頻率、喜好等方面進(jìn)行單變量或多變量的客戶分組。這種分組是極為常見(jiàn)的客戶細(xì)分方式，但存在的不足是客戶群劃分帶有明顯得主觀色彩，需要有豐富的行業(yè)經(jīng)驗(yàn)才能得到比較合理或理想的客戶細(xì)分，否則得到的分組可能無(wú)法充分反映和展現(xiàn)客戶的特點(diǎn)，主要表現(xiàn)在，同一客戶細(xì)分段中的客戶在某些特征方面并不相似，而不同客戶細(xì)分段中的客戶在某些特征方面卻又很相似。因此，這種客戶細(xì)分并沒(méi)有真正起到劃分客戶群的作用。為解決該問(wèn)題，希望從數(shù)據(jù)自身出發(fā)，充分利用數(shù)據(jù)進(jìn)行客戶的客觀分組，使諸多特征有相似性的客戶被分在同一組，而不相似的客戶被區(qū)分到另一些組中。聚類分析則是這樣一種方法聚類分析又稱群分析，它是研究（樣品或指標(biāo)）分類問(wèn)題的一種多元統(tǒng)計(jì)分析方法。聚類分析起源于分類學(xué)，但是聚類不等于分類。聚類與分類的不同在于，聚類所要求劃分的類是未知的。聚類分析內(nèi)容非常豐富，有系統(tǒng)聚類法、有序樣品聚類法、動(dòng)態(tài)聚類法、模糊聚類法、圖論聚類法、聚類預(yù)報(bào)法等。聚類分析能夠?qū)⒁慌鷺颖净颍ㄗ兞浚?shù)據(jù)依據(jù)其諸多特征，按照性質(zhì)上的親疏程度在沒(méi)有先驗(yàn)知識(shí)的情況下進(jìn)行自動(dòng)分類，產(chǎn)生多個(gè)分類結(jié)果。類內(nèi)部的個(gè)體在特征上具有相似性，不同類間個(gè)體特征的差異性較大理解聚類分析的關(guān)鍵是理解兩個(gè)要點(diǎn)：“沒(méi)有先驗(yàn)知識(shí)”和“親疏程度”。為此，可以先看一個(gè)例子編號(hào)購(gòu)物環(huán)境服務(wù)質(zhì)量A超市7368B超市6664C超市8482D超市9188E超市9490“親疏程度”的衡量與計(jì)算在聚類分析中，衡量個(gè)體之間的“親屬程度”是極為重要的，它將直接影響最終的聚類結(jié)果。衡量“親疏程度”一般有兩個(gè)角度：第一，個(gè)體間的相似程度；第二，個(gè)體間的差異程度。衡量個(gè)體間的相似程度通?？梢圆捎煤?jiǎn)單相關(guān)系數(shù)或等級(jí)相關(guān)系數(shù)等；個(gè)體間的差異程度通常通過(guò)某種距離來(lái)測(cè)度，以下著重討論個(gè)體間的差異程度。為定義個(gè)體間的距離，應(yīng)先將每個(gè)樣本數(shù)據(jù)看成k維空間上的一個(gè)點(diǎn)。例如，可將表5-1中五個(gè)超市樣本看成k等于2的二維空間上的五個(gè)點(diǎn)，也就是看成由購(gòu)物環(huán)境和服務(wù)質(zhì)量?jī)蓚€(gè)變量構(gòu)成的二維平面上的五個(gè)點(diǎn)，并于此定義某種距離，計(jì)算五個(gè)點(diǎn)彼此間的“親疏程度”。通常，點(diǎn)與點(diǎn)之間距離越小，意味著它們?cè)健坝H密”，越有可能聚成一類。點(diǎn)與點(diǎn)之間距離越大，意味著它們?cè)健笆柽h(yuǎn)”，越有可能分別屬于不同的類。編號(hào)購(gòu)物環(huán)境服務(wù)質(zhì)量A超市7368B超市6664C超市8482D超市9188E超市94905.2.1定距型變量個(gè)體間距離計(jì)算

如果涉及到的k個(gè)變量都是定距型變量，那么個(gè)體間距離的定義通常有以下幾種方式：1.歐氏距離(EuclideanDistance)歐氏距離（也稱歐幾里得度量（Euclideanmetric））是一個(gè)通常采用的距離定義，指在m維空間中兩個(gè)點(diǎn)之間的真實(shí)距離，或者向量的自然長(zhǎng)度（即該點(diǎn)到原點(diǎn)的距離）。在二維和三維空間中的歐氏距離就是兩點(diǎn)之間的實(shí)際距離。2.曼哈頓距離(ManhattanDistance)

想象你在曼哈頓要從一個(gè)十字路口開(kāi)車到另外一個(gè)十字路口，駕駛距離是兩點(diǎn)間的直線距離嗎？顯然不是，除非你能穿越大樓。實(shí)際駕駛距離就是這個(gè)“曼哈頓距離”。而這也是曼哈頓距離名稱的來(lái)源，曼哈頓距離也稱為城市街區(qū)距離(CityBlockdistance)。曼哈頓距離(ManhattanDistance)

需要注意的地方：非負(fù)性：d(i,j)≥0距離是一個(gè)非負(fù)的數(shù)值；同一性：d(i,i)=0對(duì)象到自身的距離為0；對(duì)稱性：d(i,j)=d(j,i)距離是一個(gè)對(duì)稱函數(shù)；3.切比雪夫距離(ChebyshevDistance)

國(guó)際象棋玩過(guò)么？國(guó)王走一步能夠移動(dòng)到相鄰的8個(gè)方格中的任意一個(gè)。那么國(guó)王從格子(x1,y1)走到格子(x2,y2)最少需要多少步？自己走走試試。你會(huì)發(fā)現(xiàn)最少步數(shù)總是max(|x2-x1|,|y2-y1|)步。有一種類似的一種距離度量方法叫切比雪夫距離。在數(shù)學(xué)中，切比雪夫距離是向量空間中的一種度量，兩個(gè)點(diǎn)之間的距離定義是其各坐標(biāo)數(shù)值差絕對(duì)值的最大值。舉個(gè)例子：二維樣本(身高,體重)，其中身高范圍是150~190，體重范圍是50~60，有三個(gè)樣本：a(180,50)，b(190,50)，c(180,60)。那么計(jì)算a與b之間，a與c之間的曼哈頓距離、歐氏距離或切比雪夫距離標(biāo)準(zhǔn)歐氏距離的定義*

標(biāo)準(zhǔn)化歐氏距離是針對(duì)簡(jiǎn)單歐氏距離的缺點(diǎn)而作的一種改進(jìn)方案。標(biāo)準(zhǔn)歐氏距離的思路：針對(duì)數(shù)據(jù)各維分量的分布不一致情況將各個(gè)分量“標(biāo)準(zhǔn)化”到均值、方差相等。假設(shè)樣本集X的均值(mean)為m，標(biāo)準(zhǔn)差(standarddeviation)為s，那么X的“標(biāo)準(zhǔn)化變量”（標(biāo)準(zhǔn)化變量的數(shù)學(xué)期望為0，方差為1）表示為：標(biāo)準(zhǔn)化后的值=(標(biāo)準(zhǔn)化前的值－分量的均值)/分量的標(biāo)準(zhǔn)差。夾角余弦(Cosine)*夾角余弦取值范圍為[-1,1]。夾角余弦越大表示兩個(gè)向量的夾角越小，夾角余弦越小表示兩向量的夾角越大。當(dāng)兩個(gè)向量的方向重合時(shí)夾角余弦取最大值1，當(dāng)兩個(gè)向量的方向完全相反夾角余弦取最小值-1。5.2.2計(jì)數(shù)變量個(gè)體間距離的計(jì)算方式

卡方（Chi-Square）距離文化程度企業(yè)高中及以上初中小學(xué)及以下合計(jì)甲44（46）36（42）140（132）220乙60（58）60（54）160（168）280合計(jì)104963005005.2.3二值變量個(gè)體間距離計(jì)算該表是根據(jù)原始數(shù)據(jù)轉(zhuǎn)換而來(lái)的兩個(gè)體取值的交叉列聯(lián)表。表中，a+b+c+d等于變量的總個(gè)數(shù)，a為兩個(gè)體取值都為1的變量個(gè)數(shù)，b為個(gè)體x取值為0,而個(gè)體y取值為1的變量個(gè)數(shù)，c為個(gè)體x取值為1而個(gè)體y取值為0的變量個(gè)數(shù)，d為兩個(gè)體取值都是0的變量個(gè)數(shù)。顯然，a+d的比重描述了兩個(gè)體之間的相似程度，而b+c的比重反映了兩個(gè)體之間的差異程度。1.簡(jiǎn)單匹配系數(shù)

個(gè)體x10個(gè)體y1ab0cd姓名性別發(fā)燒咳嗽檢查1檢查2檢查3檢查4JackMYNPNNNMaryFYNPNPNJimMYPNNNN2.雅科比系數(shù)(Jaccardcoefficient)

一個(gè)二元屬性是對(duì)稱的，如果它的兩種狀態(tài)具有同等價(jià)值并且攜帶相同的權(quán)重；即關(guān)于哪個(gè)結(jié)果應(yīng)該用0或1編碼并無(wú)偏好（例如，屬性gender的兩種狀態(tài)男和女）。一個(gè)二元屬性是非對(duì)稱的，如果其狀態(tài)的結(jié)果不是同等重要的。為方便計(jì)，我們將用1對(duì)最重要的結(jié)果（通常是稀有的）編碼（例如，HIV陽(yáng)性），而另一個(gè)用0編碼（例如，HIV陰性）。給定兩個(gè)不對(duì)稱的二元變量，兩個(gè)都取值1的情況（正匹配）被認(rèn)為比兩個(gè)都取值0的情況（負(fù)匹配）更有意義?；谶@樣變量的相似度被稱為非恒定的相似度。對(duì)非恒定的相似度，最著名的評(píng)價(jià)系數(shù)是Jaccard系數(shù)，在它的計(jì)算中，負(fù)匹配的數(shù)目被認(rèn)為是不重要的，因此被忽略。換句話說(shuō)，就是把d去掉。姓名性別發(fā)燒咳嗽檢查1檢查2檢查3檢查4JackMYNPNNNMaryFYNPNPNJimMYPNNNN首先給Y和P值賦值為1，N賦值為05.2.4其他個(gè)體間距離計(jì)算

1.漢明距離(Hammingdistance)，漢明距離表示兩個(gè)（相同長(zhǎng)度）字對(duì)應(yīng)位不同的數(shù)量。換句話說(shuō)，它就是將一個(gè)字符串變換成另外一個(gè)字符串所需要替換的字符個(gè)數(shù)。1011101與1001001之間的漢明距離是2。2143896與2233796之間的漢明距離是3。信息熵(InformationEntropy)

信息熵并不屬于一種相似性度量。信息熵是衡量分布的混亂程度或分散程度的一種度量。分布越分散(或者說(shuō)分布越平均)，信息熵就越大。分布越有序（或者說(shuō)分布越集中），信息熵就越小。n：樣本集X的分類數(shù)；pi：X中第i類元素出現(xiàn)的概率；信息熵越大表明樣本集S分類越分散，信息熵越小則表明樣本集X分類越集中。當(dāng)S中n個(gè)分類出現(xiàn)的概率一樣大時(shí)（都是1/n），信息熵取最大值log2(n)。當(dāng)X只有一個(gè)分類時(shí)，信息熵取最小值0。5.3聚類的方法

5.3.1K-Means聚類算法K均值聚類算法（K-MeansClusteringAlgorithm）是一種迭代求解的聚類分析算法，其步驟是隨機(jī)選取K個(gè)對(duì)象作為初始的聚類中心，然后計(jì)算每個(gè)對(duì)象與各個(gè)種子聚類中心之間的距離，把每個(gè)對(duì)象分配給距離它最近的聚類中心2．K-Means(K均值)聚類算法及步驟

（1）首先確定一個(gè)k值，即我們希望將數(shù)據(jù)集經(jīng)過(guò)聚類得到k個(gè)集合。（2）從數(shù)據(jù)集中隨機(jī)選擇k個(gè)數(shù)據(jù)點(diǎn)作為質(zhì)心。（3）對(duì)數(shù)據(jù)集中每一個(gè)點(diǎn)，計(jì)算其與每一個(gè)質(zhì)心的距離（如歐式距離），離哪個(gè)質(zhì)心近，就劃分到那個(gè)質(zhì)心所屬的集合。（4）把所有數(shù)據(jù)歸好集合后，一共有k個(gè)集合。然后重新計(jì)算每個(gè)集合的質(zhì)心。（5）如果新計(jì)算出來(lái)的質(zhì)心和原來(lái)的質(zhì)心之間的距離小于某一個(gè)設(shè)置的閾值（表示重新計(jì)算的質(zhì)心的位置變化不大，趨于穩(wěn)定，或者說(shuō)收斂），我們可以認(rèn)為聚類已經(jīng)達(dá)到期望的結(jié)果，算法終止。（6）如果新質(zhì)心和原質(zhì)心距離變化很大，需要迭代3~5步驟

XYP100P212P331P488P5910P6107第一次循環(huán)

P1P2P33.162.24P411.39.22P513.511.3P612.210.3（1）首先令K等于2，隨機(jī)選擇兩個(gè)點(diǎn)：P1和P2；（2）通過(guò)勾股定理計(jì)算剩余點(diǎn)分別到這兩個(gè)點(diǎn)的距離，（3）第一次分組后結(jié)果：表其余點(diǎn)到P1、P2的距離組A：P1組B：P2、P3、P4、P5、P6（4）分別計(jì)算A組和B組的質(zhì)心：A組質(zhì)心還是P1=（0，0）B組新的質(zhì)心坐標(biāo)為：P2’=（（1+3+8+9+10）/5，（2+1+8+10+7）/5）=（6.2，5.6）第二次循環(huán)

P1P2’P22.246.3246P33.165.6036P411.33P513.55.2154P612.24.0497（5）再次計(jì)算每個(gè)點(diǎn)到質(zhì)心的距離,如表5-7所示：表5-7其余點(diǎn)到質(zhì)心的距離（6）第二次分組結(jié)果：組A：P1、P2、P3組B：P4、P5、P6（7）再次計(jì)算質(zhì)心：P1’=（1.33，1）P2”=（9，8.33）

P1’P2”P11.412P20.610P31.49.5P4471.1P5701.7P6561.7（8）再次計(jì)算每個(gè)點(diǎn)到質(zhì)心的距離，如表5-8所示：表5-8其余點(diǎn)到新質(zhì)心的距離（9）第三次分組結(jié)果：組A：P1、P2、P3組B：P4、P5、P6可以發(fā)現(xiàn)，第三次分組結(jié)果和第二次分組結(jié)果一致，說(shuō)明已經(jīng)收斂，聚類結(jié)束。k-means有個(gè)缺點(diǎn)？

怎么確定K呢？將K從2~N進(jìn)行遍歷，

然后？

K-means算法最優(yōu)k值的選取方法

K-Medians聚類算法K-Means算法存在一個(gè)問(wèn)題，就是當(dāng)數(shù)據(jù)中出現(xiàn)了某些數(shù)據(jù)偏離整體數(shù)據(jù)很遠(yuǎn)時(shí)，會(huì)給算數(shù)平均值帶來(lái)不利影響。比如，某公司有五個(gè)人的年薪是5萬(wàn)元，但是有另外一個(gè)人的年薪高達(dá)100萬(wàn)，那么年薪中間值會(huì)是5萬(wàn)（能代表公司的年薪情況），而平均值達(dá)到了20萬(wàn)（完全不能代表公司薪資情況）！這種問(wèn)題當(dāng)然也會(huì)在K-Means算法中發(fā)生。一個(gè)解決辦法就是使用K-Medians算法代替K-Means算法，二者算法相似，只是用中值代替平均值有十個(gè)點(diǎn)：1.（3,8）；2.（3,6）；3.（3,4）；4.（4,5）；5.（4,7）；6.（5,1）；7.（5,5）；8.（7,3）；9.（7，5）；10.（8,5）。將這10個(gè)點(diǎn)劃分為兩個(gè)類。首先，選取兩個(gè)初始的中心點(diǎn)為3號(hào)，和6號(hào)。然后，用曼哈頓距離公式為他們進(jìn)行劃分

C#1(3,4)C#2(5,1)

1.（3,8）4912.（3,6）2714.（4,5）2515.（4,7）4717.（5,5）3418.（7,3）5429.（7,5）56110.（8,5）671圖5-5第一次聚類后結(jié)果對(duì)第一類點(diǎn)集重新排列：（3,8）；（3,6）；（3,4）；（4,5）；（4,7）；（5,5）；（7,5）；（8,5）。對(duì)橫坐標(biāo)排序之后的中位數(shù)是4，對(duì)縱坐標(biāo)排序之后的中位數(shù)是5，這個(gè)時(shí)候第一類的中心點(diǎn)就變成了（4,5）第二類的點(diǎn)集是（5,1）和（7,3），中心點(diǎn)就是（6,2）

C#1(4,5)C#2(6,2)

1.（3,8）4912.（3,6）2713.（3,4）2514.（4,5）0515.（4,7）2716.（5,1）5227.（5,5）1418.（7,3）5229.（7,5）34110.（8,5）451

C#1(3,4)C#2(5,1)

1.（3,8）4912.（3,6）2714.（4,5）2515.（4,7）4717.（5,5