Sunday, February 21st, 2010
首先，要了解关联规则的几个概念，定义N为总事务数，N(A)、N(B)分别为项集A、项集B出现的次数，N(AB)为项集A、项集B同时出现的次数，A、B为不相交项集A∩B=Ø，规则A→B表示由A推到B：
支持度（Support）：
支持度是一种重要度量，支持度低的规则很可能是偶然现象，对推荐意义不大，另外支持度是数据剪枝的一个重要依据。
置信度（Confidence）：
置信度，字面上的解释就是这个规则到底有多可信，对于给定的规则A→B，置信度越高，B出现在包含A的事务中的概率越高。
提升度（Lift）：
Support(A→B)其实就是AB的联合概率P(AB)，Support(A) 、 Support(B)分别为A、B的概率估计P(A)、P(B)，如果A、B相互独立，则P(AB) = P(A) × P(B)，所以只有 Lift > 1 才表示A、B正相关，且越大越好。
为什么要引入提升度的概念呢？还是拿歌曲来做例子，比如歌曲A、歌曲C为小众歌曲，歌曲B为口水歌，共有10万个用户，有200个人听过歌曲A，这200个人里面有60个听过口水歌B，有40个人听过歌曲C，同时听过歌曲C的人数是300，听过口水歌B的人为50000，那么Confidence(A→B) = 0.3，Confidence(A→C) = 0.2，从置信度来看貌似A和B更相关，但是10W人里面有5W听过歌曲B，说明有一半的用户都喜欢歌曲B，但听过歌曲A的人里面只有30%的人喜欢歌曲B，很明显歌曲A和歌曲B负相关，计算Lift(A→B) = 0.6，小于1，负相关，Lift(A→C) = 100，远大于1，正相关。
当然，还有一些其他的度量因子，可自行参阅其他文档。
可以进入正题了，我们要实验的是一个文学类的网站数据，数据格式如下：
用户ID 图书ID
表示此用户阅读过该图书，我们首先要解决的问题是：喜欢图书A的用户还喜欢其他哪些图书？（图书之间的相关性）
推荐流程：
数据清理：对用户和图书分别计数，过滤掉一些超不活跃的用户和超冷门的图书
计算两两图书之间的支持度、置信度、提升度，根据最低支持度、最低置信度、最低提升度剪枝，把低于最小值的规则扔掉
对图书A进行推荐：找出图书A的所有规则，按照置信度降序排序，Top-N即为和图书A最相关的前N本图书
非常简单，关键的就是数据清理以及规则剪枝设置，这需要对业务熟悉一些，提升度的话，如果不确认，大于1即可。
结果示例：
古龙:剑毒梅香(中) →古龙:剑毒梅香(上)|古龙:剑毒梅香(下)|武林第一少年:血欲江湖|笑傲江湖之风清扬别传|草根续写:天龙八部续
古龙:剑毒梅香(下) →古龙:剑毒梅香(中)|古龙:剑毒梅香(上)|武林第一少年:血欲江湖|笑傲江湖之风清扬别传|恐怖宿舍惊魂夜:女生寝室|倚天屠龙记之复兴明教|至尊武神:六脉神剑闹武林|草根续写:天龙八部续
温瑞安：四大名捕猿猴月 → 四大名捕会京师:逆水寒|温瑞安：四大名捕铁布衫|四大名捕震关东－亡命|四大名捕破神枪: 惨绿|四大名捕破神枪－妖红|四大名捕震关东－追杀|温瑞安：四大名捕谈亭会|温瑞安：四大名捕开谢花|温瑞安：四大名捕碎梦刀|四大名捕走龙蛇|温瑞安：四大名捕猛鬼庙|温瑞安神州奇侠:人世间
异界玄奇：尸池 → 荒村血鬼洞房:剥皮新娘|真实恐怖:鬼宅小区|丫鬟不好当:王爷,请自重|人鬼恋:我的老婆不是人|灵异事件全曝光:诡异档案|恐怖的盗墓历险:荒村古墓|校园僵尸|古墓惊魂夜:坟岭村笔记|阴阳眼之鬼瞳:荒道门|极度恐怖乱坟头:墓地惊叫|盗墓传说|不解迷:殡仪馆里的化妆师|凶尸宿舍惊魂声:猛鬼校园|惊声尖叫:太平间美丽女尸|生化疯狂撕杀之丧尸异形|僵尸当街:遇上美女天师|生化异族的入侵:吸血传说|凶宅女尸:学院惊魂夜|棺木里的眼球:古井沉尸|校园恐怖女生寝室3:诡铃
变成有钱人并不难: 理财YS → 快速发财: 怎样做无本生意|创业指南:三十六计|成功三宝:习惯、心态、人脉|掌控自己命运:读孙子兵法|改变你一生的30个招术|帮你成高手:口才决定成败|左右逢源的做人心机术|穷人与富人的差别|最快的致富秘诀: 赢在观念|做个聪明的老板: 经商要会说话|把话说得滴水不漏全集|职场:1分钟读懂对方心理|恋人浪漫短信|李嘉诚的谋局与处世|股票入门:股票认知大全|男人了解女人,女人了解男人|教你理财:理财高手|心机--做人的一种智慧|必修课:这样做女孩最命好|女人的身体·女人的智慧
……
不再多举例子了，目测感觉大多比较靠谱。
Simpler could be better.
Posted in Data Mining | 2 Comments »
Sunday, November 29th, 2009
上次去beta沙龙的视频，希望没有浪费大家的时间，感谢beta沙龙的组织工作。
Posted in Data Mining | 2 Comments »
Tuesday, November 17th, 2009
周末beta沙龙和大家分享的音乐智能推荐PPT，有些内容和上次的PPT差不多，这次主要和大家分享一个完整的数据挖掘流程，同样的，还是工程方面比较多，学术方面这里有很多大牛。
Posted in Data Mining | 6 Comments »
Monday, May 18th, 2009
断断续续的做了大半年歌曲相关性方面的试验，有一些肤浅的体会，工程方面多些，学术上仍很不足，与大家分享，望后来之君少走弯路，抑或被我带入岐途，不当之处，请指正。
PS：前段时间申请了个独立域名：http://www.fuchaoqun.com，烦请订阅feed者更新：http://www.fuchaoqun.com/feed/，原http://chaoqun.17348.com作了301跳转，将来一段时间内亦能访问。
Posted in Data Mining | 7 Comments »
Tuesday, February 3rd, 2009
本博客所有原创文章采用知识共享署名-非商业性使用-相同方式共享，转载请保留链接http://chaoqun.17348.com/2009/02/slope-one-for-music-recommender-system/
不知不觉，研究歌曲相关推荐快半年了，第一篇文章利用orange进行关联规则挖掘完成于2008.08.26，到现在基本搞定基于矩阵奇异值分解(SVD)的协同过滤算法，期间得到了很多朋友的帮助，在此致谢。有些收获，将逐步的分享出来，有兴趣的可以参照研习。
对于Slope One算法，不熟悉的可以参照我之前的文章：Slope one:简单高效的推荐算法，已经被很多人证明有很好的推荐效果。
Slope one算法中有一个很重要的步骤是获取用户的打分数据，这个对很多网站都很费劲，很多用户都会听歌，但大多懒得去给歌曲打分，另外用户打分的时候会比较困惑，该打多少分呢？喜欢这首歌，是打4分还是5分呢？费劲。
我这里给出的是另外一种方法，做法是分析用户的听歌记录，一般网站都会记录这样的记录，统计一段时间内用户的听歌记录，我们得到下面格式的数据：
用户ID 歌曲ID 听歌次数
比如某个片段：
3389 9527 23
3389 9528 56
3306 1211 78
3306 9527 45
表示用户3389听歌曲9527的次数是23，听9528的次数是56，诸如此类。这样的数据当然不能直接用来做Slope one，需要把数据格式化到某个区间。我们分析一下用户听歌的行为，一般来说最喜欢的歌曲听的最多，越喜欢的歌曲听的越多，听的少的歌曲自然不那么喜欢。所以我们可以简单的模拟用户对歌曲的打分：
用户对歌曲的打分 ＝ 用户听此歌曲的次数 / 用户听单首歌曲的最大次数
这样就可以把打分数据规整到0～1之间，还是上面的数据：
3389 9527 23/56
3389 9528 56/56
3306 1211 78/78
3306 9527 45/78
用户听的最多的歌曲打分是1，其他歌曲的打分等于听歌次数除以最大次数，我们就获得了用户的打分数据了。剩下的工作就是按照标准的Slope One流程走了，程序代码可以参考：http://code.google.com/p/openslopeone/
贴出几个实例大家看看，第一次做的结果，再去做的话应该比这个要好一些：
歌曲
推荐歌曲
南无大悲观世音菩萨 刘小茜
梵音大悲咒 齐豫
大悲咒 齐豫
观世音菩萨发愿偈.大悲咒 齐豫
大悲咒 邝美云
般若波罗蜜多心经 齐豫
大悲咒 齐豫
清净法身佛 齐豫
阿弥陀佛在心间 小娟
吉祥如意 凤凰传奇
好一朵茉莉花 朱昌耀
理查德-克莱德曼《梦中的婚礼》 合辑（欧美）
茉莉花（汉族民歌） 雷佳
好一朵茉莉花-笛子 合辑（内地）
最浪漫的事 赵咏华
沧海一声笑 罗文
how can i keep from singing Enya
生死不离 ...
Posted in Data Mining | 2 Comments »
Tuesday, January 6th, 2009
本博客所有原创文章采用知识共享署名-非商业性使用-相同方式共享，转载请保留链接http://chaoqun.17348.com/2009/01/slope-one-on-netflix-prize/
前段时间做了个slope one算法在Netflix Pirze上的测试，关于slope one算法可以参考我之前写的文章:Slope one:简单高效的推荐算法，Netflix Prize是DVD在线租赁商Netflix于2006年10月2日发起一项竞赛：任何组织或个人只要能够提交比它现有电影推荐系统Cinematch效果好10%的新方法，就可以获得100万美元的奖金。竞赛最多持续到2011年10月2日。同时，NetflixPrize还提供每年5万美元的年度进步奖。为什么是五万美元的年度进步奖呢？因为100万美元大奖存银行，每年的利息是5万美元，看来老外是挺有意思的。
Netflix Pirze采用RMSE作为评测的标准，RMSE中文的意思是均方根误差，计算的公式：
其中Ot是原始数据，Ft是预测数据，n是样本数。
目前最好的成绩是有BellKor in BigChaos创造的0.8598（2009.01.05数据），比官方数据提高9.63％，这样可以推算出官方的数据应该是0.9492左右，BellKor in BigChaos也是2008年度进步奖的获得者，他们更新数据的频率很高，如不出意外，最后的大奖应该是他们的。
目前的方向大多是SVD奇异值分解，可以参见BellKor in BigChaos他们的文章http://www.netflixprize.com/community/viewtopic.php?id=1193，这里有一个开源的项目nprize，也是一个SVD处理Netflix Prize的模型，大部分代码是Python的（国外很多用Python做数据挖掘和自然语言处理的案例），成绩到了0.9046，折算比官方数据要高4.70％，如果你想拿SVD热热手，可以看看这个开源项目，过些日子我会写一些SVD应用在推荐系统方面的文章，着急的可以阅读吴军的文章数学之美 系列十八 － 矩阵运算和文本处理中的分类问题。
由于对slope one算法比较熟悉，决定看看slope one算法在netflix pirze上的表现如何，netflix prize训练数据太大，大概有1亿多条的打分记录，OpenSlopeOne在运行效率方面不是很好，OpenSlopeOne处理几百万上千万的打分数据还是非常不错的，更多的话需要更多的机器水平扩展，如果有好的Mysql DBA可以尝试优化一下mysql server的参数，估计效果会很好，当然也需要有好的机器配合，我这里是用Python写的一个程序，多进程＋多线程＋手工Map-Reduce，需要源代码的话可以找我拿。
跑出来的结果不是很好，我的得分是0.9829，比官方数据差0.0337，大概差3.55％，分析原因可能是用户打分的数据普遍偏高，人们大多给自己喜欢的电影打分，对于不喜欢的数据打分就少很多了，下面是打分数据的分布情况：
mysql> select rating,count(*) as times from nf_log group by rating;
+--------+----------+
| rating | times |
+--------+----------+
| 1 | 4617904 |
| 2 | 10131945 |
| 3 | 28810978 |
| 4 | ...
Posted in Data Mining | 4 Comments »
Friday, September 12th, 2008
About OpenSlopeOne
OpenSlopeOne is an implementation of Slope One based on PHP&MySQL, it's an open source project under GPL V3.
It aims to a fast way to use Slope One with PHP&MySQL, and it can handle tons of data.
It's localed on Google Code:
http://code.google.com/p/openslopeone/
You can get the latest code here:
svn checkout ...
Posted in Data Mining, MySQL, Open Source, PHP | No Comments »
Wednesday, September 3rd, 2008
本博客所有原创文章采用知识共享署名-非商业性使用-相同方式共享，转载请保留链接http://chaoqun.17348.com/2008/09/slope_one/
推荐系统最早在亚马逊的网站上应用，根据以往用户的购买行为，推荐出购买某种产品同时可能购买的其他产品，国内做的不错的当当网,有时候买书，它总能给我推荐出我感兴趣的其他书来，也算是技术极大的促进了销售。
一般的协同过滤算法，首先是收集用户对事物（产品）的评分情况，一种直接对某本书，或者某个歌曲打分，另种是隐性的打分，比如商务系统中，购买了表示打2分，浏览了打1分，其他的0分。我比较看好隐性打分，因为直接打分需要用户的参与程度比较高，很多网站都在内容页中留一个打分的按钮，从1～5选一个，我可能喜欢这篇文章，可我哪里知道我喜欢的程度是几分啊，还要我去思考，而网站设计中一条很重要的原则是:Do not let me think!，于是我就胡打一个分数或者不打，而隐性的打分则不同，只有你喜欢的图书你才会购买，只有你喜欢的歌曲才会听多次。
收集好用户的打分之后，通过最近邻搜索到和某个事物或者某个人特征或者兴趣相近的其他事物或者人，最近邻搜索算法一般是皮尔森相关系数（Person Correlation Coefficient）、余弦相似性（Cosine-based Similarity）以及调整余弦相似性（Adjusted Cosine Similarity）。关于余弦定理在数据挖掘中的应用，google黑白报有过介绍，可以参考数学之美 系列 12 - 余弦定理和新闻的分类。
剩下的工作就是根据最近邻集进行推荐了。
最近邻集的运算相对来说成本比较高，尤其是大量数据的时候，今天和大家分享的是一种简单高效的协同过滤算法：Slope one
基本原理
用户
对事物A打分
对事物B打分
X
3
4
Y
2
4
Z
4
?
用户Z对事物B的打分可能是多少呢？股票上有个说法是平均值可以掩盖一切异常波动，所以股票上的各个技术指标收拾不同时间段的平均值的曲线图或者柱状图等。同样的，Slope one算法也认为：平均值也可以代替某两个未知个体之间的打分差异，事物A对事物B的平均很差是：((3 - 4) + (2 - 4)) / 2 = -1.5，也就是说人们对事物B的打分一般比事物A的打分要高1.5，于是Slope one算法就猜测Z对事物B的打分是4 + 1.5 = 5.5
是不是非常的简单？
加权算法
有n个人对事物A和事物B打分了，R(A->B)表示这n个人对A和对B打分的平均差（A-B）,有m个人对事物B和事物C打分了，R（C->B）表示这m个人对C和对B打分的平均差（C-B），注意都是平均差而不是平方差，现在某个用户对A的打分是ra，对C的打分是rc，那么A对B的打分可能是：
rb = (n * (ra - R(A->B)) + m * (rc - R(C->B)))/(m+n)
开源的Slope one的程序包
Python
http://www.serpentine.com/blog/2006/12/12/collaborative-filtering-made-easy/
Java
http://taste.sourceforge.net/
http://www.daniel-lemire.com/fr/documents/publications/SlopeOne.java
http://www.nongnu.org/cofi/
PHP
http://sourceforge.net/projects/vogoo
http://www.drupal.org/project/cre
http://www.daniel-lemire.com/fr/documents/publications/webpaper.txt Slope one算法作者写的，简单明了，强烈推荐。
Erlang
http://chlorophil.blogspot.com/2007/06/collaborative-filtering-weighted-slope.html
C#
http://www.cnblogs.com/kuber/articles/SlopeOne_CSharp.html 国人写的C#版本
T-SQL
http://blog.charliezhu.com/2008/07/21/implementing-slope-one-in-t-sql/
还有一些其他语言的版本，请参考http://en.wikipedia.org/wiki/Slope_One，即将面世的，居于PHP & Mysql的Slope one算法实现将会在http://code.google.com/p/openslopeone/开源出来，主要优化的是海量数据以及分布式处理，目前在我的笔记本上（迅驰＋1.5G内存），对440W打分记录进行测试，单一线程，3小时47分处理完。速度还算是不错了，最近工作实在太忙了，等我整理好会开源出来放在上面的地址。过几天会有一篇我的算法的详细介绍，盼诸位批评指正，共同学习，共同进步。
Posted in Data Mining, Open Source, PHP | 6 Comments »
Tuesday, August 26th, 2008
本博客所有原创文章采用知识共享署名-非商业性使用-相同方式共享，转载请保留链接http://chaoqun.17348.com/2008/08/data-mining-with-python-orange-association_rule/
最近，趁着项目的间隙，折腾了一阵数据挖掘，在同事的帮助下，对新浪音乐用户的听歌记录进行了一个简易挖掘，希望能根据用户以往的听歌记录，推荐出用户可能感兴趣的其他歌曲。
Orange：
一个模块化的C++数据挖掘包，提供python接口（好像也只提供了python接口）,网址是http://www.ailab.si/orange/
关联分析：
我这里用的是类似购物篮分析，每个用户的听歌id是一个事务，不熟悉关联分析的同学可以去搜一些相关方面的资料。
数据准备：
简单清洗掉一些“脏”数据（逻辑上有问题的数据，比如某个用户在5s听了200首歌），得到类似下面的数据
15615,355029,750367,762147,803787,805014,999712,999712,999712,1013641,1024215,1028429
871029,952779,962769
1023040,1024077,1024215,1025600
757946,873801,873801,873801
862257,873479
286056,286056,286056,286056,286056,286056,286056,286056,286056,286056
873801,873801,873801,873801,873801,947750,947750
473221,473537,504206,504206,504206,504206,504206,504206
947750,1005430,1005430
974748,1024215
873479,873479,873801,873801,947750,965748,999721,1024215,1024215,1024215,1024215,1024215
873801,873801,873801
每一行是一个用户的听歌记录，没有做去重处理（orange示例中也没有，是不是可能会增加歌曲的权重？不清楚，没有去阅读orange代码），注意文件名一定要以.basket为扩展名，程序中文件地址是d:/datamining/sample.basket。
程序：
# 导入orange包
import orange
# 导入数据，注意不需要后缀
data = orange.ExampleTable("d:/datamining/sample")
# 挖掘关联规则，输入最低支持度、最低置信度、最大项集数
rules = orange.AssociationRulesSparseInducer(data, support = 0.5, confidence = 0.6, maxItemSets = 1000000)
# 打印出规则来
for r in rules:
print "%5.3f %5.3f %s" % (r.support, r.confidence, r)
是不是非常的简单？Orange实现的是Apriori算法，由于Apriori算法的问题，一旦数据量非常大，你就等着你的内存消耗光吧，反正我这边要是把所有数据都导入进去的话，笔记本1.5G的的内存根本不够用，可以试试FP-tree算法，我这边参考文章利用sql改良构建fp-tree之技术，已经把fp-tree的前缀路径都找出来了，需要的朋友可以私下找我要，由fp前缀路径挖频繁集需要用到递归，用sql去处理就非常费劲了，所以后面的算法还需要自己去探索。
居于关联规则的挖掘就告一段落，因为算法的计算复杂度非常高，效果倒不是太好（因为对于音乐，用户可能听多遍，这样打分就不一样，可能用关联规则去挖电影类的数据比较好，因为电影一般最多就看一遍），现在研究的是协同过滤，如果不出意外的话，一个改良版的PHP+Mysql实现slope one算法过几天就要出来了，到时候我会开源出来的。
Posted in Data Mining, Python | 1 Comment »