Unexpected Effects of Online no-Substitution k-means Clustering
Offline k-means clustering was studied extensively, and algorithms with a constant approximation are available. However, online clustering is still uncharted. New factors come into play: the ordering of the dataset and whether the number of points, n, is known in advance or not. Their exact effects are unknown. In this paper we focus on the online setting where the decisions are irreversible: after a point arrives, the algorithm needs to decide whether to take the point as a center or not, and this decision is final. How many centers are needed and sufficient to achieve constant approximation in this setting? We show upper and lower bounds for all the different cases. These bounds are exactly the same up to a constant, thus achieving optimal bounds. For example, for k-means cost with constant k>1 and random order, Theta(log n) centers are enough to achieve a constant approximation, while the mere a priori knowledge of n reduces the number of centers to a constant. These bounds hold for any distance function that obeys a triangle-type inequality.
Code (0)
등록된 구현이 없습니다.
Tasks
ClusteringOnline ClusteringMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Decorrelated Clustering with Data Selection Bias
Most of existing clustering algorithms are proposed without considering the selection bias in data. In many real applications, however, one cannot guarantee the data is unbiased. Selection bias might bring the unexpected…
ClusteringSelection biasNo-substitution k-means Clustering with Adversarial Order
We investigate $k$-means clustering in the online no-substitution setting when the input arrives in \emph{arbitrary} order. In this setting, points arrive one after another, and the algorithm is required to instantly dec…
ClusteringPolyspectral Mean based Time Series Clustering of Indian Stock Market
In this study, we employ k-means clustering algorithm of polyspectral means to analyze 49 stocks in the Indian stock market. We have used spectral and bispectral information obtained from the data, by using spectral and …
ClusteringTime SeriesTime Series ClusteringBrewing Discontent: How U.S. Reciprocal Tariffs on Coffee Could Echo the Boston Tea Party
This research employs quantitative techniques interpreted through relevant economic theories to analyze a proposed U.S. "Discounted Reciprocal Tariff" structure. Statistical modeling (linear regression) quantifies the po…
ClusteringregressionA Computational Approach to Improving Fairness in K-means Clustering
The popular K-means clustering algorithm potentially suffers from a major weakness for further analysis or interpretation. Some cluster may have disproportionately more (or fewer) points from one of the subpopulations in…
ClusteringFairness