[!IMPORTANT]
参与组队学习的同学须知：
本章学习时间：3天
本章配套视频教程：https://www.bilibili.com/video/BV1Mh411e7VU?p=14
第9章 聚类
到目前为止，前面章节介绍的方法都是针对监督学习(supervised
learning)的，本章介绍的聚类(clustering)和下一章介绍的降维属于无监督学习(unsupervised
learning)。
9.1 聚类任务
单词"cluster"既是动词也是名词，作为名词时翻译为"簇"，即聚类得到的子集；一般谈到"聚类"这个概念时对应其动名词形式"clustering"。
9.2 性能度量
本节给出了聚类性能度量的三种外部指标和两种内部指标，其中式(9.5)
~式(9.7)是基于式(9.1)
~式(9.4)导出的三种外部指标，而式(9.12)和式(9.13)是基于式(9.8)
~式(9.11)导出的两种内部指标。读本节内容需要心里清楚的一点：本节给出的指标仅是该领域的前辈们定义的指标，在个人研究过程中可以根据需要自己定义，说不定就会被业内同行广泛使用。
9.2.1 式(9.5)的解释
给定两个集合A A A B B B
J C = ∣ A ⋂ B ∣ ∣ A ⋃ B ∣ = ∣ A ⋂ B ∣ ∣ A ∣ + ∣ B ∣ − ∣ A ⋂ B ∣ JC=\frac{|A\bigcap B|}{|A\bigcup B|}=\frac{|A\bigcap B|}{|A|+|B|-|A\bigcap B|} J C = ∣ A ⋃ B ∣ ∣ A ⋂ B ∣ = ∣ A ∣ + ∣ B ∣ − ∣ A ⋂ B ∣ ∣ A ⋂ B ∣ Jaccard系数可以用来描述两个集合的相似程度。
推论：假设全集U U U n n n A ⊆ U A\subseteq U A ⊆ U B ⊆ U B\subseteq U B ⊆ U
元素同时在集合A A A B B B M 11 M_{11} M 11
元素出现在集合A A A B B B M 10 M_{10} M 10
元素没有出现在集合A A A B B B M 01 M_{01} M 01
元素既没有出现在集合A A A B B B M 00 M_{00} M 00
根据Jaccard系数的定义，此时的Jaccard系数为如下公式
J C = M 11 M 11 + M 10 + M 01 \mathrm{JC}=\frac{M_{11}}{M_{11}+M_{10}+M_{01}} JC = M 11 + M 10 + M 01 M 11 由于聚类属于无监督学习，事先并不知道聚类后样本所属类别的类别标记所代表的意义，即便参考模型的类别标记意义是已知的，我们也无法知道聚类后的类别标记与参考模型的类别标记是如何对应的，况且聚类后的类别总数与参考模型的类别总数还可能不一样，因此只用单个样本无法衡量聚类性能的好坏。
由于外部指标的基本思想就是以参考模型的类别划分为参照，因此如果某一个样本对中的两个样本在聚类结果中同属于一个类，在参考模型中也同属于一个类，或者这两个样本在聚类结果中不同属于一个类，在参考模型中也不同属于一个类，那么对于这两个样本来说这是一个好的聚类结果。
总的来说所有样本对中的两个样本共存在四种情况：
样本对中的两个样本在聚类结果中属于同一个类，在参考模型中也属于同一个类；
样本对中的两个样本在聚类结果中属于同一个类，在参考模型中不属于同一个类；
样本对中的两个样本在聚类结果中不属于同一个类，在参考模型中属于同一个类；
样本对中的两个样本在聚类结果中不属于同一个类，在参考模型中也不属于同一个类。
综上所述，即所有样本对存在着书中式(9.1)
~式(9.4)的四种情况，现在假设集合A A A A = S S ⋃ S D A=SS\bigcup SD A = S S ⋃ S D B B B B = S S ⋃ D S B=SS\bigcup DS B = S S ⋃ D S
J C = ∣ A ⋂ B ∣ ∣ A ⋃ B ∣ = ∣ S S ∣ ∣ S S ⋃ S D ⋃ D S ∣ = a a + b + c \mathrm{JC}=\frac{|A\bigcap B|}{|A\bigcup B|}=\frac{|SS|}{|SS\bigcup SD\bigcup DS|}=\frac{a}{a+b+c} JC = ∣ A ⋃ B ∣ ∣ A ⋂ B ∣ = ∣ S S ⋃ S D ⋃ D S ∣ ∣ S S ∣ = a + b + c a 也可直接将书中式(9.1)
~式(9.4)的四种情况类比推论，即M 11 = a M_{11}=a M 11 = a M 10 = b M_{10}=b M 10 = b M 01 = c M_{01}=c M 01 = c
J C = M 11 M 11 + M 10 + M 01 = a a + b + c \mathrm{JC}=\frac{M_{11}}{M_{11}+M_{10}+M_{01}}=\frac{a}{a+b+c} JC = M 11 + M 10 + M 01 M 11 = a + b + c a 9.2.2 式(9.6)的解释
其中a a + b \frac{a}{a+b} a + b a a a + c \frac{a}{a+c} a + c a a a a a + b a+b a + b a + c a+c a + c
9.2.3 式(9.7)的解释
Rand Index定义如下：
R I = a + d a + b + c + d = a + d m ( m − 1 ) / 2 = 2 ( a + d ) m ( m − 1 ) \mathrm{RI}=\frac{a+d}{a+b+c+d}=\frac{a+d}{m(m-1)/2}=\frac{2(a+d)}{m(m-1)} RI = a + b + c + d a + d = m ( m − 1 ) /2 a + d = m ( m − 1 ) 2 ( a + d ) 由第一个等号可知RI肯定不大于1。之所以 a + b + c + d = m ( m − 1 ) / 2 a+b+c+d=m(m-1) / 2 a + b + c + d = m ( m − 1 ) /2 ( x i , x j ) \left(\boldsymbol{x}_i, \boldsymbol{x}_j\right) ( x i , x j ) ( i ≠ j ) (i \neq j) ( i = j ) i = 1 i=1 i = 1 j j j m m m m − 1 m-1 m − 1 i = 2 i=2 i = 2 j j j m m m m − 2 m-2 m − 2 ⋯ ⋯ , i = m − 1 \cdots \cdots, i=m-1 ⋯⋯ , i = m − 1 j j j m m m ( x i , x j ) \left(\boldsymbol{x}_i, \boldsymbol{x}_j\right) ( x i , x j ) m − 1 m - 1 m − 1 m ( m − 1 ) / 2 m(m-1) / 2 m ( m − 1 ) /2
这个指标可以理解为两个样本都属于聚类结果和参考模型中的同一类的样本对的个数与两个样本都分别不属于聚类结果和参考模型中的同一类的样本对的个数的总和在所有样本对中出现的频率，可以简单理解为聚类结果与参考模型的一致性。
9.2.4 式(9.8)的解释
簇内距离的定义式：求和号左边是( x i , x j ) (x_i, x_j) ( x i , x j )
9.2.5 式(9.12)的解释
式中, k k k avg ( C i ) \operatorname{avg}\left(C_i\right) avg ( C i ) avg ( C j ) \operatorname{avg}\left(C_j\right) avg ( C j ) d cen ( C i , C j ) d_{\text {cen }}\left(C_i, C_j\right) d cen ( C i , C j ) d cen ( μ i , μ j ) d_{\text {cen }}\left(\boldsymbol{\mu}_i, \boldsymbol{\mu}_j\right) d cen ( μ i , μ j ) d cen ( C i , C j ) d_{\text {cen }}\left(C_i, C_j\right) d cen ( C i , C j )
9.3 距离计算
距离计算在各种算法中都很常见，本节介绍的距离计算方式和"西瓜书"10.6节介绍的马氏距离基本囊括了一般的距离计算方法。另外可能还会碰到"西瓜书"10.5节的测地线距离。
本节有很多概念和名词很常见，比如本节开篇介绍的距离度量的四个基本性质、闵可夫斯基距离、欧氏距离、曼哈顿距离、切比雪夫距离、数值属性、离散属性、有序属性、无序属性、非度量距离等，注意对应的中文和英文。
9.3.1 式(9.21)的解释
该式符号较为抽象, 下面计算"西瓜书"第 76 页表4.1西瓜数据集2.0属性根蒂上
"蜷缩" 和 "稍 蜷"两个离散值之间的距离。
此时, u u u a a a b b b k = 2 k=2 k = 2
从"西瓜书"表4.1中可知, 根蒂为蜷缩的样本共有 8 个 (编号 1 ∼ 5 1\sim 5 1 ∼ 5 16 ∼ 17 16\sim 17 16 ∼ 17 m u , a = 8 m_{u, a}=8 m u , a = 8 6 ∼ 9 6 \sim 9 6 ∼ 9 13 ∼ 15 13 \sim 15 13 ∼ 15 m u , b = 7 m_{u, b}=7 m u , b = 7 i = 1 i=1 i = 1 i = 2 i=2 i = 2 1 ∼ 5 1 \sim 5 1 ∼ 5 m u , a , 1 = 5 m_{u, a, 1}=5 m u , a , 1 = 5 m u , b , 1 = 3 m_{u, b, 1}=3 m u , b , 1 = 3 16 ∼ 17 16 \sim 17 16 ∼ 17 m u , a , 2 = 3 m_{u, a, 2}=3 m u , a , 2 = 3 13 ∼ 15 ) 13 \sim 15) 13 ∼ 15 ) m u , b , 2 = 4 m_{u, b, 2}=4 m u , b , 2 = 4
VDM p ( a , b ) = ∣ m u , a , 1 m u , a − m u , b , 1 m u , b ∣ p + ∣ m u , a , 2 m u , a − m u , b , 2 m u , b ∣ p = ∣ 5 8 − 3 7 ∣ p + ∣ 3 8 − 4 7 ∣ p \begin{aligned}
\operatorname{VDM}_p(a, b) & =\left|\frac{m_{u, a, 1}}{m_{u, a}}-\frac{m_{u, b, 1}}{m_{u, b}}\right|^p+\left|\frac{m_{u, a, 2}}{m_{u, a}}-\frac{m_{u, b, 2}}{m_{u, b}}\right|^p \\
& =\left|\frac{5}{8}-\frac{3}{7}\right|^p+\left|\frac{3}{8}-\frac{4}{7}\right|^p
\end{aligned} VDM p ( a , b ) = m u , a m u , a , 1 − m u , b m u , b , 1 p + m u , a m u , a , 2 − m u , b m u , b , 2 p = 8 5 − 7 3 p + 8 3 − 7 4 p 9.4 原型聚类
本节介绍了三个原型聚类算法, 其中 k k k
前两个聚类算法比较易懂, 下面主要推导第三个聚类算法：高斯混合聚类。
9.4.1 式(9.28)的解释
该式就是多元高斯分布概率密度函数的定义式:
p ( x ) = 1 ( 2 π ) n 2 ∣ Σ ∣ 1 2 e − 1 2 ( x − μ ) ⊤ Σ − 1 ( x − μ ) p(\boldsymbol{x})=\frac{1}{(2 \pi)^{\frac{n}{2}}|\boldsymbol{\Sigma}|^{\frac{1}{2}}} e^{-\frac{1}{2}(\boldsymbol{x}-\boldsymbol{\mu})^{\top} \boldsymbol{\Sigma}^{-1}(\boldsymbol{x}-\boldsymbol{\mu})} p ( x ) = ( 2 π ) 2 n ∣ Σ ∣ 2 1 1 e − 2 1 ( x − μ ) ⊤ Σ − 1 ( x − μ ) 对应到我们常见的一元高斯分布概率密度函数的定义式:
p ( x ) = 1 2 π σ e − ( x − μ ) 2 2 σ 2 p(x)=\frac{1}{\sqrt{2 \pi} \sigma} e^{-\frac{(x-\mu)^2}{2 \sigma^2}} p ( x ) = 2 π σ 1 e − 2 σ 2 ( x − μ ) 2 其中 2 π = ( 2 π ) 1 2 \sqrt{2 \pi}=(2 \pi)^{\frac{1}{2}} 2 π = ( 2 π ) 2 1 ( 2 π ) n 2 , σ (2 \pi)^{\frac{n}{2}}, \sigma ( 2 π ) 2 n , σ ∣ Σ ∣ 1 2 |\boldsymbol{\Sigma}|^{\frac{1}{2}} ∣ Σ ∣ 2 1 σ 2 \sigma^2 σ 2 Σ \boldsymbol{\Sigma} Σ ( x − μ ) 2 σ 2 对应 ( x − μ ) ⊤ Σ − 1 ( x − μ ) \frac{(x-\mu)^2}{\sigma^2} \text { 对应 }(\boldsymbol{x}-\boldsymbol{\mu})^{\top} \boldsymbol{\Sigma}^{-1}(\boldsymbol{x}-\boldsymbol{\mu}) σ 2 ( x − μ ) 2 对应 ( x − μ ) ⊤ Σ − 1 ( x − μ )
概率密度函数 p ( x ) p(\boldsymbol{x}) p ( x ) x \boldsymbol{x} x x \boldsymbol{x} x p ( x ) p(\boldsymbol{x}) p ( x ) x \boldsymbol{x} x p ( x ) p(\boldsymbol{x}) p ( x ) p ( x ) p(x) p ( x ) p ( x ) = 0 p(x)=0 p ( x ) = 0 ∫ p ( x ) d x = 1 \int p(x) \mathrm{d} x=1 ∫ p ( x ) d x = 1 p ( x ) p(\boldsymbol{x}) p ( x ) p ( x ) = 0 p(\boldsymbol{x})=0 p ( x ) = 0 ∫ p ( x ) d x = 1 \int p(\boldsymbol{x}) \mathrm{d} \boldsymbol{x}=1 ∫ p ( x ) d x = 1
注意, "西瓜书"中后面将 p ( x ) p(\boldsymbol{x}) p ( x ) p ( x ∣ μ , Σ ) p(\boldsymbol{x} \mid \boldsymbol{\mu}, \boldsymbol{\Sigma}) p ( x ∣ μ , Σ )
9.4.2 式(9.29)的解释
对于该式表达的高斯混合分布概率密度函数
p M ( x ) p_{\mathcal{M}}(\boldsymbol{x}) p M ( x ) ( 9.28 ) (9.28) ( 9.28 ) p ( x ) p(\boldsymbol{x}) p ( x ) k k k p ( x ) p(\boldsymbol{x}) p ( x ) μ , Σ \boldsymbol{\mu}, \boldsymbol{\Sigma} μ , Σ p M ( x ) p_{\mathcal{M}}(\boldsymbol{x}) p M ( x ) k k k α i \alpha_i α i k k k μ i , Σ i \boldsymbol{\mu}_i, \boldsymbol{\Sigma}_i μ i , Σ i
在"西瓜书"中该式下方(P207 最后一段)中介绍了样本的生成过程, 实际也反应了
"混合系数" α i \alpha_i α i α i \alpha_i α i i i i α i \alpha_i α i i i i α 1 , α 2 , … , α k \alpha_1, \alpha_2, \ldots, \alpha_k α 1 , α 2 , … , α k i i i α i \alpha_i α i i i i μ i , Σ i \boldsymbol{\mu}_i, \boldsymbol{\Sigma}_i μ i , Σ i p ( x ∣ μ i , Σ i ) p\left(\boldsymbol{x} \mid \boldsymbol{\mu}_i, \boldsymbol{\Sigma}_i\right) p ( x ∣ μ i , Σ i ) μ , Σ \boldsymbol{\mu}, \boldsymbol{\Sigma} μ , Σ μ i , Σ i ) \left.\boldsymbol{\mu}_i, \boldsymbol{\Sigma}_i\right) μ i , Σ i ) x \boldsymbol{x} x k k k x \boldsymbol{x} x p ( x ∣ μ i , Σ i p\left(\boldsymbol{x} \mid \boldsymbol{\mu}_i, \boldsymbol{\Sigma}_i\right. p ( x ∣ μ i , Σ i x \boldsymbol{x} x p ( x ∣ μ i , Σ i ) p\left(\boldsymbol{x} \mid \boldsymbol{\mu}_i, \boldsymbol{\Sigma}_i\right) p ( x ∣ μ i , Σ i )
9.4.3 式(9.30)的解释
若由上述样本生成方式得到训练集
D = { x 1 , x 2 , … , x m } D=\left\{\boldsymbol{x}_1, \boldsymbol{x}_2, \ldots, \boldsymbol{x}_m\right\} D = { x 1 , x 2 , … , x m } x j \boldsymbol{x}_j x j p M ( z j ∣ x j ) p_{\mathcal{M}}\left(z_j \mid \boldsymbol{x}_j\right) p M ( z j ∣ x j ) z j ∈ { 1 , 2 , … , k } z_j \in\{1,2, \ldots, k\} z j ∈ { 1 , 2 , … , k }
对于任意样本, 在不考虑样本本身之前 (即先验), 若瞎猜一下它由第 i i i P ( z j = i ) P\left(z_j=i\right) P ( z j = i ) α 1 , α 2 , … , α k \alpha_1, \alpha_2, \ldots, \alpha_k α 1 , α 2 , … , α k P ( z j = i ) = α i P\left(z_j=i\right)=\alpha_i P ( z j = i ) = α i i i i p M ( z j = i ∣ x j ) p_{\mathcal{M}}\left(z_j=i \mid \boldsymbol{x}_j\right) p M ( z j = i ∣ x j ) p M ( z j = i ∣ x j ) p_{\mathcal{M}}\left(z_j=i \mid \boldsymbol{x}_j\right) p M ( z j = i ∣ x j )
p M ( z j = i ∣ x j ) = P ( z j = i ) ⋅ p M ( x j ∣ z j = i ) p M ( x j ) p_{\mathcal{M}}\left(z_j=i \mid \boldsymbol{x}_j\right)=\frac{P\left(z_j=i\right) \cdot p_{\mathcal{M}}\left(\boldsymbol{x}_j \mid z_j=i\right)}{p_{\mathcal{M}}\left(\boldsymbol{x}_j\right)} p M ( z j = i ∣ x j ) = p M ( x j ) P ( z j = i ) ⋅ p M ( x j ∣ z j = i ) 分子第 1 项 P ( z j = i ) = α i P\left(z_j=i\right)=\alpha_i P ( z j = i ) = α i i i i x j \boldsymbol{x}_j x j p ( x j ∣ μ i , Σ i ) p\left(\boldsymbol{x}_j \mid \boldsymbol{\mu}_i, \boldsymbol{\Sigma}_i\right) p ( x j ∣ μ i , Σ i ) x , μ , Σ \boldsymbol{x}, \boldsymbol{\mu}, \boldsymbol{\Sigma} x , μ , Σ x j , μ i , Σ i \boldsymbol{x}_j, \boldsymbol{\mu}_i, \boldsymbol{\Sigma}_i x j , μ i , Σ i p M ( x j ) p_{\mathcal{M}}\left(\boldsymbol{x}_j\right) p M ( x j ) x j \boldsymbol{x}_j x j
注意, "西瓜书"中后面将
p M ( z j = i ∣ x j ) p_{\mathcal{M}}\left(z_j=i \mid \boldsymbol{x}_j\right) p M ( z j = i ∣ x j ) γ j i \gamma_{j i} γ j i 1 ≤ j ≤ m , 1 ≤ i ≤ k 1 \leq j \leq m, 1 \leq i \leq k 1 ≤ j ≤ m , 1 ≤ i ≤ k
9.4.4 式(9.31)的解释
若将所有 γ j i \gamma_{j i} γ j i Γ \Gamma Γ γ j i \gamma_{j i} γ j i j j j Γ \Gamma Γ m × k m \times k m × k
Γ = [ γ 11 γ 12 ⋯ γ 1 k γ 21 γ 22 ⋯ γ 2 k ⋮ ⋮ ⋱ ⋮ γ m 1 γ m 2 ⋯ γ m k ] m × k \Gamma=\left[\begin{array}{cccc}
\gamma_{11} & \gamma_{12} & \cdots & \gamma_{1 k} \\
\gamma_{21} & \gamma_{22} & \cdots & \gamma_{2 k} \\
\vdots & \vdots & \ddots & \vdots \\
\gamma_{m 1} & \gamma_{m 2} & \cdots & \gamma_{m k}
\end{array}\right]_{m \times k} Γ = γ 11 γ 21 ⋮ γ m 1 γ 12 γ 22 ⋮ γ m 2 ⋯ ⋯ ⋱ ⋯ γ 1 k γ 2 k ⋮ γ mk m × k 其中 m m m k k k Γ \Gamma Γ j j j k k k
9.4.5 式(9.32)的解释
对于训练集
D = { x 1 , x 2 , … , x m } D=\left\{\boldsymbol{x}_1, \boldsymbol{x}_2, \ldots, \boldsymbol{x}_m\right\} D = { x 1 , x 2 , … , x m } m m m k k k D D D k k k
现在的问题是, k k k { ( μ i , Σ i ) ∣ 1 ⩽ i ⩽ k } \left\{\left(\boldsymbol{\mu}_i, \boldsymbol{\Sigma}_i\right) \mid 1 \leqslant i \leqslant k\right\} { ( μ i , Σ i ) ∣ 1 ⩽ i ⩽ k } α 1 , α 2 , … , α k \alpha_1, \alpha_2, \ldots, \alpha_k α 1 , α 2 , … , α k m m m
其实这跟 k k k k k k m m m
本节的高斯混合聚类求解方法与 k k k 7.6 7.6 7.6
具体来说, 现假设已知式(9.30)的后验概率, 此时即可通过式(9.31)知道 m m m { ( α i , μ i , Σ i ) ∣ 1 ⩽ i ⩽ k } \left\{\left(\alpha_i, \boldsymbol{\mu}_i, \boldsymbol{\Sigma}_i\right) \mid 1 \leqslant i \leqslant k\right\} { ( α i , μ i , Σ i ) ∣ 1 ⩽ i ⩽ k } x j \boldsymbol{x}_j x j p M ( x j ) p_{\mathcal{M}}\left(\boldsymbol{x}_j\right) p M ( x j ) D D D x j \boldsymbol{x}_j x j { ( α i , μ i , Σ i ) ∣ 1 ⩽ i ⩽ k } \left\{\left(\alpha_i, \boldsymbol{\mu}_i, \boldsymbol{\Sigma}_i\right) \mid 1 \leqslant i \leqslant k\right\} { ( α i , μ i , Σ i ) ∣ 1 ⩽ i ⩽ k } p M ( x j ) p_{\mathcal{M}}\left(\boldsymbol{x}_j\right) p M ( x j ) m m m ∏ j = 1 m p M ( x j ) \prod_{j=1}^m p_{\mathcal{M}}\left(\boldsymbol{x}_j\right) ∏ j = 1 m p M ( x j ) m m m m m m
9.4.6 式(9.33)的推导
根据公式(9.28)可知：
p ( x j ∣ μ i , Σ i ) = 1 ( 2 π ) n 2 ∣ Σ i ∣ 1 2 exp ( − 1 2 ( x j − μ i ) T Σ i − 1 ( x j − μ i ) ) p\left(\boldsymbol{x}_{j} | \boldsymbol{\mu}_{i}, \boldsymbol{\Sigma}_{i}\right)=\frac{1}{(2 \pi)^{\frac{n}{2}}\left|\boldsymbol{\Sigma}_{i}\right|^{\frac{1}{2}}} \exp \left(-\frac{1}{2}\left(\boldsymbol{x}_{j}-\boldsymbol{\mu}_{i}\right)^{T} \boldsymbol{\Sigma}_{i}^{-1}\left(\boldsymbol{x}_{j}-\boldsymbol{\mu}_{i}\right)\right) p ( x j ∣ μ i , Σ i ) = ( 2 π ) 2 n ∣ Σ i ∣ 2 1 1 exp ( − 2 1 ( x j − μ i ) T Σ i − 1 ( x j − μ i ) ) 又根据公式(9.32)，由
∂ L L ( D ) ∂ μ i = ∂ L L ( D ) ∂ p ( x j ∣ μ i , Σ i ) ⋅ ∂ p ( x j ∣ μ i , Σ i ) ∂ μ i = 0 \frac{\partial L L(D)}{\partial \boldsymbol{\mu}_{i}}=\frac{\partial L L(D)}{\partial p\left(\boldsymbol{x}_{j} | \boldsymbol{\mu}_{i}, \boldsymbol{\Sigma}_{i}\right)} \cdot \frac{\partial p\left(\boldsymbol{x}_{j} | \boldsymbol{\mu}_{i}, \boldsymbol{\Sigma}_{i}\right)}{\partial \boldsymbol{\mu}_{i}}=0 ∂ μ i ∂ LL ( D ) = ∂ p ( x j ∣ μ i , Σ i ) ∂ LL ( D ) ⋅ ∂ μ i ∂ p ( x j ∣ μ i , Σ i ) = 0 其中：
∂ L L ( D ) ∂ p ( x j ∣ μ i , Σ i ) = ∂ ∑ j = 1 m ln ( ∑ l = 1 k α l ⋅ p ( x j ∣ μ l , Σ l ) ) ∂ p ( x j ∣ μ i , Σ i ) = ∑ j = 1 m ∂ ln ( ∑ l = 1 k α l ⋅ p ( x j ∣ μ l , Σ l ) ) ∂ p ( x j ∣ μ i , Σ i ) = ∑ j = 1 m α i ∑ l = 1 k α l ⋅ p ( x j ∣ μ l , Σ l ) \begin{aligned}
\frac{\partial L L(D)}{\partial p\left(\boldsymbol{x}_{j} | \boldsymbol{\mu}_{i}, \mathbf{\Sigma}_{i}\right)} &=\frac{\partial \sum_{j=1}^{m} \ln \left(\sum_{l=1}^{k} \alpha_{l} \cdot p\left(\boldsymbol{x}_{j} | \boldsymbol{\mu}_{l}, \boldsymbol{\Sigma}_{l}\right)\right)}{\partial p\left(\boldsymbol{x}_{j} | \boldsymbol{\mu}_{i}, \boldsymbol{\Sigma}_{i}\right)} \\
&=\sum_{j=1}^{m} \frac{\partial \ln \left(\sum_{l=1}^{k} \alpha_{l} \cdot p\left(\boldsymbol{x}_{j} | \boldsymbol{\mu}_{l}, \boldsymbol{\Sigma}_{l}\right)\right)}{\partial p\left(\boldsymbol{x}_{j} | \boldsymbol{\mu}_{i}, \boldsymbol{\Sigma}_{i}\right)} \\
&=\sum_{j=1}^{m} \frac{\alpha_{i}}{\sum_{l=1}^{k} \alpha_{l} \cdot p\left(\boldsymbol{x}_{j} | \boldsymbol{\mu}_{l}, \boldsymbol{\Sigma}_{l}\right)}
\end{aligned} ∂ p ( x j ∣ μ i , Σ i ) ∂ LL ( D ) = ∂ p ( x j ∣ μ i , Σ i ) ∂ ∑ j = 1 m ln ( ∑ l = 1 k α l ⋅ p ( x j ∣ μ l , Σ l ) ) = j = 1 ∑ m ∂ p ( x j ∣ μ i , Σ i ) ∂ ln ( ∑ l = 1 k α l ⋅ p ( x j ∣ μ l , Σ l ) ) = j = 1 ∑ m ∑ l = 1 k α l ⋅ p ( x j ∣ μ l , Σ l ) α i ∂ p ( x j ∣ μ i , Σ i ) ∂ μ i = ∂ 1 ( 2 π ) n 2 ∣ Σ i ∣ 1 2 exp ( − 1 2 ( x j − μ i ) ⊤ Σ i − 1 ( x j − μ i ) ) ∂ μ i = 1 ( 2 π ) n 2 ∣ Σ i ∣ 1 2 ⋅ ∂ exp ( − 1 2 ( x j − μ i ) ⊤ Σ i − 1 ( x j − μ i ) ) ∂ μ i = 1 ( 2 π ) n 2 ∣ Σ i ∣ 1 2 ⋅ exp ( − 1 2 ( x j − μ i ) ⊤ Σ i − 1 ( x j − μ i ) ) ⋅ − 1 2 ∂ ( x j − μ i ) ⊤ Σ i − 1 ( x j − μ i ) ∂ μ i = 1 ( 2 π ) n 2 ∣ Σ i ∣ 1 2 ⋅ exp ( − 1 2 ( x j − μ i ) ⊤ Σ i − 1 ( x j − μ i ) ) ⋅ Σ i − 1 ( x j − μ i ) = p ( x j ∣ μ i , Σ i ) ⋅ Σ i − 1 ( x j − μ i ) \begin{aligned}
\frac{\partial p\left(\boldsymbol{x}_{j} | \boldsymbol{\mu}_{i}, \boldsymbol{\Sigma}_{i}\right)}{\partial \boldsymbol{\mu}_{i}} &=\frac{\partial \frac{1}{(2 \pi)^{\frac{n}{2}}\left|\Sigma_{i}\right|^{\frac{1}{2}}} \exp\left({-\frac{1}{2}\left(\boldsymbol{x}_{j}-\boldsymbol{\mu}_{i}\right)^{\top}\boldsymbol{\Sigma}_{i}^{-1}\left(\boldsymbol{x}_{j}-\boldsymbol{\mu}_{i}\right)}\right)}{\partial \boldsymbol{\mu}_{i}} \\
&=\frac{1}{(2 \pi)^{\frac{n}{2}}\left|\boldsymbol{\Sigma}_{i}\right|^{\frac{1}{2}}} \cdot \frac{\partial \exp\left({-\frac{1}{2}\left(\boldsymbol{x}_{j}-\boldsymbol{\mu}_{i}\right)^{\top} \boldsymbol{\Sigma}_{i}^{-1}\left(\boldsymbol{x}_{j}-\boldsymbol{\mu}_{i}\right)}\right)}{\partial \boldsymbol{\mu}_{i}}\\
&=\frac{1}{(2 \pi)^{\frac{n}{2}}\left|\boldsymbol{\Sigma}_{i}\right|^{\frac{1}{2}}}\cdot \exp\left({-\frac{1}{2}\left(\boldsymbol{x}_{j}-\boldsymbol{\mu}_{i}\right)^{\top} \boldsymbol{\Sigma}_{i}^{-1}\left(\boldsymbol{x}_{j}-\boldsymbol{\mu}_{i}\right)}\right) \cdot-\frac{1}{2} \frac{\partial\left(\boldsymbol{x}_{j}-\boldsymbol{\mu}_{i}\right)^{\top} \boldsymbol{\Sigma}_{i}^{-1}\left(\boldsymbol{x}_{j}-\boldsymbol{\mu}_{i}\right)}{\partial \boldsymbol{\mu}_{i}}\\
&=\frac{1}{(2 \pi)^{\frac{n}{2}}\left|\boldsymbol{\Sigma}_{i}\right|^{\frac{1}{2}}}\cdot \exp\left({-\frac{1}{2}\left(\boldsymbol{x}_{j}-\boldsymbol{\mu}_{i}\right)^{\top} \boldsymbol{\Sigma}_{i}^{-1}\left(\boldsymbol{x}_{j}-\boldsymbol{\mu}_{i}\right)}\right) \cdot\boldsymbol{\Sigma}_{i}^{-1}\left(\boldsymbol{x}_{j}-\boldsymbol{\mu}_{i}\right)\\
&=p\left(\boldsymbol{x}_{j} | \boldsymbol{\mu}_{i}, \boldsymbol{\Sigma}_{i}\right) \cdot \boldsymbol{\Sigma}_{i}^{-1}\left(\boldsymbol{x}_{j}-\boldsymbol{\mu}_{i}\right)
\end{aligned} ∂ μ i ∂ p ( x j ∣ μ i , Σ i ) = ∂ μ i ∂ ( 2 π ) 2 n ∣ Σ i ∣ 2 1 1 exp ( − 2 1 ( x j − μ i ) ⊤ Σ i − 1 ( x j − μ i ) ) = ( 2 π ) 2 n ∣ Σ i ∣ 2 1 1 ⋅ ∂ μ i ∂ exp ( − 2 1 ( x j − μ i ) ⊤ Σ i − 1 ( x j − μ i ) ) = ( 2 π ) 2 n ∣ Σ i ∣ 2 1 1 ⋅ exp ( − 2 1 ( x j − μ i ) ⊤ Σ i − 1 ( x j − μ i ) ) ⋅ − 2 1 ∂ μ i ∂ ( x j − μ i ) ⊤ Σ i − 1 ( x j − μ i ) = ( 2 π ) 2 n ∣ Σ i ∣ 2 1 1 ⋅ exp ( − 2 1 ( x j − μ i ) ⊤ Σ i − 1 ( x j − μ i ) ) ⋅ Σ i − 1 ( x j − μ i ) = p ( x j ∣ μ i , Σ i ) ⋅ Σ i − 1 ( x j − μ i ) 其中，由矩阵求导的法则∂ a T X a ∂ a = 2 X a \frac{\partial \mathbf{a}^{T} \mathbf{X} \mathbf{a}}{\partial \mathbf{a}}=2\mathbf{X} \mathbf{a} ∂ a ∂ a T Xa = 2 Xa
− 1 2 ∂ ( x j − μ i ) ⊤ Σ i − 1 ( x j − μ i ) ∂ μ i = − 1 2 ⋅ 2 Σ i − 1 ( μ i − x j ) = Σ i − 1 ( x j − μ i ) \begin{aligned}
-\frac{1}{2} \frac{\partial\left(\boldsymbol{x}_{j}-\boldsymbol{\mu}_{i}\right)^{\top} \boldsymbol{\Sigma}_{i}^{-1}\left(\boldsymbol{x}_{j}-\boldsymbol{\mu}_{i}\right)}{\partial \boldsymbol{\mu}_{i}} &=-\frac{1}{2} \cdot 2 \boldsymbol{\Sigma}_{i}^{-1}\left(\boldsymbol{\mu}_{i}-\boldsymbol{x}_{j}\right) \\
&=\boldsymbol{\Sigma}_{i}^{-1}\left(\boldsymbol{x}_{j}-\boldsymbol{\mu}_{i}\right)
\end{aligned} − 2 1 ∂ μ i ∂ ( x j − μ i ) ⊤ Σ i − 1 ( x j − μ i ) = − 2 1 ⋅ 2 Σ i − 1 ( μ i − x j ) = Σ i − 1 ( x j − μ i ) 因此有：
∂ L L ( D ) ∂ μ i = ∑ j = 1 m α i ∑ l = 1 k α l ⋅ p ( x j ∣ μ l , Σ l ) ⋅ p ( x j ∣ μ i , Σ i ) ⋅ Σ i − 1 ( x j − μ i ) = 0 \frac{\partial L L(D)}{\partial \boldsymbol{\mu}_{i}}=\sum_{j=1}^{m} \frac{\alpha_{i}}{\sum_{l=1}^{k} \alpha_{l} \cdot p\left(\boldsymbol{x}_{j} | \boldsymbol{\mu}_{l}, \mathbf{\Sigma}_{l}\right)} \cdot p\left(\boldsymbol{x}_{j} | \boldsymbol{\mu}_{i}, \boldsymbol{\Sigma}_{i}\right) \cdot \boldsymbol{\Sigma}_{i}^{-1}\left(\boldsymbol{x}_{j}-\boldsymbol{\mu}_{i}\right)=0 ∂ μ i ∂ LL ( D ) = j = 1 ∑ m ∑ l = 1 k α l ⋅ p ( x j ∣ μ l , Σ l ) α i ⋅ p ( x j ∣ μ i , Σ i ) ⋅ Σ i − 1 ( x j − μ i ) = 0 9.4.7 式(9.34)的推导
由式(9.30)
γ j i = p M ( z j = i ∣ X j ) = α i ⋅ p ( X j ∣ μ i , Σ i ) ∑ l = 1 k α l ⋅ p ( X j ∣ μ l , Σ l ) \gamma_{j i}=p_{\mathcal{M}}\left(z_{j}=i | \mathbf{X}_{j}\right)=\frac{\alpha_{i} \cdot p\left(\mathbf{X}_{j} | \boldsymbol{\mu}_{i}, \boldsymbol{\Sigma}_{i}\right)}{\sum_{l=1}^{k} \alpha_{l} \cdot p\left(\mathbf{X}_{j} | \boldsymbol{\mu}_{l}, \boldsymbol{\Sigma}_{l}\right)} γ j i = p M ( z j = i ∣ X j ) = ∑ l = 1 k α l ⋅ p ( X j ∣ μ l , Σ l ) α i ⋅ p ( X j ∣ μ i , Σ i ) 带入式(9.33)
∑ j = 1 m γ j i ( X j − μ i ) = 0 \sum_{j=1}^{m} \gamma_{j i}\left(\mathbf{X}_{j}-\boldsymbol{\mu}_{i}\right)=0 j = 1 ∑ m γ j i ( X j − μ i ) = 0 移项, 得
∑ j = 1 m γ j i x j = ∑ j = 1 m γ j i μ i = μ i ⋅ ∑ j = 1 m γ j i \sum_{j=1}^m \gamma_{j i} \boldsymbol{x}_j=\sum_{j=1}^m \gamma_{j i} \boldsymbol{\mu}_i=\boldsymbol{\mu}_i \cdot \sum_{j=1}^m \gamma_{j i} j = 1 ∑ m γ j i x j = j = 1 ∑ m γ j i μ i = μ i ⋅ j = 1 ∑ m γ j i 第二个等号是因为 μ i \mu_i μ i j j j
μ i = ∑ j = 1 m γ j i x j ∑ j = 1 m γ j i \boldsymbol{\mu}_i=\frac{\sum_{j=1}^m \gamma_{j i} \boldsymbol{x}_j}{\sum_{j=1}^m \gamma_{j i}} μ i = ∑ j = 1 m γ j i ∑ j = 1 m γ j i x j 9.4.8 式(9.35)的推导
根据公式(9.28)可知：
p ( x j ∣ μ i , Σ i ) = 1 ( 2 π ) n 2 ∣ Σ i ∣ 1 2 exp ( − 1 2 ( x j − μ i ) T Σ i − 1 ( x j − μ i ) ) p(\boldsymbol x_{j}|\boldsymbol\mu_{i},\boldsymbol\Sigma_{i})=\cfrac{1}{(2\pi)^\frac{n}{2}\left| \boldsymbol\Sigma_{i}\right |^\frac{1}{2}}\exp\left({-\frac{1}{2}(\boldsymbol x_{j}-\boldsymbol\mu_{i})^T\boldsymbol\Sigma_{i}^{-1}(\boldsymbol x_{j}-\boldsymbol\mu_{i})}\right) p ( x j ∣ μ i , Σ i ) = ( 2 π ) 2 n ∣ Σ i ∣ 2 1 1 exp ( − 2 1 ( x j − μ i ) T Σ i − 1 ( x j − μ i ) ) 又根据公式(9.32)，由
∂ L L ( D ) ∂ Σ i = 0 \cfrac{\partial LL(D)}{\partial \boldsymbol\Sigma_{i}}=0 ∂ Σ i ∂ LL ( D ) = 0 可得
∂ L L ( D ) ∂ Σ i = ∂ ∂ Σ i [ ∑ j = 1 m ln ( ∑ i = 1 k α i ⋅ p ( x j ∣ μ i , Σ i ) ) ] = ∑ j = 1 m ∂ ∂ Σ i [ ln ( ∑ i = 1 k α i ⋅ p ( x j ∣ μ i , Σ i ) ) ] = ∑ j = 1 m α i ⋅ ∂ ∂ Σ i ( p ( x j ∣ μ i , Σ i ) ) ∑ l = 1 k α l ⋅ p ( x j ∣ μ l , Σ l ) \begin{aligned}
\cfrac {\partial LL(D)}{\partial\boldsymbol\Sigma_{i}}&=\cfrac {\partial}{\partial \boldsymbol\Sigma_{i}}\left[\sum_{j=1}^m\ln\Bigg(\sum_{i=1}^k \alpha_{i}\cdot p(\boldsymbol x_{j}|\boldsymbol\mu_{i},\boldsymbol\Sigma_{i})\Bigg)\right] \\
&=\sum_{j=1}^m\frac{\partial}{\partial\boldsymbol\Sigma_{i}}\left[\ln\Bigg(\sum_{i=1}^k \alpha_{i}\cdot p(\boldsymbol x_{j}|\boldsymbol\mu_{i},\boldsymbol\Sigma_{i})\Bigg)\right] \\
&=\sum_{j=1}^m\cfrac{\alpha_{i}\cdot \cfrac{\partial}{\partial\boldsymbol\Sigma_{i}}\left(p(\boldsymbol x_{j}|\boldsymbol\mu_{i},\boldsymbol\Sigma_{i})\right)}{\sum_{l=1}^k\alpha_{l}\cdot p(\boldsymbol x_{j}|\boldsymbol\mu_{l},\boldsymbol\Sigma_{l})} \\
\end{aligned} ∂ Σ i ∂ LL ( D ) = ∂ Σ i ∂ [ j = 1 ∑ m ln ( i = 1 ∑ k α i ⋅ p ( x j ∣ μ i , Σ i ) ) ] = j = 1 ∑ m ∂ Σ i ∂ [ ln ( i = 1 ∑ k α i ⋅ p ( x j ∣ μ i , Σ i ) ) ] = j = 1 ∑ m ∑ l = 1 k α l ⋅ p ( x j ∣ μ l , Σ l ) α i ⋅ ∂ Σ i ∂ ( p ( x j ∣ μ i , Σ i ) ) 其中
∂ ∂ Σ i ( p ( x j ∣ μ i , Σ i ) ) = ∂ ∂ Σ i [ 1 ( 2 π ) n 2 ∣ Σ i ∣ 1 2 exp ( − 1 2 ( x j − μ i ) T Σ i − 1 ( x j − μ i ) ) ] = ∂ ∂ Σ i { exp [ ln ( 1 ( 2 π ) n 2 ∣ Σ i ∣ 1 2 exp ( − 1 2 ( x j − μ i ) T Σ i − 1 ( x j − μ i ) ) ) ] } = p ( x j ∣ μ i , Σ i ) ⋅ ∂ ∂ Σ i [ ln ( 1 ( 2 π ) n 2 ∣ Σ i ∣ 1 2 exp ( − 1 2 ( x j − μ i ) T Σ i − 1 ( x j − μ i ) ) ) ] = p ( x j ∣ μ i , Σ i ) ⋅ ∂ ∂ Σ i [ ln 1 ( 2 π ) n 2 − 1 2 ln ∣ Σ i ∣ − 1 2 ( x j − μ i ) T Σ i − 1 ( x j − μ i ) ] = p ( x j ∣ μ i , Σ i ) ⋅ [ − 1 2 ∂ ( ln ∣ Σ i ∣ ) ∂ Σ i − 1 2 ∂ [ ( x j − μ i ) T Σ i − 1 ( x j − μ i ) ] ∂ Σ i ] \begin{aligned}
\cfrac{\partial}{\partial\boldsymbol\Sigma_{i}}\left(p(\boldsymbol x_{j}|\boldsymbol\mu_{i},\boldsymbol\Sigma_{i})\right)&=\cfrac{\partial}{\partial\boldsymbol\Sigma_{i}}\left[\cfrac{1}{(2\pi)^\frac{n}{2}\left| \boldsymbol\Sigma_{i}\right |^\frac{1}{2}}\exp\left({-\frac{1}{2}(\boldsymbol x_{j}-\boldsymbol\mu_{i})^T\boldsymbol\Sigma_{i}^{-1}(\boldsymbol x_{j}-\boldsymbol\mu_{i})}\right)\right] \\
&=\cfrac{\partial}{\partial\boldsymbol\Sigma_{i}}\left\{\exp\left[\ln\left(\cfrac{1}{(2\pi)^\frac{n}{2}\left| \boldsymbol\Sigma_{i}\right |^\frac{1}{2}}\exp\left({-\frac{1}{2}(\boldsymbol x_{j}-\boldsymbol\mu_{i})^T\boldsymbol\Sigma_{i}^{-1}(\boldsymbol x_{j}-\boldsymbol\mu_{i})}\right)\right)\right]\right\} \\
&=p(\boldsymbol x_{j}|\boldsymbol\mu_{i},\boldsymbol\Sigma_{i})\cdot\cfrac{\partial}{\partial\boldsymbol\Sigma_{i}}\left[\ln\left(\cfrac{1}{(2\pi)^\frac{n}{2}\left| \boldsymbol\Sigma_{i}\right |^\frac{1}{2}}\exp\left({-\frac{1}{2}(\boldsymbol x_{j}-\boldsymbol\mu_{i})^T\boldsymbol\Sigma_{i}^{-1}(\boldsymbol x_{j}-\boldsymbol\mu_{i})}\right)\right)\right]\\
&=p(\boldsymbol x_{j}|\boldsymbol\mu_{i},\boldsymbol\Sigma_{i})\cdot\cfrac{\partial}{\partial\boldsymbol\Sigma_{i}}\left[\ln\cfrac{1}{(2\pi)^{\frac{n}{2}}}-\cfrac{1}{2}\ln{|\boldsymbol{\Sigma}_i|}-\frac{1}{2}(\boldsymbol x_j-\boldsymbol\mu_i)^T\boldsymbol{\Sigma}_i^{-1}(\boldsymbol x_j-\boldsymbol\mu_i)\right]\\
&=p(\boldsymbol x_{j}|\boldsymbol\mu_{i},\boldsymbol\Sigma_{i})\cdot\left[-\cfrac{1}{2}\cfrac{\partial\left(\ln{|\boldsymbol{\Sigma}_i|}\right) }{\partial \boldsymbol{\Sigma}_i}-\cfrac{1}{2}\cfrac{\partial \left[(\boldsymbol x_j-\boldsymbol\mu_i)^T\boldsymbol{\Sigma}_i^{-1}(\boldsymbol x_j-\boldsymbol\mu_i)\right]}{\partial \boldsymbol{\Sigma}_i}\right]\\
\end{aligned} ∂ Σ i ∂ ( p ( x j ∣ μ i , Σ i ) ) = ∂ Σ i ∂ [ ( 2 π ) 2 n ∣ Σ i ∣ 2 1 1 exp ( − 2 1 ( x j − μ i ) T Σ i − 1 ( x j − μ i ) ) ] = ∂ Σ i ∂ { exp [ ln ( ( 2 π ) 2 n ∣ Σ i ∣ 2 1 1 exp ( − 2 1 ( x j − μ i ) T Σ i − 1 ( x j − μ i ) ) ) ] } = p ( x j ∣ μ i , Σ i ) ⋅ ∂ Σ i ∂ [ ln ( ( 2 π ) 2 n ∣ Σ i ∣ 2 1 1 exp ( − 2 1 ( x j − μ i ) T Σ i − 1 ( x j − μ i ) ) ) ] = p ( x j ∣ μ i , Σ i ) ⋅ ∂ Σ i ∂ [ ln ( 2 π ) 2 n 1 − 2 1 ln ∣ Σ i ∣ − 2 1 ( x j − μ i ) T Σ i − 1 ( x j − μ i ) ] = p ( x j ∣ μ i , Σ i ) ⋅ [ − 2 1 ∂ Σ i ∂ ( ln ∣ Σ i ∣ ) − 2 1 ∂ Σ i ∂ [ ( x j − μ i ) T Σ i − 1 ( x j − μ i ) ] ] 由矩阵微分公式∂ ∣ X ∣ ∂ X = ∣ X ∣ ⋅ ( X − 1 ) T , ∂ a T X − 1 B ∂ X = − X − T a b T X − T \cfrac{\partial |\mathbf{X}|}{\partial \mathbf{X}}=|\mathbf{X}|\cdot(\mathbf{X}^{-1})^{T},\cfrac{\partial \boldsymbol{a}^{T} \mathbf{X}^{-1} \mathbf{B}}{\partial \mathbf{X}}=-\mathbf{X}^{-T} \boldsymbol{a b}^{T} \mathbf{X}^{-T} ∂ X ∂ ∣ X ∣ = ∣ X ∣ ⋅ ( X − 1 ) T , ∂ X ∂ a T X − 1 B = − X − T ab T X − T
∂ ∂ Σ i ( p ( x j ∣ μ i , Σ i ) ) = p ( x j ∣ μ i , Σ i ) ⋅ [ − 1 2 Σ i − 1 + 1 2 Σ i − 1 ( x j − μ i ) ( x j − μ i ) T Σ i − 1 ] \begin{aligned}
\cfrac{\partial}{\partial\boldsymbol\Sigma_{i}}\left(p(\boldsymbol x_{j}|\boldsymbol\mu_{i},\boldsymbol\Sigma_{i})\right)&=p(\boldsymbol x_{j}|\boldsymbol\mu_{i},\boldsymbol\Sigma_{i})\cdot\left[-\cfrac{1}{2}\boldsymbol{\Sigma}_i^{-1}+\cfrac{1}{2}\boldsymbol{\Sigma}_i^{-1}(\boldsymbol x_j-\boldsymbol\mu_i)(\boldsymbol x_j-\boldsymbol\mu_i)^T\boldsymbol{\Sigma}_i^{-1}\right]\\
\end{aligned} ∂ Σ i ∂ ( p ( x j ∣ μ i , Σ i ) ) = p ( x j ∣ μ i , Σ i ) ⋅ [ − 2 1 Σ i − 1 + 2 1 Σ i − 1 ( x j − μ i ) ( x j − μ i ) T Σ i − 1 ] 将此式代回∂ L L ( D ) ∂ Σ i \cfrac {\partial LL(D)}{\partial\boldsymbol\Sigma_{i}} ∂ Σ i ∂ LL ( D )
∂ L L ( D ) ∂ Σ i = ∑ j = 1 m α i ⋅ p ( x j ∣ μ i , Σ i ) ∑ l = 1 k α l ⋅ p ( x j ∣ μ l , Σ l ) ⋅ [ − 1 2 Σ i − 1 + 1 2 Σ i − 1 ( x j − μ i ) ( x j − μ i ) T Σ i − 1 ] \cfrac {\partial LL(D)}{\partial\boldsymbol\Sigma_{i}}=\sum_{j=1}^m\cfrac{\alpha_{i}\cdot p(\boldsymbol x_{j}|\boldsymbol\mu_{i},\boldsymbol\Sigma_{i})}{\sum_{l=1}^k\alpha_{l}\cdot p(\boldsymbol x_{j}|\boldsymbol\mu_{l},\boldsymbol\Sigma_{l})}\cdot\left[-\cfrac{1}{2}\boldsymbol{\Sigma}_i^{-1}+\cfrac{1}{2}\boldsymbol{\Sigma}_i^{-1}(\boldsymbol x_j-\boldsymbol\mu_i)(\boldsymbol x_j-\boldsymbol\mu_i)^T\boldsymbol{\Sigma}_i^{-1}\right] ∂ Σ i ∂ LL ( D ) = j = 1 ∑ m ∑ l = 1 k α l ⋅ p ( x j ∣ μ l , Σ l ) α i ⋅ p ( x j ∣ μ i , Σ i ) ⋅ [ − 2 1 Σ i − 1 + 2 1 Σ i − 1 ( x j − μ i ) ( x j − μ i ) T Σ i − 1 ] 又由公式(9.30)可知α i ⋅ p ( x j ∣ μ i , Σ i ) ∑ l = 1 k α l ⋅ p ( x j ∣ μ l , Σ l ) = γ j i \cfrac{\alpha_{i}\cdot p(\boldsymbol x_{j}|\boldsymbol\mu_{i},\boldsymbol\Sigma_{i})}{\sum_{l=1}^k\alpha_{l}\cdot p(\boldsymbol x_{j}|\boldsymbol\mu_{l},\boldsymbol\Sigma_{l})}=\gamma_{ji} ∑ l = 1 k α l ⋅ p ( x j ∣ μ l , Σ l ) α i ⋅ p ( x j ∣ μ i , Σ i ) = γ j i
∂ L L ( D ) ∂ Σ i = ∑ j = 1 m γ j i ⋅ [ − 1 2 Σ i − 1 + 1 2 Σ i − 1 ( x j − μ i ) ( x j − μ i ) T Σ i − 1 ] \cfrac {\partial LL(D)}{\partial\boldsymbol\Sigma_{i}}=\sum_{j=1}^m\gamma_{ji}\cdot\left[-\cfrac{1}{2}\boldsymbol{\Sigma}_i^{-1}+\cfrac{1}{2}\boldsymbol{\Sigma}_i^{-1}(\boldsymbol x_j-\boldsymbol\mu_i)(\boldsymbol x_j-\boldsymbol\mu_i)^T\boldsymbol{\Sigma}_i^{-1}\right] ∂ Σ i ∂ LL ( D ) = j = 1 ∑ m γ j i ⋅ [ − 2 1 Σ i − 1 + 2 1 Σ i − 1 ( x j − μ i ) ( x j − μ i ) T Σ i − 1 ] 令上式等于0可得
∂ L L ( D ) ∂ Σ i = ∑ j = 1 m γ j i ⋅ [ − 1 2 Σ i − 1 + 1 2 Σ i − 1 ( x j − μ i ) ( x j − μ i ) T Σ i − 1 ] = 0 \cfrac {\partial LL(D)}{\partial\boldsymbol\Sigma_{i}}=\sum_{j=1}^m\gamma_{ji}\cdot\left[-\cfrac{1}{2}\boldsymbol{\Sigma}_i^{-1}+\cfrac{1}{2}\boldsymbol{\Sigma}_i^{-1}(\boldsymbol x_j-\boldsymbol\mu_i)(\boldsymbol x_j-\boldsymbol\mu_i)^T\boldsymbol{\Sigma}_i^{-1}\right]=0 ∂ Σ i ∂ LL ( D ) = j = 1 ∑ m γ j i ⋅ [ − 2 1 Σ i − 1 + 2 1 Σ i − 1 ( x j − μ i ) ( x j − μ i ) T Σ i − 1 ] = 0 移项推导有：
∑ j = 1 m γ j i ⋅ [ − I + ( x j − μ i ) ( x j − μ i ) T Σ i − 1 ] = 0 ∑ j = 1 m γ j i ( x j − μ i ) ( x j − μ i ) T Σ i − 1 = ∑ j = 1 m γ j i I ∑ j = 1 m γ j i ( x j − μ i ) ( x j − μ i ) T = ∑ j = 1 m γ j i Σ i Σ i − 1 ⋅ ∑ j = 1 m γ j i ( x j − μ i ) ( x j − μ i ) T = ∑ j = 1 m γ j i Σ i = ∑ j = 1 m γ j i ( x j − μ i ) ( x j − μ i ) T ∑ j = 1 m γ j i \begin{aligned}
\sum_{j=1}^m\gamma_{ji}\cdot\left[-\boldsymbol{I}+(\boldsymbol x_j-\boldsymbol\mu_i)(\boldsymbol x_j-\boldsymbol\mu_i)^T\boldsymbol{\Sigma}_i^{-1}\right]&=0\\
\sum_{j=1}^m\gamma_{ji}(\boldsymbol x_j-\boldsymbol\mu_i)(\boldsymbol x_j-\boldsymbol\mu_i)^T\boldsymbol{\Sigma}_i^{-1}&=\sum_{j=1}^m\gamma_{ji}\boldsymbol{I}\\
\sum_{j=1}^m\gamma_{ji}(\boldsymbol x_j-\boldsymbol\mu_i)(\boldsymbol x_j-\boldsymbol\mu_i)^T&=\sum_{j=1}^m\gamma_{ji}\boldsymbol{\Sigma}_i\\
\boldsymbol{\Sigma}_i^{-1}\cdot\sum_{j=1}^m\gamma_{ji}(\boldsymbol x_j-\boldsymbol\mu_i)(\boldsymbol x_j-\boldsymbol\mu_i)^T&=\sum_{j=1}^m\gamma_{ji}\\
\boldsymbol{\Sigma}_i&=\cfrac{\sum_{j=1}^m\gamma_{ji}(\boldsymbol x_j-\boldsymbol\mu_i)(\boldsymbol x_j-\boldsymbol\mu_i)^T}{\sum_{j=1}^m\gamma_{ji}}
\end{aligned} j = 1 ∑ m γ j i ⋅ [ − I + ( x j − μ i ) ( x j − μ i ) T Σ i − 1 ] j = 1 ∑ m γ j i ( x j − μ i ) ( x j − μ i ) T Σ i − 1 j = 1 ∑ m γ j i ( x j − μ i ) ( x j − μ i ) T Σ i − 1 ⋅ j = 1 ∑ m γ j i ( x j − μ i ) ( x j − μ i ) T Σ i = 0 = j = 1 ∑ m γ j i I = j = 1 ∑ m γ j i Σ i = j = 1 ∑ m γ j i = ∑ j = 1 m γ j i ∑ j = 1 m γ j i ( x j − μ i ) ( x j − μ i ) T 此即为公式(9.35)。
9.4.9 式(9.36)的解释
该式即L L ( D ) LL(D) LL ( D ) ∑ i = 1 k α i = 1 \sum_{i=1}^k{\alpha_i=1} ∑ i = 1 k α i = 1
9.4.10 式(9.37)的推导
重写式(9.32)如下:
L L ( D ) = ∑ j = 1 m ln ( ∑ l = 1 k α l ⋅ p ( x j ∣ μ l , Σ l ) ) L L(D)=\sum_{j=1}^m \ln \left(\sum_{l=1}^k \alpha_l \cdot p\left(\boldsymbol{x}_j \mid \boldsymbol{\mu}_l, \boldsymbol{\Sigma}_l\right)\right) LL ( D ) = j = 1 ∑ m ln ( l = 1 ∑ k α l ⋅ p ( x j ∣ μ l , Σ l ) ) 这里将第 2 个求和号的求和变量由式(9.32)的 i i i l l l α i \alpha_i α i i i i α i \alpha_i α i
∂ L L ( D ) ∂ α i = ∂ ∑ j = 1 m ln ( ∑ l = 1 k α l ⋅ p ( x j ∣ μ l , Σ l ) ) ∂ α i = ∑ j = 1 m 1 ∑ l = 1 k α l ⋅ p ( x j ∣ μ l , Σ l ) ⋅ ∂ ∑ l = 1 k α l ⋅ p ( x j ∣ μ l , Σ l ) ∂ α i = ∑ j = 1 m 1 ∑ l = 1 k α l ⋅ p ( x j ∣ μ l , Σ l ) ⋅ p ( x j ∣ μ i , Σ i ) \begin{aligned}
\frac{\partial L L(D)}{\partial \alpha_i} & =\frac{\partial \sum_{j=1}^m \ln \left(\sum_{l=1}^k \alpha_l \cdot p\left(\boldsymbol{x}_j \mid \boldsymbol{\mu}_l, \boldsymbol{\Sigma}_l\right)\right)}{\partial \alpha_i} \\
& =\sum_{j=1}^m \frac{1}{\sum_{l=1}^k \alpha_l \cdot p\left(\boldsymbol{x}_j \mid \boldsymbol{\mu}_l, \boldsymbol{\Sigma}_l\right)} \cdot \frac{\partial \sum_{l=1}^k \alpha_l \cdot p\left(\boldsymbol{x}_j \mid \boldsymbol{\mu}_l, \boldsymbol{\Sigma}_l\right)}{\partial \alpha_i} \\
& =\sum_{j=1}^m \frac{1}{\sum_{l=1}^k \alpha_l \cdot p\left(\boldsymbol{x}_j \mid \boldsymbol{\mu}_l, \boldsymbol{\Sigma}_l\right)} \cdot p\left(\boldsymbol{x}_j \mid \boldsymbol{\mu}_i, \boldsymbol{\Sigma}_i\right)
\end{aligned} ∂ α i ∂ LL ( D ) = ∂ α i ∂ ∑ j = 1 m ln ( ∑ l = 1 k α l ⋅ p ( x j ∣ μ l , Σ l ) ) = j = 1 ∑ m ∑ l = 1 k α l ⋅ p ( x j ∣ μ l , Σ l ) 1 ⋅ ∂ α i ∂ ∑ l = 1 k α l ⋅ p ( x j ∣ μ l , Σ l ) = j = 1 ∑ m ∑ l = 1 k α l ⋅ p ( x j ∣ μ l , Σ l ) 1 ⋅ p ( x j ∣ μ i , Σ i ) ∂ ( ∑ l = 1 k α l − 1 ) ∂ α i = ∂ ( α 1 + α 2 + … + α i + … + α k − 1 ) ∂ α i = 1 \frac{\partial\left(\sum_{l=1}^k \alpha_l-1\right)}{\partial \alpha_i}=\frac{\partial\left(\alpha_1+\alpha_2+\ldots+\alpha_i+\ldots+\alpha_k-1\right)}{\partial \alpha_i}=1 ∂ α i ∂ ( ∑ l = 1 k α l − 1 ) = ∂ α i ∂ ( α 1 + α 2 + … + α i + … + α k − 1 ) = 1 综合两项求导结果, 并令导数等于零即得式(9.37)。
9.4.11 式(9.38)的推导
注意, 在"西瓜书"第 14 次印刷中式(9.38)上方的一行话进行了勘误:
"两边同乘以 α i \alpha_i α i λ = − m \lambda=-m λ = − m
对公式(9.37)两边同时乘以α i \alpha_{i} α i
∑ j = 1 m α i ⋅ p ( x j ∣ μ i , Σ i ) ∑ l = 1 k α l ⋅ p ( x j ∣ μ l , Σ l ) + λ α i = 0 ∑ j = 1 m α i ⋅ p ( x j ∣ μ i , Σ i ) ∑ l = 1 k α l ⋅ p ( x j ∣ μ l , Σ l ) = − λ α i \begin{aligned}
\sum_{j=1}^m\frac{\alpha_{i}\cdot p(\boldsymbol x_{j}|\boldsymbol\mu_{i},\boldsymbol\Sigma_{i})}{\sum_{l=1}^k\alpha_{l}\cdot p(\boldsymbol x_{j}|\boldsymbol\mu_{l},\boldsymbol\Sigma_{l})}+\lambda\alpha_{i}=0\\
\sum_{j=1}^m\frac{\alpha_{i}\cdot p(\boldsymbol x_{j}|\boldsymbol\mu_{i},\boldsymbol\Sigma_{i})}{\sum_{l=1}^k\alpha_{l}\cdot p(\boldsymbol x_{j}|\boldsymbol\mu_{l},\boldsymbol\Sigma_{l})}=-\lambda\alpha_{i}
\end{aligned} j = 1 ∑ m ∑ l = 1 k α l ⋅ p ( x j ∣ μ l , Σ l ) α i ⋅ p ( x j ∣ μ i , Σ i ) + λ α i = 0 j = 1 ∑ m ∑ l = 1 k α l ⋅ p ( x j ∣ μ l , Σ l ) α i ⋅ p ( x j ∣ μ i , Σ i ) = − λ α i 两边对所有混合成分求和可得
∑ i = 1 k ∑ j = 1 m α i ⋅ p ( x j ∣ μ i , Σ i ) ∑ l = 1 k α l ⋅ p ( x j ∣ μ l , Σ l ) = − λ ∑ i = 1 k α i ∑ j = 1 m ∑ i = 1 k α i ⋅ p ( x j ∣ μ i , Σ i ) ∑ l = 1 k α l ⋅ p ( x j ∣ μ l , Σ l ) = − λ ∑ i = 1 k α i \begin{aligned}\sum_{i=1}^k\sum_{j=1}^m\frac{\alpha_{i}\cdot p(\boldsymbol x_{j}|\boldsymbol\mu_{i},\boldsymbol\Sigma_{i})}{\sum_{l=1}^k\alpha_{l}\cdot p(\boldsymbol x_{j}|\boldsymbol\mu_{l},\boldsymbol\Sigma_{l})}&=-\lambda\sum_{i=1}^k\alpha_{i}\\
\sum_{j=1}^m\sum_{i=1}^k\frac{\alpha_{i}\cdot p(\boldsymbol x_{j}|\boldsymbol\mu_{i},\boldsymbol\Sigma_{i})}{\sum_{l=1}^k\alpha_{l}\cdot p(\boldsymbol x_{j}|\boldsymbol\mu_{l},\boldsymbol\Sigma_{l})}&=-\lambda\sum_{i=1}^k\alpha_{i}
\end{aligned} i = 1 ∑ k j = 1 ∑ m ∑ l = 1 k α l ⋅ p ( x j ∣ μ l , Σ l ) α i ⋅ p ( x j ∣ μ i , Σ i ) j = 1 ∑ m i = 1 ∑ k ∑ l = 1 k α l ⋅ p ( x j ∣ μ l , Σ l ) α i ⋅ p ( x j ∣ μ i , Σ i ) = − λ i = 1 ∑ k α i = − λ i = 1 ∑ k α i 因为
∑ i = 1 k α i ⋅ p ( x j ∣ μ i , Σ i ) ∑ l = 1 k α l ⋅ p ( x j ∣ μ l , Σ l ) = ∑ i = 1 k α i ⋅ p ( x j ∣ μ i , Σ i ) ∑ l = 1 k α l ⋅ p ( x j ∣ μ l , Σ l ) = 1 \sum_{i=1}^k\frac{\alpha_{i}\cdot p(\boldsymbol x_{j}|\boldsymbol\mu_{i},\mathbf\Sigma_{i})}{\sum_{l=1}^k\alpha_{l}\cdot p(\boldsymbol x_{j}|\boldsymbol\mu_{l},\mathbf\Sigma_{l})}=\frac{\sum_{i=1}^k\alpha_{i}\cdot p(\boldsymbol x_{j}|\boldsymbol\mu_{i},\mathbf\Sigma_{i})}{\sum_{l=1}^k\alpha_{l}\cdot p(\boldsymbol x_{j}|\boldsymbol\mu_{l},\mathbf\Sigma_{l})}=1 i = 1 ∑ k ∑ l = 1 k α l ⋅ p ( x j ∣ μ l , Σ l ) α i ⋅ p ( x j ∣ μ i , Σ i ) = ∑ l = 1 k α l ⋅ p ( x j ∣ μ l , Σ l ) ∑ i = 1 k α i ⋅ p ( x j ∣ μ i , Σ i ) = 1 且 ∑ i = 1 k α i = 1 \sum_{i=1}^k\alpha_{i}=1 ∑ i = 1 k α i = 1 m = − λ m=-\lambda m = − λ
∑ j = 1 m α i ⋅ p ( x j ∣ μ i , Σ i ) ∑ l = 1 k α l ⋅ p ( x j ∣ μ l , Σ l ) = − λ α i = m α i \sum_{j=1}^m\frac{\alpha_{i}\cdot p(\boldsymbol x_{j}|\boldsymbol\mu_{i},\boldsymbol\Sigma_{i})}{\sum_{l=1}^k\alpha_{l}\cdot p(\boldsymbol x_{j}|\boldsymbol\mu_{l},\boldsymbol\Sigma_{l})}=-\lambda\alpha_{i}=m\alpha_{i} j = 1 ∑ m ∑ l = 1 k α l ⋅ p ( x j ∣ μ l , Σ l ) α i ⋅ p ( x j ∣ μ i , Σ i ) = − λ α i = m α i 因此
α i = 1 m ∑ j = 1 m α i ⋅ p ( x j ∣ μ i , Σ i ) ∑ l = 1 k α l ⋅ p ( x j ∣ μ l , Σ l ) \alpha_{i}=\cfrac{1}{m}\sum_{j=1}^m\frac{\alpha_{i}\cdot p(\boldsymbol x_{j}|\boldsymbol\mu_{i},\boldsymbol\Sigma_{i})}{\sum_{l=1}^k\alpha_{l}\cdot p(\boldsymbol x_{j}|\boldsymbol\mu_{l},\boldsymbol\Sigma_{l})} α i = m 1 j = 1 ∑ m ∑ l = 1 k α l ⋅ p ( x j ∣ μ l , Σ l ) α i ⋅ p ( x j ∣ μ i , Σ i ) 又由公式(9.30)可知α i ⋅ p ( x j ∣ μ i , Σ i ) ∑ l = 1 k α l ⋅ p ( x j ∣ μ l , Σ l ) = γ j i \cfrac{\alpha_{i}\cdot p(\boldsymbol x_{j}|\boldsymbol\mu_{i},\boldsymbol\Sigma_{i})}{\sum_{l=1}^k\alpha_{l}\cdot p(\boldsymbol x_{j}|\boldsymbol\mu_{l},\boldsymbol\Sigma_{l})}=\gamma_{ji} ∑ l = 1 k α l ⋅ p ( x j ∣ μ l , Σ l ) α i ⋅ p ( x j ∣ μ i , Σ i ) = γ j i
α i = 1 m ∑ j = 1 m γ j i \alpha_{i}=\cfrac{1}{m}\sum_{j=1}^m\gamma_{ji} α i = m 1 j = 1 ∑ m γ j i 此即为公式(9.38)。
9.4.12 图9.6的解释
第 1 行初始化参数, 本页接下来的例子是按如下策略初始化的: 混合系数
α i = 1 k \alpha_i=\frac{1}{k} α i = k 1 k k k k k k μ i ( 1 ⩽ i ⩽ k ) \boldsymbol{\mu}_i(1 \leqslant i \leqslant k) μ i ( 1 ⩽ i ⩽ k ) 0.1 0.1 0.1 k k k Σ i ( 1 ⩽ i ⩽ k ) \boldsymbol{\Sigma}_i(1 \leqslant i \leqslant k) Σ i ( 1 ⩽ i ⩽ k )
第 3~5 行根据式(9.30)计算共 m × k m \times k m × k γ j i \gamma_{j i} γ j i
第 6~10 行分别根据式(9.34)、式(9.35)、式(9.38)使用刚刚计算得到的
γ j i \gamma_{j i} γ j i Σ i ′ \boldsymbol{\Sigma}_i^{\prime} Σ i ′ μ i ′ \mu_i^{\prime} μ i ′ μ i \boldsymbol{\mu}_i μ i μ i ′ \mu_i^{\prime} μ i ′ γ j i \gamma_{j i} γ j i
整体来说, 第 2 ~12 行就是一个 EM 算法的具体使用例子, 学习完 7.6 7.6 7.6 γ j i \gamma_{j i} γ j i ( α i , μ i , Σ i ) \left(\alpha_i, \boldsymbol{\mu}_i, \boldsymbol{\Sigma}_i\right) ( α i , μ i , Σ i ) E M \mathrm{EM} EM ( α i , μ i , Σ i ) \left(\alpha_i, \boldsymbol{\mu}_i, \boldsymbol{\Sigma}_i\right) ( α i , μ i , Σ i ) γ j i \gamma_{j i} γ j i γ j i \gamma_{j i} γ j i ( α i , μ i , Σ i ) \left(\alpha_i, \boldsymbol{\mu}_i, \boldsymbol{\Sigma}_i\right) ( α i , μ i , Σ i )
9.5 密度聚类
本节介绍的DBSCAN算法并不难懂，只是本节在最后举例时并没有说清楚密度聚类算法与前面原型聚类算法的区别，当然这也可能是作者有意为之，因为在"西瓜书"本章习题9.7题就提到了"凸聚类"的概念。具体来说，前面介绍的聚类算法只能产生"凸聚类"，而本节介绍的DBSCAN则能产生"非凸聚类"，其本质原因，个人感觉在于聚类时使用的距离度量，均值算法使用欧氏距离，而DBSCAN使用类似于测地线距离（只是类似，并不相同，测地线距离参见"西瓜书"10.5节），因此可以产生如图9-1所示的聚类结果（中间为典型的非凸聚类）。
注意，虽然左图为 "凸聚类"（四个簇都有一个凸包），但
均值算法却无法产生此结果，因为最大的簇太大了，其外围样本与另三个小簇的中心之间的距离更近，因此中间最大的簇肯定会被
均值算法划分到不同的簇之中，这显然不是我们希望的结果。
密度聚类算法可以产生任意形状的簇，不需要事先指定聚类个数k，并且对噪声鲁棒。
9.5.1 密度直达、密度可达与密度相连
x j \boldsymbol{x}_j x j x i \boldsymbol{x}_i x i x j \boldsymbol{x}_j x j x i \boldsymbol{x}_i x i ϵ − \epsilon- ϵ − x i \boldsymbol{x}_i x i ϵ \epsilon ϵ x j \boldsymbol{x}_j x j
x j \boldsymbol{x}_j x j x i \boldsymbol{x}_i x i p 1 , p 2 , … , p n \boldsymbol{p}_1, \boldsymbol{p}_2, \ldots, \boldsymbol{p}_n p 1 , p 2 , … , p n p n = x j \boldsymbol{p}_n=\boldsymbol{x}_j p n = x j p 1 = x i \boldsymbol{p}_1=\boldsymbol{x}_i p 1 = x i
以上两个概念中, 若 x j \boldsymbol{x}_j x j x j \boldsymbol{x}_j x j x i \boldsymbol{x}_i x i x i \boldsymbol{x}_i x i x j \boldsymbol{x}_j x j
x i \boldsymbol{x}_i x i x j \boldsymbol{x}_j x j x i \boldsymbol{x}_i x i x j \boldsymbol{x}_j x j
9.5.2 图9.9的解释
在第 1 ∼ 7 1\sim 7 1 ∼ 7 ( ϵ , M i n P t s ) (\epsilon, M i n P t s) ( ϵ , M in P t s ) Ω \Omega Ω x j \boldsymbol{x}_j x j
在第 10 ∼ 24 10\sim 24 10 ∼ 24 14 ∼ 21 14\sim 21 14 ∼ 21
其中第 14 ∼ 21 14\sim 21 14 ∼ 21 Q Q Q Q Q Q q \boldsymbol{q} q q \boldsymbol{q} q q \boldsymbol{q} q ϵ \epsilon ϵ q \boldsymbol{q} q q \boldsymbol{q} q ϵ \epsilon ϵ ϵ \epsilon ϵ
第 14 ∼ 21 14\sim 21 14 ∼ 21 Γ o l d = Γ \Gamma_{\mathrm{old}}=\Gamma Γ old = Γ Γ old \Gamma_{\text {old }} Γ old Γ \Gamma Γ 1 ∼ 7 1 \sim 7 1 ∼ 7 Ω \Omega Ω
符号 " \ \backslash \ A = { a , b , c , d , e , f } , B = { a , d , f , g , h } A=\{a, b, c, d, e, f\}, B=\{a, d, f, g, h\} A = { a , b , c , d , e , f } , B = { a , d , f , g , h } A \ B A \backslash B A \ B A \ B = { b , c , e } A \backslash B=\{b, c, e\} A \ B = { b , c , e } A , B A, B A , B A A A
9.6 层次聚类
本节主要介绍了层次聚类的代表算法 AGNES。
式(9.41) (9.43)介绍了三种距离计算方式,
这与"西瓜书"9.3节中介绍的距离不同之处在于, 此 三种距离计算面向集合之间,
而9.3节的距离则面向两点之间。正如"西瓜书"第 215 页左上边注所示,
集合间的距离计算常采用豪斯多夫距离(Hausdorff distance)。
算法 AGNES 很简单,
就是不断重复执行合并距离最近的两个聚类簇。"西瓜书"图9.11为具体实 现方法,
核心就是在合并两个聚类簇后更新距离矩阵（第 11 ∼ 23 11\sim 23 11 ∼ 23
在第 1 ∼ 9 1\sim 9 1 ∼ 9 i i i C i C_i C i i i i C i C_i C i
第 18 ∼ 21 18\sim 21 18 ∼ 21 M M M i ∗ i^* i ∗ i ∗ i^* i ∗ C i ∗ C_{i^*} C i ∗ C j ∗ C_{j^*} C j ∗
