{'fraction_non_alphanumeric': 0.03434849116951745, 'fraction_numerical': 0.010707829230983174, 'mean_word_length': 4.425248333962027, 'pattern_counts': {'":': 0, '<': 7, '<?xml version=': 0, '>': 10, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 6, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A New Parallel Adaptive Clustering and its Application to Streaming Data

This paper presents a parallel adaptive clustering (PAC) algorithm to automatically classify data while simultaneously choosing a suitable number of classes. Clustering is an important tool for data analysis and understanding in a broad set of areas including data reduction, pattern analysis, and classification. However, the requirement to specify the number of clusters in advance and the computational burden associated with clustering large sets of data persist as challenges in clustering. We propose a new parallel adaptive clustering (PAC) algorithm that addresses these challenges by adaptively computing the number of clusters and leveraging the power of parallel computing. The algorithm clusters disjoint subsets of the data on parallel computation threads. We develop regularized set \mi{k}-means to efficiently cluster the results from the parallel threads. A refinement step further improves the clusters. The PAC algorithm offers the capability to adaptively cluster data sets which change over time by reusing the information from previous time steps to decrease computation. We provide theoretical analysis and numerical experiments to characterize the performance of the method, validate its properties, and demonstrate the computational efficiency of the method.


Introduction
Automatic classification is a task arising in various data processing applications [7]. As data sets increase in size and complexity, applications demand higher degrees of efficiency and autonomy from data processing algorithms. Clustering methods separate data into classes that exemplify and expose distinctive characteristics and trends within the data. One strength of clustering approaches is that they discover and exploit latent relationships within the data, rather than relying on predefined class descriptors.
Clustering methods are roughly divided into three types: centroid-based, density-based, and distribution-based methods. Centroid-based methods partition the data space into a set of k clusters based on the distance between each datum and its associated cluster descriptor (e.g., centroids). The k-means method [19] is a classic example of this class, as well as the closely-related k-medians [12] and k-medoids [15] methods. There are also fuzzy variants of these methods [12] in which each datum belongs to multiple clusters with varying degree. Density-based methods, such as the popular DBSCAN algorithm [6], partition data into clusters based on the data density. In this approach, two data belong to the same cluster when they are connected by a densely-populated region in data space. One feature of this method is that it finds cluster edges, enabling it to automatically compute the number of clusters and identify clusters of arbitrary shape. However, density-based approaches can struggle to partition data sets with irregular variance. Distributionbased methods, such as mixture models, model each cluster as a statistical distribution [3,8]. Each cluster can be represented as a continuous distribution function, which is advantageous for applications when it is necessary to synthesize new data samples.
The task of finding the global optimizer of the k-means problem is N P -hard in general. A number of methods have been developed to efficiently compute nearly-optimal partitions [11,18,25] and to choose the initial cluster centroids judiciously [22]. Choosing a good set of initial cluster centroids can improve convergence and provide a solution that is closer to being globally optimal. The k-means++ algorithm uses a probabilistic approach to choose initial centroids that are diverse but representative of the data set [2]. Initializing in this manner decreases the likelihood of either assigning many centroids to a single high-density area, or of assigning many centroids to outliers. More recently, yinyang k-means introduced a progressive series of filters to further improve efficiency by eliminating unnecessary computations [4].
Many improvements in clustering techniques have been realized, but a persistent challenge for most centroid-based clustering methods is that the number of clusters, k, must be chosen a priori. In many applications, the correct number of clusters is not known in advance. One strategy to overcome this challenge is to repeat the clustering for many choices of k, and then identify the best k using a cluster quality metric such as the silhouette score [23] or Dunn's index [5]. The regularized k-means algorithm, introduced in [13], presents a method for addressing this issue by computing both the number of classes and the class descriptors.
As multi-core computing architectures have become common, parallel algorithms to cluster large sets of data have received a great deal of attention. Hierarchical and density-based clustering approaches can benefit from growing individual clusters or subsets of the hierarchy tree in parallel [1,20,21]. In the k-means setting, parallel algorithms distribute the work of computing the distances between each data and the cluster centroids (for example, [14,16,26]). This strategy has been implemented in numerous ways to take advantage of specific parallel architectures such as GPU computing [17], message-passing systems [27], and the map-reduce framework [29]. These methods demonstrate impressive performance, but rely on the number of clusters being known in advance. Methods for analyzing data streams have been developed for both the sequential (e.g., [10,28]) and parallel [9] paradigms, but questions persist regarding whether and how the number of clusters should change as new data arrives.
In this paper we present a parallel adaptive clustering (PAC) algorithm that uses parallel computation to improve performance while applying the contribution of the regularized k-means to automatically choose the number of clusters. This new algorithm first forms a large set of small clusters over subsets of the data using shared memory parallelism which scales very well when the number of data is much larger than the number of processors. An efficient algorithm is derived to reduce the parallel result into a small set of clusters over the full data set. The contributions of this paper are • a new efficient parallel adaptive clustering (PAC) method, • exploration of the analytical properties of the proposed algorithm, • a new algorithm for clustering data streams.
The paper begins with a review of the regularized k-means method and a new improvement to the Distribution Statement A: Approved for Public Release, Distribution is Unlimited. algorithm in Section 2. Section 3 introduces the new PAC algorithm and Section 4 presents mathematical analysis of the algorithm. Numerical experiments validate the algorithm and highlight its characteristics in Section 5. Section 6 presents the new algorithm for clustering data that arrives over time, and demonstrates the ability of the algorithm to flexibly adjust the partition as new data arrives, using far fewer computations than the naive approach. The discussion of parallel adaptive clustering is concluded in Section 7.

Review of Regularized k-means
One of the principal centroid-based approaches that adaptively computes the number of clusters is regularized k-means [13]. The regularized k-means method simultaneously computes both the number of clusters, k, and the set of clusters, , by minimizing the global regularized k-means energy function, where x ∈ X ⊂ R d are the data to be clustered,ḡ i ∈ R d is the centroid of cluster G i , and |G i | is the number of data in cluster G i . The regularization parameter, λ > 0, is chosen to balance cluster size and cluster variance. The set of clusters, G, is a partition of X: The regularized k-means algorithm initially assigns all data to a single cluster, k = 1 where G 1 = X, and takes a greedy approach to minimize the regularized k-means energy function. During a single iteration, each datum is individually examined to determine whether the global energy can be reduced by reassigning the datum to a different cluster while holding all else constant. The change in global energy resulting from moving datum, x, currently assigned cluster G i , to a different cluster, G j , can easily be expressed as ∆E RKM ( x, G i , G j , λ) and computed directly from the energy Equation (1). If ∆E RKM ( x, G i , G J , λ) < 0, then x will be reassigned to cluster G j , where If j = k + 1, a new cluster is created. The regularized k-means method is presented in Algorithm 1.
The main benefit of the regularized k-means algorithm is that it does not require the number of clusters to be specified a priori, which is advantageous when the best choice of k is unknown prior to clustering. This approach requires the selection of the regularization parameter, λ, to balance the terms in the global energy. It was shown in [24] and [13] that the clustering result is not sensitive to the value of λ, as λ may vary over a large interval without causing the number of clusters to change. Furthermore, it was demonstrated that when the number of clusters produced by both methods is the same, the regularized k-means algorithm can produce clusters identical to those obtained by classical k-means.
The algorithm presented in [13] lacks a way to remove existing clusters although this is sometimes necessary to reduce the total energy. We present a modified regularized k-means algorithm to address this situation by pausing after each iteration through the data set to identify existing clusters that should be merged. Merging two clusters, G i and G j , produces a change in the global Distribution Statement A: Approved for Public Release, Distribution is Unlimited.
Algorithm 1: Regularized k-means algorithm (with modification in lines [11][12][13][14] Input: X; λ; ITER MAX ; TOL 1 initialize: set k ← 1; assign all x ∈ X to G 1 2 repeat Create G k+1 by assigning x to G k+1 ; 10 Updateḡ i ; setḡ k+1 = x; Set k ← k + 1; Merge G i and G j , and set k ← k − 1; The clusters G i and G j should be merged when this quantity is negative. This condition is computationally efficient to evaluate and provides a way to remove spurious clusters caused by sensitivity to data order. This new modification is included in Algorithm 1 (lines 11-13).

The PAC Approach
To adaptively cluster a given data set, the PAC algorithm partitions subsets of the data, X p , into sets of clusters, C p , p = 1 . . . n, using parallel computation to decrease computation time.
Then, these clusters are efficiently collected into groups, G = {G}, using a regularized set k-means approach. Finally, a refinement step resolves misclassified points. The adaptive capability of the parallel step can reduce the number of misclassified points in the refinement step. Algorithm 2 outlines the complete parallel adaptive clustering algorithm.

Parallel Clustering
The first step of the parallel algorithm distributes the data to parallel threads. The data set is randomly partitioned into n disjoint subsets, X = n p=1 X p , and in parallel each X p is partitioned Distribution Statement A: Approved for Public Release, Distribution is Unlimited.

Algorithm 2: Parallel Adaptive Clustering
Input: X; n; λ c ; λ g ; ITER MAX ; TOL 1 Partition X into n subsets, X 1 . . . X n ; 2 foreach p = 1 . . . n, in parallel, do 3 Use regularized k-means (Algorithm 1) to partition X p into a set of clusters, C p . 4 Collect clusters from all parallel threads, C = n p=1 C p ; 5 Use regularized set k-means (Algorithm 1 with Equation (5)) to partition C into global clusters, G; 6 Refine the clusters G = {G} to obtain the final cluster configuration (Algorithm 3); Output: Set of clusters, G into a set of clusters, C p , by minimizing the regularized k-means energy on each thread, which is Equation (1) for the individual thread, where C p,j ∈ C p is the j th cluster in the partition of X p . In this work, the regularization parameter, λ c , is chosen to be the same for all threads to avoid bias, but it is possible to vary the regularization parameter for each thread.

Grouping
Once the clusters from the parallel threads have been accumulated, groups are formed by minimizing the regularized set k-means energy, Here, C is the set of all clusters from the parallel threads: C = {C i,j } ∀i,j where C p = {C i,j } i=p , and λ g is the regularization parameter for the grouping step. The groups being formed are G i ⊆ C, and |G i | = C∈G i |C|. The energy Equation (5) is minimized using Algorithm 1, where Equation (5) is substituted for Equation (1). This minimization must be done on a single thread, but it is computationally efficient because it does not require the examination of individual data points. Reassigning C from G i to another existing cluster G j , j ∈ 1 . . . k, j = i results in a change to the global energy equal to Distribution Statement A: Approved for Public Release, Distribution is Unlimited. Obtain γ i,j by Equation (8); Update current best cluster for x; 12 Reassign each x to the best cluster identified for it; 13 Update centroid locations; 14 Compute total energy according to Equation (1); 15 until Energy change is less than TOL or number of iterations exceeds ITER MAX ; Output: Refined clusters The change in global energy produced by moving C to be a new cluster, G k+1 , is equal to

Refinement
Since the grouping step does not alter the contents of the cluster from the parallel threads, a refinement is necessary to correct poorly classified points. If λ c and λ g are chosen appropriately, then the number of misclassified points will be small. The refinement procedure searches for points in each cluster for which reassignment to a different cluster would reduce the global energy (all else remaining constant). All points identified for relocation are moved simultaneously and cluster centroids are updated accordingly. Empty clusters are removed at the end of each iteration.
To improve efficiency, we reuse information computed during the parallel step to identify points which should not be reassigned. The minimum distance from a point, x, to its assigned centroid, g i , which is necessary for reassigning x to reduce the global energy is γ i,j such that where λ r is the value of the regularization parameter used in the refinement step. Section 4 provides Distribution Statement A: Approved for Public Release, Distribution is Unlimited.
additional details on the selection of the regularization parameters λ c , λ g , and λ r . A two-stage filter inspired by [4] efficiently eliminates points as candidates for reassignment (Algorithm 3). The first filter attempts to eliminate entire subsets of data as candidates for reassignment, while avoiding examining individual points within the subsets. For subsets which cannot be ruled out entirely, the second filter seeks to identify individual points which are not candidates for reassignment. The first filter requires fewer computations per datum than the second filter, while both have a reduced computational burden compared to fully computing ∆E for each data point. The value γ i,j is computed at the beginning of each refinement iteration, and the value ρ = max x∈C c − x is computed in the initial parallel clustering. Section 4.4 provides more detail on γ i,j and the filtering process.

Analysis of the PAC Algorithm
Mathematical analysis informs the implementation of the PAC algorithm and the characteristics of its results. First, examination of the energy equations provides insight into judicious selection of the regularization parameters. A study of the regularized set k-means quantifies a strong relationship with the original regularized k-means method and allows us to localize the clusters prior to the refinement step. The refinement procedure is studied to improve computational efficiency.

Selection of the Regularization Parameter
From the mathematical form of the regularized k-means energy function, the effect of the regularization parameter on the clusters produced by the method can be characterized. The regularization parameter imposes an upper bound on the total variance permitted within each cluster.

Lemma 1. Let C be a set of clusters which is a minimizer of the regularized k-means energy Equation (4) on a particular parallel thread. Then max
Proof. Let C ∈ C be a non-empty cluster, |C| > 0. Since C is a minimizer of Equation (4), the marginal energy Equation (7) must be non-negative, implying that The maximum distance between any point in a cluster and the cluster centroid is bounded by the regularization parameter. This result gives a bound on the variance of each cluster.

Corollary 1. Let C be a set of clusters which is a minimizer of the regularized k-means energy Equation (4). Then var(C)
Proof. Using Equation (9) we decompose the variance of C, which complete the proof.
Distribution Statement A: Approved for Public Release, Distribution is Unlimited.
Lemma 1 and Corollary 1 show that the regularization parameter governs the cluster width and bounds the variance of clusters produced by the regularized k-means. When regularized set k-means is used to partition a set of clusters, C = {C}, analogous properties can be shown.

Lemma 2. Let G be a set of clusters which is a minimizer of the regularized set k-means energy function Equation (5). Then
Proof. Let each G ∈ G be a cluster which is partitioned into a set of non-empty clusters C ∈ G, |C| > 0. Because G is a minimizer of Equation (5), the marginal energy function Equation (7) must be non-negative for G. Noting that |G| ≥ |C| ≥ 1, this implies that for all C ⊆ G ∈ G, Lemma 3. Let G be a set of clusters which minimizes Equation (5). Then the variance of G ∈ G is bounded, Proof. G is decomposed into disjoint subsets, the clusters {C} C⊆G . The variance of G can then be written, Substituting Equation (12) into Equation (14) completes the proof.
Theorem 1. Let G ∈ G be a global cluster formed by the parallel and grouping steps of the PAC algorithm. Then G has variance satisfying Proof. Lemma 3 gives an upper bound on var(G) which depends on the variance of all C ⊆ G.
In the parallel adaptive algorithm, each C is a cluster formed by the regularized k-means method which by Corollary 1 has variance bounded by λ c . Substituting this result into Lemma 3 completes the proof.
Observe the relationship between Equation (15) and the result of Corollary 1. The variance of a global cluster, G, depends on the variance of each C ∈ G and the variance in the centroids of all C ∈ G, which in turn are bounded by λg |C| 2 and λ c , respectively.
Distribution Statement A: Approved for Public Release, Distribution is Unlimited.

Relation Between Grouping and Global Minimum
The objective function minimized by the grouping step is a generalization of the global energy function, and this relationship gives insight into the selection of regularization parameters. In general a minimizer of Equation (5) is not a minimizer of Equation (1) because var(C) = 0. Theorem 2 shows that G is a minimizer of the regularized k-means energy function Equation (1) subject to the constraint that the contents of each C ∈ C do not change.
Theorem 2. Let var(C) = 0 for all C ∈ C and λ = λ g . Then the grouping energy Equation (5) is equivalent to the global energy, Equation (1). Proof. For λ = λ g , the regularization term in Equation (5) is identical to that in Equation (1) Enforcing var(C) = 0 ∀C ⊆ G i and substituting the result into Equation (1) completes the proof.
In the special case that |C| = 1, Equation (5) is identical to the marginal energy from [13] and is a generalization of regularized k-means clustering for data with arbitrary mass. The computation of marginal energy associated with merging two groups in Equation (3) is still applicable in this setting. The grouping algorithm is very efficient when |C| ≪ |X| because the computation involves only the aggregate mean and size of each C ∈ C.
Deciding whether C should be assigned to G for a particular distance ḡ −c depends on the sizes of C and G as well as on λ g . In general, the clusters C and G contain many elements. The grouping step requires λ g ≫ λ c due to the quantity of elements in each C, as shown in the following theorem.
Theorem 3. Let C 1 , C 2 ∈ C be two non-empty clusters. These two clusters can only be assigned to the same global cluster, Proof. Let C 1 be contained within any G i ∈ G that also contains C 2 . C 1 will be removed from G i to form a new cluster, G k+1 , unless there exists some G j with 1 ≤ j ≤ k such that From Equation (6) and Equation (7), this condition can be written, and C 1 will be moved into G k+1 unless Equation (17) is satisfied for some G ∈ {G j } k j=1 .
As |G| and |C| increase, the impact of the regularization parameter on the resulting clusters decreases. Because the clusters in C are smaller overall, the 1 |C| 2 term in Equation (17) will have the largest influence on the significance of λ g . In order to retain balance between the terms in the energy equation, λ g must be increased quadratically as |C| increases.

Stability of k after Grouping
If the parameters are appropriately chosen then the parallel step and the grouping step should produce a set of clusters which are nearly optimal in terms of the global energy. The number of points which must be reassigned to obtain an optimal solution should be small, which is necessary for efficiency since the refinement treats each candidate point individually. For simplicity in parameter selection, we choose λ r = λ g . Recalling from Section 4.2 that we require λ g > λ c > 0, we introduce the parameter ω ∈ (0, 1) such that λ c = ωλ g . Judicious selection of λ g can guarantee that new clusters should not be formed during the refinement process.
Theorem 4. Let λ c = ωλ g for some 0 < ω < 1. Then for any x ∈ C ⊆ G ∈ G, moving x to start a new cluster will cause an increase in the global energy if Proof. In order for x ∈ G to form a new cluster it must be true that |C| ≥ 1 and |G| ≥ max {|C| , 2}, therefore, The triangle inequality guarantees that for any x ∈ C ⊆ G, Using the bounds from Lemma 1, Lemma 2 and substituting the relationship λ c = ωλ g , From Equation (7), it is known that reassigning x ∈ G to form a new cluster will increase the energy if This condition must be true if and rearranging this inequality gives the result Equation (20).
Choosing λ g sufficiently large relative to λ c prevents new clusters from forming during refinement. If the clusters from the parallel threads are large, then λ g may be chosen close to λ c and still provide this guarantee, as illustrated in Figure 1. In typical cases (|C| ≫ 1), a λ g which is  Figure 1: The quantity λ g ≥ λc ωmax is a function of |C|. Larger |C| increase the stability of k after the grouping step, as ω max asymptotically approaches 1.

Refinement Efficiency and γ i,j
If the parameters for the initial clustering and grouping steps are suitably chosen, then only a small portion of the data is reassigned during the refinement. The algorithm must determine whether each point should be reassigned. To increase efficiency, we develop a two-tiered filtering process to quickly identify many points which should not be reassigned. Theorem 5 describes how the distances between centroids can be used to quickly find points which should not be reassigned.
Theorem 5. Let G i , G j , i = j, be clusters for which there exists a value γ i,j > 0 satisfying Equation (8). If ḡ i − x ≤ γ i,j for a datum x ∈ G, then moving x ∈ G i to G j will not decrease the total energy.
Proof. The triangle inequality guarantees that for any x ∈ G i , Substituting Equation (26) into Equation (6), where C = x, Equation (27) gives a lower bound on the change in energy created by moving x from G i to G j . Replacing ḡ i − x with γ i.j we obtain the left-hand side expression of Equation (8), which is monotone decreasing for γ i,j > 0. Therefore, there exists at most one γ i,j > 0 for which Equation (8) is satisfied. If this γ i,j exists, then it is guaranteed that ∆E RKM ( x, G i , G j , λ g ) ≥ 0 for any x ∈ G i satisfying ḡ i − x < γ i,j , and this x will not be moved from G i to G j .
If there exists γ i,j > 0 which satisfies Equation (8) and ρ ≤ γ i,j − ḡ i −c , then moving any x ∈ C from G i to G j will not decrease the total energy.
Proof. This property follows directly from the definition of ρ, the derivation of γ i,j , and the triangle inequality: Corollary 2 gives a method for identifying entire clusters of points which should not be reassigned. This forms the first layer of the refinement filter, and Theorem 5 provides the second. A filter using Lemma 1 and Lemma 2 to identify any group, G j , which is far enough from G i that no data should be reassigned from G i to G j could be implemented, but in the experiments shown here this would not add considerable savings over the filter based on Corollary 2.

Numerical Experiments
This section demonstrates the properties of the PAC method through various numerical experiments. In these experiments, the parameter value is set to be λ r = λ g , which is sufficient to guarantee that the number of clusters will not increase during the refinement (Theorem 4). Due to the consequence of Theorem 3, λ g is chosen based on the sizes of the clusters, where it is necessary to specify the constant, ǫ, rather than to select λ g directly.  The data set represented by the 2-d histogram in Figure 2(a) is a mixture of data drawn from four distinct Gaussian distributions. The means of three of those distributions lie in close proximity to one another and the tails of these distributions overlap. This data may appear to be optimally clustered by either k = 2 or k = 4. We apply the PAC algorithm with λ c = ǫ = 0.05 1. In the parallel step, the data is randomly partitioned into 16 subsets of equal size, which are clustered on parallel computation threads using regularized k-means (Algorithm 1), producing the clusters in Figure 2(b).

Illustration of PAC Algorithm
2. The grouping step aggregates the clusters from all parallel threads, organizing them into groups and producing the four clusters shown in Figure 2(c). These clusters are disjoint subsets of the data set, but they are overlapping in the 2-D data space.
3. The refinement step reassigns points near the cluster boundaries (Figure 2(d)). The refinement procedure affects the cluster boundaries to a large extent while not changing the cluster centroids as significantly. This shows the efficiency of the refinement procedure, as only a small portion of each cluster's points are reassigned.

The Influence of λ c
The value of λ c affects the number of clusters produced by each thread during the parallel step, which in turn affects the subsequent steps. Changing the values of the regularization parameters affects the efficiency of the algorithm even though the final cluster configuration may be identical.
As an example, consider a set of data lying on three concentric rings in the Cartesian plane (Figure 3). There are many choices of λ c and ǫ for which the parallel adaptive clustering algorithm produces the three cluster solution in Figure 4(d). Due to the random assignment of data to each parallel thread, the distribution of data for each thread tends to follow the distribution of the full data set. In Figure 4(b), the choice of λ c = 2 results in a clustering where the number of clusters (and cluster centroids) computed by each thread is the same as or slightly larger than the number of clusters in the final configuration. In contrast, Figure 4(a) represents an "over-segmentation," where each thread produces many more clusters than will appear in the final configuration (in this case, λ c = 1). Conversely, "under-segmentation"  Figure 4: Results of using PAC to cluster (in the (r, θ) plane) data which lies in three concentric rings in the Cartesian plane. In the parallel step 4(a), λ c = 2 produces approximately three clusters per thread, while λ c = 1 produces far more clusters 4(b) and λ c = 24 produces fewer 4(c). In all three cases, it is possible to choose a value λ g such that the final output of the algorithm is the three-cluster solution, 4(d). Table 1 compares the computational time to produce the three-cluster solution for each choice of λ c . can occur when λ c is large (here, λ c = 24) and the parallel threads produce fewer clusters than will be represented in the final partition. (Figure 4(c)). For any of these values of λ c , one can choose λ g such that the final cluster configuration after refinement is identical to Figure 4(d). The choice of λ c , however, affects the computational burden of finding that solution. Table 1 lists some choices of λ g which produce the 3-cluster solution, as well as the associated computational time. When the parallel threads over-segment the data, the 3-cluster solution can be achieved but requires more computation in the grouping step, to combine many small clusters into groups. However, when the parallel threads under-segment the data, achieving the 3-cluster solution requires much more computation in the refinement step, to reassign a larger number of individual data points. For λ c = 1 and λ c = 2 the refinement step converges in a single iteration while requiring several iterations for λ c = 24. This is investigated further in Section 5.3.
One of the advantages of using regularized k-means to perform the initial parallel clustering is that individual threads are not constrained by a predetermined number of clusters. This is important for efficiency because it permits the number of clusters in each C p to be optimized for X p which helps to prevent over-and under-segmentation. The risk of either under-segmenting or over-segmenting the data is higher if a non-adaptive method (i.e., classical k-means) is used on each parallel thread.

Convergence of the Refinement Step
To study the convergence properties of the refinement iteration, consider the clustering of the data set in Figure 2. For the parameter choices λ c = 0.05, 0.1, 0.5, Figure 5 shows the computed global energy and the percentage of data being reassigned at each iteration. For each value of λ c , λ g is chosen so that the final partition is the four-cluster solution in Figure 2(d). Because the value of λ g changes between experiments, the absolute energy values in the different experiments cannot be directly compared; however, Figure 5(a) demonstrates that larger values of λ c tend to result in more points which must be reassigned during the refinement. The refinement procedure may not converge monotonically, particularly for large values of λ c . When data are merged more aggressively during the initial clustering, the number of misclassified points remaining after the grouping step increases and the refinement step will require more iterations for convergence. In this experiment, the refinement converges in five iterations for λ c = 0.05, six iterations for λ c = 0.1, and ten iterations for λ c = 0.5.
In clustering the data in Figure 3 the computational cost of the refinement step is considerably higher for λ c = 24 than for the other cases. While the computational time of the refinement step    Figure 7: Convergence of the refinement step in clustering the data set from Figure 3 using λ c = 24. The percentage of the data set being reassigned (a) and the global energy evaluation relative to the energy prior to refinement (b) are computed for each refinement iteration.
increases as the number of clusters increases, it also depends on the stability of the clusters. With λ c = 24, the parallel initial clustering does not separate the data well and a great deal of work must be performed during the refinement step in order to obtain the k = 3 solution. Figures 6  and 7 show the evolution of the cluster configuration for λ c = 24 throughout the refinement step. Prior to refinement (Figure 6(a)) the energy is high (iteration 0 in Figure 7(b)), but the first refinement iteration reduces the energy substantially while reassigning nearly 65% of the data points and eliminating one cluster. After the large change in cluster centroid locations, there are many additional points which could be moved to produce a lower energy. The second iteration eliminates a second cluster, which moves the configuration toward the more-stable k = 3 solution. From this state, the refinement process proceeds smoothly toward the final configuration, terminating after iteration 5. The computational cost is very high for refinement iterations in which a large percentage of the data is reassigned.  The scaling performance of the algorithm is analyzed using a shared-memory computing node with 32 processors. The data set from Figure 2(a) is clustered using 128 threads with parameter values λ c = 0.06, ǫ = 0.01 (λ g = 418932). Figure 8 shows the computational cost of the entire procedure (excluding input and output) as the number of processors is doubled. All of these experiments produce the k = 4 solution depicted in Figure 2(d).

Computational Efficiency
The computational cost of the parallel step scales well with the number of processors (Figure 8(a),8(b)). The computational time for the refinement step scales poorly with the number of processors, quickly becoming constant due to the fact that it exploits only up to k-fold parallelism. While the grouping step does not scale with the number of processors, it occupies an insignificant portion of the total processing time (Figure 8(c)). The total execution time for the algorithm (excluding input and output operations) is dominated by the time required for the initial parallel clustering step when the number of processors is small, but dominated by the time required for the refinement step when the number of processors is large.
In Figure 9, the number of processors is fixed at 16 and the data from Figure 2 is clustered many times with different parameter choices. In particular, we select λ c from a set of 6 uniformly spaced points in the range [0.05, 0.1] and choose ǫ from a set of 100 uniformly spaced points in the range [0.003, 0.015] for a total of 600 parameter combinations. For each set of parameters clustering is performed 25 times, randomly reordering the data each time. These experiments resulted in partitions with 1 ≤ k ≤ 32, though k < 5 occurred much more frequently than configurations with higher numbers of clusters. Figure 9 demonstrates that the refinement step is the primary driver  of the overall computational cost, and k drives the cost of the refinement step. For each value of k the height of the curve is the time required for the algorithm, averaged over each trial that resulted in k clusters, with vertical whiskers illustrating the standard deviation from the average. The computational cost of the parallel step is generally low across the experiments, with small variance across repeated trials. The computational cost of the grouping step has an insignificant computational cost with negligible variance. However, the refinement step has a computational cost which increases significantly as k increases. The variance is larger for larger values of k due to the small number of experiments resulting in k > 5.

Stability
The initial ordering of the data and the choice of regularization parameters affect the final cluster configuration. We repeat the clustering of the data from Figure 2 while varying the data order and parameter values. Figure 10 shows the value of k for the final cluster sets as a function of λ g , corresponding to λ c = 0.06 and λ c = 0.1. The red lines in the charts indicate the standard The stability of a cluster configuration is assessed by the sensitivity of the solution to the value of the regularization parameter and the initial ordering of the data. A stable solution is one in which the outcome (i.e., the number of clusters, k) changes very little when the input order of the data or the regularization parameter value is changed. Figure 10 illustrates that the two-cluster solution is more stable than the four-cluster solution. This is caused by the large separation between the clusters in the two-cluster solution. Figure 10(b) shows that the regularization parameter may vary over a large interval without changing the cluster configuration.
In Figure 10(a), the regularization parameter is small enough that the large decentralized cluster begins to be subdivided. However, over a number of trials, the number of clusters produced varies as the input order of the data is perturbed. The red bars on the plots in Figure 10(a) and (b) show the variance of the computed value of k during 25 trials with random reordering of the data. The two-cluster solution is quite stable with respect to the data order, while solutions with more than two clusters are more sensitive to the input order of the data.

Application to Time-Dependent Data
We apply the PAC method to a problem where the data set is changing over time. This is important because many current applications rely on data that arrives continuously, and require that the classification model be capable of adapting to new data as it becomes available. In such cases, the optimal number of clusters to partition the data set may change over time; methods which fix the number of clusters to be constant have a serious drawback in this setting. A second challenge is that dynamically updating the partition to integrate new data is cumbersome or impossible. The parallel adaptive clustering algorithm provides a framework that can be naturally extended to clustering data streams, with the capability to dynamically update the cluster configuration to integrate new data and adjust the number of clusters. This is accomplished by utilizing the intermediate cluster configuration when incorporating new data, as described in Algorithm 4.

Algorithm 4: Parallel Adaptive Clustering for Streaming Data
Input: n; λ c ; λ g ; ITER MAX ; TOL Output: cluster configuration 1 initialize: t = 0, X 0 = {∅}, C 0 = {∅} 2 while more data do 3 Retrieve new data,X = n p=1X p ; set t ← t + 1; Use Algorithm 1 to partition each subset of the new data,X p , into a set of clusters, C p , by minimizing (4); 6 Collect clusters from each parallel thread,C = n p=1C p ; Use Algorithm 1 to cluster C t into groups, G, by minimizing (5), ; 9 Compute refined clusters for time t using Algorithm 3;

Time-Dependent PAC Algorithm
To efficiently cluster time-dependent data, the PAC algorithm keeps a record of the output at each time step. At time t, a new set of data,X t , becomes available and the parallel step is performed only on the new data to form a set of clusters,Ĉ t . We allow C t to denote the collection of the results of the parallel clustering for all time steps up to t, so that C t = ∪ t τ =1Ĉ τ . Similarly, we let X t represent the aggregation of all data that has become available by time step t: τ . The global cluster configuration at time t is obtained by performing the grouping and refinement procedures on C t .
When the number of data arriving at each incremental time step is roughly constant, it is appropriate to use a constant λ c for all time steps. λ g can be adjusted at each time step to account for the increasing size of the aggregate data set. As |X| grows |C| increases even though the average size of C ∈ C may not change, causing the regularization term to lose significance compared to the fitting term when λ g is constant. In the time-varying case, λ g is updated to account for both the sizes of the clusters (Theorem 3) and changes in |X|.
The cluster configuration produced by the time-dependent PAC at time t with n parallel threads is equivalent to the result of the PAC algorithm on the aggregate data X t with nt parallel threads. In the following experiments ν = 0.1 is used, but practice we have found that 0 < ν < 1 may be appropriate.

Experiment for Data Stream Clustering
To illustrate the clustering of time-dependent data using the PAC algorithm, we consider a data set containing points drawn at random from four distinct Gaussian distributions with different means but similar variance (Figure 11(a)). We label each of these four Gaussian peaks as follows: subset A is centered near (0.9, 0.1); subset B is centered near (0.1, 0.9); subset C is centered near (0.9, 0.4);   and subset D is centered near (0.5, 0.5). This data set arrives incrementally over a period of 20 time steps, but the distribution of data arriving at each time step changes over time. Figure 11(b) illustrates the amount of data from each subset which has arrived by time t. During the first few iterations, only data from subsets A and B arrive. Then, from t = 6 to t = 10, most of the new data is from subset C, with only a small amount of new data from A and B. From t = 11 until the final time, nearly all of the new data is from subset D. Figure 11(c) shows that the number of clusters adapts to accommodate changes in the underlying data set. The data from subsets A and B are well-separated and the algorithm forms two clusters at first. As data from subset C starts to accumulate, the algorithm adds a cluster. Similarly, a fourth cluster is added when data from subset D arrives. Eventually subsets A and C are small, compared to subsets B and D, and are sufficiently close to be joined into a single cluster. The k = 3 solution persists until the end of the experiment.
The primary benefit of the proposed algorithm for clustering time-dependent data is the ability to dynamically update the number of clusters at each time step. A secondary benefit is computational efficiency. When methods such as k-means are used to cluster the time-dependent data, it is necessary to recompute the classical k-means partition from scratch at each time increment. For k = 2, 3, 4, the computational cost of this approach increases quickly as the data set grows in size. The cost also increases for the PAC algorithm in Figure 13 as the data set grows in size, but more slowly. The cost of the refinement step increases approximately linearly, but more slowly than the cost of classical k-means. In this experiment, λ c is sufficiently small to prevent under-segmentation. The cost of the parallel step is low and roughly constant as the number of data being processed by this step is constant at each time instant. The cost of the grouping step is also very small at

Conclusion
This work presents the parallel adaptive clustering (PAC) algorithm as a new method for centroidbased clustering that dynamically selects the number of clusters and leverages parallel processing to increase efficiency. Mathematical analysis of the algorithm gives clear insight into how the regularization parameters affect cluster properties, the basis of the regularized set k-means, the stability of the pre-refinement cluster configuration, and a computationally efficient implementation of the refinement procedure. The PAC algorithm is computationally efficient for multi-core computing architecture, and is immediately applicable to a wide range of data, including data streams.