Approximate Distributed K-Means Clustering over a Peer-to-Peer Network
Approximate Distributed K-Means Clustering over a Peer-to-Peer Network
复制标题
DOI：
10.1109/tkde.2008.222
复制
发表时间：
2009-10-01
影响因子：
8.9
通讯作者：
Kargupta, Hillol
中科院分区：
文献类型：
--
作者：
Datta, Souptik;Giannella, Chris R.;Kargupta, Hillol
数据密集型P2P网络的应用越来越广泛。在这种P2P环境中的数据挖掘是一种自然的扩展。然而，常见的单片数据挖掘架构不适合在这样的环境中，因为它们通常需要集中的分布式数据，这通常是不实际的，在一个大型的P2P网络。避免大规模同步或数据集中的分布式数据挖掘算法提供了另一种选择。本文研究了数据和计算资源分布在大型P2P网络中的分布式K均值聚类问题。它提供了两种算法，它们产生的结果近似于标准的集中式K-means聚类算法。第一个是设计在一个动态的P2P网络，可以产生集群的“本地”同步。第二种算法使用均匀采样的对等点，并提供了分析保证的准确性聚类的P2P网络。实验结果表明，这两种算法表现出良好的性能相比，他们的集中式同行在适度的通信成本。
Data intensive Peer-to-Peer (P2P) networks are finding increasing number of applications. Data mining in such P2P environments is a natural extension. However, common monolithic data mining architectures do not fit well in such environments since they typically require centralizing the distributed data which is usually not practical in a large P2P network. Distributed data mining algorithms that avoid large-scale synchronization or data centralization offer an alternate choice. This paper considers the distributed K-means clustering problem where the data and computing resources are distributed over a large P2P network. It offers two algorithms which produce an approximation of the result produced by the standard centralized K-means clustering algorithm. The first is designed to operate in a dynamic P2P network that can produce clusterings by "local" synchronization only. The second algorithm uses uniformly sampled peers and provides analytical guarantees regarding the accuracy of clustering on a P2P network. Empirical results show that both the algorithms demonstrate good performance compared to their centralized counterparts at the modest communication cost.