Relational Algorithms for k-means Clustering
Relational Algorithms for k-means Clustering
复制标题
DOI：
10.4230/lipics.icalp.2021.97
复制
发表时间：
2020-08
期刊：
影响因子：
--
通讯作者：
Benjamin Moseley;K. Pruhs;Alireza Samadian;Yuyan Wang
中科院分区：
文献类型：
--
作者：
Benjamin Moseley;K. Pruhs;Alireza Samadian;Yuyan Wang
数据科学家所面临的大多数学习任务都涉及关系数据，但是标准学习问题的大多数标准算法并非旨在接受关系数据作为输入。解决此问题的标准实践是加入关系数据，以创建标准学习算法所期望的几何输入的类型。不幸的是，这种标准做法具有指数性最差的时间和空间复杂性。这使我们考虑了我们所说的关系学习问题：````可以在关系数据上有效地实施哪种标准学习算法，对于那些无法有效的算法可以在关系数据上有效地实现，并且有一种替代算法类似的性能保证了标准算法？''在本文中，我们解决了两种著名的$ k $ -k $ -MEANS聚类问题的算法的关系学习问题。我们首先表明，可以在关系数据上有效地实现$ k $ -Means ++算法。相比之下，我们表明自适应$ k $ -MEANS算法可能无法在关系数据上有效实现，因为这意味着$ p = \＃p $。但是，我们表明，这种自适应$ k $ -MEANS算法的略有变化可以在关系数据上有效实现，并且该替代算法具有与原始算法相同的性能保证，也就是说，它输出$ O（1 1） ）$ - 近似草图。
The majority of learning tasks faced by data scientists involve relational data, yet most standard algorithms for standard learning problems are not designed to accept relational data as input. The standard practice to address this issue is to join the relational data to create the type of geometric input that standard learning algorithms expect. Unfortunately, this standard practice has exponential worst-case time and space complexity. This leads us to consider what we call the Relational Learning Question: ``Which standard learning algorithms can be efficiently implemented on relational data, and for those that can not, is there an alternative algorithm that can be efficiently implemented on relational data and that has similar performance guarantees to the standard algorithm?'' In this paper, we address the relational learning question for two well-known algorithms for the standard $k$-means clustering problem. We first show that the $k$-means++ algorithm can be efficiently implemented on relational data. In contrast, we show that the adaptive $k$-means algorithm likely can not be efficiently implemented on relational data, as this would imply $P = \#P$. However, we show that a slight variation of this adaptive $k$-means algorithm can be efficiently implemented on relational data, and that this alternative algorithm has the same performance guarantee as the original algorithm, that is that it outputs an $O(1)$-approximate sketch.