聚类

在”无监督学习”中，训练样本的标记信息是未知的，目标是通过对无标记训练样本的学习来揭示数据的内在性质及规律。

聚类既能作为一个单独过程,用于找寻数据内在的分布结构,也可作为分类等其他学习任务的前驱过程

基于不同的学习策略,人们设计出多种类型的聚类算法。本章后半部分将对不同类型的代表性算法进行介绍,但在此之前我们先讨论聚类算法涉及的两个基本问题——性能度量和距离计算

性能度量

聚类性能度量亦称为聚类”有效性指标”。与监督学习中的性能度量作用相似，对聚类结果，我们需要通过某种性能度量来评估其好坏；另一方面,若明确了最终将要使用的性能度量，则可直接将其作为聚类过程的优化目标,从而更好地得到符合要求的聚类结果.

聚类是将样本集D划分为若干互不相交的子集，即样本簇.那么,什么样的聚类结果比较好啦？直观上，我们希望”物以类聚”,即同一簇的样本尽可能彼此相似，不同簇的样本尽可能不同.换言之,聚类结果的”簇内相似度”高且”簇间相似度”低.

聚类性能度量大致有两类.一类是将聚类结果与某个”参考模型”进行比较，称为”外部指标”;另一类是直接考察聚类结果而不利用任何参考模型,称为”内部指标”.
对数据集$D={x_1,x_2,…,x_m}$,假定通过聚类给出的簇划分为$C={C_1,C_2,..,C_k}$,参考模型给出的簇划分为$C^ ={C_1^ ,C_2^ ,…,C_s^ }$.相应地，令$\lambda$与$\lambda^ $分别表示与C和$C^ $对应的簇标记向量.我们将样本两两配对考虑,定义

$a=|SS|,SS={(x_i,x_j)|\lambda_i=\lambda_j,\lambda_i^* =\lambda_j^* ,i＜j}$ $a=|SD|,SD={(x_i,x_j)|\lambda_i=\lambda_j,\lambda_i^* ≠\lambda_j^* ,i＜j}$ $a=|DS|,DS={(x_i,x_j)|\lambda_i≠\lambda_j,\lambda_i^* =\lambda_j^* ,i＜j}$ $a=|DD|,SS={(x_i,x_j)|\lambda_i≠\lambda_j,\lambda_i^* ≠\lambda_j^* ,i＜j}$

其中集合SS包含了在C中隶属于相同簇且在$C^ $中也隶属于相同簇的样本对,集合SD包含了在C中隶属于相同簇但在$C^ $中隶属于不同簇的样本对,….由于每个样本对$(x_i,x_j)(i＜j)$仅能出现在一个集合中,因此有a+b+c+d=m(m-1)/2成立.

基于上面的a,b,c,d可导出下面常用的聚类性能度量外部指标：

Jaccard系数(JC) $JC=\frac{a}{a+b+c}$
FM指数 $FMI=\sqrt{\frac{a}{a+b}·\frac{a}{a+c}}$
Rand指数 $RI=\frac{2(a+d)}{m(m-1)}$ 显然，上述性能度量的结果值均在[0,1]区间，值越大越好

考虑聚类结果的簇划分$C={C_1,C_2,….,C_k},定义$

$avg(C)=\frac{2}{|C|(|C-1)}\sum_{1≤i＜j≤|C|}dist(x_i,x_j)$ $diam(C)=max_{1≤i＜j≤|C|}dist(x_i,x_j)$ $d_{min}(C_i,C_j)=min_{x_i∈C_i,x_j∈C_j}dist(x_i,x_j)$ $d_{cen}(C_i,C_j)=dist(\mu_i,\mu_j)$

其中,dist(·,·)用于计算两个样本之间的距离;$\mu$代表簇C的中心点$\mu=\frac{1}{|C|}\sum_{1≤i≤|C|}x_i$.
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$中心点的距离。

基于上面的式子可导出下面这些常用的聚类性能度量内部指标

DB指数(DBI) $DBI=\frac{1}{k}\sum_{i=1}^kmax_{j≠i}(\frac{avg(C_i)+avg(C_j)}{d_{cen}(\mu_i,\mu_j)})$
Dunn指数(DI) $DI=min_{1≤i≤k}{min_{j≠i}(\frac{d_{min}(C_i,C_j)}{max_{1≤l≤k}diam(C_l)})}$

显然,DBI的值越小越好,而DI则相反,值越大越好.

距离计算

对函数$dist(·,·)$,若它是一个”距离度量”，则需满足一些基本性质:

非负性:$dist(x_i,x_j)≥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)≤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})$,最常用的是”闵科夫斯基距离”
对p≥1,显然满足上面距离度量的性质

