人工智能聚類分析作業(yè)

聚類方法（Clustering）人工智能技術(shù)導(dǎo)論——張少宏廣州大學(xué)計(jì)算機(jī)學(xué)院內(nèi)容1.聚類方法原理介紹1.1什么是聚類1.2為什么聚類1.3聚類問(wèn)題特征1.4主要聚類算法的分類1.5聚類方法的不穩(wěn)定性2.案例分析心肌細(xì)胞數(shù)據(jù)聚類（層次聚類，Kmeans）中國(guó)男足近幾年到底在亞洲處于幾流水平？（Kmeans）某移動(dòng)公司客戶細(xì)分模型（Kmeans，使用SPSS）3.推薦參考書目1.聚類方法原理介紹1.1什么是聚類1.2為什么聚類1.3聚類問(wèn)題特征1.4主要聚類算法的分類1.5聚類方法的不穩(wěn)定性1.1什么是聚類聚類（Clustering）就是在沒(méi)有指導(dǎo)信息下將數(shù)據(jù)分組成為多個(gè)類（Cluster，一般也譯為簇）。最大特點(diǎn)：沒(méi)有指導(dǎo)信息（無(wú)監(jiān)督學(xué)習(xí)）最大化類內(nèi)相似度，最小化類間相似度或者最大化類間距離，最小化類內(nèi)距離。分類和聚類的區(qū)別分類：有指導(dǎo)信息（訓(xùn)練集）相關(guān)生活例子：教小孩認(rèn)車牌聚類：沒(méi)有指導(dǎo)信息相關(guān)生活例子：課程設(shè)計(jì)組隊(duì)聚類分析舉例1“物以類聚，人以群分”聚類分析舉例2誰(shuí)經(jīng)常光顧商店，誰(shuí)買什么東西，買多少？按會(huì)員卡記錄的光臨次數(shù)、光臨時(shí)間、性別、年齡、職業(yè)、購(gòu)物種類、金額等變量分類這樣商店可以….識(shí)別不同顧客群的購(gòu)買模式（如喜歡一大早來(lái)買酸奶和鮮肉，習(xí)慣周末時(shí)一次性大采購(gòu)）刻畫不同的客戶群的特征指定不同的促銷計(jì)劃一般沒(méi)有事先設(shè)定的客戶群性質(zhì)類別這正是聚類分析的目的所在聚類分析舉例3原標(biāo)題：Kmeans聚類算法應(yīng)用實(shí)例：中國(guó)男足近幾年到底在亞洲處于幾流水平？/leoo2sk/archive/2010/09/20/k-means.html

