Комбинации бинарных признаков (векторов)

Question

Исходными данными для субъекта является двоичная матрица m-на-n (допускаются только 0 и 1). m строки представляют наблюдения, n столбцы - особенности. Некоторые наблюдения отмечены как цели, которые должны быть отделены от остальных.

Хотя это похоже на типичную проблему NN, SVM и т. Д., Мне не нужно обобщать. Мне нужен эффективный алгоритм, чтобы найти как можно больше комбинаций столбцов (признаков), которые полностью отделяют цели от других наблюдений, то есть классифицируют.

Например:

    f1 f2 f3
o1   1  1  0
t1   1  0  1
o2   0  1  1

Здесь {f1, f3} - приемлемая комбинация, которая отделяет цель t1 от остальных (o1, o2) (кстати, {f2} НЕ является, так как по определению задачи функция ДОЛЖНА присутствовать в цели). Другими словами,

t1(f1) & t1(f3) = 1 and o1(f1) & o1(f3) = 0, o2(f1) & o2(f3) = 0
where '&' represents logical conjunction (AND).

М - около 100 000, n - 1000. В настоящее время данные упакованы в 128-битные слова вдоль m, и поиск оптимизирован с помощью sse4 и еще много чего. Тем не менее, получение этих комбинаций функций занимает слишком много времени. После 2 миллиардов обращений к процедуре спуска дерева она покрыла около 15% корневых узлов. И нашел около 8000 комбо, что является достойным результатом для моего конкретного приложения.

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

Answer 1

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

1) Построить дерево решений. Пометьте цели как A, а не цели как B, и пусть дерево принятия решений изучит категоризацию. В каждом узле выберите функцию так, чтобы функция P (цель | функция) и P (цель '| функция') была максимальной. (то есть как можно большее количество целей падает на положительную сторону, и как можно больше нецелевых объектов падает на отрицательную сторону)

2) Используйте жадный алгоритм. Начните с пустого набора и на каждом временном шаге добавляйте feauture, который убивает большинство нецелевых строк.

3) Используйте рандомизированный алгоритм. Начните с небольшого подмножества положительных характеристик некоторой цели, используйте набор в качестве начального числа для жадного алгоритма. Повторите много раз. Выберите лучшее решение. Жадный алгоритм будет быстрым, поэтому все будет в порядке.

4) Используйте генетический алгоритм. Создайте случайные начальные числа для жадного алгоритма, как в 3, чтобы сгенерировать хорошие решения, и перекрестно сгенерируйте их (побитовые и, вероятно,), чтобы сгенерировать новые потенциальные начальные числа. Помните лучшее решение. Держите хорошие решения как нынешнее население. Повторите для многих поколений.

Вам нужно будет быстро найти ответ «сколько из заданных строк имеют заданную функцию f», поэтому, вероятно, вам понадобятся специализированные структуры данных, возможно, с использованием BitArray для каждой функции.