{'fraction_non_alphanumeric': 0.028993010613512813, 'fraction_numerical': 0.00783070152731038, 'mean_word_length': 4.55863309352518, 'pattern_counts': {'":': 0, '<': 0, '<?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': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Distributed Lance-William Clustering Algorithm

One important tool is the optimal clustering of data into useful categories. Dividing similar objects into a smaller number of clusters is of importance in many applications. These include search engines, monitoring of academic performance, biology and wireless networks. We first discuss a number of clustering methods. We present a parallel algorithm for the efficient clustering of objects into groups based on their similarity to each other. The input consists of an n by n distance matrix. This matrix would have a distance ranking for each pair of objects. The smaller the number, the more similar the two objects are to each other. We utilize parallel processors to calculate a hierarchal cluster of these n items based on this matrix. Another advantage of our method is distribution of the large n by n matrix. We have implemented our algorithm and have found it to be scalable both in terms of processing speed and storage.


Introduction
Dividing similar objects into a smaller number of clusters is of importance in many applications. These include search engines, monitoring of academic performance, biology and wireless networks. We first discuss a number of clustering methods. These include the Kmeans clustering algorithm and a number of hierarchal clustering methods. Hierarchal clustering methods have advantages over K-means. Unfortunately, Hierarchal Clustering can be expensive. It is for this reason that hierarchal clustering has been avoided in some applications. One example of such an application is the clustering of candidate protein structures into a limited number of groups (Zheng, Gallicchio, Deng, Andrec, & Levy, 2011). If and when clustering is used it is generally K-means clustering. Hierarchal Clustering, itself, is also divided into sub-methods such as simple hierarchal clustering (SHC) and complete hierarchal clustering (CHC). There are a few other methods of hierarchal clustering. While SHC has faster algorithms, CHC, which is more useful, is O(n 3 ). This can be prohibitive for large n.
We present a parallel algorithm for the efficient clustering of proteins into groups. The input consists of an n by n distance matrix.

2
Choice of clustering method

Clustering Methods
Clustering is the generic term for methods of categorizing objects into groups or clusters.
There are hierarchal and non-hierarchal methods. There are methods that build clusters top-downthat is they begin with all item in one large cluster and break down that cluster over a number of iterations. There are also bottom-up or agglomerative algorithms.
Non-hierarchal or partition methods include K-means, Graph Theoretic and other methods.
The non-hierarchal clustering methods in general pre-sets the number of clusters and then fit the n items into those clusters. The name K-means indicates that there is a pre-set number of K clusters. It is an efficient algorithm but does not have the advantages of hierarchal clustering.
Hierarchal clustering methods, on the other hand, first assign every item to its own cluster. For n items, we start, therefore, with n clusters. The algorithm then iterates and combines two of the clusters into one larger cluster. It iterates n times until there is one large cluster. A snapshot is taken after every iteration of what clusters there were at the end of each iteration. This is preserved in an upside down tree (Dendrogram). If our goal, for example, was to divide the data into 10 clusters, we simply look 10 levels down the treeon that level will be 10 clusters.
Thus, there are numerous advantages of hierarchal clustering. One advantage is that there is no pre-set number of clusters. Another advantage of hierarchal clustering is that it's output is a full tree (also known as a Dendrogram) of clusters. The bottom 'row' of the tree is each of the n items in its own cluster. The second to the bottom row shows n-1 clusters and the top of the tree shows one large cluster. Once finished we can choose any of the output levels of the tree depending on how finely clustered we want it.

Ward's method
We found that Hierarchal bottom-up agglomerative clustering to be useful in many situations but having a cost of O(n 3 ). This makes it too expensive to use in many real world applications.
One exception is Single-Linkage hierarchal clustering which can be solved by an algorithm that mimics the Prim's Minimum Spanning Tree Algorithm.
To get a feel for the various hierarchal clustering methods, let's illustrate single-linkage and complete linkage. Complete-linkage clustering tends to produce 'round' clusters whereas single-linkage clustering tends to produce 'long' clusters. The shapes of the other clustering methods are in between.
As an example let's look at the three clusters depicted in figure 1 Lavrenko (2014) Hierarchal Clustering algorithms, in the next iteration, would combine two of these clusters and arrive at a total of two resulting clusters. The difference between the specific hierarchal clustering algorithms is the rule used to decide which of the two clusters to combine.

Figure 1: Example of 3 clusters
In single linkage we measure the distance between clusters as the distance between their closest members. Single-linkage would combine the red and yellow clusters because the rightmost red and left-most yellow are closer than the blue item is to any red or yellow. As you can see we will have an elongated red/yellow cluster where the far yellow and reds may be very different from each other.
In complete linkage we measure the distance between clusters as the distance between their furthest members. Complete linkage would not combine the red and yellow because we will use the distance of the furthest red and furthest yellow which is a larger distance than blue to either yellow or red. It looks like the blue is closer to the furthest yellow (on the right) then to the furthest red (on the bottom-left). Therefore blue would be combines with yellow. In complete linkage, the clusters tend to be circular and closer to each other.
The other schemes produce clusters that are in between; not as elongated as produced by simple-linkage and not as circular as produced by complete-linkage.
Although there exist specialized algorithms for single-linkage (Hendrix et al., 2013), complete linkage tends to give better clusters (not elongated) and is more useful.
For these reasons we employ agglomerative hierarchal complete linkage clustering. This method gives more useful clusters than single-linkage and does not pre-designate a specific number of clusters as in non-hierarchal clustering methods. We use the Lance-Williams update algorithm (Lance & Williams, 1967) and We note that the Lance-Williams algorithm is general and can be used with any of the hierarchal methods listed above; for single-linkage we would suggest more efficient algorithms such as Hendrix (2013).
In the next section we give a brief review of the literature with resources for more study.

Non-hierarchal methods
There are numerous non-hierarchal clustering methods that begin with a set number of categories and then try to best place items into those categories. K-means, mentioned earlier, is one of the earliest clustering algorithms (Steinhaus, 1956). In addition regression has been used (Gawrysiak, Okoniewski, & Rybinski, 2001). More recently, decision trees methods, which can be useful for categorization into given categories via numerous decision criteria (Liu, Xia, & Yu, 2005) have been used. Kaewchinporn (2011), combined the decision tree method and K-means by used trees to develop weights to be used in K-means. "Random Forest" classification has been developed to address some shortcomings of decision trees. A Random Forest is a group of decision trees where each tree is built via different test data. When it is time to categorize all the trees are used and an average taken. For more information see (Prinzie & Van den Poel, 2008).
The algorithms for these methods are intrinsically more efficient than the algorithms for hierarchal clustering. That is because these methods do not build a hierarchal tree of categories. Instead they pre-suppose a set of categories and then try to fit the input items into those categories.
Some of these methods assume categorical data such as gender and age and some may use numerical data but they all assume a set number of categories.
On the other hand, there are many applications where the clusters differ from each other just as a matter of degree. Take protein structure categorization as an example. We are given n protein chains of exactly the same sequence but they each are folded (their structure or conformation) in a slightly different shape. The chemist or biologist wants to have these proteins structures categorized such that those of a similar structure will be in the same category. It is apparent that a hierarchy of clusters would be useful since there is no way to decide on a pre-set number of clusters. When clustering is used it is typically with K-means due to the cost of hierarchal clustering but it, unfortunately, does not give the best solutions.
Naïve hierarchal clustering, such as the algorithm parallelized in this paper, was presented for an SIMD machine by Ranka and Sahni (Ranka & Sahni, 1991); they focused on a shuffle-exchange network. Li (1990) also describes one for SIMD machines. Parallel algorithms for naïve hierarchal clustering either were for specific architectures or for single-link clustering.
As mentioned in the last section, in this paper we focus specifically on parallelizing the generic Lance-Williams clustering algorithm.

Lance-William Algorithm
We parallelize the generic Lance William algorithm. This algorithm is able to computer a hierarchal closing dendrogram for many hierarchal clustering schemes.
The Lance-William algorithm is iterative. It starts with n clusters and in every iteration combines two clusters together so that after the iteration there are n-1 clusters. The basic algorithm is:

Lance -William Algorithm
For k= 1 to n 1. From the distance matrix obtain the minimum distance and set aside the (i,j): O(n 2 ) time 2. Combine item i and item j into one item thus reducing the number of clusters by 1.
3. Re-calculate new distances between pre-existing clusters and the new combined cluster: O(n) time.

Network
Implementation of the algorithm distributed hierarchical clusteringwas compiled and run on Andy (College of Staten Island's High Performance Computing cluster). Andy has 744 cores, Nehalem 2.93 GHz chip, 3 Gb per core ("Home | CUNY High Performance Computing Center," n.d.) Parallelized RMSD and distributed hierarchical clustering algorithms were implemented using C and MPI (Pacheco, 1997).
RAM is also distributed which makes 2 − 2 (upper triangle of n by n matrix) storage feasible since the table is divided up amongst the workstations.

Methodology
We described the general Lance William algorithm above.
To parallelize, we divided up the matrix amongst p processors. Figure 2 shows how this is done. Note that a distance matrix only needs the upper (or lower) diagonal part filled (index i,j will have the same value as index j,i). The number of non-blank cells is divided by p; in this case 28/7 = 4 items per processor. Matrix items are assigned to processors on a row by row basis as in the figure.

Parallel Lance Williams Algorithm
Each processor , ℎ 1 ≤ ≤ , is sent their portion of the matrix: items. As the data files were read in from disk they were sent to the processors. The processors are also sent the (i,j) global matrix indices for their data portion. This is especially important for step 6a below.
Divide up matrix amongst the processors.
For k= 1 to n 1. All processors , ℎ 1 ≤ ≤ , simultaneously calculate their local minimum distance from the cells of the distance matrix assigned to them 2. Each p m broadcasts their local minimum 3. Each p m now has all p sets (lmin m , p m ) where lmin m is a local minimum and p m is the corresponding processor. 4. Each processor simultaneously calculates the global minimum (gmin) and the "winning" processorthe process that has the global minimum (i,j) in its part of the matrix. Note that communication is unnecessary at this step since very processor has enough information to calculate the global minimum. 5. The processor that was assigned cell (i,j), which in the example of figure 2 is (2,5), broadcasts that items i and j should be combined into one cluster. 6. Update step: we no longer need columns i and j and rows i and j. The ith column and row will be used for the new combined I,j cluster. The jth column and row will be marked not to be used again.
, +. , +. | , − , | for complete linkage clustering. a. Processors must communicate with each other to obtain any necessary Dk,i from another processor that it needs. Note that the only processors that need to participate in this communication are those that have data items corresponding to rows i or j of the global matrix. Processors that have data items from the jth row or jth column send a list of triples (i,j,distance) to all processors that have data items in the ith row or ith column. b. The sending processors mark the sent matrix elements as erased not to be used again. The processors that receive the communication apply the formula and fill their previously used ith row and column with the updated combined cluster information. Thus the number of clusters has been reduced by 1.

Complexity Analysis
The naïve Lance Williams algorithm is O(n 3 ) There is an outer loop that iterated n time where n is the number of items . For each of those the upper diagonal matrix is search a maximum of ( 2 − 2 ) times. It is a maximum because after each iteration the size of the matrix is reduced by one row and one column as clusters are combined.
In our parallel version all work is divided evenly amongst the processors. In addition, the matrix elements are evenly divided and stored.
Work per iteration: per distributed unit. Communication:  The initial matrix element is sent p separate sends and receives  At most p broadcasts per iteration (step 2) and  At most p sends and receives per iteration (step 6a) Note that a subset of processors are involved in this communication.

Storage:
( 2 − 2 ) ℎ ℎ ( ⁄ ) 6 Experimental Results Figure 2 shows the results of the algorithm as applied to many items. The algorithm was tested many times with varying numbers of items, n, to be clustered. The average of n was 1968.
For each n we ran the program with varying numbers of processors. As we can see from figure 2, speedup is initially linear until about 5 processors. From that point until p=15 the average running time decreased. From p=15 and on the figure show the speed converging. We see that in this case that the optimal number of processors is about p=15. After that, the communication costs amongst processors seem to outweigh any computational gains.
The specific optimum number of processors will grow as the number of items to be clustered grows. The algorithm is scaleable as the problem grows.
Especially noteworthy is that our algorithm cuts down on storage requirements which is a bottleneck for large clustering problems. Use of our algorithm on distributed networks with separate memory spaces seems promising and should make use of hierarchal clustering possible on any distributed network of workstations.