摘要：现代 IT 系统经常产生大量事件日志，事件模式发现就成了重要的日志管理任务。为完成此目标，数据挖掘方法已经预先给出了很多方式。本文提出 Log Cluster 算法，其继承了文本事件日志数据聚类和线性模式挖掘。

日志事件模板可以被应用到很多方面，如：事件日志更正规则开发，系统错误和网络异常的检测，相关事件的可视化，网络通信模式的识别和报告，IDS 告警分类的自动构建。

基于行的非结构日志聚类算法，假设在事件日志中每个事件是通过单行日志描述的，每行模式代表一组相似事件。本文提出新的数据聚类算法Log Cluster，可以同时发掘频繁发生的模式和文本事件日志的离散事件。

相关工作：

SLCT：自动日志解析，分配符合相同模式的事件日志行到相同簇中，所有检测的簇都被作为行模式。用户需要提供支持阈值 s 以便SLCT定义每个簇中最少行数量。在日志处理期间，所有来自日志的频繁词放入集合作为此日志的候选。

建立单词字典，对所有日志建立包含单词频率和坐标的字典；建立日志簇；生成日志模板。

IPLoM 是一种层级聚类算法，基于系统消息特点涉及的生产式方法；开始将整个事件日志作为一个单独的部分，三步循环划分。第一步，将有相同词数量的行分配到一起；第二步，每个部分进一步被划分，通过标识最少唯一词数量的词位置，分配有相同词的行到相同部分划分；第三步，基于词对间的关系划分每个部分。

根据日志长度划分；标记位置划分，不同位置的单词都会统计次数，拥有最少变化单词的位置用来进行日志划分；基于映射划分，单独标记集合在两个标记位置间的映射关系对簇划分；生成模板。

IPLoM 比 SLCT 的优势在于可以检测带通配符的行模式。

LogSig：生成单词对，单词对包括单词及位置信息；日志聚类，根据每个日志计算度量值决定日志属于的簇；模板生成。

Log Cluster 算法：L = [l1, l2...ln]是文本事件日志，由 n 行组成，每行 li (1<=i<=n) 是事件的完全表征，i 是行唯一标识；每行 li 是 k 个词的序列，li = (wi1, wi2,...wik)。Log Cluster 使用支持阈值 s(1<=s<=n) 作为输入参数，将日志划分到 C1,C2,...Cm 簇中，每簇至少 s 条日志，O是离群簇。

Log Cluster 将日志聚类问题视作模式挖掘问题，每簇 Cj 通过模式 pj 标识为唯一的。为检测簇，Log Cluster 从日志中挖掘模式 pj。模式 pj 和簇 Cj 的支持值定义为 Cj 中日志的数量，每种模式由词和通配符组成。

为找到达到支持阈值的模式，这种模式所有词至少在 s 条日志中出现。

Log Cluster 考虑日志中的每个词但是不包括位置信息。Iw 是包含单词 w 的行标识的集合。如果 Iw大于等于阈值 s ，则 w 是频繁词，所有频繁词的集合使用 F 表示。

Log Cluster 使用一个 h 大小的框架计数器。在预先处理事件日志时，每条事件日志行的去重词散列到 0 到 h-1的整数，增加对应的计数数量。(构建词表，统计词频)。

频繁词汇认定后，Log Cluster 产生簇的候选，对事件日志中的每行，Log Cluster 从日志提取所有频繁词，将词处理为元组，保留原始行中的位置信息。元组会作为簇候选的标识，所在行会被归为对应的候选。

如果给定的候选不存在，则初始化并将支持计数设为1，从行中创建其行模式。如果候选存在，其支持计数增加，行模式调整以覆盖当前行。

Log Cluster不记录分配给候选簇的行。

举例：事件日志“Interface DMZ-link down at node router2”，频繁词是“Interface, down, at, node”，该行被分配给识别的候选元组(Interface, down, at, node)。如果候选不存在，则设置行模式初始化为“Interface *{1,1} down at node *{1,1}”，计数设为 1，通配符 *{1，1}可匹配任何单一词汇。如果下一行产生同样的候选标识“Interface HQ link down at node router2”，候选支持计数增加到 2。行模式设置为“Interface *{1,2} down at node *{1,1}”，为使模式匹配，至少一个但不超过2个在 interface和down之间。

通过所有数据完成簇候选构建后，LogCluster 将所有支持计数小于支持阈值 s 的候选排除，保留剩余的。当模式挖掘使用较小的支持阈值执行时，LogCluster 与 SLCT 相似，倾向于过拟合，即较大的簇可能会被划分为较小的簇，有过于详细的行模式。

第一种减少过拟合的启发式策略叫 Aggregate_Support，在候选生成完成后，簇选择前使用。这种启发涉及发现对每种候选有更详细行模式的候选，增加在给定候选中的支持。此种模式可以重叠。

第二种启发称为 Join_Cluster，在簇已经从候选中选择后使用。Cw 包含所有共现的高频词汇。dep(w, w')代表 w' 在含有 w 的日志行中发生的频繁度。词 w' 在该模式中的权重计算公式，词的权重代表了词与模式中其他词之间关联的强度。Join_Cluster 启发将用户支持词权重阈值 t 作为输入参数(0 < t <= 1)，具有相同第二标识的簇连接在一起。两个或更多簇合并时，连接簇的支持是所有原始簇的和就，合并簇的模式适应所有原始簇。

可使用规则表达式过滤日志，移除过滤的内容。

在挖掘过程中，现有的模式挖掘模式将将词作为原子处理，不尝试发现词内部的潜在结构。

流程图：