Кластеризация точек по матрице расстояний.

[altha]

Есть матрица NxN расстояний между N точками попарно.
Координаты точек неизвестны. Надо разделить эти точки на кластеры.
Никто не присоветует, как лучше решать?

[Dan_Te]

Подойдет любой из классических методов кластеризации (кстати, за счет этого можно делать не писать программы, а использовать SPSS или Statistica, например).

1) Если размерность d пространства, в котором лежат точки, известна, то задача сводится к классической задаче кластеризации, когда известны координаты точек. Другими словами, координаты можно рассчитать по матрице расстояний, это все равно как последовательно строить треугольники по трем сторонам (если все происходит на плоскости, d=2) или тетраэдры по четырем сторонам (если d=3), и т.д.
Надо только изначально задать положения нескольких точек, например, если d=2, то предположим, что первая точка в начале координат, вторая на положительной полуоси абсцисс, третья в верхней полуплоскости. Тогда координаты всех точек определятся однозначно.

2) Можно сразу провернуть иерархический алгоритм, не вычисляя координаты точек. Я не буду его описывать, потому что про алгоритмы кластеризации хорошо написано здесь:
http://www.statsoft.ru/home/textbook/mo ... cluan.html
Если что-то не понятно, то спрашивайте, постараюсь ответить =))

[altha]

Большое спасибо,
буду читать!

[Зомби]

Доклады Академии наук, Том 348, №1, Стр 34-36
М.К.Козлов
Версия кластерного анализа, элиминирующая кластер как нечеткое понятие

Построение, подобное дендрограмме, но более привязанное к интуитивному пониманию "плотности распределения"

[Mashutka]

[quote="Dan_Te"]Подойдет любой из классических методов кластеризации (кстати, за счет этого можно делать не писать программы, а использовать SPSS или Statistica, например).

1) Если размерность d пространства, в котором лежат точки, известна, то задача сводится к классической задаче кластеризации, когда известны координаты точек. Другими словами, координаты можно рассчитать по матрице расстояний, это все равно как последовательно строить треугольники по трем сторонам (если все происходит на плоскости, d=2) или тетраэдры по четырем сторонам (если d=3), и т.д.
Надо только изначально задать положения нескольких точек, например, если d=2, то предположим, что первая точка в начале координат, вторая на положительной полуоси абсцисс, третья в верхней полуплоскости. Тогда координаты всех точек определятся однозначно.

2) Можно сразу провернуть иерархический алгоритм, не вычисляя координаты точек. Я не буду его описывать, потому что про алгоритмы кластеризации хорошо написано здесь:
http://www.statsoft.ru/home/textbook/mo ... cluan.html
Если что-то не понятно, то спрашивайте, постараюсь ответить

Cпасибо большое за ссылку,очень помогла для выполнения семестровой работы!!!