1

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

  • How are you matching? – paparazzo Jul 11 '17 at 21:59
  • Question is too vague. A small example of the input and desired output would be highly beneficial. What is the exact goal? – dagnelies Jul 13 '17 at 14:16
  • @dagnelies sample input, made up to kind of represent the log files I'm dealing with – Sten Petrov Jul 13 '17 at 17:47
  • @Paparazzi I've tried Cosine distance between bags of words, Minhashing and LSI. They all work to at least some extent (Cosine performs best in terms of accuracy and speed) but neither of them scale past 100K – Sten Petrov Jul 13 '17 at 17:49
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.

  • The supervised learning part is highly problematic - my input can have new 'classes' of fragments pop into existence or old ones stop showing up. Some are short-lived in the order of hours, some are very long lived, in the order of months and the stream of 'events' doesn't stop. – Sten Petrov Jul 10 '17 at 17:53
  • 1
    Hmm well the problem set of unsupervised speed optimized text classification faster than K-Means O(kn) sounds like a challenge. There's the possibility of applying a Gibbs sampler with an Unsupervised Naive Bayes Classifier. Otherwise you can set up a process to train a supervised learning model (NB/RNN) which trains a model with new data adds prior occurrences to the new model classification count. When the model is complete the current results and model are switched with the new model and set this process to happen per unit time. – Julian Wise Jul 11 '17 at 13:02
1

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.
  • The problem here is that with time I have to accommodate unknown fragments that would belong to a new cluster. If I use a sample to "learn" the clusters then such new clusters wouldn't form – Sten Petrov Jul 13 '17 at 20:21
  • Also Levenshtein is too expensive, 100+ tokens in a fragment would be too heavy to measure via Levenshtein – Sten Petrov Jul 13 '17 at 20:22
0

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.

  • Levenshtein is too slow for large number of tokens, ~O(n^2). The proposed method is not too far from selecting a centroid in a cluster, your c_tokens. The total complexity of clustering N fragments that are broken into F fragments each and fall into K clusters would then be ~O(NLF^2), which is way too much – Sten Petrov Jul 13 '17 at 20:40
  • I thought you had at most ~4000 chars per line. ...so perhaps 100 words per line. It shouldn't be a biggy to compare 2 such lines. – dagnelies Jul 13 '17 at 20:41
  • 4Kb, even with avg word length of 10 would still amount to 400 tokens... In reality most fragments break down into between 100 and 200 tokens. Even if I bring that down with very aggressive cleanup there would still be 50-100 tokens – Sten Petrov Jul 13 '17 at 20:48
  • @StenPetrov ...you're right, here is a simpler metric suggestion – dagnelies Jul 13 '17 at 21:03
  • This is Cosine similarity, which I'm already using. One minor difference in my implementation is Similarity = S/Max(N,M) – Sten Petrov Jul 13 '17 at 21:10
-2

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.

  • So that's >10GB RAM if you use short for 100K fragments and it takes square time to calc the matrix. Already doing that and besides computational time this is the other limit I'm hitting. 200K fragments - 40GB, 300K - 90GB... While I could use a 400GB RAM machine rented in the cloud it would cost a fortune at the computational times I'm seeing. – Sten Petrov Jul 13 '17 at 18:21
  • How long are the vectors you're multiplying? – Sten Petrov Jul 13 '17 at 18:22
  • You are doing it multiple times currently. Matrix square time? There would be no purpose to a matrix. Multiply 2 number is fast. Did I say it had to be in memory. Question say text fragments are sized ~200 to ~4000 characters. This cuts processing by 2/3 and you just dismiss it. If you have space to store the vector you have space to store sum. Sorry I tried to help. – paparazzo Jul 13 '17 at 18:32
  • 1
    I'm not clear what is it you're proposing. You can quickly compare 2 vectors, especially if they aren't too long. But then you need to do that O(n^2) where n is the number of fragments. What is the exact algorithm you're proposing, your answer only focuses on the distance measure – Sten Petrov Jul 13 '17 at 18:55
  • 1
    huh? 2/3 of what, how? – Sten Petrov Jul 13 '17 at 20:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.