用关系型数据结构实现itembased算法——Hive
本文讨论我们在关联关系挖掘中最常用的算法Itembased算法的实现。Itembased基本算法思路
我们考虑如下数据场景：
假设我们面对的是一个根据文章的主题词对文章与文章之间的相关性做计算的问题。
通过如下数据表示：
文章1：词1:score1，词2:score2，词3:score3，词4:score4......
......
......
我们把每篇文章看做一个item，目的是通过分析他们词之间的关系来计算每篇文章(item)之间的相似性
一种方法是，我们把每篇文章都看成一个N维的向量(N=所有词的个数)，文章在对应维度的值就是文章中包含词的那个score。
所有的文章表示成一个M*N的矩阵，M为文章的数
文章词1词2词3词4词5词6……文章1score1score2score3score400 …….
每篇文章表示成一个向量之后，就可以用数学中计算向量夹角的方式计算每两篇文章的相似性(就是向量夹角的cos值)。
计算结果形式如下：
left_itemright_itemsimilarity文章1文章K0.8…… 其中第三个字段就是左item，和右item这两个向量的夹角的cos值。
实现方法
从上述介绍中看，假如我们有M篇文章，要两两计算文章的相似性，时间复杂度为O(M*M).
此外，计算两个向量夹角时，根据公式：cos<a,b>=(ab的内积)/(|a||b|)，可以得到复杂度为O(N)
因此，整个计算过程的复杂度为O(N*M*M)。
仔细看下这个过程，我们发现，在不同向量之间求cos的时候，只有内积是需要重新计算的，而两个向量的模不需要重新计算。同时计算内积时也不需要考虑全部的维度，而只需要考虑两个向量在N个维度中，都不为0的维度即可，向量的模的计算也不需要那些为0的维度。
因此这样的情况下，十分适合用关系型的数据表达上述结构。如下：
table_1
文章词score文章1词1score1文章1词2score2文章1词3score3文章1词4score4文章2 ……
虽然这种方法比由文章做key，词和score做value的方式占用更多的空间(每篇文章重复了多次)，但却十分利于利用关系型的方式来计算。
如下：
首先，我们计算每个向量的模，根据模的计算公式容易得到：
create table table_modasselect 文章,sqrt(sum(score*score)) as modfromtable_1 group by 文章;然后需要计算每两个向量之间的内积，这里的关键是：
没有维度交集的两个向量内积为0，也不需要计算，
而且向量和自身不需要求内积。
create table table_productasselect t1.文章 as l_文章,t2.文章 as r_文章,sum(t1.score*t2.score) as productfromtable_1 t1 jointable_1 t2 on(t1.词=t2.词)wheret1.文章<>t2.文章 group by t1.文章,t2.文章;
现在内积有了，模也有了，最后一步cos的计算就很简单了。
create table table_similarityasselect p.l_文章 as left_item,p.r_文章 as right_item,p.product/(m1.mod*m2.mod) as similarityfromtable_product p jointable_mod m1 on (p.l_文章=m1.文章) jointable_mod m2 on (p.r_文章=m2.文章);
这样给定一篇文章，我们就可以知道与其相似的文章有哪些，以及相似度是多少，并且根据相似度排序。
select right_item,similarityfromtable_similaritywhere l_item='文章1'order by similarity desc;
是不是很方便？
结语：
通过关系型的方式实现Itembased的方法最大的好处就是简单，只需要了解SQL的逻辑就可以。
不好的地方就是同一篇文章需要在每个词中重复出现，这本身也是关系型的特点。
页:
[1]