结合EM和DBSCAN算法对网站用户行为进行建模（Modelling website user behaviors by combining the EM and DBSCAN algorithms）_用户行为建模 项目

Modelling website user behaviors by combining the EM and DBSCAN algorithms

结合EM和DBSCAN算法对网站用户行为进行建模
摘要：Web日志可以提供相应网站的用户访问模式的丰富信息，只要对它们进行适当的分析。但是，由于大量的日志量和集群环境中日志文件的分布，要找到底层日志数据中隐藏的有趣模式并非易事。本文提出了一种基于密度的带噪声应用空间聚类(DBSCAN)算法和期望最大化(EM)算法的迭代方法，用于聚类web用户会话。每个集群对应一个或多个web用户活动。通过频繁模式挖掘和顺序模式挖掘技术，识别出每个集群的唯一用户访问模式。与EM算法、DBSCAN算法和kmeans算法的聚类结果相比，该方法在web会话挖掘中准确率更高，在识别聚类随时间变化方面更有效。我们证明了所实现的系统不仅能够识别常见的用户行为，而且能够识别网络攻击。
关键词： 聚类；web usage mining；

1. 背景

（1）会议/刊物级别

Published in: 2016 Moratuwa Engineering Research Conference (MERCon)
CCF None

（2）作者团队

（3）研究背景

Web日志记录用户访问网站时的活动和网站资源使用情况。Web访问日志文件包含数百万条日志记录。每个日志文件包含一组与用户会话相对应的条目。每个这样的条目包含用户的IP地址、HTTP状态码、时间戳、web请求URI、用户代理和HTTP请求类型。在这些低级数据之间可能隐藏着一些有趣的模式。这些有趣的模式包括关于攻击、黑客活动、用户访问类型等的信息。一个典型的网站有大量的注册和/或访客用户。它收集了大量的日志文件[1]中的数据。这些日志文件很难处理，实际上手工破译来检索这些有用的信息[2]是不可行的。因此，日志文件被保留在一边，只在系统遭受重大攻击(造成严重破坏)后使用。然而，识别出的访问模式可以用来分析系统性能和网络流量，改进系统设计，对网站设计更改做出决策，模拟用户行为和处理商业智能。

许多用户每天都会访问一个网站。它们可能在系统上执行例行操作，也可能不执行例行操作。如果系统开发人员和系统管理员能够确定实际的用户导航模式和他们在网站上执行的操作，他们就能够通过识别恶意用户行为来改善网站及其人机交互(HCI)组件，以及系统安全性。此外，识别网站中的用户行为模式有助于识别系统的后门和漏洞，这有助于防止系统被用户和黑客利用。此外，我们可以发现系统中一些失败或中断的事务，并找出可能的原因[3]。在一个网络会话中，用户可以选择许多访问路径。我们期望普通用户能够使用其中的一些访问路径，但也可能存在普通用户不会使用的其他有趣的访问路径。这表明该网站存在恶意活动。在识别用户访问模式方面采用了许多技术。其中包括k均值聚类、基于密度的噪音应用空间聚类(DBSCAN)、Apriori算法和Web访问模式树(WAP-tree)[4][7]。拒绝类是其中最流行的一种。k-means算法和PSO算法聚类web日志的局限性在于，专家没有足够的信息来确定数据在初始阶段[8]生成的聚类数量。像k-means, DBSCAN这样的聚类算法需要密度区域上的聚类计数和最小点计数等参数。这些参数值随数据集的不同而不同。领域专家很难为这些参数给出正确的值。使用集群，可以根据用户的访问模式对不同的用户进行集群。在集群中，只有具有相似属性的节点被聚在一起。但是，要创建入侵者检测系统，需要识别不同集群访问模式之间的差异。因此，需要考虑将集群分组在一起的访问路径的公共部分以及区分集群的访问路径的属性。

本文提出了一种新的网络日志聚类和用户访问模式识别机制。首先通过日志文件清理模块发送日志。通过删除不必要的数据来净化日志，并将其转换为通用格式。然后创建会话。由于聚类数和聚类中的会话数是未知的，所以很多聚类算法无法单独使用。

因此，利用EM和DBSCAN算法(EM+DBSCAN)对web会话进行聚类，以识别web日志中的用户访问模式。最后在签名模块中，从每个集群的会话(访问的网页序列)中为每个集群选择一个唯一的签名。每个签名由特定集群的唯一页面或页面访问的唯一序列组成。这些签名用于定义用户行为模型。系统结果进行了定量和定性的评估，这是在三个不同领域的网站进行的:非营利组织，金融机构和教育机构。他们发现了一些有趣的模式和攻击，其中一些甚至连网站管理员都不知道。本文的其余部分组织如下。第2节回顾了关于web日志预处理和web会话聚类的相关工作。所实现的系统将在第3节中描述。第4节讨论了制度的有效性，第5节总结了全文。

