The importance of data mining and management grows as a vast number of data are accumulated. However, traditional data mining algorithms, such as clustering and locality-sensitive hashing, do not scale well in the presence of large and complex data sets. This is primarily due to the fact that a custom similarity function, known as the “kernel function”, is used to compute distances between data points with complex data types and non-linear relationships. In order to use kernelization, the original data mining algorithm must be re-formulated into a form that uses inner-products between the given data points. Unfortunately, such a re-formulation comes at the cost of expensive operations such as an
eigen-decomposition of a large similarity matrix. In this work, we show how uniform sampling among the given data points can be used to address high computational complexities in kernelized data mining algorithms. In particular, we focus on three major algorithms used in data mining and retrieval: kernel k-means, kernel principal component analysis (KPCA), and locality-sensitive hashing (LSH).
For the kernel k-means clustering, we use uniform sampling to compute a (1 + n-δ)-approximation of the per-iteration cost with complexity O(n^{1+δ}), for any δ ∈ (0, 1).
For KPCA, we lower the complexity down to O(kn^{1+δ} +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.
For the LSH algorithm we present, we address an additional issue of distribution-sensitivity, where the query time and accuracy varies depending on the underlying distribution of the data. We show that Voronoi-partitioning the data set around centers chosen uniformly at random yields stable and fast query time while maintaining high accuracy with fewer hash tables. We also show that our algorithm satisfies the locality-sensitive property. Through extensive experiments, we confirm that our algorithms
are very fast compared to the original algorithms while maintaining good accuracy.
많은 데이터 마이닝 알고리즘들은 이미지나 복잡계 네트워크 등의 복합적이고 비선형적 특징을 지닌 데이터를 다루기 위해 커널 기법을 사용한다. 커널 기법은 주어진 데이터를 임의의 고차원 유클리드 공간으로 묻음(embedding)으로써, 고차원에서의 내적을 간결히 표현한다. 이를 통해 유사도 함수의 정의와 데이터의 비선형성을 해결할 수 있게 되지만, 군집화나 주성분 분석등의 알고리즘을 커널화 시키면 높은 계산 복잡도를 얻게 된다. 본 논문에서는 균일 표집법을 통해 원래 알고리즘을 근사화하여, 커널화를 통해 증가되는 복잡도를 줄이는 방법을 제안한다. 여러 마이닝 알고리즘 중에서도 특히, 커널 기반의 군집화와 주성분 분석, 그리고 최근방 이웃 탐색을 위한 해싱 기법을 다룬다.
군집화와 주성분 분석 알고리즘의 측면에서는 각 반복 계산시 행하는 비용 함수의 계산을 고속화하기 위해 주어진 데이터의 일부만을 균일하게 취하는 방식을 제시한다. 이렇게 근사화한 비용 함수가 원래 함수값의 좋은 근사가 됨을 보이고, 원래 방식과 수치적인 차이는 거의 없으면서도 10배에서 15배 빠른 수행 시간을 얻는다는 것을 실험적으로 보인다.
해싱 알고리즘의 측면에서는, 균일 표집을 통해 얻은 대표점들을 중심으로 보로노이 분할을 하여 해싱 함수를 정의하면, 기존의 커널 기반의 해싱 기법들 보다 훨씬 빨리 질의를 수행할 수 있음을 보인다. 추가적으로, 이 논문에서 제시한 방식으로 해싱을 수행하면 국소적 민감형 해싱 (Locality-sensitive hashing) 성질을 만족하게 되어, 근사 최근방 이웃 탐색 문제도 효율적으로 해결할 수 있음을 증명하였다.
