К-среднее с эллипсоидами

Question

У меня есть n точек в R ^ 3, которые я хочу покрыть k эллипсоидами или цилиндрами (мне все равно, что проще). Я хочу примерно минимизировать объединение томов. Скажем, n - это десятки тысяч, а k - несколько. Время разработки (то есть простота) важнее времени выполнения.

Очевидно, что я могу использовать k-средства и использовать идеальные шары для своих эллипсоидов. Или я могу запустить k-средних, а затем использовать минимум эллипсоидов, охватывающих кластер, а не покрывать шариками, хотя в худшем случае это не лучше. Я видел разговоры об обработке анизотропии с помощью k-средних, но ссылки, которые я видел, казалось, думали, что у меня есть тензор; Я не знаю, я просто знаю, что данные будут объединением эллипсоидов. Есть предложения?

[Редактировать: есть пара голосов за подбор смеси многовариантных гауссиан, что кажется жизнеспособной попыткой. Запуск EM-кода для этого не уменьшит объем объединения, но, конечно, k-means также не минимизирует объем.]

Answer 1

Таким образом, вы, вероятно, знаете, что k-means является NP-сложным, и эта проблема является еще более общей (более сложной).Поскольку вы хотите создавать эллипсоиды, может иметь смысл установить смесь k многомерных гауссовых распределений.Возможно, вы захотите попытаться найти решение с максимальным правдоподобием, которое представляет собой невыпуклую оптимизацию, но, по крайней мере, ее легко сформулировать и, скорее всего, доступен код.

Кроме того, вам, скорее всего, придется написать собственный эвристический алгоритм поиска с нуля, это просто огромное дело.

Answer 2

Я сделал нечто подобное с многовариантными гауссианами, используя этот метод . Авторы используют куртоз в качестве меры разделения, и я нашел, что это удовлетворительный метод для моего приложения, точки кластеризации, полученные с помощью лазерного дальномера (то есть компьютерного зрения).

Answer 3

Если эллипсоиды могут сильно перекрываться, затем такие методы, как k-означает, что пытаются назначить точки для отдельных кластеров не будет работать очень хорошо. Часть каждого эллипсоида должна соответствовать поверхности вашего объекта, но все остальное может быть внутри, все равно. То есть алгоритмы покрытия мне кажется, это сильно отличается от алгоритмов кластеризации / расщепления; союзы не делятся.

Гауссовские смеси с множеством совпадений? Понятия не имею, но посмотрите рисунок и код на Числовые рецепты с. 845 .

Покрытия трудны даже в 2d, см. найти почти-минимально-покрытие-множество-дисков-на-2-D-плоскости . * +1011 *