半结构化数据关联的更好算法

Question

我需要将半结构化文本的传入片段与以前遇到的片段进行匹配。

大多数文本片段大小为200 ~4000字符，包含人类可读的文本(最多只有几个句子)和机器生成的文本字符串和数字代码、ID、URI等。

我使用了K-均值聚类和各种距离度量，取得了一些成功，但对于大型数据集(或者可能是我的实现？)-~1000个项目在30秒内被聚在一起，但是10000需要超过10分钟才能生成~150个集群。

我尝试了LSH/Minhash，但是散列的概率性质有时会遗漏一些重要的标记，并因此错误地放置了一些片段，另外，散列计算对于这样的小文本并没有提高多少速度--计算300个哈希值的成本不是0，然后300个值的数组就在碎片被破解成的“单词”的数量附近。

什么是适合于任务的最快的聚类算法？理想情况下，我可以从头实现一些东西，而不是现成的软件/服务/包。

知道输入是什么样子的：

[Timestamp] A package of type Box with ID 123456 was not successfully checked in. [FKFGSIGURE] 12345 ~\logs\checkin\17-08-01.log Host:123.123.123.123 Pod:somepodname <...more stuff here...>

[DateTime] Invalid access attempt at Door 123. Badge XYZ was declined access. Suspending badge for 5 minutes. 23456 ~\logs\checkin\17-06-01.log Host:13.23.13.12 <...more junk...>

[Date] [Time] Host: 2.3.4.5 restart failed

etc x100000

Answer 1

我需要将半结构化文本的传入片段与以前遇到的片段进行匹配。

因此，根据您的问题域，可能的输出可以被归类为分类，其中前面的每个片段都是一个类别，新传入的文本可以分配给这个类别。

朴素贝叶斯算法作为一种文本分类算法，具有很高的可扩展性和线性复杂度。NB算法查看类中的特征，而不关注这些特征是相互依赖还是依赖于其他特征的存在，所有这些属性都独立地贡献了事件在类内的概率，因此被称为“朴素”，因此在线性时间内运行，而不与类语言的每个向量相比较。

作为一种概率分类器，朴素贝叶斯算法可以很好地从头构造。有许多Youtube视频演示了如何将其应用于机器学习和语言处理包，以获得更基本的理解--查看链接这里。

也就是说，朴素贝叶斯算法通常是监督学习，而你目前通过K-均值应用的方法是无监督学习。

Answer 2

根据字符串的长度，您可能会考虑一个原始的字符串距离度量，比如Levenshtein距离。这个度量是快速和容易计算的。

这个指标的缺点是它不会认为“无序”输入是相似的。例如，"WORD_A WORD_B“WORD_C WORD_D不接近"WORD_D WORD_C WORD_B WORD_A”。

这个指标(除了速度)的好处是，它将很快将"SOME_TEXT COMMON_ERROR_MESSAGE“之类的信息与其他类似的消息组合在一起。

它是有希望的，你可以得到K-意味着“在一定程度上成功地”使用小数据集。如果您的实现首先对数据集进行采样，则很有可能会得到更大的集，几乎可以同样快地工作。

试一试如下：

1. 选择大数据集的n%样本
2. 对该样本执行K均值
3. 考虑集群“已完成”。
4. 通过将其余的100%-n%的数据集与现有的群集结果“匹配”，将其分类。基本上您所依赖的事实是，如果K << SIZE_OF_DATASET，那么您不需要过多地担心哪个数据点是用于生成集群的n%样本的成员。

Answer 3

编辑:新的度量

既然它应该是快速的，那么让我们找一个更简单的度量。:)

首先，将行拆分成单词(简单的空格分割，忽略其他一切)。

给定2行，分别用N和M字表示。让“相似性”是：

相似性=2*S/ (N + M)

S在这里的用词有很多共同之处。使用哈希集快速计算。

因为即将出现的算法是基于阈值的，所以当字数相差太大时，您甚至可以放弃此计算，并将其设置为0。

作为对k均值或其他高级聚类算法的替代，我建议一些简单得多的方法。不知道它有没有名字。

基本上，对于每一行，通过将其与任意项进行比较，检查这条线“最接近”的集群是什么。如果相似度达到某个阈值，则将其添加到集群中。否则，创建包含此单行的新群集。

.这也许不是最好的，但它应该是非常有效的，同时提供令人满意的结果.

clusters = [] for line in log: tokens = line.split() candidate = None for c in clusters: c_tokens = tokens of the an item in the cluster c sim = similarity(tokens, c_tokens) if sim > threshold and is the best so far: candidate = c if candidate found: add the line/tokens to candidate found else: add a new cluster containing this line/tokens

复杂度为O( N*k)，其中N为行数，k为簇数，这取决于阈值。