我们常将属性划分为”连续属性”和”离散属性”.另外在讨论距离计算时,属性上是否定义了”序”关系更为重要。例如定义域为{1,2,3}的离散属性与连续属性的性质更接近一些,能直接在属性值上计算距离:”1”与”2”比较接近,与”3”比较远,这样的离散属性则不能直接在属性值上计算距离,称为”无序属性”.显然,闵科夫斯基距离可用于有序属性.

对于无序属性可采用VDM(Value Difference Metric).令$m_[u,a]$表示在属性u上取值为a的样本数,k为样本簇数,则属性u上两个离散值a与b之间的VDM距离为

$VDM_{p}(a,b)=\sum_{i=1}^k|\frac{m_{u,a,i}}{m_{u,a}}-\frac{m_{u,b,i}}{m_{u,b}}|^p$

于是,将闵科夫斯基距离和VDM结合即可处理混合属性.假定有$n_c$个有序属性，$n-n_c$个无序属性,不失一般性,令有序属性排列在无序属性之前,则

$MinkovDM_p(x_i,x_j)=(\sum_{u=1}^{n_c}|x_{iu}-x_{ju}|^p+\sum_{u=n_c+1}^nVDM_p(x_{iu},x_{ju}))^{\frac{1}{p}}$

当样本空间中不同属性的重要性不同时,可使用”加权距离”.以加权闵科夫斯基距离为例:

$dist_{wmk}(x_i,x_j)=(w_1·|x_{i1}-x_{j1}|^p+...+w_n·|x_{in}-x_{jn}|^p)^{\frac{1}{p}}$

原型聚类

原型聚类亦称为”基于原型的聚类”,此类算法假设聚类结构能通过一组原型刻画,在现实聚类任务中极为常见.

k均值算法

机器学习(五)——k-means

学习向量量化（LVQ）

“学习向量量化”也是试图找到一组原型向量来刻画聚类结构,但与一般聚类算法不同的是,LVQ假设数据样本带有类别标记，学习过程利用样本的这些监督信息来辅助聚类.

给定样本集$D={(x_1,y_1),(x_2,y_2),….(x_m,y_m)}$每个样本$x_j$是由n个属性描述的特征向量$(x_{j1};x_{j2};….;x_{jn}),y_i∈Y$是样本$x_j$的类别标记.LVQ的目标是学得一组n维原型向量${p_1,p_2,…,p_q}$,每个原型向量代表一个聚类簇,簇标记$t_i$∈Y

学得一组原型向量之后,即可实现对样本空间的簇划分,对任意样本$\vec{x}$,它被划入与其距离最近的原型向量所代表的簇中,换言之,每个原型向量$\vec{p_i}$定义了一个与之相关的区域$R_i$，该区域中每个样本与$\vec{p_i}$的距离不大于它与其他原型向量$\vec{p’_ i}$的距离，即

若将$R_i$中的样本全用向量$\vec{p_i}$表示,则可实现数据的有损压缩，这称为向量化,LVQ由此而得名

密度聚类

密度聚类亦称为”基于密度的聚类”,此类算法假设聚类结构能通过样本分布的紧密程度确定.
DBSCAN是一种著名的密度聚类算法,它基于一组”邻域”参数($\epsilon$,MinPts)来刻画样本分布的密度程度,给定数据集$D={x_1,x_2,…,x_m}$,定义下面几个概念:

$\epsilon邻域：对x_j∈D,其\epsilon邻域包含样本集D中与x_j的距离不大于\epsilon的样本,即N_{\epsilon}(x_j)=\{x_i∈D|dist(x_i,x_j)≤\epsilon\}$
核心对象：若$x_j$的$\epsilon$-邻域至少包含MinPts个样本,即$|N_{\epsilon}(x_j)|≥MinPts,则x_j是一个核心对象$
密度直达：若$x_j$位于$x_i$的$\epsilon邻域$中，且$x_i$是核心对象，则称$x_j$由$x_i$密度直达
密度可达：对$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$密度可达
密度相连:对$x_i$与$x_j$,若存在$x_k$使得$x_i$与$x_j$均由$x_k$密度可达,则称$x_i$与$x_j$密度相连.

基于这些概念,DBSCAN将”簇”定义为:由密度可达关系导出的最大的密度相连样本集合.形式化地说,给定邻域参数$(\epsilon,MinPts)$,簇C$\subseteq D$满足以下性质地非空样本子集:

层次聚类
层次聚类(hierarchical clustering)试图在不同层次对数据集进行划分，从而形成树形的聚类结构
AGNES是一种采用自底向上聚合策略的层次聚类算法，它先将数据集中的每个样本看作一个初始簇，然后在算法的每一步中找出距离最近的两个聚类进行合并，直到达到预设的聚类簇个数，这里的关键是如何计算聚类簇之间的距离，给定聚类簇$C_i与C_j$可通过下面的式子来计算距离：

聚类