Алгоритмы с оценками для решения задач анализа данных тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат физико-математических наук Долгушев, Алексей Владимирович

• Долгушев, Алексей Владимирович
• кандидат физико-математических наук
• 2012

Оглавление диссертации кандидат физико-математических наук Долгушев, Алексей Владимирович

Введение

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. Разработаны полиномиальные алгоритмы, позволяющие находить оптимальное решение экстремальных задач, к которым сводится проблема помехоустойчивого ой'-Ппе распознавания векторной последовательноегн как структуры, включающей повторяющийся вектор, при наличии «посторонних» векторов-вставок: а) из произвольного множества ненулевых векторов; б) из заданного алфавита. Предполагается, что помеха яв шется выборкой из нормального распределения с диагональной матрицей ковариаций, а критерием принятия решения является максимум функционала правдоподобия.

Факт КР-нолноты указанного случая задачи МЭБС установлен впервые.

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

Полиномиальные оЙ'-Ппс алгоритмы, гарантирующие оптимальное решение задач, к которым сводятся указанные выше проблемы анализа и распознавания последовательностей, предложены впервые.

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

Таким образом, в работе найдено решение научной проблемы, имеющей важное теоретическое и прикладное значение в области анализа структурированных данных и распо шавания образов.

Заключение

Список литературы диссертационного исследования кандидат физико-математических наук Долгушев, Алексей Владимирович, 2012 год

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/