推荐系统中的两种不同类型的用户

在设计推荐系统时，我们发现有两种用户，一种用户可以称为大众化用户，这种用户喜欢的物品是大家都喜欢的物品。 还有一种用户是偏激的用户，他们喜欢的是大家不怎么喜欢的东西，他们的看法总是和大众化看法相反。

在设计推荐系统时，要充分考虑这两种用户的特点

推荐系统的5个问题

by Richard MacManus

http://www.readwriteweb.com/archives/5_problems_of_recommender_systems.php

1. Lack of Data 数据缺失

Perhaps the biggest issue facing recommender systems is that they need a lot of data to effectively make recommendations. It's no coincidence that the companies most identified with having excellent recommendations are those with a lot of consumer user data: Google, Amazon, Netflix, Last.fm.

推荐系统的最大问题是它们需要很大的数据量来做出好的推荐。毫无疑问，那些在推荐系统上做出很好结果的公司都是拥有大量用户数据的公司:Google, Amazon, Netflix, Last.fm.

2. Changing Data 数据变化

This issue was pointed out in ReadWriteWeb's comments by Paul Edmunds, CEO of 'intelligent recommendations' company Clicktorch. Paul commented that systems are usually "biased towards the old and have difficulty showing new".

An example of this was blogged by David Reinke of StyleHop, a resource and community for fashion enthusiasts. David noted that "past behavior [of users] is not a good tool because the trends are always changing" (emphasis ours). Clearly an algorithmic approach will find it difficult if not impossible to keep up with fashion trends. Most fashion-challenged people - I fall into that category - rely on trusted fashion-conscious friends and family to recommend new clothes to them.

David Reinke went on to say that "item recommendations don't work because there are simply too many product attributes in fashion and each attribute (think fit, price, color, style, fabric, brand, etc) has a different level of importance at different times for the same consumer." He did point out though that social recommenders may be able to 'solve' this problem.

3. Changing User Preferences 用户兴趣的变化

Again suggested by Paul Edmunds, the issue here is that while today I have a particular intention when browsing e.g. Amazon - tomorrow I might have a different intention. A classic example is that one day I will be browsing Amazon for new books for myself, but the next day I'll be on Amazon searching for a birthday present for my sister (actually I got her a gift card, but that's beside the point).

On the topic of user preferences, recommender systems may also incorrectly label users - a la this classic Wall St Journal story from 2002, If TiVo Thinks You Are Gay, Here's How to Set It Straight.

4. Unpredictable Items 不可预测的项目

In our post on the Netflix Prize, about the $1 Million prize offered by Netflix for a third party to deliver a collaborative filtering algorithm that will improve Netflix's own recommendations algorithm by 10%, we noted that there was an issue with eccentric movies. The type of movie that people either love or hate, such as Napoleon Dynamite. These type of items are difficult to make recommendations on, because the user reaction to them tends to be diverse and unpredictable.

Music is full of these items. Would you have guessed that this author is a fan of both Metallica and The Carpenters? I doubt Last.fm would make that recommendation.

5. This Stuff is Complex! 系统很复杂

We're stating the obvious here, but the below slide from Strands' presentation at Recked illustrates that it takes a lot of variables to do even the simplest recommendations (and we imagine the below variables only scratch the surface):

Web研究方面的资源

经过半年对Web的研究，还是很有感触，失败让人学习啊！特别我们实验室刚开始做网络，没有前人的经验更是困难啊。

我目前在做collaborative filtering & recommend system， 就是推荐系统，比如amazon里面推荐书，或者其他的推荐网站。

我做了一个网页，收集了这方面的一些研究资源：http://xlvector.googlepages.com/webcrawling

今年上半年要好好努力，争取做出点成绩。

越来越感到牛顿话的正确：成功的人都是站在前人的肩膀上的。

昨天给一个18岁的孩子写了一个成人赠言，我觉得也适合用来勉励自己：

有信心！有决心！有恒心！

今年的web方面的会议

