Вопрос из области распознавания образов

[Pebble]

Здравствуйте.
Вопрос такой. Имеется матрица размером 50x10000. Каждый столбец матрицы - вектор признаков образа. Хочется сгруппировать строки этой матрицы так, чтобы получилось 4 группы. Далее для каждой группы сложить все строки, входящие в нее, получив в итоге 4 результирующие строки. Собственно хочется, чтобы с.к.о. каждой такой результирующей строки было максимально и при этом эти 4 строки отличались друг от друга по с.к.о. минимально.
Подскажите, пожалуйста, что можно попытаться сделать.

[Circiter]

А что такое с.к.о.?

[Pavia]

с.к.о. - среднее квадратическое отклонение

Я бы попробовал применить автоматические методы сегментации. K-means, карты Кохенена и др

[nn910]

Сведем к более наглядной задаче. Сначала центрируем строки,вычитая из каждой строки среднее арифметическое всех 50 строк,ответ задачи от этого не изменится.Получаем 50 векторов $v_i$ 10000мерных но естественно лежащих в каком-то подпространстве размерности до 50(кстати косинусы углов между ними-это коэффициенты корреляции этой пары строк).Сумма их =0.Посчитаем D - сумму квадратов длин всех векторов.Для каждого разбиения 50 векторов на 4 группы М1,М2,М3,М4 $DM=\min_{i}{\sum_{Mi}{|v_j|^2}-(\dfrac{1}{|Mi|} |\sum_{Mi}{v_j}|)^2}$откуда ясна задача-первое слагаемое максимально приблизить к D/4, а у суммы векторов каждого подмножества сохранить свойство всего множества -сумма=0,или мала.То есть просто набирать минимизируя сумму,пока сумма квадратов длин набранных не дойдет до D/4,потом 2ю группу,итд.Получится уже неплохое DM~0,2D, и при организации полного перебора разбиения,у которых сумма квадратов длин хотя бы одной группы меньше DM,смотреть не нужно.То есть разово задача решаема,но если она в цикле...

[Pavia]

Цитата:

Для каждого разбиения 50 векторов на 4

Цитата:

и при организации полного перебора разбиения,

А не долго ли перебираться будет? А еще и вычисления Дисперсии.

-- Сб сен 19, 2009 13:20:24 --

Хотя тут у нас сочетания без повторений. 230300 вариантов на 10 000 сумирование за несколько минут рассчитается

[Pebble]

nn910, поясните, пожалуйста, т.к. не могу ухватить идею того, что Вы предлагаете сделать.

Цитата:

Сведем к более наглядной задаче. Сначала центрируем строки,вычитая из каждой строки среднее арифметическое всех 50 строк,ответ задачи от этого не изменится.Получаем 50 векторов 10000мерных

Насколько я понимаю, каждую строку рассматриваем, как точку в 10000-мерном пространстве. Имеем 50 таких точек. Вычитая среднее арифметическое - переносим начало координат в центр облака точек.

Цитата:

Посчитаем D - сумму квадратов длин всех векторов

Величина D/50 есть дисперсия (если не цепляться к терминологии). О чем нам может сказать дисперсия в данном случае? По-моему, ни о чем. Или я не прав?
И дальше совсем непонятно что мы пытаемся сделать.