聚类任务

在无监督学习中，训练样本的标记信息是未知的，目标是通过无标记的训练样本学习来揭示数据的内在性质和规律，为进一步的数据分析提供基础。

无监督学习还有密度估计、异常检测等。

聚类是试图将数据集中的样本划分为若干个不相交的子集“簇”，每个簇对应一些潜在的概念（类别）。

聚类既可以作为一个单独过程，又可以用作分类等其他学习任务的前驱过程。

性能度量

直观上我们希望“物以类聚”，即同一簇的样本尽可能相似，不同簇样本尽可能不同，即“簇内相似度”高，“簇外相似度”低。

聚类的性能度量分成两类：

• 一类是将聚类结果与某个“参考模型”进行比较，称为外部度量。（如专家给出的划分结果）
• 另一个是直接考察聚类结果而不利用任何参考模型，称为“内部度量”

外部度量

假设通过聚类得到的划分结果是C，参考模型得到的划分结果是C*，定义：

• a = 在C中属于相同簇,且在C*中也属于相同簇的样本对 （1,1）
• b = 在C中属于相同簇,但在C*中属于不同簇的样本对 （1,0）
• c = 在C中属于不同簇,但在C*中属于相同簇的样本对 （0,1）
• d = 在C中属于不同簇,且在C*中也属于不同簇的样本对 （0,0）

由于每个样本仅能出现在一个集合中，有
a+b+c+d = m(m-1)/2

得到以下外部指标：

• Jaccard系数:
  $$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)}$$

内部度量

考虑簇的划分结果$\mathcal{C} = {C_1,C_2,…, C_k}$，定义：
$$avg(C) = \frac{2}{|C|(|C|-1)} \sum_{1\leq i < j \leq |C|} dist(x_i, x_j)$$
$$diam(C) = max_{1\leq i < j \leq |C|} dist(x_i, x_j)$$
$$d_{min} (C_i, C_j) = min_{x_i\in C_i, x_j \in C_j} dist(x_i, x_j)$$
$$d_{cen} (C_i, C_j) = dist(\mu_i, \mu_j)$$

$\mu$ 是C的中心点。avg是簇C内样本平均距离，diam是簇内样本间最远距离，dmin是簇间样本对距离，dcen是簇中心距离。

基于上面的式子可以得到下面的内部指标：

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

显然DBI越小越好，DI越大越好。

距离计算

距离的基本性质：

1. 非负性 dist(x1,x2)>=0
2. 同一性 dist(x1,x2)=0 当且仅当 x1 =x2
3. 对称性
4. 直抵性（三角不等式）

用于“有序距离”的闵可夫斯基距离

最常用的“闵可夫斯基距离”:
$$dist = {(\sum\limits_{k = 1}^n {|{p_k} - {q_k}{|^r}} )^{\frac{1}{r}}}$$

• r = 2 , 即欧式距离
• r = 1 , 即曼哈顿距离
• r = $\infty $ ， 即切比雪夫距离

用于“无序距离”的VDM（value difference metric）

$$VDM_p(a, b) = \sum_{i=1}^k |\frac{m_{u,a,i}}{m_{u,a}} - \frac{m_{u,b,i}}{m_{u,b}}|$$
m_ua是属性u上取值为a的样本数，m_u,a,i是第i个样本簇在属性u上取值为a的样本数。

将闵可夫斯基距离和VDM结合可以处理混合属性。
当样本中的不同属性重要性不同的时候可以使用“加权距离”。

我们通常用距离来定义相似度，相似度越大，距离越小，但是相似度度量未必要满足距离度量的所有性质，尤其是直递性。

在显示任务中，有必要基于样本来确定合适的距离计算式，可以通过“距离度量学习”实现。

原型聚类

原型聚类亦称作“基于原型的聚类”。此类算法假设聚类结构通过一组原型刻画，在显示聚类任务中极为常用。通常情况下，算法对原型进行初始化，然后对原型进行迭代更新求解。再用不用的二元性表示、不同的求解方式将会产生不同的算法。

k均值算法

k均值算法针对所有的簇划分，最小化平方误差:
$E = \sum_{i=1}^k \sum_{x\in C_i} ||x = \mu_i||_2^2$
找到最优解是NP难问题，因此k均值算法采用了贪心策略，通过迭代优化来近似求解。

学习向量量化

高斯混合聚类

密度聚类

层次聚类

课外阅读

1. 聚类也许是机器学习中“新算法”出现最多，最快的一个领域，因为不存在客观标准
2. 距离除了闵可夫斯基距离域外还有内积距离和余弦距离等