決策支持系統(tǒng)與商務智能：第六章 聚類分析

聚類分析§6.1引言§6.2距離和相似系數§6.3系統(tǒng)聚類法§6.4動態(tài)聚類法12/4/20231§6.1引言12/4/20232什么是聚類聚類（Clustering）就是將數據分組成為多個類（Cluster）。在同一個類內對象之間具有較高的相似度，不同類之間的對象差別較大。12/4/20233什么是聚類早在孩提時代，人就通過不斷改進下意識中的聚類模式來學會如何區(qū)分貓和狗，動物和植物12/4/20234聚類分析無處不在誰經常光顧商店，誰買什么東西，買多少？按忠誠卡記錄的光臨次數、光臨時間、性別、年齡、職業(yè)、購物種類、金額等變量分類這樣商店可以….識別顧客購買模式（如喜歡一大早來買酸奶和鮮肉，習慣周末時一次性大采購）刻畫不同的客戶群的特征（用變量來刻畫，就象刻畫貓和狗的特征一樣）12/4/20235什么情況下需要聚類為什么這樣分類？因為每一個類別里面的人消費方式都不一樣，需要針對不同的人群，制定不同的關系管理方式，以提高客戶對公司商業(yè)活動的相應率。12/4/20236聚類分析無處不在挖掘有價值的客戶，并制定相應的促銷策略：如，對經常購買酸奶的客戶對累計消費達到12個月的老客戶針對潛在客戶派發(fā)廣告，比在大街上亂發(fā)傳單命中率更高，成本更低！12/4/20237聚類分析無處不在誰是銀行信用卡的黃金客戶？利用儲蓄額、刷卡消費金額、誠信度等變量對客戶分類，找出“黃金客戶”！這樣銀行可以……制定更吸引的服務，留住客戶！比如：一定額度和期限的免息透資服務！百盛的貴賓打折卡！在他或她生日的時候送上一個小蛋糕！12/4/20238聚類的應用領域經濟領域：幫助市場分析人員從客戶數據庫中發(fā)現不同的客戶群，并且用購買模式來刻畫不同的客戶群的特征。誰喜歡打國際長途，在什么時間，打到那里？對住宅區(qū)進行聚類，確定自動提款機ATM的安放位置股票市場板塊分析，找出最具活力的板塊龍頭股企業(yè)信用等級分類……生物學領域推導植物和動物的分類；對基因分類，獲得對種群的認識數據挖掘領域作為其他數學算法的預處理步驟，獲得數據分布狀況，集中對特定的類做進一步的研究12/4/20239有貢獻的研究領域數據挖掘聚類可伸縮性、各種各種復雜形狀類的識別，高維聚類等統(tǒng)計學主要集中在基于距離的聚類分析，發(fā)現球狀類機器學習無指導學習（聚類不依賴預先定義的類，不等同于分類）空間數據技術生物學市場營銷學12/4/202310什么情況下需要聚類以上分析，沒有大量的數據去支持，DataMining就什么都挖不出來。大量的數據不等于大量的垃圾，我們需要針對客戶市場細分所需要的資料。如需要知道白金持卡人和金卡持卡人的流動率，各自平均消費水平有多少，等；聚類分析可以輔助企業(yè)進行客戶細分，但是Datamining的客戶細分不等同于商業(yè)領域的細分，看不懂結果，也可能造成企業(yè)管理層無法對結果善加利用。12/4/202311聚類分析原理介紹聚類分析中“類”的特征：聚類所說的類不是事先給定的，而是根據數據的相似性和距離來劃分聚類的數目和結構都沒有事先假定12/4/202312聚類分析原理介紹聚類方法的目的是尋找數據中：潛在的自然分組結構astructureof“natural”grouping感興趣的關系relationship12/4/202313聚類分析原理介紹什么是自然分組結構Naturalgrouping?我們看看以下的例子：有16張牌如何將他們分為一組一組的牌呢？AKQJ12/4/202314聚類分析原理介紹分成四組每組里花色相同組與組之間花色相異AKQJ花色相同的牌為一副Individualsuits12/4/202315聚類分析原理介紹分成四組符號相同的牌為一組AKQJ符號相同的的牌Likefacecards12/4/202316聚類分析原理介紹分成兩組顏色相同的牌為一組AKQJ顏色相同的配對Blackandredsuits12/4/202317聚類分析原理介紹分成兩組大小程度相近的牌分到一組AKQJ大配對和小配對Majorandminorsuits12/4/202318聚類分析原理介紹這個例子告訴我們，分組的意義在于我們怎么定義并度量“相似性”Similar因此衍生出一系列度量相似性的算法AKQJ大配對和小配對Majorandminorsuits12/4/202319§6.2距離和相似系數相似性度量：距離和相似系數。距離常用來度量樣品之間的相似性，相似系數常用來度量變量之間的相似性。樣品之間的距離和相似系數有著各種不同的定義，而這些定義與變量的類型有著非常密切的關系。12/4/202320變量的測量尺度通常變量按測量尺度的不同可以分為間隔、有序和名義尺度變量三類。間隔尺度變量：變量用連續(xù)的量來表示，如長度、重量、速度、溫度等。有序尺度變量：變量度量時不用明確的數量表示，而是用等級來表示，如某產品分為一等品、二等品、三等品等有次序關系。名義尺度變量：變量用一些類表示，這些類之間既無等級關系也無數量關系，如性別、職業(yè)、產品的型號等。本章主要討論具有間隔尺度變量的樣品聚類分析方法。12/4/20232112/4/202322距離有多種定義方法，在聚類分析中最常用的是歐氏距離，即有當各變量的單位不同或測量值范圍相差很大時，應先對各變量的數據作標準化處理。最常用的標準化處理是，令其中和分別為第個變量的樣本均值和樣本方差。12/4/202323二、相似系數聚類分析方法不僅用來對樣品進行分類，而且可用來對變量進行分類，在對變量進行分類時，常常采用相似系數來度量變量之間的相似性。變量之間的這種相似性度量，在一些應用中要看相似系數的大小，而在另一些應用中要看相似系數絕對值的大小。相似系數(或其絕對值)越大，認為變量之間的相似性程度就越高；反之，則越低。聚類時，比較相似的變量傾向于歸為一類，不太相似的變量歸屬不同的類。12/4/202324相似系數一般需滿足的條件（1），當且僅當和是常數；（2），對一切；（3），對一切。

