社交媒体数据处理与社区发现的创新方法

# 社交媒体数据处理与社区发现的创新方法 ## 一、Twitter 流中首故事检测的学习事件概况法 ### 1.1 背景与问题提出 近年来，社交媒体发展迅猛，截至 2015 年 12 月 26 日，Twitter 平台活跃用户超 3 亿，日推文超 4 亿条。首故事检测（FSD）旨在识别未在已发布推文中报道过的事件的首份报告，对新事件检测意义重大。主流的 FSD 方法是在线聚类，如 SinglePass 算法，但存在效率低、性能差且未考虑事件相关特征的问题。 ### 1.2 相关工作 - **SinglePass 及其改进**：SinglePass 是代表性的增量聚类框架，被广泛应用。不过，其大量的相似度计算导致效率低下。为改进它，Petrovic 提出基于局部敏感哈希（LSH）的方法，能保证效果且成本恒定；还将释义融入 LSH 算法进一步提升检测效果。 - **Nugget - based 方法**：Qiu 提出的 Nugget - based 方法使用推文事件信息的三个元素作为事件的 Nugget，能降低 Cmin 值至 0.410，效率优于 P - LSH 方法，但该方法通过预设规则生成 Nugget 或概况，无法充分表达事件信息。 ### 1.3 事件概况法的首故事检测 #### 1.3.1 算法框架 事件概况法首故事检测算法（EP - FSD）旨在提高 SinglePass 的效率。检测推文前，系统用机器学习方法训练模型生成推文概况。新推文到达时，生成其概况并与各事件概况比较。若匹配则归为该事件，否则计算推文与各事件中所有推文的相似度，若低于阈值则为该事件的首故事。其框架如下： ```mermaid graph LR A[新推文到达] --> B[生成推文概况] B --> C{匹配事件概况?} C -- 是 --> D[归为该事件] C -- 否 --> E[计算相似度] E --> F{相似度低于阈值?} F -- 是 --> G[成为首故事] F -- 否 --> H[归为其他事件] ``` #### 1.3.2 学习事件概况的分类器 为检查每个单词是否符合事件概况要求，构建分类器。给定单词 w，提取其特征向量 fw，训练决策函数 G 以确定单词的标签 y。 \[y = G(fw)\] 其中，fw = (f1, f2, ..., fn) 是推文中单词的特征，y = 1 表示单词符合要求可加入概况，y = 0 表示不符合。 #### 1.3.3 特征设计 研究中考虑了 17 种独特特征，分为 4 组，具体如下表： |特征类型|编号|特征|描述|示例| | ---- | ---- | ---- | ---- | ---- | |术语特征 TF|1|isTitle|单词首字母大写|Nobel Prize| |术语特征 TF|2|isUp|单词字母全大写|MILLZ| |术语特征 TF|3|NotAlpha|包含非字母字符|F - 16, debate2012| |术语特征 TF|4|LenMore3|单词长度大于 3|play, happy| |术语特征 TF|5|NotWord|单词在字典中|cooooold| |术语特征 TF|6|Noun|是否为名词|Quantum| |元数据（MD）|7|Hashtag|是否在主题标签中|#HiphopAwards| |元数据（MD）|8|At|是否在 @ 中|@kendricklamar| |全局特征 GF|9|TF|词频|词频| |全局特征 GF|10|IEF|逆事件频率|IEF = log(N/EF)| |全局特征 GF|11|TF*IEF|TF 与 IEF 的乘积|TF*log(N/IEF)| |全局特征 GF|12|In2Events|单词出现在多个事件中|-| |面向事件的特征（EOF）|13|Name|是否为人名|Mo Yan| |面向事件的特征（EOF）|14|Location|是否为地名|MOSCOW| |面向事件的特征（EOF）|15|Time|是否为时间|2012| |面向事件的特征（EOF）|16|Action|是否为动作|debate| |面向事件的特征（EOF）|17|Concept|是否为维基百科实体|HiphopAwards| #### 1.3.4 概况生成 分类器训练完成后，新推文到达时，将每个单词输入分类器以确定是否可选为概况，从而生成推文概况。事件概况由该事件中所有推文的概况组成。 对于