The k-medoids algorithm has been one of the representative clustering algorithm. This algorithm is ro-bust to noises or outliers than k-means algorithm due to medoids selected from actual data objects. However, k-medoids algorithm isn’t widely used for big data analytics as the k-means algorithm because of its high computational complexity to find new medoid. Solving complexity problem of k-medoids, there are many variations of k-medoid algorithm which manly focused on how to find medoid object efficiently. But, those algorithms fail to consider the accuracy. This thesis analysis of limitation about previous studies and suggest a new 2LP-PAM algorithms. The 2LP-PAM features fast completion and high accuracy. The level 1 PAM is global medoids search phase to find good seeds using PAM algorithm on sampling objects. The level 2 PAM is global refining phase using local medoid search on each cluster. We prove theoretically the optimal sam-pling parameters for level 1 PAM and show the parameters aren’t local optimum objects. Also, We suggest a new local search algorithm using disjoint dataset. Finally, we evaluated our algorithm using real dataset and show that 2LP-PAM is the fast and the most accurate algorithm among distributed k-medoids algorithms.
k-medoids 알고리즘은 대표적인 클러스터링 알고리즘이다. 이 알고리즘은 실제 데이터 객체에서 선택되어진 medoids를 사용하기 때문에 outlier와 noise에 강하다. 하지만, k-means 알고리즘과 달리 새로운 medoid를 탐색하는데 높은 계산 복잡도를 필요로하는 k-medoids 알고리즘은 빅 데이터 분석에는 널리 쓰지지 못하고 있다. k-medoids 알고리즘의 계산 복잡도 문제를 하결하기 위해, 어떻게 medoid 객체를 효율적으로 찾을지에 초점을 맞춘 다양한 알고리즘의 변형들이 있다. 하지만, 그러한 알고리즘들을 계산 복잡도 문제를 극복하는데 초점을 맞춘나머지 알고리즘의 정확도에 대해서는 충분히 고려하지 못하였다. 이 논문은 기존 연구된 알고리즘들의 한계를 분석하고 새로운 2LP-PAM 알고리즘을 제안한다. 2LP-PAM 알고리즘은 빠른 완료와 높은 정확도를 특징으로하며, 전역적 탐색을 통해 좋은 seed를 찾는 level 1 단계와 각 클러스터에 대한 지역적 탐색을 통한 전역적인 보정인 level 2의 두 단계로 구성된다. 우리는 level 1 PAM에 있어서 최적화된 샘플링을 위한 파라미터를 이론적으로 밝히며 해당 파라미터는 지역 최적 수렴에 빠지지 않음을 보인다. 또한, 분리분할을 통한 새로운 지역 탐색 알고리즘을 제안한다. 마지막으로, 우리는 real dataset을 통하여 알고리즘들을 평가하며 분산 k-medoids 알고리즘 중 제안한 2LP-PAM이 가장 빠르며 가장 정확한 알고리즘임을 보인다.
