新浪微博分析算法（一）标签传播

摘自：新浪微博背后的那些算法剖析

1，标签传播
       微博用户量浩大，不同的人有不同的兴趣。挖掘每个用户的兴趣有助于更加精准的广告投放、内容推荐。为了得到每个用户的兴趣，可以为用户打上标签，每个标签代表用户的一个兴趣，用户可以拥有一个或多个标签。为了得到最终的用户标签，先做第一个假设：
       每个用户的好友(或粉丝)中与该用户具有相同兴趣的人占多数。
       这就引出了本文介绍的第一个算法，即标签传播算法。在这个算法中，每个用户的标签取其好友或粉丝中标签最多的一个或多个。当然，可以将好友和粉丝的标签都考虑进来，整合的时候可以考虑赋予好友的标签和粉丝的标签不同的权重。标签传播算法的过程如下：
       1) 对一部分用户给出初始标签；
       2) 对每一个用户，统计其好友和粉丝的标签数目，赋予该用户出现次数最多的一个或者多个标签。
       3) 循环进行第2步，直到用户的标签不再发生大的变化为止。

2，用户相似度计算
       标签传播算法实现起来比较简单，其缺点在于当所做的假设不符合事实时，比如为了社交上的礼貌，我们一般会把自己的亲友添加关注，这些人不一定和我们拥有同样的标签；该算法的结果就会变得很差。解决的办法就是通过计算用户之间的相似度来衡量好友或粉丝的标签对用户标签的贡献率。因而得到第二个假设：
       与用户越相似的好友或粉丝，其标签越可能是用户的标签。
       那么，如何衡量用户之间的相似度呢？这就需要考虑到用户发表的微博信息了，包括转发的和原创的。这里是要考虑用户之间的相似度而不是用户微博之间的相似度，因而在实际计算时，将某个用户的所有微博信息聚集到一起进行计算。一个可选的方法是使用词袋法将微博信息表示成词语向量，然后直接使用余弦方法等计算其相似度。但这个方法太过简单，不容易达到好的结果，这里介绍一种基于LDA（隐含狄利克雷分布）的相似度计算方法。
       LDA仍然使用词袋法表示文本，但是在中间添加了一个主题层，形成了“文档-主题-词语”三层概率模型，即每篇文档看成是主题的一种概率分布，主题又被看成是单词的概率分布。在LDA模型下，文档可以被看成按照如下方式生成：
       1) 对于每篇文档：
       2) 从主题分布中抽取一个主题；
       3) 从该主题的词语分布中抽取一个词语；
       4) 重复第2步和第3步，直到该文档的所有词语都生成。
       LDA模型参数的估计算法不在本文的讨论范围之内。这里只需要知道，通过LDA可以得到每个用户的微博信息的主题分布。然后使用余弦方法、KL距离等计算相似度的方法来得到用户间主题分布的相似度，以之作为用户之间的相似度。而后使用该相似度对标签传播进行加权。