Большинство взаимно удаленных k элементов (кластеризация?) - PullRequest
Новая
       29

Большинство взаимно удаленных k элементов (кластеризация?)

4 голосов
/ 23 марта 2011

У меня простой вопрос машинного обучения:

У меня есть n (~ 110) элементов и матрица всех парных расстояний. Я хотел бы выбрать 10 элементов, которые наиболее далеко друг от друга. То есть я хочу 

Maximize:
  Choose 10 different elements.
  Return min distance over (all pairings within the 10).

Моя метрика расстояния симметрична и учитывает неравенство треугольника.

Какой алгоритм я могу использовать? Мой первый инстинкт - делать следующее:

  1. Сгруппировать n элементов в 20 кластеры.
  2. Замените каждый кластер только элемент этого кластера, который самый дальний от среднего элемента оригинал №.
  3. Используйте грубую силу, чтобы решить проблема на оставшихся 20 кандидатов. К счастью, 20 выбрать 10 только 184 756

Редактировать: благодаря проницательному комментарию etarion в заявлении о задаче оптимизации было изменено «Возвращать сумму (расстояний)» на «Возвращать минимальное расстояние»

Ответы [ 2 ]

5 голосов
/ 23 марта 2011

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

Пусть D - верхняя треугольная матрица с вашими расстояниями в верхнем треугольнике.Т.е. где i

Тогда ваша цель - максимизировать x '* D * x, где x является двоичным значением с 10 элементами, установленными в 1, а остальные в0. (Установка i-й записи в x в 1 аналогична выбору i-го элемента в качестве одного из ваших 10 элементов.)

«Стандартная» выпуклая оптимизация, связанная с комбинаторной задачей, подобной этой, заключается в расслабленииограничения такие, что х не нужно дискретно оценивать.Это дает нам следующую проблему:

maxify y '* D * y при условии: 0 <= y_i <= 1 для всех i, 1' * y = 10 </p>

Это (морально) квадратичная программа.(Если мы заменим D на D + D ', она станет добросовестной квадратичной программой, и у вас получится не отличаться.) Вы можете использовать стандартный решатель QP или просто подключить его крешатель выпуклой оптимизации по вашему выбору (например, cvx).

Значение y, которое вы получаете, не обязательно (и, вероятно, не будет) двоичным вектором, но вы можете преобразовать скалярные значения в дискретные вкуча способов.(Самое простое - это, вероятно, позволить x быть 1 в 10 записях, где y_i является наибольшим, но вам может потребоваться сделать что-то более сложное.) В любом случае, y '* D * y с y, которое вы получаете, даетВы получаете верхнюю границу для оптимального значения x '* D * x, поэтому, если x, который вы строите из y, имеет x' * D * x очень близко к y '* D * y, вы можете быть очень довольны своим приближением.

Дайте мне знать, если что-то из этого неясно, обозначено или нет.

2 голосов
/ 23 марта 2011

Хороший вопрос.

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

Вот очевидный базовый уровень, с которым я бы сравнил любое другое решение:

  1. Повторите 100 раз:
  2. Жадно выберите точку данных, удаление которой меньше всего уменьшает целевую функцию, и удалите ее.
...