本总结是是个人为防止遗忘而作, 不得转载和商用
相似度 / 距离计算方法总结
既然聚类思路的核心是度量样本间的内在相似性, 那相似度 / 距离的计算方法是什么呢?
首先先给出个汇总图, 然后在解释, 汇总图如下:
解释:
闵可夫斯基距离 / 欧氏距离:
对于两个点 (x1,y1),(x2,y2), 他们的距离是 ((x2-x1)2 + (y2-y1)2)1/2
为了拓展为 n 维, 就定义向量 x=(x1,y1, z1, ...), 不过为了方便举例就用 3 维来说明吧:
两个三维的点 x=(x1,x2, x3),y=(y1, y2, y3)
于是它们的距离就是 ((x1-y1)2+ (x2-y2)2 + (x3-y3)2)1/2
PS: 这就是二范式 ||x -y||2 , 即: 里面都是平方, 外面都是平方根
那如果里面都是 3 次方, 外面是 3 次方根呢? 或者里面都是 p 次方, 外面是 p 次方根呢? 也可以吧, 反正就是度量度量两点间的距离
于是把上面的汇总下就是: 闵可夫斯基距离 / 欧氏距离的公式
PS: 如果 p=2 时是欧氏距离, p 为某一个值时是闵可夫斯基距离, p 为时是切比雪夫距离
杰卡德相似系数:
有时有这样的情况: A 和 B 是两个集合
比如: A 喜欢看某些电影, B 喜欢看某些电影我们想度量 A 和 B 之间的相似度
这时就用杰卡德相似系数了
推荐系统可考虑选择这个
余弦相似度:
如下图所示:
有些时候会用 A 和 B 之间张成的的角的大小来度量两者的相似性
文本相似度可考虑选择这个
Pearson 相似系数:
就是求两个随机变量的相关系数, 即: 协方差除上标准差
因为相关系数的绝对值小于等于 1,cov(X, Y) 可以认为是标准化的协方差, 而协方差又是线性关系的一种度量所以这个可以度量两者的相似性
相对熵 (K||L 距离 / 散度):
这个在最大熵模型中已经解释了, 不懂的看我的总结
Hellinger 距离:
令α= 0 的话, 就有下面的推导
令α= ±1 时, 这个就是 K-L 散度
Jaccard 相似度的由来
记: R(u) 是给用户 u 作出的推荐列表, 而 T(u) 是用户在测试集上真正的行为列表
于是有如下准确率和召回率:
而 Jaccard 相似度就是把准确率和召回率做了个合并, 成为:
Jaccard 系数特点和用途:
各个特征间是均一无权重的
网页去重 / 考试防作弊系统 / 论文抄袭检查
余弦相似度与 Pearson 相似系数:
首先, 余弦相似度可以做如下变换:
这时, 如果令 Pearson 中的μx 和μy 都等于 0 的话, 那 Pearson 相似系数的公式就是余弦相似度的公式
所以 Pearson 相关系数即将 xy 坐标向量各自平移到原点后的夹角余弦!
这即解释了为何文档间求距离使用夹角余弦因为这一物理量表征了文档去均值化后的随机向量间相关系数
最后:
在实际应用中, 根据情况选择一种距离求出后, 对距离取分之一, 就是相似度, 即: 距离和相似度互为倒数
代码 (源自邹博老师)
例子
已知:
某影院收集了 N 个用户对于 M 个电影的观影记录每个用户一行, 第 i 行记录形式为:
< 用户 ID>\t < 电影 1>;< 电影 2>;
如:
- 1347842 44
- 1347847 30;44
- 134790 28;30
- ....
已知莫愁的观影记录为: 84,14, 90,91, 29, 21, 9, 44,24, 89, 8, 42, 41, 40,25, 37, 30, 16, 97, 52, 62,56,80, 83, 36,26, 73, 64, 32, 27, 67, 65, 79, 87, 17
求:
找出与莫愁最匹配的前 15 名用户
解 (其实更贴近的说法是思考过程):
令 A = 莫愁的观影记录集合; B = 某影院收集了 N 个用户对于 M 个电影的观影记录
1, 第一步是想办法求出 A 与 B 的相似度
而对比下上面那些相似度发现使用杰卡德相似度会十分方便, 不过有没有其他相似度可以使用?
我们作如下思考: 对于每一个用户, 我们都可以为其创建一个默认的全为 0 的向量, 向量的长度是电影数量 M 然后对该向量做此操作: 凡是用户看过的电影, 向量中对应该电影的那个元素的值为 1, 反之为 0 为了方便之后的说明, 我们假定两个用户莫愁和用户 X 的电影向量 M1 和 Mx 如下:
- M1 =[0010100101101....0101010]M
- Mx = [1001010010110....1011010]M
这样看来, 使用余弦相似度好像也不错
而如果把 M1 和 Mx 的那些值看做是坐标点的话, 就能使用欧氏距离
所以说, 在实践层面上面的相似度都是可以使用的
2, 在第一步中有: 对每一个用户都存一个长度为 M 的向量但有必要一定要存一个这么长的向量吗? 还是向量 M1 和 Mx:
- M1= [0010100101101....0101010]M
- Mx= [1001010010110....1011010]M
对余弦相似度来说 M1T.Mx 和 ||M1||||Mx|| 代表什么?
M1T.Mx 代表:
||M1|| 代表:
, 即莫愁看过的电影的数量
||Mx|| 同上
而 M1 和 Mx 都是只有 0 和 1 两个元素的向量啊, 如果 M1 的第 i 个元素和 Mx 的第 i 个元素不同时为 1 的话, M1T.Mx = 0, 反之 M1T.Mx = 1
即: M1T.Mx 就是看看莫愁和用户 x 看过的电影中有多少个一样的!
于是, 如果使用余弦相似度的话, 我们就没必须把 M1 和 Mx 在程序中写出来然后再去做, 只需要统计下相同的数目以及每个人看过几个电影就可以了
因为本章仅仅总结相似度, 所以这个题就到底为止了
PS:电影见的相似度可以这么思考: 对于用户 1,看过电影 1,2,3,.... 对于用户 2,看过电影 1,3,4,.... 其他用户.... 上面是用户对电影的数据,下面我们改变下统计方式,根据上面的数据统计出电影对用户的数据,即: 看过电影 1 的用户有:用户 1,用户 2, 用户 5,.... 其他电影.... 然后把这个数据代入刚才的相似度计算中就可以了。 |
到底哪个相似度好啊
看了上面的例子, 相信你会想这个问题
在回答这个问题之前先看几幅图
下面几幅图是刚才例子中采取不同的标准求得的相似度的情况
第一列是用户 ID, 第二列是某用户看过的电影中与莫愁看过的电影相同的数目, 第三列是相似度, 越接近行首相似程度越高
第一行: 莫愁和自己的相似度是 1, 排在行首
第二行: 用户 305344 看了 95 个电影, 然后这 95 个电影中正好包含了莫愁看的那 35 个
篮框行: 用户 1114324 看了 44 个电影, 然后这 22 个电影中正好包含了莫愁看的那 35 个
这样判断没问题
在余弦相似度中排在第七位的篮框行在这里排在了第二位, 而刚才排在第二位的却排在了第三位, 为什么呢?
因为 Jaccard 是这么想: 莫愁看了 35 个, 用户 1114324 看了 44 个, 他们中有 22 个相同的, 这个 22 在 35 中占了比例很高, 在 44 中占得比例也高, 所以我认为 1114324 与莫愁最相似
所以, 那种相似度都有它的解释, 没有说哪个一定好哪个一定坏, 这个最终还要看场合
来源: http://lib.csdn.net/article/machinelearning/37043