ЖУРНАЛ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И МАТЕМАТИЧЕСКОЙ ФИЗИКИ, 2011, том 51, № 11, с. 2106-2112
УДК 519.712.41
О СЛОЖНОСТИ НЕКОТОРЫХ ЗАДАЧ КЛАСТЕРНОГО АНАЛИЗА^
© 2011 г. А. В. Кельманов
(630090 Новосибирск, пр-т Акад. Коптюга, 4, Ин-т матем. СО РАН) e-mail: kelm@math.nsc.ru Поступила в редакцию 15.02.2011 г.
Доказана NP-полнота нескольких актуальных задач кластеризации конечного множества векторов евклидова пространства. Библ. 13.
Ключевые слова: дискретная оптимизация, сложность, NP-полнота, кластеризация, евклидово пространство, анализ данных.
ВВЕДЕНИЕ
Объект исследования настоящей работы — проблемы оптимизации. Предмет исследования — некоторые актуальные задачи кластеризации конечного множества векторов евклидова пространства. Цель работы — анализ алгоритмической сложности этих задач.
Проблемы кластерного анализа исследуются более полувека. Из недавно опубликованного обзора [1] видно, что принципы, критерии, модели, задачи, методы и алгоритмы кластеризации рассматривались в тысячах публикаций. При этом скорость разработки алгоритмов (как правило, эвристических и не имеющих теоретических гарантий по точности) для решения разнообразных прикладных задач значительно опередила скорость изучения алгоритмической сложности редуцированных оптимизационных задач, к которым сводятся прикладные проблемы. Статус сложности многих редуцированных задач до настоящего времени остается невыясненным, хотя интуитивно и гипотетически они считаются NP-трудными. Между тем выяснение сложностного статуса позволяет решить вопросы о существовании как точного полиномиального алгоритма решения редуцированной экстремальной задачи, так и эффективного алгоритма, гарантирующего оптимальность решения соответствующей прикладной проблемы. Поэтому изучение алгоритмической сложности задач кластерного анализа и их систематизация является важным направлением исследований.
В этой краткой работе анализируется алгоритмическая сложность нескольких похожих по постановке задач кластерного анализа. Мотивацией исследований послужил тот факт, что статус сложности этих задач не был известен. В постановочном плане они близки к хорошо известной (см. [2]—[5]) NP-полной задаче MSSC (Minimum-Sum-of-Squares Clustering) — кластеризации множества векторов евклидова пространства по критерию минимума суммы квадратов расстояний от элементов кластеров до их центров. В некоторых публикациях (см., например, [1], [4], [6]) эта же задача фигурирует под названием k -Means. Рассматриваемые задачи по постановке близки также к тем задачам кластерного анализа, NP-полнота которых была установлена в [7]—[10]. Чтобы пояснить отличие задач, исследуемых в настоящей работе, от задач, изученных ранее в [2]—[10], рассмотрим одну из возможных содержательных трактовок анализируемой проблемы.
Имеется совокупность (таблица), включающая несколько результатов измерения набора (вектора) каких-либо характеристик для элементов из некоторого множества материальных объектов. Каждый объект может находиться в двух состояниях: активном и пассивном. В пассивном состоянии значения всех измеряемых характеристик из набора равны нулю, а в активном — значение хотя бы одной характеристики не равно нулю. Для активных состояний одной части объектов из множества известен алфавит эталонных наборов значений всех характеристик. Для ак-
1)Работа выполнена при финансовой поддержке РФФИ (коды проектов 09-01-00032 и 10-07-00195), целевой программы № 2 Президиума РАН (проект № 227), целевой программы СО РАН (интеграционный проект № 44), целевой программы АВЦП Рособразования (проект № 2.1.1/3235), а также федеральной целевой программы "Научные и научно-педагогические кадры инновационной России" (гос. контракт № 14.740.11.0362).
2106
тивных состояний другой части объектов этого множества аналогичные данные отсутствуют (неизвестны). В каждом результате измерения имеется ошибка, причем соответствие между объектом и результатом измерения его характеристик неизвестно. Требуется, используя критерий минимума суммы квадратов расстояний, разбить совокупность наборов на три семейства непересекающихся подмножеств: 1) семейство, состоящее из единственного множества, содержащего наборы, соответствующие пассивному состоянию всех объектов; 2) семейство, состоящее из подмножеств, каждое из которых содержит наборы, соответствующие активному состоянию одного объекта, имеющего известные характеристики; 3) семейство, состоящее из подмножеств, каждое из которых содержит наборы, соответствующие активному состоянию одного объекта с неизвестными характеристиками. Одновременно с разбиением требуется оценить неизвестные характеристики для части объектов в активном состоянии, учитывая, что данные содержат ошибку измерения. Судя по обзору [1], сформулированная содержательная проблема характерна и актуальна для широкого спектра приложений, связанных с анализом данных и распознаванием образов.
Отличие рассматриваемых ниже задач, к которым сводится сформулированная проблема, от близких аналогов состоит в следующем. Задача М88С (см. [2]—[6]) ориентирована на случай, когда анализируемая совокупность наборов (данных) состоит лишь из третьего семейства. В задачах, изучавшихся в [7]—[9], предполагалось, что заданная на входе совокупность наборов состоит только из первого и третьего семейства. В [10] анализировалась еще более простая задача, когда во множестве наборов требовалось найти всего один многоэлементный кластер или подмножество фиксированной мощности в предположении, что входная совокупность наборов включает, во-первых, соответствующее подмножество результатов измерения только для одного объекта, который может находиться лишь в активном состоянии, а во-вторых, эта совокупность содержит произвольные и "непохожие" между собой наборы.
Статья имеет следующую структуру. В разд. 1 приведены формулировки и дан мини-обзор тех известных МР-полных задач кластеризации по критерию минимума суммы квадратов расстояний, которые наиболее близки к рассматриваемым задачам. Формулировки возможных вариантов задач, соответствующих содержательной проблеме, изложенной во Введении, даны в разд. 2. В разд. 3 доказано, что эти задачи относятся к классу труднорешаемых задач дискретной оптимизации. Возможные подходы, методы и эффективные алгоритмы с оценками для решения этих задач не являются предметом настоящего исследования, но их изучение представляется делом ближайшей перспективы.
1. НЕКОТОРЫЕ БЛИЗКИЕ АНАЛОГИ ЗАДАЧИ М88С
Одна из самых известных задач кластеризации имеет следующую формулировку в форме верификации свойств.
Задача М88С. Дано: множество = {уь у2,..., ун} векторов из К?, натуральное число J > 1 и положительное число А. Вопрос: существует ли разбиение множества ^ на непустые подмножества (кластеры) С1, С2,..., С1 такое, что имеет место неравенство
X XIIу - у(С)||2 * А, (1.1)
1=1 у<С
где центр -го кластера
у(С) = С! X у' У =1'2' •••'1.
МР-полнота различных вариантов этой задачи (обусловленных тем, что размерность пространства и число кластеров могут являться или не являться частью входа задачи) была установлена совсем недавно в [2]—[5]. Более ранние публикации содержали ошибки в доказательстве, что было отмечено в [2], [3].
К числу менее изученных в алгоритмическом плане МР-полных задач (см. [7]—[10]) относятся следующие разновидности задачи кластеризации по критерию минимума суммы квадратов расстояний.
Задача MSSC-Case. Дано: множество ty — {y y2, ..., yn} векторов из Rq, натуральное число M > 1 и положительное число A. Вопрос: существует ли разбиение множества ty на J = N - M + 1 непустых кластеров С1, С2,..., CN_M+1 такое, что мощность одного из кластеров равна M и справедливо неравенство (1.1).
Из формулировки легко видеть, что эта задача соответствует ситуации (упомянутой во Введении), когда во множестве векторов требуется найти всего один M-элементный кластер и N - M одноэлементных кластеров (см. [10]).
Задача MSSC-N. Дано: множество ty — {y 1, y2,..., yn} векторов из [Rq, натуральное число J и положительное число A. Вопрос: существует ли разбиение множества ty на кластеры C1, C2,..., CJ и ® = ty\(u jCj) такое, что справедливо неравенство
j
ЕЕ II y - y(Cj )ll2 + EMI2 * A, (1.2)
j=1 yeCj ye®
где центр j -го кластера
y(C) = TC1! E y' j =1'2'J.
Cj|yeCj
Задача MSSC-F. Дано: множество ty = {y1, y2, ..., yN} векторов из Rq, натуральные числа M1, M2, ..., MJ и положительное число A. Вопрос: существует ли разбиение множества ty на кластеры C1, C2, ..., CJ и ® = ty\(ujCj) такое, что имеет место неравенство (1.2) при ограничениях
|Cj| = Mj, j = 1, 2,..., J, на мощности кластеров.
Задачи MSSC-N и MSSC-F, изучавшиеся в [7]—[9], соответствуют описанной во Введении ситуации, когда центр одного из кластеров (это кластер ® в формуле (1.2)) определять не требуется. В практических задачах этот кластер ассоциируется либо с измерительным шумом, который может содержаться в таблице с данными, либо с пассивными состояниями объектов. Символы F и N в названиях задач образованы от английских слов Fixed и Nonfixed для обозначения двух возможных вариантов одной общей проблемы. Эти варианты индуцируются наличием (Fixed) или отсутствием (Nonfixed) ограничений на мощности искомых кластеров C1, C2,..., CJ. Следует отметить, что задачи MSSC-N и MSSC-F являются NP-полными даже в простейшем случае, когда J = 1 (см. [8]).
2. НЕИЗУЧЕННЫЕ ЗАДАЧИ КЛАСТЕРНОГО АНАЛИЗА
Задачи кластеризации, сформулированные ниже, соответствуют содержательной проблеме, изложенной во введении.
Задача MSSC-NN. Дано: множество ty = {y1, y2,..., yN} и алфавит {v1, v2,..., vK} векторов из Rq, натуральное число J и положительное число A. Вопрос: существует ли разбиение множества ty на непустые кластеры C1, C2,..., CJ, ®1, ®2,..., ®K и ® = ty\((uyCj) u (uk®k)) такое, что имеет место неравенство
Е El y - y(Cj )||2 + ЕЕ Е lly - v kl2 + El yll2 ^ A , (2.1)
j=1 yeCj k=1 ye® k ye®
где центр j -го кластера
y(Cj) = Ey' j = 1'2'J.
|C j 1 yeCj
Задача М88С^№ Дано: множество % = {уь у2, ...,ун} и алфавит {V!, V2,..., Vк} векторов из Кч, натуральные числа М1, М2, ..., М} и положительное чи
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.