数据相似性的度量方法
现实中，我们需要处理的数据具有着不同的形式和特征。而对数据相似性的度量又是数据挖掘分析中非常重要的环节。针对这些不同形式的数据，不可能找到一种具备普遍意义的相似性度量算法，甚至可以说，每种类型的数据都有它对应的相似度度量标准。这些标准很多，也比较杂乱，有必要作以总结。
标称属性相似度度量
很简单，拿两个对象O1和O2举例，直接看这两个对象每种属性的属性值的匹配数。
假设这一类对象一共有n个属性（每个对象都有这n个属性），两个对象O1和O2匹配的属性数为m，那么相似度为匹配数占总属性数的总数。
即：sim(O1, O2) = m/n
二元属性相似度度量
总的来说，和标称属性是类似的，但是情况稍微复杂一点。要分成对称和非对称2种形式。
对称二元属性：对象的所有属性都是一样重要的。这就和标称属性类似了，用所有具有相同属性值的属性个数除总的属性数。公式和标称属性一致。
sim(O1, O2) = (m1 + m2) / n m1和m2是O1和O2中全为0或者全为1的属性数。
非对称二元属性：所谓非对称，是说我们只关心“正匹配”的情况，也就是只关心两个对象属性中都是1的情况。
sim(O1, O2) = m1 / n
Jaccard系数：两个集合的交比两个集合的并
数值属性相似度度量
“闵可夫斯基”距离，也叫Lp范数。
切比雪夫距离：使用的时候，维度起码为3以上；两个点之间的距离定义为各坐标数值差的最大值。
曼哈顿距离。
欧氏距离。
加权的欧式距离。对不同属性设置不同的权重，各权重之和为1，这样依然可以保证相似度的统一性。
序数属性相似度度量
假设序列用1，2，3……来表示，通过以下公式将每个整数型的属性值映射到[0.0, 1.0]的区间上。
y = x − 1 / m − 1
混合类型属性相似度度量
前面情况都是数据库中的数据相对类型比较统一，但是很多时候，实际工作中遇到的情况却并非如此。我们遇到的一组数据可能拥有多种类型的属性，也就是混合类型属性。
sim(O1, O2) = (从1到m fi*sim(O1i, O2i)) / (从1到m fi)
sim(O1i, O2i)表示2个对象在属性i上的相似度。
对于fi呢？这样计算：
- 假如O1，O2中有一个对象不具有属性i，则fi = 0。
- 假如O1，O2的属性i是非对称二元属性（请看上面对于二元属性部分的讲解），且对应的属性值都是0，则fi = 0。
- 除了以上2种情况，fi=1。
余弦相似性
针对文档数据的，特殊的相似度测量方法。
汉明距离
可以描述为将同等长度的字符串由其中一个变换到另一个的最小替换次数。如将a(11100)变换为b(00010)，则其距离为4，汉明距离主要是为了解决在通信中数据传输时，改变的二进制位数，也称为信号距离。
相关距离
相关距离是用来衡量随机变量X、Y之间的相关程度的一种方法，取值为[-1,1]，且系数越大，相关度越高。当X、Y线性相关时，若为正线性相关时则为1，相关距离 = 1 - 相关系数。
最近邻搜索问题
计算所有数据之间的距离，比较大小即可。但随着数据量的增大以及数据维度的提高，这种方法就很难在现实中应用了，因为效率会非常低。解决此类问题的思路基本分为两类：
- 通过构建索引，快速排除与查询相关度不大的数据；
- 通过降维的方法，对数据条目先降维，再查询。
前者主要是为了解决数据量过大的问题，比较常见的有我们熟知的二叉搜索树，Merkel tree，B-tree，quad-tree等；后者主要是为了解决维度过大的问题，比较常见的方法有LSH（局部敏感哈希）。
Kd-tree
Kd-tree就是一种对多维欧式空间分割，从而构建的索引，解决数据量过大的问题。
KD树更加适用于实例数量远大于空间维度的KNN搜索，如果实例的空间维度与实例个数差不多时，它的效率基于等于线性扫描。
LSH
在信息检索，数据挖掘以及推荐系统等应用中，我们经常会遇到的一个问题就是面临着海量的高维数据，查找最近邻。如果使用线性查找，那么对于低维数据效率尚可，而对于高维数据，就显得非常耗时了。为了解决这样的问题，人们设计了一种特殊的hash函数，使得2个相似度很高的数据以较高的概率映射成同一个hash值，而令2个相似度很低的数据以极低的概率映射成同一个hash值。我们把这样的函数，叫做LSH（局部敏感哈希）。LSH最根本的作用，就是能高效处理海量高维数据的最近邻问题。
定义
我们将这样的一族hash函数 H={h: S→U}称为是(r1,r2,p1,p2)敏感的，如果对于任意H中的函数h，满足以下2个条件：
- 如果d(O1,O2) < r1，那么Pr[h(O1) = h(O2)] ≥ p1；
- 如果d(O1,O2) > r2，那么Pr[h(O1) = h(O2)] ≤ p2。
表示当足够相似时，映射为同一hash值的概率足够大；而足够不相似时，映射为同一hash值的概率足够小。
针对不同的相似度测量方法，局部敏感哈希的算法设计也不同。
无论是哪种LSH，其实说白了，都是将高维数据降维到低维数据，同时，还能在一定程度上，保持原始数据的相似度不变。LSH不是确定性的，而是概率性的，也就是说有一定的概率导致原本很相似的数据映射成2个不同的hash值，或者原本不相似的数据映射成同一hash值。这是高维数据降维过程中所不能避免的（因为降维势必会造成某种程度上数据的失真），不过好在LSH的设计能够通过相应的参数控制出现这种错误的概率，这也是LSH为什么被广泛应用的原因。
min-hash：使用Jaccard系数度量数据相似度
1.hash函数的选择
Jaccard系数主要用来解决的是非对称二元属性相似度的度量问题，常用的场景是度量2个集合之间的相似度。即2个集合的交比2个集合的并。
维度高的input matrixi通过MinHash转换成维度低的signature matrix。
为什么这个是针对Jacard相似度呢？
因为对于签名矩阵的任意一行，它的两列元素相同的概率是x / n，其中x代表这两列所对应的文档所拥有的公共词项的数目。而x / n也就是这两个文档的Jaccard系数。
2.构造LSH函数族
虽然经过降维，暗示没有解决找原始问题，你需要遍历所有的集合对才能找到相似的集合对。所以我们需要将相似的集合聚集在一起，减少查找范围。
- 将signature matrix水平分割成一些区块（记为band），每个band包含了signature matrix中的r行。
- 对每个band计算hash值，得到每个band的hash值。
- 如果某两个文档的，同一水平方向上的band，映射成了同一hash值，我们就将这两个文档映射到同一个hash bucket中，也就是认为这两个文档是足够相近的。
计算出两个文档被映射到同一个hash bucket中的概率。每个band有一个hash函数（这个hash函数不易冲突），然后将band中的r行通过hash映射，映射到同一值表示这两个文档在这个band中是相同的。
b个band至少有一个相同的概率是1−(1−s^r)^b。这样的方法称为AND then OR，它是先要求每个band的所有对应元素必须都相同，再要求多个band中至少有一个相同。符合这两条，才能发生hash碰撞。
P-stable hash：使用欧氏距离度量数据相似度
聚类算法
- K-means作为聚类中最基本的算法，基于距离来聚类；DBSCAN是基于密度来进行聚类。
- K-means需要指定簇的个数作为参数，DBSCAN不需要事先知道要形成的簇类的数量，DBSCAN自动确定簇个数。
- dbscan受MinPts和eps取值很大关系，kmeans受初值影响较大。
- 与K-means方法相比，DBSCAN可以发现任意形状的簇类。DBSCAN可以处理不同大小和不同形状的簇，K-means很难处理非球形的簇和不同形状的簇。
- K-means可以用于稀疏的高纬数据，如文档数据。DBSCAN则不能很好反映高维数据。
- K-means可以发现不是明显分离的簇，即便簇有重叠也可以发现，但是DBSCAN会合并有重叠的簇。
基于划分的聚类算法
K-means算法
如何正确使用「K均值聚类」？ K-means、K-means ++、K-modes和K-prototype聚类算法简述 附Python代码
- 输入数据一般需要做缩放，如标准化。
- 如果输入数据的变量类型不同，部分是数值型（numerical），部分是分类变量（categorical），需要做特别处理。方法1是将分类变量转化为数值型，但缺点在于如果使用独热编码（one hot encoding）可能会导致数据维度大幅度上升，如果使用标签编码（label encoding）无法很好的处理数据中的顺序（order）。方法2是对于数值型变量和分类变量分开处理，并将结果结合起来，具体可以参考Python的实现，如K-mode和K-prototype。
- 输出结果非固定，多次运行结果可能不同。
基于层次的聚类算法
BIRCH算法
基于密度的聚类算法
DBSCAN(Density-Based Spatial Clustering of Applications with Noise)算法、OPTICS(Ordering Points To Identify the Clustering Structure)算法
基于网格的聚类算法
基于模型的聚类算法
高斯混合模型(GMM)
参考
LSH(Locality Sensitive Hashing)原理与实现