Intro

在阅读完《ViSeq: Visual Analytics of Learning Sequence in Massive Open Online Courses》后觉得里面的参考文献[27]似乎更有帮助，于是精读了这篇文章：《Unsupervised Clickstream Clustering for User Behavior Analysis》，作以下笔记。

Unsupervised Clickstream Clustering for User Behavior Analysis

ABSTRACT

面向通用的在线服务（社交网络或众包服务），了解用户行为。

研究面向用户行为分析的无监督点击流聚类，建立了一个无监督的系统，从点击流数据（用户点击事件的痕迹）中捕捉用户行为，并以直观的方式可视化检测到的行为，通过划分相似图来识别相似用户的集群。

相似图上的分区（也就是聚类过程）利用迭代特征剪枝算法（iterative feature pruning）来捕捉用户集群中的自然层次结构，产生直观的特征便于可视化和理解。

INTRODUCTION

Clickstreams：用户操作生成的带有时间戳的事件序列。

点击流分析系统的要求：

在大的、杂乱的点击流数据集上可扩展和良好运行。
系统应该能够捕捉到先前未知的用户行为（即在没有预先定义类别或标签的情况下捕捉行为）
系统应该是交互式的，以直观易懂的方式呈现检测到的行为，来帮助其他人理解用户行为。

本文介绍一个实用的、可扩展的用户点击流行为分析工具的设计与评估。

使用点击流之间的相似性度量来构建用户之间的相似性图，捕捉用户的行为模式。

使用层次聚类的方法来检测最流行的用户行为模式，并使用迭代特征剪枝技术来消除每一个后续聚类层中主导特征的影响。

最终输出结果是一个行为聚类的层次结构，高层聚类代表更一般的用户行为模式，低层聚类进一步识别出在关键行为模式上存在差异的较小群体。

进一步使用卡方检验识别的统计特征可用于对行为聚类进行分类和标记的。

case studies：采用了来自Whisper和人人网的两个数据集——

在Whisper中识别出不同层次的“休眠用户”的行为模式，并根据相邻的行为集群对休眠用户进行有效的预测
研究Whisper中的用户屏蔽行为，发现大部分屏蔽行为是双向的，通常发生在私聊之后、与性暗示相关。
在人人网数据集中准确识别了95%的假账户，发现了使用不同账号攻击方法的用户小组。

从两个基准上评估该工具：

算法生成的行为集群是否易于理解（能够理解用户行为的含义）
用算法评估了生成的聚类的质量（优于K-means）

本文的三个主要贡献：

提出了一种新型无监督的在线用户行为建模方法。将详细的用户行为模型捕捉为可视化图中的层次簇，并自动生成直观的特性来解释每个行为集群的含义。
对两个大规模的点击流数据集（总共1.42亿次点击事件）进行了case studies，可以有效地帮助服务提供商识别意外的用户行为（人人网的恶意帐户、Whisper的恶俗会话），甚至可以预测用户未来的行为（Whisper中的休眠用户）。
对工具进行基准评估，显示该算法生成的聚类标签易于理解，并且我们的工具能够生成高精度的用户行为模型。

在线服务中的用户行为建模。
点击流分析：使用聚类技术来识别具有相似点击流活动的用户集群[8,25,27,29]，用于推断用户兴趣[25]或预测未来的行为[8]。
点击流可视化：点击事件序列[35]、点击转换[32]

CLICKSTREAM DATASETS

数据来源：Whisper和人人网

Whisper

一款流行的用于匿名社交信息的智能手机应用程序。

与Whisper的数据科学团队合作拿到的数据集：45天内99990名用户的1.36亿次点击事件（表1）

每个click事件都由userID、时间戳、事件类型和事件参数组成。

事件类型：33种，可分为6类：

浏览：浏览whispers用户，访问公共whisper feeds（热门/附近/最新）。
帐户：创建用户帐户并登录应用程序。
发布：发布原始的whisper和回复，点赞/点踩一个whisper，分享whisper，并为某个whisper标记话题。
聊天：发起聊天，屏蔽某用户，被屏蔽。
通知：收到关于自己的whisper被点赞/回复的通知，以及whisper推荐。
垃圾邮件：whisper被系统管理员检查或删除，标记他人的whisper为垃圾信息。此类事件均低于1%（在表2中省略了）。