Web Intelligence (WI'09)
Workshop proposal submission: January 15, 2009
Electronic submission of full papers: April 10, 2009
Tutorial proposal submission: April 10, 2009
Workshop paper submission: April 30, 2009
Notification of paper acceptance: June 3, 2009
Camera-ready copies of accepted papers: June 30, 2009
Workshops: September 15, 2009
Conference: September 15-18, 2009

ECIR2010
10 Sep 2009: Workshop/tutorial submission deadline
01 Oct 2009: Paper submission deadline
22 Oct 2009: Poster and demo submission deadline
31 Oct 2009: Notification of acceptance (workshops/tutorials)
23 Nov 2009: Notification of acceptance (papers/posters/demos)
20 Dec 2009: Camera-ready copy
15 Jan 2010: Registration open
01 Feb 2010: Author registration

WISE2009
Workshop proposals February 28, 2009
Full paper submission May 1, 2009
Tutorial/Panel proposals May 31, 2009
Author notification June 15, 2009
Camera-ready submission June 28, 2009
Author registration June 28, 2009
Conference and Workshops October 5-7, 2009

ACM Recommender Systems 2009
Tutorial Proposals: April 10, 2009
Paper Submission: May 8, 2009
Workshop Proposals: May 15, 2009
Doctoral Symposium Applications: June 8, 2009
Paper Acceptance Notifications: June 19, 2009
Conference: October 22-25, 2009
Doctoral Symposium: October 22
Tutorials: October 22
Technical Program: October 23-24
Workshops: October 25

常见爬虫分析

最近在写一篇关于爬虫的论文，写了N天英文，感觉用英文说事真是麻烦，还是用汉语说更能表达我的观点。所以写一篇博客总结一下。

很多人说，爬虫有什么了不起的，不就是个广度优先搜索嘛！现在也有各种各样的开源爬虫，拿过来直接用挺方便，不过实际的网络爬虫确实不那么简单。

一般来说，好的爬虫要满足两个条件：（1）首先爬比较著名的网站，比如sina，qq，啥的（2）在更新的时候，首先更新比较著名的网站，比如sina,qq啥的。这两个条件很容易理解，因为这些网站受到很多用户的注意，所以先爬先更新是应该的。

那么我要问，互联网上这么多网站，你怎么知道哪些网站是著名的？有人要说，不是有著名的pagerank算法吗，他可以基于链接关系给出网页的排名。那么我又要问这帮人，现在网页还没有爬下来，你怎么运行你的pagerank算法。这个问题就不那么好解决了。

于是，一个牛人说，我们可以这样，我们先用广度优先搜索爬一段时间，然后得出一个网页集合，然后用pagerank算法对这个集合中的那些未爬网页（就是这个集合中的网页会指向很多网页，这些网页很多没爬）排名，然后选择排名最高的网页先爬。这个就是启发式爬虫的思想，简单的说，他是用一个优先级队列，而不是广度优先爬虫的FIFO队列来存储待爬的网页，然后用爬下来的网页直接的链接结构启发式的估计待爬网页的排名。
这个爬虫的想法不错，不过还是有效率问题，我们知道，pagerank是一个迭代算法，如果网页多了，算起来还是很费事的。

一个牛人看到这个问题，他重新研究了广度优先爬虫，他忽然发现，广度优先爬虫能够自然的倾向于爬著名的网站，这是因为著名的网站有大量的反向链接，所以很容易从别的网页发现著名的网站，从而著名的网站能够比较早的爬下来。广度优先爬虫的这个属性实在是太好了，不过尽管他有这个倾向，但是他在爬著名网站这个问题上的效率还是不如上面的那种爬虫，也就是说，他首先爬下来的网页中，还是有大量的不重要的网页。

所以说，如果我们有一个方法，能够像广度优先爬虫那么自然的对著名网页有一种倾向，而且这个倾向非常大。那么这中爬虫无疑是很高效的，不用每次都算PageRank就能自动的先爬著名的网站，这种爬虫当然很好很强大。

我的这篇文章，主要就是谈如何设计这种爬虫。

popular网页的两个基于链接的特征

在web graph中，什么样的网页是popular的，也许有人说，PageRank高的是popular的。不过PageRank还是有很多缺点的。我们研究发现，popular网页有两个特征：

1. popular的网页和大多数网页的距离都很近
2. popular的网页和其他的网页连接很紧密

PageRank算法在上面两个特征上都有所反应，但反应的不够。

PageRank算法的几个主要问题

PageRank是一种基于链接的网页排名算法，他的主要思想是，一个网页如果被很多其他网页链向，他就有比较高的排名，同时一个网页如果被排名高的网页指向，他也会有比较高的排名。这个是PageRank的一个经典解释。
不过这个算法还是有很多问题。

我们举一个例子，比如下图。黄色的网页被很多蓝色的网页指向，但是这些蓝色的网页只被少数的橙色的网页指向。也就是说，如果没有这些橙色的网页，黄色的和蓝色的网页就和整个互联网不联通了。在这个例子中，黄色的网页会获得比较高的PageRank，但实际上，黄色的网页不应该有这么高的排名，因为他和整个互联网的联系是松散的。他的排名其实是被蓝色的网页提高上去的。



这是一个典型的link farm，也就是链接工厂的结构。黄色的网页叫target page,就是我们要提高rank的网页，而蓝色的网页是boost page，也就是用来提高rank的网页。

PageRank的最大问题，就是对链接工厂无能为力。但这是为什么呢？我们可以用pagerank的另一个解释来说明这个问题。很多研究表明，一个页面的pagerank是这样获得的：

我们知道，对一种网页，有很多从其他网页到他的路径。比如对网页x，有一条从y到x的路径，那么y就通过这条路径把自己的pagerank注入到x，路径越长，注入的rank就越多。那么，一个网页如果有很多比较短的到他的路径，这个网页就会有比较高的rank。但是，这里面有一个问题，那就是这些路径可能都是交叉的。比如上面的图中，所有到黄色顶点的路径都会在橙色顶点相交。而同时，link farm是一个稠密图，他里面的短路径是很多的。这就解释了pagerank为什么解决不了链接工厂的问题。

那么对于越多的SEO网站，我们有什么手段来发现他们呢？下面这个方法比较著名：

我们忽略那些特别短的路径，因为spam会从link farm中获得很多短路径，如果我们忽略掉特别短的路径对pagerank的影响，可以解决这个问题。

对于web graph中的一个网页v，我们把到他的距离为h的顶点数记为S(v,h)。
那么对于任何一个顶点v，S(v,h)关于h的分布是用来对v排名的一个重要手段，现在有很多这方面的研究。

随机计数算法 probabilistic counting

一个著名的问题，给定一个数据集，一共有n个元素，其中完全不同的元素个数为m，怎么求出m？
如果要准确的计算，那么复杂度是nlog(n)的，因为我们首先要对n个元素排序，然后去重。
那么，我们如果n特别大，比如在搜索引擎的算法中，n可能有上亿，这个时候我们也不需要求出准确的m，只要给一个比较准确的m，满足一定的误差要求。这时就可以用一种随机计数的方法。
这个算法主要流程如下：
1.生成一个p个元素的数组 Bitmap[p], Bitmap[i] = 0
2.对数据集中的每个元素，求出他的hash值, h = hash(data[i]) mod p; Bitmap[h] = 1
3.最终，我们令Bitmap中0元素所占的比例为V, 那么一个m的估计就是
m = -p ln(V)

这个算法已经提出了很久。在计算图的全源最短路径时有也很多应用。

下面几篇文章是这个领域的一些重要文章

1.Probabilistic counting algorithms for data base applications
2.A linear-time probabilistic counting algorithm for database applications

一些互联网技术方面比较好的会议和期刊

4．0 国际专业著名刊物

ACM Transactions on Information Systems （TOIS）
ACM Transactions on Database Systems (TODS)
ACM COMPUTING SURVEYS
IEEE/ACM TRANSACTIONS ON NETWORKING
IEEE JOURNAL OF SELECTED AREAS IN COMMUNICATIONS
IEEE Transactions on Knowledge & Data Engineering (TKDE)
Journal of Data Mining & Knowledge Discovery (JKDD)
Data and Knowledge Engineering(DKE)
VLDB Journal (VLDBJ)
Information Processing and Management（IP&M）

3．5 国际专业著名刊物

ACM Transaction on Storage
IEEE Transactions on Parallel Distributed Systems (TPDS)
IEEE Transactions on Computer
ELSEVIER JOURNAL OF NETWORK AND COMPUTER APPLICATIONS
Intl Journal of Concurrency and Computation
Intl Journal of Parallel Distributed System
Intl Journal of Computer Networks
Bioinformatics

3.0国际专业著名刊物

ACM TRANSACTIONS ON COMPUTER SYSTEMS
ACM TRANSACTIONS ON SENSOR NETWORKS
ACM COMPUTER COMMUNICATION REVIEW
ACM JOURNAL OF THE ACM
IEEE Transactions on Computer
IEEE NETWORK
IEEE INTERNET COMPUTING
IEEE TRANSACTIONS ON MOBILE COMPUTING
IEEE WIRELESS COMMUNICATIONS
IEEE TRANSACTIONS ON COMPUTERS
ELSEVIER ad hoc networks
ELSEVIER computer networks
ELSEVIER JOURNAL OF NETWORK AND COMPUTER APPLICATIONS
ELSEVIER Journal of Network and Computer Applications
ELSEVIER Pervasive and Mobile Computing
SPRINGER WIRELESS NETWORKS
SPRINGER MOBILE NETWORKS & APPLICATIONS
Journal of Computer Networks

3．0 国际专业品牌刊物

ACM Intl Symposium on Modeling, Analysis and Simulation of Wireless and Mobile Systems (MSWiM)
ACM ACM TRANSATIONS ON INTERNET TECHNOLOGY
IEEE Transactions on vehicular technology
IEEE Transactions on Computer
ELSEVIER computer communications
ELSEVIER AD HOC AND SENSOR NETWORKS
JOHN WILEY&SONS INC NETWORKS
JOHN WILEY&SONS INC WIRELESS COMMUNICATIONS
Data and Knowledge Engineering (DKE)
Information Systems (IS)
WORLD WIDE WEB Journal
Knowledge and Information Systems (KIS)
Information Retrieval
Journal of Web Semantics
SIGMOD Record
Journal of Computer Networks
Journal of Software and Systems

2．0 国际有一定知名度的刊物/国内重要期刊

Intl Journal of Information Technology，
Journal of Information Science，
Journal of Computer Science and Technology,
Journal of Web Engineering
JOURNAL OF COMPUTER SCIENCE AND TECHNOLOGY （JCST）
KICS JOURNAL OF COMMUNICATIONS AND NETWORKS
IEICE TRANSATION ON COMMUNICATIONS
《中国科学》
《科学通报》

互联网是宇宙吗？

如果我们把互联网看成一个宇宙，那么网站就是星系，网页就是恒星。
不过这个还是有点问题，门户网站可以看做一个星系，但是google呢？google和很多搜索引擎，网页目录一样，他们有点像一个核，指向了大多数网站。

最近有研究显示，银河系中心有一个黑洞，而这个黑洞的引力是的银河系的其他恒星围绕这个黑洞旋转。这个模型很适合互联网，而这个黑洞对应了互联网的核。很多重要的网站都在这个核里面。

对于任何有核的结构，比如原子，大家会对核的分裂很感兴趣。如果我们随机的删去核中网页的超级链接，那么这个核是分成几个差不多大的核，还是分成一个大的核已经很多很小的核？

实验表明，是分成一个大的核和很多很小的核。所以，对于互联网的核，不可能一刀劈两半，只能一层层的削，每削一刀，一些不重要的网站就从核中分离出去了。

下面是互联网的结构图，包含了20w个网站，而中间那些红点，是诸如google，sina，baidu，yahoo那些网站

这个图经过了1周的迭代，现在已经变成了下面这个样子，这个样子看起来很像一个圆盘

我们将PageRank前10000名的网站标成了黄色。

Web Crawler 爬虫的困惑：下一步走向何处

最简单的表述，爬虫的作用就是从一个起始页面开始，抓取整个互联网。但是，互联网太大了，一个爬虫显然不可能抓取整个互联网。那么最简单的想法是，先抓取比较重要的网页，然后再抓取比较不重要的网页，同时比较频繁的更新重要的网页。

这样问题就出来了，爬虫怎么知道什么网页是重要的？也许有人说，不是有pagerank算法吗？但是，pagerank是在爬下网页后根据网页之间的超级连接计算出来的，现在爬虫什么也没爬，他怎么知道互联网的拓扑结构。

我们可以把互联网定义为一个世界，而爬虫相当于在一个世界中的探索者，在一开始，爬虫对这个世界一无所知，这时他只能在这个世界中盲目的走来走去，但是他每走一步，都会加深对这个世界的认识，我们把这种认识称为爬虫眼中的世界。所以，在爬虫研究中，最重要就是，如何根据爬虫眼中的世界去判断下一步走向哪里？

那么，就出现了几种不同的爬虫：
1) 广度优先搜索爬虫(BFS)
这种爬虫永远盲目的走下去，他不会利用它已经获得的知识，就是不停的爬...

