多核环境下基于海量日志的类似行为模式用户识别方法

摘要

本发明公开了一种多核环境下基于海量日志的类似行为模式用户识别方法。现有的方法运算量巨大、I/O操作繁重。本发明方法首先在WEB服务器端设置单独的日志数据库，用于存放记录用户访问信息的日志数据集；其次读入日志数据集中的部分日志信息至内置多核CPU的通用计算机内存；根据多核环境下设置的线程个数，均分日志数据集，得到多个局部日志数据集，作为各线程的处理数据源；然后各线程分别搜索局部日志数据集，获取局部类似行为模式，并进行归约；最后并行归并各线程获得的局部类似行为模式集至全局类似行为模式集，获得具有类似行为模式的用户。本发明可使类似访问模式的识别过程具有较高的运行效率和加速比。

权利要求

1.多核环境下基于海量日志的类似行为模式用户识别方法，其特征在于该方法的具体步骤是：

步骤(1).在WEB服务器端设置单独的日志数据库，用于存放记录用户访问信息的全局日志数据集，全局日志数据集中的每一条日志信息包括用户ID、访问时间、访问IP、请求页面和请求功能号；

步骤(2).以可用内存为限，读入全局日志数据集中的部分日志信息至内置多核CPU的通用计算机内存；

步骤(3).根据多核环境下设置的线程个数，采用水平等间距静态投影方法均分全局日志数据集，得到多个局部日志数据集，作为各线程的处理数据源：设全局日志数据集中有R条记录，采用水平等间距静态投影分配方法将完整的全局日志数据集划分为n份，其中n=线程个数，使得各线程分配的局部日志数据集为 ，其中 ；

步骤(4).各线程分别搜索步骤(3)获得的局部日志数据集，获取局部类似行为模式，并进行归约：各线程将需要处理的局部日志数据集按日志的访问时间从先到后排序；如k个不同用户ID对于同一个请求功能号的日志访问时间间隔小于预设的窗口时间、并尚未置入局部类似行为模式集，则将此k个用户ID作为一个项置入局部类似行为模式集，并记该项的支持度为1；如k个不同用户ID对于同一个请求功能号的日志访问时间间隔小于预设的窗口时间，同时对应的项已置入局部类似行为模式集，则把该项的支持度加1，其中k>=2在此过程中，若生成的局部类似行为模式集容量达到了预先定义的最大内存上限值，则可先将该局部类似行为模式集以文件形式保存在硬盘中；

步骤(5).重复步骤(2)、(3)、(4)，至全局日志数据集中的所有日志信息都已处理完毕；

步骤(6).并行归并各线程获得的局部类似行为模式集至全局类似行为模式集，获得具有类似行为模式的用户：选择空闲核，合并部分局部类似行为模式集至１个新的局部类似行为集，即把局部类似行为模式集中相同项的支持度进行累加，形成１个新的局部类似行为模式集；多核并行执行上述工作，直至最终获得１个全局类似行为模式集，如其中某个项的支持度超过阈值，则对应的k个用户即为共享类似行为模式的用户。

说明书

多核环境下基于海量日志的类似行为模式用户识别方法

技术领域

[0001] 本发明属于数据挖据技术领域，具体涉及到一种多核环境下基于海量日志的类似行为模式用户识别方法。

背景技术

[0002] 因特网已经成为一个巨大的、分布广泛的和全球性的信息服务中心，正逐渐渗透到人们的日常工作、生活及其它领域。大量的用户通过访问电子商务网站进行信息查询和购买商品。通过分析Web服务器中的访问日志文件，从而发现用户访问站点的浏览规律，可以帮助人们理解不同用户的行为模式，最终为改进Web站点并获取更大的经济效益提供帮助。

[0003] 研究不同的用户的消费习惯，往往可以发现多个不同用户之间可能具有类似的行为模式。例如，他们可能都在每周四晚上浏览促销信息、每周五晚上网购日用品、每周日晚上确认到货和进行网上支付；或者可能都在每周五晚上进行网上阅读、每周六晚上更新博客、每周日晚上安排工作计划。这种行为模式的主要特征可以归纳为：多个不同的用户在相近的时间点上从事类似的行为，或者说他们共享具有时间特征的类似行为模式。识别上述具有类似行为模式的用户群，可以为网站提供精准的个性化服务提供帮助，例如：安排面向特定人群的团购活动，在合适的时间点推出广受欢迎的服务内容，等。

