论文标题
K均值聚类的关系算法
Relational Algorithms for k-means Clustering
论文作者
论文摘要
本文给出了在关系算法模型中有效的K均值近似算法。这是一种直接在关系数据库上运行的算法，而无需执行连接将其转换为行的矩阵代表数据点。运行时间可能呈指数级小于$ n $，这是关系数据库所代表的要聚类的数据点的数量。 很少有关系算法已知，本文提供了设计关系算法以及表征其局限性的技术。我们表明，给定两个数据点作为群集中心，如果我们根据其最接近的中心群集点点，则NP-HARD近似于群集中的点数一般关系输入中的点数。这对于常规数据输入来说是微不足道的，并且该结果例证了标准算法技术在设计有效的关系算法时可能不会直接应用。然后，本文引入了一种新方法，该方法利用拒绝采样，并构建$ k $ -Means ++算法来构建O（1）-Approximate K-Means解决方案。
This paper gives a k-means approximation algorithm that is efficient in the relational algorithms model. This is an algorithm that operates directly on a relational database without performing a join to convert it to a matrix whose rows represent the data points. The running time is potentially exponentially smaller than $N$, the number of data points to be clustered that the relational database represents. Few relational algorithms are known and this paper offers techniques for designing relational algorithms as well as characterizing their limitations. We show that given two data points as cluster centers, if we cluster points according to their closest centers, it is NP-Hard to approximate the number of points in the clusters on a general relational input. This is trivial for conventional data inputs and this result exemplifies that standard algorithmic techniques may not be directly applied when designing an efficient relational algorithm. This paper then introduces a new method that leverages rejection sampling and the $k$-means++ algorithm to construct an O(1)-approximate k-means solution.
