社交网络挖掘-Note3
9-用户行为分析 Behavior Analytics
目标是:To analyze, model, and predict individual and collective behavior
个体行为分析
对于一个用户行为分析,我们需要:可观测的行为、一些特征、发现他们之间的相关性、以及如何度量这些模型。
原 PPT 上介绍了一下格兰杰因果检验,没学过时间序列不太了解 Orz
个体行为建模
个体行为预测
上面的三种个体行为分类,其实都可以看作是一个 链路预测问题。
大体上可以分为两类:一类基于两个节点之前的相似性,一类基于两个节点之间的路径特征。
Node Neighborhood-Based Methods
可以根据 node 之间的相似性来度量,下面枚举了一些结构等价性(基于邻居节点的关系)的度量指标
Path-Based Measures
这里给出了一些思路:一是考虑两个节点之间的路径长度,按照路径的长度指数衰减;二是考虑随机游走,计算从一个节点随机游走到另一个节点的概率
机器学习方法
当然,连接预测的问题等价于一个二分类问题,可以采用一些经典的分类模型:决策树、KNN、贝叶斯、SVM、NN……
群体行为 Collective Behavior 分析
群体⾏为是指⼀个群体中的个体表现出相似的⾏为⽅式,这 种相似⾏为可以是计划并协调好的,也可以是⾃发形成的。通常将群体分成多个个体,对这些个体单独分析后,将分析结果汇聚成⼀个群体的⾏为结果
例如,社交媒体上的群体迁移⾏为 Users migrate
网站迁移:在t1时刻,某⽤户同时是网站1和网站2的成员,但在t2>t1时刻,该 ⽤户只是网站2的成员,则说明该⽤户从网站1迁移到了网站2
注意⼒迁移:在t1时刻,某⽤户同时是网站1和网站2的成员,且都属于活跃状态, 但在t2>t1时刻,该⽤户仅在网站2保持活跃,则说明该⽤户的注意 ⼒从网站1迁移到了网址2
注意⼒迁移⽐网站迁移更容易观测到
迁移行为的特征
- 活跃度越高的用户迁移概率越小
- 社交圈越大的用户迁移概率越小
- 等级 Rank 越高的用户迁移概率越小
群体⾏为模型
线性/逻辑回归模型
网络模型
⼩世界模型
侧重表达较⼩的平均最短路径
优先链接模型
侧重表达幂律分布
用户画像
用户画像过程
1、确定画像的⽤户对象和目标
- 给谁画像?画什么像?为什么画像?期望画像的结果/⺫标是什么?
2、收集画像数据
网络⾏为数据:活跃⼈数、⻚⾯浏览量、⻚⾯停留时间、访问时⻓、 社交数据等
⽤户偏好数据:浏览/收藏的内容、点评内容、品牌偏好等
⽤户交易数据:订单量、订单价、回头率、流失率等
3、⽤户建模
- 对上阶段收集到的数据进⾏处理,⽤统计模型等机器学习⽅法产⽣ ⽤户的画像标签,以备后续的应⽤使⽤
用户画像的应用价值
精准营销:通过画像将⽤户群体切割成更细的粒度,辅以短信、推 送、邮件、活动等⼿段,驱以关怀、挽回、激励等策略,以提⾼营 销业绩
客户关系管理(CRM):精准的⽤户画像为设计有效的企业与客 户互动策略提供科学指导,能有效提⾼⽤户黏度和企业品牌⼒
数据应⽤:⽤户画像是很多数据产品的基础,如推荐系统、⼲告系 统,精准的⼲告投放基于⼀系列⼈⼝统计相关的标签,性别、年龄、 学历、兴趣偏好、⼿机等
⽤户分析:早期,产品经理通过⽤户调研和访谈的形式了解⽤户各 种属性特征,在产品⽤户量扩⼤后,应以⽤户画像配合传统的⽤户 研究,以进⾏深⼊、精准的统计与分析
数据挖掘:⽤户画像可以理解为业务层⾯的数据仓库,各类标签是 多维分析的天然要素,分析系统的数据查询平台要和这些数据打通
用户标签的一般来源
⽤户⾃⼰打的标签
- ⽆论是⽤户给⾃⼰打的标签(如新浪微博标签)还是⽤户对各类网络 资源(新闻、电影、⾳乐等)打的标签
利⽤⽤户注册数据
- 网站或App⼀般都需要新注册⽤户填⼀些个⼈基本信息,甚⾄选择⼀ 些个⼈偏好标签,这些是基本画像标签的来源
利⽤⽤户社交网络数据
- 所在社交群的名称、类型,借⽤好友的特征标签等
利⽤⽤户发⾔数据
- 关于⽤户对新闻的评论、对购买商品/服务的评论等⽂字内容,都可 从中抽取关键词(例如⽤TF-IDF)作为标签
利⽤⽤户网络“消费”的物品
⽤户看过的电影所属的类型、演员、导演、国别等
⽤户点赞过的图⽚标签(如Flickr这样的图⽚社区都提供了图⽚标注 服务)
⽤户听过/下载过的歌曲类型、演唱者、作者、语⾔等
⽤户购买过的商品(⼿机、Pad等)品牌、国别等
⽤户经常浏览网站的类型、主题等
⽤户的POI/LBS所属的类型、⻛格等
⽤户玩过的游戏类型,所扮演⾓⾊类型等
用户/项目标签画像的挑战
标签缺失
- 很多⽤户出于隐私保护的考虑不使⽤标签
标签不准、不细
“宝强”“宝宝”是指王宝强?
“球迷”有⾜够的个性刻画能⼒么?
标签不完整
- “埃航”“失事⻜机”能否补充“波⾳”“737MAX”?
标签语义失配
- “旅游”与“摄影”,“复旦”与“交⼤”能否做到语义关联?
10-博弈论
复杂社会系统(网络结构)中连通性的含义体现在 两⽅⾯
- 网络结构:通过个体(结点)之间的联系(边)来体现, 包括社会关系、相互协作与交互等等
- 个体之间的相互依存:任何⼈的⾏为结果⾄少潜在地依赖 于其他⼈的联合⾏为,亦可看作是 ⾏为层次的关联性
后面这一点是博弈论的研究内容,因此课程这一部分介绍了一些博弈论。
博弈策略
- 博弈论的基本要素
1、存在不少于两⼈的博弈参与⼈ 参与⼈ 2、每个参与⼈都有⼀组⾏为决策的备选项 策略集 3、每种⾏为决策都会让参与⼈得到⼀个收益(回报),该收益也受其他参与⼈的决策影响,每个参与⼈都倾向于获得更⼤的收益 回报
博弈论⼯具就是⽤来推理参与⼈如何进⾏⾏为决策
⼀般⽽⾔,⼀个参与⼈都会在预测其他参与⼈的⾏ 为决策后才做出使⾃⼰收益最⼤的⾏为决策
下面介绍了两点经典的案例:其一为囚徒困境;其二很类似,「复习-报告」博弈,即你和搭档都可以选择准备考试/Pre,若不论对方选择什么,你选择考试总是一个较优的策略,那么最终的结果两个人都会准备考试,而这样可能并非一个最佳的结果。
这里的核心问题和囚徒困境一样,双方无法交流/达成共识,因此在个体的私利之下很难建立合作。
下面形式化的介绍一些概念
设 S 和 T 表示两个人的策略,\(P_1(S,T), P_2(S,T)\) 分别表示两人在策略组 \((S,T)\) 时的收益
若对于 2 的策略 T,1 选择策略 S 取得的收益达到最大,则称其为 最佳应对 \[ P_1(S,T)\ge P_1(S',T) \]
1 的最佳应对可能不止一个,若上面的不等式严格成立,则称策略 S 为 严格最佳应对
参与⼈1的 占优策略 是指该策略对参与⼈2的每⼀项策略都是最佳应对
参与⼈1的 严格占优策略 是指该策略对参与⼈2的每⼀项策略都是严格 最佳应对
严格占优策略最多只有⼀个,⽽占优策略可能会有多个。如果⼀个参与 ⼈存在严格占优策略,则很容易预测其⾏为决策
纳什均衡
定义:假定参与⼈1选择策略S,参与⼈2选择 策略T,若S是T的最佳应对,同时T也是S的最 佳应对,则称策略组(S,T)是⼀个纳什均衡
⾯对纳什均衡,任何参与⼈都没有动⼒选择 其他策略
如果每个参与⼈都相信对⽅在博弈中实际会 采取构成纳什均衡的某个策略,则他/她就有 动机采⽤能达成这个纳什均衡的相应策略
上面是一个简单化的例子,即仅存在一个纳什均衡;而当存在多个均衡策略的情况下,就涉及到 协调博弈
聚点理论focal point
学者谢林指出,当出现多重均衡时,如果还有某种⾃然原因使 得参与⼈倾向于选择其中某个均衡策略时,就能解决决策困惑
⽰例:⼀条没有划线的较窄的道路上有两辆⻋相向⽽⾏,到底是 ⾛左边还是⾛右边才能避免碰撞呢?
如果是两个中国⼈开⻋会避免碰撞么?
如果是⼀个中国⼈,⼀个⽇本⼈呢?
总结一下,上面区分了几种不同的存在多重均衡的情况
- 将两个人的选择相同的情况理解成「合作」,而相反则是「不合作」,不合作的收益为 0,这就存在两个均衡点。若两个均衡点中,其一对于双方都是好的,则为 聚点相同;若两人的 习惯偏好 不同,则演变为所谓 性别战
- 两种策略之间存在着差异,其中一个策略有着较高的风险(对应于高收益),与上面不同的是,这里若是「不合作」选择第风险的一方仍然可以得到一定的回报而选择高风险则略的一方则一无所获;观察上面的收益矩阵,其与囚徒困境不一样的地方在于其不存在严格占优策略,双方并没有陷入那样的困境中;然而在这种 猎⿅博弈 的场景下,双方还是因为担忧对方所选的策略而更倾向于选择风险低的那个决策,即成为 懦夫博弈
- 资源总量是有限的,因此只能进行分配,而这里有趣的一点在于,双方均选择鹰派策略的话,收益均为 0,而一方鹰派一方鸽派,双方都会有一定的收益;这里的困境在于,当一方选择鹰派策略的情况下,另一方的 最佳应对 是选择鸽派(不然是一无所获),感觉像是面对流氓的无可奈何;这被称为 鹰鸽博弈
混合策略
对于不存在纳什均衡的博弈,在参与⼈的策略集中 引⼊随机性,可以更准确地预测其决策⾏为
纳什的研究结果认为:当参与⼈的策略选择中引⼊ 随机性后,博弈总会存在均衡
攻防博弈
攻击⽅有A与B两种攻击策略,防守⽅对应有防守A与B两 种策略
如果防守⽅的策略正好对应攻击⽅的策略,则防守⽅获得 较⾼收益;没有对应上,则攻击⽅获得较⾼收益
看一个例子:两人各一枚硬币,若相同则 1 获胜,若相反则 2 获胜;这里,参与人的总收益为 0,是 零和博弈 ;这个时候,明显不存在纳什均衡。
收益矩阵表明,任何参与⼈知道了对⽅策略后都会做出相应 举措来使⾃⼰收益成为+1,两⼈不可能达成⼀致
因此,参与⼈都希望能迷惑对⼿,使其难以预测⾃⼰的⾏为
- 现实案例:诺曼底登陆
如果每个参与⼈不是选择纯策略H或T,⽽是选择⼀个出⽰H 的概率(引⼊随机性),⼜会产⽣怎样的博弈?
假设参与⼈1选择H策略的概率为p,则其选择T的概率为1-p
同理,假设参与⼈2选择H策略的概率为q,其选择T的概率为 1-q
两个参与⼈的策略表⽰变成了选择概率p与q,涉及H与T的混 合,因此称为 混合策略
在此设定下,即便某个参与⼈选择了某种纯粹策略H或T,其 收益仍然是随机的
假设参与⼈1选择H,则其收益期望是
-1q+1(1-q)=1-2q
假设参与⼈1选择T,则其收益期望是
1q+(-1)(1-q)=2q-1
混合策略博弈中,能否产⽣纳什均衡?怎样才能产⽣纳什均 衡?
若1-2q≠2q-1,则参与⼈1要么选择H要么选择T(回到了 纯策略博弈), 此时不会有纳什均衡。
只有1-2q=2q-1,即q=1/2时,才会产⽣纳什均衡
当q=1/2时,参与⼈1选择H或T的收益都没有区别,即占不到便宜
该结论解释了为什么博弈的⼀⽅希望通过随机化⾃⼰的⾏为来让 其⽆法准确判断⾃⼰的⾏为,使得对⽅对两个策略的取舍⽆差异, 从⽽不让对⽅占便宜
现实时间中的混合策略博弈案例
猜拳是⽯头、剪⼑还是布?
发球到对⽅哪个区域?
打牌时出什么牌?
11-推荐系统 Recommendation in Social Media
If interested, see two recent conference tutorials
SIGKDD2014, Recommendation in Social Media
RecSys2014, Personalized Location Recommendation
推荐系统简介
推荐算法的本质是通过⼀定的⽅式将⽤户和物品联系起来,⼀个推荐算法可以理解为学习如下的函数 \[ \arg\max_{i\in I}p(i|u)\\ \] 或者是 \[ f:U\times I\to \mathbf{R} \] 推荐系统的挑战
冷启动(cold-start)
- 新加⼊系统的⽤户和物品没有历史信息(如购买、评价记录),因此很 难推断⽤户的喜好,或者物品(项目)会被哪些⼈喜欢
数据稀疏
- 系统整体缺乏充⾜的历史信息,⽽不仅是缺少某(⼏)个⽤户的历史信息; 例如,如果系统中只有少数⽤户有很多评分记录,⼤多数⽤户只有很少 的评分记录,则系统⾯临数据稀疏问题
网络攻击
- 例如⿊客伪造评分记录
隐私保护
- ⽤户个⼈的信息被系统知道得越多,推荐就越准确,但这和个⼈隐私保 护⽭盾
解释说明
- 系统缺少向客户解释推荐某些物品的原因
经典推荐算法
基于内容的推荐 content-based
例如,在豆瓣电影中,已有对于每部电影的标签,而我们可以基于用户的历史记录得到用户的个性化标签,从而基于用户和电影之间的相似度做推荐。
协同过滤(collaborative filtering)
Collaborative filtering: the process of selecting information or patterns using techniques involving collaboration among multiple agents, viewpoints, data sources, etc.
Advantage: we don’t need to have additional information about the users or content of the items. Users’ rating or purchase history is the only information that is needed to work
更为著名的应该是协同过滤,其可以分为
- 基于记忆 Memory-based : Recommendation is directly based on previous ratings in the stored matrix that describes user-item relations
- 基于用户:基于⽤户的历史评分记录 来刻画⽤户间的相似性,相似⽤户对某 项⺫的评分可以作为⺫标⽤户对该项项的评分依据
- 基于项目:基于项目历史的被评分记 录来刻画项目间的相似性,目标⽤户对相似项目的评分可以作为目标⽤户对本项目的评分依据
- 基于模型:学习出能刻画⽤户评分⾏为的模型 Assumes that an underlying model (hypothesis) governs how users rate items.
Item-based CF
基于 memory 的协同过滤比较简单:比如对于一个用户 u 来说,我们希望预测其对于项目 i 的打分;那么我们可以考虑和这个用户最相近的若干用户,计算这些用户对于项目 i 的打分,具体公式如下:
Model-Based Collaborative Filtering
在基于 memory 的 CF 中,We predict the missing ratings based on similarities between users or items,可以说是 model-free 的;自然,在基于 model 的 CF 中,We assume that an underlying model governs how users rate
因此,我们需要基于历史数据(评分矩阵)训练这一模型,一个比较常见的方式是 SVD 分解。下面先介绍一些数理基础
想法就是对于已有的评分矩阵 X,不考虑其稀疏性,我们希望通过,我们希望得到该矩阵的一个低秩近似;想法类似于 SVD 分解,考虑到算法复杂度,更常用的可能是矩阵分解 MF 的算法,得到 loss 的形式化表述(一般还要加上一个正则项),并利用 GD 算法近似求解。
课上还介绍了另一种基于矩阵分解的模型:贝叶斯个性化排序 BPR,和上述矩阵分析的不同在于目标函数上的区别。具体见相关材料
群体推荐
有时候我们需要对一个群体进行推荐:例如和朋友一起看的电影、家庭的旅游地点、同事聚餐的餐厅等。想法自然是从个体的满意程度(评分)出发进行综合,可以有一下的几种考量
社会化推荐 Recommendation Using Social Context
包括三种面向
Recommendation Using Social Context Alone:仅仅利用网络信息,参见第 9 章中个体行为分析,即链路预测/推荐
Extending Classical Methods 使⽤评分记录和社会信息:采用公式 \[ r_{u,i}=\sum_{v\in N(u)}w_{u,v}r_{v,i} \] 与基于用户的 CF 相比,区别只是将用社交关系来刻画两个用户之间的相似程度。
Recommendation Constrained by Social Context 使用社会信息限制推荐: \[ r_{u,i}=\bar r_{u}+{\sum_{v\in N(u)\cap F(u)}sim(u,v)(r_{v,i}-\bar r_{v})\over\sum_{v\in N(u)\cap F(u)}sim(u,v)} \] 其中 \(F(u)\) 表示与 u 评分记录相近的用户,即这里协同过滤要求从评分相近的用户中,基于社交网络删选出那些邻居用户,以此来估计 u 对于 i 的评分。
基于知识的推荐
引入额外的知识
- 基于约束:设计人际交互界面,让用户输入或者选择其想要的物品属性,将其组成约束条件(规则集合),使得推荐变成一个从候选物品中选择满足约束条件集合的问题。例子如京东/淘宝的搜索
- 基于个案:先通过某种传统推荐算法产⽣⼀组推荐候选物品给⽤户,让⽤户从候选组中先选择⼀个相对满意的物品作为待推荐物品的参照,系统通过物品间的相似性计算找出其他与参照物品⾼度相似的候选物品,推送给⽤户让其再进⾏评价,通过多次与⽤户的迭代交互,最终产⽣⽤户最想要的物品。想法是根据反馈进行多次推荐?
上面的一些思路其实还是基于物品的标签属性,其面临一些问题
- 物品知识的获取:系统需要人工构建知识,对长尾实体的覆盖有限
- 用户知识的获取:系统需要用户输入信息,甚至要反复交互,体验感差
于是出现了基于 知识图谱 的推荐。形式化定义 \[ \arg\max_{i\in I}p(i|u, knowledge(i)) \] 算法分类:
- 显式画像:从知识图谱中直接找到的关联(例如两部电影 的共同属性)作为刻画两个物品相关性的依据
- 隐式画像:利⽤基于深度神经⺴络的嵌⼊embedding向 量来表⽰物品,物品间的相似度计算基于其对应嵌⼊向量在向量空间中的距离
跨领域推荐
可解释推荐
推荐系统的可解释性很重要
推荐性能评价
离线实验
通过⽇志系统获得⽤户⾏为数据,产⽣统⼀数据(样本)集
将数据集分为训练集和测试集
⽤训练集训练出模型后在测试集上检验推荐效果
⽤户调查
- 为了获取⽤户真实的满意度
在线实验
将推荐系统(算法)上线做 AB测试,与其他算法进⾏⽐较
测试⽤户会被分组,体验不同的推荐算法
⼀个新的推荐算法最终上线,需要完成上述3步:
⽤离线实验证明其在离线指标上优于现有算法
通过⽤户调查确定⽤户对其满意度不低于现有算法
通过AB测试确定其在核⼼指标上优于现有算法
把推荐看成是不同的任务,可能有不同的指标
- Predictive accuracy - Metrics measure error rate
- Classification Accuracy: Precision and Recall
- Evaluating Ranking of Recommendation
12-应用案例
这一章介绍了一些应用案例,和课程 PJ 联系起来
Flickr社交网络分析
Cha M, Mislove A, Gummadi K P. A measurement-driven analysis of information propagation in the flickr social network. In WWW2009.
分析问题(目标)
How widely does information spread in the Flickr social network? Do popular pictures gather fans from different parts of the network or is their popularity limited to a certain region?
How quickly does information spread through the social network? How long after the upload of a photo do fans mark it as a favorite?
Does information in Flickr flow along its social network links? What fraction of a photo’s fans discovered the photo through a friend? How long does this process take? By what other mechanisms do fans discover their favorite photos?
爬取⽅式
- Start with a randomly selected Flickr user and followed all of the friends links in the forward direction in a breadth first search fashion.
- To capture the dynamics of friends’ relationships, visit all users in the previous day’s social network graph and recorded any newly created or removed friend links or users.
- Collect information on the favorite photos of the Flickr users.
分析结果:流⾏图⽚涨粉的⻓期趋势
- First, many photos do show an active rise in popularity during the first few days after they are uploaded.
- Second, after the first few (10-20) days, most pictures, enter a period of steady linear growth. The median growth rate does not show any sign of slowing down even after 1 or 2 years
- For a majority of pictures, over 40% of fans were acquired after the first 100 days. Conversely, our analysis suggests that Flickr users take a long period of time to find out about interesting pictures.
- A majority of the less-popular photos attract their limited fan population early on during their lifetime, and they become dormant after the first few months.
Twitter 社交网络分析
Kwak, H, et al. “What is Twitter, a Social Network or News Media?.” In Figure 1: Number of followings and followers WWW2010.
下面的两个案例主要给我们的 PJ 提供了一些思路
微博好友推荐
数据获取
利⽤微博提供的API或⾃⼰写爬⾍来获取
数据爬取策略
网络关系爬取:先选取种⼦⽤户结点,再⽤⼲度优先策略爬取邻 居结点(爬⼏之内的邻居结点?)
⽤户发⾔内容爬取
将目标⽤户的微博列表全都爬下来
通过关键词定位⼀些微博热帖,将其转发/回复的微博⽤户信息爬下 来,包括转发路径数
基于共现的tag embedding
利⽤word embedding模型(word2vec)为每个标签⽣成反映 标签共现特征的embedding向量
每个⽤户的表⽰向量可以⽤其所有tag embedding的加权均 值表⽰
没有标签的⽤户可以应⽤标签传播算法为其⽣成标签
基于⽤户表⽰向量产⽣推荐结果
两个⽤户的表⽰向量余弦距离⾮常接近的话就值得相互推荐为好友
两个⽤户的表⽰向量前后串联,每⼀维作为分类模型的特征套上经 典分类模型来产⽣预测结果(逻辑回归或SVM),即预测两⼈之间 是否应该存在⼀条好友链接
两个⽤户的表⽰向量灌⼊深度神经网络产⽣预测结果
样本获取
正负样本⽐例设置
对于测试集中的⼀个⽤户,选取其多少(⽐例)的微博好 友作为未知待测的正样本,剩下的则作为已知的好友关系?
实验评测
对于⼀个推荐问题,应该以⼀个⽤户为单位,基于推荐给 该⽤户的所有好友真假来计算推荐性能得分,最后取全体 测试⽤户的得分均值
有多少条推荐记录的测试⽤户才考虑?
对于⼀个⼆分类问题(预测链接存在or不存在),则可以 采⽤相关的⼆分类预测指标,则基于所有⽤户对(“⽤户 -项目”对)的真假来计算总体性能分数
⾖瓣电影推荐
- 数据获取
- 利⽤网站提供的API或者公开的知识图谱
- ⾃⼰写爬⾍
- 数据爬取策略
- 从⽤户出发:通过某种原则选择种⼦⽤户,将这些⽤户评论(评分) 过的电影都爬下来
- 从电影出发:通过某种原则选择种⼦电影,将评论(评分)这些电影 的所有⽤户数据都爬下来
- 若不能爬取全集(代价太⼤),则需设定⼀个爬取范围(终⽌条件)
- 除了评论(评分),还有什么价值数据可以爬?
- ⽤户/电影标签、电影导演/演员/制⽚等信息、⽤户的关注列表…
- 数据爬取策略
- 推荐⽅法与特征提取
- 基于协同过滤
- 基于内容
- 混合⽅法
- 基于DNN嵌⼊内容特征与历史信息
- 如何提取⽂本语义(知识)信息?:CNN
- 如何集成历史观影记录⽣成⽤户偏好:RNN(LSTM, GRU)
- 再利⽤已知的评分记录来指导神经网络的学习
- 样本获取与⽣成
- 正负样本如何判定?什么是喜欢的电影?什么是不喜欢的电影?那没有评分过的电影 是喜欢还是不喜欢?
- 有多少条电影推荐记录的测试⽤户才考虑?
- 正负样本的⽐例怎样才合适?