Probabilistic k-Median Clustering in Data Streams
Probabilistic k-Median Clustering in Data Streams
复制标题
数据流中的概率 k 中值聚类
DOI：
10.1007/s00224-014-9539-7
复制
发表时间：
2012
影响因子：
0.5
通讯作者：
C. Sohler
中科院分区：
文献类型：
--
作者：
Christiane Lammersen;Melanie Schmidt;C. Sohler
我们工作的重点是引入和构造概率核心集。概率核心集可以包含概率点，并且这些点的数量应该是输入大小的多对数。然而，总的存储大小也受到每个点的概率分布的表示大小的影响。因此，我们的第一个观察是，概率核心集的大小应受到点的数量和点的表示大小的限制。我们提出了度量和欧氏情形下概率k-中值问题的第一（k，ε）-coreset构造.核心集的大小为poly（ε−1，k，log（W/（pmin <$δ），其中W是加权概率输入点的期望总权重（当所有权重至少为1时），pmin是某个点在某个位置实现的概率，δ是构造的错误概率。我们的欧几里德问题的核心集可以保持在数据流。
The focus of our work is introducing and constructing probabilistic coresets. A probabilistic coreset can contain probabilistic points, and the number of these points should be polylogarithmic in the input size. However, the overall storage size is also influenced by representation size of the propability distribution of each point. So, our first observation is that the size of probabilistic coresets shall be restricted in the number of points and in the representation size of the points. We propose the first (k, ε)-coreset constructions for the probabilistic k-median problem in the metric and Euclidean case. The coresets are of size poly(ε−1, k, log(W/(pmin⋅δ))), where W is the expected total weight of the weighted probabilistic input points when all weights are scaled to be at least one, pmin is the probability of a point to be realized at a certain location, and δ is the error probability of the construction. Our coreset for the Euclidean problem can be maintained in data streams.