在进入算各算法前，最后介绍一下相异性计算，是每种算法都需要用到的基础知识。
相异性计算
很多算法都是根据数据在空间中的位置进行分类与聚类，在你还不能把一条数据在脑海中映射到一个空间中去的时候。可以先看看这个：
相异性矩阵
我们的数据大致情况都是如以下矩阵所述：每行为一条数据，每列为一个属性
$$
\begin{matrix}
x_{1,a} & … & x_{1,b} & … & x_{1,c} \\
… & … & … & … & … \\
x_{i,a} & … & x_{i,b} & … & x_{i,c} \\
… & … & … & … & … \\
x_{n,a} & … & x_{n,b} & … & x_{n,c} \\
\end{matrix}
$$
那么可以构造出这样一个矩阵，使得任意两条数据的距离(相异性)都可以通过矩阵得到，称作相异性矩阵，表示方式如下：
$$
\begin{matrix}
0 \\
d(2,1) & 0 \\
d(3,1) & d(3,2) & 0 \\
… & … & … & … \\
d(n,1) & d(n,2) & … & … & 0 \\
\end{matrix}
$$
这里的 d(i,j) 是第 i 个元素和第 j 的元素的差异值，是一个0到1之间的数，没有差异为0，完全相反则为1，如果根据上面的数组，构造一个差异化矩阵，那么就是这样的。
有很多算法都是以相异性矩阵为基础进行运算的。那么问题来了，如何计算相异性呢？而且还有各种各样的数据的相异性如何计算？
空间度量
标称属性计算
在统计里面，叫做类型数据，在数据挖掘里面通常叫标称属性，比如颜色，红，黄，蓝等，怎么计算相相似度，通常使用数量个数去匹配，不去管它的具体内容。
$$
d(i,j) = \frac{p-m}{p} \\
sim(i,j) = 1 - d(i,j) = \frac{m}{p}
$$
通常d(i,j) 是i 和 j 的相异性，sim(i,j) 为 i和j 的相似性。p为属性的个数，m为相同的属性个数。
比如这样一个数据：每个人有两个属性：性别，爱好
人，性别，爱好
甲，男，蓝色
乙，女，蓝色
丙，男，红色
那么计算相似性就是
d(甲，乙) = (2-1)/2 = 1/2
sim(甲，乙) = 1 - d(甲，乙) = 1/2
d(乙,丙) = (2-0)/2 = 1
sim(乙,丙) = 1 - d(甲，乙) = 0
可以得出，在性别和爱好上，乙和丙完全相异，好像是废话，一般实际应用中，还会加上权重等，可以根据实际情况去优化这个公式。
二元属性
二元属性，其实就是一种特殊的标称属性，程序中叫true，false，boolean，0，1等等，有特殊性就会有特殊的算法去计算，公式如下
$$
d(i,j) = \frac{r+s}{q+r+s+t} \\
d(i,j) = \frac{r+s}{q+r+s} \\
$$
其中，r是在对象i中为true，在j中为false的个数， s是在对象i中为false,在j中为true的个数
q是都为true的个数，t则为都为false的个数。一般情况下，认为都为false的情况是不重要的，所以有了下面的公式。这里面不多举例了
数值属性
欧几里得距离:
欧氏距离：最常使用计算距离的方法，理论可以称为“两点之间，线段最短”，欧氏距离指的就是两点间的最短距离。
二维和三维空间的两个点是很好想象的，三维以上的，实际上就是多加一维，多一个距离的开方了。
$$
d(i,j) = \sqrt{(x_{i1}-y_{i1})^2 + (x_{i2}-y_{i2})^2 + … +(x_{ip}-y_{ip})^2}
\tag{欧几里得距离}
$$
曼哈顿距离:
曼哈顿距离：比欧氏距离容易理解一点吧，欧氏距离是“两点之间，线段最短”，但“线段”，在有些场景是走不通的。
比如二维空间的两个坐标[1,1]和[2,2]，我是不能从[1,1]直接走到[2,2]的，我要先沿着x轴走至[2,1]或者先沿着y轴走到[1,2]后，才能再走到[2,2]，那么三维以上的空间的话，无非也就是轴多了一些，算起来就是路径的长度，所以曼哈顿距离又称城市距离。
$$
d(i,j) = |x_{i1}-y_{i1}| + |x_{i2}-y_{i2}| + … + |x_{ip}-y_{ip}|
\tag{曼哈顿距离}
$$
附：网上盗个一看就懂的图
闵可夫斯基距离:
后来，又有闵可夫斯基对这两个算法进行了扩展，吸收二者的优先，出现了闵可夫斯基距离（闵氏距离）
$$
d(i,j) = \sqrt[p]{|x_{i1}-y_{i1}|^h + |x_{i2}-y_{i2}|^h + … + |x_{ip}-y_{ip}|^h}
\tag{闵氏距离}
$$
其中，h的值就等于p，为了公式好看保留p做常数而已。
另外，还有上确界距离、切比雪夫距离、加权欧几里得距离等等，不一一介绍了。
马氏距离
马氏距离：协方差距离，这个是概率上的，先要算得一个协方差矩阵，有点概率的意思了。
一维空间的马氏距离有点像我们的标准差压缩，比如，一组数据 [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,3]中，1与2的距离如果用欧氏或曼哈顿距离都是1，在马氏距离中，就是2了（相隔两个标准差），而在数据[1,2,3,4,5,6,7]中，1和2的距离就是0.5。
在二维或更高维的空间里，两个点之间的距离就和每属性的分布的形态相关了。
序数属性
序数属性最常用的处理方式就是将属性映射到[0,1]的空间内，比如低、中、高，就是[0,0.5,1]这样。再使用欧氏距离直接运算即可。比如低和高的相异性为1，相似性为0。
混合属性
一个对象肯定不是只有一种类型的属性，对于多种类型的属性，分开求完之后，我们再用混合属性公式代入，即可求得最后的相异性。
$$
d(i,j) = \frac{\sum^{p}{f=1}\sigma^{(f)}{ij}d^{(f)}{ij}}{\sum^{p}{f=1}\sigma^{(f)}_{ij}}
$$
余弦相似度
最后，如果用到文本分析的话，最好了解一下余弦相似度，两篇文章有多相似，一般可以通过词频来构造一个矩阵，每一篇文章里面都有一个所谓的词频向量（这里可以把向量理解为坐标轴上的一条直线），通过两个向量的夹角，计算两篇文档的相似度。
一般，需要先构造词频向量，然后就可以计算了：
$$
sim(x,y) = \frac{x * y}{||x|| * ||y||}
$$
小结
理解数据是挖掘数据的第一步，数据的各种特征是有什么特性，是什么分布，适合用什么尺度去度量，这些不是算法能帮你做的事，都是通过各种实验、假设检验去慢慢验证的。