（一）什么是聚類
聚類，將相似的事物聚集在一起，將不相似的事物劃分到不同的類別的過程。是將復(fù)雜數(shù)據(jù)簡(jiǎn)化為少數(shù)類別的一種手段。
（二）聚類的基本思想：
- 有大量的樣本。
- 假定研究的樣本之間存在程度不同的相似性，可以分為幾類；相同類別的樣本相似度高，不同類別的樣本相似度差。
- 用一些數(shù)據(jù)指標(biāo)來描述樣本的若干屬性，構(gòu)成向量。
- 用某種方法度量樣本之間或者類別 之間的相似性（或稱距離），依據(jù)距離來進(jìn)行分類。
- 根據(jù)分類來研究各類樣本的共性，找出規(guī)律。
（三）聚類的應(yīng)用
- 商業(yè)領(lǐng)域-識(shí)別顧客購(gòu)買模式，預(yù)測(cè)下一次購(gòu)買行為，淘寶商品推薦等。
- 金融領(lǐng)域-股票市場(chǎng)板塊分析
- 安全和軍事領(lǐng)域
- 破解GPS偽隨機(jī)干擾碼和北斗系統(tǒng)民用版的展頻編碼密碼
- 識(shí)別論壇馬甲和僵尸粉
- 追溯網(wǎng)絡(luò)謠言的源頭
- 生物領(lǐng)域
- 進(jìn)化樹構(gòu)建
- 實(shí)驗(yàn)對(duì)象的分類
- 大規(guī)模組學(xué)數(shù)據(jù)的挖掘
- 臨床診斷標(biāo)準(zhǔn)
- 機(jī)器學(xué)習(xí)
- 人工智能
（四）聚類的對(duì)象
設(shè)有m個(gè)樣本單位，每個(gè)樣本測(cè)的n項(xiàng)指標(biāo)（變量），原始資料矩陣：
指標(biāo)的選擇非常重要：
必要性要求：和聚類分析的目的密切相關(guān)，并不是越多越好
代表性要求：反映要分類變量的特征
區(qū)分度要求：在不同研究對(duì)象類別上的值有明顯的差異
獨(dú)立性要求：變量之間不能高度相關(guān)（兒童生長(zhǎng)身高和體重非常相關(guān)）
散布性要求：最好在值域范圍內(nèi)分布不太集中
（五）數(shù)據(jù)標(biāo)準(zhǔn)化
在各種標(biāo)準(zhǔn)量度值scale差異過大時(shí)，或數(shù)據(jù)不符合正態(tài)分布時(shí)，可能需要進(jìn)行數(shù)據(jù)標(biāo)準(zhǔn)化。
（1） 總和標(biāo)準(zhǔn)化。 分別求出各聚類指標(biāo)所對(duì)應(yīng)的數(shù)據(jù)的總和， 以各指標(biāo)的數(shù)據(jù)除以該指標(biāo)的數(shù)據(jù)的總和。
這種標(biāo)準(zhǔn)化方法所得到的的新數(shù)據(jù)滿足：
（2）標(biāo)準(zhǔn)差標(biāo)準(zhǔn)化，即：
這種標(biāo)準(zhǔn)化方法得到的新數(shù)據(jù)，各指標(biāo)的平均值為0，標(biāo)準(zhǔn)差為1，即有：
PS：比如說大家的身高差異
（3）極大值標(biāo)準(zhǔn)差
經(jīng)過這種標(biāo)準(zhǔn)化所得到的新數(shù)據(jù)，各指標(biāo)的極大值為1，其余各數(shù)值小于1.
PS：課程難易，成績(jī)高低。
（4）極差的標(biāo)準(zhǔn)化：
經(jīng)過這種標(biāo)準(zhǔn)化所得到的新數(shù)據(jù)，各指標(biāo)的極大值為1，極小值為0，其余的數(shù)值均在0與1之間。
PS：高考算標(biāo)準(zhǔn)分。
（六）聚類的分類：
根據(jù)聚類對(duì)象的不同，分為Q型聚類，R型聚類
- Q型聚類：樣本之間的聚類即Q型聚類分析，常用距離來測(cè)度樣本之間的親疏程度
- 閔可夫斯基距離
- 馬氏距離
- 文本距離
- 秩距離
- R型聚類：變量之間的聚類即R型聚類分析，常用相似性系數(shù)來測(cè)度變量之間的親疏程度
- 相關(guān)系數(shù)
- 夾角余弦
（1）常見距離統(tǒng)計(jì)量 - 閔可夫斯基距離系列（線性距離）
p=1，時(shí)為曼哈頓距離（出租車距離）
p=2，時(shí)為歐氏距離（n維空間中的幾何距離）
p=∞，時(shí)為切比雪夫距離（棋盤格距離）
（2）常見距離統(tǒng)計(jì)量 - 馬氏距離（協(xié)方差距離）
均值為μ，協(xié)方差矩陣為∑的向量x=(1,2,...n)
相比于歐式距離，馬氏距離考慮到各種指標(biāo)之間的聯(lián)系（如身高和體重并不獨(dú)立，）且馬氏距離具有尺度無關(guān)性（scale-invariant），因此可不必做標(biāo)準(zhǔn)化。
如果協(xié)方差矩陣為單位矩陣（各指標(biāo)之間完全相互獨(dú)立），則馬氏距離化為歐幾里得距離。
如果協(xié)方差矩陣為對(duì)角矩陣，則馬氏距離化為正規(guī)化的歐幾里得距離（normalized Euclidean distance）
（3）常見距離統(tǒng)計(jì)量 - 文本距離
文本距離通常用來度量文本之間的相似度，在生物研究中常見于序列比對(duì)分析。
-
Hamming distance: 漢明距離，兩個(gè)等長(zhǎng)字符串之間直接逐位比較，有多少位不同。
缺點(diǎn)：必須要兩個(gè)等長(zhǎng)的字符串 -
Levenshtein distance：編輯距離，兩個(gè)字符串之間，從一個(gè)字符串出發(fā)進(jìn)行多少次的修正（每次一個(gè)字符串的替換，插入或刪除）可以得到第二個(gè)字符串。求解過程類似于Needleman-Wunsch 算法中的搜索和回溯過程。
（4）常見距離統(tǒng)計(jì)量 - 秩距離
序列型變量需要用秩（rank）的概念來計(jì)算距離
例如：選美大賽時(shí)有ABCDE五名參賽選手，評(píng)委需要對(duì)其表現(xiàn)作出排名。這個(gè)排名就稱為“秩”（rank）。
將每個(gè)變量的值域（上例中為[1,5]）映射到[0,1]范圍上
然后用前述某種距離計(jì)算方法來計(jì)算距離
常見相似系數(shù)統(tǒng)計(jì)量
相似系數(shù)= 1，表明完全相似
相似系數(shù)= -1 表明完全相反
相似系數(shù) = 0 表明完全獨(dú)立
相關(guān)系數(shù)：
回歸的時(shí)候要算相關(guān)系數(shù)，
夾角余弦：
類與類之間 距離的度量方法：
系統(tǒng)聚類法不僅需要度量個(gè)體與個(gè)體之間的距離，還要度量類與類之間的距離。類間距離被度量出來之后，距離最小的兩個(gè)小類將首先被合并成為一類。 由類間距離定義的不同產(chǎn)生了不同的系統(tǒng)聚類法。
- 最短距離法(Nearest Neighbor)
- 以兩類中距離最近的兩個(gè)個(gè)體之間的距離作為類間距離
- 最長(zhǎng)距離法（Further Neighbor)
- 以兩類中距離最遠(yuǎn)的兩個(gè)個(gè)體之間的距離作為類間距離
- 組間平均連接法（Between-group linkage，UPGMA）
- 以兩類個(gè)體兩兩之間的距離的平均數(shù)作為類間距離。
- 組內(nèi)平均連接法（Within-group linkage）
- 將兩類個(gè)體合并為一類后，以合并后類中所有個(gè)體之間的平均距離作為類間距離
- 重心法（Centroid clustering）
- 以兩類變量均值（重心）之間的距離作為類間距。
- 中位數(shù)法（Median clustering）
- 以兩類變量中位數(shù)之間的距離作為類間距離
- 離差平方和法（Ward’s method）
-
Ward方法并類時(shí)總是使得并類導(dǎo)致的類內(nèi)離差平方和增量最小。僅能用于歐氏距離。
image.png
-
聚類算法的分類：
目前有1000多種聚類算法：沒有一種聚類算法可以包打天下，聚類算法中的各種參數(shù)也必須依據(jù)具體問題而調(diào)節(jié)
常見聚類算法的分類：
1，層次聚類（Hierarchical clustering）
2，劃分聚類（Partitioning clustering）
3，密度聚類（Density-based）
4，期望最大化聚類（Expectation Maximization）
5，網(wǎng)格聚類（Grid-based）
6，模型聚類（Model-based）
1. 層次聚類的方法
基本思想：
在聚類分析的開始，每個(gè)樣本（或變量）自成一類； 然后，按照某種方法度量所有樣本（或變量）之間的親疏程度，并把最相似的樣本（或變量）首先聚成一小類； 接下來，度量剩余的樣本（或變量）和小類間的親疏程度，并將當(dāng)前最接近的樣本（或變量）與小類聚成一類；如此反復(fù)，知道所有樣本聚成一類為止。
舉例：
有一組數(shù)據(jù)D={a,b,c,d,e} 給了它們之間的距離矩陣。
首先，每一個(gè)例子都是一個(gè)類：
將最近的兩個(gè)類合并為一個(gè)新的類，并重新計(jì)算類之間的距離然后更新距離矩陣：
d(a,b)=0.18距離最近，合并為一類ab,然后計(jì)算ab,c,d,e之間的距離
選擇距離最近的兩個(gè)類合并為新的類：
[圖片上傳失敗...(image-62f70-1573443086632)] 距離最近，因此d,e合并為一類
不斷重復(fù)上述兩個(gè)步驟，最終只剩下一個(gè)類的時(shí)候，停止：
類別的數(shù)量取決于你剪的位置
層次聚類中，通常用組間平均連接法（UPGMA)和離差平方和法（Ward）比較穩(wěn)健。
層次聚類的優(yōu)缺點(diǎn)：
- 適用于大多數(shù)情況，穩(wěn)健性比較好
- 易于生成系統(tǒng)發(fā)育樹，分類類數(shù)可以隨意選取
- 計(jì)算量大（兩兩計(jì)算距離）
- 需要仔細(xì)選擇距離計(jì)算方法和組間距離計(jì)算方法
2. 劃分聚類的方法
劃分聚類算法：
給定一個(gè)包含n個(gè)樣本的數(shù)據(jù)集，基于劃分的方法（Partitioning Method）就是將n個(gè)樣本按照特定的度量劃分為k個(gè)簇（k≤n），使得每個(gè)簇至少包含一個(gè)對(duì)象，并且每個(gè)對(duì)象屬于且僅屬于一個(gè)簇，而且簇之間不存在層次關(guān)系。
基于劃分的方法大多數(shù)是基于距離來劃分的，首先對(duì)樣本進(jìn)行初始化分，然后計(jì)算樣本間的距離，重新對(duì)數(shù)據(jù)集中的樣本進(jìn)行劃分，將樣本劃分到距離更近的簇中，得到一個(gè)新的樣本劃分，迭代計(jì)算直到聚類結(jié)果滿足用戶指定的要求。
要想得到最優(yōu)的聚類結(jié)果，算法需要窮舉數(shù)據(jù)集所有可能的劃分情況，但是在實(shí)際應(yīng)用中數(shù)據(jù)量都比較大，利用窮舉方法聚類顯然是不現(xiàn)實(shí)的，因此大部分基于劃分的聚類方法采用貪心策略，即在每一次劃分過程中尋求最優(yōu)解，然后基于最優(yōu)解進(jìn)行迭代計(jì)算，逐步提高聚類結(jié)果的質(zhì)量。雖然這種方式有可能得到局部最優(yōu)結(jié)果，但是結(jié)合效率方面考慮，也是可以接受的。
算法：
- 選擇 K 個(gè)初始質(zhì)心，初始質(zhì)心隨機(jī)選擇即可，每一個(gè)質(zhì)心為一個(gè)類
- 把每個(gè)觀測(cè)指派到離它最近的質(zhì)心，與質(zhì)心形成新的類
- 重新計(jì)算每個(gè)類的質(zhì)心，所謂質(zhì)心就是一個(gè)類中的所有觀測(cè)的平均向量（這里稱為向量，是因?yàn)槊恳粋€(gè)觀測(cè)都包含很多變量，所以我們把一個(gè)觀測(cè)視為一個(gè)多維向量，維數(shù)由變量數(shù)決定）。
- 重復(fù)2. 和 3.
- 直到質(zhì)心不在發(fā)生變化時(shí)或者到達(dá)最大迭代次數(shù)時(shí)
舉例：
有一個(gè)二維空間的一些點(diǎn)，我們要將它們分成3個(gè)類，即K=3。
我們首先隨機(jī)選擇3個(gè)初始質(zhì)心，每一個(gè)質(zhì)心為一類：
然后我們計(jì)算每一個(gè)不是質(zhì)心的點(diǎn)到這三個(gè)質(zhì)心的距離：
將這些點(diǎn)歸類于距離最近的那個(gè)質(zhì)心的一類：
重新計(jì)算這三個(gè)分類的質(zhì)心：
不斷重復(fù)上述兩步，更新三個(gè)類：
當(dāng)穩(wěn)定以后，迭代停止，這時(shí)候的三個(gè)類就是我們得到的最后的三個(gè)：
最著名的是k-means聚類算法和K-medoids算法（中心點(diǎn)聚類）
- 要求事先確定分類數(shù)
- 運(yùn)算速度快（特別是對(duì)于大樣本）
- 初始值敏感
- 對(duì)噪聲和孤立數(shù)據(jù)點(diǎn)敏感
- 傾向于每一類別的樣本數(shù)量相等，因此常出現(xiàn)錯(cuò)誤
3. 基于密度的方法
處理“大海中的若干孤島”，以密度來區(qū)分島
大部分基于密度的方法（Density-based Method）采用距離度量來對(duì)數(shù)據(jù)集進(jìn)行劃分，在球狀的數(shù)據(jù)集中能夠正確劃分，但是在非球狀的數(shù)據(jù)集中則無法對(duì)樣本進(jìn)行正確聚類，并且受到數(shù)據(jù)集中的噪聲數(shù)據(jù)影響較大?；诿芏鹊姆椒梢钥朔@兩個(gè)弱點(diǎn)。
基于密度的方法提出“密度”的思想，即給定鄰域中樣本點(diǎn)的數(shù)量，當(dāng)鄰域中密度達(dá)到或超過密度閾值時(shí)，將鄰域內(nèi)的樣本包含到當(dāng)前的簇中。若鄰域的密度不滿足閾值要求，則當(dāng)前的簇劃分完成，對(duì)下一個(gè)簇進(jìn)行劃分。基于密度的方法可以對(duì)數(shù)據(jù)集中的離群點(diǎn)進(jìn)行檢測(cè)和過濾。
算法：
- 從數(shù)據(jù)集中隨機(jī)選擇核心點(diǎn)
- 以一個(gè)核心點(diǎn)為圓心,做半徑為V的圓,選擇圓內(nèi)圈入點(diǎn)的個(gè)數(shù)滿足密度閾值的核心點(diǎn),因此稱這些點(diǎn)為核心對(duì)象,且將圈內(nèi)的點(diǎn)形成一個(gè)簇,其中核心點(diǎn)直接密度可達(dá)周圍的其他實(shí)心原點(diǎn);
- 合并這些相互重合的簇
4. 基于網(wǎng)格的方法
基于網(wǎng)格的方法（Grid-based Method）將數(shù)據(jù)集空間劃分為有限個(gè)網(wǎng)格單元，形成一個(gè)網(wǎng)絡(luò)結(jié)構(gòu)，在后續(xù)的聚類過程中，以網(wǎng)格單元為基本單位進(jìn)行聚類，而不是以樣本為單位。由于算法處理時(shí)間與樣本數(shù)量無關(guān)，只與網(wǎng)格單元數(shù)量有關(guān)，因此這種方法在處理大數(shù)據(jù)集時(shí)效率很高?；诰W(wǎng)格的方法可以在網(wǎng)格單元?jiǎng)澐值幕A(chǔ)上，與基于密度的方法、基于層次的方法等結(jié)合使用。
5. 基于模型的方法
基于模型的方法（Model-based Method）假定數(shù)據(jù)集滿足一定的分布模型，找到這樣的分布模型，就可以對(duì)數(shù)據(jù)集進(jìn)行聚類?；谀Ｐ偷姆椒ㄖ饕ɑ诮y(tǒng)計(jì)和基于神經(jīng)網(wǎng)絡(luò)兩大類，前者以高斯混合模型（Gaussian Mixture Models，GMM）為代表，后者以自組織映射網(wǎng)絡(luò)（Self Organizing Map，SOM）為代表。目前以基于統(tǒng)計(jì)模型的方法為主。
聚類結(jié)果的解釋和驗(yàn)證：
- 對(duì)每個(gè)類別進(jìn)行命名
- 提取這一類別的共同特征，確定邊界
- 進(jìn)行驗(yàn)證
- 先對(duì)“訓(xùn)練集”進(jìn)行聚類
- 然后用已知對(duì)象特性的“測(cè)試集”根據(jù)特征邊界來將樣本進(jìn)行歸類，檢驗(yàn)特征邊界的合理性
- 經(jīng)過驗(yàn)證的聚類結(jié)果才可用于對(duì)未知樣品的可靠分類（例如臨床診斷）
- 解釋分類形成的原因，提出可能的機(jī)制假說，進(jìn)行更深入的研究
以下內(nèi)容后續(xù)補(bǔ)充：
K-means算法的R實(shí)現(xiàn)：
數(shù)據(jù)示例：
x = rbind(matrix(rnorm(100,sd=0.3),ncol=2),matrix(rnorm(100,mean=1,sd=0.3),ncol=2))
cl = kmeans(x,2,20)
plot(x,col = cl$cluster,pch=3,lwd=1)
points(cl$centers,col=1:2,pch=7,lwd=3) # 畫出中心點(diǎn)
segments(x[cl$cluster==1,][,1],x[cl$cluster==1,][,2],cl$centers[1,1],cl$centers[1,2]) # 畫出每個(gè)點(diǎn)到中心點(diǎn)的連線。
segments(x[cl$cluster==2,][,1],x[cl$cluster==2,][,2],cl$centers[2,1],cl$centers[2,2],col=2)
層次聚類算法的R實(shí)現(xiàn)：
數(shù)據(jù)示例：
data("USArrests")
hc = hclust(dist(USArrests),"ave")
plot(hc,hang = -1)
解釋說明
為了有效利用聚類算法， 首先需要度量觀測(cè)值見的距離，在R中常通過stats包里的dist函數(shù)來實(shí)現(xiàn)：
dist(x, method = "euclidean", diag = FALSE, upper = FALSE, p = 2)
dist 函數(shù)計(jì)算對(duì)象（矩陣或數(shù)據(jù)框）中兩兩間的距離，返回的是距離矩陣（dist類對(duì)象）。dist函數(shù)的參數(shù)描述如下。
| dist參數(shù) | 描述 | 默認(rèn)值 |
|---|---|---|
| x | 用于計(jì)算矩陣的對(duì)象，可以使矩陣，數(shù)據(jù)框，dist對(duì)象 | |
| method | 設(shè)置計(jì)算距離的方法：method="euclidean",計(jì)算歐氏距離（2-norm）；method="maximum"計(jì)算最大距離（supremum-norm）method="manhattan"計(jì)算絕對(duì)距離（1-norm）method="canberra" 計(jì)算蘭氏距離 method="binary"將非0元素看作1，零看作0； method="minkowski" 計(jì)算閔式距離（p-norm） | euclidean |
| diag | 邏輯值，控制是否打印距離矩陣的對(duì)角元素 | FALSE |
| upper | 邏輯值， 控制是否打印上對(duì)角元素 | FALSE |
| p | 閔可夫斯基距離的范數(shù) | 2 |
另一個(gè)計(jì)算點(diǎn)之間的距離的方法是cluster包里面的daisy函數(shù)：
daisy(x, metric = c("euclidean", "manhattan", "gower"),
stand = FALSE, type = list(), weights = rep.int(1, p),
warnBin = warnType, warnAsym = warnType, warnConst = warnType,
warnType = TRUE)
daisy函數(shù)計(jì)算數(shù)據(jù)集中每對(duì)觀測(cè)值的不相似度。daisy函數(shù)的參數(shù)描述如下：
| daisy參數(shù) | 描述 | 默認(rèn)值 |
|---|---|---|
| x | 用于計(jì)算距離的數(shù)值型矩陣或數(shù)據(jù)框 | |
| metric | 指定計(jì)算距離的方法：metric="duclidean"，計(jì)算歐氏距離；metric="manhattan"計(jì)算曼哈頓距離；metric="gower", 計(jì)算高氏距離； | euclidean |
| stand | 邏輯值，計(jì)算距離前是否標(biāo)準(zhǔn)化化樣本 | FALSE |
| type | 控制x中變量的類型。值為“ordratio”時(shí)，表示原始數(shù)據(jù)，“l(fā)ogratio”為對(duì)數(shù)變換，“assym”為非對(duì)稱二元，“symm”為對(duì)稱二元 |
k-means聚類是最簡(jiǎn)單的聚類算法之一。R中可以通過stats包里面的kmeans函數(shù)實(shí)現(xiàn)k-means聚類：
kmeans(x, centers, iter.max = 10, nstart = 1, algorithm = c("Hartigan-Wong", "Lloyd", "Forgy", "MacQueen"), trace=FALSE)
kmeans函數(shù)的參數(shù)描述如下：
| 參數(shù) | 描述 | 默認(rèn)值 |
|---|---|---|
| x | 用于聚類的數(shù)值型矩陣（或者可以 轉(zhuǎn)換成矩陣的對(duì)象） | |
| centers | 若是數(shù)值，則為簇的個(gè)數(shù)；若是數(shù)值向量，則為初始簇的中心 | |
| iter.max | 最大迭代的次數(shù)（數(shù)值型） | 10 |
| nstart | 如centers是數(shù)值，則為隨機(jī)抽取的數(shù)據(jù)集的個(gè)數(shù) | 1 |
| algorithm | 用于聚類的算法，可選項(xiàng)包括algorithm="Hartigan-Wong",algorithm="Lloyd", algorithm="Forgy",algorithm="MacQueen" |