其中25种是由用户发起的事件，其余8种是不需要用户操作的系统事件。表2显示了最流行的事件和绝对数量（以千为单位）和点击率。其中在聊天类事件下，最常见的事件是“屏蔽用户”和“被他人屏蔽”，这个在后面会进一步挖掘。

数据集里还有whisper发布的内容，将用于理解特定的用户行为和用户意图。

人人网

数据集（表1后半部分）：5998名普通用户和9994个Sybil帐户（百科解释：Sybil群体指代那些被恶意操控进行协同攻击的虚假账户，即利用社交网络中少数节点控制多个虚假身份，从而利用这些身份控制或影响网络的大量正常节点的特殊行为群体，有点像现在微博的僵尸粉）

每个click事件与whisper一样，也由userID、时间戳、事件类型和事件参数组成。

事件类型：55种，可分为8类：

社交：发送好友请求，接受或拒绝好友请求，删除好友。
照片：上传照片，组织相册，标记好友，浏览照片和撰写评论。
个人资料：浏览用户资料界面（人人网的个人资料可以被任何人浏览，但显示的信息受到所有者隐私设置的限制）。
分享：用户分享人人网内/外的视频、博客或照片的网址链接。
消息：状态更新和即时消息。
博客：阅读/撰写博客，发表评论。
通知：用户主动点击通知。
点赞：用户点赞（或点踩）某内容。

与Whisper不同的是，人人网不包含任何系统事件，如“接收通知”，所有事件都是由用户发起的。

表3显示了最流行的事件，普通用户和Sybil账户是分别计数的。后面会根据Sybil用户在某些数据上的不同来分析Sybil的攻击策略。

UNSUPERVISED USER BEHAVIOR MODELING

在高层次上，假设人们的行为自然形成集群，目标是把这些自然集群识别为行为模型。

用户集群是多维的、树形结构（图1）：最突出的特征用于将用户划分为高级类别，而不太重要的特征用于描述详细的子结构。

设计了一种迭代特征剪枝算法来捕获层次化的点击流集群：在高层次上将用户映射到一个相似度图中（节点是用户，边缘是相似度的权值），然后划分相似度图以识别具有相似点击流活动的用户集群。递归地划分新生成的集群，同时修剪用于度量点击流相似性的特征集，以生成层次化的结构。

Clickstream and Similarity Graph

Formatting User Clickstream

对于每个用户收集ta所有点击事件，形成一个单一的点击流。

是一个按到达顺序排序的离散事件序列，捕获点击流中的不同事件类型以及相邻两事件之间的时间间隔（图2）。然后使时间间隔离散化，将精确的时间间隔值映射为五个离散标识符：<1s, [1s, 1min], (1min, 1h], (1h, 1day],> 1day分别映射到g1~g5。

Clickstream Similarity Graph

聚类算法要基于相似图，所以需要一个相似度的度量。这里提到了他相似图方法的来源文献[29]：G. Wang, T. Konolige, C. Wilson, X. Wang, H. Zheng, and B. Y. Zhao. 2013b. You Are How You Click: Clickstream Analysis for Sybil Detection. In Proc. of USENIX Security.

然后后面就是《ViSeq：Visual Analytics of Learning Sequence in Massive Open Online Courses》里Data Preprocessing的内容。这里提到了polar distance的优点：更适合处理高度稀疏的向量，比较向量的“方向性”而不是“幅度”。

Feature Pruning based Clickstream Clustering

用迭代特征剪枝递归地划分相似图，在现有簇中识别细粒度行为簇。

Iterative Feature Pruning & Clustering

采用Divisive Hierarchical Clustering算法，分层聚类步骤在图1中描述，可以用于任意矩阵空间和发现任意的聚类形状。该算法的参考文献[13]： L. Kaufman and P. Rousseeuw. 2009. Finding groups in data: an introduction to cluster analysis. Vol. 344. John Wiley & Sons.

第一层的聚类中，点击流相似性是基于完整的特征集（所有k-grams的集合）来度量的。

然后执行特征修剪：识别形成父集群的主要特征，将它们从特征集中移除，并使用剩余的次要特征进一步划分父集群。比如在划分出C1后，进行特征选择以确定将用户分类到C1的关键特征（即那个关键的k-gram）。然后，在对C1进行进一步划分时，我们从特征集中去除这些k-grams，并用剩余的k-grams来计算新的相似图。

