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

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

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

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

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

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

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

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

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

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

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

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

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

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

（model-basedmethod）為每個類假定一個模型，尋找數(shù)據(jù)對給定模型的最佳擬合。深入內(nèi)容可以參考《DataMingConceptsandTechniques》即《數(shù)據(jù)挖掘概念與技術(shù)》JiaweiHanMichelineKamber機械工業(yè)出版社聚類方法的不穩(wěn)定性受所選擇變量的影響如果去掉或者增加一些變量,結(jié)果會很不同.因此，聚類之前一定要明確目標，選擇有意義的變量。變量之間的相關(guān)性也會影響聚類結(jié)果，因此可以先用主成分或因子分析法把眾多變量壓縮為若干個相互獨立的并包含大部分信息的指標，然后再進行聚類。聚類方法的不穩(wěn)定性輸入?yún)?shù)憑主觀導致難以控制聚類的質(zhì)量很多聚類算法要求輸入一定的參數(shù)，如希望產(chǎn)生的類的數(shù)目，使得聚類的質(zhì)量難以控制，尤其是對于高維的，沒有先驗信息的龐大數(shù)據(jù)。首先要明確聚類的目的，就是要使各個類之間的距離盡可能遠，類中的距離盡可能近，聚類算法可以根據(jù)研究目的確定類的數(shù)目，但聚類的結(jié)果要有令人信服的解釋。在實際操作中，更多的是憑經(jīng)驗來確定類的數(shù)目，測試不同類數(shù)的聚類效果，直到選擇較理想的分類。聚類方法的不穩(wěn)定性算法的選擇沒有絕對當聚類結(jié)果被用作描述或探查工具時，可以對同樣的數(shù)據(jù)嘗試多種算法，以發(fā)現(xiàn)數(shù)據(jù)可能揭示的結(jié)果。

聚類方法的不穩(wěn)定性聚類分析中權(quán)重的確定當各指標重要性不同的時候，需要根據(jù)需要調(diào)整權(quán)重。如加權(quán)歐式距離等。

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

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