[0004] 然而，这种类似行为的访问模式识别一般涉及TB级的历史海量数据。虽然，计算机技术的飞速发展，特别是多核技术的引入可以使得传统计算机系统的计算能力得到一定程度的提高，但是，如果没有在应用级实施针对海量日志的分析过程的优化，巨大的运算量以及繁重的I/O操作可能依旧使得多核系统在功能和性能上都难以达到预期效果。

发明内容

[0005] 本发明针对现有技术的不足，提供了一种多核环境下基于海量日志的类似行为模式用户识别方法。

[0006] 本发明方法的具体步骤是：

[0007] 步骤(1) 在WEB服务器端设置单独的日志数据库，用于存放记录用户访问信息的日志数据集，日志数据集中的每一条日志信息包括用户ID、访问时间、访问IP、请求页面、请求功能号；

[0008] 步骤(2) 以可用内存为限，读入日志数据集中的部分日志信息至内置多核CPU的通用计算机内存；

[0009] 步骤(3) 根据多核环境下设置的线程个数，采用水平等间距静态投影方法均分日志数据集，得到多个局部日志数据集，作为各线程的处理数据源；

[0010] 步骤(4) 各线程分别搜索步骤(3)获得的局部日志数据集，获取局部类似行为模式，并进行归约；

[0011] 步骤(5) 重复步骤(2)、(3)、(4)，至日志数据集中的所有日志信息都已处理完毕；

[0012] 步骤(6)并行归并各线程获得的局部类似行为模式集至全局类似行为模式集，获得具有类似行为模式的用户；

[0013] 本发明所提供的多核环境下基于海量日志的具有类似行为模式的用户识别方法由一组功能模块组成，它们包括：日志集分批读取模块、日志集等分模块、局部类似模式集生成模块和局部类似模式集汇总模块。

[0014] 日志集分批读取模块以可用内存为限，分批读入日志数据集中的部分日志信息，包括用户ID、访问时间、访问IP、请求页面、请求功能号。

[0015] 日志集等分模块根据多核环境下设置的线程个数，采用水平等间距静态投影方法均分日志集分批读取模块读取的日志数据集，得到多个局部日志数据集。

[0016] 局部类似模式集生成模块采用多线程并行的方式，将各线程待处理的局部日志数据集分别按日志的访问时间排序，获取局部类似行为模式和支持度，构建各个局部类似模式集。如局部类似行为模式集容量超过预定义的最大内存上限值，则以文件形式换出至硬盘。

[0017] 局部类似模式集汇总模块采用多线程并行的方式，累加各局部类似模式集的类似行为模式的支持度，格式化输出具有高支持度的具有类似行为模式的用户信息。

[0018] 本方明提出的方法采用数据并行和任务并行相结合的策略，在各线程生成局部类似行为模式后，再与其他线程协同，以最终获得所有的全局类似行为模式。该方法通过并行局部归约技术消除了局部类似行为模式的重复生成与计算，并可结合静态与动态任务分配机制解决处理器的负载不均衡问题。在分析海量访问日志过程中，与不经过多线程优化、直接采用多核处理器的传统方法相比，采用本方明所述方法可使类似访问模式的识别过程具有较高的运行效率和加速比。

附图说明

[0019] 图1数据流图；

[0020] 图2模式存储数据结构图；

[0021] 图3归约流程图。

具体实施方式

[0022] 本发明所提供的多核环境下基于海量日志的类似行为模式用户识别方法的具体实施方式主要分3步（如图1所示）：

[0023] （1）根据线程个数，用水平等间距静态投影方法均分全局日志数据集为各局部日志数据集，作为各线程的同等数据源；（2）将局部日志数据集按日志的访问时间排好序，并行搜索对同一个请求功能号的日志访问时间间隔小于预设时间窗口的 个不同用户ID（其中， ），将其作为局部类似行为模式并结合局部归约方法以文件形式保存；（3）结合动态任务分配机制方法并行归并局部类似行为模式，对比其支持度大小与预先设定的最小支持度阈值（min_sup），挖掘支持度大于阈值的目标类似行为模式。

[0024] 为叙述方便，定义相关符号如下：

[0025] ：第 个线程。

[0026] ：所有含对同一个请求功能号的日志访问时间间隔小于预设时间窗口的 个不同用户ID的局部类似行为模式集。