假設(shè)以世界杯和亞洲杯成績(jī)作為特征，以Kmeans算法聚類，類數(shù)為3。結(jié)果收斂如下：（1）日本，韓國(guó)，伊朗，沙特（2）烏茲別克斯坦，巴林，朝鮮（3）中國(guó)，伊拉克，卡塔爾，阿聯(lián)酋，泰國(guó)，越南，阿曼，印尼能回答中國(guó)男足和哪些國(guó)家水平比較接近。不能回答在亞洲處于幾流水平。聚類的應(yīng)用領(lǐng)域經(jīng)濟(jì)領(lǐng)域：幫助市場(chǎng)分析人員從客戶數(shù)據(jù)庫(kù)中發(fā)現(xiàn)不同的客戶群誰(shuí)喜歡打國(guó)際長(zhǎng)途，在什么時(shí)間，打到那里？對(duì)住宅區(qū)進(jìn)行聚類，確定自動(dòng)提款機(jī)ATM的安放位置企業(yè)信用等級(jí)分類……生物醫(yī)學(xué)領(lǐng)域推導(dǎo)植物和動(dòng)物的分類；對(duì)基因分類，獲得對(duì)種群的認(rèn)識(shí)癌癥病人基因表達(dá)數(shù)據(jù)分析有貢獻(xiàn)的研究領(lǐng)域數(shù)據(jù)挖掘聚類可伸縮性、各種各種復(fù)雜形狀類的識(shí)別，高維聚類等統(tǒng)計(jì)學(xué)主要集中在基于距離的聚類分析機(jī)器學(xué)習(xí)無(wú)指導(dǎo)學(xué)習(xí)（聚類不依賴預(yù)先定義的類，不等同于分類）空間數(shù)據(jù)技術(shù)生物學(xué)市場(chǎng)營(yíng)銷學(xué)1.2為什么需要聚類現(xiàn)實(shí)生活中數(shù)據(jù)太多，但是獲得數(shù)據(jù)中的模式知識(shí)太少，不可能都靠人鑒別。股票交易分析網(wǎng)頁(yè)文件聚類分析社交網(wǎng)絡(luò)團(tuán)體檢測(cè)（communitydetectioninsocialnetwork）……有些數(shù)據(jù)中的分類模糊用戶分類分析：每一個(gè)類別里面的人消費(fèi)方式都不一樣，需要針對(duì)不同的人群，制定不同的關(guān)系管理方式，以提高客戶對(duì)公司商業(yè)活動(dòng)的相應(yīng)率。用戶習(xí)慣分析：沒(méi)有明確定義習(xí)慣的方法聚類分析在人工智能方法各階段的作用表征–計(jì)算–衡量在表征階段，聚類常用于過(guò)濾數(shù)據(jù)點(diǎn)和特征選擇；在計(jì)算階段，聚類是重要應(yīng)用技術(shù)；在衡量階段，聚類常用于在大量數(shù)據(jù)中提取參考模式。1.3聚類問(wèn)題特征聚類分析中“類”的特征——無(wú)監(jiān)督學(xué)習(xí)聚類所說(shuō)的類不是事先給定的，而是根據(jù)數(shù)據(jù)的相似性和距離來(lái)劃分聚類的數(shù)目和結(jié)構(gòu)可能都沒(méi)有事先假定聚類的主觀性部分指導(dǎo)的聚類分析提供部分指導(dǎo)信息（約束聚類）數(shù)據(jù)變量類型和距離定義聚類的主觀性聚類方法的目的是尋找數(shù)據(jù)中：潛在的自然分組結(jié)構(gòu)感興趣的關(guān)系聚類的主觀性不同情況下對(duì)自然分組結(jié)構(gòu)有著不同理解聚類的主觀性什么是自然分組結(jié)構(gòu)Naturalgrouping?我們看看以下的例子：有16張牌如何將他們分為一組一組的牌呢？AKQJ聚類的主觀性分成四組每組里花色相同組與組之間花色相異AKQJ花色相同的牌為一副聚類的主觀性分成四組符號(hào)相同的牌為一組AKQJ符號(hào)相同的的牌聚類的主觀性分成兩組顏色相同的牌為一組AKQJ顏色相同的配對(duì)聚類的主觀性這個(gè)例子告訴我們，分組的意義在于我們?cè)趺炊x并度量“相似性”Similarity因此衍生出一系列度量相似性的算法AKQJ如何部分修正聚類的主觀性？

約束聚類例子MLCLML(A1,A2):

數(shù)據(jù)點(diǎn)A1,A2必須在同一個(gè)類.CL(B3,A3):數(shù)據(jù)點(diǎn)B3,A3必須在不同的兩個(gè)類.

