《机器学习》周志华-CH9（聚类）

9.1聚类任务

  聚类试图将数据集中的样本划分为若干个通常是不相交的子集，每个子集称为"簇"。

  假定样本集$D=x_1,x_2,...x_m$包含$m$个无标记样本

  每个样本$x_i=(x_{i1},x_{i2},...x_{in})$是一个$n$维向量

  聚类将样本集$D$划分维$k$个不相交的簇 { C l ∣ l = 1 , 2 , . . k } \{C_l|l=1,2,..k\} {Cl​∣l=1,2,..k}

9.2性能度量

  亦称聚类“有效性指标”（validity index）

  聚类结果与“簇内相似度”高且“簇间相似度”低
$$性能度量大致两类\{\begin{array}{ll}与“参考模型”比，“外部指标”& \\ 直接考虑结果，“内部指标”& \end{array}$$

  对数据集 D = { x 1 , x 2 , . . . x m } D=\{x_1,x_2,...x_m\} D={x1​,x2​,...xm​}

  聚类给出的簇划分 C = { C 1 , C 2 , . . . , C k } C=\{C_1,C_2,...,C_k\} C={C1​,C2​,...,Ck​}

  参考模型给的簇划分 C ∗ = { C 1 ∗ , C 2 ∗ , . . . , C k ∗ } C^*=\{C_1^*,C_2^*,...,C_k^*\} C∗={C1∗​,C2∗​,...,Ck∗​}

  同时令$\lambda$与${\lambda }^{\ast }$分布表示$C$与$C^{\ast }$对应的簇标记向量

  其中，$a+b+c+d=C_m^2=\frac{m(m-1)}{2}$

  聚类性能度量外部指标：

9.3距离计算

  对函数$dist(\cdot ,\cdot )$,若它是一个“距离度量”（distance measure），则需满足一些基本性质：

• 非负性：$dist(x_i,x_j)\ge 0;$
• 同一性：$dist(x_i,x_j)=0;$当且仅当$x_i=x_j;$
• 对称性：$dist(x_i,x_j)=dist(x_j,x_i);$
• 直递性：$dist(x_i,x_j)\le dist(x_i,x_k)+dist(x_k,x_j)$

  给定样本$x_i=(x_{i1};x_{i2};...;x_{in})$与$x_j=(x_{j1};x_{j2};...;x_{jn})$,最常用的是“闵可夫斯基距离”（Minkoski distance）
$$\begin{array}{c}dis{t}_{mk}(x_i,x_j)=(\sum _{u=1}^n|x_{iu}-x_{ju}{|}^p{)}^{\frac{1}{p}}\end{array}\text{\hspace{1em}(9.18)}$$
  对$p\ge 1$,式（9.18）满足上面所有基本性质

  $p=2$时，“闵可夫斯基距离”是欧氏距离（Euclidean distance）
$$\begin{array}{c}dis{t}_{ed}(x_i,x_j)=||x_i-x_j|{|}_2=\sqrt{\sum _{u=1}^n|x_{iu}-x_{ju}{|}^2}\end{array}\text{\hspace{1em}(9.19)}$$

  $p=1$时,“闵可夫斯基距离”是曼哈顿距离
$$\begin{array}{c}dis{t}_{man}(x_i,x_j)=||x_i-x_j|{|}_1=\sum _{u=1}^n|x_{iu}-x_{ju}|\end{array}\text{\hspace{1em}(9.20)}$$
$$属性划分\{\begin{array}{ll}“连续属性”& \\ “离散属性”& \end{array}$$
$$属性划分\{\begin{array}{llc}“有序属性”& 1，2，3& 闵可夫斯基距离可用\\ “无序属性”& 飞机，火车，轮胎& 闵可夫斯基距离不可用\end{array}$$
  对无需属性采用VDM

  令$m_{u,a}$表示属性$u$上取值为$a$的样本数

  $m_{u,a,i}$表示第$i$个样本簇中在属性$u$上取值为$a$的样本数。

  属性$u$上两个离散值$a$与$b$之间的VDM距离为：
$$\begin{array}{c}VD{M}_p(a,b)=\sum _{i=1}^k|\frac{m_{u,a,i}}{m_{u,a}}-\frac{m_{u,b,i}}{m_{u,b}}|\end{array}\text{\hspace{1em}(9.21)}$$
  将闵可夫斯基距离和VDM结合即可处理混合属性

  $n_c$个有序属性，$n-n_c$个无序属性，则：
$$\begin{array}{c}MinkovD{M}_p(x_i,x_j)=(\sum _{u=1}^{n_c}|x_{i,u}-x_{j,u}{|}^p+\sum _{u=n_c+1}^{n}VD{M}_p(x_{iu},x_{j}u){)}^{\frac{1}{p}}\end{array}\text{\hspace{1em}(9.22)}$$
  样本权重不同，“加权距离”

  加权闵可夫斯基距离：
$$\begin{array}{c}dis{t}_{wmk}(x_i,x_j)=(w_i\cdot |x_{i1}-x_{j1}{|}^p+...+w_n\cdot |x_{in}-x_{jn}{|}^p{)}^{\frac{1}{p}}\end{array}\text{\hspace{1em}(9.23)}$$
  其中，权重$w_i\ge 0(i=1,2,...,n)$表征不同属性的重要性，通常${\sum }_{i=1}^n{w}_i=1$

9.4原型聚类

  ”基于原型的聚类“，通过一组原型刻画。

9.4.1 k均值算法

  样本集 D = { x 1 , x 2 , . . . x m } D=\{x_1,x_2,...x_m\} D={x1​,x2​,...xm​}，k-means算法针对聚类所得簇划分 C = { C 1 , C 2 , . . . C k } C=\{C_1,C_2,...C_k\} C={C1​,C2​,...Ck​}最小化平方误差
$$\begin{array}{c}E=\sum _{i=1}^k\sum _{x\in C_i}||x-u_i|{|}_2^2\end{array}\text{\hspace{1em}(9.24)}$$
  其中$E$越小，内部相似度越高，$u_i=\frac{1}{|C_i|}{\sum }_{x\in C_i}x$是簇$C_i$的均值向量

  这是一个NP问题，采用贪心策略，通过迭代优化近似求解

  算法

1. 加入簇数$k=3$,随机选$3$个样本做为中心$u_1,u_2,u_3$
2. 对每一个样本，考虑与$u_1,u_2,u_3$距离分出
   $C_1=x_5,x_6,...$
   $C_2=x_1,x_{1}1,...$
   $C_1=x_{1}8,x_{1}9,...$
3. 对$C_1,C_2,C_3$分别求新的均值向量$u_1^1,u_2^2,u_3^3$,不断重复迭代，得到最终划分

9.4.2学习向量化(Learning Vector Quantization,LVQ)

  假设样本有类别标记，学习过程利用样本的监督信息来辅助聚类

  给定样本集$D=\{(x_1,y_1),(x_2,y_2),...(x_m,y_m)\}$

  LVQ关键在于如何更新原型向量

  对样本$x_j$,若最近的原型向量$P_{i^{\ast }}$与$x_j$类别标记相同，则令$P_{i^{\ast }}$向$x_j$的方向靠拢，此时新原型向量为

  类似的，若$P_{i^{\ast }}$与$x_j$的类别标记不同，则更新后的原型向量与$x_j$之间的距离增大为$(1+\eta )\cdot ||P_{i^{\ast }}-x_j|{|}_2$,从而更远离$x_j$

  学得一组原型向量 { P 1 , P 2 , . . . P q } \{P_1,P_2,...P_q\} {P1​,P2​,...Pq​}后，可实现对样本空间$\chi$的簇划分。任意样本$\chi$,划入最近簇中；

  每个$P_{i^{\ast }}$定义了与之相关的区域$R_i$。区域中样本与$P_i$距离不大于其他原型向量$P_{i^{,}}$的距离：
R i = { x ∈ χ ∣ ∣ ∣ x − p i ∣ ∣ 2 ≤ ∣ ∣ x − p i , ∣ ∣ 2 , i ′ ≠ i } \begin{equation} R_i=\{x\in\chi| \quad||x-p_i||_2\leq||x-p_{i^,}||_2,i^{'}\neq{i}\} \tag{9.27} \end{equation} Ri​={x∈χ∣∣∣x−pi​∣∣2​≤∣∣x−pi,​∣∣2​,i′=i}​(9.27)​
  形成了对样本空间$\chi$的簇划分 { R 1 , R 2 , . . . R q } \{R_1,R_2,...R_q\} {R1​,R2​,...Rq​}称为”Voronoi剖分“

9.4.3高斯混合聚类

  高斯混合（Mixture-of-Gaussian）聚类采用概率模型来表达聚类原型

  对$n$维样本空间$X$中的随机向量$x$，若$X$服从高斯分布，概率密度函数维：

  样本生成过程：

  根据${\alpha }_1,{\alpha }_2,...{\alpha }_k$定义的先验分布选择高斯混合成分，${\alpha }_i$为第$i$个成分概率

  根据概率密度进行采样，生成相应的样本

  生成训练集 D = { x 1 , x 2 , . . . x m } D=\{x_1,x_2,...x_m\} D={x1​,x2​,...xm​}

  令随机变量 z j ∈ { 1 , 2 , . . k } z_j\in\{1,2,..k\} zj​∈{1,2,..k}表示生成样本$x_j$的高斯混合成分，其取值未知。显然，$z_j$的先验概率$P(z_j=i)$对应${\alpha }_i(i=1,2,...,k)$.根据贝叶斯定理，$z_j$的后验分布对应于

9.5密度聚类

  DBSCAN是基于一组”邻域“参数$(\xi ,MinP{t}_s)$来刻画样本分布的紧密程度。给定数据集 D = { x 1 , x 2 . . . x m } D=\{x_1,x_2...x_m\} D={x1​,x2​...xm​}

• $\xi -$邻域：对$x_j\in D$,其$\xi$邻域包含样本集$D$中与$x_j$的距离不大于$\xi$的样本，即 N ξ ( x j ) = { x i ∈ D ∣ d i s t ( x i , x j ) ≤ ξ } N_{\xi}(x_j)=\{x_i\in{D}|dist(x_i,x_j)\leq\xi\} Nξ​(xj​)={xi​∈D∣dist(xi​,xj​)≤ξ}
• 核心对象（core object） ： 若$x_j$的$\xi$邻域至少包含$MinP{t}_s$个样本，即$|N_{\xi }(x_j)|\ge MinP{t}_s$,则$x_j$是一个核心对象
• 密度直达（directly density-reachable） ：若$x_j$位于$x_i$的$\xi$邻域中，且$x_i$是核心对象。称$x_j$由$x_i$密度直达。
• 密度可达（density-reachable） ：对$x_i$与$x_j$，若存在样本序列$p_1,p_2,...,p_n,$其中$p_1=x_i,p_n=x_j$且$p_{i+1}$由$p_i$密度直达，则称$x_j$由$x_i$密度可达；
• 密度相连（density-connected） ：对$x_i$与$x_j$,若存在$x_k$使得$x_i$与$x_j$均由$x_k$密度可达，则称$x_i$与$x_j$密度相连。

  DBSCAN的簇定义为：给定邻域参数$(\xi ,MinP{t}_s)$,簇$C\subseteq D$是满足以下性质的非空样本子集：

9.6层次聚类

  最小距离：
$$\begin{array}{c}{d}_{min}(C_i,C_j)=\underset{x\in C_i,z\in C_j}{\min }dist(x,z)\end{array}\text{\hspace{1em}(9.41)}$$

  最大距离：
$$\begin{array}{c}{d}_{max}(C_i,C_j)=\underset{x\in C_i,z\in C_j}{\max }dist(x,z)\end{array}\text{\hspace{1em}(9.42)}$$

  平均距离：
$$\begin{array}{c}{d}_{avg}(C_i,C_j)=\frac{1}{|C_i||C_j|}\sum _{x\in C_i}\sum _{x\in C_j}dist(x,z)\end{array}\text{\hspace{1em}(9.43)}$$