[0027] ：所有含对同一个请求功能号的日志访问时间间隔小于预设时间窗口的 个不同用户ID，且ID值为j的局部类似行为模式集。

[0028] ：所有含 个不同用户ID的局部类似行为模式支持度大于min_sup 的目标类似行为模式集，即 。

[0029] ：分配到第 个线程的序列日志数据集。

[0030] ：分配给 的含 个不同用户ID的局部类似行为模式集，且 。

[0031] ：分配给 的含 个不同用户ID，且ID值为j的局部类似行为模式集。

[0032] ：分配给 的含 个不同用户ID的局部类似行为模式支持度大于min_sup 的目标类似行为模式集，且 。

[0033] （1）静态等分全局日志数据集

[0034] 为了减少数据偏移的发生及实现多线程搜索局部类似行为模式，首先采用水平等间距静态投影数据分解模式均分全局日志数据集以实现各线程数据负载均衡。假设全局日志数据集中有 条记录，采用水平等间距静态投影分配方法将完整的日志数据集划分为n份(n=线程个数)，使得各线程分配的局部日志数据集为 。其中第 个线程对应的数据集 表示：

[0035]

[0036] 为第 个线程的第 条记录， 为全局日志数据集中的第 条记录。经过以上变换，全局日志数据集 被分割成 个规模为 的局部数据集 ，即。

[0037] （2）局部类似行为模式搜索、归约与保存

[0038] 线程 获得局部日志数据集 后，先针对 独立搜索类似行为模式，即查找并存储对同一个请求功能号的日志访问时间间隔小于预设时间窗口的 个不同用户ID。为减少多核环境下有限存储带宽上的竞争，若 能够全部存储在内存中，则将 按日志访问时间排序后写入内存；若 较大，不能全部存放，则对 进行二次划分，形成 ，然后将 排序后写入内存。针对当前的MDB（Memory Database），算法搜索所有的 并存储在相应的数据结构中（如图2所示），随后依次查找下一个 ( ），循环执行直到再没有新的局部类似行为模式 产生为止。在此过程中，若生成的局部类似行为模式容量达到了预先定义的最大内存上限值，则先将该部分 以文件形式保存在硬盘中，然后再计算并存储新的 。

[0039] 为了提高挖掘效率，减少 的数目和 的复杂度，算法结合局部归约技术来消除的重复生成与计算。即线程 扫描 只保存用户ID值 唯一的 ，将相同 的类似行为模式支持数进行累加。针对线程 ，该归约方法具体实现过程如图3所示。

[0040] 算法归约操作使得所有相同的 位于同一链表中，从而快速实现将相同局部类似行为模式的支持数进行累加，确保在 中得到的 不仅是支持度（sup）为1的局部类似行为模式集 ，而同时存在 的 。因此，算法的第一趟扫描将发现sup各异的含个不同用户ID的 ，然后第 趟扫描以第 趟的 的sup集合作为种子集来生成新sup的 ，并将它作为下一趟扫描的种子集。如此循环执行直到挖掘出所有的 ，并最终以文件保存。为防止多核环境下对共享文件数据的读写或写写竞争，文件的命名采用以不同线程名区分的保护方法。

[0041] （3）局部类似行为模式归并

[0042] 将 得到的局部类似行为模式与 交互，实现局部类似行为模式汇总，即把所有文件中 个用户ID值 相同的局部类似行为模式 的支持度sup进行累加，从而获得目标类似行为模式 。此阶段再次结合多线程编程的任务分解模式，通过采用动态任务分配机制，先把以不同文件编号开始的文件汇总任务依次保留在一个全局任务列表内，然后各线程同时处理分配到的任务，彼此相互独立、互不干扰。方法在一定的时间间隔内循环判断是否存在空闲处理器核，若存在，则从全局任务列表中读取一个新任务在此处理器核上进行处理。反复调用该方法，直到列表中所有的汇总任务被处理完毕，此时得到的所有 即为所挖掘出来的全局类似行为模式，最终将 的支持数与min_sup比较生成，而 对应的用户ID则共享类似行为模式。为了减少数据汇总的计算量，当前任务的文件初始编号保持比上一次汇总任务的文件初始编号增1。

[0043] 本发明可用于电子商务网站的海量日志挖掘，以快速识别具有类似行为模式的用户。