聚類方法(Clustering).ppt

聚類方法（Clustering）,統(tǒng)研會學術交流篇之,演講人： 上海財經(jīng)大學統(tǒng)計學系 呂江平,主講內(nèi)容,聚類方法原理介紹 案例分析（SAS/Enterprise Miner） 推薦參考書目,什么是聚類,聚類（Clustering）就是將數(shù)據(jù)分組成為多個類（Cluster）。在同一個類內(nèi)對象之間具有較高的相似度，不同類之間的對象差別較大。,什么是聚類,早在孩提時代，人就通過不斷改進下意識中的聚類模式來學會如何區(qū)分貓和狗，動物和植物,聚類分析無處不在,誰經(jīng)常光顧商店，誰買什么東西，買多少？ 按忠誠卡記錄的光臨次數(shù)、光臨時間、性別、年齡、職業(yè)、購物種類、金額等變量分類 這樣商店可以. 識別顧客購買模式（如喜歡一大早來買酸奶和鮮肉，習慣周末時一次性大采購） 刻畫不同的客戶群的特征（用變量來刻畫，就象刻畫貓和狗的特征一樣）,什么情況下需要聚類,為什么這樣分類？ 因為每一個類別里面的人消費方式都不一樣，需要針對不同的人群，制定不同的關系管理方式，以提高客戶對公司商業(yè)活動的相應率。,聚類分析無處不在,挖掘有價值的客戶，并制定相應的促銷策略： 如，對經(jīng)常購買酸奶的客戶 對累計消費達到12個月的老客戶 針對潛在客戶派發(fā)廣告，比在大街上亂發(fā)傳單命中率更高，成本更低！,聚類分析無處不在,誰是銀行信用卡的黃金客戶？ 利用儲蓄額、刷卡消費金額、誠信度等變量對客戶分類，找出“黃金客戶”！ 這樣銀行可以 制定更吸引的服務，留住客戶！比如： 一定額度和期限的免息透資服務！ 百盛的貴賓打折卡！ 在他或她生日的時候送上一個小蛋糕！,聚類的應用領域,經(jīng)濟領域： 幫助市場分析人員從客戶數(shù)據(jù)庫中發(fā)現(xiàn)不同的客戶群，并且用購買模式來刻畫不同的客戶群的特征。 誰喜歡打國際長途，在什么時間，打到那里？ 對住宅區(qū)進行聚類，確定自動提款機ATM的安放位置 股票市場板塊分析，找出最具活力的板塊龍頭股 企業(yè)信用等級分類 生物學領域 推導植物和動物的分類； 對基因分類，獲得對種群的認識 數(shù)據(jù)挖掘領域 作為其他數(shù)學算法的預處理步驟，獲得數(shù)據(jù)分布狀況，集中對特定的類做進一步的研究,有貢獻的研究領域,數(shù)據(jù)挖掘 聚類可伸縮性、各種各種復雜形狀類的識別，高維聚類等 統(tǒng)計學 主要集中在基于距離的聚類分析，發(fā)現(xiàn)球狀類 機器學習 無指導學習（聚類不依賴預先定義的類，不等同于分類） 空間數(shù)據(jù)技術 生物學 市場營銷學,什么情況下需要聚類,以上分析，沒有大量的數(shù)據(jù)去支持，Data Mining就什么都挖不出來。 大量的數(shù)據(jù)不等于大量的垃圾，我們需要針對客戶市場細分所需要的資料。如需要知道白金持卡人和金卡持卡人的流動率，各自平均消費水平有多少，等； 聚類分析可以輔助企業(yè)進行客戶細分，但是Data mining的客戶細分不等同于商業(yè)領域的細分，看不懂結果，也可能造成企業(yè)管理層無法對結果善加利用。,聚類分析原理介紹,聚類分析中“類”的特征： 聚類所說的類不是事先給定的，而是根據(jù)數(shù)據(jù)的相似性和距離來劃分 聚類的數(shù)目和結構都沒有事先假定,聚類分析原理介紹,聚類方法的目的是尋找數(shù)據(jù)中： 潛在的自然分組結構a structure of “natural” grouping 感興趣的關系relationship,聚類分析原理介紹,什么是自然分組結構Natural grouping ? 我們看看以下的例子： 有16張牌 如何將他們分為 一組一組的牌呢？,聚類分析原理介紹,分成四組 每組里花色相同 組與組之間花色相異,花色相同的牌為一副 Individual suits,聚類分析原理介紹,分成四組 符號相同的牌為一組,符號相同的的牌 Like face cards,聚類分析原理介紹,分成兩組 顏色相同的牌為一組,顏色相同的配對 Black and red suits,聚類分析原理介紹,分成兩組 大小程度相近的牌分到一組,大配對和小配對 Major and minor suits,聚類分析原理介紹,這個例子告訴我們，分組的意義在于我們怎么定義并度量“相似性”Similar 因此衍生出一系列度量相似性的算法,大配對和小配對 Major and minor suits,聚類分析原理介紹,相似性Similar的度量（統(tǒng)計學角度） 距離Q型聚類（主要討論） 主要用于對樣本分類 常用的距離有（只適用于具有間隔尺度變量的聚類）： 明考夫斯基距離（包括：絕對距離、歐式距離、切比雪夫距離） 蘭氏距離 馬氏距離 斜交空間距離 此不詳述，有興趣可參考應用多元分析（第二版）王學民 相似系數(shù)R型聚類 用于對變量分類，可以用變量之間的相似系數(shù)的變形如1rij定義距離 這里不詳細介紹這種聚類度量方法,聚類分析原理介紹,變量按測量尺度（Measurement Level）分類 間隔（Interval）尺度變量 連續(xù)變量，如長度、重量、速度、溫度等 有序（Ordinal）尺度變量 等級變量，不可加，但可比，如一等、二等、三等獎學金 名義（Nominal）尺度變量 類別變量，不可加也不可比，如性別、職業(yè)等,當對象是同時被各種類型的變量描述時，怎樣描述對象之間的相異度呢？ 一種可取的辦法是把所有變量一起處理，將不同類型的變量組合在單個相異矩陣中，把所有有意義的變量轉(zhuǎn)換到【0，1】的區(qū)間上，只進行一次聚類分析。詳見參考書,主要聚類算法的分類,層次的方法（也稱系統(tǒng)聚類法）（hierarchical method） 劃分方法（partitioning method） 基于密度的方法（density-based method） 基于網(wǎng)格的方法（grid-based method） 基于模型的方法（model-based method） 其中，前兩種算法是利用統(tǒng)計學定義的距離進行度量,層次的方法（也稱系統(tǒng)聚類法）（hierarchical method）,定義：對給定的數(shù)據(jù)進行層次的分解： 分類： 凝聚的（agglomerative）方法（自底向上）（案例介紹） 思想：一開始將每個對象作為單獨的一組，然后根據(jù)同類相近，異類相異的原則，合并對象，直到所有的組合并成一個，或達到一個終止條件為止。 分裂的方法（divisive）（自頂向下） 思想：一開始將所有的對象置于一類，在迭代的每一步中，一個類不斷地分為更小的類，直到每個對象在單獨的一個類中，或達到一個終止條件。,層次的方法（也稱系統(tǒng)聚類法）（hierarchical method）,特點： 類的個數(shù)不需事先定好 需確定距離矩陣 運算量要大，適用于處理小樣本數(shù)據(jù),廣泛采用的類間距離：,最小距離法（single linkage method） 極小異常值在實際中不多出現(xiàn)，避免極大值的影響,廣泛采用的類間距離：,最大距離法（complete linkage method） 可能被極大值扭曲，刪除這些值之后再聚類,廣泛采用的類間距離：,類平均距離法（average linkage method）類間所有樣本點的平均距離 該法利用了所有樣本的信息，被認為是較好的系統(tǒng)聚類法,廣泛采用的類間距離：,重心法（centroid hierarchical method） 類的重心之間的距離 對異常值不敏感，結果更穩(wěn)定,廣泛采用的類間距離,離差平方和法（ward method） D2=WMWKWL 即 對異常值很敏感；對較大的類傾向產(chǎn)生較大的距離，從而不易合并，較符合實際需要。,層次的方法缺陷：,一旦一個步驟（合并或分裂）完成，就不能被撤銷或修正，因此產(chǎn)生了改進的層次聚類方法，如BRICH,BURE,ROCK,Chameleon。詳見參考書,劃分方法（Partitioning method）,較流行的方法有: 動態(tài)聚類法（也稱逐步聚類法），如k均值算法、k中心點算法 思想： 隨機選擇k個對象，每個對象初始地代表一個類的平均值或中心，對剩余每個對象，根據(jù)其到類中心的距離，被劃分到最近的類；然后重新計算每個類的平均值。不斷重復這個過程，直到所有的樣本都不能再分配為止。（圖解）,劃分方法（Partitioning method）,特點： k事先定好 創(chuàng)建一個初始劃分，再采用迭代的重定位技術 不必確定距離矩陣 比系統(tǒng)聚類法運算量要小，適用于處理龐大的樣本數(shù)據(jù) 適用于發(fā)現(xiàn)球狀類,劃分方法（Partitioning method）,缺陷： 不同的初始值，結果可能不同 有些k均值算法的結果與數(shù)據(jù)輸入順序有關，如在線k均值算法 用爬山式技術（hill-climbing）來尋找最優(yōu)解，容易陷入局部極小值,基于距離的方法進行聚類只能發(fā)現(xiàn)球狀類，當類的形狀是任意的時候怎么識別？（黑板圖示） 下面介紹其中一種常用的算法：,基于密度的方法 （density-based method）,主要有DBSCAN，OPTICS法 思想： 只要臨近區(qū)域的密度超過一定的閥值，就繼續(xù)聚類 特點： 可以過濾噪聲和孤立點outlier，發(fā)現(xiàn)任意形狀的類,基于網(wǎng)格的方法 （grid-based method）,把樣本空間量化為有限數(shù)目的單元，形成一個網(wǎng)絡結構，聚類操作都在這個網(wǎng)格結構（即量化空間）上進行,基于模型的方法 （model-based method）,為每個類假定一個模型，尋找數(shù)據(jù)對給定模型的最佳擬合。 此不詳述，有興趣可以參考DataMing Concepts and Techniques即數(shù)據(jù)挖掘概念于技術Jiawei Han Micheline Kamber機械工業(yè)出版社,不穩(wěn)定的聚類方法,受所選擇變量的影響 如果去掉或者增加一些變量,結果會很不同.因此，聚類之前一定要明確目標，選擇有意義的變量。 變量之間的相關性也會影響聚類結果，因此可以先用主成分或因子分析法把眾多變量壓縮為若干個相互獨立的并包含大部分信息的指標，然后再進行聚類。,不穩(wěn)定的聚類方法,輸入?yún)?shù)憑主觀導致難以控制聚類的質(zhì)量 很多聚類算法要求輸入一定的參數(shù)，如希望產(chǎn)生的類的數(shù)目，使得聚類的質(zhì)量難以控制，尤其是對于高維的，沒有先驗信息的龐大數(shù)據(jù)。 首先要明確聚類的目的，就是要使各個類之間的距離盡可能遠，類中的距離盡可能近，聚類算法可以根據(jù)研究目的確定類的數(shù)目，但分類的結果要有令人信服的解釋。 在實際操作中，更多的是憑經(jīng)驗來確定類的數(shù)目，測試不同類數(shù)的聚類效果，直到選擇較理想的分類。,不穩(wěn)定的聚類方法,算法的選擇沒有絕對 當聚類結果被用作描述或探查工具時，可以對同樣的數(shù)據(jù)嘗試多種算法，以發(fā)現(xiàn)數(shù)據(jù)可能揭示的結果。,不穩(wěn)定的聚類方法,聚類分析中權重的確定 當各指標重要性不同的時候，需要根據(jù)需要調(diào)整權重。如加權歐式距離，權重可以用專家法確定。,案例演示,有一個電信公司的數(shù)據(jù)，變量為： ID：用戶電話號碼 Mobile：移動電話通話時間 Fixed：固定電話通話時間 DDD: 長途直撥通話時間 IP: IP電話通話時間 研究目的：挖掘不同人群撥打電話的特征 下面用SAS/Enterprise Miner演示,Q & A,推薦參考書目,應用多元分析（第二版）王學民 上海財經(jīng)大學出版社 應用多元統(tǒng)計分析即Appied Multivariate Satistics5th EdRichard A. Johnson, Dean W. Wichern中國統(tǒng)計出版社 數(shù)據(jù)倉庫即Building the Data Warehouse3th Ed，W.H.Inman機械工業(yè)出版社 數(shù)據(jù)挖掘原理Principles of Data MiningDavid Hand Heikki Mannila Padhraic Smgth機械工業(yè)出版社 Data Mining Introduction and Advanced TopicsMargaret H.Dunh