《机器学习公式推导与代码实现》学习笔记，记录一下自己的学习过程，详细的内容请大家购买作者的书籍查阅。

聚类分析(cluster analysis)是一类经典的无监督学习算法，在给定样本的情况下，聚类分析通过度量特征相似度或者距离，将样本自动划分为若干类别。

距离度量和相似度度量是聚类分析的核心概念，大多数聚类算法建立在距离度量之上。常用的距离度量方式包括闵氏距离和马氏距离，常用的相似度度量方式包括相关系数和夹角余弦等。

(1) 闵氏距离即闵可夫斯基距离(Minkowski distance)，该距离定义如下，给定m维向量样本集合X，对于xi，xj∈X，xi=(x1i,x2i,...xmi)T，那么样本xi与样本xj的闵氏距离可定义为： d i j = ( ∑ k = 1 m ∣ x k i − x k j ∣ p ) 1 p , p ≥ 1 d_{ij}=\left ( \sum_{k=1}^{m}\left | x_{ki}-x_{kj} \right | ^{p} \right )^{\frac{1}{p} }, p\ge 1 dij​=(k=1∑m​∣xki​−xkj​∣p)p1​,p≥1 可以简单看出，当p=1时，闵氏距离就变成了曼哈顿距离(Manhatan distance)： d i j = ∑ k = 1 m ∣ x k i − x k j ∣ d_{ij}=\sum_{k=1}^{m}\left | x_{ki}-x_{kj} \right | dij​=k=1∑m​∣xki​−xkj​∣ 当p=2时，闵氏距离就变成了欧氏距离(Euclidean distance)： d i j = ( ∑ k = 1 m ∣ x k i − x k j ∣ 2 ) 1 2 d_{ij}=\left ( \sum_{k=1}^{m}\left | x_{ki}-x_{kj} \right | ^{2} \right )^{\frac{1}{2} } dij​=(k=1∑m​∣xki​−xkj​∣2)21​ 当p=∞时，闵氏距离也称切比雪夫距离(Chebyshev distance)： d i j = m a x ∣ x k i − x k j ∣ d_{ij}=max\left | x_{ki}-x_{kj} \right | dij​=max∣xki​−xkj​∣ (2) 马氏距离全称马哈拉诺比斯距离(Mahalanobis distance)，是一种衡量各个特征之间相关性的聚类度量方式。给定一个样本集合X=(xij)mxn，假设样本的协方差矩阵为S，那么样本xi与样本xj之间的马氏距离可以定义为： d i j = [ ( x i − x j ) T S − 1 ( x i − x j ) ] 1 2 d_{ij}=\left [\left(x_{i}-x_{j}\right)^{T} S^{-1}\left(x_{i}-x_{j}\right)\right] ^{\frac{1}{2}} dij​=[(xi​−xj​)TS−1(xi​−xj​)]21​ 当S为单位矩阵，即样本的各特征之间相互独立且方差为1时，马氏距离就是欧氏距离。

(3) 相关系数(correlation coefficent)是度量样本相似度最常用的方式。相关系数有多种定义方式，较为常用的是皮尔逊相关系。相关系数越接近1，两个样本越相似；样本xi与样本xj之间的相关系数可定义为： r i j = ∑ k = 1 m ( x k i − x ˉ i ) ( x k j − x ˉ j ) [ ∑ k = 1 m ( x k i − x ˉ i ) 2 ∑ k = 1 m ( x k j − x ˉ j ) 2 ] 1 2 r_{ij}=\frac{\sum_{k=1}^{m}\left ( x_{ki}-\bar{x}_{i}\right )\left ( x_{kj}-\bar{x}_{j}\right )}{\left [ \sum_{k=1}^{m} \left ( x_{ki}-\bar{x}_{i}\right )^{2} \sum_{k=1}^{m} \left ( x_{kj}-\bar{x}_{j}\right )^{2} \right ] ^{\frac{1}{2} } } rij​=[∑k=1m​(xki​−xˉi​)2∑k=1m​(xkj​−xˉj​)2]21​∑k=1m​(xki​−xˉi​)(xkj​−xˉj​)​ 上边这个式子看起来有点复杂，其实就是： r ( X , Y ) = C o v ( X , Y ) V a r [ X ] V a r [ Y ] r\left ( X,Y \right ) =\frac{Cov\left ( X,Y \right ) }{\sqrt{Var\left [ X \right ] Var\left [ Y \right ] } } r(X,Y)=Var[X]Var[Y] ​Cov(X,Y)​ (4) 余弦夹角(angle cosine)也是度量两个样本相似度的方式。夹角余弦越接近1，表示两个样本越相似: s i m i l a r i t y = c o s ( θ ) = A ⋅ B ∥ A ∥ ∥ B ∥ similarity=cos\left ( \theta \right ) =\frac{A\cdot B}{\left\|A\right\|\left\|B\right\|} similarity=cos(θ)=∥A∥∥B∥A⋅B​ 样本xi与样本xj之间的夹角余弦可定义为： A C i j = ∑ k = 1 m x k i x k j [ ∑ k = 1 m x k i 2 ∑ k = 1 m x k j 2 ] 1 2 AC_{ij}=\frac{\sum_{k=1}^{m}x_{ki}x_{kj}}{\left [ \sum_{k=1}^{m}x_{ki}^{2} \sum_{k=1}^{m}x_{kj}^{2}\right ] ^{\frac{1}{2}}} ACij​=[∑k=1m​xki2​∑k=1m​xkj2​]21​∑k=1m​xki​xkj​​

聚类算法将相似的样本归入同一个簇(cluster)中，这使得同一个簇中的样本对象的相似度尽可能大，同时不同簇中的样本对象的差异性也尽可能大。常用的聚类算法有如下几种：

sklearn在不同数据集上的10类聚类算法效果对比。