12/4/202325最常用的兩個相似系數12/4/20232612/4/202327相似系數除常用來度量變量之間的相似性外有時也用來度量樣品之間的相似性，同樣，距離有時也用來度量變量之間的相似性。由距離來構造相似系數總是可能的，如令這里

為第個樣品與第

個樣品的距離，顯然

滿足定義相似系數的三個條件，故可作為相似系數。距離必須滿足定義距離的四個條件，所以不是總能由相似系數構造。高爾（Gower）證明，當相似系數矩陣為非負定時，如令則

滿足距離定義的四個條件。12/4/202328§6.3系統(tǒng)聚類法系統(tǒng)聚類法是聚類分析諸方法中用得最多的一種?；舅枷胧牵洪_始將個樣品各自作為一類，并規(guī)定樣品之間的距離和類與類之間的距離，然后將距離最近的兩類合并成一個新類，計算新類與其他類的距離；重復進行兩個最近類的合并，每次減少一類，直至所有的樣品合并為一類。12/4/202329常用的系統(tǒng)聚類方法一、最短距離法二、最長距離法三、中間距離法四、類平均法五、重心法六、離差平方和法(Ward方法)12/4/202330一、最短距離法定義類與類之間的距離為兩類最近樣品間的距離，即12/4/202331最短距離法的聚類步驟(1)規(guī)定樣品之間的距離，計算

個樣品的距離矩陣

，它是一個對稱矩陣。(2)選擇

中的最小元素，設為

，則將

和

合并成一個新類，記為

，即(3)計算新類

與任一類

之間距離的遞推公式為12/4/202332最短距離法的聚類步驟在中，

和

所在的行和列合并成一個新行新列，對應

，該行列上的新距離值由（6.3.2）式求得，其余行列上的距離值不變，這樣就得到新的距離矩陣，記作

