Better algorithm to correlate semi-structured data

Question

I have the need to match incoming fragments of semi-structured text to previously encountered fragments.

The most text fragments are sized ~200 to ~4000 characters and contain both human-readable text (a few sentences at most) and machine-generated text - string and numberic codes, IDs, URIs etc.

I've used K-Means clustering with various distance measures with some success but it's too slow for large datasets (or maybe it's my implementation?) - ~1000 items get clustered in about 30 sec but 10000 take over 10 min to produce ~150 clusters.

I tried LSH/Minhash but the probabilistic nature of the hashes sometimes misses important tags and misplaces some of the fragments as a result, plus the hash calculation doesn't improve speed much for such small texts - the cost of calculating 300 hash values is not 0 and then the array of 300 values is in the vicinity of the number of "words" the fragments get broken into anyway.

What is the fastest clustering algorithm that would be suitable for the task? Ideally something that I could implement from scratch, not a ready software/service/package.

Idea what the input looks like:

[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

I have the need to match incoming fragments of semi-structured text to previously encountered fragments.

So by your problem domain the possible output could be classed as categorical where each previous fragment is a category which new incoming text could be assigned to.

Naive Bayes as a text classification algorithm is highly scalable and performs in linear complexity time. A NB algorithm looks at features in a class without focusing on whether these features depend on each other or upon the existence of the other features, all of these properties independently contribute to the probability that your event is within a class, hence being dubbed ‘Naive’, and hence running in linear time without comparison to each vector of your class language.

Being a probability classifier a Naive Bayes algorithm can be comfortable constructed from scratch. There are many Youtube videos showing how to apply it with Machine Learning and Language Processing packages, for a more fundamental understanding check out the link here.

That said Naive Bayes algorithms are generally supervised learning whilst your current method of application through K-means applies unsupervised learning.

Answer 2

Depending on the length of your Strings you might consider a raw String distance metric like the Levenshtein Distance. This metric is quick and easy to compute.

The downside of this metric is that it won't consider "out of order" input to be similar. For example "WORD_A WORD_B" WORD_C WORD_D" is not close to "WORD_D WORD_C WORD_B WORD_A".

The upside of this metric (other than speed) is that it will quickly group things like "SOME_TEXT COMMON_ERROR_MESSAGE" with other similar messages.

It is promising that you can get K-means working "somewhat successfully" with small datasets. Chances are good you could get larger sets working almost as quickly if your implementation samples your dataset first.

Try something like:

1. Choose a n% sample of your big dataset
2. Perform K means on that sample
3. Consider the clustering "done".
4. Classify the remaining 100-n% of your dataset by "fitting" them to the existing clustering result. You are basically relying on the fact that if K << SIZE_OF_DATASET then you don't need to worry too much about which data point are members of the n% sample you used to generate your clustering.

Answer 3

Edit: new metric

Since it should be fast, let's find a simpler metric. :)

---

First, split the lines into words (simple space splitting, ignoring everything else)

Given 2 lines, with respectively N and M words. Let the "similarity" be:

similarity = 2 * S / (N + M)

where S is the amount of words in common. Which should be quick to compute using a hash set.

Since the coming algorithm is based on a threshold, you can even discard this computation when the amount of words differs too much and set it to 0.

---

As an alternative to fancy k-means or other advanced clustering algorithms, I suggest something much simpler. Dunno if it has a name.

Basically, for each line, check what cluster the line is "closest" to by comparing it to a random item of it. If the similarity reached a certain threshold, add it to the cluster. Otherwise create a new cluster containing this single line.

...it's perhaps not the best, but it should be very efficient while providing satisfactory results.

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

The complexity would be O( N * k ) where N is the number of lines, and k the number of clusters, which depends on the threshold.

Answer 4

I have used cosine similarity past 100K here.

A trick is to do the sqrt(sum(a[i] * a[i])) once and store it.

Do a running sum(a[i] * b[i]) and give up when it does not have a chance.