Trend Detection in Twitter

方法其实都很直接,甚至可以说是直白。

1st Approach

首先能想到的最简单的方法就是统计所有term(词)的频数(当然,stopwords是一定要剔除的)。
所谓的trend可以理解成某个term的使用频数突然增高了。所以,算法的核心就变成了将当前term的频数和过去一段时间的平均频数相比较:

image

Twitter采用的是过去一个月的平均值作为baseline。
如此简陋的方法当然有很多的问题,最大的问题是对低频词的偏袒。频数很低的词,只需要突然增加一点点,ratio就可以变得很大:

image

2nd approach

上述方法中使用的ratio实在是太简陋了,考虑用一个更好的统计学上的参数替代它。
方法2的基本假设,是认为每个terms之间是独立的,且满足一个静态的二项式分布:

image

然后用卡方检验来衡量观察到的数据和假设分布之间的差异:

image

将卡方检验套用到term上:

image

对于某个特定的term,将term当成category1,而将其他的term当成category2,于是就有了上述的公式。
方法2的核心就是将方法1中的ratio替换成了卡方检验。用卡方检验的好处,一是能够从统计学上找到理论支持,另一方面,它其实是对高频词做了加权。

实际应用中,还需要改动一下公式,做点smoothing:

image

3rd approach

前2个方法,都是将term当前的频数和过去一个月的平均频数做比较。但是有一些term,它的趋势是周期性的,例如“good morning”每天早晨的频数都会特别高。为了解决这些问题,仅仅用过去一个月的平均值作为唯一的比较就不合适了:

image

image

方法3是借鉴了google的做法。它引入了更多的feature,但是也带来了问题,就是计算很复杂。而且没有说清楚具体是怎么做的(演讲人也提到,这个方法他在yahoo尝试了,但是Twitter好像不是这么做的。)

三个方法从简单到复杂,整个思路的过程很完整。值得学习。

演讲人还提到,trend可以分成2类 – sudden events 和 expected event,大致如下图:

image

——————-

Topic Detection

topic detection就是对前面trend detection得到的结果做clustering:

image

问题是,大数据量下,如果要计算每个vector和cluster之间的similarity,计算开销太大了。所以,不采用传统的smilarity的计算方法,而是用Minhash + Locality Sensitive Hashing

image

image

image

— END. —

Advertisements
相册 | 此条目发表在Analyzing Big Data with Twitter分类目录,贴了, 标签。将固定链接加入收藏夹。

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s