Although kernel-based unsupervised learning methods, such as kernel k-means and kernel Principal Component Analysis (KPCA), have great potential for analyzing complex data, their practicality is limited by the high computational complexity. In this paper, we present novel techniques based on subspace approximation to accelerate kernel k-means and KPCA to reduce their Omega(kn^2) complexity. For kernel k-means, we reduce the per-iteration complexity down to O(n^(1+delta)) for any delta \in(0, 1), and prove that our algorithm`s per-iteration approximation of the distortion is within a factor of (1+n^(-delta) of the regular kernel k-means algorithm`s distortion. For KPCA, we lower the complexity down to O(kn(1+delta) + k^3), where k is the number of principal components, and prove that the reduced-size problem we solve is spectrally equivalent to the original KPCA problem. Through extensive experiments, we confirm that our algorithms are very fast compared to the original algorithms while maintaining good accuracy.
커널 k-평균 군집화와 커널 주성분 분석법같은 커널 방식의 러닝은 복잡한 데이터를 분석하는데 큰 장점을 가지고 있지만, 계산 복잡도가 크다는 단 점을 가지고 있다. 이 학위 논문에서는 커널 k-평균 군집화와 커널 주성분 분석법에 대해 부분공간 방식을 도입하여 복잡도를 kn^2보다 훨 씬 낮게 만든 알고리즘을 설명한다. 제시한 커널 k-평균 군집화에 대해서 복잡도를, 임의의 0과 1사이의 delta에 대해, 매 반복에 따라 O(n(1+delta))를 가지며 정확도는 (1+n^(-delta))의 비로 가짐을 증명 하였다. 커널 주성분 분석법에 대해서는 원래의 문제 크기를 줄여서 복잡도 O(kn^(1+delta)+k^3)로 가지는 알고리즘을 제시 하였고 그것이 원래 문제 푸는것과 동치임을 증명하였다. 그리고 다양한 실험을 통해 알고리즘이 좋은 정확도를 유지하면서 빠른 성능을 가짐을 확인하였다.