2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

 
 
 
 Re: Вопрос из области распознавания образов
Сообщение19.09.2009, 05:35 
А что такое с.к.о.?

 
 
 
 Re: Вопрос из области распознавания образов
Сообщение19.09.2009, 09:26 
Аватара пользователя
с.к.о. - среднее квадратическое отклонение

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

 
 
 
 Re: Вопрос из области распознавания образов
Сообщение19.09.2009, 11:05 
Сведем к более наглядной задаче. Сначала центрируем строки,вычитая из каждой строки среднее арифметическое всех 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,смотреть не нужно.То есть разово задача решаема,но если она в цикле...

 
 
 
 Re: Вопрос из области распознавания образов
Сообщение19.09.2009, 11:43 
Аватара пользователя
Цитата:
Для каждого разбиения 50 векторов на 4
Цитата:
и при организации полного перебора разбиения,
А не долго ли перебираться будет? А еще и вычисления Дисперсии.

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

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

 
 
 
 Re: Вопрос из области распознавания образов
Сообщение23.09.2009, 16:00 
nn910, поясните, пожалуйста, т.к. не могу ухватить идею того, что Вы предлагаете сделать.
Цитата:
Сведем к более наглядной задаче. Сначала центрируем строки,вычитая из каждой строки среднее арифметическое всех 50 строк,ответ задачи от этого не изменится.Получаем 50 векторов 10000мерных

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

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

 
 
 [ Сообщений: 6 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group