A linear time algorithm for approximate 2-means clustering (Q2573339)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A linear time algorithm for approximate 2-means clustering |
scientific article |
Statements
A linear time algorithm for approximate 2-means clustering (English)
0 references
7 November 2005
0 references
The authors propose an efficient algorithm suitable for the \(k\)-means clustering problem. More precisely, they suggest a randomized algorithm that determinate the \((1+\varepsilon)\) approximate 2-means clustering of a given points set in linear time, in constant probability, for any dimension. The main result of the paper is the following assertion: The algorithm specified in the paper determinates a \((1+\varepsilon)\) approximate 2-means clustering of a point set \(P\) in \(R_d\) in time \(O\big((1/\varepsilon)^{O(1/\varepsilon)} (d/\varepsilon)^dn\big)\), with constant probability.
0 references
\(k\)-means clustering
0 references
\((1+\varepsilon)\) approximate 2-means clustering
0 references
randomization
0 references
randomized algorithm
0 references
