目录
- 五、聚类的质量评价
- （一）簇的数目估计
- （二）外部质量评价
- （三）内部质量评价
- 六、离群点挖掘
- （一）相关问题概述
- （二）基于距离的方法
- （三）基于相对密度的方法
- 七、其它聚类方法
五、聚类的质量评价
聚类分析是将一个数据集分解成若于个子集，每个子集称为一个簇，所有子集形成的集合称为该对象集的一个聚类。一个好的聚类算法应该产生高质量的簇和高质量的聚类，即簇内相似度总体最高，同时簇间相似度总体最低。鉴于许多聚类算法，包括 k k k-平均算法， DBSCAN算法等都要求用户事先指定聚类中簇的数目 k k k，因此，下面首先讨论k的简单估计方法。
（一）簇的数目估计
许多聚类算法，比如
k
k
k-平均算法，甚至DIANA算法等，都需要事先指定簇的数目
k
k
k，并且
k
k
k的取值会极大地影响聚类的质量，然而事先确定簇的数目
k
k
k并非易事。我们可以先考虑两种极端情况。
（1）把整个数据集
S
S
S当作一个簇，即令
k
=
1
k=1
k=1，这样做看上去既简单又方便，但这种聚类分析结果没有任何价值。
（2）把数据集
S
S
S的每个对象当作一个簇，即令
k
=
∣
S
∣
=
n
k=|S|=n
k=∣S∣=n，这样就产生了最为细粒度的聚类。因此，每个簇都不存在簇内差异，簇内相似度就达到最高。但这种聚类并不能为
S
S
S提供任何关于
S
S
S的概括性描述。
由此可知，簇的数目
k
k
k至少应该满足
2
≤
k
≤
n
−
1
2≤k≤n-1
2≤k≤n−1，但簇数
k
k
k具体取什么值最为恰当仍然是含糊不清的。
一般认为，
k
k
k的取值可以通过数据集分布的形状和尺度，以及用户要求的聚类分辨率来进行估计，且学者们已经有许多不同的估计方法，比如肘方法 (elbow method)，交叉验证法以及基于信息论的方法等。
一种简单而常用的
k
k
k值经验估计方法认为，对于具有
n
n
n个对象的数据集，其聚类的簇数
k
k
k取
n
2
\begin{aligned}\sqrt\frac{n}{2}\end{aligned}
2n 为宜。这时，在平均期望情况下每个簇大约有
2
n
\sqrt{2n}
2n 个对象。在此基础上，还有人提出了进一步附加限制，即簇数
k
<
n
k<\sqrt{n}
k<n。
比如，设
n
=
8
n=8
n=8，则簇数
k
=
2
k=2
k=2 为宜，且在平均情况下每个簇有4个点，而根据附加的经验公式
k
<
2.83
k<2.83
k<2.83。利用这两个关于簇数
k
k
k的经验公式，似乎也从一个侧面说明，例10-5中
k
=
2
k=2
k=2 是最恰当的簇数。
（二）外部质量评价
如果我们已经很好地通过估计得到了聚类的簇数
k
k
k，就可以使用一种或多种聚类方法， 比如，
k
k
k-平均算法，凝聚层次算法或者DBSCAN算法等对已知数据集进行聚类分析，并得到多种不同的聚类结果。现在的问题是哪-种方法的聚类结果更好一些，或者说，如何比较由不同方法产生的聚类结果，这就是聚类的质量评价。
目前，对聚类的质量评价已有许多方法可供选择，但一般可以分为两大类，即外部 (extrinsic) 质量评价和内部 (intrinsic) 质量评价。
外部质量评价假设数据集已经存在一种理想的聚类 (通常由专家构建)，并将其作为常用的基准方法与某种算法的聚类结果进行比较，其比较评价主要有聚类熵和聚类精度两种常用方法。
1、聚类熵方法
假设数据集
S
=
{
X
1
,
X
2
,
…
,
X
n
}
S=\{X_1,X_2,…,X_n\}
S={X1,X2,…,Xn}，且
T
=
{
T
1
,
T
2
,
…
,
T
m
}
T=\{T_1,T_2,…,T_m\}
T={T1,T2,…,Tm} 是由专家给出的理想标准聚类，而
C
=
{
C
1
,
C
2
,
…
,
C
k
}
C=\{C_1,C_2,…,C_k\}
C={C1,C2,…,Ck} 是由某个算法关于
S
S
S的一个聚类，则对于簇
C
i
C_i
Ci相对于基准聚类
T
T
T的聚类熵定义为
E
(
C
i
∣
T
)
=
−
∑
j
=
1
m
∣
C
i
∩
T
j
∣
∣
C
i
∣
log
2
∣
C
i
∩
T
j
∣
∣
C
i
∣
(10-20)
E(C_i|T)=-\sum_{j=1}^m\frac{|C_i\cap T_j|}{|C_i|}\log_2\frac{|C_i\cap T_j|}{|C_i|}\tag{10-20}
E(Ci∣T)=−j=1∑m∣Ci∣∣Ci∩Tj∣log2∣Ci∣∣Ci∩Tj∣(10-20) 而
C
C
C关于基准
T
T
T的整体聚类熵定义为所有簇
C
i
C_i
Ci关于基准
T
T
T的聚类熵的加权平均值，即
E
(
C
)
=
1
∑
i
=
1
k
∣
C
i
∣
∑
i
=
1
k
∣
C
i
∣
×
E
(
C
i
∣
T
)
(10-21)
E(C)=\frac{1}{\mathop{\sum}\limits_{i=1}^k|C_i|}\sum_{i=1}^k|C_i|\times E(C_i|T)\tag{10-21}
E(C)=i=1∑k∣Ci∣1i=1∑k∣Ci∣×E(Ci∣T)(10-21) 聚类熵方法认为，
E
(
C
)
E(C)
E(C) 值越小，其
C
C
C相对于基准
T
T
T的聚类质量就越高。
值得注意的是，公式 (10-21) 的右端第1项的分母
∑
i
=
1
k
∣
C
i
∣
\begin{aligned}\sum_{i=1}^k|C_i|\end{aligned}
i=1∑k∣Ci∣ 是每个簇中元素个数之和，且不能用
n
n
n去替换。因为，只有当
C
C
C是一个划分聚类时，分母才为
n
n
n，而一般的聚类方法，比如DBSCAN的聚类，其分母可能小于
n
n
n。
2、聚类精度
聚类精度 (precision) 评价的基本思想是使用簇中数目最多的类别作为该簇的类别标记，即对于簇 C i C_i