基于Tag的相关度计算
原文地址：http://www.blogkid.net/archives/2046.html
最近在思考相似度推荐的算法，想过不少主意，但觉得最省事的莫过于用Lucene或Sphinx之类的全文检索软件，把每个个体的tag信息放在索引中，用的时候直接去查。搜索引擎可以搞定计算TF/IDF、计算相关性之类的脏活儿，直接返回相关的内容，可谓省时省力。
不过还是我忍不住自己想了一下，感觉也还算简单，今天写一些自己的心得，算是抛一块砖头。相似度计算可以用余弦定理来算。简单来说，我们可以为一个个体找到一组描述其特征的值，比如描述苹果、梨、香蕉，可能有：
苹果： 球形 甜味 红色 多汁
梨： 球形 甜味 黄色 多汁
香蕉： 长形 甜味 黄色
把这些特征编个号，排一下，就可以把这些特征数字化了：
苹果： 1, 2, 3 , 4
梨： 1, 2, 5 , 4
香蕉：6 , 2 , 5
可以把上面每个看做是一个描述该个体特征的向量，这里有6个特征，于是向量是六维的：
苹果： [ 1, 1, 1, 1, 0, 0]
梨： [ 1 , 1, 0, 1, 1, 0 ]
香蕉：[0 , 1 , 0 , 0, 1 , 1]
通过余弦定理计算两两夹角（余弦定理还记得吧，cosA = 向量内积/向量模的积）：
cos (苹果^梨) = 3/4 = 0.75
cos(梨^香蕉) = 2/(2*1.732) = 0.577
cos(苹果^香蕉) = 1/(2*1.732) = 0.289
两个向量夹角越小，说明二者相似程度越高。相应地，cos的值就越大。所以在这个简单的计算中，苹果和梨的相似程度要大于梨和香蕉，梨和香蕉的相似程度要大于苹果和香蕉。
举这样的例子其实不太适合，因为对于这些有明显特征的东西如苹果、梨，有更好的计算办法。但如果换成是一个blog上的文章，采用tag来提取特征向量方式会非常合适。同时这个例子中并没有加入对于词频的分析，也就是说对每个特征，给的权重都是一样的，实际上不该如此。
要计算词频并与权重相关联，就需要祭出TF/IDF算法，吴军写过一个详细的介绍。某一个特征的权重=ln(D/Dw)，其中D是个体总数，Dw是这个特征在总数中出现的次数。
回到刚才的例子，6个特征的权重分别是：
球形： ln(3/2) = 0.405
甜味： ln(3/3) = 0
红色： ln(3/1) = 1.099
多汁： ln(3/2) = 0.405
黄色： ln(3/2) = 0.405
长形： ln(3/1) = 1.099
计算权重之后，相应特征向量为：
苹果： [ 0.405, 0, 1.099, 0.405, 0, 0]
梨： [0.405 ,0 , 0 , 0.405 , 0.405, 0 ]
香蕉：[0 , 0 , 0 , 0, 0.405 , 1.099]
再求夹角：
cos (苹果^梨) = 0.377
cos(梨^香蕉) = 0.200
cos(苹果^香蕉) = 0
可能你对苹果和香蕉相关度变成0觉得很难理解，他俩明明都有“甜味”啊。但别忘了，所有的样本都是有“甜味”的水果，所以在这种情况下，有“甜味”已经不是需要考虑的特征了。
写到后来计算对数累死了，以后这种活儿，还是该直接交给搜索引擎去干。当然，我们得明白其中的道理，这样才能更好地控制它。
今天又仔细看了看Google吴军的几篇文章（1 2 3），深入浅出的讲解，举重若轻的功力，实在令人佩服啊。
有深度
余弦定理？
有意思！
?……?
同是张磊
还大你一岁
完全不同的轨迹啊
叫这名字的，确实太多了
发现不少朋友们收藏了这文章
还算容易看懂吧
第一次能够比较认真地去看一些技术性文章…觉得这个余弦定理蛮有意思的。当我看到“向量内积/向量模的积”时，豁然开朗，囧
好久没看数学，好像都忘了……囧死！！
不过我要实现文章的自动分类,单纯这些似乎还是不够,怎么给每个词设置权重似乎也是个问题.
@spacelee
如果不用tf/idf的算法，计算权重必然得找到别的办法。或者人肉？
sphinx如何查询某个词汇在某一篇文章里面出现的次数呢,好像只能查找单个词汇在所有索引文章里面出现的次数
@spacelee
sphinx没有提供这种查法，但对单个词的定它的权重，就是通过tf/idf。只不过没有提供一个查询接口而已。
站长是编程高手呀！！！
@watches
感兴趣而已