2014 dxdy logo

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

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


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему
 
 Операции с матрицами
Сообщение21.05.2015, 12:24 


10/06/12
33
Добрый день!

Возникла следующая задача из реальной жизни, алгоритм решения для которой пока подобрать не удалось.

Задача:
Дана матрица $X$ размера $m$ на $n$. Данную матрицу необходимо разделить на две $X_1$ и $X_2$, количество строк в первой $j$, во второй $k=m-j$ соответственно. Множества строк $j$ и $k$ не пересекаются.

Пусть матрица $Z$ имеет размерность $1$ на $n$. Формула для каждого элемента $z_i$, $(i=1:n)$ будет следующей:

$z_i = \frac{\underset{j}{\sum} x^j_i}{\underset{k}{\sum} x^k_i}$, т.е. верхняя сумма, например, берется по всем элементам матрицы $X_1$ в $i$-ом столбце.

Нужно подобрать $j$ и $k$ таким образом, чтобы выборочная дисперсия была минимальна: $D(Z) \to \min$

Сейчас пытаюсь привести это все к какой-нибудь задаче оптимизации. Буду признателен за любую возможную помощь. Перебор работает пока $m$ или $j$ невелики.

 Профиль  
                  
 
 Re: Операции с матрицами
Сообщение21.05.2015, 12:41 
Заслуженный участник
Аватара пользователя


18/05/06
13288
с Территории
Скорее всего, она и есть полнопереборная. Но может быть, найдутся какие-нибудь хорошие эвристики, дающие разумное приближение.

 Профиль  
                  
 
 Re: Операции с матрицами
Сообщение21.05.2015, 19:29 
Заслуженный участник


14/03/10
867
Aarnikotka в сообщении #1018150 писал(а):
Возникла следующая задача из реальной жизни, алгоритм решения для которой пока подобрать не удалось.
Хорошего точного решения придумать и не удастся, если, конечно Вы запрещаете случаи $j=0$ и $k=0$ :twisted: Действительно, Ваша задача остается NP-сложной, даже если Вас интересуют только матрицы из нулей и единиц и устраивает только случай $DZ=0$. Что касается приближенных алгоритмов, вряд ли они кем-то разрабатывались специально для такой задачи; поэтому можно попробовать свести ее к какой-нибудь известной задаче и применить известные для нее алгоритмы. Впрочем, никаких иллюзий по поводу скорости таких алгоритмов и качества приближения быть не должно :lol:

 Профиль  
                  
 
 Re: Операции с матрицами
Сообщение22.05.2015, 10:01 


10/06/12
33
Спасибо за комментарии! А если посмотреть на эту задачу под другим углом: делить матрицы по принципу корреляции строк (сумм нескольких строк)? Так как данные из реальной жизни, при суммирование строк корреляция между суммами достигает значений более 0,9 (закон больших чисел?). Единственная проблема - даже с такой корреляцией коэффициент вариации может быть высоким (или, наоборот, низким). Все зависит, судя по всему, от коэффициента смещения в уравнении $y=a x + b$, где $x$ это одна сумма, а $y$ - другая. Возможно ли как-то устремить коэффициент смещения к нулю при суммировании строк по коэффициенту корреляции (Пирсона)?

-- 22.05.2015, 10:06 --

Или же в этом случае в регрессионной модели $y=a x + b_{\min}+\varepsilon$ все наши махинации с уменьшением $b$ уйдут в увеличение дисперсии $\varepsilon$? :roll:

 Профиль  
                  
 
 Re: Операции с матрицами
Сообщение22.05.2015, 10:14 
Заслуженный участник
Аватара пользователя


18/05/06
13288
с Территории
Ваш вопрос сродни тому, на каком километре дороги тут будет заправка или Макдональдс. А по дороге-то и не ездил никто сроду; это вообще не дорога, это направление.
Пробовать надо.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 5 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group