当所有新的集群无法进一步分割时（比如聚类质量达到一个最小的阈值），算法停止。

剪枝的关键步骤是找出形成父簇的主要特征（finding the primary features responsible for forming the parent cluster），用了卡方检验（Chi-square statistics） (χ2)——一种衡量特征在分离不同类数据实例时的区分能力的经典度量。（卡方检验参考了文献[33]：Yiming Yang and Jan O. Pedersen. 1997. A Comparative Study on Feature Selection in Text Categorization. In ICML.）

对于给定的一个集群C1，我们根据在C1内部和外部的用户分布情况来衡量每个特性的χ2得分。然后选出χ2得分最高的特征。经验数据显示χ2分布通常表现出“长尾”特性——只有少数主导特征得分较高。我们通过识别分布中的最低点（或转折点）自动选择顶部特征[22]。

Understanding the Behavioral Clusters

根据卡方检验选择的主要特征来推断出这个聚类的意义，可以作为集群形成的原因以及集群包含哪些用户行为的解释。通过识别卡方分布中的最低点（或转折点）自动选择顶部特征（selected features，这个后面要用）。

Determining the Number of Subclusters

对于每个父类簇（及其相似性图），我们的系统识别其中的自然子簇数：在不断地划分为更多的子簇时监控总体聚类质量的变化，当生成更多的子集群将不再提高集群质量时算法将停止。

评价聚类质量的指标：模块度（Modularity），用于测量簇内边缘到簇外边缘的密度。参考文献[4]：V. D. Blondel, J. Guillaume, R. Lambiotte, and E. Lefebvre. 2008. Fast unfolding of communities in large networks. JSTAT 2008, 10 (2008).

Cluster Visualization

建立了一个可视化工具展示用户行为聚类，回答一些关键问题：主要的行为类别是什么？哪种行为更普遍？不同类型的行为之间有什么关系？etc.

Visualization Interface

图3是可视化界面的截图，该工具用了D3.js开发，默认是用Packed Circle展示（子集群嵌套在其父集群中），圆圈大小反映了集群中的用户数量。

点击某一个聚类可以弹窗出一个信息窗口，比如图3中的弹窗显示了Cluster #1中的具体每个k-grams出现的频率和χ2得分。

Visualizing Whisper and Renren Clusters

图3和图4分别是Whisper和人人网数据集的可视化截图。

聚类过程中把模块度（Modularity）阈值设为0.01，到达阈值时算法停止。

对于Whisper数据集，系统生成了107个簇（包括根）的树层次结构，其中包含95个叶簇，最大树深为4。

对于人人网数据集，层次结构包含108个簇（95个叶簇），最大深度为4。

可视化工具只显示每个集群的选定特性（selected features）。80%的集群具有少于5个选定的特性，90%的集群具有少于10个的特性，表明流行的用户行为可以用少量的关键特征维度来表征。（不然的话比如whisper有80903个不同的k-grams）

EVALUATION: CLUSTER LABELS

接下来分析Whisper和人人网的行为集群并证明了它们在识别意外行为和预测未来活动方面的有效性。

评估包括三个步骤：

为了评估理解和标记行为集群的容易程度，进行了一项用户研究。要求参与者阅读集群信息并描述相应的用户行为，然后检查不同的人是否给出了一致的描述。
对异常行为集群进行了深入的案例研究，并为这两个网络提供了新的见解。
评估集群的质量。

User Study to Interpret Clusters

要求参与者使用可视化工具（Packed Circle界面）浏览行为集群，只使用Whisper集群（图3），只查看覆盖90%用户的顶级集群（总共37个集群）。

User Study Results

收集了参与者对37组个集群的555个描述（每个集群15个描述），发现行为集群对参与者来说是可以理解的。

然后为了了解描述的“一致性”，让3名外部专家独立阅读和评估收集的描述。对于每个集群，专家读取所有15个描述并打上一致性分数（范围0到1）=一致性描述的数量/所有描述的数量。一致性得分分布显示在图8。

在检查一致性得分较低的集群时有两个关键的观察结果：

较低级别的集群更难解释，图9显示聚类层次越低，平均一致性得分越低，说明较低级别的集群表示更具体的甚至是难以描述的异常行为。
具有更多selected features的簇更难解释。

