Алгоритм кластерного анализа? (Какой-нибудь побыстрее бы.)

[Portnov]

Может кто подскажет?

Нужен алгоритм кластерного анализа, работающий достаточно быстро. Классический k-means - вобще NP-полный. А требования к скорости примерно такие: где-то миллион трёхмерных векторов на десяток-другой кластеров разложить за пару секунд. K-means на моих данных нужно не меньше 30 секунд. Особенность ситуации: почти совсем не важна точность алгоритма. Не важно, будет ли задаваться число кластеров изначально или выбираться самим алгоритмом. Более того, на самом деле мне нужны только центры этих кластеров, какой вектор к какому кластеру принадлежит - мне не интересно (так что совершенно неважно, что алгоритм будет делать с пограничными векторами). Если алгоритм будет игнорировать мелкие кластеры или выбросы - тоже не важно. В общем, можно жертвовать почти чем угодно в угоду скорости. Есть что-нибудь такое?

[sciko]

с-means? А вообще хотелось бы чем не подошли вот эти методы кластеризации.