Я ищу эффективный алгоритм для идентификации блочной структуры в матрице с множеством 0 записей.
Например, матрица 6 × 7
0.0975 0.9575 0 0 0 0 0
0.2785 0.9649 0 0 0 0 0
0.5469 0.1576 0 0 0 0 0
0 0 0.9706 0.9572 0 0 0
0 0 0 0 0.8235 0.3171 0.0344
0 0 0 0 0.6948 0.9502 0.4387
состоит из трехблоки размеров 3 × 2, 1 × 2 и 2 × 3 соответственно.
Блок определяется набором строк и набором столбцов.Блочная структура характеризуется тем, что все записи, которые не принадлежат блоку, равны 0.Однако в блоках также могут быть записи с точным значением-0.
Тривиальное решение - всегда объявлять всю матрицу блоком;поэтому ищется решение, в котором число записей внутри блока должно быть как можно меньше.
Чтобы сделать вещи сложнее (или, может быть, проще?), блоки не должны быть смежными.Пермутированная версия вышеуказанной матрицы
0 0.9572 0 0 0 0 0.9706
0 0 0.0975 0 0 0.9575 0
0.4387 0 0 0.9502 0.6948 0 0
0.0344 0 0 0.3171 0.8235 0 0
0 0 0.2785 0 0 0.9649 0
0 0 0.5469 0 0 0.1576 0
, следовательно, также имеет трехблочную структуру, которая может быть описана как:
- блок, содержащий строки 3, 4 и столбцы1, 4, 5,
- блок, содержащий строку 1 и столбцы 2, 7,
- блок, содержащий строки 2, 5, 6 и столбцы 3, 6.
Решения, о которых я подумал:
Используйте алгоритм кластеризации на основе веса соединения.Однако матрица не обязательно должна быть симметричной или даже квадратной.Между определенной строкой и конкретным столбцом нет соответствия.
Первоначально определите блок, состоящий из одной (не 0) записи (описанной ее строкой и ее столбцом), смотритедля не-0 записей в своей строке и в своем столбце и добавлении соответствующих столбцов и строк увеличивайте таким образом итеративно до тех пор, пока не будут добавлены строки или столбцы;это идентифицирует один блок.Сделайте то же самое, начиная с записи, которая не содержится в блоке.Повторяйте до тех пор, пока не останется не 0 записей.Здесь я сомневаюсь, что этот алгоритм эффективно масштабируется до большой матрицы со многими блоками.
Я ищу алгоритм или другие идеи для алгоритма, а не для реализации.Тем не менее, реализация, например, в Matlab или Python будет приветствоваться.