# Ising-Based Kernel Clustering +
## 4 Evaluation
### Execution Time  
Figure 8 shows the total execution time of the preprocessing for annealing. These execution times include the times for generating the kernel, Gram, and QUBO matrices. _Proposed_ indicates the proposed method that is defined by the matrix-matrix calculations for using numerical libraries. _Conventional_ is the conventional implementation in which coefficients of the kernel, Gram, and QUBO matrices are calculated iteratively [22]. _Internal_ and _External_ indicate the internally-constrained and externally-constrained QUBO matrix-generating methods, respectively. The internally-constrained QUBO matrix contains coefficients of the Lagrange multiplier. Conversely, the externally-constrained QUBO  
Figure 6: The clustering results on the dataset with 6 circles. Data points having the same color belong to the same cluster. (**a**) The conventional Euclidean-based method; (**b**) the proposed kernel-based method. Figure 7: The qualities of the proposed kernel-based and conventional Euclidean-based methods for different numbers of clusters. matrix does not contain the coefficients of the Lagrange multiplier. The experiments are conducted by changing the number of data points from 8 to 1024. When the number of data points is eight, both internal and external _Proposed_ methods are about 10 times faster than both internal and external _Conventional_ methods. This is because the preprocess for annealing is represented as the matrix-matrix calculations to utilize numerical libraries. The numerical libraries can accelerate the matrix-matrix calculations by adopting techniques of distributed memory and highly parallel programming models. As the number of data points increases, the difference between _Proposed_ and _Conventional_ increases. The difference between the proposed and the conventional methods are at most 12.4 million and 6.1 million times when the number of data points is 1024. This is because the conventional method requires more instructions for calculating coefficients than the proposed method. The proposed method uses a numerical library to process calculations with a high level of parallelism. Moreover, numerical libraries are highly optimized to maximize machine performance by specializing in specific calculations. Conventional methods, on the other hand, are implemented in script languages such as Python to implement easily and are not specialized in bringing the best out of the performance. As a result, the proposed method achieves speedups of millions of times over the conventional method. Since the proposed method accelerates the preprocess for annealing methods, the matrix-matrix computation has the potential to solve large-scale Ising-based clustering problems. To further investigate the effectiveness of matrix-matrix calculations in the preprocess for annealing, Figures 9-12 show the breakdowns of the preprocess time. Figures 9 and 10 show the execution times for calculating the kernel and Gram coefficients, respectively. _Proposed_ uses the method of determining the coefficients of matrices by matrix-matrix calculations, as shown in Equations (7) and (9). _Conventional_ calculates the coefficients sequentially by implementing Equations (6) and (8). Figure 8: Total execution time of preprocessing for annealing. Figure 9 shows that the execution time for determining the coefficients of the kernel matrix is not so long. The acceleration rate of the proposed method to the conventional method is also small, ranging from 1.5 to 7.6. This is because the proposed method determines the coefficients of kernel matrix by not matrix-matrix calculations but scalar-matrix calculation. As shown in Equation (9), an exponential operator \(exp()\) and a multiplier \(-\frac{1}{2\sigma^{2}}\) is applied to the elements of the Gaussian kernel matrix \(\mathbf{M}\) only once to each element of the squared distance \(\mathbf{D^{2}}\). Since the numerical library cannot be highly parallelized for scalar-matrix operation, the acceleration ratio of the proposed method to the conventional method is low.