一、聚類分析（Cluster Analysis）簡介
聚類分析是直接比較各事物之間的性質，将性質相近的歸為一類，将性質差别較大的歸入不同的類的分析技術。
數理統計中的數值分類有兩種問題：
- 判别分析：已知分類情況，将未知個體歸入正确類别
- 聚類分析：分類情況未知，對資料結構進行分類。
基本思想
聚類分析的基本思想: 對所研究的樣品或名額(變量)之間存在着程度不同的相似性(或親疏關系)。（1）根據一批樣品的多個名額, 具體找出一些能夠度量樣品或名額之間的相似程度的統計量。
（2）以這些統計量為分類的依據, 把一些相似程度較大的樣品(或名額)聚合為一類。
把另一些彼此之間相似程度較大的樣品(或名額)聚合為另一類。
- 按相似程度的大小
- 把關系密切的樣品聚合到一個小的分類機關,
- 關系疏遠的樣品聚合到一個大的分類機關,
- 直到把所有的樣品(或名額)都聚合完畢。
- 把不同的類型一一劃分出來, 形成一個由小到大的分類系統。再把整個分類系統畫成一張分群圖(又稱譜系圖), 用它把所有樣品(或名額)間的親疏關系表示出來。
二、聚類對象
- 要做聚類分析，首先得按照我們聚類的目的，從對象中提取出能表現這個目的的特征名額；然後根據親疏程度進行分類。
- 聚類分析根據分類對象的不同可分為Q型和R型兩大類
- Q型是對樣本進行分類處理，其作用在于:
- 具有共同特點的樣本聚在一起
- 所得結果比傳統的定性分類方法更細緻、全面、合理
- R型是對變量進行分類處理，其作用在于：
- 可以了解變量間及變量組合間的親疏關系
- 可以根據變量的聚類結果及它們之間的關系，選擇主要變量進行回歸分析或Q型聚類分析
三、相似性度量
- 進行“相關性”或“相似性”度量。在相似性度量中常常包含有許多主觀上的考慮，但是最重要的是考慮名額性質或觀測的尺度。
- 當樣品進行聚類時，“靠近”往往是距離。同時對名額進行聚類時，根據相關系數或某種關聯性度量來聚類。
Q型樣品間的“相似性”度量—距離(皮爾遜系數(課下去看））
- 設每個樣品有 p 個名額, 觀察值記為 x i = ( x 1 i , x 2 i , . . , x p i ) T , i = 1 , 2 , 3 , . . . , n x_i = (x_{1i},x_{2i},..,x_{pi})^T, i = 1,2,3,...,n xi=(x1i,x2i,..,xpi)T,i=1,2,3,...,n
- 每個樣品 x i x_i xi可看成是 p 維空間的一個點。于是, 可用各點之間的距離來衡量各樣品點之間的接近程度。
-
樣品 x i x_i xi和 x j x_j xj之間的距離$d(x_i,x_j),一般應滿足如下條件：
i. d ( x i , x j ) ≥ 0 d(x_i,x_j)\geq 0 d(xi,xj)≥0，且 d ( x i , x j ) = 0    ⟺    x i = x j d(x_i,x_j) = 0 \iff x_i = x_j d(xi,xj)=0⟺xi=xj
ii. d ( x i , x j ) = d ( x j , x i ) d(x_i,x_j) = d(x_j,x_i) d(xi,xj)=d(xj,xi)
iii. d ( x i , x j ) ≤ d ( x i , x k ) + d ( x k , x j ) d(x_i, x_j) \leq d(x_i,x_k) + d(x_k,x_j) d(xi,xj)≤d(xi,xk)+d(xk,xj)
有時所用的距離不滿足(ⅲ), 但在廣義的角度上仍稱為距離。常用的距離有如下幾種:
- 絕對距離【曼哈頓距離】（Block） d i j = ∑ k = 1 p ∣ x i k − x j k ∣ d_{ij} = \sum^p_{k = 1}|x_{ik}-x_{jk}| dij=∑k=1p∣xik−xjk∣
- 歐氏距離(Euclidean distance) d i j = [ ∑ k = 1 p ( x i k − x j k ) 2 ] 0.5 d_{ij} = [\sum^p_{k=1}(x_{ik}-x_{jk})^2]^{0.5} dij=[k=1∑p(xik−xjk)2]0.5
- 明考斯基距離(Minkowski) d i j = [ ∑ k = 1 p ( x i k − x j k ) q ] 1 q d_{ij} = [\sum^p_{k = 1}(x_{ik}-x_{jk})^q]^{\frac {1}{q}} dij=[k=1∑p(xik−xjk)q]q1
- 明考斯基距離(Minkowski) d i j ( ∞ ) = m a x 1 ≤ k ≤ q ∣ x i k − x j k ∣ d_{ij}(\infty ) = max_{1\leq k\leq q}|x_{ik}-x_{jk}| dij(∞)=max1≤k≤q∣xik−xjk∣
- 以上距離與各變量的量綱有關，為了消除量綱的影響，可對資料标準化。
- 資料的标準化 x i j ′ = x i j − x j ‾ S j x_{ij}' = \frac{x_{ij}-\overline{x_j}}{ {S_j}} xij′=Sjxij−xj其中 x j ‾ \overline{x_j} xj和 S j S_j Sj是第j個名額的均值和樣本标準差
案例1：歐洲各國語言
題目大意
- 歐洲各國的語言有許多相似之處，有的十分相似。為了研究這些語言的曆史關系，也許通過比較他們數字的表達式比較恰當。表列舉出英語，挪威語，丹麥語，荷蘭語，德語，法語，西班牙語，意大利語，波蘭語，匈牙利語和芬蘭語的1,2,…,10的拼法，希望計算這11種語言之間的語言的距離。
11種歐洲語言的數詞
- 在聚類分析中通常要結合實際問題來選擇适用的距離, 有時應根據實際問題定義新的距離。
- 顯然，本例無法直接用上述公式來計算距離。但可以發現前三種文字(英、挪、丹)很相似。
- 特别是每個單詞的第一個字母。可以用10個數詞中第一個字母不同的個數來定義兩種語言之間的距離。例如：英語和挪威語中隻有1和8的第一個字母不同, 則它們之間的距離為2。于是我們得到這樣的表格
數學模組化之聚類分析
R型聚類統計量
- 夾角餘弦 2、相關系數
數學模組化之聚類分析 數學模組化之聚類分析
- 對兩個名額之間的相似程度用相似系數來刻劃，相似系數絕對對值越接近于1，表示名額間的關系越密切，絕對值越接近于0，表示名額間的關系越疏遠.
三、 系統聚類分析
- 1 系統聚類分析的基本思想是：
- 距離相近的樣品（或變量）先聚成類，距離相遠的後聚成類，過程一直下去，每個樣品（或變量）總能聚到合适的類中。
- 系統聚類分析過程是：假設總共有n個樣品（或變量），第一步将每個樣品（或變量）獨自聚成一類，共有n類；
- 第二步根據所确定的樣品（或變量）“距離”公式，将距離較近的兩個樣品（或變量）聚合為一類，其他樣品（或變量）仍各自聚為一類，共有n－1類；
- 第三步将“距離”最近的兩個類進一步聚成一類，共聚成n－2類；……以上步驟一直進行下去，最後将所有的樣品或變量）聚成一類。
- 将整個分類系統地畫成一張譜系圖，是以有時系統聚類分析也叫譜系聚類分析。
- 2 類間距離
- 首先定義類與類之間地距離，又類間的距離定義不同産生不同的系統聚類分析。常見的類間的距離有8種之多，與之相應的系統聚類分析也有8種之多、分别為最短距離法、最長距離法、中間距離法、重心法、類平均法、可變類平均法、可變法和離差平方和法。它們的歸類步驟基本是一緻的。
- 用 i , j i,j i,j表示樣品 x i , x j x_i,x_j xi,xj。用 d i j d_{ij} dij表示 x i x_i xi與 x j x_j xj之間的距離，用 G p G_p Gp與 G q G_q Gq之間的距離用 D ( G p , G q ) D(G_p,G_q) D(Gp,Gq)表示。下面給出四種最常用的類與類之間距離的定義。
1 、最短距離（Nearest Neighbor)
{ D p q = D ( G p , G q ) = m i n { d i j ∣ i ∈ G p , j ∈ G q } } \{D_{pq} = D(G_p,G_q) = min\{ d_{ij}|i\in G_p,j\in G_q \}\} {Dpq=D(Gp,Gq)=min{dij∣i∈Gp,j∈Gq}}
即定義 G p G_p Gp與 G q G_q Gq之間的距離為 G p G_p Gp與 G q G_q Gq中最近的兩個樣品的距離。
類與類之間的最短距離有如下的遞推公式。設 G r G_r Gr由 G p G_p Gp與 G q G_q Gq合并而成，則 G r G_r Gr與其它類 G k ( k ̸ = p , q ) G_k(k \not= p,q) Gk(k̸=p,q)
D ( G r , G k ) D(G_r,G_k) D(Gr,Gk) = m i n { d y ∣ i ∈ G r , j ∈ G k } = m i n { m i n { d y ∣ i ∈ G p , h ∈ G k } m i n { d y ∣ i ∈ G q , j ∈ G k } } = m i n { D ( G p , G k ) , D ( G q , G k ) } = min\{ d_y|i\in G_r,j\in G_k \}\\=min\{ min\{ d_y|i\in G_p,h \in G_k\}min\{d_y|i\in G_q,j\in G_k\} \}\\=min\{D(G_p,G_k),D(G_q,G_k)\} =min{dy∣i∈Gr,j∈Gk}=min{min{dy∣i∈Gp,h∈Gk}min{dy∣i∈Gq,j∈Gk}}=min{D(Gp,Gk),D(Gq,Gk)}
- 說的就是兩個類的距離就是不同類的最短距離。
最短距離法進行聚類分析的步驟如下：
- 開始各樣本自成一類
- 根據樣品的特征，規定樣品之間的距離 d i j d_{ij} dij，共有 C 2 n C^n_2 C2n個。将所有清單，記為D(0)表，該表是一張對稱表。所有的樣本點各自為一類。
- 選擇D(0)表中最小的非零數，不妨假設 d p q d_{pq} dpq，于是将 G p G_p Gp和 G q G_q Gq合并為一類，記為 G r = { G p , G q } G_r = \{ G_p,G_q\} Gr={Gp,Gq}。
- 利用遞推公式計算新類與其它類之間的距離。分别删除D（0）表的第p，q行和第p， q列，并新增一行和一列添上的結果，産生D（1）表。
- 在D（1）表再選擇最小的非零數，其對應的兩類有構成新類，再利用遞推公式計算新類與其它類之間的距離。分别删除D（1）表的相應的行和列，并新增一行和一列添上的新類和舊類之間的距離。結果，産生D（2）表。類推直至所有的樣本點歸為一類為止。
小總結
（1） 定義樣品之間的距離
（2） 找出距離最小元素，設為 D p q D_{pq} Dpq，則将 G p G_p Gp與 G q G_q Gq合并成以新類記為 G r G_r Gr，記為 G r = { G p , G q } G_r = \{ G_p, G_q\} Gr={Gp,Gq}
（3）按上式計算新類與其他類之間的距離。
（4）重複（2），（3）的步驟，直到将所有元素并成一類為止。
(如果某一步距離最小的元素不止一個，則将對應這些最小元素的類可以同時合并）
樣例
設有6個樣品，每個隻測一個名額，分别是1， 2，5，7，9，10，試采用絕對值距離用最短距離法将它們進行分類。
解（1）樣品首先采用絕對值距離，計算樣品之間的距離陣為D(0).
-
現在有六個類，把距離最短的合成一個類，新圖如下圖所示（合并過後，會把。
多個類的都考慮進去）
數學模組化之聚類分析 - 這裡我們看到有兩個“2”，遇見這種情況優先合并小類。
數學模組化之聚類分析 數學模組化之聚類分析 數學模組化之聚類分析
2. 最長距離法
- 這個所謂的最長距離指不是要取類和類的最長距離，而是在合并之後，類和類之間的距離選擇”最長的數”。
- 舉例說明：
數學模組化之聚類分析 - 仍然選擇短的合并
數學模組化之聚類分析 - 此時 G 7 G_7 G7和 G 3 G_3 G3的距離為什麼是4呢，因為我們選擇的是 G 3 G_3 G3和 G 7 G_7 G7的最長距離作為兩個類之間的距離。
- 同理為什麼 G 8 G_8 G8和 G 7 G_7 G7是9也是這個原因。
數學模組化之聚類分析 數學模組化之聚類分析 - 分類結果往往差别不大
3. 類平均距離（組内平均連接配接法）
4. 重心法
- 基本就是類間距離計算公式不一樣
5. 動态聚類法（快速聚類法）（k-mean\高斯混合法)
- 系統聚類法是一種比較成功的聚類方法。但是複雜度是 O ( n 2 ) O(n^2) O(n2)，速度特别慢。
- 比如在市場抽樣調查中，有4萬人就其對衣着的偏好作了回答，希望能迅速将他們分為幾類。這時，采用系統聚類法就很困難，而動态聚類法就會顯得友善，适用。
- 動态聚類使用于大型資料。
基本思想
- 基本思想：選取若幹個樣品作為凝聚點，計算每個樣品和凝聚點的距離，進行初始分類，然後根據初始分類計算其重心，再進行第二次分類，一直到所有樣品不再調整為止。
數學模組化之聚類分析
動态聚類法的基本步驟：
第一，選擇凝聚點；
第二，初始分類；
對于取定的凝聚點，視每個凝聚點為一類，将每個樣品根據定義的距離向最近的凝聚點歸類。
第三，修改分類
得到初始分類，計算各類的重心，以這些重心作為新的凝聚點，重新進行分類，重複步驟2，3，直到分類的結果與上一步的分類結果相同，表明分類已經合理為止。
具體步驟
用一個簡單的例子來說明動态聚類法的工作過程。例如我們要把圖中的點分成兩類。快速聚類的步驟：
1、随機選取兩個點 x 1 ( 1 ) x_1^{(1)} x1(1)和 x 2 ( 1 ) x_2^{(1)} x2(1)作為凝聚點。
2、對于任何點 x k x_k xk，分别計算 d ( x k , x l ( 1 ) ) d(x_k,x_l^{(1)}) d(xk,xl(1))和 d ( x k , x 2 ( 1 ) ) d(x_k,x_2^{(1)}) d(xk,x2(1))
3、若 d ( x k , x 1 ( 1 ) ) < d ( x k , x 2 ( 1 ) ) d(x_k,x_1^{(1)})<d(x_k,x_2^{(1)}) d(xk,x1(1))<d(xk,x2(1))，則将x劃為第一類，否則劃給第二類。
4、分别計算兩個類的重心，則得 x 1 ( 2 ) x_1^{(2)} x1(2)和 x 2 ( 2 ) x_2^{(2)} x2(2)，以其為新的凝聚點，對空間中的點進行重新分類，得到新分類。
選擇聚點
聚點（種子）是一批有代表性的樣品，它的選擇決定了初始分類，對最終分類有較大影響。
在進行快速聚類法前，要根據研究問題的要求及了解程度先定下分類數k，這樣就可以在每一類中選擇一個有代表性的樣品作為聚點（初始聚點）。
選擇聚點有下列方法：
(1)經驗選擇。如果對研究對象比較了解，根據以往的經驗定下k個樣品作為聚點。
(2)将n個樣品人為地（或随機地）分成k類，以每類的重心作為聚點。
(3)最小最大原則。設要将n個樣品分成k類，先選擇所有樣品中距離最遠的兩個樣品 x i 1 , x i 2 x_{i_1},x_{i_2} xi1,xi2為前兩個聚點，即選擇 x i 1 x_{i_1} xi1和 x i 2 x_{i_2} xi2，使 d ( x i 1 x i 2 ) = d i 1 , i 2 = m a x { d i j } d(x_{i_1}x_{i_2}) = d_{i_1,i_2} = max\{ d_{ij}\} d(xi1xi2)=di1,i2=max{dij}
然後選擇第3個聚點xi ,使其與前兩個聚點的距離最小者等于所有其餘的與 x i 1 x_{i_1} xi1, x i 2 x_{i_2} xi2的較小距離中最大的
案例
某商店5位售貨員的銷售量和教育程度如下表：
對這5位售貨員分類。
- 選擇凝聚點
- 計算各樣品點兩兩之間的距離，得到如下的距離矩陣（定義距離為（“銷售量”，“教育程度”））
數學模組化之聚類分析 d 25 = 53 d_{25} = \sqrt {53} d25=53
為最大。可選擇2和5作為凝聚點。
2.初始分類
對于取定的凝聚點，視每個凝聚點為一類，将每個樣品根據定義的距離，向最近的凝聚點歸類。
- 得到初始分類為： G 1 : { 1 , 2 } , G 2 : { 3 , 4 , 5 } G_1: \{ 1,2\} , G_2: \{ 3,4,5\} G1:{1,2},G2:{3,4,5}
-
修改分類
重心是指每類的均值向量，計算G1和G2的重心：G1的重心（1,1.5）， G2的重心（7.33,1.67）以這兩個重心點作為凝聚點，再按最小距離原則重新聚類
數學模組化之聚類分析
- 得到分類結果和上面雷同