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

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). 

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

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

Answer 1

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

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

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

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

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

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