2. 相关工作

如上所述，web日志聚类和识别用户导航模式主要包括两个步骤——web日志预处理和web会话聚类[9]。下面的小节描述了每个步骤的相关工作。

2.1 web日志预处理

在web访问日志中，有必要进行初始清理，因为在数据挖掘时，有些数据并不令人感兴趣。在日志配置中，可能存在不相关和冗余的信息，或者嘈杂和不可靠的数据。在访问日志中，由于日志系统或服务器配置的原因，数据可能会重复，并且日志数据可能有不同的级别。日志是半结构化的，不同的日志库和系统可以发现不同的日志记录模式。因此，web日志数据在使用之前需要进行处理。

Web日志预处理包括两个主要单元:日志数据清理和用户会话识别。日志数据清理步骤包括数据选择、归一化、清理和转换[10]。Web日志数据预处理是一个复杂的过程，需要花费整个日志挖掘过程[10]一半以上的时间。数据清理的目的是去除异常值或无关数据。用户会话识别单元由用户识别、会话识别和用户访问路径完成[11]组成。这是web使用挖掘中最常见的日志预处理顺序。

在web日志预处理之后创建了许多类型的数据格式和数据结构。在一种格式中，web日志被转换成web会话，web服务器日志中的页面访问事件被发现为频繁事件[12]。在另一种方法中，web日志被转换成数据立方体结构[13]。Pitkow[14]解决了从web服务器日志中识别用户和用户会话的困难。在大多数web日志挖掘系统中，预处理首先尝试在web日志处理[15]中构建用户会话。

2.2 web会话聚类

我们的重点是使用网络会话聚类技术来分组用户会话。一个网络使用会话或简单的会话，我们将从现在开始称它为一个网络用户和网络服务器之间交互的一个插曲。会话由用户在一个或多个集[16]中访问的页面组成。网络会话聚类的任务是根据相似性对网络会话进行分组，从而最大化组内相似性，最小化组间相似性。

对web日志[9]，[17]，[18]进行聚类的技术有:基于群优化的聚类技术、模糊聚类技术、DBSCAN聚类技术、k-means聚类技术和分层聚类算法(BIRCH算法)。其中K-means聚类是最流行的。集群计数的数量需要为使用k-means集群提供。因此，当正确的集群计数不知道[17]时，它可能是一个限制。当给出不正确的集群计数时，结果就不那么准确了。

DBSCAN需要聚类的最小密度数，EM聚类算法可以在不给出聚类数的情况下给出聚类结果。然而，在簇数的情况下，EM给出的结果不是很精确，它给出了近似于簇数[19]的结果。基于群算法的聚类是基于粒子群算法(Particle Swarm Optimization, PSO)的聚类算法，PSO聚类算法不能通过动态扩展来自行确定最优的聚类个数，因此与k-means[8]具有相同的局限性。

由于这些聚类技术的局限性，还使用了混合聚类。例如结合两种聚类算法[20]引入K-SVMeans算法。SyMP是一种在大数据集中识别任意形状聚类的聚类方法，它使用高斯分量确定最优聚类数[21]。

3. EM+DBSCAN

所实现的系统解决了两个主要问题。正如我们在第1节和第2节中所解释的，聚类算法需要输入参数，例如聚类数或形成稠密区域所需的最小点数。这些参数在初始阶段很难得到正确的值。尽管有些算法不需要这样的输入参数，但它们在聚类web会话时不能提供所需的准确性。我们要处理的下一个问题是识别将会话分组到单个集群的访问路径中的公共子部分，以及识别将会话分组到不同集群的子部分。

我们的系统由三个主要部分组成。第一个组件是日志清理引擎。它将日志数据净化为标准格式，并在weblog数据上构建索引数据库。第二个组件是聚类组件。它对日志清理引擎给出的矩阵进行处理，使用EM+DBSCAN聚类算法对会话进行聚类。图1为系统组成及系统架构。

第三个组件是签名模块。比聚类更重要的是识别这些聚类的区别。识别这种唯一性并对其进行标记是签名模块的任务。在这里，识别集群的独特特征称为指纹。

3.1 预处理和索引

首先，我们需要对web服务器的访问日志进行预处理并建立索引。我们读取服务器访问日志，过滤特定站点的日志记录，并删除可以采用不同格式的副本。

有每天或每周创建的不同大小的访问日志。过滤的和结构化的日志记录被追加到一个名为log的文件中。按照[11]中的建议，使用三个步骤清理日志数据。会话由IP或’IP’和’Agent’[22]分组生成。这些web用户会话包含在一个会话文件中。每个URL都有一个唯一的数字(整数)。映射文件包含这些整数到url的映射。对映射文件进行排序，通过查看url中的参数长度和参数名找到url之间的相似性。可以使用不同的URL参数集引用同一个页面。

