基于特征转移概率的网络日志聚类分析算法_齐文.pdf

小 型 微 型 计 算 机 系 统 ：年 月 第 期 收稿日期：收修改稿日期：基金项目：国家自然科学基金项目（）资助 作者简介：齐文，男，年生，硕士，副教授，会员，研究方向为大数据管理；朱曦源，男，年生，本硕博连读生，研究方向为大数据管理；宋杰，男，年生，博士，教授，博士生导师，高级会员，研究方向为大数据存储管理、高能效计算、机器学习应用基于特征转移概率的网络日志聚类分析算法齐 文，朱曦源，宋 杰（辽东学院 工程技术学院，辽宁 丹东）（东北大学 软件学院，沈阳）：摘 要：随着信息化建设，互联网行业的发展，各种信息设备在运行和通信中，会产生大量的网络日志数据 网络日志的内容是非结构化的格式，获取相关信息具有一定难度，并且这种数据正在迅速增长为庞大的体量，所以从中获得所需的信息并对相关信息进行处理，是一个非常具有挑战性的任务 数据挖掘的技术是非常传统的技术，实施往往耗费太多时间，并产生过多的数据，大数据环境下，传统的串行的网络日志聚类方法存在性能的局限性，不再适合处理网络日志这样的海量数据，目前比较常用的对于网络日志的并行处理方法在计算时间、并行效率、准确率等方面存在一定改进空间 因而，本文提出了一种基于特征转移概率改进的网络日志聚类处理技术，并在 平台上实现了用于提取频繁的庞大的网络日志的模式 实验结果表明，所提出的方法能够在大数据环境下对完整的网络日志提取所需信息并实现高效的分析，相对于目前常见的聚类分析算法，本文提出的基于特征转移概率的处理方式将执行时间降低到了 关 键 词：日志分析；大数据；聚类算法；并行处理中图分类号：文献标识码：文 章 编 号：（），（，）（，）：，：；引 言随着信息化建设，互联网行业的发展，各种信息设备在运行和通信中，会产生大量的网络日志数据 日志数据的来源很多，如网络、文件和计算服务器，网络日志数据对于商业规则、统计分析、网络广告、推荐系统等都很有用 因此，能够合理处理并分析体量庞大的网络日志数据是有实际意义的当前的研究提出了许多使用 和 的网络日志分析聚类优化算法 然而这种使用 的网络日志处理方法都存在计算速度慢，磁盘 开销大，尤其在实时处理在线式的网络日志数据方面性能较低 也有研究提出了使用 的聚类处理方法，但是这些方法，而既不提供数据分析，也不提供对 内容的查询机制 这种缺乏对捕获、存储和查询出处的支持，是在数据处理过程中和之后充分利用详细分析的瓶颈 以及存在诸如没有去除冗余数据，以及没有考虑以最小的空间要求实现高精度的预处理的问题，以及输出不适合对数据的进一步处理，比如聚类或是分类等 针对上述问题，网络日志的聚类算法可以进一步改进本文提出了一种网络日志处理方法，实现了高精度的预处理以及实现了数据的高效进一步聚类处理 该方法以提高聚类性能为目标，以最少的时间处理和分析网络日志，并能获得较高的准确率和灵敏度 本文提出的特征转移概率是指特征向量向一特定聚类中心转移的概率，基于此，分布式并行处理方法能够分析完整的网络日志数据集并提取有用的信息，在集群上进行并行处理完成聚类算法本文提出的基于特征转移概率的聚类方法首先要对网络日志数据集进行数据预处理，生成特征向量再用分布式优化的 聚类方法基于特征转移概率进行聚类，为了获得更好的并行效率和速度，本文采用了 以及弹性分布式数据集 实验与其他优化的聚类算法进行比较，本文分布式改进的网络日志处理技术实际实验中选择的特征能够在高准度下提高聚类速度，保持了与现有的聚类方法接近的收敛灵敏度和准确度，并将执行时间降低到了 本文第 节介绍了一些关于聚类算法的预备知识 第 节介绍了预处理的方法，并进行了举例演示 第 节介绍了特征转移概率与相关的公式以及本文提出的基于特征转移概率的算法实现 第 节介绍了实验，实验测试在不同约束条件如聚类精度和数据量规模下进行 预备知识数据聚类的目的是确定数据值的分组或发现数据中的模式 聚类算法根据一些相似性度量将 个对象分成 个组相似性度量可以从维度或模式集合生成 一个理想的集群将 个数据的一部分放入一个与其他组隔离的紧凑组中 聚类通常被认为是一项无监督的任务，因为没有提供具有特定标签的训练 聚类过程包括 个步骤：特征提取、模式接近度确定（即建立对之间的距离值）、聚类（即分组）和抽象（例如，从聚类中选择一个小的子样本统计表示完整的数据集）聚类算法是最经典的聚类算法之一，该算法以距离作为评价的相似度指数，即两个对象之间的距离越近，相似度越大 对于给定的样本集，计算任意两个样本之间的距离，根据样本之间的距离将样本集划分为 个聚类，它实现起来比较简单，可以扩展到大型数据集，并且保证收敛性 实现的算法如算法 所示算法 聚类算法步骤 随机选择 个集群中心点步骤 聚类分配 在这一步，将数据集中的每个数据点分配给一个中心点，选择与数据点最接近的中心点步骤 中心点移动 对于每个中心点，计算分配给每个中心点的所有数据点的平均值 这个计算出来的平均值就是这个特定中心点的新值步骤 计算每个中心点从之前的值中移动的距离平方的总和，重复步骤 和，直到这个值不小于或等于阈值（通常是 ）或迭代次数达到指定的最大迭代次数然而，传统的串行 聚类算法还是难以高效、准确地对海量运行状态监测进行聚类分析 接下来本文将讨论这个算法在不同平台上的实现细节，以深入了解这种迭代算法如何被修改以适应不同的数据集 在 上的 分析 的工作原理是将处理过程分成两个阶段：阶段和 阶段 每个阶段都有键值对作为输入和输出 输入的网络日志文件通常驻留在 分布式文件系统（）中，会提供一个包含要读取的文件的路径，读取这个目录中的所有网络日志 然后，它将这些网络日志分成一个或多个块 一个 作业无非是一个应用于数据集的程序，由若干个任务组成的 在完成第一个 任务后，各节点仍然各自再执行几个 任务 但是他们也开始将一个 任务的中间输出交换到另一个 需要的地方，是将数据从 转移到 的过程，从而使得 获得输入，不同子集分区的键空间被分配给每个 节点；这些子集分区是 任务的输入 它决定了映射阶段输出的一个键值对，将被送到哪个 中去 类可以找到一个给定的键值对将被送到哪个分区 默认的 会对键的哈希值进行操作，并根据这个结果分配分区 单个节点上的中间键集合在交付给 之前，会被 自动排序 当排序后的输入数据中的下一个键与前一个键不同时，它就会启动新的 任务 框架对排序顺序中的每一个唯一的键都会调用一次（）可以遍历与该键相关的值，并产生零个或多个输出值 输出值需要与输入值的类型相同，输入键也不需要改变 通过调用到方法 （，）来收集输出对 还接收 和 对象作为参数，其使用方式与（）方法相同 将 作业的输出键值对写入一个输出文件 实现将作业输出写到 中 然后，写入的输出文件存在 中 的网络日志处理方法结束 这里 的特点是把计算移到数据上，而不是把数据移到计算上，数据以块的方式存储在集群中的多个节点上，从而相对于传统的串行处理方法，这种基于 和 的分布式并行处理方法，取得了不错的效果，并且成功地处理了大规模网络日志数据集对于 聚类等迭代算法，并不是一个理想的选择 基本上，映射器从磁盘上读取数据和中心点 磁盘上的数据和中心点 然后这些映射器将数据实例分配给集群 一旦每个映射器完成了他们的操作，还原器通过计算每个簇中存在的数据点的平均数来计算新的中心点 每个集群中存在的数据点的平均值 现在，这些新的中心点被写入到磁盘上 然后，这些中心点由映射器在下一次迭代中读取，整个过程不断重复，直到算法结束 整个过程不断重复，直到算法收敛 算法 给出了在 上的 的伪代码 算法 和算法 给出了 聚类的映射器和化简器函数的伪代码算法 在 上的 输入：数据点，聚类数 步骤 随机初始化 个聚类中心步骤 将 中的每个数据点与最近的聚类中心联系起来，把数据点分成 个集群 期 齐 文 等：基于特征转移概率的网络日志聚类分析算法 步骤 重新计算聚类中心的位置 重复第 步和第 步，直到数据点的成员资格不再有变化输出：是集群成员的数据点算法 映射器输入：数据点，聚类数 和聚类中心步骤 对于每个数据点 步骤 将 分配给最接近的聚类中心输出：带有相关数据点的聚类中心算法 化简器输入：带有相关数据点的聚类中心步骤 计算集群中数据点的平均值计算新的聚类中心步骤 将全局中心写到磁盘上输出：新的聚类中心 在 上的 分析与基于 的 模型相比，具有很多优势 提供的内存计算在大规模分析中非常有用 内存计算主要有两个优势 第一，由于数据存储在内存中，所以迭代作业不需要重复的磁盘访问 第二，交互式作业不需要每次查询都访问磁盘，相反，可以用来将数据库存储在内存中并频繁查询由于日志数据是非结构化的，本文从每一行中解析并创建一个结构，在分析时，这个结构又会成为每一行 之后创建、然后，可以从文本文件中加载数据作为，然后它可以处理这些数据 给定一个日志行的，使用 函数将每一行转化为 对象 会被缓存在内存中，因为会对其进行多次转换和操作 通过映射变换提取出内容大小，然后调用不同的操作（、和）来输出各种统计数据 上的 实现与在 上的 实现类似 节中描述的基于 的 全局中心点不是写在磁盘上，而是写在内存中 这样可以加快处理速度并减少 磁盘 的开销 此外，数据将被加载到系统内存中，以提供更快的访问 以便提供更快的访问 上的 均值聚类涉及多线程每个线程将一个数据向量与一个中心点联系起来，最后中心点被重新计算，用于下一次迭代 最后为下一次迭代重新计算 允许本文对大量的输入数据进行流处理 由于 基于内存计算的良好性能，降低了时间要求，并保证了一定的准确度由于 对于迭代计算的性能良好，故本文选择 的 为基础进行优化，提出了基于特征转移概率的 聚类算法 具体实现在下节开始讨论 预处理与聚类特征一些公开的网络服务器日志数据集，如，和 的数据集都是优质的数据集 本文通过这些数据集来熟悉处理 服务器日志 由于这些网络日志数据具有非结构化数据的特点，含有大量的噪声数据，必须消除这些不相关的数据，所以需要对网络日志进行预处理 表 描述了一个样本的 表 对网络日志条目头的简要描述 日志条目描述远程主机地址远程日志名称：时间戳请求的时区请求方式 服务器上的路径协议版本状态码返回数据的大小：引用程序 用户代理 预处理使用了整个网络日志数据集的解析技术 在本次实验，首先将网络日志数据按照以下方式进行拆分到其属性 特征选择作为一个预处理步骤，需要通过消除冗余和不相关的特征，只选取信息丰富和简洁的特征来增强分类过程 在应用这一原则后，分类过程中由于过度拟合而导致的问题就被消除了 为了加强这一任务，通常采用特征选择算法来选择信息量最大的属性，从而减少特征空间对于较大的数据集，有多种技术可以确保计算、存储和数据工作流程得到优化，并且可以实现潜在的更大规模建模的可扩展性 这些计算扩展技术如，它将数据分割为单元进行并行处理 然后，被处理的单元被重新映射回更大的数据集，以便进一步分析或处理 计算平台旨在通过提供包括大量存储、分布式文件系统和先进的处理能力在内的高性能计算环境来利用 的概念 是一个开源的 框架的实现，在需要进行大数据分析时，对、和 的使用进行了优化 使用更复杂的分布式聚类模型，数据被一次性加载到内存中，可以对其进行大量操作 当 应用程序提交时，在主节点上创建 对象，从 读取数据以创建 对象 它从 读取数据以创建 对象，并向集群资源管理器请求资源 向集群资源管理器请求资源 集群资源管理器将资源分配给每个工作节点的一个或多个执行器进程 每个工作节点有一个或多个执行器进程，每个工作节点向集群资源管理器报告资源使用和任务运行状态 每个工作节点使用心跳机制来向集群资源管理器报告资源使用情况和任务运行状态 对象根据多个 之间的依赖关系构建一个有向无环图（），并将该 提交给 调度器以确定多个 之间的依赖关系提交给 调度器 调度器将 解析为多个任务集，提交给任务调度器 任务调度器将任务分配给执行进程，当一个执行进程收到一个任务时，会从执行进程的线程池中抽取一个线程来执行该任务 预处理方法在这个实验中，本文使用了弹性分布式数据集和，用于