聚類方法Clustering課件

1、聚類方法clustering聚類方法（clustering）統(tǒng)研會學(xué)術(shù)交流篇之聚類方法clustering主講內(nèi)容 聚類方法原理介紹 案例分析（sas/enterprise miner） 推薦參考書目聚類方法clustering什么是聚類 聚類（clustering）就是將數(shù)據(jù)分組成為多個類（cluster）。在同一個類內(nèi)對象之間具有較高的相似度，不同類之間的對象差別較大。聚類方法clustering什么是聚類 早在孩提時代，人就通過不斷改進下意識中的聚類模式來學(xué)會如何區(qū)分貓和狗，動物和植物聚類方法clustering聚類分析無處不在 誰經(jīng)常光顧商店，誰買什么東西，買多少？ 按忠誠卡記錄的光臨

2、次數(shù)、光臨時間、性別、年齡、職業(yè)、購物種類、金額等變量分類 這樣商店可以. 識別顧客購買模式（如喜歡一大早來買酸奶和鮮肉，習(xí)慣周末時一次性大采購） 刻畫不同的客戶群的特征（用變量來刻畫，就象刻畫貓和狗的特征一樣）聚類方法clustering什么情況下需要聚類 為什么這樣分類？ 因為每一個類別里面的人消費方式都不一樣，需要針對不同的人群，制定不同的關(guān)系管理方式，以提高客戶對公司商業(yè)活動的相應(yīng)率。聚類方法clustering聚類分析無處不在 挖掘有價值的客戶，并制定相應(yīng)的促銷策略： 如，對經(jīng)常購買酸奶的客戶 對累計消費達到12個月的老客戶 針對潛在客戶派發(fā)廣告，比在大街上亂發(fā)傳單命中率更高，成本更

3、低！聚類方法clustering聚類分析無處不在 誰是銀行信用卡的黃金客戶？ 利用儲蓄額、刷卡消費金額、誠信度等變量對客戶分類，找出“黃金客戶”！ 這樣銀行可以 制定更吸引的服務(wù)，留住客戶！比如： 一定額度和期限的免息透資服務(wù)！ 百盛的貴賓打折卡！ 在他或她生日的時候送上一個小蛋糕！聚類方法clustering聚類的應(yīng)用領(lǐng)域 經(jīng)濟領(lǐng)域： 幫助市場分析人員從客戶數(shù)據(jù)庫中發(fā)現(xiàn)不同的客戶群，并且用購買模式來刻畫不同的客戶群的特征。 誰喜歡打國際長途，在什么時間，打到那里？ 對住宅區(qū)進行聚類，確定自動提款機atm的安放位置 股票市場板塊分析，找出最具活力的板塊龍頭股 企業(yè)信用等級分類 生物學(xué)領(lǐng)域 推導(dǎo)

4、植物和動物的分類； 對基因分類，獲得對種群的認識 數(shù)據(jù)挖掘領(lǐng)域 作為其他數(shù)學(xué)算法的預(yù)處理步驟，獲得數(shù)據(jù)分布狀況，集中對特定的類做進一步的研究聚類方法clustering有貢獻的研究領(lǐng)域 數(shù)據(jù)挖掘 聚類可伸縮性、各種各種復(fù)雜形狀類的識別，高維聚類等 統(tǒng)計學(xué) 主要集中在基于距離的聚類分析，發(fā)現(xiàn)球狀類 機器學(xué)習(xí) 無指導(dǎo)學(xué)習(xí)（聚類不依賴預(yù)先定義的類，不等同于分類） 空間數(shù)據(jù)技術(shù) 生物學(xué) 市場營銷學(xué)聚類方法clustering什么情況下需要聚類 以上分析，沒有大量的數(shù)據(jù)去支持，data mining就什么都挖不出來。 大量的數(shù)據(jù)不等于大量的垃圾，我們需要針對客戶市場細分所需要的資料。如需要知道白金持卡人

5、和金卡持卡人的流動率，各自平均消費水平有多少，等； 聚類分析可以輔助企業(yè)進行客戶細分，但是data mining的客戶細分不等同于商業(yè)領(lǐng)域的細分，看不懂結(jié)果，也可能造成企業(yè)管理層無法對結(jié)果善加利用。聚類方法clustering聚類分析原理介紹 聚類分析中“類”的特征： 聚類所說的類不是事先給定的，而是根據(jù)數(shù)據(jù)的相似性和距離來劃分 聚類的數(shù)目和結(jié)構(gòu)都沒有事先假定聚類方法clustering聚類分析原理介紹 聚類方法的目的是尋找數(shù)據(jù)中： 潛在的自然分組結(jié)構(gòu)a structure of “natural” grouping 感興趣的關(guān)系relationship聚類方法clustering聚類分析原理