图2显示了数据预处理引擎中的组件。网络记录按网络会话分组和索引。唯一id指向web日志记录列表。一段时间内被请求最多的页面可以通过计算web页面请求的数量来检索。

为大多数常见页面(页面出现次数可以调整)构建新的映射文件。为了支持[15]聚类算法，我们构建了一个NxM矩阵，其中分别包含pageID和session number(默认大小为session文件的总大小和page count)。由于矩阵具有数值元素，许多聚类算法可以在矩阵上执行。

3.2 使用EM和DBSCAN算法对web会话进行聚类

DBSCAN是最常用的聚类算法之一。DBSCAN需要两个参数:ε (epsilon，它指定了要被认为是一个簇的一部分的点之间的距离)和minPts(形成一个密集区域所需的最小点数)[6]。与k-means相反，DBSCAN不要求用户预先指定数据中的集群数量。DBSCAN可以找到任意形状的簇。DBSCAN具有噪声的概念，并且对异常值[5]具有鲁棒性。

我们尝试的另一种聚类方法是EM算法[23]。与DBSCAN不同，该算法在密度差异较大的情况下也能很好地工作。它遵循一种次优的迭代方法，并试图找到具有属性最大似然的概率分布的参数。EM可以通过传递集群计数或不传递集群计数来执行，其中k-means需要集群计数来执行[19]。在没有聚类计数的情况下运行EM时，聚类结果的精度较低。

存在k-means和DBSCAN相结合的工作，EM和DBSCAN相结合的工作不存在。将EM和DBSCAN两种算法相结合，可以消除各自算法在聚类计数和精度下降等方面的缺点。

EM+DBSCAN算法的使用描述如下，如图3所示。首先，我们执行EM聚类算法，通过-1，因为我们不知道聚类数。EM聚类算法在寻找聚类数量方面是充分的。该算法根据给定的数据集输出合适的聚类计数值。数据集的数量除以集群的数量，再除以一个高斯函数，计算出集群中web会话的最小和最大数量。这些值被输入到DBSCAN算法中，集群计数由系统输出。比较簇间距离、簇内距离和完整性值(簇内距离最高、簇间距离最低、完整性最高)，找出最佳值。

然后将该最优值所给出的聚类数再次输入EM算法，并交换各算法的结果以得到一个最优值。通过考察簇间距离和簇内距离的图，可以认为这些值达到了最佳水平。标绘图应该在最佳的聚类数处达到一个稳定的值。最终的聚类结果为稳态期间产生的最佳聚类结果。

3.3 识别簇签名

每个集群包含自己的特性。然后为每个集群找到独特的特性，这些特性对应不同的用户行为。集群由称为指纹的唯一签名来识别。采用频繁模式挖掘和序列模式挖掘方法寻找签名的唯一性。集群建立在这样一个假设之上，即每个集群可以通过出现一个或一组页面来区分。然而，在某些情况下，我们无法在集群中找到唯一的页面，因此我们需要找到一组唯一标识该集群的页面。然后还必须考虑页面访问顺序，以找到集群的独特特性。关联规则挖掘是一种发现大数据集[24]中变量或项之间感兴趣的关系的方法。与序列挖掘相比，关联规则挖掘通常不考虑事务内或跨事务的项目顺序，但它比序列挖掘快。因此，我们采用关联规则挖掘的方法来获取簇签名的置信度。如果获得的签名不是唯一的，则继续序列模式挖掘。有些集群没有唯一的页面出现，但有些有。以图4中的cluster 1页面发生矩阵为例。会话1、会话6和会话7属于集群1。集群1中的所有以上会话都包含页面P1、P6和P10。P6只发生在集群1上，而P1和P10可以在其他集群上看到，比如集群2和集群3(分别是会话2和会话4)。因此，P6是集群1的唯一签名。在某些集群中，很难找到唯一的页面出现。例如，考虑图4中的矩阵会话2、3和5。它们都属于同一个cluster (cluster 2)。P1和P2不能被考虑在cluster的签名中，因为P2在session 5中没有出现。由于不能给聚类2一个唯一的签名，因此使用序列模式挖掘来查找签名。图5所示为集群签名模块实现。

Apriori用于在支持级别为1或接近1的集群中查找签名(支持级别1表示在集群的所有会话中出现一个或多个页面)。在页面出现矩阵上进行简单的字符串搜索可以确认签名的唯一性。签名是通过检查长度和网页的位置在web会话中得到优化的。

4. 评估

