compactness：同一个簇内对象间的距离
separation：度量一个簇和其他簇的分离程度
connectivity：空间距离相近的对象放在同一聚类的程度 # Silhouette Coefficient 衡量一个对象与同簇的对象的相似性对比它与其他簇的对象的相似性的程度
假设 \(C_i\) 是一个包含了数据 \(i\) 的簇，对于数据点 \(i, i\in C_i\) 而言，有
\(a(i)=\frac{1}{C_i|-1}\sum_{j\in C_i, i\neq j}d(i,j)\)
\(b(i)=\underset{k\neq i}{min}\frac{1}{C_k|}\sum_{j\in C_k}d(i,j)\)
数据 \(i\) 的 Silhouette 值定义为 \(s(i)\frac{b(i)-a(i)}{max\{a(i), b(i)\}},\ if\ |C_i|>1\); \(s(i)=0,\ if \ |C_i|=1\)，而 \(-1\leq s(i)\leq 1\)。当 \(s(i)\) 越靠近 1，说明数据 \(i\) 被聚类在越适合的簇中，若 \(s(i)=0\)，说明数据 \(i\) 处在两个簇中间，若 \(s(i)\) 越靠近 -1，说明数据 \(i\) 很可能被错分了
对一个 \(K\) 个簇的集合，整体的 Silhouette Coefficient 定义为
\(SC=\underset{k}{max} \frac{1}{|C_k|}\sum_{i\in C_k} s(i)\)
Dunn Index
对于一个具有 \(K\) 个簇的集合，它的 Dunn Index 定义如下：
\(DI=\frac{\underset{1\leq i<j \leq K}{min}\delta(C_i, C_j)}{\underset{1\leq k \leq K}{max} \Delta_k}\)
其中 \(\delta(C_i, C_j)\) 指代簇间距离，\(\Delta_k\) 指代簇内聚类（直径），这个值越小越好
簇间距离的各种定义
- 两个簇之间最近的两个数据点之间的距离 \(\delta(C_i, C_j)=\underset{x\in C_i, y\in C_j}{min}d(x,y)\)
- 两个簇之间最远的两个数据点之间的距离 \(\delta(C_i, C_j)=\underset{x\in C_i, y\in C_j}{max}d(x,y)\)
- 两个簇中心的距离 \(\delta(C_i, C_j)=d(\mu_i, \mu_j), \mu_k=\frac{\sum_{x\in C_k} x}{|C_k|}\)
簇内聚类（直径）的各种定义
- 簇内距离最大的数据对的聚类 \(\Delta_k = \underset{x,y\in C_k}{max} d(x,y)\)
- 簇内所有词对的平均距离 \(\Delta_k = \frac{2}{|C_k|(|C_k|-1)}\sum_{x,y\in C_k,x\neq y}d(x,y)\)
- 簇内所有点到簇中心的聚类 \(\Delta_k = \frac{\sum_{x\in C_k} d(x,\mu_k)}{|C_k|}\)
Rand Index (需要 Gold Standard：一个人工分好的簇集合)
假设一个集合 \(S=\{o_1, o_2,...,o_n\}\) 包含 \(n\) 个元素。对它有一个划分 \(X=\{X_1,X_2,...,X_r\}\)，包含了 \(r\) 个子集；一个划分 \(Y={Y_1,Y_2,...,Y_s}\)，包含了 \(s\) 个子集，定义如下几个符号：
Rand Index
\(a\): 出现在 \(X\) 中相同子集，并且出现在 \(Y\) 中相同子集的元素对的个数 \((x,y), x\in X_i, y\in X_i, x\in Y_j, y\in Y_j\)
\(b\): 出现在 \(X\) 中不同子集，并且出现在 \(Y\) 中不同子集的元素对的个数 \((x,y), x\in X_i, y\notin X_i, x\notin Y_j, y\in Y_j\)
\(c\): 出现在 \(X\) 中相同子集，并且出现在 \(Y\) 中不同子集的元素对的个数 \((x,y), x\in X_i, y\in X_i, x\notin Y_j, y\in Y_j\)
\(d\): 出现在 \(X\) 中不同子集，并且出现在 \(Y\) 中相同子集的元素对的个数 \((x,y), x\notin X_i, y\in X_i, x\in Y_j, y\in Y_j\)
Rand Index 的定义为 \(RI=\frac{a+b}{a+b+c+d}=\frac{a+b}{\tbinom{n}{2}}=\frac{TP+TN}{TP+TN+FP+FN}\)，它衡量了两个划分的相似程度
Adjusted Rand Index
| \(Y_1\) | \(Y_2\) | ... | \(Y_s\) | sum | |
|---|---|---|---|---|---|
| \(X_1\) | \(n_{11}\) | \(n_{2}\) | ... | \(n_{1s}\) | \(a_{1}\) |
| \(X_2\) | \(n_{21}\) | \(n_{22}\) | ... | \(n_{2s}\) | \(a_{2}\) |
| ... | ... | ... | ... | ... | ... |
| \(X_r\) | \(n_{r1}\) | \(n_{r2}\) | ... | \(n_{rs}\) | \(a_{r}\) |
| sum | \(b_{1}\) | \(b_{2}\) | ... | \(b_{s}\) |
Adjusted Rand Index 的定义为 \(ARI=\frac{\sum_{ij}\tbinom{n_{ij}}{2}-\left[\sum_i \tbinom{a_i}{2} \sum_j \tbinom{b_j}{2}\right]/\tbinom{n}{2}}{\frac{1}{2}\left[\sum_i \tbinom{a_i}{2} \sum_j \tbinom{b_j}{2}\right]-\left[\sum_i \tbinom{a_i}{2} \sum_j \tbinom{b_j}{2}\right]/\tbinom{n}{2}}\)，它是基于 Rand Index 的改进，用于应对当 \(r\neq s\) 的情况
Micro Precision, Recall, F1 (需要 Gold Standard：一个人工分好的簇集合)
这个评判指标完全和分类中的一样，链接在这里 唯一不同的是如何决定 cluster 跟 Gold Standard 中的哪个 class 去计算指标，相对于先要给出 cluster 的class 标签。大致有两种方式：（1）由人工决定，这在一些词聚类上可以使用；（2）用 majority voting \(\underset{1\leq k\leq K}{argmax}|Cluster_i \cap Class_k|\) 来决定 cluster \(i\) 的 class 标签
Topic Coherence
参考 (References)
- https://en.wikipedia.org/wiki/Silhouette_(clustering)
- https://en.wikipedia.org/wiki/Dunn_index
- https://en.wikipedia.org/wiki/Rand_index
- http://qpleple.com/topic-coherence-to-evaluate-topic-models/