FTCA Data Clustering Algorithm

Foreword

Walking through the English-speaking expanses of the Internet in search of a solution to one of the painful topics at work, I came across a very interesting algorithm called “Fast Threshold Clustering Algorithm”. This clustering algorithm, which is noteworthy, appeared relatively recently, namely in November of this year, and the author is David Varadi. A link to the source will be available at the end of the article.

For starters, what is clustering?

Clustering is a program that allows you to create from a certain set of objects - groups (hereinafter referred to as clusters), formed by meaning or content, the number of these groups, while it may not be known in advance. These objects can be either documents or numbers, depending on what needs to be grouped.
There are many diverse clustering algorithms ranging from the usual K-means in a variety of implementations and interpretations, and ending with more complex algorithms to understand, which may include suffix trees (STC) or higher mathematics (Lingo, SVD, etc.). A common problem that overtakes a certain algorithm is a mistake. A mistake always takes place to be, especially when we are talking about documents that contain real human speech. Indeed, it is not always clear to the machine where to put the tale about Tsar Saltan: to politics, to the history of ancient Russia, or to create a cluster? Objects can have many relationships with other objects for different properties. They are still struggling with this task.

And how to avoid this error?

There are many ways to avoid errors. You can clearly highlight the key properties of the object, which by no means can be in one cluster, but ideally can approach another. For example, in the example above, you can search for the presence of the words “lived-were”, “kingdom-state” and the like, and do not include this document in certain clusters. And you can make a graph of dependencies between objects and already looking at this graph make further inferences (This method works, for example, SCT and Lingo). There are many solutions, even a crutch condition for satisfying a property on certain data sets can significantly increase the accuracy of clustering as a whole.

And what kind of algorithm did you talk about at the beginning?

The algorithm described by David attracted my attention not by its asymptotics or practical applicability, but by its simplicity. It is built on ordinary human logic and is very similar to other algorithms.

First, imagine that we have a set of objects that we want to group and a function that says how much the two objects are similar to each other in percentage terms:
F (x, y) = F (y, x) = ...%
- correlation function of two objects.
(Actually this is all that the human brain usually uses when grouping objects.)

Next, we introduce the concept of average similarity:
G (x, y1, y2, ..., yn) = SUM (F (x, yk)) / n
- This function shows how much the object resembles a group of other objects.

Algorithm

At the very first (and long) step, it is required, for convenience, to sort all our objects by their average correlation with other objects in ascending order. That is, we get a list of the first element of which will be the element with the smallest average correlation, and the last, on the contrary, with the largest.
Next, we should decide how many clusters to create and by what principle. What is the principle? And this is our Treshold - the very border above which the objects are considered similar enough to be together, in the same group.

Clusters are created according to the following algorithm:
1) Sort objects.
2) We take the first and last object from our sorted list.
• If their correlation is greater than our border of similarity - we create one cluster with the first elements of these two objects and find all the objects from the remaining ones, the average correlation of which with the whole cluster will be more than a trashhold.
• If their correlation is less than the similarity boundary, we create two clusters of elements in which they will fall according to the same principle as described above.
3) If there is one object left - create a separate cluster and shove it there. Otherwise, we return to step 1.

That's all, in the end you should get a fairly stable cluster. It is noteworthy that this algorithm quite sensibly creates separate clusters for objects that do not fit anywhere and there is the ability to adjust the percentage similarity parameter. Thus, these objects create their own habitat and do not allow an error that does not go through the trashhold to get into this habitat and spoil the whole picture.
Also, if you dig deeper into the logic, you can understand that the algorithm is very flexible in the sense that we can quite easily increase the accuracy at a loss of speed or vice versa. For example, adding a movable trashhold function for each cluster, which will show what the average connectivity of objects within the cluster is. Thus, the error will not decrease, it will decrease (although inserting an element into the cluster will trigger a recalculation of this trashhold, which will kill performance). In the opposite direction, on the contrary, you can reduce the accuracy of the algorithm and increase performance by adding an object to the cluster that resembles only the standard, the core of the cluster.

Summary

Summing up, I want to say that even I still do not understand why David began the name with the word “Fast”, which means “Fast”. This algorithm, of course, cannot be called fast unless you use the huge correlation matrix of each object with each + average values ​​for each object, but calculating all this is a very difficult operation, due to the possible complexity of the correlation function itself. Theoretically, the idea is very good, practically the same - it can process small amounts of data.
The usual asymptotic complexity of the algorithm is O (n ^ 3) of the possibly complex function F (x, y). When using the correlation matrix, we get O (n ^ 2) in speed and O (n ^ 2) in memory, which will knock out all the traffic jams from the RAM. These are the pies, dear Khabrachane.

Next time I will try to tell you about the results of my testing of this algorithm.

Source: cssanalytics.wordpress.com/2013/11/26/fast-threshold-clustering-algorithm-ftca