{'fraction_non_alphanumeric': 0.029221357724060107, 'fraction_numerical': 0.014610678862030053, 'mean_word_length': 4.55893034004622, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Real-time Clustering Algorithm Based on Predefined Level-of-Similarity

This paper proposes a centroid-based clustering algorithm which is capable of clustering data-points with n-features in real-time, without having to specify the number of clusters to be formed. We present the core logic behind the algorithm, a similarity measure, which collectively decides whether to assign an incoming data-point to a pre-existing cluster, or create a new cluster&assign the data-point to it. The implementation of the proposed algorithm clearly demonstrates how efficiently a data-point with high dimensionality of features is assigned to an appropriate cluster with minimal operations. The proposed algorithm is very application specific and is applicable when the need is perform clustering analysis of real-time data-points, where the similarity measure between an incoming data-point and the cluster to which the data-point is to be associated with, is greater than predefined Level-of-Similarity.


Introduction
The main gist behind clustering is to group data-points into various groups (clusters) based on their features i.e. properties. The generation of clusters basically varies application wise (Xu and Wunsch, 2005); because it depends on what factors are to be taken into consideration to form a particular cluster. But, the focus of every clustering algorithm remains same i.e. to group similar data-points to a common cluster. The thing that differs is how this goal of forming a cluster is achieved. Different algorithms use different concept to deal with similarity measure among the data-points. There are many popular clustering algorithms (Hartigan, 1975) that group data-points based on various strategies to define the similarity measure between them. Centroid-based, connectivity-based, density-based, graph-based, etc are the commonly used strategies.
Often used algorithms like k-means, hierarchical clustering, DBSCAN, etc require a set of data-points in space beforehand. Without making fine adjustments to these pre-existing clustering algorithms, it is not possible to cluster the data-points in real-time. Hence, a real world problem exists if there is necessity of grouping data-points which are incoming to a system, in real-time. Besides, algorithm like k-means needs to specify number of clusters to which the data-points are to be grouped into and also cannot identify clusters with arbitrary shape.
Hence, taking all these limitations into consideration, this paper proposes a different kind of machine learning algorithm that can group incoming data-points without need of specifying number of clusters to be formed. The main agenda behind proposing this algorithm is to facilitate those problems which require clustering of data-points based on some level-of-similarity, and most importantly in real-time. Without having to specify the number of clusters to be formed, the algorithm is capable of: • grouping of incoming data-points in realtime, • dealing with n number of features (high set of dimensionality), • generating clusters based on a level-of-similarity (a similarity measure), • identifying clusters with arbitrary shape.
There have been few approaches to generation of clusters of data in real-time. D-Stream (Chen and Tu, 2007) used a density-based approach to generate and adjust clusters in realtime. (Aggarwal et al., 2003a) divided the whole clustering process into two components: online and offline. Online component periodically stored detailed summary statistics and offline component facilitated an analyst to use variety of inputs including time horizon and number of clusters to be formed. CluStream (Aggarwal et al., 2003b) did clustering of large evolving data streams by viewing the stream of data as a changing process over time. Work by (Guha et al., 2000) maintained clustering of a sequence of data-points observed at a period of time.
The main focus of our work is to let an analyst to decide the level-of-similarity according as required, and leave the rest to the algorithm. The rest part of the paper is as follows. Section 2 describes all about the proposed algorithm -its core logic and blocks. Implementation of algorithm is done in section 3 and finally the work is concluded in Section 4 along with future directions.

The Proposed Algorithm
This algorithm requires initial declaration of cluster strictness. Cluster Strictness is the lowest permitted level of similarity between a data-point and the centroid of a cluster. Here, cluster centroid is the average of features of the data-points present in a cluster, and is an effective way of representing that particular cluster. If cluster strictness is set to a measure of 60; then the variability between a cluster centroid (C) and a data-point (D) is a measure of 40 at-most, if D is to be associated to cluster C.
Hence, this algorithm is capable of generating clusters based on a level-of-similarity. If one needs clusters with very low variance among the data-points, the cluster strictness can be adjusted accordingly; may be around 80-95%. That is why, cluster strictness plays a significance role in generating clusters and its value depends completely on what application the clustering is being done.

Data-point & Features
A data-point can have multiple features (n-features). Those features are the characteristics which collectively define a data-point. A stream of data-points can be grouped into various clusters, based on their features. Below is an example of a data-point with 7 features.
A data-point: 5 10 15 20 25 30 35 During implementation of the proposed algorithm, this pattern is used to represent a data-point and similarity measure between the data-points and cluster(s) is calculated accordingly. The algorithm takes data-points with n-features, one data-point at a time, and requires all the data-points to have same fixed number of features.
When the algorithm runs for the very first time, and is waiting for a new data-point; till this moment number of clusters is 0. Cluster strictness needs to be defined beforehand. Based on requirements, this value can be adjusted. Higher the value of cluster strictness, less is the variance between the data-points in a cluster. Depending on the data-points, using higher value of cluster strictness may result into more number of clusters. This is more likely to happen, if the incoming data-points are less identical with each other.
After assigning some value to cluster strictness, say 70%, the number of features that should be matched between a data-point and a cluster is calculated using the formula, should match f eatures = no of f eatures * cluster strictness 100 (1) Suppose, if the data-points that are to be clustered have 20 features. That means, cluster strictness with 70% results into 14 features that must be matched (at least) for a data-point to be associated to a particular cluster.

Shape & Size of Clusters
It is not possible to illustrate data-points with n-features (where n>2) in a 2D plane. For better understanding of size and shape of the clusters formed by the proposed algorithm, let us consider incoming data-points of only one feature. The centroid with small value has less coverage area than a centroid with larger value. Suppose, there are two clusters with centroid 10 and 100. With similarity measure set to 60, the cluster with centroid 10 accepts a new data-point with its feature between the range 6-14; while the cluster with centroid 100 assigns a new data-point with its feature lying between 60-140. This depicts the fact that cluster size varies based on value of its centroid.
Whenever a new data-point arrives, it's similarity is checked with centroid of all the clusters. Since, the algorithm is centroid-based, with addition of a new data-point in a cluster, shifts the value of its centroid. The centroid of a cluster shifts to a particular direction, where the density of data-points is more concentrated. Hence, the algorithm is able to identify arbitrary shaped clusters as well.

Qualifying Feature
A feature qualifies to be counted as matched feature, when its similarity measure lies between the range: (cluster strictness) and (100 + ( 100 -cluster strictness)). That is, the valid range is 70-130, when cluster strictness is considered 70. Suppose, when variability check of 5 and 13 is to be done with respect to 9, a basic mathematics can be used. 9 with respect to 9 gives a similarity measure of 100. 5 with respect to 9 gives a similarity measure of 55.56. And, 13 with respect to 9 gives a similarity measure of 144.44. If allowed variability is considered to be a measure of 50 then similarity measure of both 5 and 12 fall under the range 50-150, and are considered to be associated to 9 by at-least a measure of 50.
In case of data-points, following formula is used to calculate the similarity measure.
where i is an index for clusters, and j is an index for features.
As an example, in formula 2, i=3 and j=7 reflect the fact that cluster 3 is being considered, and 7th feature of a data-point & 7th feature of the centroid of cluster 3 are being used to compute the level of similarity between them. If the resulted similarity measure lies between the range (cluster strictness) and (100 + ( 100 -cluster strictness)) then 7th feature is said to be matched, and the value of matched feature counter for the cluster 3 is incremented by 1. This process of calculating similarity feature of an incoming data-point is done with all the cluster(s). And if the matched feature counter for a cluster reaches the limit of minimum number of features that should be matched between a data-point and a cluster, that particular cluster is now placed into a list of qualified cluster.

Qualified Cluster List
This list contains the cluster(s) that satisfy the condition of having at least a minimum number of features that have matched with an incoming data-point. After calculation of similarity measure for a data-point with all the cluster(s), there might arise any one of the following three situations.

Qualified cluster list is empty
Qualified list being empty indicates that no similar cluster(s) were found within the provided level of similarity. Hence, a new cluster is generated and the data-point is assigned to the newly formed cluster. The data-point is the centroid of this cluster.

Qualified cluster list contains exactly 1 cluster
In this case, the data-point is simply assigned to the cluster which is present in the list. And, the centroid of the cluster is re-calculated.

Qualified cluster list contains more than 1 cluster
Case 1: If the list contains more than 1 cluster, the cluster with maximum matched features is identified. The data-point is now assigned to the identified cluster. Case 2: Sometimes two or more cluster might come-up with the same highest number of matched features. In this case, the cluster with maximum average of qualifying similarity measures is identified, and the data-point is assigned to that cluster accordingly.

Conflicting Clusters
Whenever multiple clusters show up in qualified cluster list, while trying to identify the nearest similar cluster based on the highest number of matched features, those clusters are said to be the conflicting ones. In such case, an average of qualifying similarity measures is calculated for all the clusters which are in the qualified list and have same number of matched feature, and finally the cluster with the maximum average is considered to be the cluster to which the data-point is associated.
While calculating an average, only the qualifying similarity measures are being considered. One fact is also being taken into consideration that technically 60 and 140 are same with respect to 100. Both have variability measure of 40. Hence, if a similarity measure lies within the valid range, but is greater than 100 then the similarity measure is brought to the left side of the number system with reference to 100, using formula 3.

Implementation of the Algorithm
For best illustration of the implementation of the proposed algorithm, let us consider following 10 data-points, each of 10 features, which are to be clustered in real-time. The data-points are input to the algorithm in serial fashion. Let us suppose, level-of-similarity for a cluster is considered to be 60. That means variability measure of 40 between a data-point and a cluster centroid is acceptable. With cluster strictness set to 60, using formula 1 we get minimum number features that must be matched to be 6. Number of qualified features came out to be 4 which is less than 6. C1 cannot be added to list of qualified cluster. Since, there are no any clusters in the list of qualified cluster, a new cluster C2 is generated and Data-point 2 is assigned to C2. Number of qualified features came out to be 9 which is greater than 6. C1 is added to list of qualified cluster. Number of qualified features came out to be 5 which is less than 6. C2 cannot be added to list of qualified cluster. Since, C1 is only the cluster in the list of qualified cluster, Data-point 3 is assigned to C1. Number of qualified features came out to be 5 which is less than 6. C1 cannot be added to list of qualified cluster. Number of qualified features came out to be 5 which is less than 6. C2 cannot be added to list of qualified cluster. Since, there are no any clusters in the list of qualified cluster, a new cluster C3 is generated and Data-point 4 is assigned to C3. Number of qualified features came out to be 8 which is greater than 6. C1 is added to list of qualified cluster. Number of qualified features came out to be 5 which is less than 6. C2 cannot be added to list of qualified cluster. Number of qualified features came out to be 8 which is greater than 6. C3 is added to list of qualified cluster. Since, C1 and C3 are in the list of qualified cluster and both the clusters have same number of qualified features. Now, average of the qualifying features is calculated for both the clusters. Qualifying features beyond 100 are brought to below 100 using the conversion formula: Number of qualified features came out to be 9 which is greater than 6. C2 is added to list of qualified cluster. Number of qualified features came out to be 5 which is less than 6. C3 cannot be added to list of qualified cluster. Since, C2 is only the cluster in the list of qualified cluster, Data-point 6 is assigned to C2. Number of qualified features came out to be 4 which is less than 6. C2 cannot be added to list of qualified cluster. Number of qualified features came out to be 7 which is greater than 6. C3 is added to list of qualified cluster. Since, C1 and C3 are in the list of qualified cluster and both the clusters have same number of qualified features. Now, average of the qualifying features is calculated for both the clusters.

Conclusion
We presented the theoretical aspect of the proposed algorithm and implemented it on 10 data-points (all of them with 10-features) with supposition that they are input to the algorithm one after another, just like a stream-of-data in serial fashion. We also discussed how formation of clusters can be manipulated just by increasing/decreasing the level-ofsimilarity. The algorithm is applicable in real-world scenario where the task is to group a stream of data-points, incoming to a system, based on their similarity with the average of features (centroid) of data-points existing in their respective previously formed clusters. If none of the existing clusters satisfy the similarity measure, new clusters are formed and data-points are assigned to appropriate clusters accordingly.

Future Directions
In our literature review, we did not find any real-time algorithm which resembles to the working theme of application of this algorithm. It would definitely be meaning-less to test the performance of this algorithm with existing real-time clustering algorithms which collect data for a quantum of time and perform clustering analysis on the collected data. Hence, calculation of performance of this algorithm with relative to another clustering algorithm that groups data-points one at a time, would be the main future direction to work on.
When number of clusters in the space is relatively large, the complexity of algorithm also increases proportionately. Hence, it would be an interesting problem to try decreasing the number of similarity checks that is done when a new data-points arrives. Instead of checking the similarity of data-points with all the pre-existing clusters, an approach can be made so that only a certain number of clusters are taken into consideration for similarity check. This way the number of required computations can be decreased relatively.
(i) (j) Figure 2: Step-by-Step graphical representation of how incoming data-points were clustered