在系统评价过程中进行了两个定量实验和两个定性实验。一个大学网站，一个金融网站和一个非营利组织网站都在我们的评估中。第一个定量分析的评价比较了k-means, EM, DBSCAN和我们的EM +DBSCAN聚类算法的性能。接下来，我们评估集群自动生成签名的准确性。第三个实验评估了网站如何随时间变化，并分析了集群和会话的时间效应。第四，我们演示了系统如何检测异常和攻击。

4.1 评价聚类算法

定量分析包括对四种聚类算法的评价。它们是k-means, EM, DBSCAN和EM+DBSCAN算法。这些算法用于对网络会话进行聚类。对于k-means算法，聚类计数的个数是系统的输入。但是在典型的场景中，实际的集群数是事先不知道的。错误!一个比较k-means, EM, DBSCAN和我们的结合算法EM+DBSCAN在非营利组织网络会议。为了进行比较，审议了30 000次会议。用V-measure、簇内距离和最近的簇距离来评估簇[25]。v-measure和簇间距离的值越高越好，簇内距离的值越低越好。EM+DBSCAN与其他三种算法相比，在簇内距离和v-measure方面给出了更好的结果，如Error!没有找到参考源…最近的群集距离表示平均结果(秒到k-means)。错误!没有找到参考源…b和错误!c评估由教育网站数据和金融网站数据生成的聚类。

4.2 评估集群签名唯一性

聚类30,000个会话后，确定了15个集群。使用频繁模式挖掘(FPM)对11个集群生成签名，其余4个集群使用序列模式挖掘(SPM)生成签名，如表1所示。

集群签名采用标准正则表达式表示法。重复计数在方括号内给出。方括号中的两个值表示重复计数的最小值和最大值。页面id在括号中给出。覆盖率代表在一个集群中有签名的会议的百分比，歧视代表在其他集群中没有该集群签名的会议的百分比。为了获得更好的签名，覆盖率和歧视值都需要很高。在表1中，除聚类10中的coverage值和聚类8中的discrimination值外，其余都给出了较高的值。这意味着签名是唯一的。

4.3 网站时间变化的影响评估

随着时间的推移，所有的网站都在变化和发展。网站管理需要以主动的方式监控和控制用户在系统上的行为。在这里，通过检查集群及其签名，系统能够评估用户行为受网站变化的影响程度。由于用户导航结构的改变(如添加或删除网页或更改UI组件)，可以看到模型中新的集群创建、分裂和合并行为。图7是4个月时间内收集的30,000次非营利组织网络日志。会议以x轴表示时间(以月为单位)，y轴表示聚类。据网站管理员介绍，在这四个月的时间里，网站的导航栏发生了3次重大变化。从EM+DBSCAN中可以清楚地识别出这3个变化，如图7所示。图7中的数字1、2和3分别代表网站菜单变化、超链接变化和新增功能。EM, DBSCAN, k-means(由领域专家和EM+DBSCAN给出的聚类数)也对同一数据集进行了测试。DBSCAN只识别三个变化中的一个(群集11)。EM无法找到任何更改。当使用领域专家知识执行kmeans时，它无法找到任何更改。EM+DBSCAN的聚类计数的K-means识别出三个中的两个主要变化(在聚类2和8中)。利用EM、DBSCAN和k-means检测变化，生成如图7所示的图形。由于篇幅限制，没有在本文中展示。

4.4 攻击检测

集群是通过使用页面出现矩阵来构建的，该矩阵是一个二进制矩阵。它表示用户会话中的特定页面存在。在实验中，我们还使用了一个频率矩阵来表示一个页面在一个会话中出现的次数。为每个聚类建立频率矩阵。利用频率矩阵生成的聚类如图8所示。在没有网站更改的地方生成一个新的集群。因此，它是一个有趣的集群，并对相应的web会话进行了手工探索，这表明该集群对应的攻击。使用索引数据库手动确认攻击。发现一个页面的页面出现次数急剧增加，这偏离了正常的用户页面访问次数。与正常的页面访问相比，一次页面访问的持续时间要短一些。HTTP代理的名称，bittorrent，也表明这是一种攻击。

5. 结论

本文所讨论的解决方案结合了两种著名的聚类算法，克服了它们的缺点，提出了一种最优的web日志聚类算法。EM+DBSCAN是一种新的web日志挖掘方法，它比k-means算法的精度有了提高。用户访问模式和用户行为是系统的主要输出。在每次站点更新之后，管理员可以通过查看用户导航模型的最新趋势来验证系统是否实现了预期目标。因此，该方法可以用来改善网站的人机交互和导航。它还可以显示网站的核心功能被使用的程度。检测攻击是系统的其他一些用途。作为未来的工作，需要性能的改进。对数据集进行采样并消除迭代是改进性能的一些可能的方法。