6、介紹 什么是自然分組結(jié)構(gòu)natural grouping ? 我們看看以下的例子： 有16張牌 如何將他們分為 一組一組的牌呢？akqj聚類方法clustering聚類分析原理介紹 分成四組 每組里花色相同 組與組之間花色相異akqj花色相同的牌為一副花色相同的牌為一副individual suits聚類方法clustering聚類分析原理介紹 分成四組 符號相同的牌為一組akqj符號相同的的牌符號相同的的牌like face cards聚類方法clustering聚類分析原理介紹 分成兩組 顏色相同的牌為一組akqj顏色相同的配對顏色相同的配對black and red suits聚類方法c

7、lustering聚類分析原理介紹 分成兩組 大小程度相近的牌分到一組akqj大配對和小配對大配對和小配對major and minor suits聚類方法clustering聚類分析原理介紹 這個例子告訴我們，分組的意義在于我們怎么定義并度量“相似性”similar 因此衍生出一系列度量相似性的算法akqj大配對和小配對大配對和小配對major and minor suits聚類方法clustering聚類分析原理介紹相似性similar的度量（統(tǒng)計學(xué)角度） 距離q型聚類（主要討論） 主要用于對樣本分類 常用的距離有（只適用于具有間隔尺度變量的聚類）： 明考夫斯基距離（包括：絕對距離、歐式距

8、離、切比雪夫距離） 蘭氏距離 馬氏距離 斜交空間距離 此不詳述，有興趣可參考應(yīng)用多元分析（第二版）王學(xué)民 相似系數(shù)r型聚類 用于對變量分類，可以用變量之間的相似系數(shù)的變形如1rij定義距離 這里不詳細介紹這種聚類度量方法聚類方法clustering聚類分析原理介紹變量按測量尺度（measurement level）分類 間隔（interval）尺度變量 連續(xù)變量，如長度、重量、速度、溫度等 有序（ordinal）尺度變量 等級變量，不可加，但可比，如一等、二等、三等獎學(xué)金 名義（nominal）尺度變量 類別變量，不可加也不可比，如性別、職業(yè)等聚類方法clustering 當對象是同時被各種類

9、型的變量描述時，怎樣描述對象之間的相異度呢？ 一種可取的辦法是把所有變量一起處理，將不同類型的變量組合在單個相異矩陣中，把所有有意義的變量轉(zhuǎn)換到【0，1】的區(qū)間上，只進行一次聚類分析。詳見參考書聚類方法clustering主要聚類算法的分類層次的方法（層次的方法（也稱系統(tǒng)聚類法）（系統(tǒng)聚類法）（hierarchical hierarchical methodmethod）劃分方法（劃分方法（partitioning methodpartitioning method）基于密度的方法（基于密度的方法（density-based methoddensity-based method）基于網(wǎng)格的方法

10、（基于網(wǎng)格的方法（grid-based methodgrid-based method）基于模型的方法（基于模型的方法（model-based methodmodel-based method）其中，前兩種算法是利用其中，前兩種算法是利用統(tǒng)計學(xué)定義的距離統(tǒng)計學(xué)定義的距離進行度量進行度量聚類方法clustering層次的方法（也稱系統(tǒng)聚類法）（hierarchical method） 定義：對給定的數(shù)據(jù)進行層次的分解：定義：對給定的數(shù)據(jù)進行層次的分解： 分類：分類：凝聚的（凝聚的（agglomerativeagglomerative）方法（自底向上）（案例介紹）方法（自底向上）（案例介紹）思想：

11、一開始將每個對象作為單獨的一組，然后根據(jù)同類思想：一開始將每個對象作為單獨的一組，然后根據(jù)同類相近，異類相異的原則，合并對象，直到所有的組合并成相近，異類相異的原則，合并對象，直到所有的組合并成一個，或達到一個終止條件為止。一個，或達到一個終止條件為止。分裂的方法（分裂的方法（divisivedivisive）（自頂向下）（自頂向下）思想：一開始將所有的對象置于一類，在迭代的每一步中，思想：一開始將所有的對象置于一類，在迭代的每一步中，一個類不斷地分為更小的類，直到每個對象在單獨的一個一個類不斷地分為更小的類，直到每個對象在單獨的一個類中，或達到一個終止條件。類中，或達到一個終止條件。 聚類方

