最近在学习Python和C的同时也开始看有关人工智能方面的应用算法。从豆瓣上看到一本不错的书——《集体智慧编程》（Programming Collective Intelligence）。这本书好就好在它用了非常实际的案例去介绍业界目前比较流行的解决方案，而不是学院派地从算法分析入手。看起来挺快餐的吧，但是这非常适合现代开发者的快节奏步伐，现实中我们没有时间去慢慢从数学学起。然而学习数学部分也有好处，至少知道了这些原理后可以帮助我们消化这些算法。而且其实这些算法看起来玄乎，但事实上是从一些简单的（可被理解的）数学模型上转化而来。下面我打算简单地将我的学习记录一下，方便查阅并和大家分享。虽然我标题上是写协作过滤，但事实上这些数学模型可以用到其他地方的。将要涉及到的数学模型有：欧几里德距离、皮尔逊相关度、曼哈顿距离、Jaccard系数、余弦相似度等。
欧几里德距离（Euclidean Distance）
就是我们在高中时学过的在坐标系里求两点距离的方法。那再扩展一下，此法不仅在欧几里德空间里可以用，在任何内积空间都可以使用。公式是：
[math]D(p,q)=\sqrt{\sum_{i=1}^{n}(p_{i}-q_{i})^{2}},[/math]
where [mathi]p=(p_{1},p_{2},\ldots,p_{n})[/mathi] and [mathi]q=(q_{1},q_{2},\ldots,q_{n})[/mathi]
这个模型能够很准确地求得两点的距离，但是如果放到实际问题中，可能会构成一些问题。比如说我们在豆瓣里给电影打分，如果豆瓣给我们匹配口味最接近的用户。做法是在电影构成的空间里，将用户根据对不同电影的分数分散在空间里。然后用这个公式算出与我距离最近的用户。这样初看应该是个蛮完美的方案，但是此法没有考虑到不同用户评分的严格度是不一样的。比如有的用户对喜欢的电影打5分，但是严格的用户可能只会给4分，这样一来，本来口味相近的用户就会因此而被拉远。即此法不能修正“夸大分值”（Grade Inflation）。但是并不是说用这个方法就不能用，其实在应用中它的效果还是很不错的，只是要在恰当的地方运用。
曼哈顿距离（Taxicab Geometry）
这个数学模型有很多名字，也有被叫做方格线距离或计程车几何的。相对于欧几里德距离（两点的直线距离），曼哈顿距离则是这两点在直角坐标系里构成的方形的X和Y轴的长度之和。公式：
[math]D(p,q)=\|p-q\|=\sum_{i=1}^{n}|p_{i}-q_{i}|,[/math]
where [mathi]p=(p_{1},p_{2},\ldots,p_{n})[/mathi] and [mathi]q=(q_{1},q_{2},\ldots,q_{n})[/mathi]
这个方法看似和欧几里德距离很像，但是相比之下有个要点要清楚，就是曼哈顿距离是依赖于空间的转度的。试想空间中的两点随着空间按原点旋转，根据旋转后的新位置算得的曼哈顿距离是不同的，而欧几里德距离在这种情况下是不变的。
Jaccard系数（Jaccard Index）
也被叫做Jaccard相似度系数。在统计学中用以比较两个样本的相似度，算法是两个样本的交集比上两个样本的并集：
[math]J(A,B)=\frac{|A\cap B|}{|A\cup B|}[/math]
结果会在0–1之间，越大越相似。
余弦相似度（Cosine similarity）和Tanimoto系数（Tanimoto coefficient）
我在写这篇博客之前看到余弦相似度和Tanimoto系数将Jaccard系数扩展出了二进制属性。我也顺带提一下，余弦相似度被很广泛得用在文本挖掘中。其实余弦相似度是利用了向量空间里的两个向量夹角的余弦值（cosine），从-1到1之间。-1表示两个向量相反，0表示独立无关，1表示完全一样。如果放在语义挖掘中就可以算两个词的关系了，当然这只是一种应用。Tanimoto系数则与之相似，不过结果范围在-1/3到1之间。来看一下公式，
余弦相似度 ：
[math]\cos(\theta)=\frac{A\cdot B}{\|A\|\|B\|}[/math]
Tanimoto系数：
[math]T(A,B)=\frac{A\cdot B}{\|A\|^{2}+\|B\|^{2}-A\cdot B}[/math]
皮尔逊相关度（Pearson product-moment correlation coefficient）
这个数学模型应该算是提到的这几个里面最复杂的了。根据其定义，皮尔逊相关度是两变量的协方差和其标准差之积的比。协方差是用来衡量两个变量相互改变的程度的。标准差是用来衡量一个变量的分散程度的。而皮尔逊相关度就是如果两个变量的变化趋于一致，其值就是各正直，最大为1；如果两个变量的变化趋于相反，则其值为负最小为-1；零的时候也就是他们统计独立的时候。此属性恰好就克服了我在欧几里德距离部分提到的一个问题，也就是说皮尔逊相关度可以修正“夸大分值”，放进之前的那个例子而言，如果将打分严格和不严格但是品味相似的用户比较时，虽然欧几里德距离得不到期望的结果，但是皮尔逊相关度就可以分辨出两人的变化度是趋于一致的，就能辨别出。
皮尔逊原公式写出来感觉挺简单，但是不太适合写程序，下面我就来从定义出发，化到可以用来做程序的表达式。
由定义：
[math]\rho_{X,Y}=\frac{\mathrm{cov}(X,Y)}{\sigma_{X}\sigma_{Y}}=\frac{E[(X-\mu_{X})(Y-\mu_{Y})]}{\sigma_{X}\sigma_{Y}}[/math]
其中，
[math]\mu_{X}=E(X),\mu_{Y}=E(Y)[/math]
[math]\sigma_{X}=\sqrt{E(X^{2})-(E(X))^{2}},\sigma_{Y}=\sqrt{E(Y^{2})-(E(Y))^{2}}[/math]
[math]E[(X-\mu_{X})(Y-\mu_{Y})]=E(XY)-\mu_{X}\mu_{Y}[/math]
所以得到：
[math]\rho_{X,Y}=\frac{E(XY)-E(X)E(Y)}{\sqrt{[E(X^{2})-(E(X))^{2}][E(Y^{2})-(E(Y))^{2}]}}[/math]
又因为
[math]E(X)=\sum_{i=1}^{n}(p_{i}x_{i}),p=\frac{1}{N}[/math]
[mathi]E(Y)[/mathi]同理，得到：
[math]\rho_{X,Y}=\frac{\frac{\sum(XY)}{N}-\frac{\sum(X)}{N}\cdot\frac{\sum(Y)}{N}}{\sqrt{[\frac{\sum X^{2}}{N}-(\frac{\sum X}{N})^{2}][\frac{\sum Y^{2}}{N}-(\frac{\sum Y}{N})^{2}]}}[/math]
最后消去N：
[math]\rho_{X,Y}=\frac{\sum(XY)-\frac{\sum X\sum Y}{N}}{\sqrt{(\sum X^{2}-\frac{(\sum X)^{2}}{N})(\sum Y^{2}-\frac{(\sum Y)^{2}}{N})}}[/math]
这样一来就可以用程序实现了，毕竟只是需要SUM和SQRT。
–EOF–
