聚类性能度量
聚类性能度量大致有两类。一类是将聚类结果与某个“参考模型”(reference model)进行比较，称为“外部指标”(external index);
另一类是直接考察聚类结果而不利用任何参考模型，称为“内部指标”(internal index)。
内部指标
对数据集$D = \lbrace x_1, x_2, \ldots, x_m \rbrace$,假定通过聚类给出的簇划分为$C = \lbrace C_1, C_2, \ldots, C_k \rbrace$,
参考模型给出的簇划分为$ C^* = { C_1^*, C_2^*, C_s^* }$。相应地，令$\lambda$与$\lambda^*$分别表示
与$C$和$C^*$对应的簇标记向量。我们将样本两两配对考虑，定义
$ a = \mid SS \mid, SS = { (x_i,x_j) \mid \lambda_i = \lambda_j , \lambda_i^* = \lambda_j^* , i<j }$
$ a = \mid SD \mid, SD = { (x_i,x_j) \mid \lambda_i = \lambda_j , \lambda_i^* \neq \lambda_j^* , i<j }$
$ a = \mid DS \mid, DS = { (x_i,x_j) \mid \lambda_i \neq \lambda_j , \lambda_i^* = \lambda_j^* , i<j }$
$ a = \mid DD \mid, DD = { (x_i,x_j) \mid \lambda_i \neq \lambda_j , \lambda_i^* \neq \lambda_j^* , i<j }$
其中集合SS包含了在$C$中隶属相同簇且在$C^*$中也隶属相同簇的样本对，集合SD包含了在$C$中隶属于相同簇但在$C^*$中隶属于
不同簇的样本对，$\cdots \cdots$由于每个样本对$(x_i,x_j)(i<j)$仅能出现在一个集合中，因此有$a+b+c+d=m(m-1)/2$成立。
Jaccard系数(Jaccard Coefficient,简称JC)
$ JC = \frac{a}{a+b+c} $FM指数(Fowlkes and Mallows Index,简称FMI)
$ FMI = \sqrt{\frac{a}{a+b} \cdot \frac{a}{a+c}} $Rand指数(Rand Index,简称RI)
$ RI = \frac{2(a+d)}{m(m-1)} $
显然，上述性能度量指标的结果均在[0,1]区间，值越大越好。
外部指标
考虑聚类结果的簇划分$C = { C_1, C_2, \ldots, C_k }$,定义
$ avg(C) = \frac{2}{\mid C \mid (\mid C \mid - 1)} \sum_{1 \leq i < j \leq \mid C \mid} dist(x_i,x_j) $
$ diam(C) = \max_{1 \leq i < j \leq \mid C \mid } 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) $
其中，$dist(\cdot, \cdot)$用于计算两个样本之间的距离；$\mu$代表簇$C$的中心点$\mu = \frac{1}{\mid C \mid} \sum_{1 \leq i \leq \mid C \mid} 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指数(Davies-Bouldin Index,简称DBI)
$ DBI = \frac{1}{k} \sum_{i=1}^k \max_{j \neq i} \left( \frac{avg(C_i) + avg(C_j)}{d_{cen} (\mu_i,\mu_j)} \right) $Dunn指数(Dunn Index,简称DI)
$ DI = \min_{1 \leq i \leq k} \left\lbrace \min_{j \neq i} \left( \frac{d_{min} (C_i,C_j)}{\max_{1 \leq l \leq k} \ diam(C_l)} \right) \right\rbrace $
显然，DBI的值越小越好，而DI则相反，值越大越好。
Entropy
对于一个聚类i，首先计算$P_{ij}$。$P_{ij}$指的是聚类i中的成员（member）属于类（class）j的概率，
$P_{ij} = \frac{m_{ij}}{m_i}$。其中$m_i$是聚类i中所有成员的个数，$m_{ij}$是聚类i中的成员属于
类j的个数。每个聚类的entropy可以表示为$e_i = - \sum_{j=1}^L P_{ij} \log_2 P_{ij}$，其中L是
类（class）的个数。整个聚类划分的entropy为$e = \sum_{i=1}^K \frac{m_i}{m}e_i$，其中K是聚类（cluster）
的数目，m是整个聚类划分所涉及到的成员个数。
Purity
使用上述Entropy中的$P_{ij}$定义，我们将聚类i的purity定义为$p_i = \max(p_{ij})$。整个聚类划分的purity为
$purity = \sum_{i=1}^K \frac{m_i}{m} P_i$，其中K是聚类（cluster）的数目，m是整个聚类划分所涉及到的成员个数。
相似性度量
我们常将属性划分为“连续属性”(continuous attribute)和“离散属性”(categorical attribute)，前者在定义域上有无穷多个
可能的取值，后者在定义域上是有限个取值。然而，在讨论距离计算时，属性上是否定义了“序”关系更为重要。例如定义域为
${ 1, 2, 3 }$的离散属性与连续属性的性质更接近一些，能直接属性值上计算距离：“1”与“2”计较接近、与“3”比较远，这样
的属性称为“有序属性”(ordinal attribute);而定义域为${ 飞机, 火车, 轮船 }$这样的离散属性则不能直接在属性值上计算
距离，称为“无序属性”(non-ordinal attribute)。
有序属性的度量
欧氏距离（Euclidean Distance）
欧氏距离是最易于理解的一种距离计算方法，源自欧式空间中两点间的距离公式。
$d_{12} = \sqrt{\sum_{k=1}^n (x_{1k} - x_{2k})^2}$曼哈顿距离（Manhattan Distance）
曼哈顿距离也称为城市街区距离（City Block Distance）
$ d_{12} = \sum_{k=1}^n \mid x_{1k} - x_{2k}\mid $切比雪夫距离（Chebyshev Distance）
$ d_{12} = \max_i(\mid x_{1i} - x_{2i}\mid) $
另一种形式为：
$ d_{12} = \lim_{k \rightarrow \infty} {\left( \sum_{i=1}^n {\mid x_{1i} - x_{2i} \mid}^k \right)}^{\frac{1}{k}} $闵可夫斯基距离（Minkowski Distance）
闵可夫斯基距离不是一种距离，而是一组距离的定义。
$ d_{12} = \sqrt[p]{\sum_{k=1}^n {\mid x_{1k} - x_{2k} \mid}^p}$
其中p是一个参数。
当p=1时，就是曼哈顿距离；
当p=2时，就是欧氏距离；
当p=3时，就是切比雪夫距离。
根据变参数的不同，闵氏距离可以表示一类的距离。
闵氏距离的缺点
闵氏距离，包括曼哈顿距离、欧氏距离和切比雪夫距离都存在明显的缺点。
举个例子：二维样本（身高，体重），有三个样本：a(180, 50), b(190, 50), c(180, 60)。那么a与b直觉的闵氏距离等于a与c之间
的闵氏距离，但是身高的10cm真的等价于体重的10kg么？因此用闵氏距离来衡量这些样本间的相似度很有问题。
简单来说，闵氏距离的缺点主要有两个：
(1) 将各个分量的量纲(scale), 也就是“单位”当做相同的看待了；
(2) 没考虑各个分量的分布(期望，方差等)可能是不同的。标准化欧氏距离（Standardized Euclidean Distance）
标准化欧氏距离是针对简单欧氏距离的缺点而作的一种改进方案。标注欧氏距离的思路：既然数据各维分量的分布不一样，那么先
将各个分量都标准化到均值、方差相等。假设样本集X的均值(mean)为m，标准差(standard deviation)为s。样本集的标准化过程用
公式描述就是：
$X^* = \frac{X-m}{s} $
标准化后的值 = (标准化前的值 - 分量的均值) / 分量的标准差
经过简单的推导就可以得到两个n维变量$a(x_{11}, x-{12}, \ldots, x_{1n})$与$b(x_{21}, x_{22}, \ldots, x_{2n})$间的
标准化欧氏距离的公式：
$ d_{12} = \sqrt{\sum_{k=1}^n {\left( \frac{x_{1k} - x_{2k}}{s_{k}} \right)}^2} $
如果将方差的倒数看成是一个权重，这个公式可以看成是一种加权欧氏距离(Weighted Euclidean Distan马氏距离（Mahalanobis Distance）
有M个样本向量$X_1~X_m$，协方差矩阵记为S，均值记为向量$\mu$，则其中样本向量X到$\mu$的马氏距离表示为：
$ D(X) = \sqrt{(X_i-X_j)^T S^{-1} (X_i - X_j)}$
而其中向量$X_i$与$X_j$之间的马氏距离定义为：
$ D(X_i, X_j) = \sqrt{(X_i - X_j)^T S^{-1} (X_i - X_j)}$
若协方差矩阵是单位矩阵（各个样本向量之间独立同分布），则公式就成了：
$ D(X_i, X_j) = \sqrt{(X_i - X_j)^T (X_i - X_j)}$
也就是欧氏距离了。
若协方差矩阵是对角矩阵，公式变成了标准化欧氏距离。
马氏距离的优点：量纲无关，排除变量之间的相关性的干扰。夹角余弦（Cosine）
$ \cos(\theta) = \frac{\sum_{k=1}^n x_{1k} x_{2k}}{\sqrt{\sum_{k=1}^n {x_{1k}}^2} \sqrt{\sum_{k=1}^n {x_{2k}}^2}} $
夹角余弦取值范围为[-1,1]。夹角余弦越大表示两个向量的夹角越小，夹角余弦越小表示两向量的夹角越大。当两个向量的方向
重合时夹角余弦取最大值1，当两个向量的方向完全相反时夹角余弦取最小值-1。汉明距离（Hamming Distance）
两个等长字符串s1与s2之间的汉明距离定义为将其中一个变为另外一个所需要做的最小替换次数。例如字符串“1111”与“1001”之
间的汉明距离为2。
应用：信息编码（为了增强容错性，应使得编码间的最小汉明距离尽可能大）。杰卡德相似系数（Jaccard Similarity Coefficient）
(1) 杰卡德相似系数
两个集合A和B的交集元素在A、B的并集中所占的比例，称为两个集合的杰卡德相似系数：
$ J(A,B) = \frac{\mid A \bigcap B \mid}{\mid A \bigcup B \mid} $
(2) 杰卡德距离
$ J_{\delta}(A,B) = 1 - J(A,B) = \frac{\mid A \bigcup B \mid - \mid A \bigcap B \mid}{\mid A \bigcup B \mid}$
(3) 杰卡德相似系数与杰卡德距离的应用
样本A与样本B是两个n维向量，并且所有维度的取值都是0或1.例如：A(0, 1, 1, 1), B(1, 0, 1, 1)。我们将样本看成一个集合，
1表示集合包含该元素，0表示集合不包含该元素。
p : 样本A与B都是1的维度的个数；
q : 样本A是1，样本B是0的维度的个数；
r : 样本A是0，样本B是1的维度的个数；
s ：样本A与B都是0的维度的个数。
p+q+r可以理解为A与B的并集的元素的个数，而p是A与B的交集的元素个数。
$ J = \frac{p}{p+q+r} $相关系数（Correlation Coefficient）与相关距离（Correlation Distance）
(1) 相关系数的定义
$\rho_{XY} = \frac{Cov(X,Y)}{\sqrt{D(X)} \sqrt{D(Y)}} = \frac{E((X-EX)(Y-EY))}{\sqrt{D(X)} \sqrt{D(Y)}} $
相关系数是衡量随机变量X与Y相关程度的一种方法，相关系数的取值范围是[-1,1]。相关系数的绝对值越大，则表明X与Y相关度
越高。当X与Y线性相关时，相关系数取值为1（正线性相关）或-1（负线性相关）。
(2) 相关距离的定义
$D_{XY} = 1 - \rho_{XY}$信息熵（Information Entropy）
信息熵并不属于一种相似性度量。信息熵是衡量分布的混乱程度或分散程度的一种度量。分布越分散（或者说分布越平均），信息熵
就越大；分布越有序（或者分布越集中），信息熵就越小。
计算给定的样本集X的信息熵的公式：
$ Entropy(X) = \sum_{i=1}^n -p_i \log_2 p_i$
参数的含义：
n : 样本集X的分类数；
$p_i$ : X中第i类元素出现的概率
信息熵越大表明样本集S分类越分散，信息熵越小则表明样本集X分类越集中。当S中n个分类出现的概率一样大时（都是$\frac{1}{n}$)，
信息熵取最大值$ \log_2(n)$。当X只有一个分类时，信息熵取最小值0。
无序属性的度量
- VDM(Value Difference Metric)
令$m_{\mu,a}$表示在属性$\mu$上取值为a的样本数，$m_{\mu,a,i}$表示在第i个样本簇中在属性$\mu$上取值为a的样本数，
k为样本簇数，则属性$\mu$上两个离散值a与b之间的VDM距离为:
$ VDM_p(a,b) = \sum_{i=1}^k {\mid \frac{m_{\mu,a,i}}{m_{\mu,a}} - \frac{m_{\mu,b,i}}{m_{\mu,b}} \mid}^p $
于是，将闵可夫斯基距离和VDM结合即可处理混合属性。假定有$n_c$个有序属性、$n-n_c$个无序属性，不失一般性，令有序
属性排在无序属性之前，则
$ MinkovDM_p(x_i,x_j) = {\left( \sum_{\mu=1}^{n_c} {\mid x_{i \mu} - x_{j \mu} \mid}^p + \sum_{\mu = n_c + 1}^n VDM_p (x_{i \mu}, x_{j \mu}) \right) }^{\frac{1}{p}} $
黑科技
SimHash + 汉明距离
simhash是谷歌发明的算法，据说很nb，可以将一个文档转换成64位的字节，然后我们可以通过判断两个字节的汉明距离就知道是否相似了。
汉明距离是以理查德·卫斯里·汉明的名字命名的。在信息论中，两个等长字符串之间的汉明距离是两个字符串对应位置的不同字符的个数。换句话说，它就是将一个字符串变换成另外一个字符串所需要替换的字符个数。例如：
1011101 与 1001001 之间的汉明距离是 2。
“toned” 与 “roses” 之间的汉明距离是 3。
首先我们来计算SimHash：
① 提取文档关键词得到[word,weight]这样一个数组。（举例 [美国，4]）
② 用hash算法将word转为固定长度的二进制值的字符串[hash(word),weight]。（举例 [100101，4]）
③ word的hash从左到右与权重相乘，如果为1则乘以1 ，如果是0则曾以-1。（举例4,-4,-4,4,-4,4）
④ 接着计算下个数，直到将所有分词得出的词计算完，然后将每个词第三步得出的数组中的每一个值相加。（举例美国和51区，[4,-4,-4,4,-4,4]和[5 -5 5 -5 5 5]得到[9 -9 1 -1 1 9]）
⑤ 对第四步得到的数组中每一个值进行判断，如果＞0记为1，如果＜0记为0。（举例[101011]）
第四步得出的就是这个文档的SimHash。
这样我们就能将两个不同长度的文档转换为同样长度的SimHash值，so，我们现在可以计算第一个文档的值和第二个文档的汉明距离（一般<3就是相似度高的）。
SimHash本质上是局部敏感性的hash（如果是两个相似的句子，那么只会有部分不同），和md5之类的不一样。 正因为它的局部敏感性，所以我们可以使用海明距离来衡量SimHash值的相似度。
如果想要小数形式的可以这么做：1 - 汉明距离 / 最长关键词数组长度。
参考资料
机器学习中的相似性度量
机器学习：第九章 聚类—周志华