Archive for the ‘Open Source’ Category
Wednesday, November 26th, 2008
本博客所有原创文章采用知识共享署名-非商业性使用-相同方式共享，转载请保留链接http://chaoqun.17348.com/2008/11/sphinx-on-windows-xp/
前一阵子尝试使用了一下Sphinx，一个能够被各种语言(PHP/Python/Ruby/etc)方便调用的全文检索系统。网上的资料大多是在linux环境下的安装使用，当然，作为生产环境很有必要部署在*nix环境下，作为学习测试，还是windows环境比较方便些。
本文旨在提供一种便捷的方式让Sphinx在windows下安装配置以支持中文全文检索，配置部分在linux下通用。
一、关于Sphinx
Sphinx 是一个在GPLv2 下发布的一个全文检索引擎，商业授权（例如, 嵌入到其他程序中）需要联系作者（Sphinxsearch.com）以获得商业授权。
一般而言，Sphinx是一个独立的搜索引擎，意图为其他应用提供高速、低空间占用、高结果相关度的全文搜索功能。Sphinx可以非常容易的与SQL数据库和脚本语言集成。
当前系统内置MySQL和PostgreSQL 数据库数据源的支持，也支持从标准输入读取特定格式的XML数据。通过修改源代码，用户可以自行增加新的数据源（例如：其他类型的DBMS的原生支持）。
搜索API支持PHP、Python、Perl、Rudy和Java，并且也可以用作MySQL存储引擎。搜索API非常简单，可以在若干个小时之内移植到新的语言上。
Sphinx特性：
高速的建立索引(在当代CPU上，峰值性能可达到10MB/秒);
高性能的搜索(在2–4GB的文本数据上，平均每次检索响应时间小于0.1秒);
可处理海量数据(目前已知可以处理超过100GB的文本数据,在单一CPU的系统上可处理100M文档);
提供了优秀的相关度算法，基于短语相似度和统计（BM25）的复合Ranking方法;
支持分布式搜索;
提供文件的摘录生成;
可作为MySQL的存储引擎提供搜索服务;
支持布尔、短语、词语相似度等多种检索模式;
文档支持多个全文检索字段(最大不超过32个);
文档支持多个额外的属性信息(例如：分组信息，时间戳等);
停止词查询;
支持单一字节编码和UTF-8编码;
原生的MySQL支持(同时支持MyISAM和InnoDB);
原生的PostgreSQL支持.
中文手册可以在这里获得，感谢译者的辛勤工作。
二、Sphinx在windows上的安装
1.直接在http://www.sphinxsearch.com/downloads.html找到最新的windows版本，我这里下的是Win32 release binaries with MySQL support，下载后解压在D:\sphinx目录下；
2.在D:\sphinx\下新建一个data目录用来存放索引文件，一个log目录方日志文件，复制D:\sphinx\sphinx.conf.in到D:\sphinx\bin\sphinx.conf（注意修改文件名）；
3.修改D:\sphinx\bin\sphinx.conf，我这里列出需要修改的几个：
type = mysql # 数据源，我这里是mysql
sql_host = localhost # 数据库服务器
sql_user = root # 数据库用户名
sql_pass = '' # 数据库密码
sql_db = test # 数据库
sql_port = 3306 # 数据库端口
sql_query_pre = SET NAMES utf8 # 去掉此行前面的注释，如果你的数据库是uft8编码的
index test1
{
# 放索引的目录
path = D:/sphinx/data/
# 编码
charset_type = utf-8
# 指定utf-8的编码表
charset_table = 0..9, A..Z->a..z, _, a..z, U+410..U+42F->U+430..U+44F, U+430..U+44F
# 简单分词，只支持0和1，如果要搜索中文，请指定为1
ngram_len = 1
# ...
Posted in Full Text Sarch, Open Source, 默认分类 | 3 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 | 1 Comment »