。(4)對

重復上述對

的兩步得

，如此下去直至所有元素合并成一類為止。如果某一步中最小的元素不止一個，則稱此現象為結(tie)，對應這些最小元素的類可以任選一對合并或同時合并。12/4/20233312/4/20233412/4/20233512/4/202336二、最長距離法類與類之間的距離定義為兩類最遠樣品間的距離，即12/4/202337最長距離法與最短距離法的并類步驟完全相同，只是類間距離的遞推公式有所不同。遞推公式：最長距離法容易被異常值嚴重地扭曲，一個有效的方法是將這些異常值單獨拿出來后再進行聚類。12/4/20233812/4/202339三、中間距離法類與類之間的距離既不取兩類最近樣品間的距離，也不取兩類最遠樣品間的距離，而是取介于兩者中間的距離。12/4/20234012/4/20234112/4/20234212/4/20234312/4/20234412/4/20234512/4/20234612/4/20234712/4/20234812/4/20234912/4/202350以上我們對例6.3.1采用了多種系統(tǒng)聚類法進行聚類，其結果都是相同的，原因是該例只有很少幾個樣品，此時聚類的過程不易有什么變化。一般來說，只要聚類的樣品數目不是太少，各種聚類方法所產生的聚類結果一般是不同的，甚至會有大的差異。從下面例子中可以看到這一點。12/4/20235112/4/20235212/4/20235312/4/20235412/4/202355從這三個樹形圖來看，只有Ward方法較好地符合了我們的實際聚類要求，它將31個地區(qū)分為以下三類：第Ⅰ類：北京、浙江、上海和廣東。這些都是我國經濟最發(fā)達、城鎮(zhèn)居民消費水平最高的沿海地區(qū)。第Ⅱ類：天津、江蘇、云南、重慶、河北、新疆、山東、湖北、四川、湖南、福建、廣西、海南和西藏。這些地區(qū)在我國基本上屬于經濟發(fā)展水平和城鎮(zhèn)居民消費水平中等的地區(qū)。第Ⅲ類：山西、甘肅、內蒙古、遼寧、黑龍江、吉林、青海、寧夏、安徽、貴州、河南、陜西和江西。這些地區(qū)在我國基本上屬于經濟較落后地區(qū)，城鎮(zhèn)居民的消費水平也是較低的。如果分為五類，則廣東和西藏將各自為一類。12/4/202356單調性令

是系統(tǒng)聚類法中第

次并類時的距離，如果一種系統(tǒng)聚類法能滿足

，則稱它具有單調性。這種單調性符合系統(tǒng)聚類法的思想，先合并較相似的類，后合并較疏遠的類。最短距離法、最長距離法、可變法、類平均法、可變類平均法和離差平方和法都具有單調性，但中間距離法和重心法不具有單調性。12/4/202357類的個數如果能夠分成若干個很分開的類，則類的個數就比較容易確定；反之，如果無論怎樣分都很難分成明顯分開的若干類，則類個數的確定就比較困難了。確定類個數的常用方法有：

1.給定一個閾值T。

2.觀測樣品的散點圖。

3.使用統(tǒng)計量。包括：統(tǒng)計量，半偏統(tǒng)計量，偽統(tǒng)計量和偽統(tǒng)計量。12/4/202358§6.4動態(tài)聚類法動態(tài)聚類法的基本思想是，選擇一批凝聚點或給出一個初始的分類，讓樣品按某種原則向凝聚點凝聚，對凝聚點進行不斷的修改或迭代，直至分類比較合理或迭代穩(wěn)定為止。類的個數k可以事先指定，也可以在聚類過程中確定。選擇初始凝聚點(或給出初始分類)的一種簡單方法是采用隨機抽選(或隨機分割)樣品的方法。動態(tài)聚類法有許多種方法，本節(jié)中，只討論一種比較流行的動態(tài)聚類法——k均值法。k均值法是由麥奎因(MacQueen,1967)提出并命名的一種算法。12/4/202359k均值法的基本步驟(1)選擇k個樣品作為初始凝聚點，或者將所有樣品分成k