Определение столбцов и рядов кластеров с помощью линейного программирования

Question

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

Будет ли приемлем следующий подход?

• Иметь непрерывную переменную для каждой строкии столбец, который является «длиной», охватываемой всеми элементами в этой строке / столбце
• Имеется переменная для каждой «точки» (каждая черная точка), которая указывает, является ли она членом группы строк или столбцов
• Минимизировать сумму первых переменных

И есть ли лучший способ сделать это?Можно ли как-то сформулировать это как чисто проблему ограничения (т.е. без минимизации)?У меня правильная терминология?Спасибо!

Answer 1

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

Ваши баллы могут быть либо в «группе столбцов», либо в «группе строк». Из вашего предложения выше я понимаю, что вы знаете количество групп столбцов и групп строк заранее?

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

• Вертикальная ширина горизонтальных скоплений (c(H) = max (i,j in H) |yi - yj|)
• Горизонтальная ширина вертикальных скоплений (c(V) = max (i,j in V) |xi - xj|)

С H горизонтальным кластером, V вертикальным кластером, и общая стоимость составит:

c(H1) + c(H2) + ... + c(Hn) + c(V1) + c(V2) + ... + c(Vp)

с n (количество горизонтальных кластеров) и p (количество вертикальных кластеров), известных заранее. Это правильно?

Для горизонтальных групп вы говорите, что у вас не может быть "дырок". Я бы представил это как ограничение вашей проблемы, если вы можете определить размер отверстий. Например:

for each i in C, ( min (j in C) |xi - xj|  ) < r

обеспечит, чтобы у вас не было разрыва больше r в горизонтальном кластере C. Это то, что вы хотите? Является ли r фиксированным номером?

Это полная проблема, или у вас есть другие ограничения (минимальное количество баллов в группе или что-то в этом роде)?

Вам нужно точное минимальное решение, или «хорошего» решения будет достаточно?

Наконец, для технической части, так как ваш предыдущий пост был помечен 'python', а этот нет, вам нужно использовать python для решения модели?

Answer 2

Я наконец понял, как представить этот вопрос в линейной форме.В моем ответе есть полное описание на Есть ли хороший способ сделать этот тип майнинга? , но вот краткое резюме:

• Использовать бинарный код (0 /1) переменные для каждой соседней пары в строке, F_i.Это будет 1, когда пара находится в одной группе, и 0 в противном случае.

• Используйте константы S_i для описания количества пробелов между каждой парой точек.

• Минимизируйте сумму двух слагаемых:

  • Сумма 1 - F-i.Сведение к минимуму объединяет пары в большие группы.

  • Сумма F_i * S_i.Сведение к минимуму отделяет Париж с большими расстояниями.

Изменяя относительный вес двух слагаемых, вы можете изменить важность расстояния между горизонтальными группами.1034 * Это основано на асимметрии в задаче, в которой горизонтальные группы чувствительны к расстоянию, а вертикальные группы нет.