Многомерная кластеризация логических значений

Вот мой сценарий проблемы:

У меня есть несколько тысяч объектов. Каждый объект имеет 256 логических измерений (истинных или ложных). Я хочу найти такие кластеры, что

  1. Каждый кластер имеет минимальное количество истинных измерений (размерность кластера истинна, если и только если любой объект в этом кластере имеет рынок этого измерения как истинный).
  2. Общая сумма всех истинных измерений по всем кластерам минимальна.
  3. Каждый кластер не больше определенного предопределенного значения.

Оптимальность решения не требуется, однако алгоритм должен быть быстрым.

Как мне лучше всего подойти к этой проблеме? Есть ли алгоритм, который вы могли бы порекомендовать?

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


cluster-analysis multidimensional-array algorithm
person aZen    schedule 19.11.2012    source источник
comment
Означает ли пункт 1, что каждый кластер должен иметь по крайней мере некоторое фиксированное количество истинных измерений или что каждый кластер должен иметь как можно меньшее количество истинных измерений? Если у вас есть функциональная, но медленная реализация, возможно, вам следует предоставить небольшой пример с гораздо меньшими размерами.   -  person Patricia Shanahan    schedule 19.11.2012
comment
Это означает, что каждый кластер должен иметь как можно меньше истинных измерений. Я только что заметил, что это может быть немного избыточным. Всего 2 и 3 должно быть достаточно, чтобы определить проблему. Перебор в основном выглядит следующим образом: 1) Найти несгруппированный объект с наименьшими истинными измерениями и добавить в новый кластер (текущий кластер) 2) Найти наиболее похожий, не сгруппированный объект (в текущий кластер) и добавить. Повторяйте до тех пор, пока текущий кластер не будет заполнен 3) Перейти к 1), если есть еще не кластеризованные объекты   -  person aZen    schedule 19.11.2012
comment
Моя интуиция подсказывает, что вы должны начать с объектов с наиболее реальными размерами. После того, как вы поместите один из них в кластер, вы сможете добавить множество других объектов бесплатно, потому что их истинные размеры являются подмножеством размеров первого объекта. Объекты с малым количеством истинных размеров можно разместить практически везде, где есть место.   -  person Patricia Shanahan    schedule 19.11.2012

Ответы (2)


arrow_upward
2
arrow_downward

Вы можете написать это как линейную программу со смешанными целыми числами (MILP)< /сильный>:

У вас есть фиксированное количество кластеров и объектов.
Каждый кластер может иметь не более 256 истинных размеров.
Параметр D_{k,j} равно 1, если измерение i истинно в объекте k.

У вас есть следующие переменные:

  1. d_{i,j}— двоичная переменная, равная 1, если измерение j является истинным измерением кластера i.
  2. o_{i,k}— это двоичная переменная, которая имеет значение true, если объект k находится в кластере i.

У вас есть следующие ограничения:

  1. Каждый объект может находиться только в одном кластере
  2. Измерение истинно в кластере, если оно истинно во всех объектах внутри кластера.
  3. Каждый кластер может содержать только M объектов

Второе ограничение сложное, потому что оно не кажется линейным, но на самом деле его можно написать линейным. Ограничения можно записать так:

  1. C1для всех k
  2. C2для всех i и j
  3. C3для всех

Целевая функция может быть суммой всех d_{i,j}, поэтому вы минимизируете общую сумму всех истинных измерений по всем кластерам.

Позвольте мне объяснить второе ограничение: справа вы вычисляете количество элементов внутри кластера i за вычетом количества объектов, размерность j которых равна единице. Это равно нулю, если все объекты имеют размерность j, или чему-то положительному, если нет.

Если это оценивается как ноль, то d_{i,j}должен равняться один, чтобы избежать нарушения ограничения. Если нет, d_{i,j}может быть любым (нулем или единицей). Это работает, потому что d_{i,j}появится в целевой функции, что означает, что когда программа имеет выбор между нулем или единицей, он выберет ноль.

После того, как вы напишете это, вы можете решить это с помощью коммерческого решателя (если он у вас есть, они дают бесплатные лицензии студентам, если вы один из них) или Coin-OR просто чтобы назвать один.

Напоминаем: решение MILP — это NP-полная задача.

