2. 通信网信息传输与分发技术重点实验室, 石家庄 050081;
3. 中兴通讯股份有限公司, 深圳 518057
针对传统日志模板挖掘时需要日志聚类数目作为先验信息的问题，提出了一种基于归一化特征判别的日志模板挖掘算法.首先，对日志数据进行压缩，以提高后续处理效率；其次，进行日志聚类过程，使用归一化的日志统计特征判断聚类是否满足要求，若满足，则聚类成功；若不满足，则采用二分搜索的方式调整日志聚类的数目，重新进行聚类；最后，从聚类结果中提取日志模板，设计了一种衡量模板挖掘效果的评价指标.在真实数据集上的实验结果表明，算法的模板挖掘匹配度优于基准方法，并且具有良好的泛化性能.
2. Science and Technology of Information Transmission and Dissemination in Communication Networks Laboratory, Shijiazhuang 050081, China;
3. ZTE Corporation, Shenzhen 518057, China
A log template extraction algorithm based on normalized feature discrimination is proposed, aiming at the problem that the number of clusters needs to be provided as a priori information in traditional log template extraction. First, log data is initially compressed to reduce data redundancy. Then, a log clustering process is implemented, and the normalized feature is used to discriminate whether the clustering result meets requirement:if so, the clustering process is successfully completed; if not, the number of log clusters is adjusted by using binary search and redo clustering. Finally, the log template is extracted via clustering results. In addition, an evaluation metric that measures the effectiveness of template extraction is designed. Experiments on real data indicated that the algorithm can achieve more stable and accurate template extraction performance than the benchmark method, and it had good generalization performance.
日志记录了系统内部操作的重要信息，如系统状态、程序崩溃等，运维人员可以通过日志数据对系统进行分析与优化，并进行异常检测.随着大数据技术的发展，各种网络服务和分布式系统变得愈加复杂，系统生成日志的规模越来越大.如何从海量日志中挖掘出有效信息，快速准确地提取日志模板，成为日志处理领域亟待解决的问题.
提出一种基于归一化特征的日志模板挖掘算法，在对日志进行初步的聚类过程后，使用归一化聚类后日志的统计特征作为判别聚类成功的标准，解决了传统日志聚类方式需要日志聚类数目作为先验信息的问题，提高了算法的泛化能力.通过对不同日志数据进行实验的结果表明，算法有效地提高了模板挖掘的准确率.
1 相关工作由于日志集合中不同类型的日志长度不一，词汇量大，传统的基于01词袋模型聚类的模板挖掘方法仅仅使用日志单词本身的基本特征进行关键词判别，忽略了日志集合的整体特征，因此在实际应用时效果不佳[1]；基于聚类后提取模板的方式是当前主流的日志模板挖掘方法：Vaarandi等[2]提出的简单日志聚类法主要采用基于密度的聚类算法，通过人工设定阈值的方式对聚类大小进行控制，阈值越小，每个聚类中的文本相似程度越高；Fu等[3]使用以单词为最小单位的编辑距离对日志进行聚类，并提取每个聚类中的频繁词序列或公有日志文本片段作为日志模板；迭代分区日志挖掘法(IPLoM，iterative partitioning log mining)[4-5]根据日志的长度、频繁项、词位关系等逐步将日志集合划分成多个聚类，并根据聚类中的频繁项从每个聚类中构造日志模板，尽管该方法相比于传统方法能够取得更好的效果，但由于划分聚类的标准较为单一且固定，无法在较为复杂的场景下取得满意的效果；Li等[6]在预先给出日志聚类数目的情况下，通过建立基于词对关系的聚类转移增益计算构造最终聚类，聚类效果较好；Nandi等[7]在聚类构建过程中引入日志时间序列关系辅助判断，提高了模板挖掘的准确率；日志分析系统LogCluster中的日志聚类算法使用聚合层次聚类，在得到聚类结果后，选择每个聚类中与其他序列距离最小的序列作为日志模板[8].
以上方法通过聚类的方式结合了日志集合的整体信息和词项的单位信息，然而大多需要人工干预的过程，与自动化进行模板挖掘的目标不符.针对上述问题，提出一种基于归一化特征的日志模板挖掘算法，通过对日志进行聚类完成模板挖掘过程，并使用归一化特征判断聚类结果，不需人工干预即可自动完成聚类，可以在先验信息较少时取得更好的模板挖掘效果.
2 日志模板挖掘算法 2.1 问题描述针对日志模板挖掘问题，建立基本日志模板挖掘问题模型M.定义：
| $ \begin{array}{l} M = \left( {D, T, V} \right), D = \left\{ {{d_i}|1 \le i \le {N_d}} \right\}, T = \left\{ {{t_j}|1 \le j \le {N_t}} \right\}, \\ V = \left\{ {{v_{ij}}|1 \le i \le {N_d}, 1 \le j \le {N_t}} \right\}, {V_{ij}} = f\left( {{d_i}, {t_j}} \right) \end{array} $ |
满足以下条件约束：
| $ \begin{array}{l} \forall {v_{ij}} \in V, {v_{ij}} = 0 \vee {v_{ij}} = 1\\ \forall {d_i} \in D, \exists j\left( {{v_{ij}} = 1 \wedge {t_j} \in T} \right)\\ \forall {d_i} \in D, \neg \exists j\exists k\left( {{v_{ij}} = 1 \wedge {v_{ik}} = 1} \right) \end{array} $ |
其中：D为原始日志集合；Nd为原始日志数量；T为日志模板集合；Nt为模板数量；V为日志和日志模板的对应关系，用一个二元组Vij=f(di, tj)表示；vij表示日志di是否可以与模板tj匹配，vij=1表示是，vij=0表示否.模型的3个约束表示对于每条日志和每条模板只存在匹配和不匹配2种情况，匹配且仅匹配一条模板.
对于原始日志集D，模型M将D中任一元素匹配至模板集合T中的仅一条元素，该过程表示原始日志和日志模板的生成过程和多对一的匹配关系.
2.2 解决思路当前的主流方法是基于聚类的日志模板挖掘方法. LogSig算法在预先给出日志聚类数目的情况下，通过建立基于词对关系的聚类转移增益计算构造最终聚类.其中，预先给出日志聚类数目需要人类的先验知识，而在实际情况下，对于未知的日志数据数目难以取得，严重限制了算法的应用场景.如果能够设置某种条件对聚类数目做出预先估计，将大大增加算法的应用价值.
对于不同的日志类型，挖掘出的模板类别数，即算法需要的聚类数目是相差较大的[9]，若对其设置相同的聚类数目则不能很好地适应，但对于算法而言，需要有一套统一的判别标准.使用的基于归一化特征进行判别的方式则能够较好地解决聚类数目差别较大的问题.
特征归一化处理是数据挖掘的基础工作之一.不同的评价指标往往有不同的量纲和量纲单位，这种情况会很大程度上影响数据分析的效果.为消除评价指标因量纲不同产生的影响，需要对数据进行归一化处理，以解决数据之间的可比性.原始数据在经过了归一化处理后，各指标处于同一数量级，适合进行相互间的对比评价.
在模板挖掘问题中，算法所需的聚类数目并不适合进行归一化，因为不同日志系统需要的聚类数目在归一化操作后依然差距较大，因此，为使不同日志系统产生的结果具有可比性，需要采用更合适的归一化特征进行判别.在实际的日志系统中可以发现，不同的日志系统，其单条日志中参数部分所占比例是在一定范围内的，通过基于频繁项的参数判别方式构造参数比例相关的归一化特征，可以作为判别依据，从而搜索出合适的聚类数目[10].
所提出的日志模板挖掘流程如图 1所示.在当前日志的总类别数未知时，可通过在搜索过程中设置统计归一化特征进行判别的方式搜索出合适的聚类数目，并进行模板挖掘.
|
图 1 基于归一化特征的日志模板挖掘算法流程 |
基于归一化特征的日志模板挖掘算法实现过程如下.
算法1 基于归一化特征的日志模板挖掘算法
输入：日志数据集Data, 最大类别数k, 关键词阈值λ1, 关键词比例阈值λ2, 日志比例阈值λ3
输出：日志模板集T
1 压缩日志集Data生成新日志集D
2 do二分搜索:
3 当前搜索值mid
4 随机初始化日志聚类C, C中包含mid个类别
5 设置C′为空集
6 while C!=C′ do
7 C=C′
8 遍历搜索D中每条日志的
9 end while
10 根据λ1, 统计生成C中各类别关键词
11 根据λ2, 统计生成D中聚类成功日志所占比例r
12 根据λ3和r, 更新二分搜索区间值
13 while二分搜索区间>1
14 根据日志聚类C, 提取日志模板集T
15 return T
算法实现过程的详细步骤如下.
1) 对待处理的日志进行数据压缩
日志输出系统中存在着大量形式固定、易于检出的参数，如uuid、IP地址等.首先使用正则表达式去除日志中已知形式的参数；之后采用统计词频的方式构筑关键词词典.在对单词在全体日志中出现的频数进行统计后，统一设定一个阈值，频数大于该阈值的单词构成初步关键词表.为了实现对关键词更精确的提取，对初步关键词中的单词判断其是否属于以下3个类别：
① 符合英文基本语义的单词，如：apple, book;
② 计算机领域的专业词汇，如：dns, dhcp;
③ 对于特定的日志集，常出现特定表示，例如：BUPT.
对于符合英文基本语义的单词选择，使用PyEnchant作为筛选器辅助筛选.
若单词不属于以上3种类别中的任何一个，则剔除出关键词表.
利用关键词词典，使用01词袋模型对单条日志构筑一个n维的01向量，向量相同的日志只保留一条，实现对原始数据进行压缩.由此方式可以使得进入聚类算法的日志数量大大降低，减少由数据冗余带来的额外系统资源消耗，有效提高算法效率.
2) 对日志进行聚类
算法首先依据二分搜索初始值给出一个聚类数目的初始值k.先将日志随机划分成数量均匀的k类，在二分搜索每一次的判别过程中对每条日志进行转移增益函数计算，将其分到增益函数最大的聚类.
给定一个聚类C，T(C)表示聚类C的日志中所有有序单词对的集合.例如，以下是来自某应用程序的一条日志：
2017-08-23 14:46:28.579ERROR: Not exist file "config.py"
通过正则表达式，去除时间参数，得到
ERROR: Not exist file "config.py"
两两提取日志中的单词，并保留其顺序，形成有序单词对：
{ERROR:, Not }, {ERROR:, exist },
{ERROR:, file }, {ERROR:, "config.py" },
{Not, exist}, {Not, file}, {Not, "config.py"},
{exist, file}, {exist, "config.py"},
{file, "config.py"}
经过转换，有序单词对集合不仅可以保留日志中单词的顺序，并且与直接对日志进行操作相比，可以降低后续计算的时间复杂度，进一步提高算法效率.
对于任意有序单词对t∈T(C), N(t, C)表示C中包含t的日志的数量，s(t, C)=N(t, C)/|C|表示C中包含t的日志所占比例.
定义ϕ(C)为聚类C的聚类纯净值，
| $ \phi (C)=\sum\limits_{t\in T(C)}{N}(t, C){{\left[ s(t, C) \right]}^{2}} $ | (1) |
聚类纯净值用来衡量聚类中日志的“纯净”程度.当聚类包含的日志属于同一类的比例越高，所包含日志条目数越大，则该纯净值越大.
由此，定义日志集合D的整体纯净值为
| $ \mathit{\Phi }(D) = \sum\limits_{i = 1}^k \phi \left( {{C_i}} \right) $ | (2) |
其中：D被划分为k个聚类，ϕ(Ci)为每个聚类的纯净值，i=1, 2, …, k.
转移增益函数的计算方式为
| $ \begin{align} & {{\mathit{\Delta }}_{i\xrightarrow{x}j}}\mathit{\Phi }(D)=\left[ \phi \left( {{C}_{j}}+\{X\} \right)-\phi \left( {{C}_{j}} \right) \right]+ \\ & \left[ \phi \left( {{C}_{i}}-\{X\} \right)-\phi \left( {{C}_{i}} \right) \right] \\ \end{align} $ | (3) |
其中：
反复进行
3) 使用归一化特征判断当前聚类数目是否满足要求
对当前聚类结果进行判断.若聚类数目可以满足实际需求，则聚类结束，进入下一步骤；若聚类数目过多或过少，则需进一步调整k值，重新进行聚类过程.
由于不同日志集合的k值不同，甚至差别非常大的，在设定了参数提取成功的要求后，满足要求的日志即认为模板挖掘成功的日志数量是一定的，因此提出基于一个归一化的特征进行判断，通过设定满足要求的日志在总体中所占得比例r，在这个比例和k值有正相关关系时，使用多次二分搜索的方式得出k值.
假设日志集合中任意一条日志为d，每条日志中的一个单词为w，设定日志模板挖掘成功的条件如下.
① 对于模板挖掘成功的日志，其参数数量应当小于x，参数所占比例p < λ1，该比例能够根据不同的日志系统进行调整.其中对于参数的判断条件为：某单词在聚类中的日志样本里出现的比例q < λ2，认为该单词是参数.
| $ {p_i} = \frac{{\sum\limits_j^{\left| {{d_i}} \right|} {\left( {{q_j} < {\lambda _2}} \right)} }}{{\left| {{d_i}} \right|}} $ | (4) |
| $ {q_j} = \frac{{\sum\limits_i^{{N_d}} E \left( {{w_j}, {d_i}} \right)}}{{{N_d}}} $ | (5) |
其中：E(wj, di)表示单词wj是否出现在日志di中，若是，值为1；否则值为0.
② 模板挖掘成功的日志在全体日志集合中所占比例r>λ3.
| $ r = \frac{{\sum\limits_i^{{N_d}} {\left( {{p_i} < {\lambda _1}} \right)} }}{{{N_d}}} $ | (6) |
设定以上条件后，k值和r值就具有了一定的正相关性，在OpenStack日志数据集的实验结果如图 2所示.因此，利用二分搜索的方式可以自动地定位到k值.为获得较为稳定的k值，可以进行多次二分搜索，并对得到的结果取平均值作为最终的聚类数目.由于λ1、λ2、λ3是归一化到[0, 1]区间内且有物理意义的特征，所以受不同类型日志文本特征的影响较小.这样，对于不同类型的日志集合，都能够得到相应的聚类数目k，并根据该k值自动进行日志聚类以及后续的模板挖掘过程.
|
图 2 OpenStack日志数据集上k值与r的相关性 |
现有的模板挖掘提取算法大多需要人工干预的过程，所提出的无监督、可以自更新的模板挖掘算法解决了传统的基于聚类的模板挖掘算法中聚类数目k需要人工预先设定的问题，对不同类型的日志数据集可搜索出合适的聚类数目；此外，考虑到日志数量可能非常庞大，算法对日志数据先进行压缩再处理，使得进入算法的日志数量大大降低，在处理大规模日志数据时仍能保持较高的效率.
3 评价标准现有日志集合Data，经过数据压缩后得到包含压缩去重后的n条日志的集合D，设有Gi条日志对应去重后的日志Di.
标准模板(此处将人工提取的日志模板称为标准模板)拥有一个模板集合T，包含m个日志模板，即T将D划分成了m类，类别n中包含了Ki条日志，且有
经过模板挖掘算法后得到一个模板集合T′，其中包含m′个日志模板，D中任意一条日志对应且仅对应T′中的一个模板.
现提出一个衡量日志模板匹配度的评价标准，将模板挖掘算法产生的T′在D上与参考标准T的差异度定义为
| $ {\rm{NotMatch}}\left( {T, {T^\prime }} \right) = \\\frac{{\sum\limits_i^n {\left\{ {\left[ {\max \left( {\left| {F\left( {{D_i}} \right)} \right|, \left| {{F^\prime }\left( {{D_i}} \right)} \right|} \right) - \left| {{\rm{WLCS}}\left( {F\left( {{D_i}} \right), {F^\prime }\left( {{D_i}} \right)} \right)} \right|} \right]} \right\}} \max \left( {{{\log }_{10}}{G_i}, 1} \right)}}{{\sum\limits_i^n {\left| {F\left( {{D_i}} \right)} \right|} \max \left( {{{\log }_{10}}{G_i}, 1} \right)}} $ | (7) |
匹配度即为
| $ {\rm{Match}}\left( {T, {T^\prime }} \right) = 1 - {\rm{ NotMatch }}\left( {T, {T^\prime }} \right) $ | (8) |
其中：F(Di)表示日志Di在T中对应的模板，F′(Di)表示日志Di在T′中对应的模板；|F(Di)|表示模板F(Di)中包含的单词个数；WLCS(d, d′)表示以单词为最小单位进行比较的两条日志的最长公共子(单词)序列.
对于单条压缩后的日志，使用基于最长公共子序列(WLCS, word longest common subsequence)的方法判断日志与真实模板的相似度，经取补变换后获得差异度.单条压缩后日志产生的差异度与其在源数据集中数量的对数相乘，并加权求和，可以解决源数据分布不均的问题；最终结果除以总差异度从而归一化到[0, 1]区间，并百分化，使得评判标准能够很好地衡量日志模板的匹配程度.
4 实验 4.1 实验数据实验在2个数据集上进行.其中OpenStack数据集采集自OpenStack分布式系统日志，大小约439 MB，共约700万条日志，经正则表达式去参和01词袋模型压缩后共有767条互不相同的日志，人工标注类别257类；Ubuntu数据集采集自Ubuntu操作系统日志，大小约1.37 MB，共有19 228条日志，经正则表达式去参和01词袋模型压缩后包含2 706条互不相同的日志，人工标注类别8类.
4.2 实验结果与分析分别执行所提出的基于归一化特征的模板挖掘算法与传统的基于01词袋模型的模板挖掘算法(简称基于01词袋模型)、基于编辑距离的模板挖掘算法(简称基于编辑距离)和IPLoM算法，比较模板挖掘的匹配度，得到的实验结果如表 1所示.
|
表 1 4种日志模板挖掘算法的匹配度对比 |
从表 1可以看出，基于01词袋模型和基于编辑距离的模板挖掘算法和IPLoM算法在操作系统日志数据集上参数识别效果差；在OpenStack数据集上，4种算法的匹配效果差异不大.而本算法在2个数据集上都取得了较好的效果，在Ubuntu操作系统日志数据集上的效果尤为明显.
由于OpenStack日志数据集的数据量、参数量较多，形式较为复杂，符合正则表达式规则的部分也比较大，仅使用正则表达式去参并利用词频进行压缩后，已经能够取得一定的效果.若进一步进行模板挖掘，虽能够识别一定量的参数，但也会对其中部分模板元素产生误识别，从而降低总体的识别效果. Ubuntu操作系统日志集形式较为简单，参数量少，但参数在日志中的占比相对较大，容易对部分算法产生误导.
对于复杂的OpenStack日志数据集来说，尽管通过初步的参数识别过程已经能够取得较好的效果，但各算法的错误依然集中在将部分关键词也视为参数，导致各算法将很多相似类别的日志识别为同一类；而这部分关键词多数为符合英文语义的单词，在算法的第1步中已经进行过滤.为验证这一步骤的必要性，设计实验验证了筛选关键词对模板挖掘匹配度的影响.实验结果如表 2所示.
|
|
表 2 4种日志模板挖掘算法+关键词筛选的匹配度对比 |
从表 2可以看出，在加入关键词筛选后，各算法的表现均有提升.对于OpenStack日志，由于其本身形式较复杂，基于01词袋模型和基于编辑距离的算法在该数据集上的效果提升不明显；IPLoM和本算法在提供了英文单词的先验信息后效果提升明显.
通过设计和日志聚类内容相关的纯净值特征表示，本算法不仅能够保证聚类中样本之间是相似的，也可保证整个聚类能够提取出一个公共部分，有效避免了模板元素被识别为参数的情况.基于归一化特征判别的模板挖掘算法通过设定和聚类数目无关的归一化特征，能够避免不同日志集的类别数量差异，从而具备较好的泛化能力.
5 结束语日志模板挖掘是日志分析领域的重要部分，是进行系统异常检测的基础工作.针对大规模日志的模板挖掘，现有方法在缺乏先验信息的情况下效果较差.笔者提出基于归一化特征的日志模板挖掘算法，在依赖的先验信息更少时能够取得更好的效果.实验证明算法的模板挖掘准确率高，并且相对于其他算法可以更好的适应各种类型的日志，具有较好的泛化能力.
| [1] |
董蜻灵, 李芳, 何婷婷.基于LDA模型的文本聚类研究[C]//孙茂松, 陈群秀.中国计算语言学研究前沿进展(2009r 2011).北京: 清华大学出版社, 2011: 455-461.
|
| [2] |
Vaarandi R. A data clustering algorithm for mining patterns from event logs[C]//Proceedings of the 3rd IEEE Workshop on IP Operations & Management (IPOM 2003). Kansas City: IEEE, 2003: 119-126.
|
| [3] |
Fu Q, Lou J G, Wang Y, et al. Execution anomaly detection in distributed systems through unstructured log analysis[C]//2009 Ninth IEEE International Conference on Data Mining. Miami: IEEE, 2009: 149-158.
|
| [4] |
Makanju A, Zincirheywood A N N, Milios E E. Clustering event logs using iterative partitioning[C]//Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2009: 1255-1264.
|
| [5] |
Makanju A, Zincirheywood A N N, Milios E E. Investigating event log analysis with minimum apriori information[C]//Ifip/IEEE International Symposium on Integrated Network Management. Ghent: IEEE, 2013: 962-968.
|
| [6] |
Tang L, Li T, Perng C S. LogSig: generating system events from raw textual logs[C]//Proceedings of the 20th ACM International Conference on Information and Knowledge Management. New York: ACM, 2011: 785-794.
|
| [7] |
Nandi A, Mandal A, Atreja S, et al. Anomaly detection using program control flow graph mining from execution logs[C]//ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2016: 215-224.
|
| [8] |
Vaarandi R, Pihelgas M. LogCluster-A data clustering and pattern mining algorithm for event logs[C]//2015 11th International Conference on Network and Service Management (CNSM). Barcelona: IEEE, 2015: 1-7.
|
| [9] |
Aharon M, Barash G, Cohen I, et al. One graph is worth a thousand logs: uncovering hidden structures in massive system event logs[C]//Joint European Conference on Machine Learning and Knowledge Discovery in Databases. Berlin: Springer, 2009: 227-243.
|
| [10] |
Vaarandi R. A breadth-first algorithm for mining frequent patterns from event logs[C]//International Conference on Intelligence in Communication Systems. Berlin: Springer, 2004: 293-308.
|