聚類方法(Clustering).ppt

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