數(shù)據(jù)變量類型變量按測(cè)量尺度（MeasurementLevel）分類名義尺度變量（Nominal）類別變量，不可加減也不可比大小，如性別、職業(yè)等有序尺度變量（Ordinal）等級(jí)變量，不可加減，但可比較大小，如獎(jiǎng)學(xué)金、名次等間隔尺度變量（Interval）區(qū)間變量，可以加減但不能比較倍數(shù)，如年份、經(jīng)緯度等比率尺度變量（Ratio）定比變量，可以加減也可以比較倍數(shù)，如身高、體重等擴(kuò)展閱讀/wiki/Level_of_measurement數(shù)據(jù)變量類型按照數(shù)據(jù)結(jié)構(gòu)分：結(jié)構(gòu)化數(shù)據(jù)：即行數(shù)據(jù)，存儲(chǔ)在數(shù)據(jù)庫(kù)里，可以用二維表結(jié)構(gòu)來(lái)邏輯表達(dá)實(shí)現(xiàn)的數(shù)據(jù)例子：學(xué)生檔案數(shù)據(jù)非結(jié)構(gòu)數(shù)據(jù)：不方便用數(shù)據(jù)庫(kù)二維邏輯表來(lái)表現(xiàn)的數(shù)據(jù)例子：圖象、聲音、超媒體、基于網(wǎng)絡(luò)的變量等信息混雜變量類型的數(shù)據(jù)如何聚類？當(dāng)對(duì)象是同時(shí)被各種類型的變量描述時(shí)，怎樣描述對(duì)象之間的相異度呢？學(xué)生數(shù)據(jù)：【性別，身高，獎(jiǎng)學(xué)金等級(jí)】傳統(tǒng)辦法：把所有變量一起處理，將不同類型的變量組合在單個(gè)相異矩陣中，把所有有意義的變量轉(zhuǎn)換到【0，1】的區(qū)間上，再進(jìn)行聚類分析。新方法：將不同類別變量數(shù)據(jù)分別聚類再合并聚類融合（ClusterEnsembles）聚類融合，再對(duì)一致矩陣進(jìn)行聚類處理類別向量相關(guān)矩陣一致矩陣距離/相似性定義最常用的數(shù)值型數(shù)據(jù)相似性Similarity的度量明考夫斯基距離（適用于數(shù)值型數(shù)據(jù)）Q=2時(shí)歐式距離常用的距離1.歐氏距離2.曼哈頓距離3.切比雪夫距離4.明可夫斯基距離5.標(biāo)準(zhǔn)化歐氏距離6.馬氏距離7.夾角余弦8.漢明距離9.杰卡德距離&杰卡德相似系數(shù)10.相關(guān)系數(shù)&相關(guān)距離11.信息熵?cái)U(kuò)展閱讀：/1954428598/blog4主要聚類算法的分類層次的方法（hierarchicalmethod）劃分方法（partitioningmethod）Kmeans(J.MacQueen,1956.被引用11748次）基于密度的方法（density-basedmethod）基于模型的方法（model-basedmethod）……層次的方法（也稱系統(tǒng)聚類法）（hierarchicalmethod）定義：對(duì)給定的數(shù)據(jù)進(jìn)行層次的分解：分類：凝聚的（agglomerative）方法（自底向上）

思想：一開始將每個(gè)對(duì)象作為單獨(dú)的一組，然后根據(jù)同類相近，異類相異的原則，合并對(duì)象，直到所有的組合并成一個(gè)，或達(dá)到一個(gè)終止條件為止。分裂的方法（divisive）（自頂向下）

思想：一開始將所有的對(duì)象置于一類，在迭代的每一步中，一個(gè)類不斷地分為更小的類，直到每個(gè)對(duì)象在單獨(dú)的一個(gè)類中，或達(dá)到一個(gè)終止條件。

層次聚類方法（hierarchicalmethod）特點(diǎn)：類的個(gè)數(shù)不需事先定好需確定距離矩陣運(yùn)算量大，適用于處理小樣本數(shù)據(jù)

廣泛采用的類間距離：最小距離法（singlelinkagemethod）廣泛采用的類間距離：最大距離法（completelinkagemethod）極大值很可能被異常離群點(diǎn)（Outliers）扭曲，刪除這些值之后再聚類廣泛采用的類間距離：類平均距離法（averagelinkagemethod）類間所有樣本點(diǎn)的平均距離該法利用了所有樣本的信息，被認(rèn)為是較好的系統(tǒng)聚類法廣泛采用的類間距離：重心法（centroidhierarchicalmethod）類的重心之間的距離對(duì)異常值不敏感，結(jié)果更穩(wěn)定

比對(duì)相似度(pairwisesimilarity)層次聚類例子（類平均距離法）在兩個(gè)維度上分別進(jìn)行層次聚類層次聚類方法方法缺陷：

一旦一個(gè)步驟（合并或分裂）完成，就不能被撤銷或修正，因此產(chǎn)生了改進(jìn)的層次聚類方法，如BRICH,BURE,ROCK,Chameleon。劃分方法（Partitioningmethod）較流行的方法有:動(dòng)態(tài)聚類法（也稱逐步聚類法），如k－均值算法、k－中心點(diǎn)算法思想：隨機(jī)選擇k個(gè)對(duì)象，每個(gè)對(duì)象初始地代表一個(gè)類的平均值或中心，對(duì)剩余每個(gè)對(duì)象，根據(jù)其到類中心的距離，被劃分到最近的類；然后重新計(jì)算每個(gè)類的平均值。不斷重復(fù)這個(gè)過(guò)程，直到所有的樣本都不能再分配為止。（下頁(yè)詳細(xì)圖解）Kmeans（k－均值算法）Since1967Kmeans算法算法步驟：（1）適當(dāng)選擇c個(gè)類的初始中心；（2）在第k次迭代中，對(duì)任意一個(gè)樣本，求其到c個(gè)中心的距離，將該樣本歸到距離最短的中心所在的類；（3）利用均值等方法更新該類的中心值；（4）對(duì)于所有的c個(gè)聚類中心，如果利用（2）（3）的迭代法更新后，值保持不變，則迭代結(jié)束，否則繼續(xù)迭代。Kmeans算法該算法的最大優(yōu)勢(shì)在于簡(jiǎn)潔和快速。算法的關(guān)鍵在于初始中心的選擇和距離公式。最常用是歐式距離：例：(1,2)和(2,1)的歐式距離sqrt(|1-2|^2+|2-1|^2)=1.414利用數(shù)據(jù)點(diǎn)計(jì)算新的聚類中心公式：設(shè)一個(gè)類只有兩個(gè)(1,2)和(2,1)，新聚類中心((1+2)/2,(2+1)/2)K-Means聚類例子

紅點(diǎn)為中心，其他點(diǎn)為數(shù)據(jù)，圈為一個(gè)聚類課后練習(xí)，要求下周上課交每個(gè)人都交紙質(zhì)版將右表的數(shù)據(jù)點(diǎn)進(jìn)行Kmeans聚類使用A1，B1，C1作為初始的聚類中心以歐氏距離作為距離函數(shù)求Kmeans算法收斂后的三個(gè)聚類要求算出每次迭代的數(shù)據(jù)劃分和新中心的數(shù)據(jù)數(shù)據(jù)點(diǎn)(x,y)A1(2,10)A2(2,5)A3(8,4)B1(5,8)B2(7,5)B3(6,4)C1(1,2)C2(4,9)作業(yè)格式（填寫，迭代直到收斂）迭代序號(hào)中心A1A2A3B1B2B3C1C21(2,10)(5,8)(1,2)1232….參考：每次迭代的中心和分布劃分方法（Partitioningmethod）特點(diǎn)：類的數(shù)目Ｋ事先定好創(chuàng)建一個(gè)初始劃分，再采用迭代的重定位技術(shù)不必確定距離矩陣比層次聚類法運(yùn)算量要小，適用于處理龐大的樣本數(shù)據(jù)適用于發(fā)現(xiàn)球狀類劃分方法（Partitioningmethod）缺陷：不同的初始值，結(jié)果可能不同有些k均值算法的結(jié)果與數(shù)據(jù)輸入順序有關(guān)，如在線k均值算法一般用貪心算法來(lái)尋找最優(yōu)解，容易陷入局部極小值Kmeans方法的局限性Kmeans在數(shù)據(jù)有著不同特征時(shí)存在問(wèn)題：各類數(shù)據(jù)點(diǎn)數(shù)目差距太大不同密度非球型分布其他元素（存在離群點(diǎn)，……）不同類數(shù)據(jù)點(diǎn)數(shù)目差距太大OriginalPointsK-means(3Clusters)不同密度OriginalPointsK-means(3Clusters)非球型分布Non-globularShapesOriginalPointsK-means(2Clusters)基于密度的方法

（density-basedmethod）主要有DBSCAN，OPTICS法思想：只要臨近區(qū)域的密度超過(guò)一定的閥值，就繼續(xù)聚類特點(diǎn)：可以過(guò)濾噪聲和孤立點(diǎn)outlier，發(fā)現(xiàn)任意形狀的類基于模型的方法

（model-basedmethod）為每個(gè)類假定一個(gè)模型，尋找數(shù)據(jù)對(duì)給定模型的最佳擬合。深入內(nèi)容可以參考《DataMingConceptsandTechniques》即《數(shù)據(jù)挖掘概念與技術(shù)》JiaweiHanMichelineKamber機(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)歐式距離等。

2.案例演示2.1心肌細(xì)胞數(shù)據(jù)聚類18個(gè)數(shù)據(jù)點(diǎn)，44000個(gè)基因（特征）2.2Kmeans算法應(yīng)用示例：中國(guó)男足近幾年到底在亞洲處于幾流水平？/leoo2sk/archive/2010/09/20/k-means.html

實(shí)際是看和哪些對(duì)手水平相近2.3Kmeans聚類分析案例——某移動(dòng)公司客戶細(xì)分模型（SPSS）/post/k-means.html數(shù)據(jù)點(diǎn)比對(duì)距離(pairwisedistance)層次聚類例子在兩個(gè)維度上分別進(jìn)行層次聚類劃分聚類（Kmeans，類數(shù)K=4）2.2Kmeans應(yīng)用實(shí)力：中國(guó)男足定位數(shù)據(jù)：名次分?jǐn)?shù)（06世界杯，10世界杯，07亞洲杯）數(shù)據(jù)規(guī)格化：映射到[0,1]區(qū)間Kmeans運(yùn)行過(guò)程參數(shù)類數(shù)K=3抽取日本、巴林和泰國(guó)的值作為三個(gè)簇的種子，即初始化三個(gè)簇的中心為A：{0.3,0,0.19}，B：{0.7,0.76,0.5}和C：{1,1,0.5}。以歐氏距離度量運(yùn)行結(jié)果算法迭代三次收斂，結(jié)果為日本，韓國(guó)，伊朗，沙特烏茲別克斯坦，巴林，朝鮮中國(guó)，伊拉克，卡塔爾，阿聯(lián)酋，泰國(guó)，越南，阿曼，印尼聚類結(jié)果的其他發(fā)現(xiàn)在亞洲一流隊(duì)伍中，日本與沙特水平最接近，而伊朗則相距他們較遠(yuǎn)，這也和近幾年伊朗沒(méi)落的實(shí)際相符。烏茲別克斯坦和巴林雖然沒(méi)有打進(jìn)近兩屆世界杯，不過(guò)憑借預(yù)算賽和亞洲杯上的出色表現(xiàn)占據(jù)B組一席之地，而朝鮮由于打入了2010世界杯決賽圈而有幸進(jìn)入B組。同樣奇跡般奪得2007年亞洲杯的伊拉克卻被分在三流，看來(lái)亞洲杯冠軍的分量還不如打進(jìn)世界杯決賽圈重。2.3Kmeans聚類分析案例——某移動(dòng)公司客戶細(xì)分模型（SPSS）/post/k-means.html數(shù)據(jù)來(lái)源《SPSS統(tǒng)計(jì)分析高級(jí)教程