|
=== Relationship with ''k''-means ===
The weighted kernel ''k''-means problem<ref name="dhillon2004kernel">{{cite conference
The kernel ''k''-means problem is an extension of the ''k''-means problem where the input data points are mapped non-linearly into a higher-dimensional feature space via a kernel function <math>k(x_i,x_j) = \varphi^T(x_i)\varphi(x_j)</math>. The weighted kernel ''k''-means problem further extends this problem by defining a weight <math>w_r</math> for each cluster as the reciprocal of the number of elements in the cluster,
:<math>
\max_{\{C_s\}} \sum_{r=1}^k w_r \sum_{x_i,x_j \in C_r} k(x_i,x_j).
</math>
Suppose <math>F</math> is a matrix of the normalizing coefficients for each point for each cluster <math>F_{ij} = w_r</math> if <math>i,j \in C_r</math> and zero otherwise. Suppose <math>K</math> is the kernel matrix for all points. The weighted kernel ''k''-means problem with n points and k clusters is given as,
:<math>
\max_F \operatorname{trace} (KF)
</math>
such that
:<math>
F = G_{n\times k}G_{k\times n}^T
</math>
:<math>
G^TG = I
</math>
such that <math>\operatorname{rank}(G) = k</math>. In addition, there are identity constraints on <math>F</math> given by,
:<math>
F\cdot \mathbb{I} = \mathbb{I}
</math>
:<math>
F^T\mathbb{I} = \mathbb{I}
</math>
where <math>\mathbb{I}</math> represents a vector of ones.
This problem can be recast as
:<math>
\max_G \operatorname{trace}(G^TG).
</math>
This problem is equivalent to the spectral clustering problem when the identity constraints on <math>F</math> are relaxed. In particular, the weighted kernel ''k''-means problem can be reformulated as a spectral clustering (graph partitioning) problem and vice versa. The output of the algorithms are eigenvectors which do not satisfy the identity requirements for indicator variables defined by <math>F</math>. Hence, post-processing of the eigenvectors is required for the equivalence between the problems.<ref name="dhillon2004kernel">{{cite conference
| author = Dhillon, I.S. and Guan, Y. and Kulis, B.
| year = 2004
| book-title = Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining
| pages = 551–556
| url = https://www.cs.utexas.edu/users/inderjit/public_papers/kdd_spectral_kernelkmeans.pdf
}}</ref>
Transformingshares the spectralobjective clusteringfunction problemwith intothe aspectral weightedclustering kernelproblem, ''k''-meanswhich problemcan greatlybe reducesoptimized thedirectly computationalby multi-level burdenmethods.<ref>{{cite journal|last=Dhillon|first=Inderjit|author2=Yuqiang Guan |author3=Brian Kulis |title=Weighted Graph Cuts without Eigenvectors: A Multilevel Approach|journal=IEEE Transactions on Pattern Analysis and Machine Intelligence|date=November 2007|volume=29|issue=11|pages=1944–1957|doi=10.1109/tpami.2007.1115|pmid=17848776|citeseerx=10.1.1.131.2635|s2cid=9402790}}</ref>
=== Relationship to DBSCAN ===
| 