{'fraction_non_alphanumeric': 0.04707354006188689, 'fraction_numerical': 0.01125814734347225, 'mean_word_length': 4.234321157822191, 'pattern_counts': {'":': 0, '<': 11, '<?xml version=': 0, '>': 0, '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}}
A New Clustering Algorithm Based on Near Neighbor Influence

This paper presents Clustering based on Near Neighbor Influence (CNNI), a new clustering algorithm which is inspired by the idea of near neighbor and the superposition principle of influence. In order to clearly describe this algorithm, it introduces some important concepts, such as near neighbor point set, near neighbor influence, and similarity measure. By simulated experiments of some artificial data sets and seven real data sets, we observe that this algorithm can often get good clustering quality when making proper value of some parameters. At last, it gives some research expectations to popularize this algorithm.


Introduction
Clustering is an unsupervised learning method which tries to find some distributions and patterns in unlabeled data sets. Usually, those points in the same cluster should have more similarity than other points in other clusters. There have been thousands of clustering algorithms until now, but none of them is all purpose.
Clustering algorithms are usually categorized into partitioning methods, hierarchical methods, density-based methods, grid-based methods, and model-based methods [8,13].
KMeans [11] is a classical partitioning clustering algorithm presented in 1967. It has some inherent shortcomings. For example, this kind of algorithm needs a predefined number of clusters, but this number cannot be obtained correctly before clustering process. KMeans only adapts to find those globular clusters with near radius because of its assignment strategy of point to the nearest cluster. When the number of clusters is large, KMeans is very sensitive to initialization.
Affinity Propagation (AP) [5] is a new type of clustering algorithm published on Science in 2007. It needs a predefined similarity measure and Θ(n 2 ) time and space cost when computing and storing a similarity matrix corresponding to its data set.
Finally, it produces a clustering result but can't give a hierarchical clustering structure in a form of multi-level tree.

This paper presents a new Clustering algorithm based on Near Neighbor
Influence (CNNI), which is inspired by the idea of near neighbor and the superposition principle of influence.
The remainder of this paper is organized as follows. Section 2 lists several related papers. Section 3 gives some basic concepts. Section 4 presents a new clustering algorithm based on near neighbor influence. Section 5 validates the algorithm by some simulated experiments. Conclusions and future works are presented in Section 6.

Related Work
This paper is related in some aspects to several papers [2,6,7,9,12], although it was developed quite independently. Jarvis and Patrick [9] presented a shared nearest neighbor approach to similarity first. A similar idea was later proposed in ROCK [6].
In [9], a shared nearest neighbor graph is constructed from a proximity matrix, in which a link is created between a pair of points X and Y if and only if point X and point Y have each other in their closest k nearest neighbor lists.
L. Ertöz et al. [2] presented an improved J-R clustering method by redefining the similarity between pairs of points in terms of how many nearest neighbors the two points share. This paper is also superficially similar to some density-based clustering methods, such as DBSCAN [3]. DBSCAN needs two parameters, and our CNNI algorithm only needs one parameter that can be determined easily. You will see that they have essential difference in basic idea and concrete implementations.

Some Basic Concepts
Suppose there is a data set S = {X 1 , X 2 , …, X n } in an m-dimensional Euclidean space. Naturally, we can use Euclidean metric as our dissimilarity measure. In order to describe our algorithm clearly, some concepts are presented first. Definition 1. The δ near neighbor point set δ(P) of point P is defined as where d(X,P) is the dissimilarity measure between point X and point P in the data set S. δ is a predefined threshold parameter.

Definition 2.
One kind of similarity measure based on dissimilarity measure is defined as s(X, P) = 1/(1+d(X, P)), (2) where s(X, P) is the similarity measure between point X and point P, and d(X, P) is the dissimilarity measure between point X and point P. When X = P, there are d(X, P) = 0 and s(P, X) = 1. So we can ensure 0 < s(X, P) ≤ 1.
In this paper, we use equation (2) to translate the dissimilarity measure to the similarity measure. In some cases, s(X, P) = exp(-d(X, P)) can also be used as a kind of similarity measure [12]. For some local clustering problems, perhaps s(X, P) = exp(-d(X, P) / δ) is a better similarity measure.
Definition 3. The δ near neighbor influence I δ (P) of point P is defined as where δ(P) is the δ near neighbor point set of point P, and s(X, P) is the similarity measure between point X and point P.
The concept of near neighbor influence is presented based on the superposition principle of influence. It is similar to the influence function [2] and the notion of density [7]. In [2], the sum of the similarities of a point's nearest neighbors is taken as a measure of this density.

Clustering based on Near Neighbor Influence
In order to implement this algorithm, first we should construct the δ near neighbor point sets of the data set S = {X 1 , X 2 , …, X n } basing on one kind of dissimilarity measure. Then sort S with descending sequence basing on the δ near neighbor influence of every point. Finally, basing on an idea of boosting-spread clustering, the sorted data set can be analyzed step by step by disjoint-set structure.
This new clustering method is termed CNNI algorithm.
Output: a cluster label array Label [1..n] of the data set S.

Procedure:
Step1. First construct the δ near neighbor point set δ(X i ) for each point X i (i = 1, 2, …, n) according to Definition 1. Then compute the δ near neighbor influence I δ (X i ) for each point X i (i = 1, 2, …, n) according to Definition 3.
Step2. Sort the data set S = {X 1 , X 2 , …, X n } with descending sequence basing on I δ (X i ) of every point X i (i = 1, 2, …, n). Without loss of generality, suppose there is Step3. Construct a disjoint-set for every point in the data set S. The constructing procedure is listed as below: Make_Set(X i ); /* Make_Set(X) is an operation of the disjoint-set data structure.*/ Step4. Construct a structure DS(X i , δ(X i )) for every point X i (i = 1, 2, …, n). Here, DS(X i , δ(X i )) is composed of a label index of point X i and its corresponding adjacency-list structure used to store δ(X i ). An array with n structures can be expressed as ((X 1 , δ(X 1 )), (X 2 , δ(X 2 )), …, (X n , δ(X n ))).
Step5. Construct and merge those clusters of the data set S. Here, the array element Label[i] is used to record the cluster label of point X i (i = 1, 2, …, n). The constructing and merging procedure is listed in Table 1. Step6. Finally we get a super set {C 1 , …}, which is a set of clusters of the data set S = {X 1 , X 2 , …, X n }. The cluster label of every point in S is recorded by the array Label[i] ← 0; /* Every point is regarded as an isolated point at first. */ 3 i ← 1; 4 j ← 1; /* Tag j records the current number of clusters. Its initial value is set to 1. */ 5 while and (many points of δ(X i ) are not assigned to any cluster C t (0 < t < j), which is constructed before)) /* If Label[i] is equal to 0 and the Label[] value of many points in δ(X i ) is also equal to 0, then the condition of the if() sentence is true. In our experiments, "many" is set to (0.8*|δ(X i )|). */ 9 { 10 C j ← Union(X i , P∈δ(X i )); /* Union(·, ·) is an operation of the disjoint-set data structure. After this operation, the j-th cluster C j stores point X i and δ(X i ). */ 11 Label Point X i joins to one cluster C r (0 < r < j) constructed before, which contains the most points of δ(X i ); /* Here, "most" is not the same as "many" above. It means that C r (0 < r < j) is the cluster that contains the largest number of points of δ(X i ). In this step, we call Find_Set(X), an operation of the disjoint-set data structure, to search the cluster set of point X. */ 19 Label
(3) Although we use the Euclidean metric as our dissimilarity measure in this paper, the algorithm is by no means restricted to this measure and this data space. If we can construct a proper dissimilarity measure in a hybrid-attribute space, then the algorithm can also be used.

Setting parameter δ
Parameter δ will affect the results of clusters. In some cases, when n is very large, we can make |δ(X i )| << n be valid almost for all i (i = 1, 2, …, n) by setting a proper δ.
Intuitively, if the dissimilarity measure of two points is smaller than δ, then the two points should be in the same cluster. Here, we present two methods to estimate parameter δ.
(1) The first method is described by equation (4) for estimating parameter δ.
is the maximal dissimilarity measure of two points that should be in the same cluster, and is the minimal dissimilarity measure of two points that should be in different clusters.
(2) The second method is a concrete algorithm based on a MST of the data set S (or a sample of S). That is: a. First construct a MST from the data set S.
c. Search two near neighbor edges in ES(MST(S)) that have the maximal diversification. Then another equation for estimating parameter δ can be represented as: where e k and e k+1 are two near neighbor edges having maximal diversification in ES(MST(S)).

The Improved Version of CNNI Algorithm (ICNNI)
The main cost of CNNI algorithm is constructing the δ near neighbor point sets of the data set S. If we can design a proper index structure and use some improving techniques, then constructing δ(X i ) (i = 1, 2, …, n) will cost less time with the same result. The improved version of CNNI algorithm by decreasing time complexity of constructing the δ near neighbor point sets of the data set S is named as ICNNI algorithm. The detailed description and discussion on how to make some improvements in constructing the δ near neighbor point sets of the data set S is given in [1].

The Extended Version of CNNI Algorithm (ECNNI)
The Extended version of CNNI algorithm (ECNNI) can be obtained by revising the concrete procedure of Step5 in CNNI Algorithm. Usually, parameter δ in ECNNI algorithm can be set as a smaller value than in CNNI algorithm so that less space and time are need to construct and store the δ near neighbor point set {δ(X 1 ), δ(X 2 ), …, δ(X n )}.  [3]. They are described in Table 3.  0) and (many points of δ(X i ) are not assigned to any cluster C t (0 < t < j), which is constructed before)) 9 A recursion function, PutNearNearborPointsIntoCurrentCluster (the current point P, the current cluster ID j, the data set S, the δ near neighbor point set {δ(X 1 ),  In subsection 5.6, the valid interval of parameter δ between CNNI algorithm and ECNNI algorithm are compared by using some artificial data sets.
Performance and effect of algorithms are measured by time cost (label: ST), number of clusters (label: NC), the average deviation between all points and their means (label: ADM), comparative figures, or clustering purity [14] (label: CP).
In the following experiments, we implement the definition of data structures and three basic operations of the disjoint-set structure basing on some contents in [10]. dimension of grid cell [1], and δ is the threshold parameter in Definition 1.

Note
In Table 4, Table 5, and Figure 1 -2, there are some comparative experimental results. Intercomparing CNNI, ICNNI, and KMeans, we find that ICNNI is faster than CNNI with the same clustering results (the same ADM, NC, and the same clusters displayed by figures). Intercomparing CNNI, ICNNI, and AP, we find that ICNNI is faster than CNNI with the same clustering results, and CNNI and ICNNI are faster than AP with similar clustering quality (displayed by Figure 1

and other figures in
Online Resource 2).

Validate the Compress Result of CNNI Algorithm by Clustering Pixel Points of Two Bmp Pictures in RGB Space
Two bmp pictures are named as Picture1 and Picture2. Figure 5 gives the RGB space distribution of 200 * 200 pixel points in Picutre1. Figure 6. lists the original picture and five compressed pictures of Picture1. The five compressed pictures are drawn using the means of clusters obtained by clustering pixel points of Picutre1 in RGB space using CNNI algorithm. Figure 7 and Figure 8 are similar to Figure 5 and Figure 6 respectively.

Analysis and Conclusions of Experimental Results
From Figure 1 to Figure 4, we find that CNNI, ICNNI, and ECNNI algorithm can find those obvious clusters of some artificial data sets.
From Table 4 and Table 5, ICNNI algorithm is validated in decreasing time cost.
We find that constructing the δ near neighbor point sets is the main part of time cost.
From Figure 4, we find that ECNNI algorithm can get more obvious clusters than DBSCAN algorithm for some artificial data sets. From Table 6, we find that ECNNI algorithm has longer valid interval of parameter δ than parameter Eps of DBSCAN.
DBSCAN algorithm needs two parameters, and ECNNI algorithm only needs one parameter.
From Figure 5 and Figure 7, we find that the clusters of Picture1 and Picture2 are not very obvious. This is the main reason that the experimental results of CNNI algorithm are sensitive to parameter δ.
From Table 8, we find that the valid interval of parameter δ in ECNNI algorithm is mainly less than the valid interval of parameter δ in CNNI algorithm.
CNNI algorithm is a new clustering algorithm with fast clustering speed. It can often get good clustering quality, although it is sensitive to parameter δ for some scatter data sets. ICNNI algorithm is an improved clustering algorithm with faster clustering speed than CNNI. ICNNI algorithm is sensitive to parameters δ and r i (i = 1, 2, …, m). Generally, r i (i = 1, 2, …, m) ≥ δ is a better choice. ECNNI algorithm is an extended clustering algorithm with less valid interval of parameter δ than CNNI and ICNNI, which often results in faster speed in constructing δ near neighbor point sets.

Conclusions
This paper presents a new effective clustering algorithm CNNI, which can often get better clustering results or faster clustering speed for some data sets than some classical clustering algorithms.
CNNI algorithm is robust to outliers and allows to find clusters with different shapes. The number of clusters does not have to be fixed before clustering. Usually, parameter δ has some valid interval that can be determined by using an exploring method. In the process of constructing δ near neighbor point sets, if using an improved constructing method [1], or using the SS-tree [15] (or SR-tree [16]) index structure, the time complexity of this algorithm can even be decreased to O(nlogn), which means it can be suitable to large data sets.
CNNI algorithm is sensitive to parameters δ when many noises and few obvious clusters exist, and it also cannot generate clusters with different levels of scatter because parameter δ is fixed before clustering.
The next work is to further improve this algorithm in time cost or clustering quality and overcome its two drawbacks.