最后根据用户研究的描述和作者自己的解释，在Whisper和人人网数据集的顶级集群中添加了短标签（就是图3和图4里那些命名）。

EVALUATION: CASE STUDIES

两个目标：

通过分析集群中的用户行为来验证集群标签的正确性。
探讨有趣的（或意想不到的）用户行为，并展示用户行为模型的预测能力。

Case Study 1: Inactive Whisper Users

Whisper Cluster#2，标签是不活跃用户（inactive users），selecte features几乎是由“接收通知”事件组成，表明这些用户在app中根本不活跃。图10是用户在点击流中进行了活跃事件的天数，明显这一类用户是很少的。

这里表明算法成功地将休眠用户分组到一个单独的子集群中，并且不是少数群体而是第二大群体。

Predicting Dormant Users

高层次上的思路：Whisper使用用户最近的点击流来构建行为模型，并定期（例如每月）更新模型。本文的假设是处于“非活动”集群中的用户更有可能完全休眠，因此可以使用非活动集群来预测未来的休眠用户。通过调查“非活动”集群中的用户是否会随时间迁移到“休眠”集群来验证这一假设。

文中的不活跃（inactive）用户和休眠（dormant）用户是不同的两类。

表4比较来自两个相邻快照的集群，以确定用户迁移到休眠集群的可能性。将点击流数据分成三个快照，然后记录从两个相邻的快照迁移到休眠集群的用户数，显示出处于半休眠集群中的用户比其他用户更容易迁移到休眠集群中。

Case Study 2: Hostile Behaviors of Whisper Chatters

Whisper Cluster#4，在私聊时经常屏蔽某些人。图11显示这个集群中的用户执行屏蔽操作的频率要高得多。

探讨屏蔽事件的可能原因：假设是Cluster#4中的用户更容易发布公开的Whisper，从而吸引不必要的聊天者来骚扰他们。表5中列出了Cluster#4内外用户的行为统计数据，Cluster#4中的用户更积极地发布公开的Whisper，会吸引更多人的点赞和回复，用了具有统计学意义的Welch双样本T检验（Welch two-sample t-tests）显示Cluster#4内外用户的显著不同。

表6列出了Cluster#4内外用户的热门关键字，关键字根据它们与集群的关联程度进行排序。显示出Cluster#4发布的Whisper有更多的露骨信息。

Users Who Get Blocked

在Cluster#4里有1412个用户经常被他人屏蔽（图12里的4-2-1），然后图13显示这些人就是经常被屏蔽。现在的问题是：双向屏蔽是不是经常发生的？不过文中的数据集不能直接记录到双向屏蔽，然后采用了一种近似的方法：若互相屏蔽间隔在1h内就把这两个事件配对。然后图14就显示Cluster#4中有更多的成对屏蔽事件，特别是4-2-1。

Case Study 3: Renren Sybil Accounts

分析人人网中的Sybil账户，系统成功将95%的真正Sybil账户分在了一块。selected features表明倾向于更多地发送好友请求。

此外，在Sybil账户发现了更多的子集群，表明有多种不同的攻击策略（表7）。

EVALUATION: CLUSTER QUALITY

将本文算法与现有的聚类方法进行了比较。

Clustering Quality

RQ：给定一个小样本的已知用户，如何准确地检索到相同类型的其他用户？

Experiment Setups

举例：假设知道一个小样本的Sybil账户（x%），使用已知样本作为seeds，对人人网数据集的行为集群进行着色。任何包含已知Sybil的集群都将被着色为Sybil-cluster。然后使用两个指标来评估准确性：Precision（Sybil-cluster中真正的Sybil帐户的用户百分比）和Recall（Sybil-cluster中捕获的真实Sybil账户的百分比，也就是除去了原有已知样本的数量）。然后x取不同的值，重复实验10次。

Comparison Baselines

与K-Means和层次聚类两种算法作对比。对于K的取值采用了最高模块度（modularity）的值。

Results

图15展示了三种算法在三类用户上的Precision和Recall，表明本算法质量较高。

CONCLUSION & FUTURE WORK

总结就是重述了一遍INTRODUCTION里的话。

Broader Applications

可以推广到在线社交网络之外，可以从他们的HTTP日志中提取对应的“用户事件”。对于其他服务，特定事件将取决于服务功能。