2) 反向链接爬虫(BackLink)
这种爬虫在走下一步之前，先根据已经掌握的知识，判断在候选链接中那个链接可能会有比较大的反向链接数，然后就选择那个链接爬下去...

3)pagerank爬虫
这种爬虫更聪明一点，他在判断下一步走向哪里前，先根据现有的知识，将候选链接中每个链接的pagerank计算出来，然后选择那个链接爬下去...

这3种爬虫是爬虫界的典型代表，也许大家觉得，效果最差的应该是BFS爬虫，因为这种爬虫很懒，不会利用自己已经获得的知识，其实这种认识是错误的。 根据研究发现，在很多情况下，效果最差的可能是BackLink爬虫，why？

这是因为，互联网拓扑结构实在是太复杂了，一点点知识用不好还不如不用。BackLink爬虫经常会陷入到局部极小。举一个例子，一个backlink爬虫某一天爬进了新浪网，在里面爬了一段时间，他忽然发现，这个网站太好了，很多页面都有比较大的backlink，于是这个爬虫就在sina里不停的爬，由于sina实在是很大，于是这个爬虫便乐不思蜀，永远也不从sina里出来了，而在他眼里，sina似乎就是整个世界。

所以，如何利用爬虫眼中的互联网去估计整个互联网还是很困难的，难就难在互联网实在是太大了。很多算法，稍不注意就会像上面的例子那样限入到以偏概全的错误中去。但是，如果老是盲目的爬下去，似乎又对不起已经获得的一些知识，所以，如何运用已知世界去预测未知世界，是爬虫遇到的最大困难.

