# Ising-Based Kernel Clustering +
## 3 Ising-Based Kernel Clustering
### Kernel Method for Combinatorial Clustering  
In the kernel method, elements of a Gram matrix \(G\) express the degree of similarities in the high-dimensional feature space between two data points. The elements of a Gram matrix are calculated by the following equation.  
\[g(x_{i},x_{j}) = k(x_{i},x_{j})-\frac{1}{n}\sum_{l}k(x_{i},x_{l}) \tag{6}\] \[- \frac{1}{n}\sum_{k}k(x_{k},x_{j})+\frac{1}{n^{2}}\sum_{k,l}k(x_{ k},x_{l}).\]  
Hereinafter, \(g(x_{i},x_{j})\) is denoted as \(g_{ij}\). The proposed method can calculate all necessary similarities in advance. This is because the proposed method is the optimization method using similarities among all data points. This method does not need to update any similarities in the calculation process. The calculation of similarities is performed for all pairs of data points. Thus, the Gram matrix \(G\) is calculated by the following equation.  
\[G = \begin{bmatrix}g_{0,0}\cdots g_{0,N-1}\\ \vdots\ddots\vdots\\ g_{N-1,0}\cdots g_{N-1,N-1}\end{bmatrix} \tag{7}\] \[= \boldsymbol{M}-\overline{M_{h}}[1\ldots 1]-\begin{bmatrix}1\\ \vdots\\ 1\end{bmatrix}\overline{M_{h}}^{\mathsf{T}}-\overline{M_{a}}\begin{bmatrix}1 \ldots 1\\ \vdots\ddots\vdots\\ 1\ldots 1\end{bmatrix}\]  
\(M\) is a kernel matrix with elements calculated by the kernel function. \(\overline{M_{h}}\) is a \(K\)-dimensional vector whose \(i\)-th vector component represents an arithmetic mean among \(k(x_{i},x_{0}),\ldots,k(x_{i},x_{N-1})\). The second and third terms of Equation (7) are derived from the second and third terms of Equation (6). \(\overline{M_{a}}\) in Equation (7) is a scalar that represents the arithmetic mean among all elements of the kernel matrix \(\mathbf{M}\). Therefore, the elements of the fourth term in Equation (7) are equivalent to the fourth term of Equation (6) for each element \(g_{ij}\). Switching the kernel function, called a kernel trick, enables the Gram matrix to represent various measures of similarities. \(k(\mathbf{x_{i}},\mathbf{x_{j}})\) requires the kernel trick to select the appropriate Mercer kernel defined by [PERSON]'s theorem. [PERSON]'s theorem determines that the available matrix used as the Gram matrix is only positive and semi-definite. The kernel function is defined so that the inner product matrix transformed from the original data is the symmetric Gram matrix. In this paper, the kernel function \(k(\mathbf{x_{i}},\mathbf{x_{j}})\) is given by the following Gaussian kernel.  
\[k(\mathbf{x_{i}},\mathbf{x_{j}})=\exp\left(-\frac{1}{2\sigma^{2}}d(\mathbf{x_{i}},\mathbf{x_{j} })^{2}\right). \tag{8}\]  
\(k(\mathbf{x_{i}},\mathbf{x_{j}})\) in Equation (8) are the elements of the kernel matrix \(\mathbf{M}\) and are also calculated in the same way for all pairs of the data points. Thus, the kernel matrix is expressed by using a squared Euclidean distance matrix \(\mathbf{D^{2}}\) as follows, where \(\mathbf{D^{2}}\) has the elements of squared distances \(d(x_{i},x_{j})^{2}\).  
\[\mathbf{M} = \begin{bmatrix}k(x_{0},x_{0})\ldots k(x_{0},x_{N-1})\\ \vdots\ddots\vdots\\ k(x_{N-1},x_{0})\ldots k(x_{N-1},x_{N-1})\end{bmatrix} \tag{9}\] \[= EXP(-\frac{1}{2\sigma^{2}}\mathbf{D^{2}})\] \[= \begin{bmatrix}\exp\left(-\frac{1}{2\sigma^{2}}d(x_{0},x_{0})^{2 }\right)\ldots exp\left(-\frac{1}{2\sigma^{2}}d(x_{0},x_{N-1})^{2}\right)\\ \vdots\ddots\vdots\\ exp\left(-\frac{1}{2\sigma^{2}}d(x_{N-1},x_{0})^{2}\right)\ldots exp\left(- \frac{1}{2\sigma^{2}}d(x_{N-1},x_{N-1})^{2}\right)\end{bmatrix}\]  
Here, \(EXP(\mathbf{X})\) is defined as the function that calculates Napier's constant \(e\) to the power of each element in the matrix \(\mathbf{X}\). Nowadays, numerical libraries implement such an exponential function to accelerate calculations. In addition, the same calculations of \(\frac{1}{2\sigma^{2}}d(x_{i},x_{j})\) are performed as the scalar-matrix calculation in recent numerical libraries.