探討一個更有效的 K-means 組群化演算法

Abstract

當我們要分割資料集(dataset)成為多個組群(cluster)的時候，K-means 組群化(clustering)演算法可以說是一種很合適而且普遍使用的方式，然而大多數以 K-means 為基礎的組群化實作卻要花費大量的距離計算次數才能夠算出收斂時的形心。在本篇文章中，我們提出一個新的以 K-means 為基礎的組群化演算法，它以一種較有效率的方式算出與傳統方法一樣潔果的形心。在本演算法中，我們將原始的資料集分割成一個個大小相同的子空間稱為單位區塊。我們使用一一種簡單的計算方式算出個單位區塊的形心稱為CUB(centroid of unit block)，而這些CUB可以代表簡化後的資料集，其個數遠小於原始的資料集。利用這簡化後的資料集與處理位於組群邊界上單位區塊的機制，便可以很快方便使用者的應用，我們在文中特別討論單位區塊最佳化和效能評估。