信息熵 (Entropy)
1948年香农（Claude Shannon）在“通信的数学原理”中提出了信息上的概念。实质上是使用比特（Bit）来度量信息量，在计算中一个字节是8个比特。信息量的比特数和所有可能情况的对数函数log有关，例如一个事情有32中情况那么他的信息熵为log32 = 5。
一般，由于不同情况的发生概率不相同的所以香农指出准确的信息量H的计算公式参考下面信息熵的定义。
信息熵的定义如下：
$$ H(X) = -\sum_{x\in{X}}P(x)logP(x) $$
条件熵 (Conditional Entropy)
假定X和Y是两个随机变量，X使我们需要了解的。如果我们知道了X的随机分布P(X)，也就知道了X的熵。但如果我们只知道一些Y的情况，Y与X一起出现的概率也就是他们的联合概率分布（JointProbability），以及Y发生下X发生的概率即条件概率分布。定义在Y的条件下的条件熵为：
$$ H(X|Y) = -\sum_{x\in{X},y\in{Y}}P(x,y)logP(x|y) $$
互信息 (Mutual Information)
互信息是一个取值在0到min(H(X),H(Y))之间的函数，用来表明X与Y的相关性。当二者完全相关取值为1，完全无关取值为0。互信息定义如下：
$$ I(X;Y) = -\sum_{x\in{X},y\in{Y}}P(x,y)log\frac{P(x,y)}{P(x)P(y)} $$
$$ I(X;Y) = H(X) - H(X|Y) $$
相对熵 (Relative Entropy)
相对熵又名交叉熵，同互信息一样也是用来衡量相关性，但和变量的互信息不同，主要是衡量取值为正数的两个函数的相似性，定义如下：
$$ KL(f(x)||g(x)) = -\sum_{x\in{X}}f(x)*log\frac{f(x)}{g(x)} $$
相对熵的对称性表达为：
$$ JS(f(x)||g(x)) = \frac{1}{2}[KL(f(x)||g(x))+KL(g(x)||f(x))] $$
同质性(Homogeneity) & 完整性（completeness）
同质性和完整性是用于评估衡量聚类算法聚类结果的两个标准。二者往往具有一定的负相关性。
同质性是指：每一个cluster(聚类结果簇)中所包含的数据应归属于一个class(类)。
完整性是指：所有属于同一个class的数据应该被归到相同的cluster中。
我们假定数据集有N个数据。分类classes使用\(C = {c_i|i=1,…,n } \),聚类结果clusters，\(K= {ki|1,…,m }\). 所以\( A = a{ij} \)中的 \(a_{ij}\)表示数据属于class \(c_i\) 和 cluster\(k_j\)
我们定义当H(C,K)=0时，Homogeneity和completeness都为1。所以h和c可以做如下定义：
$$
h=
\begin{cases}
1 &\mbox{if H(C,K)=0}\\
1-\frac{H(C|K)}{H(C,K)} &\mbox{else}
\end{cases}
$$
$$
c=
\begin{cases}
1 &\mbox{if H(K,C)=0}\\
1-\frac{H(K|C)}{H(K,C)} &\mbox{else}
\end{cases}
$$
其中
$$ H(C|K) = -\sum_{k=1}^{|K|}\sum_{c=1}^{|C|}\frac{A_{ck}}{N}log\frac{A_{ck}}{\sum_{c=1}^{|C|}A_{ck}} $$
$$ H(C,K) = -\sum_{k=1}^{|K|}\sum_{c=1}^{|C|}\frac{A_{ck}}{N}log\frac{A_{ck}}{N} $$
$$ H(K|C) = -\sum_{c=1}^{|C|}\sum_{k=1}^{|K|}\frac{A_{ck}}{N}log\frac{A_{ck}}{\sum_{k=1}^{|K|}A_{ck}} $$
$$ H(K,C) = H(C,K) $$
最终，我们计算V-measure通过给予h和c不同的权重。其中b大于1时completeness影响更大
$$ V_b = \frac{(1+b)hc}{(b * h)+c} $$
参考：
- 《数学之美》第二版 吴军著
- Rosenberg A, Hirschberg J. V-Measure: A Conditional Entropy-Based External Cluster Evaluation Measure[C]//EMNLP-CoNLL. 2007, 7: 410-420.
