Есть набор из 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 элементов массива без проверки.
Перекуём баги на фичи!
)