12、法clustering層次的方法（也稱系統(tǒng)聚類法）（hierarchical method） 特點：特點： 類的個數(shù)不需事先定好類的個數(shù)不需事先定好 需確定距離矩陣需確定距離矩陣 運算量要大，適用于處理小樣本數(shù)據(jù)運算量要大，適用于處理小樣本數(shù)據(jù) 聚類方法clustering廣泛采用的類間距離： 最小距離法（single linkage method） 極小異常值在實際中不多出現(xiàn)，避免極大值的影響 聚類方法clustering廣泛采用的類間距離： 最大距離法（complete linkage method） 可能被極大值扭曲，刪除這些值之后再聚類聚類方法clustering廣泛采用的類間距離：

13、類平均距離法（average linkage method）類間所有樣本點的平均距離 該法利用了所有樣本的信息，被認為是較好的系統(tǒng)聚類法聚類方法clustering廣泛采用的類間距離： 重心法（重心法（centroid hierarchical methodcentroid hierarchical method） 類的重心之間的距離類的重心之間的距離 對異常值不敏感，結(jié)果更穩(wěn)定對異常值不敏感，結(jié)果更穩(wěn)定 聚類方法clustering廣泛采用的類間距離 離差平方和法（離差平方和法（ward methodward method） d2=wmwkwl 即 對異常值很敏感；對較大的類傾向產(chǎn)生較大的距

14、離，從而不易合并，較符合實際需要。 lklkmklklxxxxnnnd2cluster kcluster lcluster m聚類方法clustering層次的方法缺陷： 一旦一個步驟（合并或分裂）完成，就不能被撤銷或修正，因此產(chǎn)生了改進的層次聚類方法，如brich,bure,rock,chameleon。詳見參考書 聚類方法clustering劃分方法（partitioning method） 較流行的方法有較流行的方法有: : 動態(tài)聚類法（也稱逐步聚類法），如k均值算法、k中心點算法 思想：思想： 隨機選擇k個對象，每個對象初始地代表一個類的平均平均值值或中心中心，對剩余每個對象，根據(jù)其到

15、類中心的距離，被劃分到最近的類；然后重新計算每個類的平均值。不斷重復(fù)這個過程，直到所有的樣本都不能再分配為止。（圖解） 聚類方法clustering劃分方法（partitioning method） 特點：特點： k k事先定好事先定好 創(chuàng)建一個初始劃分，再采用迭代的重定位技術(shù)創(chuàng)建一個初始劃分，再采用迭代的重定位技術(shù) 不必確定距離矩陣不必確定距離矩陣 比系統(tǒng)聚類法運算量要小，適用于處理龐大的樣本數(shù)據(jù)比系統(tǒng)聚類法運算量要小，適用于處理龐大的樣本數(shù)據(jù) 適用于發(fā)現(xiàn)球狀類適用于發(fā)現(xiàn)球狀類聚類方法clustering劃分方法（partitioning method） 缺陷：缺陷： 不同的初始值，結(jié)果可能

16、不同不同的初始值，結(jié)果可能不同 有些有些k k均值算法的結(jié)果與數(shù)據(jù)輸入順序有關(guān)，如在線均值算法的結(jié)果與數(shù)據(jù)輸入順序有關(guān)，如在線k k均值算法均值算法 用爬山式技術(shù)（用爬山式技術(shù)（hill-climbinghill-climbing）來尋找最優(yōu)解，容易陷入局部極小值）來尋找最優(yōu)解，容易陷入局部極小值聚類方法clustering 基于距離的方法進行聚類只能發(fā)現(xiàn)球狀類，當類的形狀是任意的基于距離的方法進行聚類只能發(fā)現(xiàn)球狀類，當類的形狀是任意的時候怎么識別？（黑板圖示）時候怎么識別？（黑板圖示） 下面介紹其中一種常用的算法：下面介紹其中一種常用的算法：聚類方法clustering基于密度的方法（den