那也许有人要问，现在的搜索引擎爬虫不是都爬的挺好的吗，没发现有上面的问题啊。这是因为，在一个搜索引擎系统中，利用了团结就是力量的道理。在一个真正的搜索引擎中，不会只有一个爬虫在爬，而是成千上万个爬虫从互联网的不同角落开始爬，而每爬一段时间，他们还会互相交流一下自己对互联网结构的看法。所以即使一个爬虫会不时的陷入局部极小，但其他爬虫能够把它从坑中拉出来。在这种设计下，一帮很弱的兵整合在一起就会形成一个有战斗力的部队。

但是，对单一爬虫的研究还是很重要的，如果每个爬虫都很强大，那么把他们组合起来，将是一个更强的的部队。

下面这个例子可以很好的说明几种爬虫的区别

这是我们正在研究的爬虫，他能够对世界产生一个整体的认识，而不会局限到某一个聚类中
Best First 可以看到这种爬虫是爬完一个聚类爬下一个，很难形成对世界的整体认识
Bread First 这种爬虫比Best好一点，但效果取决于网页的顺序

网络中顶点相似度的计算 node similarity measurement in network

Graph的一个最大好处，是他可以用尽量少的空间来存储物体(object)直接的相似度。如果我们有N个物体，要存储他们两两直接的相似度，需要用N*N的存储空间。但是用Graph可以节省很多空间，因为他可以将很多相似度隐含到网络的结构中去。

