Найти "самую большую" плотную субматрицу в большой разреженной матрице

Question

Учитывая большую разреженную матрицу (скажем, 10k + на 1M +), мне нужно найти подмножество, не обязательно непрерывное, строк и столбцов, которые образуют плотную матрицу (все ненулевые элементы). Я хочу, чтобы эта подматрица была как можно большей (не самая большая сумма, а наибольшее количество элементов) в рамках некоторых ограничений соотношения сторон.

Есть ли какие-либо известные точные или апроксаматные решения этой проблемы?

Быстрое сканирование в Google, похоже, дает много близких, но не совсем результатов. Какие условия мне нужно искать?

---

изменить: Просто чтобы уточнить; подматрица не обязательно должна быть непрерывной . На самом деле порядок строк и столбцов совершенно произвольный, поэтому смежность совершенно не имеет значения.

---

Мысль, основанная на идее Чада Окере

1. Порядок строк от наибольшего до наименьшего (не обязательно, но может помочь перфект)
2. Выберите две строки, которые имеют "большое" перекрытие
3. Добавьте все остальные строки, которые не уменьшат перекрытие
4. Запись, установленная
5. Добавьте любой ряд, уменьшающий перекрытие наименьшим
6. Повторяйте на # 3, пока результат не станет маленьким
7. Начните сначала с # 2 с другой стартовой парой
8. Продолжайте, пока не решите, что результат достаточно хорош

Answer 1

Полагаю, вы хотите что-то подобное. У вас есть матрица, как

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.

Вы будете выполнять итерации, пока не найдете больше новых строк и столбцов для добавления. Это сделало бы вас слишком локальным минимумом. Вы можете сохранить результат и начать заново с другой начальной точки (возможно, той, которая не вписывается в ваше текущее решение).

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

Это, очевидно, заняло бы много времени, но я не знаю, сможете ли вы сделать это быстрее.

Answer 2

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

Итак, после осознания того, что это сложная задача для NP (путем сокращения до MAX-CLIQUE), я решил придумать эвристику, которая до сих пор хорошо работала для меня:

Если задана N x M двоичная / логическая матрица, найдите большую плотную подматрицу:

Часть I : Генерация разумных подматриц-кандидатов

1. Рассмотрим каждую из N строк как M -мерный двоичный вектор, v_i , где i = 1 до N
2. Вычислить матрицу расстояний для N векторов, используя расстояние Хэмминга
3. Использование алгоритма UPGMA (метод невзвешенной пары с средним арифметическим) для кластеризации векторов

Первоначально каждый из v_i векторов представляет собой одноэлементный кластер. Шаг 3 выше (кластеризация) дает порядок, в котором векторы должны быть объединены в подматрицы. Таким образом, каждый внутренний узел в иерархическом дереве кластеризации является подматрицей-кандидатом.

Часть II : Подматрицы кандидатов и рангов

1. Для каждой подматрицы вычислите D , количество элементов в плотном подмножестве векторов для подматрицы, исключив любой столбец с одним или несколькими нулями.
2. Выберите подматрицу, которая максимизирует D

У меня также были некоторые соображения относительно минимального количества строк, которые нужно было сохранить из исходной полной матрицы, и я бы отбросил любые подходящие подматрицы, которые не удовлетворяли этому критерию, прежде чем выбирать подматрицу с макс. * значение.

Answer 3

Это проблема Netflix ?

MATLAB или некоторые другие библиотеки разреженных матриц могут иметь способы справиться с этим.

Ты намереваешься написать свой собственный?

Может быть, вам поможет одномерный подход для каждой строки. Алгоритм может выглядеть так:

1. Зацикливание в каждом ряду
2. Найти индекс первого ненулевого элемента
3. Найти индекс ненулевого элемента строки с наибольшим интервалом между ненулевыми столбцами в каждой строке и сохранить оба.
4. Сортировка строк по наибольшему и наименьшему промежутку между ненулевыми столбцами.

С этого момента я начинаю размыты (извините, не разработчик алгоритмов). Я бы попробовал зацикливаться на каждой строке, выравнивая индексы начальной точки, ища максимально ненулевой прогон индексов столбцов, который мог бы.

Вы не указываете, должна ли плотная матрица быть квадратной. Я предполагаю, что нет.

Я не знаю, насколько это эффективно или каково было бы его поведение Big-O. Но для начала это метод грубой силы.

Answer 4

EDIT. Это НЕ то же самое, что проблема ниже .. Мой плохой ...

Но, исходя из последнего комментария ниже, он может быть эквивалентен следующему:

1. Найдите самую дальнюю вертикально разделенную пару нулевых точек, между которыми нет нулевой точки.
2. Найдите самую дальнюю горизонтально разделенную пару нулевых точек, между которыми нет нулей?

3. Тогда горизонтальная область, которую вы ищете, это прямоугольник, который подходит между этими двумя парами точек?

   Эта точная проблема обсуждается в книге Джона Бентли под названием «Программирование жемчуга», и, насколько я помню, хотя есть решение в одном измерении, нет простого ответа для 2-го или более высокого уровня. пространственные варианты ...

Задача 1 = D состоит в том, чтобы найти наибольшую сумму непрерывного подмножества набора чисел:

итерация по элементам, отслеживание промежуточного итога по определенному предыдущему элементу и максимальный промежуточный итог, видимый до сих пор (и начальный и конечный элемент, который его сгенерировал) ... На каждом элементе, если промежуточный итог maxrunning больше, чем макс. общее количество, видимое до сих пор, макс. видимое до сих пор и значение endelemnt сбрасываются ... Если максимальный промежуточный итог падает ниже нуля, начальный элемент сбрасывается на текущий элемент, а промежуточный итог сбрасывается в ноль ...

2-D проблема возникла из-за попытки сгенерировать алгоритм обработки визуального изображения, который пытался найти в потоке значений яркости, представляющих пиксели в 2-цветном изображении, найти «самую яркую» прямоугольную область в пределах образ. т.е. найти содержащуюся 2-D субматрицу с наибольшей суммой значений яркости, где «Яркость» измерялась по разнице между значением яркости пикселя и общей средней яркостью всего изображения (так много элементов имели отрицательные значения)

РЕДАКТИРОВАТЬ: Чтобы найти 1-D решение, я выкопал свою копию 2-го издания этой книги, и в нем Джон Бентли говорит: «2-D версия остается нерешенной, так как это издание выходит в печать ... "который был в 1999 году.