Разметка множества объектов

Question

Я пытаюсь разделить набор из 100 объектов на два подмножества.Каждый объект имеет набор числовых атрибутов.

Текущая целевая функция состоит в том, чтобы минимизировать среднее значение разницы между средними значениями атрибутов каждого набора.Другими словами, мы сначала вычисляем среднее значение каждого атрибута в каждом наборе, затем берем разницу каждого атрибута между наборами и, наконец, берем среднее значение этих различий.

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

Решения, которые я придумаю, довольно просты:

• Используйте жадный алгоритм для итеративного добавленияновый объект для одного из подмножеств
• То же, что и выше, но разрешается возвратный контроль для перебалансировки подмножеств после каждого нового распределения
• Начать с полностью заполненных наборов (на основе случайного назначения), а затем выполнитьжадный поиск для перемещения объекта из одного набора в другой, если он понижает целевую функцию.

Существуют ли более точные методы, чем эти;то есть это приведет к более близко подобранным наборам, но не займет очень много времени для оценки?

Answer 1

Если я правильно понимаю вашу целевую функцию, похоже, вы можете рассчитать стоимость для каждого объекта напрямую.Сделайте один проход данных, чтобы вычислить среднее значение каждого атрибута.
Затем cost(obj) := sum( [ obj.attr[i]-mean[i] for i in len(obj.attr) ])

Это сводит проблему к проблеме разбиения , которая хорошо изучена.

Возможно, вам придется нормализовать каждое значение в процентах от наблюдаемого диапазона, чтобы предотвратить доминирование атрибута с широким диапазоном при принятии решения.Диапазон может быть найден в том же проходе, что и среднее значение.

Answer 2

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

Если вы хотите что-то доказать, то в конечном итоге ключом может быть размерность ваших атрибутов:

Если у вас есть только один числовой атрибут, решение будет простым.Если у вас много атрибутов и достаточно равномерное распределение, не разделение может быть «хорошим».Попытайтесь разделить гиперкубы на две половины, используя свою метрику, чтобы получить представление.

В других случаях может быть геометрическое решение, если проецировать точки на одно измерение, сохраняя расстояния как можно лучше.Одним из подходов для этого является многомерное масштабирование (MDS).