相似度图G(V,E,W).如果两个顶点直接有边连接，那么边的权重就代表两个顶点直接的相似度。那么如果两个顶点之间没有边连接呢？虽然没有边连接，但只要图是联通的，那么肯定有若干条路径连接，这就是前面所说的，顶点的相似度蕴含在图的结构当中。那么我们的相似度函数必须在考虑图的边的同时，还要考虑图中的路径。

以下是本文用到的一些记号
inv(A) : A的逆矩阵
pow(A,n) ：A的n次方

1.Katz的方法
A new status index derived from sociometric analysis 1953
如果G的邻接矩阵是A，a(i,j)是顶点i,j的相似度。那么Katz用一下的方法来度量相似度：
S = inv(I - pA) - I = pA + pow(pA,2) + ... + pow(pA,n) + ...
这个方法通过邻接矩阵的n次方来考虑图中小于n的路径。这个方法的优点是定义很简单，意义也很清楚。缺点就是，矩阵的求逆计算太耗时。 而且这个方法一次性的计算了图中所有顶点对之间的相似度，如果我们仅仅要知道两个顶点直接的相似度，复杂度就太高了。

2.RandomWalk 随机游走
这个方法首先计算出图的马尔可夫转移概率矩阵。然后在图中进行随机游走。假设从i开始随机游走，如果i,j之间有一条边，那么从i到j的转移概率是p(i,j). 那么我们考虑图中的任意一个点k，那么我们考虑如果从i出发，随机在图中游走，那么第一次走到k需要的平均步数，可以看作i,k之间的相似度。
Random-Walk Computation of Similarities between Nodes of a Graph with Application to Collaborative Recommendation. 2007 Francois Fouss


未完待续...