17、sity-based method） 主要有dbscan，optics法 思想：思想： 只要臨近區(qū)域的密度超過一定的閥值，就繼續(xù)聚類 特點：特點： 可以過濾噪聲和孤立點outlier，發(fā)現(xiàn)任意形狀的類聚類方法clustering基于網(wǎng)格的方法（grid-based method） 把樣本空間量化為有限數(shù)目的單元，形成一個網(wǎng)絡(luò)結(jié)構(gòu)，聚類操作都在這個網(wǎng)格結(jié)構(gòu)（即量化空間）上進行 聚類方法clustering基于模型的方法（model-based method） 為每個類假定一個模型，尋找數(shù)據(jù)對給定模型的最佳擬合。 此不詳述，有興趣可以參考dataming concepts and techniqu

18、es即數(shù)據(jù)挖掘概念于技術(shù)jiawei han micheline kamber機械工業(yè)出版社聚類方法clustering不穩(wěn)定的聚類方法受所選擇變量的影響受所選擇變量的影響如果去掉或者增加一些變量如果去掉或者增加一些變量, ,結(jié)果會很不同結(jié)果會很不同. .因此，聚類之前一定要明因此，聚類之前一定要明確目標，選擇有意義的變量。確目標，選擇有意義的變量。變量之間的相關(guān)性也會影響聚類結(jié)果，因此可以先用主成分或因子分變量之間的相關(guān)性也會影響聚類結(jié)果，因此可以先用主成分或因子分析法把眾多變量壓縮為若干個相互獨立的并包含大部分信息的指標，析法把眾多變量壓縮為若干個相互獨立的并包含大部分信息的指標，然后再進

19、行聚類。然后再進行聚類。聚類方法clustering不穩(wěn)定的聚類方法輸入?yún)?shù)憑主觀導(dǎo)致難以控制聚類的質(zhì)量輸入?yún)?shù)憑主觀導(dǎo)致難以控制聚類的質(zhì)量很多聚類算法要求輸入一定的參數(shù)，如希望產(chǎn)生的類的數(shù)目，使得聚很多聚類算法要求輸入一定的參數(shù)，如希望產(chǎn)生的類的數(shù)目，使得聚類的質(zhì)量難以控制，尤其是對于高維的，沒有先驗信息的龐大數(shù)據(jù)。類的質(zhì)量難以控制，尤其是對于高維的，沒有先驗信息的龐大數(shù)據(jù)。首先要明確聚類的目的，就是要使各個類之間的距離盡可能遠，類中首先要明確聚類的目的，就是要使各個類之間的距離盡可能遠，類中的距離盡可能近，聚類算法可以根據(jù)研究目的確定類的數(shù)目，但分類的距離盡可能近，聚類算法可以根據(jù)研究目的

20、確定類的數(shù)目，但分類的結(jié)果要有令人信服的解釋。的結(jié)果要有令人信服的解釋。在實際操作中，更多的是憑經(jīng)驗來確定類的數(shù)目，測試不同類數(shù)的聚在實際操作中，更多的是憑經(jīng)驗來確定類的數(shù)目，測試不同類數(shù)的聚類效果，直到選擇較理想的分類。類效果，直到選擇較理想的分類。聚類方法clustering不穩(wěn)定的聚類方法算法的選擇沒有絕對算法的選擇沒有絕對當聚類結(jié)果被用作描述或探查工具時，可以對同樣的數(shù)據(jù)嘗試多種算當聚類結(jié)果被用作描述或探查工具時，可以對同樣的數(shù)據(jù)嘗試多種算法，以發(fā)現(xiàn)數(shù)據(jù)可能揭示的結(jié)果。法，以發(fā)現(xiàn)數(shù)據(jù)可能揭示的結(jié)果。 聚類方法clustering不穩(wěn)定的聚類方法 聚類分析中權(quán)重的確定聚類分析中權(quán)重的確定 當各指標重要性不同的時候，需要根據(jù)需要調(diào)整權(quán)重。如加權(quán)歐式距離，當各指標重要性不同的時候，需要根據(jù)需要調(diào)整權(quán)重。如加權(quán)歐式距離，權(quán)重可以用專家法確定。權(quán)重可以用專家法確定。 聚類方法clustering案例演示 有一個電信公司的數(shù)據(jù)，變量為： id：用戶電話號碼 mobile：移動電話通話時間 fixed：固定電話通話時間 ddd: 長途直撥通話時間 ip: ip電話通話時間 研究目的：挖掘不同人群撥打電話的特