Алгоритмы с оценками для решения задач анализа данных тема автореферата и диссертации по математике, 01.01.09 ВАК РФ
|
Долгушев, Алексей Владимирович
АВТОР
|
||||
|
кандидата физико-математических наук
УЧЕНАЯ СТЕПЕНЬ
|
||||
|
Новосибирск
МЕСТО ЗАЩИТЫ
|
||||
|
2012
ГОД ЗАЩИТЫ
|
|
01.01.09
КОД ВАК РФ
|
||
|
|
||||
На правах рукописи
Ог 1
п 1
и
ДОЛГУШЕВ АЛЕКСЕЙ ВЛАДИМИРОВИЧ
АЛГОРИТМЫ С ОЦЕНКАМИ ДЛЯ РЕШЕНИЯ ЗАДАЧ АНАЛИЗА ДАННЫХ
01.01.09 — дискретная математика и математическая кибернетика
Автореферат диссертации на соискание учёной степени кандидата физико-математических наук
- 1 НОЯ 2012
Новосибирск — 2012
005054066
005054066
Работа выполнена в Федеральном государственном бюджетном образовательном учреждении высшего профессионального образования «Новосибирский государственный университет».
Научный руководитель:
доктор физико-математических наук, старший научный сотрудник, Кельманов Александр Васильевич
Официальные оппоненты: доктор физико-математических наук,
профессор,
Гимади Эдуард Хайрутдинович
доктор физико-математических наук, профессор,
Попков Владимир Константинович
Ведущая организация:
Федеральное государственное бюджетное учреждение пауки Институт математики и механики Уральского отделения Российской академии наук
Защита состоится '"¿1" ноября 2012 г. в 16 часов па заседании диссертационного совета Д 003.015.01 при Федеральном государственном бюджетном учреждении науки Институте математики им. С. Л. Соболева Сибирского отделения РАН по адресу: 630090, г. Новосибирск, пр. Коп-тюга 4.
С диссертацией можно ознакомиться к библиотеке Института математики им. С. Л. Соболева Сибирского отделения РАН.
Автореферат разослан '_" октября 2012 г.
Ученый секретарь диссертационного совета, доктор физико-математическх наук, старший научный сотрудник,
Шамардин Ю.В.
Общая характеристика работы
Актуальность работы1. Объектом исследования настоящей работы являются проблемы оптимизации. Предмет исследования — дискретные экстремальные задачи, к которым сводятся актуальные проблемы помехоустойчивого анализа данных, распознавания образов и классификации. Цель исследования — анализ алгоритмической сложности этих задач и построение эффективных алгоритмов с гарантированными оценками точности для их решения.
Одной из наиболее известных экстремальных задач анализа дан-пых и распознавания образов является задача MSSO (Minimum Sum-of-Squares Clustering) — кластеризации (разбиения) конечного множества векторов евклидова пространства по критерию минимума суммы квадратов расстояний. На протяжении нескольких десятилетий эта задача считалась NP-трудной. Однако совсем недавно2 в доказательстве сё труднорсшасмости были обнаружены ошибки. В связи с этим снова стал актуальным анализ алгоритмической сложности этой задачи и её специальных случаев. Один из таких случаев проанализирован в настоящей работе.
К числу актуальных относится задача разбиения (но критерию минимума суммы квадратов расстояний) конечного множества векторов евклидова пространства па кластеры фиксированной мощности в случае, когда центр одного из кластеров определять не требуется (считается, что он фиксирован и равен нулю). Эта задача в постановочном плане близка к задаче MSSC, но не эквивалентна ей. Она важна для ряда приложений, связанных с помехоустойчивым анализом данных'5. В настоящей работе изучается простейший в содержательном плане случай этой задачи, когда заданное множество требуется разбить на два кластера.
В приложениях, связанных с помехоустойчивой обработкой сигналов, актуальны задачи4 анализа и распознавания векторных последо-
1 Работа выполнена при поддержке грантов РФФИ (проекты №09-01-00032, № 1007-00195), а также ФЦП «Научные и научно-педагогические кадры инновационной России» (гос. контракт № 14.740.11.0362).
2Aloise D-, Hansen P. On the Complexity of Minimum Suin-of-Squares Clustering // Les Cahiers du GERAI), G-2007-50. 2007. 12 p.
3Кельманов A.B. Проблема oil-line обнаружения повторяющегося фрагмента в числовой последовательности // Тр. МММ УрО РАН. Екатеринбург. 2008. Т. 14. № 2. С. 81-88.
4Kel'manov A.V., Jeon В. A Posteriori Joint Detection and Discrimination of Pulses
in a Quasiperiodic Pulse Train //' IEEE Trans, on Signal Pruc., 2004, Vol. 52, No. 3, pp. ()4r>-f)5(¡.
вательностей, структура которых в отсутствие помехи содержит ненулевые информационно значимые векторы, перемежающиеся с нулевыми векторами. В частных случаях эти задачи можно трактовать как задачи обнаружения разладки5 (изменения свойств) случайной последовательности. В тысячах публикаций рассматриваются разнообразные постановки подобных задач и последовательные (on-line) алгоритмы их решения, основанные на фундаментальной рабо те Вальдаь. В то же время эффективные апостериорные (off-line) алгоритмы с гарантированными оценками точности для большинства из этих задач отсутствуют7. Несколько таких задач исследовано в настоящей работе.
Цель диссертационной работы — исследование задач кластеризации конечно! !) множества век торов евклидова пространства, а также экстремальных задач связанных с помехоустойчивым анализом и распознаванием векторных последовательностей, структура которых характеризуется наличием повторяющихся информационно значимых векторов; построение эффективных алгоритмов с гарантированными оценками точности для решения этих задач.
Основные результаты:
1. Доказана ХР-полнота задачи MSSC — кластеризации конечного множества векторов евклидова пространства по критерию минимума суммы квадратов расстояний — в случае, когда размерность пространства является, а число кластеров не является частью входа задачи.
2. Построен эффективный '¿-приближённый алгоритм для решения NP-трудной задачи разбиения конечного множества векторов евклидова пространства на два кластера фиксированной мощности но критерию минимума суммы квадратов расстояний от элементов кластера до его центра в случае, когда центр одного из кластеров совпадает с началом координат.
3. Для этой же задачи обоснована приближённая полиномиальная схема (PTAS).
4. Разработаны полиномиальные алгори тмы, позволяющие находить оптимальное решение экстремальных задач, к которым сводится проблема помехоустойчивого off-line распознавания векторной последовательности как структуры, включающей повторяющийся вектор, при на-
5Ширяев А.Н. Статистический последовательный анализ // М.: Наука, 1976, 272 с.
6Wal<l Л. Sequential analysis, New York: John Wiley, 1!M7. 224 p.
"Ксльманов A.IB. О некоторых полиномиально разрешимых и NP-трудных задачах анализа и распознавания последовательностей с квазинериодической структурой // 13-я Всероссийская конференция «Математические методы распознавания обранов» (MMPO-lSj. Сборник докладов. М.: МАКС Пресс, 2007. - с. 2G1-264.
линии «посторонних» векторов-вставок: а) из произвольного множества ненулевых векторов; б) из заданного алфавита. Предполагается, что помеха является выборкой из нормального распределения с диагональной матрицей коварпаций, а критерием приня тия решения является максимум функционала правдоподобия.
Научная новизна результатов состоит в следующем.
1. Факт NP-полиоты указанного случая задачи MSSC установлен впервые.
2. Эффективные алгоритмы с константной оценкой точности, а также схема PTAS для решения задачи разбиения векторов евклидова пространства на два кластера фиксированной мощности в случае, когда не требуется определя ть центр одного из кластеров, до настоящего времени отсутствовали.
3. Полиномиальные off-line алгоритмы, гарантирующие оптимальное решение задач, к которым сводя тся указанные выше проблемы анализа и распознавания последовательностей, предложены впервые.
Методы исследований. Основными инструментами исследований служили методы дискретной оптимизации, среднеквадратического приближения, математической статистики и полиномиальной сводимости. При обосновании приближенных алгоритмов применялась специальная техника, позволяющая находить гарантированную границу уклонения приближенного решения от оптимального. Эффективная разрешимость задач устанавливалась конструктивно (алгоритмически).
Теоретическая и практическая значимость. Работа носит теоретический характер. Её результаты могут быть использованы в математической теории распознавания образов и классификации, а также в теории дискретных экстремальных задач, например, в исследованиях, связанных с изучением алгоритмической сложности. Предложенные алгоритмы могут использоваться в компьютерных технологиях, ориентированных на решение прикладных задач.
На'защиту выносится совокупность результатов но исследованию алгоритмической сложности, а также эффективные алгоритмы с гарантированными оценками точности для задач дискретной оптимизации, к решению которых сводятся актуальные проблемы анализа данных, распознавания образов и классификации.
Личный вклад автора. Все выносимые па защиту результаты получены соискателем лично. Постановки проблем анализа данных и распознавания образов предложены научным руководителем. Подходы к анализу алгоритмической сложности и идеи алгоритмических решений редуцированных оптимизационных задач найдены совместно с научным
руководителем и соавтором. Доказательства утверждений выполнены соискателем. Конфликт интересов с соавторами отсутствует.
Апробация работы. Результаты диссертации докладывались на следующих международных и российских конференциях: XLV и XLVI международных студенческих конференциях «Студент и научно-технический прогресс» (г. Новосибирск. 2007, 2008), 15-й международной конференции «Проблемы теоретической кибернетики» (г. Казань, 2008), XIV Байкальской международной школе-семинаре «Методы оптимизации и их приложения» (г. Северобайкальск, 2008), международной конференции «Алгоритмический анализ неустойчивых задач» (г. Екатеринбург. 2008), международной конференции «Classification, Forecasting, Data Mining» (г. Варна, Болгария, 2009), IV Всероссийской конференции «Проблемы оптимизации и экономические приложения» (г. Омск, 2009), 14-й Всероссийской конференции «Математические методы распознавания образов» (г. Суздаль, 2009), Российской конференции «Дискретная оптимизация и исследование операций» (Алтай, 2010). 8-ой Международной конференции «Интеллектуализация обработки информации» (г. Пафос, Кипр, 2010). XIV Всероссийской конференции «Математическое программирование и приложения» (г. Екатеринбург, 2011), V Всероссийской конференции «Проблемы оптимизации и экономические приложения» (г. Омск, 2012), IX международной конференции «Интеллектуализация обработки информации» (г. Будва, Черногория, 2012). Кроме того, результаты работы обсуждались па семинарах кафедры Теоретической кибернетики Новосибирского государственного университета и на семинарах отдела Теоретической кибернетики Института математики им. C.JI. Соболева СО РАН.
Публикации. По результатам исследований опубликовано 16 работ. В их числе 4 статьи в журналах, рекомендованных ВАК РФ, 4 статьи в рецензируемых трудах конференций и 8 тезисов докладов.
Структура и объем диссертации. Диссертация изложена на 112 страницах и включает введение, две главы, заключение и список цитируемой литературы из 172 наименования.
Содержание работы
Во Введении обоснована актуальность темы диссертационной работы, приведено краткое изложение её содержания, сформулированы основные результаты, выносимые на защиту.
В Первой главе представлен обзор задач дискретной оптимиза-
ции, возникающих в рамках оптимизационных моделей кластеризации и поиска подмножеств, а также подходов и методов их решения.
Анализируется известная задача MSSC и задача разбиения множества векторов евклидова пространства на два кластера при условии, что центр одного из кластеров совпадает с началом координат. Для одного из случаев первой задачи установлена NP-полнота. Для второй задачи предложен эффективный приближённый алгоритм решения с константной оценкой точности и приближённая полномиальная схема решения.
В форме верификации свойств первая из этих задач формулируется следующим образом.
ЗАДАЧА MSSC. Длио: множество V = {l>i,..., v*¿} векторов из R', натуральное число J > 1 и положительное число А. Вопрос: существуют ли такое разбиение множества V на непустые подмножества (кластеры) С\,... ,Cj, что имеет место иещвепство
J
££>-tJ(Cj)||2<A
j=i veCj
где, v(Cj) = J2veCj j = 1, ■ ■ ■ — центр j-го кластера?
Одномерный вариант задачи разрешим за полиномиальное время8. Четыре возможных случая многомерного варианта этой задачи индуцируются комбинированием размерности пространства и числа кластеров как элементов, которые либо являются, либо не являются частью входа задачи. Ранее была установлена полиномиальная разершимость одного9 и доказана10 NP-трудность11 еще двух из четырех возможных случаев задачи. Сложность оставшегося случая устанавливает
Теорема 1.1. Задача MSSC NP-rcoyma в случае, когда размерность пространства является, а число кластеров не является частью входа задачг1 соответственно.
Доказательство основано па полиномиальном сведении задачи J-MSSC к частному случаю задачи (./ + 1)-MSSC и NP-полноте задачи
8Rao M. Cluster Analysis and Mathematical Programming // J. Amer. Statist. Assoc. 1971. Vol. 66. P. 622-626.
9Inaba M., Katch N., Imai II. Applications of Weighted Voronoi Diagrams and Randomization to Variance-Based Clustering // Prcc. Annual Symp. un Comput. CI torn. 1994. P. 332-339.
'"Aloise D., Deshpande A., Hansen P., Popat P. NP-Hardness of Euclidean Sum-of-Squares Clustering // Les Cahiers du ОЕПАП, G-2008-33. 2008. Л p.
nMahajan M., Nimbhorkar P., Varadarajaa K. The Planar k-means Problem is NP-Hard // Lecture Notes in Coinputer Science. 2009. Vol. 5431. P. 284-285.
2-MSSC10.
В этой же главе рассматривается Задача VS12 (Vector Subset). дано: множество У = {уи ■ ■ ■, 2In} векторов шК« и нлтщюлыюс число М > 1. НлЙТИ: подмножество С С У мощности М такое, что целевая функция
s(c) = J2\\y-y(c)\\2+ £ NI2' w
уес уеУ\с
где у(С) = щ £,;ес У. минимальна.
Задача VS NP-трудна в сильном смысле, так как целевая функция 5(C) минимальна тогда и только тогда, когда максимальна целевая функция NP-трудной13 в сильном смысле14 задачи MLSVS (Maximum Length of the Sum of Vectors in a Subset.) поиска подмножества векторов с максимальной нормой суммы.
Для решения задачи MLSVS ранее были предложены: полиномиальный приближённый алгоритм13 (без априорной оценки точности), FPTAS14 для случая фиксированной размерности пространства, полиномиальный алгоритм15, гарантирующий нахождение оптимального решения для случая фиксированной размерности пространства, а также псевдополиномнальные алгоритмы16, гарантирующие оптимальность решения задачи в случае, когда компоненты векторов имеют целочисленные значения. Апаниз этих результатов указывает па актуальность поиска таких приближенных алгоритмов решения задачи VS и MLSVS, сложность которых не зависит экспоненциально от размерности пространства. Для решения задачи VS в работе обоснован
12Кельманов A.B., Пяткин A.B. О сложности некоторых задач поиска подмножеств векторов и кластерного анализа // Журн. выч. мат. и мат. фгм. 2009, Т.49, N'11. С. 2059-2067.
13Гимади Э. X., Кельманов А. В., Кельманова М. А., Хамидуллин С. А. Апостериорное обнаружение в числовой последовательности квазипериодического фрагмента при заданном числе повторов /'/' Сиб. мсурн. индустр. математики. 2006. Т. 9, №1(25). С. 55-74.
14Бабурин А. Е., Гимади Э. X., Глебов Н. И., Пяткин А. В. Задача отыскания подмножества вектором 1- максимальным суммарным весом // Дискретный апалия и исследование операций. Сер. 2. 2007. Т. 14, № 1. С. 32-42.
15Гимади Э. X., Пяткин А. В., Рыков И. А. О полиномиальной разрешимости некоторых задач выбора подмножества векторов в евклидовом пространстве фиксированной размерности / ' Дискретный анали-ч и исследование операций. 2008. Т. 15, №6. С. 11-19.
1иГимади 9. X., Глазков Ю. В., Рыков И. А. О двух задачах выбора подмножества векторов с целочисленными координатами в евклидовом пространстве с максимальной нормой суммой разности //' Дискретный анали-ч и исследование операций. 2008. Т. 15, №5. С. 30-43.
Алгоритм Л\.
Шаг 1. Для каждого у € У, найдем подмножество В{у) С у, состоящее из вектора у и М — 1 векторов, имеющих максимальные проекции на направление вектора у.
Шаг 2. Выберем тот вектор у* & У и подмножество В (у*) С У, для которых целевая функция
D(B(y),y)= ¿2 \\x-yf + И' <2)
хеВ(у) х£У\В(у)
минимальна. Подмножество В (у*) объявляем результатом работы алгоритма.
Теорема 1.2. Алгоритм Л\ находит 2-приближённое решение задачи VS за врелт 0(qN2). Оценка 2 точности алгоритма достижима.
В этой же главе для решения задачи VS предложена схема PTAS. Алгоритм, реализующий эту схему, заключается в следующем. Пусть t и s — натуральные параметры алгоритма.
Алгоритм Ai-
Шаг 1. Найдём 2-приближённое решение В* и значение целевой функции S(B*) с помощью алгоритма Л\. По значению целевой этого решения и параметру алгоритма s вычислим шаг h = ^ sjS(B*)/M дискретной сетки.
Шаг 2. Для каждого подмножества фиксированной мощности t € [2, N] множества У построим линейную оболочку, которую дискретизу-ем с шагом h.
Шаг 3. Для каждого элемента z дискретной сетки, лежащего в шаре радиуса 2%JS(B*)/М, построим подмножество T{z) С У, состоящее из М векторов, имеющих наибольшие проекции па направление вектора вектора z.
Шаг 4. По формуле (2) вычислим значение функции D(T(z), z).
Шаг 5. Среди найденных на шагах 2, 3 подмножеств выберем подмножество Т*, для которого значение функции S минималыю. Подмножество Т* объявляем решением задачи VS.
Теорема 1.3. Алгоритм Л2 находит приближённое решение задачи VS с относительной погрешностью е < 1/t + ,s), где = y/t^l/s +{t- l)/.s2, за время 0(qNt+1 s1"1).
Во Второй главе рассматриваются проблемы помехоустойчивого off-line анализа и распознавания векторных последовательностей по критерию минимума суммы квадратов уклонений и максимума правдоподобия, анализируются дискретные экстремальные задачи, к которым
сводится решение этих проблем, обосновываются эффективные алгоритмы нахождения оптимального решения редуцированных задач. Эти задачи входят в большое семейство17 дискретных экстремальных задач, к которым сводятся актуальные проблемы18 помехоустойчивого off-line анализа и распознавания структурированных данных в виде числовых и векторных последовательностей, включающих повторяющиеся, чередующиеся и перемежающиеся информационно значимые векторы.
Одна из возможных содержательных трактовок рассматриваемых проблем состоит в следующем. Сканирующий источник сообщений через канал связи с помехой передает данные об активном и пассивном состояниях основного и посторонних объектов в виде последовательности наборов измеряемых информационно важных харак теристик. В пассивном состоянии значения всех компонент набора равны нулю. В активном состоянии значение хотя бы одной компоненты не равно нулю. Имеется конечная совокупность основных объектов. Каждому объекту соответствует уникальный набор измеряемых характеристик. На приёмную сторону поступает зашумлённая последовательность квазинери-одически перемежающихся наборов, в которой кроме набора, соответствующего активному состоянию основного объекта, имеются ненулевые наборы-вставки, соответствующие активным состояниям посторонних объектов. Термин «квазипериодически» означает, что интервал времени между двумя последовательными ненулевыми наборами не одинаков, а лишь ограничен сверху и снизу некоторыми константами. Необходимо определить (распознать), от какого из основных объектов были получены данные, а также найти в последовательности повторяющийся набор, соответствующий его активному состоянию. Анализируется два случая: а) наборы-вставки являются произвольными ненулевыми наборами; б) наборы-вставки принадлежат заданному конечному алфавиту.
Этой содержательной проблеме соответствует модель анализируемых данных, в которой векторная последовательность х„ 6 К'', п G АГ = {1,2,____N}, обладает свойством:
!и, u<=U, п € /С;
vn, vn G V, п е £; (3)
О, neJV\(X:u£),
17lH.tp://maÜi.nsi-.ru/~S(:r}i;<'/qpsl
18Kcl'manov A.V., Mikhailova L.V., Khamidullin S.A. QPSLab System for Analysis ami Recognition <>Г Signals With a Quasipcriodic Structure // 9-th Intern. Conf. сPattern Recognition and Image Analysis: New Information Technologies»: Conference Proceedings. Nizhni Novgorod, 2008. Vol." 1. p. 412-418.
где К U С = {пь... ,пм} С j\í, К. Л С = 0, \Ц = К > О, |£| = L > О;
U, V С К4. U П V = 0. Предполагается, что К. = {п,м.....п^.}, £ =
{n„j,..., }, где {ni,.... цк} и {t/j,..., } — подмножества порядковых номеров из множества {1,..., А/}. а элемен ты набора {/лi...., пл/} удовлетворяют ограничениям
1 < rmin ^ пт - пт_! Гтах ^ ЛГ - 1, т = 2.....Л/, (4)
где натуральные константы Tm¡n и Ттах задают допустимый интервал между ближайшими номерами двух ненулевых векторов последовательности (3). Доступной для обработки считается последовательность
Уп = хп + е„, пеМ, (5)
где е„ — вектор помехи (ошибки измерения), независимый от Хц.
В этой модели вектор и соответствует набору характеристик активного состояния основного объекта в содержательной проблеме; vn — наборам характеристик активного состояния «посторонних» объектов, набор {ni,... ,?).д/} — порядковым номерам ненулевых наборов в принятой последовательности, {/ii и {v\ — порядковым номерам ненулевых наборов от основного и «посторонних» объектов, соответственно. Константы Ттт и Ттлх задают минимальный и максимальный интервалы между двумя последовательными наборами в принятой последовательности, соответствующими активным состоянии объектов (интервал квазипериодичности).
Оптимизационные модели содержательных проблем распознавания формулируются в виде задач минимизации функционала
N
S{u,{vn,neC}, гц ,...,пЛ/. щ.....цк) = ~ J;"H2,
71=1
где структура последовательностей х„ и уп, п € AÍ, задаётся формулами (3), (4) и (5). В работе установлено, что к задачам минимизации функционала (6) сводятся статистические постановки проблем в случае, когда вектор ет, есть выборка пз гу-мерпого нормального распределения с параметрами (О.ст2/), где I — единичная матрица, а критерием решения является максимум функционала правдоподобия.
Из модели (3)-(5) следует, что минимизация функционала (6) сводится к решению следующих оптимизационных задач. Рлс1Ю:шлвлпи1:(А). Длмо: последовательность уп е W, п € Л/\ конечное множество U С 1', неотрицательное целое, число L и натуральные К, Ттт и Тщах- НаЙТИ: вектор и € И, а также наборы
{ni,... ,пм} С N и {(j.1,..., р. к} ^ {1, - - -, Л/}, такие что
к L
Fa(u, ПЬ...,ПЛ/. Hl.....Рк) = + -»• inax, (7)
¿=1 j=1
где
ft(n,u) = 2(j/„,u) - ||u||2, n G Л/", ii£W, (8)
r(n) = |Ы12, nejv, (9)
при условии, что M = К + L, а элементы множества {п\,... ,тгм} удовлетворяют ограничениям (4).
Распознавание(Б). Дано: последовательность уп g Шч, п 6 Л/\ конечные множества U С К4 и V С неотрицательное, целое число L и натуральные К, ТтЬ, и Ттлх. Найти: вектор и е U, а также наборы. {щ,... ,пм} < .V а {//;.....//а: } С {1,...,М}, такие, что
к L
FB(u, пь...,/1Л/, Mi.....Нк) = ^ шах' (10)
г=1 j=l
где k(n,u) определяется формулой (8),
с(п) = шах(2(уп,и) - |М|2), пеЛГ, (11)
v
при условии, что М = К + L, а элементы набора {пь ... ,пм} удовлетворяют ограничениям. (4).
Установлено, что максимумы функций FA и FB находятся по правилу
max Ft(u, пм, (ii,... ,рм) =
и, {71.1....."Л/}. {ß\.....МЛ/ }
К L
max max (V]м) + V"/»(гг,0)) (12)
" {«1....."«}. {М1 Ai> .=1
где F, = Fa, 1*{п) = r(n), п е лл для задачи распознавание(а), F* = Fd, l*(n) = c(n), п € .АЛ для задачи распознава[Ше(б). Для построения алгоритмов решения задач распознавание(а) и (в) рассматривается следующая баювая экстремальная задача. Задача В. Дано: числовые последовательности gi(n) и 52(1). п £ М, неотрицательное целое число L и натуральные К, 'Г„,ш и Гшах.
Найти: наборы {пь ... ,пд/} С N и ----f!K} с {1,____м} такие,
что
к L
G(m,...,nM, iii.....р.к) = Х^Кч) + Y,92^1'^ шах' (|3)
¿=1 j=1
где {i'i,----vl,} = {1,... ,м} \ {/^,... ,рк}, при условии, что М = К +
L, а элементы набора {iii,... ,пд/} удовлетворяют ограничениям (4).
Доказательство полиномиальной разрешимости этой задачи носит конструктивный характер и основывается па реализации схемы динамического программирования, обоснованной в следующем утверждении.
Лемма 2.1. Максимум целевой функции задачи В определяется по формуле
G„mx = max шах G(n,K,t,M), (14)
т>ешд,(Л/) te{K,K+\.....л/}
а значения функции G(n,K,t,M), п (Е ыд/(М), t е {К, К + 1,...,Л/}, вычисляются по следующим рекуррентным формулам:
G(n, k, t, т)
д\(п), если к = 1, t — 1, т = 1, п е uji(M), gi(n) + max H(j,m— 1), если
iflm-ll")
к = 1, t = 2,..., M, m = i, n e шт(М),
3i(n) + max max G(j, к — 1, s, m — 1), если nrs
1(") »e{fe-i.....m —1} (.'•>;
k = 2,...,K, t = k,...,M, m = t, n G tum(M), дъ{п) + max G(j, k, t, m — 1), если j67,7, -Д")
k fc = 1,..., K, t = k,..., Л/, m-t+l,...,M, n£ ujm{M),
H (n, m)
(If,)
где
92{n), если m = 1, /i€wi(M), Зг(п) + max H(j,m — 1), йсуш
m = 2,..., Л/, n e wm(M)\
um(M) = [1 + (m - l)Tmin, TV - (Л/ - m)rmin], гтг = 1_____M,
— интервал допустимых значений т-ой компоненты набора {пь . . . ,Пд/},
7m-i(n) = {i! max{l + (т - 2)Tmin, " - ^max)} < j < n - Tmhl,
m = 2.....А/,
— интервал допустимых значений (т - 1 )-ой компоненты набора {пх,... ,пд/} при условии, что т-ая -компонента равна п.
В следствии к этой лемме установлены формулы вычисления оптимальных наборов {пи...,пм} и {/7ь...,/*л-}, которые опускаются здесь в виду громоздкости.
Алгоритм А в решения базовой экстремальной задачи заключается в вычислении С,Ш1Х но формулам из леммы 2.1 (прямой ход) и нахождении оптимальных наборов по формулам следствия (обратный ход).
Теорема 2.1. Алгоритм Ав находит точное решение задачи В за
время 0( УКМ~ (-^111 ах Ттш
В работе построены алгоритмы Ат " -4я2 решения задач распознавания (А) и (В). Эти алгоритмы включают в себя три шага: 1) вычисление функций к(п,и) = сл(п|и), /,(тг) = д2{п), пеМ, (/»(") = г(п). п е АЛ для задачи рлспознавлние(а), /,(■«) = с(п), п £ Л/", для задачи р асп оз И А в Л11И К (В)) для каждого фикси]>овашюго и е Ы\ 2) вычислении (?„1;гх(с), и е и, с помощью алгоритма Ац\ 3) вычислении Стаж = тах,1еиС7ПГМ(и) и соответствующего этому значению целевой функции вектора й и наборов {Л1,..., пм}. {Дь ...,/}.к-}■
Установлена истинность следующих утверждений.
Теорема 2.2. Алгоритм Ащ находит оптимальное решение задачи распознавлппе(л) за время
0( \Ы\М{К{К + Ь)2(Тпхлх - Тпйп + 1) +
Теорема 2.3. Алгоритм Ав2 находит оптимальное. решение, задачи распознлвлние(б) за время 0{Ы(\Ы\К{К + £)2(тшях — у,,,;,,
+ 1) +
Значения (Ттпх - 7'ш;„ + 1), К и Ь не превышают N. Поэтому алгоритмы Ав, Ая|. Ав2 полиномиальны.
В частном случае, когда \Ы\ = 1, алгоритмы Ат и Аи2 гаран тируют оптимальность }>ешения актуальных задач помехоустойчивого обнаружения заданного вектора в последовательности при наличии «посторонних» векторов-вставок: а) из произвольного множества ненулевых векторов; б) из заданного алфавита.
В Заключении перечислены основные результаты диссертационной работы, очерчен круг возможных теоретических и практических применений полученных результатов, обозначены перспективы для дальнейших исследований.
Автор выражает искреннюю благодарность и глубокую признательность своему научному руководителю Александру Васильевичу Кель-маиову. а также всем сотрудникам кафедры Теоретической кибернетики НГУ и лабораторий Анализа данных и Дискретных задач в исследова-
нии операций ИМ СО РАН за постоянное внимание к работе, ценные замечания, плодотворные дискуссии и поддержку.
Список литературы
[1] Долгушев АЛЗ., Кельманов А.В. К вопросу об алгоритмической сложности одной задачи кластерного анализа // «Дискретный анализ и исследование операций», 2010, том 17, № 2, с. 39-45.
[2] A.V. Dolgushev, A.V. Kel'manov. On the Algorithmic Complexity of a Problem in Cluster Analysis //' «Journal of Applied and Industrial Mathematics». 2011. Vol. 5, No.2, pp. 191-194.
[3] Долгушев А.В., Кельманов А.В. Приближённый алгоритм для решения одной задачи кластерного анализа / / «Дискретный анализ и исследование операций», 2011, том 18. № 2, с. 29-40.
[4| A.V. Dolgushev. A.V. Kel'manov. An Approximation Algorithm for Solving a Problem of Cluster Analysis // «Journal of Applied and Industrial Mathematics», 2011, Vol. 5, No. 4, pp. 551-558.
[5| Долгушев А.В., Кельманов А.В. Об одном варианте задачи обнаружения в числовой последовательности образца фрагмента среди квазипериодически перемежающихся фрагментов // Труды XIV Байкальской международной школы-семинара «Методы оптимизации и их приложения». Иркутск, Байкал, 2-8 июля 2008 г. Т. 1 (Математическое программирование): Иркутск, ИСЭМ СО РАН, 2008, с. 35()-3()2.
[6] Алексей Долгушев, Александр Кельманов. Об одной задаче распознавания последовательности, включающей повторяющийся вектор /,/ Proceedings of the Intern. Conference «Classification, Forecasting. Data Mining» (CFDM 2009). June 22-July 2. 2009, Varna, Bugaria // Intern. Book Series «Information Science and Computing», No. 8 / Suppl. to the Intern. Journal, «Information Technologies and Knowcledge», Vol. 3, 2009, pp. 91-96.
[7| Долгушев A.B.. Кельманов А.В. Алгоритм помехоустойчивого распознавания последовательности, включающей повторяющийся вектор, при наличии посторонних векторов-вставок из алфавита /,'
Математические методы распознавания образов: 14-я Всероссийская конференция (ММРО-14). Владимирская обл., г. Суздаль, 2126 сентября 2009 г. : Сборник докладов. — М.: МАКС Пресс, 2009, с. 22Г>-228.
[8| Долгушев A.B. Обнаружение и идентификация заданного числа наборов эталонных фрагментов в квазипериодической последовательности /,/ Тез. докл. XLV Международной научной студенческой конференции «Студент и научно-технический прогресс». Новосибирск, 10-12 апреля 2007. с. 216.
[9] Долгушев A.B. Задача обнаружения и идентификации двух перемежающихся фрагментов в числовой последовательности // Тез. докл. XLVI Международной научной студенческой конференции «Студент и научно-технический прогресс». Новосибирск, 26-30 апреля 2008, с. 185.
[10] Долгушев A.B., Кельманов A.B. Задача обнаружения и идентификации двух квазипериодически перемежающихся фрагментов в числовой последовательности // Тез. докл. 15-й международной копф. «Проблемы теоретической кибернетики» (Казань, 2-7 июня 2008). Под ред. Ю.И. Журавлева. — Казань: Отечество, 2008, с. 28.
[11] Долгушев A.B. Об одном варианте задачи обнаружения образца фрагмента среди неизвестных перемежающихся фрагментов // Тез. докл. междупар. копф. «Алгоритмический анализ неустойчивых задач», посвященной 100-летию со дня рождения В.К. Иванова, 1-6 сентября 2008 г. — Екатеринбург: изд-во Уральского университета. 2008, с. 266-267.
[12] Долгушев A.B., Кельманов A.B. Об одной задаче поиска вектора в векторном алфавите // Материалы IV Всероссийской конференции «Проблемы оптимизации и экономические приложения». Омск, 29 июня - 4 июля 2009, с. 123.
[13] Долгушев A.B.. Кельманов A.B. К вопросу о сложности задачи MSSC // Материалы Российской конференции «Дискретная оптимизация и исследование операций», DOOR-2010. Алтай, 27 июня - 3 июля 2010. — Новосибирск: Изд-во Института математики СО РАН, 2010, с. 186. htt.i>://math.ns(:.ru/c(mference/(loor2()l()/book.html.
[14] Долгушев A.B.. Кельманов A.B. Приближённый алгоритм решения одной задачи кластерного анализа // Тез. докл. Всероссийской конференции «Математическое программирование и приложения». Екатеринбург, 2011, с. 84.
|15| Долгушев A.B., Кельманов A.B., Шепмайер В.В. Аппроксимациои-ная схема для одной задачи кластерного анализа // Материалы V Всероссийской конференции «Проблемы оптимизации и экономические приложения». Омск. 2012, с. 120.
|К)| Долгушев A.B.. Кельманов A.B.. Шепмайер В.В. Приближённая полиномиальная схема схема для одной задачи кластерного анализа // Интеллектуализация обработки информации: 9-ая международная конференция (ИОИ-9). Черногория, г. Вудва. 10-22 сентября, 2012 г.: Сборник докладов — М: МАКС Пресс, 2012 с. 242 244.
Долгушев Алексей Владимирович
Алгоритмы с оценками для решения задач анализа данных
Автореферат диссертации на соискание учёной степени кандидата физико-математических наук
Подписано в печать 11.10.12. Формат 60 х 84 1/16. Усл. печ. л. 1.3. Уч.-изд. л. 1.3. Тираж 100 экз. Заказ № 254 __
Редакционно-издательский центр НГУ 630090, Новосибирск, ул. Пирогова, 2
Введение
1 Труднорешаемые задачи кластеризации данных
1.1 Задачи поиска подмножеств и кластеризации векторов в евклидовом пространстве
1.2 Об алгоритмической сложности задачи MSSC.
1.2.1 Постановка задачи.
1.2.2 Известные факты о задаче.
1.2.3 NP-полнота задачи в случае, когда размерность пространства является, а число кластеров не является частью входа задачи
1.3 Задача VS поиска подмножества «похожих» векторов.
1.3.1 Постановка задачи.
1.3.2 2-приближённый алгоритм.
1.3.3 Апроксимационая схема.
Фундаментальной проблемой математической кибернетики и дискретной математики является анализ данных и распознавание образов. Эта проблема представляет значительный интерес как в практическом плане — в связи с прикладными проблемами обработки информации, так и в теоретическом плане — стимулируя поиск и изучение новых техник, принципов и алгоритмов во множестве предметных областей (математической статистике, исследовании операций, компьютерной геометрии и др.)
Основы анализа данных были заложены классическими работами Фишера (основы дискримипаптного анализа), Колмогорова, Хинчппа (задача о разделении двух смесей распределения) и в дальнейшем развиты в теории статистических решений и активно изучавшимися с середины прошлого века задачами сопоставления нового объекта одному из заданных классов, разделения множества объектов на несколько непересекающихся классов и др. В России это направление интенсивно развивается в ВЦ РАН (Журавлев, Рудаков, Рязанов, Дюкова), ИММ Уро РАН (Еремин, Мазуров, Хачай), а также ИМ СО РАН (Кельманов, Гимади, Пяткин).
Задачи анализа и распознавания данных, как правило, связаны с содержательными проблемами, в которых требуется по результатам измерения или вычисления характеристик объектов принять решение о взаимосвязи объектов между собой и с новыми объектами.
Следующий за формулированием содержательной проблемы шаг — построение конструктивной модели анализируемых данных. Эта модель содержательной проблемы анализа данных практически всегда формулируется в форме задачи оптимизации критерия или функционала (минимума суммы квадратов уклонений, максимума правдоподобия, максимума апостериорной вероятности и др.), адекватно отражающего проблему. Многообразие критериев в комбинации с многообразием моделей (структур) анализируемых данных порождает широкий спектр редуцированных экстремальных задач, к которым сводится поиск оптимального решения. При этом сходные в содержательном плане проблемы сводятся к отличающимся экстремальным задачам. Зачастую простейшие и давно известные проблемы анализа данных сводятся к решению экстремальных задач, для которых эффективные алгоритмы с оценками точности решения неизвестны.
Этап построения модели в общем случае включает в себя выделение информативных признаков объектов, определение «меры близости» между объектами на основе их характеристик и выбор критерия или функционала, подлежащего оптимизации.
Следующим за получением редуцированной задачи оптимизации этапом является построение алгоритма нахождения решения оптимизационной задачи. Алгоритмы решения оптимизационной задачи анализа данных делятся на две основные категории: on-line и off-line.
Первые ориентированы на нахождение решения задачи за минимальное время, или построение так называемых «быстрых» алгоритмов. Среди этих алгоритмов преобладают эвристики, которые позволяют иаходигь приближённое решение, которое могло бы считаться приемлемым с точки зрения конкретных приложений, однако не дающие теоретических гарантий но точности.
Алгоритмы второго типа нацелены на получение решения с заданной точностью. Построение таких алгоритмов связано с анализом статуса алгоритмической сложности оптимизационных задач и получение теоретических оценок точности решения. Среди недостатков off-line алгоритмов можно отметить высокую трудоёмкость, возникающую в результате необходимости решения нетривиальных, затратных в вычислительном плане задач комбинаторной оптимизации [58].
Поскольку выбор различных информативных признаков и критериев приводит к различным решениям, и даже один и тот же алгоритм может выдавать различные результаты в зависимости о г варьирования его параметров, следующим за построением алгоритма этапом является оценка качества и интерпретация результатов. Для оценки качества используются формальные (численное моделирование) или неформальные тесты (мнения экспертов, визуализация результатов, сопоставление результатов, полученных различными способами и др.). Если оценка качества работы алгоритма анализа или распознавания данных показывает недостаточную приемлемость результатов с точки зрения прикладной проблемы, то цикл решения проблемы возобновляется, с выбором других информативных признаков, критериев и т.д.
Значительное число возникающих в рамках анализа данных математических проблем относится к классу труднорешаемых (NP-трудных) оптимизационных задач [19]. Универсальным методом решения подобных задач является выбор наилучшего решения из всей совокупности вариантов решения путем их прямого перебора. Однако использование этого метода представляется малопригодным для практической реализации, даже с учётом самых впечатляющих возможностей современных компьютеров, так как число допустимых вариантов решения и, следовательно, время решения проблемы увеличивается экспоненциально с ростом размерности задачи. Эта экспоненциальная зависимость стимулирует поиск приближённых алгоритмов с оценками точности решения, таких, что время решения задачи с помощью этих алгоритмов было бы полиномом от размерности задачи.
Выяснение сложностного статуса позволяет решить вопросы о существовании, как точного полиномиального алгоритма решения редуцированной экстремальной задали, так и эффективного алгоритма, гарантирующего оптимальность решения соответствующей прикладной проблемы.
Вопрос выяснения статуса алгоритмической сложности требует особой тщательности, примером чему может служить одна из наиболее известных задач анализа данных — задача MSSC (от англ. Minimum Sum-of-Squares Clustering) кластеризации евклидовых векторов по критерию минимума суммы квадратов расстояний — на протяжении нескольких десятков лет считавшейся труднорешаемой несмотря на ошибки и неточности во всех известных вплоть до недавнего времени доказательствах этого факта.
К числу актуальных относится задача разбиения (по критерию минимума суммы квадратов расстояний) конечного множества векторов евклидова пространства на кластеры фиксированной мощности в случае, когда центр одного из кластеров определять не требуется. Эта задача в постановочном плане близка к задаче MSSC, но не эквивалентна ей. Она важна для ряда приложений, связанных с помехоустойчивым анализом данных [39]. В настоящей работе изучается простейший, но важный случай этой задачи, когда заданное множество требуется разбить па два кластера.
В приложениях, связанных с помехоустойчивой обработкой сигналов, актуальны задачи анализа и распознавания числовых и векторных последовательностей, структура которых в отсутствие помехи содержит ненулевые информационно значимые фрагменты или векторы, чередующиеся с нуль-значными фрагментами. В частных случаях эти задачи можно трактовать как задачи обнаружения разладки (изменения свойств) случайной последовательности. В тысячах публикаций рассматриваются разнообразные постановки задач и последовательные (on-line) алгоритмы обработки подобных последовательностей, основанные на фундаментальных работах Вальда [165] и ряда других отечественных и зарубежных исследователей. В то же время эффективные апостериорные (off-line) алгоритмы с оценками точности для большинства из этих задач отсутствуют. Несколько подобных задач, для которых off-line алгоритмы с оценками точности ранее не были известны, рассматриваются в настоящей работе.
Методы исследований. Основными инструментами исследований служили методы дискретной оптимизации, среднеквадратического приближения, математической статистики и полиномиальной сводимости. При обосновании приближенных алгоритмов применялась специальная техника, позволяющая находить гарантированную границу уклонения приближенного решения от оптимального. Эффективная разрешимость задач устанавливалась конструктивно (алгоритмически).
Теоретическая и практическая значимость. Работа носит теоретический характер. Её результаты могут быть использованы в математической теории распознавания образов и классификации, а также в теории дискретных экстремальных зада^1,1 например, в исследованиях, связанных с изучением алгоритмической сложности. предложенные алгоритмы могут использоваться в компьютерных технологиях, ориентированных на решение прикладных задач.
Йа защиту выносится совокупность результатов по исследованию алгоритмической сложности, а также эффективные алгоритмы с гарантированными оценками точности для задач дискретной оптимизации, к решению которых сводятся актуальные проблемы анализа данных, распознавания образов и классификации.
Апробация работы. Результаты диссертации докладывались на следующих международных и российских конференциях: XLV и XLVI международных студенческих конференциях «Студент и научно-технический прогресс» (г. Новосибирск, 2007,
2008), 15-й международной конференции «Проблемы теоретической кибернетики» (г. Казань, 2008), XIV Байкальской международной школе-семинаре «Методы оптимизации и их приложения» (г. Северобайкальск, 2008), международной конференции "Алгоритмический анализ неустойчивых задач» (г. Екатеринбург, 2008), международной конференции «Classification, Forecasting, Data Mining» (г. Варна, Болгария,
2009), IV Всероссийской конференции «Проблемы оптимизации и экономические приложения» (г. Омск, 2009), 14-й Всероссийской конференции «Математические методы распознавания образов» (г. Суздаль, 2009), Российской конференции «Дискретная оптимизация и исследование операций» (Алтай, 2010), 8-ой Международной конференции «Интеллектуализация обработки информации» (г. Пафос, Кипр,
2010), XIV Всероссийской конференции «Математическое программирование и приложения» (г. Екатеринбург, 2011), V Всероссийской конференции «Проблемы оптимизации и экономические приложения» (г. Омск, 2012), IX Международной конференции «Интеллектуализация обработки информации» (Черногория, г. Будва, 2012). Кроме того, результаты работы обсуждались на семинарах кафедры Теоретической кибернетики Новосибирского государственного университета и на семинарах отдела Теоретической кибернетики Института математики им. C.JI. Соболева СО РАН.
Публикации. Представленные в диссертационной работе результаты опубликованы в работах [22-33,87,88].
Структура и объем диссертации. Диссертация изложена па 82 страницах и включает введение, две главы, заключение и список цитируемой литературы, включающий 171 источник.
Основные результаты диссератционной работы заключаются в следующем:
1. Доказана ОТ-пол нота задачи МЭЭС — кластеризации конечного множества векторов евклидова пространства по критерию минимума суммы квадратов расстояний — в случае, когда размерность пространства является, а число кластеров не является частью входа задачи.
2. Построен эффективный 2-приближённый алгоритм для решения КР-трудной задачи разбиения конечного множества векторов евклидова пространства на два кластера фиксированной мощности по критерию минимума суммы квадратов расстояний от элементов кластера до его центра в случае, когда центр одного из кластеров совпадает с началом координат.
3. Для этой же задачи обоснована приближённая полиномиальная схема (РТАЭ).
4. Разработаны полиномиальные алгоритмы, позволяющие находить оптимальное решение экстремальных задач, к которым сводится проблема помехоустойчивого ой'-Ппе распознавания векторной последовательноегн как структуры, включающей повторяющийся вектор, при наличии «посторонних» векторов-вставок: а) из произвольного множества ненулевых векторов; б) из заданного алфавита. Предполагается, что помеха яв шется выборкой из нормального распределения с диагональной матрицей ковариаций, а критерием принятия решения является максимум функционала правдоподобия.
Факт КР-нолноты указанного случая задачи МЭБС установлен впервые.
Эффективные алгоритмы с константной оценкой точности, а также схема РТАЭ для решения задачи разбиения векторов евклидова пространства на два кластера фиксированной мощности в случае, когда не требуется определять центр одного из кластеров, до настоящего времени отсутствовали.
Полиномиальные оЙ'-Ппс алгоритмы, гарантирующие оптимальное решение задач, к которым сводятся указанные выше проблемы анализа и распознавания последовательностей, предложены впервые.
Работа носит теоретический характер. Её результаты могут быть использованы в математической теории распознавания образов и классификации, а также в теории дискретных экстремальных задач, например, в исследованиях, связанных с изучением алгоритмической сложности. Предложенные алгоритмы могут использоваться в компьютерных технологиях, ориентированных на решение прикладных задач.
Таким образом, в работе найдено решение научной проблемы, имеющей важное теоретическое и прикладное значение в области анализа структурированных данных и распо шавания образов.
Заключение
1. Абусев P.A. О сравнении поточечной и групповой классификации в случае многомерного распределения // Статистические методы оценивания и проверки гипотез: Межвуз. сб. науч.тр. — Пермь, 1982.— С. 3-9.
2. Абусев P.A. Групповая классификация. Решающие правила и их характеристики-Пермь. 1992.-218 С.
3. Астафьева Н.М. Вейвлет-анализ: основы теории и примеры применения // Успехи физических наук. 1998.-Т. 1GG. №11.-С. 1145-1170.
4. Боровков A.A. Математическая статистика. — М.: Наука, 1984, —471 С.
5. Бродский Б.Е., Дарховский Б.С. Сравнительный анализ нспараметричсских методов скорейшего обнаружения разладки // Теория вероятностей и ее применения. 1990-Т. 35, 4.-С. 655-С68.
6. Вапник В. Н. Червоненкис, А.Я. Теория распознавания образов —М.: Наука, 1974 — 416 С.
7. Васильев В.И. Распознающие системы. Справочник — Киев.: Наукова думка,1983 — 424 С. t1.
8. Величко В.М. Алгоритм распознавания изолированных слов //В кн.: Тезисы докладов Всесоюзной школы-семииара APC0-I3 — Новосибирск, 1984 —С. 85-86.
9. Вптязев В.В. Вейвлст анализ временных рядов. Учебное пособие. — СПб.: Изд-во Санкт-Пстсрургского университета. 2001.
10. Воробьев В.И. Теория и практика вейвлет-преобразования — СПб.: Издательство ВУС, 1999 -204 С.
11. Гпмади Э.Х., Кельмапов А. В., Кельмапова М. А., Хамидуллии С. А. Апостериорное обнаружение в числовой последовательности квазипериодического фрагмента при заданном числе повторов // Сиб. жури, иидустр. математики. — 2006 -Т. 9, № 1(25). — С. 55-74.
12. Гпмади Э. X., Пяткин А. В., Рыков И. А. О полиномиальной разрешимости некоторых задач выбора подмножества векторов в евклидовом пространстве фиксированной размерности // Дискретный анализ и исследование операций. — 2008.-Т. 15, №6.-С. 11-19.
13. Гэрп М., Джонсон Д. Вычислительные машины и труднорешаемые задачи: Пер. с апп.-М.: Мир, 1982-416 С.
14. Дарховскпй Б.С. Апостериорное обнаружение момента «.разладки» случайной последовательности // Теория вероятностен и се применения, 1980 —Т. 25. Вып.1. С.476-489.
15. Дарховскпй B.C. Непараметрпческий метод для апостериорного обнаружения момента «разладки» последовательности независимых случайных величия // Теория вероятностей и ее применения, 1976 —Т. 21. Вып. 1 —С. 180-134.
16. Долгушев A.B., Кельманов A.B. К вопросу об алгоритмической сложности одной задачи кластерного анализа // Дискретный анализ и исследование операций, 2010-Т. 17, № 2-С. 39-45.
17. Долгушев A.B. Кельманов A.B. Об одной задаче поиска вектора в векторном алфавите // Материалы IV Всероссийской конференции «Проблемы оптимизации и экономические приложения» — Омск, 29 шоня-4 июля 2009. —С. 123.
18. Долгушсв А.В., Ксльманов А.В. Приближенный алгоритм для решения одной задачи кластерного анализа // «Дискретный анализ и исследование операций»,2011 . 18, № 2-С. 29-40.
19. Долгутпев А.В., Кельманов А.В. Приближённый алгоритм решения одной задачи кластерного анализа // Тез. докл. Всероссийской конференции «Математическое программирование и приложения» — Екатеринбург, 2011 —С. 266-267.
20. Долгушев А.В., Кельманов А.В. Шеимайер В.В. Аппроксимациоипая схема для одной задачи кластерного анализа // Материалы V Всероссийской конференции «Проблемы оптимизации и экономические приложения» — Омск, 2012 —С. 120.
21. Каминаскас В.А. Шииените Д.А. Обнаружение изменения параметров процесса авгорегрессии // Тр. АН Лит.ССР, 1975-серия 1.Б, Т. 4(89)-С. 143-147.
22. Кельманов А.В. О сложности некоторых задач анализа данных // Жури, вы-чнел. матем. и мат. физики, 2010-Т 50, № 11-С. 2045-2051.
23. Кельманов А.В. Проблема о fi-line обнаружения повторяющегося фрагмента вчисловой последовательности // Труды Института математики и механики УрО
24. РАН. 2008. - Т. 14, № 2. - С. 81-88. i/
25. Кельманов A.B., Окольнишникова Л.В. Апостериорное совместное обнаружение и различение подпоследовательностей в квазипериодической последовательности // Сибирский журнал индустриальной математики, 2000— Т.З, №2(6). С. 115-139.
26. Кельманов A.B., Пяткип A.B. О сложности некоторых задач поиска подмножеств векторов и кластерного анализа // Жури, вычисл. матем. и мат. физики, 2009. Т. 49, № 11. — С. 2059-2067.
27. Кельманов A.B. Хамидуллин С.А., Окольнишникова Л.В. Апостериорное обнаружение одинаковых подпоследовательностей-фрагментов в квазипериоди-чсской последовательности // Сиб. журн. пндустр. математики, 2002 — Т.5, №2(10)-С. 94-108.
28. Кельманов A.B., Хамидуллин С.А., Окольнишникова Л.В. Апостериорное обнаружение одинаковых подпоследовательностей-фрагментов в квазипериодиче-скои последовательности // Сиб. журн. пндустр. математики, 2002 —Т. 5, № 2 (10)-С. 94-108.
29. Кельманов A.B., Хамидуллин С.А. Апостериорное обнаружение заданного числа одинаковых подпоследовательностей в квазипериодической последовательности /, Журн. вычисл. математики и мат. физики, 2001,—Т. 41, № 5. —С. 807-820.
30. Кельманов A.B., Хамидуллин С.А., Окольнишникова Л.В. Распознавание квазипериодической последовательности, включающей одинаковые подпоследовательности-фрагменты / / Сиб. журн. индустр. математики, 2002-Т. 5, №4(12)-С. 38-54.
31. Клигене Н. Исследование точности оценки максимального правдоподобия момента изменения параметров уравнения авторсгрсссии // Статистические проблемы управления — Вильнюс: Ин-т математики и кибернетики АН ЛитССР, 1975-Вып. 12.-С. 42-70.
32. Клигене Н. Методы обнаружения моментов изменения свойств случайных процессов // Автоматика и телемеханика, 1983 —№10. —С. 5-56.
33. Клигене Н.И. Оценка момента изменения параметров распределения случайных последовательностей // Теория вероятностей и ее применения, 1973 — Т. 18, Вып. 3-С. 677-678.
34. Клигене Н.И. Точное распределение оценки максимального правдоподобия момента изменения параметров авторегрессии // Статистические проблемы управления—Вильнюс: Изд-во Ин-т математики и кибернетики АН ЛитССР, 1978.— М. 31.-С. 929.
35. Клигис В.И. Групповая классификация многомерных марковских последовательностей // Статистические проблемы управления — Вильнюс, 1981 — Ёып. 50-С. 57-74.
36. Линейка А. Определение моментов изменения свойств авторегрессиониой последовательности // Статистические проблемы управления — Вильнюс: Ин-т математики и кибернетики АН ЛитССР, 1977 —Вып. 24.— С. 27-71.
37. Дипейка А. Определение моментов изменения свойств авторегрессионных последовательностей с неизвестными параметрами. В кн.: Статистические проблемы управления— Вильнюс: Институт физики и математики АН ЛитССР, 1982 — Вып. 54-С. 9-28.
38. Луме.чьский В.Я. Один алгоритм обнаружения момента времени изменения свойств случайного процесса // Автоматика и телемеханика, 1972 —№ 10 — С. 67-73.
39. Моптвилас А. Обработка результатов наблюдений при определении изменения свойств случайных сигналов // Статистические проблемы управления —Вильнюс: Ин-т математики и кибернетики АН ЛитССР 1973 —Вып. 7 —С. 41-53.
40. Моптвилас A.M. Определение изменений свойств случайных сигналов при неизвестных параметрах этих сигналов. В кн.: Статистические проблемы управления—Вильнюс: Институт физики и математики АН ЛитССР, 1973 —Вып. 7 —1. С. 8-20
41. Никифоров И. В. Последовательное обнаружение изменения свойств временных рядов — М.: Наука, 1983-199 С.
42. Пападпмитрпу X., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность: Пер. с англ. —М.: Мир. 1985 — 512 С.
43. Тельксиис Л. Определение изменения свойств случайных процессов при неполных априорных данных // Статистические проблемы управления — Вильнюс: Ий-г математики и кибернетики АН ЛитССР, 1975 —Вып. 12, —С. 9-26.
44. Тельксиис Л. Определение наиболее вероятных изменений свойств многомерных динамических систем с неизвестными параметрами // Статистические проблемы управления. — Вильнюс: Ин-т математики и кибернетики АН ЛитССР, 1977 — Вып. 24.-С. 9-26.
45. Тельксиис Л.А. Определение наиболее вероятного момента времени изменения характера случайного процесса // Нелинейные и оптимальные системы, Тр. В^ссс. спмп. по статистическим проблемам в технической кибернетике —М.: Наука. 1971-С. 223-228.
46. Трчькснис Л. О применении оптимального байесова алгоритма обучения при определении момента времени изменения свойств случайных сигналов // Автоматика и телемеханика, 1969 —№ б —С. 52-58.
47. G3J Ту Дж. Гонсалес Р. Принципы распознавания образов — М.: Мир, 1978 — 411 С.
48. Фишер Р.А. Статистические методы для исследователей — М.: Госстатиздат, 1958-267 С.
49. Фор А. Восприятие и распознавание образов —М.: Машиностроение, 1989 — 272 С.
50. Фу К. Структурные методы в распознавании образов —М.: Мир, 1977 — 319 С.
51. Фукунага К Введение в статистическую теорию распознавания образов —М.: Паука. 1979-367 С.
52. Ширяев А.Н. Задача скорейшего обнаружения нарушения стационарного режима //Докл. АН СССР. 1961-Т. 138, №5.-С. 1039-1042.
53. Ширяев А.Н. Обнаружение спонтанно возникающих эффектов // Докл. АН СССР. 1961-Т. 138, №4. -С. 799-801.
54. Aloise D., Deshpande A., Hansen P., Popat P. NP-Hardness of Euclidean Sum-of-Squares Clustering // Les Cahiers du GERAD, G-2008-33, 2008-4 P.
55. Aloise D and Hansen P. On the Complexity of Minimum Sum-of-Squarcs Clustering /' Les Cahiers du GERAD, G-2007-50, 2007- 12 P.
56. Aloise D. Hansen P., and Liberti L. An improved column generation algorithm for minimum ынп-of-squares clustering // Mathematical Prgramming, 2010.
57. Anderberg M. Cluster Analysis for Applications // New York: Academic, 1973.
58. Aminian F., Aminian M., Collins H.W. IEEE Transactions on Instrumentation and Measurement // 2002-Vol. 51, Part 3-P. 544-550.
59. Bagiiov A.M., Yearwoord ,J. Hierarchical grouping to optimize an objective function // European Journal of Operational Research. 170:578-596, 2006.
60. Bagshaw M., Johnson R.A. Sequential procedures for detecting parameter changes in a time series model // J. Amer. Statist. Assoc. 1977, —72, 359 —P. 593-597.
61. Bandelt H.J., Dress A.W.M. Weak Hierarchies Associated with Similarity Measures: an Additive Clustering Technique // Bulletin of Mathematical Biology, 1989 — Yol. 51. P. 133-166.
62. Bezdek .J.C. Pattern Recognition with Fuzzy Objective Function Algorithms // Plenum. New York, 1981.i
63. Box G.E.P. Tiao G.C. A change in level of a nonstationary time series // Biometrika, 1965. № 1-2-P. 181-192.
64. Brucker P. On the Complexity of Cluestering Problems // Optimization and Operations Research, Lecture Notes in Economics and Mathematical Systems, 1978 — Vol. 157. P. 45-54.
65. Brusco M.J. A repetitive branch-and-bound procedure for minimum within-cluster sum of squares partitioning // Psychometrika, 71:347-363, 2006.
66. Chen H.L. Chuang K.T., and Chen M.S. Labeling unclustered categorical data into clusters based on the important attribute values // Proceedings of the Fifth IEEE International Conference on Data Mining (ICDM'05), 2005.
67. Chernoff H., Zacks S. Estimating the current mean of a normal distribution which is subjected to a change in time // Ann. Math. Statist, 1964 —Vol. 35, № 3 —P. 9991018.
68. Davis M. The application of nonlinear filtering to fault detection in linear systems // Automatic Control, IEEE Transactions on, 1975-Vol. AC-20, № 2-P. 257-259.
69. Delattre M. and Hansen P. Classification d'homogeneite maximum // Actes du Colloque Analyse de Donnrees et Informatique, INRIA 1, 1977 —P. 99-104.
70. Dhillon I.S. and Modlia D.S. A data-clustering algorithm on distributed memory multiprocessors // Lecture Notes in Artificial Intelligence, 1759:245-260, 2002.
71. Dolgushev A.V. and Kermanov A.V. On the Algorithmic, Complexity of a Problem in Cluster Analysis // Journal of Applied and Industrial Mathematics, 2011 — Vol. 5, No. 2-PP. 191-194.
72. Dolgushev A.V. and Kel'manov A.V. An Approximation Algorithm for Solving a Problem of Cluster Analysis // Journal of Applied and Industrial Mathematics, 2011 — Vol. 5, No. 4-PP. 551-558.
73. Diday E. Oulers and Overlapping Clusteis by Pyramids // Research Report, 730, INRIA, France, 1987.
74. Diehr G. Evaluation of a branch and bound algorithm for clustering // SIAM Journal Scientific and Statistical Computing, 6:268-284, 1985.
75. Drincas P., Frieze A., Kannan R., Vcmpala S., Vinay V. Clustering Large Graphs Via the Singular Value Decomposition // Machine Learning. 2004 —Vol. 56 —PP. 9-33.92j Duda R , Hart P., and Stork D. Pattern Classification // New York, Wiley, 2001.
76. Everitt B., Landau S., and Leese M. Cluster Analysis // London: Arnold, 2001.
77. Fasulo D An analysis of recent work on clustering algorithms // Technical Report UW-CSE-01-03-02, University of Washington, 1999.
78. Fischei B. Roth V., and Buhmann J.M. Clustering with the connectivity kernel // Advances in Neural Information Processing Svstems, 16, 2004.
79. Fogel D. An introduction to simulated evolutionary optimization // IEEE Trans. Neural Netw.-Vol. 5, No. 1 —PP. 3-14.
80. Fradkin D., Muchnik I.B., and Streltsov S Image compression in real-time multiprocessor systems using divisive K-means clustering // In International Conference on Integration of Knowledge Intensive Multi-Agent Systems (KIMA'03) — PP. 506-511.
81. Carey M.R., Johnson D.S. Computers and Intractability: A Guide to the Theory of NP-Completeness — Fieeman, San Francisco, CA, 1979.
82. Glover F. Tabu search, part I // ORSA J. Comput., 1989-Vol. 1, No. 3-PP. 190-206.
83. Guan Y., Ghorbani A.A., and Belacel N. Y-means: a clustering method for intrusion detection // In IEEE Canadian Conference on Electrical and Computer Engineering-PP. 1083-1086.
84. Gusfield D. Algorithms on Strings. Trees and Sequences: Computer Science and Computational Biology // Cambridge, U.K.: Cambridge Univ. Press, 1997.
85. Franti P. Virmajoki O., and Kaukoranta T. Branch-and-bound technique for solving optimal clustering // In International Conference on Pattern Recognition (1CPR'02) — PP. 232-235.
86. Hansen P. and Aloisc D. A survey on exact methods for minimum sum-of-squares clustering // http://www.math.iit.edu/Buck65files/nisscStLouis.pdf
87. Hansen P and Delattre M Complete-link duster analysis by graph coloring // Journal of the American Statistical Association, 73.397-403, 1978.
88. Hansen P. and Jaumard B. Cluster Analysis and Mathematicla Programming // Les Cahiers du GERAD, G-97-10. 1997-36 P.
89. Hinkley D. V., Hinkley E. A. Inference about the change-point in a sequence of binominal variables // Biometrica, 1970 —Vol. 57 —PP. 477-488.
90. Jain A.K. and Dubes R.C. Algorithms for clustering data // New Jersey, Englewood Cliffs- Prentice HallPattern, 1988.
91. Jain A.K. Duin R P.W. and Mao J. Statistical Pattern Recognition- A Review // IEEE Transactions 011 Pattern Analysis and Machine Intelligence, 2000 —Vol. 22, No. l.-P. 4-37.
92. Jolion J.M., Meer P., and Bataouche S. Robust Clustering with Applications 111 Computer Vision // IEEE Transactions on Pattern Analysis and Machine Intelligence. 1991-Vol. 13, No. 8-PP. 791-802.
93. Jones R.H., Growell D.H., Kapunial L.E. A method for detecting change in a time series applied to newborn EEC // Elec-troenceph. Clin. Neurophysiol, 1969 — Vol. 27-PP. 87-93.
94. Jones R.H., Growell D.H., Kapunial L E. Change detection model for serially conelatcd multivariate data // Biometrics. 1970-Vol. 26, No. 2-PP. 269-281.
95. Kanungo T., Mount D M., Netanyahu N. S., Piatko C.D., Silverman R., Wu A. Y. An Efficent I<-Means Clustering Algorithm: Analysis and Implementation // IEEE Transactions on Pattern Analysis and Machine Intelligence, 2002 —Vol. 24, Part 7 — PP. 881-892.
96. Kel'manov A.V., Jeon B. A Posteriori Joint Detection and Discrimination of Pulses in a Quasiperiodic Pulse Train // IEEE Transactions on Signal Piocessing. — 2004. — Vol. 52. №. 3 P. 1-12.
97. Kel'manov A.V., Khamidullin S.A. A Posterioii Joint Detection and Discrimination of a Given Number of Subsequences in a Quasiperiodic Sequence // Pattern Recognition and Image Analysis 2000. - Vol. 10. № 3. - P. 379-388.
98. Kolniogorov A. N. Confidence limits for an unknown distribution function // AMS, 1941-Vol. 12-PP. 461-463.128| Koontz W L G, Narcndra PM., and Fukunaga K. A branch and bound clustering algorithm ,'/ IEEE Trans. Coniput,, 1975-Vol. C-24-PP. 908-915.
99. Kumar A., Sabliarwal Y., and Sen S. A simple linear time (1 + ^-approximation algorithm for K-means clustering in any dimensions // Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), 2004 — PP. 454-462.
100. MacQueen J.B. Some Methods for Classification and Analysis of Multivariate Obseivations // Pioc. 5-th Beikeley Synip. of Mathematical Statistics and Probability. 1967-Vol. PP. 281-297.
101. Mahajan M., Nimbhorkar P., Varadarajan K. The Planar K-means Problem is NP-Hard // Lecture Notes in Computer Science, 2009-Vol. 5431-PP. 284-285.
102. McCormick Jr. W.T., Shweitzer P.J., and White T.W. Problem Decomposition and Data Regularization by a Clustering Technique // Operations Research, 993-1009, 1972.
103. Meila M. The uniqueness of a good optimum for K-means // ACM International Conference Proceeding Series, 148:625-632, 2006.
104. Merle O. du. Hansen P., Jaumard B., and Mladenovic N. An interior point algorithm for minimum sum-of-squares clustering // SIAM J. Sci. Comput., 21:1485-1505, 2000.
105. Merz P An iterated local search for minimum sum-of-squares clustering // Lecture Notes in Computer Science, 2810'286-296. 2003
106. Muller I< . Mika S., Ratscli G. Tsuda K., and Scliolkopf B., An introduction to kernel-based learning algorithms j' IEEE Trans. Neural Netw., 2001 ol. 12. No. 2 — PP. 181-201.
107. Neyman J. and Pearson E. S. On the Problem of the Most Efficient Tests of Statistical Hypotheses // Phil. Trans. R. Soc. Loud., 1933-Vol. 231-PP. 289-337.
108. Page E. S. Continuous inspection schemes // Biometrica, 1954 — Vol. 41 — PP. 100115.
109. Peng J. and Wei Y. Appioximating k-means-type clustering via semidefinite programming // SIAM Journal on Optimization, 18:186-205. 2007.
110. Scholkopf B. and Smola A., Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond // Cambridge, MA: MIT Press, 2002.
111. Sherali H D. and Adams W.P. A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems // Netherlands: Kluwer Academic Publishers, 1999,-Vol. 31.
112. Spath H. Cluster analysis algorithm for data reduction and classification of objects /,/ John Wiley and sons, New York, 1980-P. 60-61.
113. Steinley D. K-means clustering: A half-century synthesis // British Journal of Mathematical and Statistical Psychology, 59:1-34. 2006.
114. Taillard E.D. Heuristic methods for large centroid clustering problems // Journal of Heuristics, 9:51-73, 2003.
115. Vinod H.D. Integer programming and the theory of grouping // J. Amer. Stat. Assoc., 64:506-519, 1969.
116. Walcl A. Sequential analysis. New York: John Wiley, 1947-212 P.
117. Wang J. A linear assignment clustering algorithm based on the least similar cluster representatives // IEEE Transactions on systems, man, and cybernetics, Part A:Ssystems and humans, 29:100-104, 1999.
118. Welch W.J. Algorithmic complexity: three up-hard problems in computational statistics. Journal of Statistical Computation and Simulation, 15:17-25, 1982.
119. Willsky A.S., Jones H.L. A generalised likelihood ratio approach to detection and estimation of jumps in linear systems // IEEE Trans, on Autom. Control. 1976 — AC-21, l.-PP. 108-112.
120. Wirth H. Algorithms + Data Structures = Programs // New Jersey: Prentice Hall. 1976 - 366 P.
121. Zliuaug X. Huang Y. Palaniappan K., and Zhao Y. Gaussian mixture density modeling, decomposition, and applications // IEEE Trans. Image Process., 1996 — Vol. 5, No. 9 — PP. 1293-1302.171. http://math.nsc.ru/ sergc/qpsl/
