1. 聚类任务
无监督学习：训练样本的标记信息是未知的，目标是通过对无标记训练样本的学习来揭示数据的内在性质及规律，为进一步的数据分析提供基础。
无监督学习中，研究最多、应用最广的是聚类
常见的无监督任务有：聚类、密度估计、异常分析
聚类试图将数据集中的样本划分为若干个通常不想交的子集，每个子集称为一个”簇”
注意：聚类任务仅能自动形成簇结构，簇所对应的概念语义需由使用者来把握和命名。
聚类结果使用包含m个元素的簇标记向量$\bf \lambda=(\lambda_1;\lambda_2;…;\lambda_m)$表示，$\lambda_j \in {1,2,\ldots,k}$表示第j个样本的簇标记。
聚类的两个作用：
- 作为一个单独过程，用于找寻数据内在的分布结构
- 作为其他学习任务的前驱过程
下面介绍聚类任务的两个基本问题—性能度量和距离计算
2. 性能度量
聚类性能度量亦称聚类有效性指标，与监督学习中的性能度量作用相似。
性能度量的作用：
- 对聚类结果，使用性能度量来评估其好坏
- 直接将性能度量作为聚类过程的优化目标
聚类结果的”簇内相似度”高且”簇间相似度”低的聚类结果比较好。
聚类性能度量分为两类：
-
外部指标
将聚类结果与某个参考模型进行比较
-
内部指标
直接考察聚类结果不使用任何参考模型
我们使用数学进行建模表示：
数据集$D={\textbf x_1,\textbf x_2,\ldots,\textbf x_m}$
通过聚类给出的簇划分为$\cal C={C_1,C_2,\ldots,C_k}$
参考模型给出的簇划分为$\cal C^\ast={C_1^\ast,C_2^\ast,\ldots,C_s^\ast}$
$\lambda$ 与$\lambda^\ast$分别表示$C$与$\cal C^\ast$对应的簇标记向量
基于此，定义：
\[a=\mid SS\mid,\qquad SS=\{(x_i,x_j)\mid \lambda_i = \lambda_j,\lambda_i^\ast = \lambda_j^\ast,i<j\}\\ b=\mid SD\mid,\qquad SD=\{(x_i,x_j)\mid \lambda_i = \lambda_j,\lambda_i^\ast \not = \lambda_j^\ast,i<j\}\\ c=\mid DS\mid,\qquad DS=\{(x_i,x_j)\mid \lambda_i \not = \lambda_j,\lambda_i^\ast = \lambda_j^\ast,i<j\}\\ d=\mid DD\mid,\qquad DD=\{(x_i,x_j)\mid \lambda_i \not = \lambda_j,\lambda_i^\ast \not = \lambda_j^\ast,i<j\}\tag{2-1}\]在公式2-1中，集合SS包含了在$C$中属于相同簇，在$\cal C^\ast$也属于相同簇的样本对；
集合SD包含了在$C$中属于相同簇，在$\cal C^\ast$不属于相同簇的样本对；
集合DS包含了在$C$中不属于相同簇，在$\cal C^\ast$属于相同簇的样本对；
集合DD包含了在$C$中不属于相同簇，在$\cal C^\ast$也不属于相同簇的样本对。
由于每个样本对仅能出现在一个集合中，因此$a+b+c+d=m(1-m)/2$成立
基于公式2-1，可推导出一下常用的聚类性能度量外部指标：
- Jaccard系数(JC)
\(JC=\frac{a}{b+c+d}\tag{2-2}\)
- FM指数(FMI)
\(FMI=\sqrt{\frac{a}{a+b}\cdot \frac{a}{a+c}}\tag{2-3}\)
- Rand指数(RI)
上述性能度量的结果值均在$[0,1]$之间，且越大越好。
考虑聚类结果的簇划分$\cal C={C_1,C_2,\ldots,C_k}$，定义：
\[avg(C)=\frac{2}{\mid C \mid(\mid C \mid -1)}\sum_{1\leq i<j\leq \mid C \mid}dist(\textbf x_i,\textbf x_j)\\ diam(C)=max_{1\leq i<j\leq \mid C \mid}dist(\textbf x_i,\textbf x_j)\\ d_{min}(C_i,C_j)=min_{\textbf x_i \in C_i,\textbf x_j \in C_j}dist(\textbf x_i,\textbf x_j)\\ d_{cen}(C_i,C_j)=dist(\mu_i,\mu_j)\tag{2-5}\]$dist(\cdot ,\cdot)$用于计算两个样本之间的距离
$avg(C)$对应簇$C$内样本间的平均距离；
$diam(C)$对应簇$C$内样本间的最远距离;
$d_{min}(C_i,C_j)$对应簇$C_i$与$C_j$最近样本间的距离；
$d_{cen}(C_i,C_j)$对应簇$C_i$与$C_j$中心点的距离；
基于公式2-5，推导出常用的聚类性能度量内部指标：
- DB指数(DBI)
\(DBI=\frac{1}{k}\sum_{i=1}^k \underset{j\not=i}{\max}\left(\frac{avg(C_i)+avg(C_j)}{d_{cen}(C_i,C_j)}\right) \tag{2-6}\)
- Dunn指数(DI)
\(DI=\underset {1\leq i \leq k}{\min}\left\{\underset{j\not=i}{\min}\left(\frac{d_{min}(C_i,C_j)}{\max_{1 \leq l \leq k }diam(C_l)}\right)\right\}\tag{2-7}\)
DBI越小越好，DI越大越好
3. 距离计算
对函数$dist(\cdot,\cdot)$，若它是一个距离度量，需满足以下条件：
\[非负性：dist(\textbf x_i,\textbf x_j)\geq 0;\\ 同一性：dist(\textbf x_i,\textbf x_j)= 0\;当且仅当\;\textbf x_i=\textbf x_j;\\ 对称性：dist(\textbf x_i,\textbf x_j)= dist(\textbf x_j,\textbf x_i);\\ 直递性：dist(\textbf x_i,\textbf x_j)\leq dist(\textbf x_i,\textbf x_k)+dist(\textbf x_k,\textbf x_j)\tag{3-1}\]若两个样本$\textbf x_i=(x_{i1};x_{i2};,\cdot,x_{in};)$与$\textbf x_j=(x_{j1};x_{j2};,\cdot,x_{jn};)$，最长用的距离是”闵可夫斯基距离“：
\[dist_{mk}(\textbf x_i,\textbf x_j)=\left(\sum_{\mu=1}^n\mid x_{i\mu}-x_{j\mu}\mid^p\right)^{\frac{1}{p}}\tag{3-2}\]$p\geq 1$
公式3-2实际是$\textbf x_i-\textbf x_j$的$L_p$范数$\mid\mid\textbf x_i-\textbf x_j\mid\mid_p$。
公式3-2满足公式3-1中的所有性质
当$p=2$时，闵可夫斯基距离即为欧氏距离：
\[dist_{ed}(\textbf x_i,\textbf x_j)=\mid\mid\textbf x_i-\textbf x_j\mid\mid_2=\sqrt{\sum_{\mu=1}^n\mid x_{i\mu}-x_{j\mu}\mid^2}\tag{3-3}\]当p=1时，闵可夫斯基距离即为曼哈顿距离：
\[dist_{man}(\textbf x_i,\textbf x_j)=\mid\mid\textbf x_i-\textbf x_j\mid\mid_1=\sum_{\mu=1}^n\mid x_{i\mu}-x_{j\mu}\mid\tag{3-4}\]在讨论距离时，”序”的关系很重要，据此，分为两类
-
有序属性
1与2接近，与3较远
可使用闵可夫斯基距离进行计算
-
无需属性
{飞机，火车，轮船}
可使用VDM距离
令$m_{\mu,a}$表示在$\mu$上取值为$a$的样本数，$m_{\mu,a,i}$表示在第$i$个样本簇中属性$\mu$上取值为$a$的样本数，$k$为样本簇数，则属性$\mu$上两个离散值$a$与$b$之间的VDM距离为：
\[VDM_P(a,b)=\sum_{i=1}^k\mid\frac{m_{\mu,a,i}}{m_{\mu,a}}-\frac{m_{\mu,b,i}}{m_{\mu,b}}\mid^p\tag{3-5}\]将闵可夫斯基距离与VDM距离结合即可处理混合属性。
假设有$n_c$个有序属性，$n-n_c$个无序属性，不失一般性，令有序属性排列在无序属性之前，则：
\[MinkovDM_p(\textbf x_i,\textbf x_j)=\left(\sum_{\mu=1}^{n_c}\mid x_{i\mu}-x_{j\mu}\mid^p+\sum_{\mu=n_c+1}^nVDM_p(x_{i\mu}x_{j\mu})\right)^{\frac{1}{p}}\tag{3-6}\]当样本空间中不同属性的重要性不同时，可使用”加权距离”，以加权闵可夫斯基距离为例：
\[dist_{wmk}(\textbf x_i,\textbf x_j)=(w_1\cdot\mid x_{i1}-x_{j1}\mid^p+\ldots+w_n\cdot\mid x_{in}-x_{jn}\mid^p)^{\frac{1}{p}}\tag{3-7}\]公式3-7中，权重$w_i\geq 0$，表示不同属性的重要性，通常$\sum_{i=1}^n=1$
4. 原型聚类-k均值算法
首先介绍什么是原型聚类
原型是指样本空间中具有代表性的点
原型聚类也称基于原型的聚类，此类算法假设聚类结构能通过一组原型刻画，在现实聚类中极为常用。
一般流程为 先对原型进行初始化，然后对原型进行迭代更新求解。
采用不同的原型表示、不同的求解方式，将产生不同的算法。
下面介绍k均值算法(k-means)：
数据集$D={\textbf x_1,\textbf x_2,\ldots,\textbf x_m}$
通过聚类给出的簇划分为$\cal C={C_1,C_2,\ldots,C_k}$
最小化平方误差：
\[E=\sum_{i=1}^k\sum_{x\in C_i}\mid\mid x-\mu_i \mid\mid_2^2\tag{4-1}\]公式4-1中，$\mu_i=\frac{1}{\mid C_i\mid}\sum_{x\in C_i}x$是簇$C_i$的均值向量。
公式4-1表示了簇内样本围绕簇均值向量的紧密程度，E越小则簇内样本相似度越高。
最小化公式4-1是一个NP难问题，因为找到最优解需考察样本集D所有可能的簇划分。
k均值算法采用贪心策略，通过迭代优化来近似求解。伪代码如下：
我们看一下上面的伪代码，首先随机选择k个样本作为初始均值向量(选择几个样本，最后变有几个簇)，然后循环迭代下面两个过程：
- 计算每一个样本与每个均值向量的距离，根据距离判断簇标记
- 根据划分好的簇，计算新的均值向量
直至均值向量未更新，迭代停止。(通常设置最大迭代论述和最小调整幅度阈值)
K值的选择：
-
手肘法
核心指标为SSE，即公式4-1代表的平方误差。
手肘法的核心思想是：随着聚类数k的增大，样本划分会更加精细，每个簇的聚合程度会逐渐提高，那么误差平方和SSE自然会逐渐变小。并且，当k小于真实聚类数时，由于k的增大会大幅增加每个簇的聚合程度，故SSE的下降幅度会很大，而当k到达真实聚类数时，再增加k所得到的聚合程度回报会迅速变小，所以SSE的下降幅度会骤减，然后随着k值的继续增大而趋于平缓，也就是说SSE和k的关系图是一个手肘的形状，而这个肘部对应的k值就是数据的真实聚类数。当然，这也是该方法被称为手肘法的原因。（转载：https://blog.csdn.net/qq_15738501/article/details/79036255）
-
轮廓系数法
该方法的核心指标是轮廓系数，某个样本点的轮廓系数定义如下： \(S=\frac{b-a}{max\{a,b\}}\tag{4-2}\) 其中，a是$x_i$与同簇的其他样本的平均距离，称为凝聚度，b是$x_i$与最近簇中所有样本的平均距离，称为分离度。最近簇的定义为用$x_i$到某个簇所有样本平均距离作为衡量该点到该簇的距离后，选择离$x_i$最近的一个簇作为最近簇。
求出所有样本的轮廓系数后再求平均值就得到了平均轮廓系数。平均轮廓系数的取值范围为[-1,1]，且簇内样本的距离越近，簇间样本距离越远，平均轮廓系数越大，聚类效果越好。那么，很自然地，平均轮廓系数最大的k便是最佳聚类数。
K个初始点的选择(转载：https://blog.csdn.net/HUSTLX/article/details/51362267)：
- 选择批次距离尽可能远的K个点
首先随机选择一个点作为第一个初始类簇中心点，然后选择距离该点最远的那个点作为第二个初始类簇中心点，然后再选择距离前两个点的最近距离最大的点作为第三个初始类簇的中心点，以此类推，直至选出K个初始类簇中心点。
-
选用层次聚类或者Canopy算法进行初始聚类，然后利用这些类簇的中心点作为KMeans算法初始类簇中心点
常用的层次聚类算法有BIRCH和ROCK，在此不作介绍，下面简单介绍一下Canopy算法，主要摘自Mahout的Wiki： 首先定义两个距离T1和T2，T1>T2.从初始的点的集合S中随机移除一个点P，然后对于还在S中的每个点I，计算该点I与点P的距离，如果距离小于T1，则将点I加入到点P所代表的Canopy中，如果距离小于T2，则将点I从集合S中移除，并将点I加入到点P所代表的Canopy中。迭代完一次之后，重新从集合S中随机选择一个点作为新的点P，然后重复执行以上步骤。 Canopy算法执行完毕后会得到很多Canopy，可以认为每个Canopy都是一个Cluster，与KMeans等硬划分算法不同，Canopy的聚类结果中每个点有可能属于多个Canopy。我们可以选择距离每个Canopy的中心点最近的那个数据点，或者直接选择每个Canopy的中心点作为KMeans的初始K个类簇中心点。
5. 原型聚类-学习向量量化
学习向量量化(LVQ)也是试图找到一组原型向量来刻画聚类结构，但是与k均值不同的是，LVQ假设样本数据带有类别标记，学习过程利用样本的这些监督信息来辅助聚类。
数据集$D={(\textbf x_1,y_1),(\textbf x_2,y_2),\ldots,(\textbf x_m,y_m)}$，每个样本由n个属性进行描述，$y_i\in \cal Y$表示样本$x_i$的类别标记。LVQ的目标是学习一组n维原型向量${\textbf p_1,\textbf p_2,\ldots,\textbf p_q}$。
下面看一下LVQ的算法伪代码：
看一下上面的伪代码，首先对第$q$个簇可从类别为$t_q$的样本中随机选择一个作为原型向量，接下来进行迭代，迭代具体内容为：算法随机选择一个有标记的样本，找出与其最近的原型向量，并根据两者的类别标记是否一致来对原型向量进行相应的更新。直至算法的停止条件满足(达到最大迭代书，原型向量更新很小甚至不再更新)，将最终结果返回。
LVQ算法的关键在于6-10行，即如何更新原型向量。
直观感觉，对样本$x_j$，若最近的原型向量$p_{i^\ast}$与$x_j$的的类别标记相同，则令$p_{i^\ast}$向$x_j$的方向靠拢，公式为：
\[p'=p_{i^\ast}+\eta \cdot (x_j-p_{i^\ast})\tag{5-1}\]$p’$与$x_j$之间的距离为：
\[\begin{align} \mid\mid p'-x_j\mid\mid_2&=\mid\mid p_{i^\ast}+\eta \cdot(x_j-p_{i^\ast})-x_j\mid\mid_2\\ &=(1-\eta)\cdot\mid\mid p_{i^\ast}-x_j\mid\mid_2 \end{align}\tag{5-2}\]设$\eta$为超参数，学习率$\eta \in (0,1)$，则原型向量$p_{i^\ast}$在更新之后更接近$x_j$。
在学习到一组原型向量${\textbf p_1,\textbf p_2,\ldots,\textbf p_q}$之后，即可实现对样本空间的簇划分，对任意样本x，它将被划入与其距离最近的原型向量所代表的簇中；
事实上，每个原型向量$p_i$定义了与之相关的一个区域$R_i$，该区域中每个样本与$p_i$的距离不大于它与其他原型向量$p_{i’}(i’ \not = i)$的距离，即：
\[R_i=\{x\in \cal X \mid \quad \mid\mid x-p_i\mid\mid_2 \leq \mid\mid x-p_{i'}\mid\mid_2,i' \not = i\}\tag{5-3}\]公式5-3中，若将$R_i$中的样本全部用原型向量$p_i$表示，则可实现数据的有损压缩，这称为”向量量化“，LVQ的名字由此而来。
通过公式5-3对样本空间$\cal X$形成的簇划分${R_1,R_2,\ldots, R_q }$，通常称为”Voronoi剖分”。
6. 密度聚类-DBSCAN
密度聚类也称基于密度的聚类，密度聚类假设聚类结构能通过样本分布的紧密程度确定。
大体流程为密度聚类算法从样本密度的角度来考察样本之间的可连续性，并基于可连续性不断扩展聚类簇以获得最终结果。
DBSCAN是一种著名的密度聚类算法，基于一组邻域参数($\epsilon$,MinPts)来刻画样本分布的紧密程度。
数据集$D={\textbf x_1,\textbf x_2,\ldots,\textbf x_m}$
定义以下概念：
-
$\epsilon$-邻域
对$x_j\in D$，其$\epsilon$邻域包含样本集D中与$x_j$的距离不大于$\epsilon$的样本，即$N_{\epsilon}(x_j)={x_i\in D \mid dist(x_i,x_j)\leq \epsilon}$；
-
核心对象
若$x_j$的邻域至少包含$MinPts$个样本，即$\mid N_{\epsilon}(x_j)\mid\geq MinPts$，则$x_j$是一个核心对象
-
密度直达
若$x_j$位于$x_i$的领域中，且$x_i$是核心对象，则称$x_j$由$x_i$直达；
-
密度可达
对$x_i$与$x_j$，若存在样本序列$p_1,p_2,\ldots,p_n$，其中$p_1=x_1,p_n=x_j$且$p_{i+1}$由$p_i$密度直达，则称$x_j$由$x_i$密度可达；
-
密度相连
对$x_i$与$x_j$，若存在$x_k$使得$x_i$与$x_j$均由$x_k$密度可达，则称$x_i$与$x_j$密度相连
在上图中，虚线代表邻域，因此，$x_2$由$x_1$密度直达，$x_3$由$x_1$密度可达，同理$x_4$由$x_1$密度可达，所以$x_3$与$x_4$密度相连
DBSCAN将”簇”定义为由密度可达关系导出的最大密度相连样本集合。
簇的定义为：
\[连接性：x_i \in C,x_j\in C\implies x_i与x_j密度相连\\ 最大性：x_i \in C,x_j由x_i密度可达\implies x_j\in C\tag{6-1}\]找出满足公式6-1的聚类簇的方法为：若$x$为核心对象，由$x$密度可达的所有样本组成的集合记为$X={x’\in D \mid x’由x密度可达}$，$X$即为满足连接性与最大性的簇。
据此，看一下DBSCAN的伪代码：
据上述伪代码所示，DBSCAN算法现根据给定的邻域参数($\epsilon$,MinPts)找出所有的核心对象，然后以任意核心对象出发，找出由其密度可达的样本生出聚类簇，知道所有核心对象均被访问过为止。
7. 层次聚类
层次聚类试图在不同层次对数据集进行划分，从而形成树形的聚类结构。
数据集的划分可采用”自底向上“的聚合策略，也可采用自顶向下的分拆策略。
AGNES是一种采用自底向上聚合策略的层次聚类算法。它先将数据集中的每个样本看作一个初始聚类簇，然后在算法的每一步中找出距离最近的两个聚类簇进行合并，不断重复，直至达到预设的聚类簇个数。
算法的关键是计算聚类簇之间的距离，每个簇实际上是一个样本集合，因此，计算聚类簇之间的聚类可以转换成计算集合的某种距离即可。
给定聚类簇$C_i$与$C_j$，距离计算如下：
\[最小距离：d_{min}(C_i,C_j)=\underset {x \in C_i,z \in C_j}\min dist(x,z)\\ 最大距离：d_{max}(C_i,C_j)=\underset {x \in C_i,z \in C_j}\max dist(x,z)\\ 平均距离：d_{avg}(C_i,C_j)=\frac{1}{\mid C_i\mid\mid C_j\mid}\sum_{x \in C_i}\sum_{z \in C_j} dist(x,z)\tag{7-1}\]根据公式7-1，最小距离由两个簇的最近样本决定，最大距离由两个簇的最远样本决定，平均距离由两个簇的所有样本共同决定。
当使用$d_{min}$、$d_{max}$、$d_{avg}$分别作为聚类簇距离时，AGNES算法相应被称为单链接、全链接、均链接算法。
AGNES算法伪代码为：
如上述伪代码所示，先对仅含一个样本的初始聚类簇和相应的的距离矩阵进行初始化，然后不断合并距离最近的聚类簇，并对合并得到的聚类簇距离矩阵进行更新。不断重复上述过程，直至达到预设的聚类簇的数量。
上述学习笔记主要参考周志华的《机器学习》一书。
