标签传播算法在微博用户兴趣图谱的应用

http://hui.csdn.net/MeetingInfo.aspx?mid=111
（据主办方说之后会有PPT和现场视频放出）




我的听后感是，这个应该是三个主讲人中讲的最棒的。
本来我的关注点可能还是如何爬微博，虽然这部分几乎没收获。
但是也感叹原来算法如此简单。

对于最后问答环节提到的最初建立7000万用户的兴趣图谱，用了多久。
1天的时间我觉得还是真的已经不算慢了。

那么综合来说，可能几个重点就是：
现有算法考虑的是文本信息和社交行为两点。
在文本信息中又要考虑到各种信息价值低的信息（TF和IDF）。
最后在Hadoop平台中我认为肯定是有优化的，只不过这个东西是没有提到的。

新浪微博在这方面的优势也就是“大数据”了。
当算法不变的情况下，我看中的还是“自标签”这个东西的不可靠性。
首先，在“自标签”问题中，文本标准化（降噪、归一）是问题。
其次，存在于“自标签”中的“噪音”，是否可以代表一定的用户个性？
最后，“自标签”一定存在长尾。


=================以下是几乎PPT文字版还原========================

by 张俊林（新浪微博-搜索部-推荐组）

用户兴趣图谱的重要性
        -个性化概念（199X年出现的概念）
        -根据用户的行为以及用户产生的内容等方方面面的数据来从中到处用户可能的兴趣点
        -用户个性化兴趣建模
                10年前很多人都在关注
                现在时机才算成熟
兴趣图谱的用户
        -个性化建模
        -推荐感兴趣的信息
                -感兴趣的人
                -感兴趣的微博
                -感兴趣的新闻
                -感兴趣的图片
                -感兴趣的群组
                -定向广告推送（商业，热★）
                
订阅微博重排序（部分用户已经可看到）
        -智能排序
                把feed流，根据用户兴趣图谱，按照可能更感兴趣的顺序，来重新排序
                现在在新浪微博内部，几乎每个用户都已经构建出兴趣图谱

微博环境下有很多可利用信息
        -发表的微博内容
        -转发评论的微博内容
        -自标签
        -参加的群组
        -参加的投票
        -我关注的人
        -关注我的人
        -社交行为
        ……

构建用户兴趣图谱可利用的信息
        本讲座主要涉及到的信息
                -文本内容
                        -发表
                        -转发
                        -自标签
                -综合
                        -社交行为

标签传播算法
        自动挖掘社交关系中的“团结构”
        问题：对于社交网络S，如何通过标签传播算法自动发现其中的密集连接子图？
        基本思路：
                -初始阶段
                        为途中每个节点赋予一个独一无二的标签L
                -多轮迭代
                        通过社交关系（即图的边）将标签向其他节点传播
                        某个节点node将根据与其有边联系的其它节点的标签来决定自己此轮应该赋予哪个标签（更新标签L）
                                -将其邻居节点的标签中出现次数最多的那个标签赋予自己（count）
                                -如果邻居节点的标签数目一样多，无法找出最多个数标签
                                        -则随机赋予一个标签即可
                -直到图中的节点标签都不再改变（稳定），迭代结束
                        对于一个密集连接子图，即最后达到所有节点的标签是一样的（圈子/群组形成）
        
        
使用标签传播算法计算微博用户兴趣图谱
        Recap: 利用到的信息
                发表的微博内容-->兴趣词
                转发微博内容-->兴趣词
                自标签
                社交行为
        构建图结构
                图节点：用户ID
                节点之间的边：社交信息（理论上有权重）
                        -转发
                        -评论
                        -@U
                初始标签（利用文本信息，不再只有一个，是一个列表）
                        内容兴趣词
                        自标签
                基本假设
                        如果两个用户之间的互动越频繁，那么两者之间的社交关系越紧密，而亲密的社交关系往往蕴含着潜在的兴趣关联或者较强的线下社交关系
                                经过测试，发现在微博用户中，较强的线下社交关系不太存在
                
        算法流程
                多轮迭代
                        STEP1: 找到与节点A有变联系的邻居节点，形成邻居节点集合S，S中的这些节点代表了与用户A有过互动行为的用户集合，同时A也放入集合S中
                        STEP2：统计集合S所有用户中出现过的不同标签的频次，用户A本身初始的标签按照频次f参与计数（count），即给用户本身的标签一个较大的初始频次
                        STEP3：将第二步获得的标签按照其频次和标签的IDF值使用类似TF: IDF（单词的信息含量）计算框架的方式计算其权重，并按照权重得分高低排序，取TOP K标签作为节点A的新标签集合（更新，重排）
                迭代终止条件
                        次数or不再变化
                        
        
        为何引入类似IDF因子
                用户标签中饱含一些非常通用的内容，信息含量低
                        80后、音乐、网络营销etc（至少有7000万用户有这些标签，是噪音）
                控制方法
                        只保留信息含量高的
                        计算权值公式中调节TF和IDF因子重要性
        
        算法优点：
                综合内容因素和社交因素（社交因素就是希望体现出如下假设）
                        你所在的群组反映你的兴趣
                对发布内容少的用户也可以刻画其兴趣
                        在微博中，真正活跃的用户不多
                        在这种情况下，单纯根据其内容因素，是分析不出什么结果的
                        只好通过他的群体行为，获得他可能的兴趣点
                        
                        
大规模数据计算问题
        新浪微博用户超过3亿
        分布式计算
                Hadoop平台
                MapReduce任务
        MapReduce
                只需要关注任务本身
                写一个map，一个reduce
                不需要关注大数据是否出错等
                
                Input切分成数据块
                对于每个计算，由K(KEY),V组成
                        进行Map(k, v) --> (k', v')
                经过Group(k', v')s by k'
                Reducer
                得到结果
        
        WordCount
                map(String key, String value);
                        //key: doc name
                        //value: doc contents
                        for each word w in value:
                                EmitIntermediate(w, "1");
                reduce(String key, Iterator values)://累加
                        //key: a word
                        //values: a list of counts
                        int word_count = 0;
                        for each v...
                        
        改造的标签传播算法
                While(Condition is not satisfied)
                        数据聚合MapReduce任务
                        标签传播计算MapReduce任务
                数据聚合MapReduce任务（数据预处理）
                        与通常的MR任务不同，有两类输入数据
                                用户社交数据：<uid.list(uid)>的形式
                                用户的初始标签信息：<uid.list(word)>的形式
                        我们希望的形式（合并）
                                <uid.list(uid). list(word)>
                        典型的One-2-One join操作，我们采取标准的Reduce-side join的方法
                标签传播计算MapReduce任务
                        <uid.list(uid).list(word)>的形式
                        Map操作
                                解析values
                                        list uidList = parse(value)
                                        list wordList = parse(value)
                                标签传播
                                        for each u in uidList:
                                                EmitIntermediate(u, AsString(wordList):
                                                        如果是节点自身，传播f次
                        Reduce操作（收集过程）
                                key: uid
                                values: list(word)列表
                                
                                统计标签频次
                                计算标签权值（引入TF和IDF）
                                取TOP K

算法效果示例
        略
        

问答环节
        1. 当初7000万用户的用户图谱构建，用了多久
                1小时
        
        2. 收敛（最后会不会有所有用户标签一样）
                IDF解决一些太常见的信息含量低的词
                        抛弃
                        得分公式
                        
        3. 兴趣图谱 作为 新浪微博 是基础数据
                应该不会对外提供