Designing an efficient parallel spectral clustering algorithm on multicore processors in Julia Abstract   Spectral clustering is widely used in data mining, machine learning and other fields. It can identify the arbitrary shape of a sample space and converge to the global optimal solution. Compared with the traditional kmeans algorithm, the spectral clustering algorithm has stronger adaptability to data and better clustering results. However, the computation of the algorithm is quite expensive. In this paper, an efficient parallel spectral clustering algorithm on multicore processors in the Julia language is proposed, and we refer to it as juPSC. The Julia language is a highperformance, opensource programming language. The juPSC is composed of three procedures: (1) calculating the affinity matrix, (2) calculating the eigenvectors, and (3) conducting kmeans clustering. Procedures (1) and (3) are computed by the efficient parallel algorithm, and the COO format is used to compress the affinity matrix. Two groups of experiments are conducted to verify the accuracy and efficiency of the juPSC. Experimental results indicate that (1) the juPSC achieves speedups of approximately 14   xc3x97        xe2x88xbc  18  xc3x97     on a 24core CPU and that (2) the serial version of the juPSC is faster than the Python version of scikitlearn. Moreover, the structure and functions of the juPSC are designed considering modularity, which is convenient for combination and further optimization with other parallel computing platforms.

A Binary Linear ProgrammingBased KMeans Approach for the Capacitated Centered Clustering Problem The kmeans algorithm is one of the most popular clustering algorithms in the machine learning community. Its simplicity and scalability make it the primary choice for many clustering applications. We introduce here a variant of the kmeans algorithm that can account for complex side constraints. The key idea is to use binary linear programming for assigning objects to clusters. Unlike existing extensions of the kmeans algorithm that are designed for accommodating specific types of constraints, our approach can be applied to a wide range of constrained clustering problems with minor modifications. We demonstrate the effectiveness and efficiency of the proposed approach by comparing it to a stateoftheart algorithm on a test set that comprises 18 instances of the capacitated centered clustering problem. The proposed approach performed particularly well on largesized instances with more than 100 clusters. It even found new bestknown solutions for the four largest instances in the test set.