A linear time algorithm for approximate 2-means clustering (Q2573339): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
| Property / full work available at URL | |||
| Property / full work available at URL: https://doi.org/10.1016/j.comgeo.2005.01.003 / rank | |||
Normal rank | |||
| Property / OpenAlex ID | |||
| Property / OpenAlex ID: W2095535627 / rank | |||
Normal rank | |||
Revision as of 02:30, 20 March 2024
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
