布尔矩阵与个性化推荐系统(原创）

经常上当当网购书的朋友都知道，当选择了几本书，放入购物车中，然后系统就会推荐你，购买了这两本书的用户还购买了什么书，淘宝等购物网站也有类似的功能。 在推荐系统中还有一个经典的案例，具体我记得不太清楚了，好像是沃尔玛的啤酒和尿布的案例，也是各大BI厂商的经常提起的一个案例，自动推荐系统现在已经是各大电子商务网站必不可少的营销方式了。
   另一个类似的应用就是好友推荐系统，经常使用校内的朋友知道，当你加了好多同学后，
系统会自动为你推荐，你很可能认识某某某。而且推荐的还算比较准，至少针对我的推荐是比较准确的。
   曾经想过这些东西，也查过资料，但是一查就扯远了，都是什么BI等各大厂商炒作出来的名词。
最近，由于在研究报警关联分析和过滤方面的算法，用到了很多布尔代数和矩阵方面的知识。周末没什么事情，翻了翻Oracle的大厚本《Oracle专家编程》，看到索引聚集表，发现这个和搜索引擎中常用算法中的倒排序有些相像。突然想起了javaeye上流传的那个迅雷的变态的面试还是笔试题（大概内容5000观看电影纪录，一亿的用户记录，如何有效的合并，如果快速找出看了5个影片的用户）。想了想思路，能否借鉴Oracle的索引聚集表或矩阵等数学模型解决呢？尝试着是否可以用矩阵的数据模型，理论上好像可行，但是实际上，还是空间和效率的问题。
我的思路是这样的，建立一个矩阵，横坐标为影片ID，纵坐标为用户ID，这样就构成一个二维的矩阵，（x,y）的值为1或0，代表着X用户看了影片Y或没看。
但是算了下，这个矩阵的大小也是非常庞大的，光靠内存看样是不行了。
拿笔画了几下，怎么能找出看了五个以上电影的用户呢?只能是在影片集合里每次5个不同的影片，然后按这五个影片ID取出5列，全部进行&操作，结果为1的，就是看了五个，但是这个方法效率问题有问题，而且也不容易实现。
这个问题没解决，但是确在这个矩阵上发现了一个规律。
取出两个影片，可以很快的计算出看了这两个影片的用户ID。例如去影片Y1，Y2
他们对应的列进行&操作，结果列中，值为1 的下标为同时看过这两个影片的用户的ID。
找到看了这两个影片用户的ID的同时，又很容易找到他们还看了哪些影片。通过用户ID，找到对应的行，这一行中为1 的值，则代表这个用户看过的影片了。
知道这些，再运用点概率方面的知识，不就是个影片推荐系统吗，其他的推荐系统不也可以用类似的方式解决了吗？
是否能用矩阵解决推荐系统的问题。出于好奇，就将这个问题深入研究了一下，我的周末就这样没有了，呵呵。
假设有商品进行如下编号
0大米，1白面，2豆油，3巧克力，4洗发水，5沙发，6酱油，7方便面，8桌子，9椅子，10沙发垫，11洗面奶，12卫生纸，13火腿肠，14可乐
现在建立一个矩阵。（0，0）为顶点，为了方便商品和客户编号都从0开始的整数。
横向15个，为产品编号。
000000000000000
000000000100000
010000000000000
000000000000000
000000000000000

横坐标为为顾客的ID，纵坐标为产品的ID，例如上图中
（1,9）的值为1，代表了编号为1的顾客购买了编号为9的这个商品。
（2,1）的值为1，代表了编号为1的顾客购买了编号为1的这个产品。

假设通过历史数据训练后的矩阵如下所示，这是只是为了说明问题，如果真正应用，这个矩阵可能非常大的。    

                 
000000000000000
111000000000100
111000000010000
111000000010000
010000000000000
                       

历史数据建立好以后，系统开始正式运行了。
当你选择了，大米和白面这两个商品后（编号为0和1），系统开始进行推荐运算，如果运算的呢？
取大米和白面这两个列，第0列，和第1列。
如下
大米 白面     大米&白面
0      0              0
1      1              1
1      1              1
1      1              1
0      1              0                            
然后进行&（and）运算得到右边的的列（大米&白面） ，第1行，第2行，第3行的值都唯一（下标从第0行开始计算），则代表这个编号为1，2，3的顾客曾经同时购买过大米和白面。
得到这些信息后，可以推测，有相同购买记录的人购买行为据有一定的相似性。只要能知道顾客1，2，3还购买了其他的什么产品，然后按购买的比率进行统计下，就可以有效的进行推荐了。
怎么求顾客1，2，3还购买了其他的什么产品呢？全在矩阵中表示着呢。 矩阵的每一行代表每个顾客购买的产品记录。1，2，3购买的产品记录如下。
111000000000100
111000000010000
111000000010000
设这3行为 T1,T2,T3，那么T=T1|T2|T3 ，可以知道T代表这三个人都购买了哪些产品。
上面的T = 111000000010100 ，对照产品编号表，这三个顾客购买了大米0，白面1，
豆油2，卫生纸12，沙发垫10。你已经选择了大米和白面那么去除大米和白面后。
T = 001000000010100
那么豆油，卫生纸，沙发垫，都可以作为推荐的产品。
但是这样的推荐有点不可靠，不能每个人都购买趋向都相同。所以必须利用一些概率的知识来解决此问题。
现在已经得到豆油2，卫生纸12，沙发10垫了等都是可以推荐的商品了。
这些数据来源于3个顾客的购买记录。
那么统计一下，在相同购买记录中（大米，白面）的这些用户（1，2，3）购买豆油，卫生纸，沙发垫的百分比是多少，然后根据这个百分比，把百分比高的作为首要推荐产品，就更有效了。
111000000000100
111000000010000
111000000010000
                                                                
豆油（2列）上，所有的位置都为1 ，可以认为是100%的够购买过豆油。
沙发垫（10）上，3个中两个位置为1，可以认为都买沙发垫的占67%。
卫生纸（12）上，只有一个1，那么可以认为购买此物品的占33%。

那么给出了最终的推荐结果
强烈推荐：豆油
首要推荐：沙发垫
次要推荐：卫生纸

这样一个简单的商品自动推荐系统的雏形就出来了，这只是个简单的想法，应该还有很多地方不成熟，与真实的商用系统相差应该比较遥远，只是希望能起到抛砖引玉的作用。    

再来看看好友推荐系统，横坐标，纵坐标都为用户的ID，是好友的，就在相应的位置标志为1，知道这个人的所有好友，然后计算所有好友的好友，他们中间的一些共同的好友可能就是你认识的。一般取20%-30%（我估计的数字）以上应该就可以了，推荐系统，应为几乎不存在你所有的好友都是其中的一个人的好友。
这个好友关系组成的矩阵，又可以抽象为图论中的一个有向图。那么另一个功能，我怎么能认识他，例如我通过谁可以认识奥巴马？通过好友的好友去与奥巴马建立关系，可以抽象为在这儿图上两点之间的最短路径问题，理论上好像是可以，没有去深入研究，应该不会这么简单的，毕竟六度空间不是那么容易实现的。