Найдите “самую большую” плотную подматрицу в большой разреженной матрице
https://stackoverflow.com/questions/1217355
-
10-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Учитывая большую разреженную матрицу (скажем, 10k + на 1M +), мне нужно найти подмножество, не обязательно непрерывное, строк и столбцов, которые образуют плотную матрицу (все ненулевые элементы).Я хочу, чтобы эта вложенная матрица была как можно больше (не самая большая сумма, но наибольшее количество элементов) в рамках некоторых ограничений соотношения сторон.
Существуют ли какие-либо известные точные или приблизительные решения этой проблемы?
Быстрое сканирование в Google, похоже, дает много близких, но не совсем точных результатов. На какие условия мне следует обратить внимание?
Редактировать: Просто чтобы уточнить;субматрица не обязательно быть непрерывным.На самом деле порядок строк и столбцов абсолютно произвольный, поэтому смежность совершенно не имеет значения.
Мысль, основанная на идее Чада Окере
- Упорядочивайте строки от наибольшего количества к наименьшему (не обязательно, но может помочь улучшить).
- Выберите две строки, которые имеют "большое" перекрытие
- Добавьте все остальные строки, которые не уменьшат перекрытие
- Запишите этот набор
- Добавьте любую строку, которая уменьшит перекрытие как можно меньше
- Повторяйте упражнение № 3 до тех пор, пока результат не станет небольшим.
- Начните сначала с #2 с другой стартовой парой
- Продолжайте до тех пор, пока не решите, что результат достаточно хорош
Решение
Я полагаю, вы хотите что-то подобное. У вас есть матрица, как
1100101
1110101
0100101
Вы хотите столбцы 1,2,5,7 и строки 1 и 2, верно? Эта подматрица будет 4х2 с 8 элементами. Или вы могли бы пойти с колонками 1,5,7 со строками 1,2,3, которые были бы матрицей 3x3.
Если вам нужен «приблизительный» метод, вы можете начать с одного ненулевого элемента, а затем найти другой ненулевой элемент и добавить его в список строк и столбцов. В какой-то момент вы натолкнетесь на ненулевой элемент, который, если бы в вашу коллекцию были добавлены строки и столбцы, ваша коллекция больше не была бы полностью ненулевой.
Таким образом, для вышеприведенной матрицы, если вы добавите 1,1 и 2,2, в вашей коллекции будут строки 1,2 и столбцы 1,2. Если вы попытаетесь добавить 3,7, это вызовет проблему, потому что 1,3 - ноль. Так что вы не могли бы добавить это. Вы можете добавить 2,5 и 2,7, хотя. Создание подматрицы 4x2.
Вы будете выполнять итерации, пока не найдете больше новых строк и столбцов для добавления. Это сделало бы вас слишком локальным минимумом. Вы можете сохранить результат и начать заново с другой начальной точки (возможно, той, которая не вписывается в ваше текущее решение).
Тогда просто остановись, когда через некоторое время ты не сможешь найти.
Это, очевидно, заняло бы много времени, но я не знаю, сможете ли вы сделать это быстрее.
Другие советы
Это проблема Netflix ?
MATLAB или некоторые другие библиотеки разреженных матриц могут иметь способы справиться с этим.
Собираетесь ли вы написать свой собственный?
Может быть, вам поможет одномерный подход для каждой строки. Алгоритм может выглядеть так:
<Ол>С этого момента я начинаю расплываться (извините, не дизайнер алгоритмов). Я бы попробовал циклически проходить по каждой строке, выстраивая индексы начальной точки в поисках максимально ненулевого индекса индексов столбцов, который мог бы.
Вы не указываете, должна ли плотная матрица быть квадратной. Я предполагаю, что нет.
Я не знаю, насколько это эффективно или как будет выглядеть поведение Big-O. Но для начала это метод грубой силы.
Редактировать.Это НЕ то же самое, что описанная ниже проблема..Я виноват...
Но, основываясь на последнем комментарии ниже, это может быть равносильно следующему:
- Найдите самую дальнюю по вертикали пару нулевых точек, между которыми нет нулевой точки.
- Найти самую дальнюю по горизонтали пару нулевых точек , разделенных нулями , между которыми нет нулей ?
Тогда горизонтальная область, которую вы ищете, - это прямоугольник, который помещается между этими двумя парами точек?
Именно эта проблема обсуждается в книге Джона Бентли "Жемчужины программирования", и, насколько я помню, хотя решение в одном измерении существует, простого ответа для двумерных или более высоких вариантов нет ...
Задача 1= D, по сути, состоит в том, чтобы найти наибольшую сумму непрерывного подмножества набора чисел:
выполните итерацию по элементам, отслеживая текущий итог по конкретному предыдущему элементу и максимальный промежуточный итог, виденный на данный момент (а также начальный и конечный элементы, которые его сгенерировали)...Для каждого элемента, если промежуточный итог maxrunning больше, чем максимальный итог, просмотренный на данный момент, значения max, просмотренный на данный момент, и endelemnt сбрасываются...Если максимальное общее количество хода становится ниже нуля, начальный элемент сбрасывается на текущий элемент, а общее количество хода сбрасывается на ноль...
Двумерная проблема возникла из-за попытки сгенерировать алгоритм обработки визуального изображения, который пытался найти в потоке значений яркости, представляющих пиксели в двухцветном изображении, "самую яркую" прямоугольную область внутри изображения.т.е. найдите содержащуюся в нем двумерную подматрицу с наибольшей суммой значений яркости, где "Яркость" измерялась разницей между значением яркости пикселя и общей средней яркостью всего изображения (так много элементов имели отрицательные значения)
Редактировать:Чтобы найти 1-D решение, я достал свой экземпляр 2-го издания этой книги, и в нем Джон Бентли говорит: "2-D версия остается нерешенной, поскольку это издание выходит в печать ...", что было в 1999 году.
Я знаю, что вы больше не работаете над этим, но я подумал, что у кого-то может возникнуть такой же вопрос, как у меня в будущем.
Итак, осознав, что это трудная задача для NP (путем сокращения до MAX-CLIQUE), я решил придумать эвристику, которая до сих пор хорошо работала для меня:
Учитывая, что N x M двоичная / логическая матрица, найдите большую плотную подматрицу:
Часть I . Создание разумных подматриц-кандидатов
<Ол>Изначально каждый из v_i векторов был одноэлементным кластером. Шаг 3 выше (кластеризация) дает порядок, в котором векторы должны быть объединены в подматрицы. Таким образом, каждый внутренний узел в иерархическом дереве кластеризации является подматрицей-кандидатом.
Часть II : подсчитайте и оцените подматрицы кандидатов
<Ол>У меня также были некоторые соображения относительно минимального количества строк, которые необходимо было сохранить из исходной полной матрицы, и я бы отбросил любые подходящие подматрицы, которые не удовлетворяли этому критерию, прежде чем выбирать подматрицу с max D значение.