person alestanis    schedule 19.11.2012
comment
Кажется, есть недоразумение с тем, что размерность истинна в кластере, если она верна для всех объектов внутри кластера. Это должно быть. Измерение ложно в кластере, если оно ложно во всех объектах внутри кластера. Но в целом это очень хорошая идея. Благодарю вас! Я отмечу его принятым, как только у меня будет время проверить! - person aZen; 21.11.2012
comment
В этом случае вторым ограничением должно быть d_i,j ‹ сумма o_i,k*D_k,j / N, где N — количество объектов. Эта сумма всегда будет между нулем и единицей. Если один из D_k,j равен единице, то он также заставит d_i,j быть равным единице. - person alestanis; 21.11.2012
comment
Я разработал (теоретическое) решение, используя Simplex. К сожалению, он имеет ~371 000 переменных и ~1 300 000 строк. Я думаю, что это многовато для любого решателя. - person aZen; 10.02.2013
comment
@aZen, который очень очень большой, особенно если у вас есть двоичные переменные :( вы пытались решить несложную задачу, т.е. когда двоичные переменные рассматриваются как непрерывные? есть несколько очень хороших решателей, вы должны попробовать их. - person alestanis; 10.02.2013
comment
Опубликовал свое решение @alestanis. Я не думаю, что есть способ сделать это возможным. У вас есть предложение, как эффективно аппроксимировать его? Счетчик истинных размеров-разностей между объектами является метрикой, поэтому я думал сгруппировать объекты в соответствии с этим. - person aZen; 11.02.2013

arrow_upward
0
arrow_downward

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

Ограничения, которые я придумал, следующие:

1) Каждый объект находится ровно в одном кластере

2) Каждый кластер имеет не более M (постоянных) объектов.

3) Измерение кластера истинно тогда и только тогда, когда хотя бы один из объектов в этом кластере имеет это измерение как истинное.

Я объясню, как теперь применяются ограничения:

Пусть имеется n объектов и k кластеров. Считаем сумму (в дальнейшем это одна строка)

x11 + x21 + x31< /sup> + ... + xn1 + d11 + d2< /sub>1 + d31 + ... + dn1 +

x12 + x22 + x32< /sup> + ... + xn2 + d12 + d2< /sub>2 + d32 + ... + dn2 +

...

x1k + x2k + x3k< /sup> + ... + xnk + d1k + d2< /sub>k + d3k + ... + dnk

куда

xac истинно, если и только если объект a является целым кластером c

dbc истинно, если и только если измерение b в кластере c истинно

Поскольку всегда лучше (или, по крайней мере, никогда не вредно) объединять объекты в кластеры, мы знаем, что число кластеров равно ceil(объекты, деленные на M). Для простоты я сейчас опущу переменные и напишу только коэффициенты.

1) Каждый объект находится ровно в одном кластере

10...0 0...0 10...0 0...0 10...0 0...0 ... 10...0 0...0 = 1

010...0 0...0 010...0 0...0 010...0 0...0 ... 010...0 0...0 = 1

...

0..01 0...0 0...01 0...0 0...01 0...0 ... 0...01 0...0 = 1

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

2) Каждый кластер содержит не более M (постоянных) объектов.

11...1 0...0 0...0 0...0 0...0 0...0 ... 0...0 0...0 <= M

0...0 0...0 11...1 0...0 0...0 0...0 ... 0...0 0...0 <= M

...

0...0 0...0 0...0 0...0 0...0 0...0 ... 11...1 0...0 <= M

Сумма объектов не больше M. Это ограничение должно быть очевидным.

Теперь начинается сложная часть:

3) Измерение кластера истинно, если хотя бы для одного из объектов в этом кластере это измерение задано как истинное.

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

0..010...0 -10...0 0...0 0...0 ... 0...0 0...0 <= 0

где 1 означает, что это измерение для этого объекта (в этом кластере) имеет значение true, а -1 идентифицирует измерение (в данном случае первое). Если объект установлен в этом кластере, размерность для этого кластера должна быть 1 (1*1 -1*d ‹= 0), если он не установлен, размерность также может быть нулевой (0*1 - 1*d ‹ = 0).

Для второго измерения в первом кластере это будет выглядеть так:

0..010...0 0-10...0 0...0 0...0 ... 0...0 0...0 <= 0

и для последнего кластера и последнего измерения, подобного этому

0...0 0...0 0...0 0...0 ... 0..010..0 0...0-1 <= 0

Теперь мы можем просто минимизировать сумму xac, и все готово.

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

Теперь проблема в следующем: я работаю с 70 кластерами, 3000 объектов и 2300 измерений. Используя описанный выше подход, это приводит к 371000 переменных (кластеры * объекты + кластеры * измерения) и 1292095 строк (оценка строк как объектов + кластер + измерения * журнал (объекты) * кластеры)

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

Спасибо :)

person aZen    schedule 10.02.2013