Есть набор из 65000 множеств, в каждом множестве от 1 до 35000 элементов (элементы — 16-битные целые числа), причем распределение размеров весьма неравномерное: среднее число элементов около 50, медианное — 13, т.е. большая часть множеств имеет менее 20 элементов, но есть и содержащие десятки тысяч. Мне нужно уменьшить этот набор путем объединения "похожих" множеств так, чтобы минимизировать сумму размеров множеств, но с таким ограничением: объединение множеств A,В,С... в некое Х возможно лишь тогда, когда размер получающегося Х не более чем в К раз (скажем, К=4) больше, чем размер каждого из А,В,С... Т.е., например, нельзя объединять множество из 10 элементов с множеством из 100. Объединять непересекающиеся множества нет смысла, а чем сильнее множества пересекаются ("похожи"), тем выгоднее их объединить.
Самое оптимальное решение не требуется, можно предлагать эвристики. Наивные переборные решения многовато операций и/или памяти требуют. Желательно уложиться в 2 гига памяти и час процессорного времени.
Здравствуйте, D. Mon, Вы писали:
> Есть набор из 65000 множеств, в каждом множестве от 1 до 35000 элементов > (элементы — 16-битные целые числа), причем распределение размеров весьма > неравномерное: среднее число элементов около 50, медианное — 13, т.е. > большая часть множеств имеет менее 20 элементов, но есть и содержащие > десятки тысяч. Мне нужно уменьшить этот набор путем объединения > "похожих" множеств так,
Я бы сначала определил меру похожести множеств, а затем какой алгоритм кластеризации (их море и разных) заюзал. А после, как по кластерам распихалось, уже объединял бы в кластерах.
Здравствуйте, Аноним, Вы писали:
А>Я бы сначала определил меру похожести множеств, а затем какой алгоритм кластеризации (их море и разных) заюзал. А после, как по кластерам распихалось, уже объединял бы в кластерах.
А при этом можно обойтись без вычисления этой меры для всех пар множеств? А то это уже больно много операций получается.
Здравствуйте, D. Mon, Вы писали:
DM>Есть набор из 65000 множеств, в каждом множестве от 1 до 35000 элементов (элементы — 16-битные целые числа), причем распределение размеров весьма неравномерное: среднее число элементов около 50, медианное — 13, т.е. большая часть множеств имеет менее 20 элементов, но есть и содержащие десятки тысяч. Мне нужно уменьшить этот набор путем объединения "похожих" множеств так, чтобы минимизировать сумму размеров множеств, но с таким ограничением: объединение множеств A,В,С... в некое Х возможно лишь тогда, когда размер получающегося Х не более чем в К раз (скажем, К=4) больше, чем размер каждого из А,В,С... Т.е., например, нельзя объединять множество из 10 элементов с множеством из 100. Объединять непересекающиеся множества нет смысла, а чем сильнее множества пересекаются ("похожи"), тем выгоднее их объединить.
DM>Самое оптимальное решение не требуется, можно предлагать эвристики. Наивные переборные решения многовато операций и/или памяти требуют. Желательно уложиться в 2 гига памяти и час процессорного времени.
На каждое множество выделяем 1024х8 байтовых значений — это покроет интервал 16-битных чисел, при этом памяти уйдёт полгига.
Потом проставляем битики для каждого встреченного числа
Потом по OR быстро объединяем множества, и считаем число получившихся бит (== размер объединённого мн-ва), причем из сравнения сразу можно исключить
а) отличающиеся по размеру
б) где максимальный элемент одного множества < минимального элемента другого (т.е. гарантированно нет пересечений)
Число размер получившегося множества увеличился в допустимых пределах, то объединяем.
Подсчет битов тоже можно считать быстро, разбивать 8 байтовые числа на четыре 2х байтовых, а для двух байтовых заранее посчитать массив, где по индексу массива хранится число бит соответсвующих этому индексу
Здравствуйте, D. Mon, Вы писали:
DM>Есть набор из 65000 множеств, в каждом множестве от 1 до 35000 элементов (элементы — 16-битные целые числа), причем распределение размеров весьма неравномерное: среднее число элементов около 50, медианное — 13, т.е. большая часть множеств имеет менее 20 элементов, но есть и содержащие десятки тысяч. Мне нужно уменьшить этот набор путем объединения "похожих" множеств так, чтобы минимизировать сумму размеров множеств, но с таким ограничением: объединение множеств A,В,С... в некое Х возможно лишь тогда, когда размер получающегося Х не более чем в К раз (скажем, К=4) больше, чем размер каждого из А,В,С... Т.е., например, нельзя объединять множество из 10 элементов с множеством из 100. Объединять непересекающиеся множества нет смысла, а чем сильнее множества пересекаются ("похожи"), тем выгоднее их объединить.
Если бы знать природу этих множеств, то можно было бы ориентироваться на предметную область.
А так...
Ну, например, отсортировать множества по размеру.
Всё равно объединять можно только множества, отличающиеся по размеру не более чем в K раз.
Это мы уже сразу отбросим заведомо неинтересные сочетания, — будем скользить по списку множеств окном, возможно, переменной ширины и проверять сочетания только внутри окна.
Далее, постеризуем элементы до K.
Если два постеризованных множества одинаковы, то их прообразы отличаются не более чем в К раз.
Для этого считаем хеши и группируем постеризованные множества по равенству хешей, перед тем, как тщательно проверять.
Эту процедуру можно сделать несколько раз с разными постеризациями (отбрасывая нижние биты, верхние биты, может быть, средние биты), чтобы уменьшить число ложных отказов.
Очень надеюсь, что тем самым мы быстро разберёмся с основной частью множеств, — с теми, которые до 50±? элементов.
A>Потом по OR быстро объединяем множества, и считаем число получившихся бит (== размер объединённого мн-ва), причем из сравнения сразу можно исключить A>а) отличающиеся по размеру A>б) где максимальный элемент одного множества < минимального элемента другого (т.е. гарантированно нет пересечений)
Как дополнительную меру каждое множество можно кодировать в виде 64 битного числа, где один бит означает наличие числа в интервале в 1024 чисел (0-1023, 1024-2047 и т.д.)
Таким образом можно очень быстро через AND двух 64битных чисел проверять множества на наличие _возможных_ совпадений и исключать из сравнения те, где совпадений гарантированно нет
2/27/2014 4:41 PM, D. Mon пишет:
> А при этом можно обойтись без вычисления этой меры для всех пар > множеств? А то это уже больно много операций получается.
Да. Тут фактически мы строим матрицу похожести, а потом еще
кластеризация и объединение. По сути, для полной обработки всех множеств
ты никуда не денешься от вычисления ~n(n-1)/2 попарных расстояний (O(n^2)).
А вот без такой матрицы надо долго думать и смотреть реальные
распределения твоих множеств. Возможно можно просто брать некие выборки
(последовательно, стохастически равномерно или в соответствие с каким
хитрым распределением — Монте-Карло подход, по сути) и по ним делать
попытки объединения, определив заранее некий порог для меры.
Можно еще попробовать упорядочить множества по мощности и разбить на
группы и затем уже в этих группах проводить объединения.
Это всё идеи. Может чем тебе и помогут.
В общем, если это разовая или очень редкая задача, то я бы не
заморачивался и пошел бы через матрицу похожести и кластеризацию.
Если же надо чтобы работало быстро и часто крутился бы последовательным
объединением по порогу. Поступает множество, сравниваем с имеющимися и в
зависимости от порога или новый кластер или объединяем с имеющимися.
Качество "упаковки", в этом случае будет понятно хуже.
Ваш Вжик
З.Ы. Написано достаточно сумбурно, но чтобы разработать полноценный
алгоритм и описать его прилично — это не день и не два работы. Ну и
многое зависит от конкретики задачи.
Здравствуйте, avpavlov, Вы писали:
A>Потом по OR быстро объединяем множества, и считаем число получившихся бит (== размер объединённого мн-ва), причем из сравнения сразу можно исключить A>а) отличающиеся по размеру A>б) где максимальный элемент одного множества < минимального элемента другого (т.е. гарантированно нет пересечений)
Объединяем каждое с каждым? Это 2 миллиарда пар по 8+8 КБ, триллионы операций. Слишком долго.
Здравствуйте, Кодт, Вы писали:
К>Если бы знать природу этих множеств, то можно было бы ориентироваться на предметную область.
Если интересно, вот тут прореженные в 8 раз данные: http://stuff.thedeemon.com/lj/sample.json.gz (127 КБ)
К>А так... К>Ну, например, отсортировать множества по размеру. К>Всё равно объединять можно только множества, отличающиеся по размеру не более чем в K раз.
Разумно, но там у распределения хвост очень длинный, участки близких по размеру множеств там получаются весьма широкие.
К>Далее, постеризуем элементы до K. К>Если два постеризованных множества одинаковы, то их прообразы отличаются не более чем в К раз. К>Для этого считаем хеши и группируем постеризованные множества по равенству хешей, перед тем, как тщательно проверять.
Здравствуйте, Vzhyk, Вы писали:
>> А при этом можно обойтись без вычисления этой меры для всех пар >> множеств? А то это уже больно много операций получается.
V>Да. Тут фактически мы строим матрицу похожести, а потом еще V>кластеризация и объединение. По сути, для полной обработки всех множеств V>ты никуда не денешься от вычисления ~n(n-1)/2 попарных расстояний (O(n^2)).
Тогда это нет, а не да. Шибко долго такую матрицу строить. Да и хранить ее негде, если вдруг надо хранить. (2 мрд значений)
V>Если же надо чтобы работало быстро и часто крутился бы последовательным V>объединением по порогу. Поступает множество, сравниваем с имеющимися и в V>зависимости от порога или новый кластер или объединяем с имеющимися. V>Качество "упаковки", в этом случае будет понятно хуже.
2/27/2014 6:06 PM, D. Mon пишет:
> Тогда это нет, а не да. Шибко долго такую матрицу строить. Да и хранить > ее негде, если вдруг надо хранить. (2 мрд значений)
Можно сделать блочный алгоритм в зависимости от памяти и количества
параллельных потоков обработки.
> Похоже на k-means или DBSCAN, да. Спасибо.
Нет, не похоже.
Эти методы как раз и требуют матрицу <близости, похожести, расстояний,
... по разному называют, в зависимости от меры>.
З.Ы. Но я тебя не убеждаю, просто предлагаю варианты.
Здравствуйте, D. Mon, Вы писали:
DM>Самое оптимальное решение не требуется, можно предлагать эвристики. Наивные переборные решения многовато операций и/или памяти требуют. Желательно уложиться в 2 гига памяти и час процессорного времени.
У меня приятель использовал Карту Коханнена для группировки биржевых данных по некоторым признакам с последующей визуализацией. Мне кажется задчи чем-то похожи.
DM>Объединяем каждое с каждым? Это 2 миллиарда пар по 8+8 КБ, триллионы операций. Слишком долго.
Кто-то тут вроде хотел в пределах часа?
Твой файл из 6800 записей обрабатывается у меня за 4 секунды.
Даже если записей будет на порядок больше, это будет 400 секунд.
При этом у меня 2 ядра, а если будет больше, то производительность линейная
Я с json не стал связываться, конвертнул в такой формат (первое число — ИД, а потом набор чисел)
Ещё я поменял меру похожести, потому что твой алгоритм больно много совпадений давал. было
... когда размер получающегося Х не более чем в К раз...
Стало
размер получающегося множества S <= A + B/4, где A < B
import java.io.BufferedReader;
import java.io.DataInputStream;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.BitSet;
import java.util.Collections;
import java.util.List;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.atomic.AtomicLong;
/**
* @author: Alexander Pavlov
* <p/>
* Date: 27/02/14 19:40
*/public class Test {
public static final int MAX_COUNT = 1024 * 64;
public static final int K = 4;
public static class S implements Comparable<S>{
private final int length;
private final int min;
private final int max;
private final long shortMap;
private final long [] fullMap;
private final String id;
public S(String id, int [] data) {
this.id = id;
BitSet bits = new BitSet(MAX_COUNT);
int m1=Integer.MAX_VALUE;
int m2=Integer.MIN_VALUE;
int q=0;
for (int i : data) {
bits.set(i);
if (m1 > i) m1=i;
if (m2 < i) m2=i;
q |= 1 << i/1024;
}
min=m1;
max=m2;
shortMap=q;
fullMap = new long [MAX_COUNT/64];
long [] bitsArr = bits.toLongArray();
System.arraycopy(bitsArr, 0, fullMap, 0, bitsArr.length);
length = data.length;
}
@Override
public int compareTo(S o) {
return length-o.length;
}
}
public static class Task implements Runnable {
private final S[] s;
private final int startIdx;
private final int batchSize;
private final AtomicLong compared;
private final AtomicLong similar;
public Task(S[] s, int startIdx, int batchSize, AtomicLong compared, AtomicLong similar) {
this.s = s;
this.startIdx = startIdx;
this.batchSize = batchSize;
this.compared = compared;
this.similar = similar;
}
@Override
public void run() {
int _similar=0;
int _compared=0;
try {
for (int c=0; c < batchSize && startIdx+c < s.length; c++) {
S base = s[startIdx+c];
for (int i=startIdx+c+1; i<s.length; i++) {
_compared++;
S other = s[i];
if (other.min > base.max || other.max < base.min || (other.shortMap&base.shortMap)==0) {
continue;
}
int mergedLength=0;
int stopAtLength = other.length + base.length / K;
for (int j=0; j<base.fullMap.length && mergedLength <= stopAtLength; j++) {
mergedLength += Long.bitCount(base.fullMap[j]|other.fullMap[j]);
}
if (mergedLength <= stopAtLength) {
_similar++;
// System.out.println(base.id + " is similar to "+other.id+" mergedLength="+mergedLength);
}
}
}
} catch (Exception ex) {
System.out.println(ex);
}
compared.addAndGet(_compared);
similar.addAndGet(_similar);
}
}
public static void main(String [] args) {
S [] s = readInput();
AtomicLong compared = new AtomicLong();
AtomicLong similar = new AtomicLong();
long started=System.currentTimeMillis();
ExecutorService pool = Executors.newFixedThreadPool(Runtime.getRuntime().availableProcessors());
for (int i=0; i < s.length; i+=16) {
pool.execute(new Task(s, i, Math.min(16, s.length-i), compared, similar));
}
pool.shutdown();
try {
pool.awaitTermination(1, TimeUnit.MINUTES);
} catch (InterruptedException e) {
}
long totalMs=System.currentTimeMillis()-started;
System.out.println("Total time "+ TimeUnit.MILLISECONDS.toMillis(totalMs)+" ms, input length="+s.length+", similar="+similar.get()+", compared pairs="+compared.get());
}
private static S[] readInput() {
try {
List<S> result = new ArrayList<>(1024*64);
BufferedReader reader = new BufferedReader(new InputStreamReader(Test.class.getResourceAsStream("/input.txt")));
for (String line = reader.readLine(); line != null; line = reader.readLine()) {
String [] parts = line.split(",");
int [] data = new int [parts.length-1];
for (int i=1;i< parts.length; i++) {
data[i-1]=Integer.parseInt(parts[i]);
}
result.add(new S(parts[0], data));
}
Collections.sort(result);
return result.toArray(new S[result.size()]);
} catch (IOException e) {
throw new RuntimeException(e);
}
}
}
Total time 3597 ms, input length=6804, similar=3433200, compared pairs=23143806
A> for (int j=0; j<base.fullMap.length && mergedLength <= stopAtLength; j++) { A> mergedLength += Long.bitCount(base.fullMap[j]|other.fullMap[j]); A> }
Это место можно ещё улучшить, если сначала проверять бит в quickMap, что там не нули, это позволит пропускать 16 элементов массива без проверки.
Здравствуйте, avpavlov, Вы писали:
A>> for (int j=0; j<base.fullMap.length && mergedLength <= stopAtLength; j++) { A>> mergedLength += Long.bitCount(base.fullMap[j]|other.fullMap[j]); A>> }
A>Это место можно ещё улучшить, если сначала проверять бит в quickMap, что там не нули, это позволит пропускать 16 элементов массива без проверки.
Здравствуйте, avpavlov, Вы писали:
A>>> for (int j=0; j<base.fullMap.length && mergedLength <= stopAtLength; j++) { A>>> mergedLength += Long.bitCount(base.fullMap[j]|other.fullMap[j]); A>>Это место можно ещё улучшить, если сначала проверять бит в quickMap, что там не нули, это позволит пропускать 16 элементов массива без проверки. A>Что ускоряет ещё в 3 раза (ну почти )
Учитывая, что большинство множеств в этом наборе имеют менее 5 элементов и они уже отсортированы, этот цикл можно выбросить и сделать просто один проход по паре множеств (a-ля mergesort).
Но ведь это только начало. Одна такая итерация покажет, какие у множеств есть "похожие". Но если есть десяток множеств, попарно похожих друг на друга, мы не можем объединить их все в одно, надо еще выбрать какие из них объединять.
Вот за демонстрацию того, что сравнение границ и уменьшенных битсетов позволяет так сильно ускорить перебор, спасибо. Обнадеживает.
Здравствуйте, D. Mon, Вы писали:
DM>Здравствуйте, Аноним, Вы писали:
А>>Я бы сначала определил меру похожести множеств, а затем какой алгоритм кластеризации (их море и разных) заюзал. А после, как по кластерам распихалось, уже объединял бы в кластерах.
DM>А при этом можно обойтись без вычисления этой меры для всех пар множеств? А то это уже больно много операций получается.
LSH идеально подойдет для такой задачи, можете воспользуоваться уже существующими реализациями.
Просто большую часть множеств небольшого размера сравниваете с помощью хешей , LSH не гарантирует попадания , но статистически дает очень хороший результат на поиск похожих соседей.
Остается только подумать как организовывать множества на вход (отсортировывать, заполнять нулями те что не дотянули по размеру и т.д.)
Здравствуйте, D. Mon, Вы писали:
DM>Самое оптимальное решение не требуется, можно предлагать эвристики. Наивные переборные решения многовато операций и/или памяти требуют. Желательно уложиться в 2 гига памяти и час процессорного времени.
Какой подход в итоге выбрал? Удалось получить желаемый результат?
Здравствуйте, Kernan, Вы писали:
K>Какой подход в итоге выбрал? Удалось получить желаемый результат?
Благодаря подсказанным avpavlov оптимизациям (сделал для каждого множества min, max и миникарту из 128 бит, с их помощью быстро отсекал заведомо непересекающиеся множества), получилось сравнить попарно все потенциально пересекающиеся мн-ва. При каждом сравнении вычислялась оценка выигрыша от возможного объединения, для каждого мн-ва запоминались до 100 лучших вариантов. Получился ориентированный граф из 65к вершин и до 100 граней из каждой вершины, который, с учетом симметрии оценочной функции, потом превращался в неориентированный с до 200 граней на вершину, у каждой грани свой "вес" — оценка выигрыша от объединения. В этом графе жадным образом (навроде градиентного спуска) искались самые выгодные грани (не соприкасающиеся), и множества на их концах объединялись. Потом весь процесс повторялся, пока не устаканится: с каждой итерацией число таких пар множеств, которые выгодно объединить, быстро падало. Итераций потребовалось всего несколько штук, все посчиталось довольно быстро (точно не помню, но заметно меньше часа).
Перекуём баги на фичи!
)
