ЖУРНАЛ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И МАТЕМАТИЧЕСКОЙ ФИЗИКИ, 2015, том 55, № 2, с. 335-344
УДК 519.7
РАНДОМИЗИРОВАННЫЙ АЛГОРИТМ ДЛЯ ОДНОЙ ЗАДАЧИ ДВУХКЛАСТЕРНОГО РАЗБИЕНИЯ МНОЖЕСТВА ВЕКТОРОВ1)
© 2015 г. А. В. Кельманов*, **, В. И. Хандеев*
(*630090Новосибирск, пр. Ак. Коптюга, 4, Ин-т математики СО РАН; **630090Новосибирск, ул. Пирогова, 2, Новосибирск. гос. ун-т) e-mail.kelm@math.nsc.ru, vladimir.handeev@gmail.com Поступила в редакцию 12.03.2014 г.
Обоснован рандомизированный алгоритм для МР-трудной в сильном смысле задачи разбиения конечного множества векторов евклидова пространства на два кластера заданных размеров по критерию минимума суммы квадратов расстояний от элементов кластеров до их центров. Предполагается, что центр одного из кластеров является оптимизируемой величиной и определяется как среднее значение по всем векторам, образующим этот кластер. Центр другого кластера фиксирован в начале координат. Предложенный алгоритм при заданных относительной ошибке и вероятности несрабатывания для установленного значения параметра находит приближенное решение задачи за линейное от размерности пространства и размера входа задачи время. Найдены условия, при которых алгоритм асимптотически точен и позволяет находить решение за время, линейное от размерности пространства и квадратичное от размера входа задачи. Библ. 23.
Ключевые слова: разбиение, множество векторов, квадраты евклидовых расстояний, NP-труд-ность, рандомизированный алгоритм, асимптотическая точность.
DOI: 10.7868/S0044466915020131
ВВЕДЕНИЕ
Предметом исследования настоящей работы является труднорешаемая задача дискретной оптимизации. Цель работы — обоснование рандомизированного алгоритма для ее решения.
Одной из наиболее известных (более полувека) задач кластерного анализа, возникающих, в частности, при решении проблем аппроксимации, компьютерной геометрии, статистики и распознавания образов, является задача MSSC (Minimum sum-of-squares clustering) (см. [1]—[3]). В этой задаче требуется разбить конечное множество векторов евклидова пространства на совокупность кластеров так, чтобы сумма по всем кластерам суммы квадратов расстояний от элементов кластера до его геометрического центра была минимальной. Под геометрическим центром кластера понимается среднее значение элементов, входящих в этот кластер. Ввиду актуальности задачи MSSC для приложений исследование этой задачи и ее специальных случаев, а также обобщений рассматривается в сотнях публикаций (см., например, [1]—[8] и цитированные там работы). Однако факт ее труднорешаемости установлен совсем недавно (см. [9]).Этот факт стимулировал исследования математических задач, близких к MSSC в постановочном плане, которые не менее актуальны для разнообразных естественно-научных и технических приложений (см., например, [4]—[21] и цитированные там работы). К их числу относится задача, рассматриваемая в настоящей работе.
Исследуемая задача моделирует, в частности, одну из актуальных проблем помехоустойчивого кластерного анализа данных, которая заключается в разбиении таблицы с результатами измерения набора числовых характеристик некоторого объекта на два таких подмножества (кластера), что одно из них соответствует активному, а другое — пассивному состояниям этого объекта (см., например, [11], [12] и [19]). Предполагается, что в пассивном состоянии значения всех характеристик объекта равны нулю, а в активном — значение хотя бы одной характеристики не равно нулю. При этом все табличные данные содержат измерительную ошибку, соответствие между
1) Работа выполнена при финансовой поддержке РФФИ (коды проектов 15-00-00462, 13-07-00070).
результатом измерения и состоянием объекта отсутствует, а критерием решения является минимум суммы квадратов уклонений.
Сильная NP-трудность задачи, которая индуцируется сформулированной проблемой, была установлена в [19]. Приближенные полиномиальные алгоритмы с оценками точности предложены в [11] и [12]. Характеристики этих алгоритмов приведены в следующем параграфе. Здесь лишь отметим, что рандомизированные алгоритмы для решения рассматриваемой задачи до настоящего времени не были кем-либо обоснованы. Вместе с этим хорошо известно (см. [22]), что алгоритмы рандомизированного типа обладают важным свойством: во многих случаях они позволяют находить приближенное решение какой-либо NP-трудной задачи с вероятностно гарантированным качеством за меньшее время, чем алгоритмы других типов. Эти факты мотивировали настоящую работу.
Ниже предложен рандомизированный алгоритм, обладающий указанным свойством. Этот алгоритм для установленного значения параметра при заданной относительной ошибке б > 0 и фиксированной вероятности у е (0, 1) несрабатывания находит (1 + б)-приближенное решение задачи с временными затратами, которые линейны как относительно размерности пространства, так и относительно размера входа задачи. Установлены условия, при которых алгоритм асимптотически точен и имеет трудоемкость, линейную относительно размерности пространства и квадратичную относительно размера входа задачи.
1. ФОРМУЛИРОВКА ЗАДАЧИ И ИЗВЕСТНЫЕ РЕЗУЛЬТАТЫ
Рассматриваемая задача имеет следующую формулировку (см. [11], [12] и [19]).
Задача 1-MSSC-F. Дано: множество ЗД = {y1, ..., yN} векторов из [Rq и натуральное число M. Найти: разбиение множества ЗД на два кластера % и ЗД\% такое, что
S(%) = X IIУ - У(% )ll2 + X Hyll2 min, (1.1)
y e % У e ЗД\%
где y( %) = ¡-Ц X У — центр кластера %, при ограничении |%|= M.
У e %
В задаче (1.1) входное множество ЗД соответствует таблице (см. содержательную трактовку во введении), содержащей N результатов измерения набора из q числовых характеристик некоторого объекта. Центр подмножества % — оптимизируемая величина, а центр подмножества ЗД\% фиксирован в начале координат. Число M соответствует числу измерений объекта в активном состоянии.
Задача 1-MSSC-F является частным, но NP-трудным случаем задачи /-MSSC-F (когда J = 1) (см. [19]). В задаче J-MSSC-F требуется разбить входное множество на J + 1 кластер, причем центры J кластеров являются оптимизируемыми величинами, а центр одного из кластеров фиксирован в начале координат (см. [19]). Символы MSSC в кратком названии сформулированной задачи подчеркивают содержательное сходство с классической NP-трудной задачей MSSC, в которой центры всех искомых непересекающихся кластеров являются оптимизируемыми величинами. Последний символ F (от английского Fixed) указывает на то, что мощности кластеров фиксированы.
В [11] для задачи 1-MSSC-F построен 2-приближенный полиномиальный алгоритм, который находит решение за время ©(qN2). Полиномиальная приближенная схема (PTAS), имеющая временную сложность ©(qN2/6 + 1(9/б)3/е), где б — гарантированная оценка относительной погрешности, предложена в [12].
Суть предлагаемого алгоритмического решения состоит в следующем. Из множества ЗД путем случайного независимого выбора (с возвращением) его элементов формируется конечное мультимножество. Для каждого из непустых подмножеств этого мультимножества вычисляется центр (среднее значение) и формируется набор из M векторов исходного множества, имеющих наибольшие проекции на этот центр. Сформированный набор объявляется претендентом на решение. В качестве окончательного решения выбирается то подмножество-претендент, для которого значение целевой функции минимально.
2. ГЕОМЕТРИЧЕСКИЕ И ВЕРОЯТНОСТНЫЕ ОСНОВЫ АЛГОРИТМА
Для построения алгоритма нам потребуется несколько вспомогательных утверждений. Положим
0(% Ь) = £ ||у - Ь||2 + £ ||у||2, (2.1)
у е % у е ЗД\%
где % с ЗД, |%| = М, Ь е К?.
Лемма 1. При любом фиксированном подмножестве % с ЗД минимум функционала (2.1) доставляется вектором у (%) = — £ у и равен 5(%). При любом фиксированном векторе Ь е К? мини-
Му е %
мум функционала (2.1) достигается на множестве, состоящем из Мвекторов множества ЗД, имеющих наибольшие проекции на вектор Ь.
Доказательство. Справедливость первого утверждения легко проверить аналитически (с помощью дифференцирования). Справедливость второго утверждения вытекает из следующей цепочки равенств:
&(Ь) = £ IIу - Ь||2 + £ ||у||2 =
у е % у е ЗД\%
= £ 01 у - Н2-||у||2) + £ 1Ы12 = £ ||у||2 + м• ||ь||2 - 2 £ <у, ь> .
у е % у е ЗД у е ЗД у е %
Остается заметить, что первые два слагаемых в правой части полученного выражения являются константами. Лемма 1 доказана.
Лемма 2. Пусть Ж — произвольное множество векторов из К? мощности N % с Ж, |%| = М; V — мультимножество, полученное к случайными независимыми одноэлементными выборками с возвращением из множества Ж. Пусть, кроме того, г (%) = — £ г и г( V п %) = ----; £ г —
М^г е % ¡V п %|^г е V п %
центры множества % и мультимножества V п % соответственно. Тогда для любого натурального t < к справедливы соотношения
Е(г(V п %)|IV п %| > ,) = г(%), (2.2)
Е (||г( V п %) - г(% )|| 2\IV п %| > ,) < -1- £ ||г - г(% )||2, (2.3)
tM ¿—I
ге %
где Е — символ математического ожидания.
Доказательство. Пусть О — множество всех к-элементных мультиподмножеств множества Ж. Положим Оt = ^^ е О и | V п %| > Ц. Заметим, что
О = £ ф М(М - М)к \
I=t
так как t есть множество тех мультиподмножеств множества Ж, которые содержат не менее t элементов из множества % (с учетом кратности).
Покажем справедливость равенства (2.2). По определению математического ожидания имеем
Е(«V п %^V п % >t) = -О- £ р^ £
1 4 V ЕЙ, V п
=О £ (£' < -,')м - ■ -м
г =
г е V п %
\
чк-I
г е % 1 = ,
1 ^ х (Е 0 -щк-')г = М е2 = г<%) •
г е %(' = г ) г е %
Второе равенство в этой цепочке следует из того, что в двойной сумме ЕУ е п Ег е У п % г каждый
вектор г е % входит в множества У е О,, для которых |У п %| = ' (при ' е {?, ..., к}), ровно к - 1
к ( 1М (N - М) ' раз, где к — число позиций в наборе У, на которых может стоять вектор г,
('-1 )
к -1
'-1
ГС -1
— количество вариантов расстановки позиций для остальных С — 1 векторов из У п %,
М' 1 — количество вариантов выбора этих векторов, а (^ — М)к ' — количество вариантов выбора к — ' векторов из У п (Ж\%).
Покажем справедливость неравенства (2.3). Заметим сначала, что
Х1г - г(% Л2 = ХИ2 - М
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.