Многомерный фильтр для устранения «плохих» предметов с большого стола?

Question

У меня есть большая таблица из N предметов с M (M> = 3) различными свойствами на предмет, Из этой таблицы я должен удалить все элементы, для которых в одной и той же таблице содержится элемент с одинаковыми или лучшими показателями по всем свойствам.

У меня есть алгоритм (python), который уже решает его, но он чувствителен к выходу и имеет наихудший случай прибл. O ((n² + n) / 2), когда в процессе не было удалено ни одного элемента. Это слишком медленно для моего проекта (где наборы данных из 100 000 элементов с 8 свойствами на элемент не являются редкостью), поэтому мне требуется что-то близкое к O (m * n log n) в худшем случае, но я не знаю, может ли эта проблема Быстро решаться.

Пример проблемы и ее решения:

  [higher value = better]
    Singing  Dancing  Acting
 A    10        20     10
 B    10        20     30
 C    30        20     10
 D    30        10     30
 E    10        30     20
 F    30        10     20
 G    20        30     10

Отклонить всех кандидатов, для которых есть кандидат, который выступает равным или лучше во всех дисциплинах.

Решение:
- А уволен, потому что B, C, E, G работают одинаково или лучше во всех дисциплинах.
- F уволен, потому что D действует одинаково или лучше во всех дисциплинах.

Существует ли алгоритм, который эффективно решает эту проблему, и что это такое?

Answer 1

Похоже, эта статья, http://flame.cs.dal.ca/~acosgaya/Research/skyline/on%20finding%20the%20maxima%20of%20a%20set%20of%20a%20vectors.pdf решает вашу проблему.

Выше ссылка не работает. Вот еще один: http://www.eecs.harvard.edu/~htk/publication/1975-jacm-kung-luccio-preparata.pdf

Answer 2

Общий ответ состоит в том, чтобы упорядочить записи в дереве и вести записи в каждом узле с максимальным значением в каждом столбце для записей, лежащих под этим узлом. Затем для каждой записи преследуйте ее вниз по дереву сверху, пока не узнаете, доминирует ли она или нет, используя примечания на каждом узле, чтобы пропустить все поддеревья, если это возможно. (К сожалению, вам, возможно, придется искать обоих потомков узла). Когда вы удаляете запись как доминирующую, вы можете обновить аннотации в узлах над ней - поскольку это не требует перебалансировки дерева, это должно быть дешево. Вы можете надеяться, по крайней мере, получить ускорение по сравнению с оригинальным кодом. Если моя память о многомерном поиске верна, вы можете надеяться перейти от N ^ 2 к N ^ (2-f), где f становится маленьким с увеличением числа измерений.

Одним из способов создания такого дерева является многократное разбиение групп записей по медиане одного измерения, циклически проходя измерения по каждому уровню дерева. Если для каждого такого разбиения вы используете медианный поиск по типу быстрой сортировки, вы можете ожидать, что для построения дерева потребуется время n log n. (KD-дерево)

Одним из факторов настройки является не полное разделение, а прекращение разделения, когда размер группы достигает N или меньше.

Answer 3

Здесь имеется частично упорядоченный набор, так что A <= B, если <em>все признаки A, имеют значения, меньшие или равные B, и A> = B, если all признаки A имеют значения, большие или равные B. Возможно, что! (A <= B || A> = B), в этом случае A и B "несопоставимы". Ваша задача состоит в том, чтобы исключить из набора те элементы, в которых преобладают другие элементы, например, удалить каждый A s.t. в множестве существует B, так что A В худшем случае все элементы несопоставимы, то есть вы ничего не можете устранить. Теперь давайте посмотрим на отношения несопоставимости. Предположим, что A! ~ B (несопоставимость) и B! ~ C. Возможно ли, что A и C все еще сравнимы? Да! Например, A может иметь черты {1,2,3}, B {2,1,5} и C {2,3,4}. Это означает, что несопоставимость не является «переходной» и, следовательно, вам отчасти не повезло; в общем, чтобы проверить, что все элементы несопоставимы, это займет O (N ^ 2) времени, насколько я понимаю.