-
Notifications
You must be signed in to change notification settings - Fork 19
文本增量式聚类算法
首先我们要简述一下为什么要做文本的泛化和聚类，以及为什么要做增量式聚类。
我们在日志系统中会接受到很多的报警信息，这些报警信息可能是因为系统的某个点故障了造成的，例如下面几条文本：
Server CDH-NAME-1 disconnected caused by timeout.
Server CDH-NAME-2 disconnected caused by timeout.
Server CDH-NAME-5 disconnected caused by timeout.
很明显，这些报警可以使用以下的形式来泛化：
Server CDH-NAME-* disconnected caused by timeout.
或者详细一点：
Server CDH-NAME-{1,2,5} disconnected caused by timeout.
我们知道是CDH集群的NAME节点掉线了几个，这个时候我们要检查所有的NameNode是否有配置不当或者其他问题。
这样的信息会有很多很多，肉眼根本来不及看，如果泛化做得好，可以大大减少看日志的时间。
如果这个时候又追加了两条信息，这个时候我们的泛化信息就需要变化了：
Server CDH-ADMIN-0 disconnected caused by timeout.
Server CDH-DATA-10 disconnected caused by timeout.
这个时候我们发现各个服务器陆续掉线，可能并不是NameNode的问题，而是一些基础的网络设施的故障，那么我们可以考虑从网络排查。
这个时候的泛化信息记作：
Server CDH-* disconnected caused by timeout.
或者详细一点：
Server CDH-{NAME-1,NAME-2,NAME-5,ADMIN-0,DATA-10} disconnected caused by timeout.
当然如果我们做二层的泛化，甚至是三层，我们可以得到更加通俗的结果（当然对前端展示带来一定挑战）：
Server CDH-{NAME-{1,2,5},ADMIN-0,DATA-10} disconnected caused by timeout.
除了泛化的信息可能随着日志的到来变化，在聚类的时候如何做到常数级别时间也是重要的问题。 例如我们现在聚类完成了，目前有k类，每一类有Ni(i \in [1,k], i \in Z)条日志。
这个时候来了一条新的日志，我们需要做2件事情：
- 快速筛选，决定和哪几类做计算，最后挑出一个
- 将这条日志和之前的日志进行合并，更新这一类
随着日志的过来，如果不能保证每条日志的常数时间处理，那么结局会很悲惨。
核心其实很简单，就是最大公共字符串求取算法。无非就是在N串字符串中不断“压榨”出新的公共字符串。
如果不能理解，那么可以看看下面的例子：
Server CDH-NAME-1 disconnected caused by timeout on 5001ms.
Server CDH-NAME-2 disconnected caused by timeout on 5002ms.
Server CDH-NAME-5 disconnected caused by timeout on 5010ms.
首先我我们找出公共部分， disconnected caused by timeout.，随后泛化成了：
{Server CDH-NAME-1,Server CDH-NAME-2,Server CDH-NAME-5} disconnected caused by timeout on {5001ms,5002ms,5010ms}.
这个时候分别对{Server CDH-NAME-1,Server CDH-NAME-2,Server CDH-NAME-5}和{5001ms,5002ms,5010ms}继续进行泛化。
Server CDH-NAME-{1,2,5} disconnected caused by timeout on 50{01,02,10}ms.
这个时候，我们注意到时间被泛化成了：50{01,02,10}ms.，这个其实不是最友好的方式，我们可以提出更友好的方式：{5001,5002,5010}ms。
但是如何实现这一点呢？其实也不复杂，将字母+数字归为一类，其它所有的字符（中文字符们，对不起了）归为另一类，然后以这个为依据切断。
切断的方式也很简单，用正则就行了：
[^0-9a-zA-Z]+|[0-9a-zA-Z]+下面是我们在实际日志上的一个实战：
可以看到，{12461700, 12461702, 12461698}的类里面没有将公共的12461提取出来。
can't connect to mysql server ,errmsg:Unknown database 'cvnavidb' MySQLConnection [id={12461700, 12461702, 12461698}, lastTime=1551971922856, user=cvnavidb, schema=cvnavidb, old shema=cvnavidb, borrowed=false, fromSlaveDB=true, threadId={298807, 298805, 298809}, charset=utf8, txIsolation=3, autocommit=true, attachment=null, respHandler=null, host=IP不能告诉你, port=端口也是, statusSync=null, writeQueue=0, modifiedSQLExecuted=false]
想要做到增量式算法，那么有一点一定要做到，就是不能依赖以前的日志，而是要依赖一个中间状态量，这个状态量再复杂，毕竟也只有一个。
我们决定将这个状态量叫pattern，也就是这个日志的模式。 这个pattern是一个String数组（或者用List也行），代表着日志中必需出现的字符。
例如：
pattern = [ "a=1 b=", " c=", " d=" ]这个pattern就可以容纳a=1 b=2 c=3 d=4这样的日志，但是不能容纳Server CDH-NAME-1 disconnected caused by timeout on 5001ms.这样的日志。
那么问题来了，如果遇到了：a=2 b=6 c=3 d=4这样的日志怎么办？
这个时候我们就需要对原有的Pattern进行更新，更新操作的原理也很简单，首先找到后面一个模式的匹配位置，也就是" c="的位置，找到以后取出前面的部分：a=1 b=6 ，将这个字符串和a=1 b=进行互操作，原理和上面的聚类算法一样，我们得到更新后的pattern。
pattern = [ "a=", " b=", " c=", " d=" ]这里还有一个容易引起BUG的地方，就是在匹配之前必需先运行LCS（这里的S是Sequence了）算法，判断大致的相似度，否则pattern很容易提取出几个空格来。
这里的相似度我们使用类似Jaccard相似度的定义：sim=\frac{common(s_1,s_2)}{max(len(s_1),len(s_2))}
并不是所有的泛化聚类都和消息体的聚类一样难缠，我们还有其他的聚类算法：
也就是我们之前说的算法，将相同的部分聚合到一起，例如：
flink/a/jiading/1
flink/b/jiading/2
flink/b/jiading/1
泛化为：flink/{a,b}/jiading/{1,2}
一般用在有层级结构的地方
flink/a/jiading/1
flink/b/jiading/2
flink/b/jiading/1
泛化为：`flink/{a/jiading/1,b/jiading/2,b/jiading/1}
一般用在类似文件夹表达的地方：
flink/a/jiading/1
flink/b/jiading/2
flink/b/jiading/1
泛化为：
flink/{
a/jiading/{
1,
2
},
b/jiading/1
}
可以展现为树形结构。
以上两种都非常容易实现增量式算法，因为太简单，这里就不赘述了，还有其他算法的话欢迎补充。