автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Методы двухэтапной и многокритериальной кластеризации данных выборок больших объемов

На правах рукописи

Киреев Василий Сергеевич

МЕТОДЫ ДВУХЭТАПНОЙ И МНОГОКРИТЕРИАЛЬНОЙ КЛАСТЕРИЗАЦИИ ДАННЫХ ВЫБОРОК БОЛЬШИХ ОБЪЕМОВ

05 13 01 - системный анализ, управление и обработка информации (научное обслуживание)

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Автор

иоз169451

Москва 2008

003169451

Работа выполнена в Московском инженерно-физическом институте (государственном университете)

Научный руководитель кандидат технических наук,

доцент Синицын Сергей Владимирович

Официальные оппоненты доктор физико-математических наук,

профессор Крянев Александр Витальевич Московский инженерно-физический институт (государственный университет), кафедра «Прикладная математика»

доктор технических наук, Емец Евгений Павлович Госкорпорация «РОСАТОМ»

Ведущая организация Московский государственный университет

экономики, статистики и информатики

Защита диссертации состоится 4 июня 2008 года в 15 часов 00 минут на заседании диссертационного совета Д 212 130 03 в Московском инженерно-физическом институте (государственном университете) по адресу 115409, г Москва, Каширское ш, 31, тел (495) 323-95-26, 324-84-98, ауд 408, главный корпус

С диссертацией можно ознакомиться в библиотеке института

Автореферат разослан 30 апреля 2008 года

Ученый секретарь диссертационного совета

Шумилов Ю Ю

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы

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

Задача кластеризации или таксономии впервые была рассмотрена в 1930-х годах Эту проблему в ее различных аспектах изучали как зарубежные так и отечественные исследователи, в том числе МакКуин Д , Ланс У , Уильяме Д , Хартиган Д , Вонг М , Кохонен Т, Фрицке Б , и Колмогоров А Н, Загоруйко Н Г , Елкина В Н , Айвазян С А , Мхитарян В С , Шумский С А , и другие Проблема кластеризации данных обычно рассматривается в двух различных вариантах постановки - нахождения естественного расслоения кластеров и нахождения кластеров в виде групп близких объектов Первый вариант может и не иметь решения, например, в случае, если исходные данные представляют собой один большой кластер, однако второй вариант имеет решение всегда, и представляет наибольший интерес для исследователей

Кластерные процедуры для нахождения схожих объектов разделяют на два основных типа - агломеративные (дивизимные) и итеративные Агломеративные процедуры основаны на пошаговом объединении пары ближайших кластеров (наблюдений) и пересчете матрицы расстояний В итеративных процедурах на каждом шаге работы рассматривается только один объект, и производится его отнесение к одному из кластеров, пока не будет получено устойчивое разбиение Пересчет матрицы расстояний приводит к тому, что вычислительная сложность иерархических процедур резко возрастает при увеличении объема выборки Итеративные методы сильно зависят от выбора начального разбиения, что приводит к необходимости повторного решения задачи с новыми условиями Недостатки рассмотренных подходов не позволяют применять их как универсальные, круг их применения ограничивается данными сравнительно небольших объемов (~ 10 -102 объектов) при априори известной информации о кластерной структуре

Вышесказанное определяет актуальность настоящей работы, связанной с разработкой математического, алгоритмического и программного обеспечения методов обработки больших объемов информации( ~ 103 объектов), определением критериев и моделей описания кластерных разбиений

Целью диссертационной работы является решение важной научной задачи, заключающейся в систематизации известных методов кластерного анализа и разработке новых, предназначенных для достижения точности решения на больших объемах информации, их теоретическое исследование, экспериментальное обоснование и анализ эффективности на основе статистических исследований

Методы исследования

При разработке математического аппарата в диссертационной работе используются методы теории математической статистики, методы дискретной оптимизации и методы многокритериальной оптимизации При разработке программного обеспечения используются методы объектно-ориентированного программирования

Научная новизна работы заключается в следующем

1 Создана модель унифицированного формального описания наиболее известных методов кластеризации для проведения их сравнительного анализа С целью определения областей эффективного использования различных методов определена их вычислительная сложность Было показано, что эффективность традиционных иерархических методов решения задачи таксономии резко снижается при увеличении объема исходных данных, а итеративные методы не могут обеспечить качество решения для выборок больших объемов по нескольким критериям

2 Впервые предложен метод «карманной» кластеризации для решения задачи таксономии на выборках большого объема и построения разбиения с возможностью выбора оптимального числа кластеров Оценка предложенного метода на предмет вычислительной сложности показала, что метод «карманной» кластеризации решает задачу таксономии на выборках большого объема за субквадратичное время, в отличие от иерархических методов, характеризующихся кубической сложностью Использование в методе двухэтапной процедуры позволяет получать стабильные кластерные решения независимо от условий проведения первого этапа

3 Впервые предложен метод (^-кластеризации, основанный на решении задачи дискретной многокритериальной оптимизации, позволяющий построить оптимальное разбиение с учетом нескольких критериев качества Исследование свойств кластерных решений, получаемых с помощью метода (^-кластеризации,

проведенное на сгенерированных тестовых примерах показало, что примерно в 70% случаев найденные решения соответствуют истинной структуре кластеров объектов в пространстве признаков В частности, метод адекватно определяет истинное число кластеров

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

Практическая значимость состоит в следующем:

1 Выполнена программная реализации метода «карманной» кластеризации, которая использовалась для решения задачи сегментации потребителей банковских услуг на данных исследования, проведенного в 2003 году Международным Агентством Социальных и Маркетинговых Исследований (МАСМИ) В дальнейшем это программное обеспечение было внедрено в маркетинговый процесс торговой организации ООО «Мегагранд XXI Век», что подтверждается соответствующим актом о внедрении

2 Выполнена программная реализации метода (^-кластеризации, которая использовалась для решения задачи многофакторного анализа и выделения сегмента учителей-новаторов в рамках выполнения Национального проекта «Образование» в 200бг по программе «Совершенствование системы повышения квалификации и профессиональной переподготовки педагогических, инженерно-технических кадров общеобразовательных школ в области информационных и коммуникационных технологий (ИКТ) и смежных областей» В этом случае была собрана и обработана информация по использованию информационных и коммуникационных технологий (ИКТ) в профессиональной деятельности среди 5500 участников программы из семи федеральных округов, прошедших в 2006г повышение квалификации В результате полученных кластерных решений был сформирован пул учителей-инноваторов для дальнейшего использования их методического опыта в области ИКТ, что подтверждено соответствующими актами о внедрении.

Эксплуатация указанных программных реализаций показала, что все они обладают большой практической значимостью и могут быть рекомендованы к дальнейшему использованию Предложенные автором методы кластерного анализа несколько лет используются в лабораторных практикумах по курсам «Теория вероятностей и математическая статистика» кафедры «Кибернетика» и «Маркетинг и маркетинговые исследования» кафедры «Экономика и

управление» МИФИ, что подтверждается соответствующим актом о внедрении Результаты данной работы вошли в проект разработки информационно-образовательного портала МИФИ для самостоятельной работы студентов, выполняемый по Инновационной программе инженерно-физического образования для нового этапа развития ядерной науки и промышленности в рамках реализации Приоритетного национального проекта «Образование» С помощью предложенных методов осуществляется статистическая обработка результатов обучения и определяется рейтинг студентов

На защиту выносятся:

1 Новый метод «карманной» кластеризации для решения задачи таксономии на выборках большого объема, в котором успешно комбинируются характеристики точности иерархических схем и простота реализации итерационных процедур кластеризации

2 Новый метод (^-кластеризации для решения задачи построения оптимального разбиения с учетом нескольких критериев качества, обеспечивающий соответствие кластерных решений истинной структуре распределения объектов в пространстве признаков

3 Математическое, алгоритмическое и программное обеспечение нового метода «карманной» кластеризации, примененное для аналитического исследования социально-демографического и психологического статуса потребителей банковских услуг с целью более эффективной работы банков на финансовом рынке

4 Математическое, алгоритмическое и программное обеспечение нового метода (^-кластеризации, примененное в ряде образовательных проектов в целях совершенствования образовательного процесса

5 Содержательные результаты кластеризации данных, полученные в ходе использования программного обеспечения метода (^-кластеризации при реализации программы «Совершенствование системы повышения квалификации и профессиональной переподготовки педагогических, инженерно-технических кадров общеобразовательных школ в области информационных и коммуникационных технологий (ИКТ) и смежных областей» в рамках Национального проекта «Образование» в 2006г

6 Содержательные результаты, полученные в ходе использования программного обеспечения метода «карманной» кластеризации для решения задачи сегментации потребителей банковских услуг на данных исследования, проведенного Международным Агентством Социальных и Маркетинговых Исследований в 2003г

Достоверность разработанного математического, алгоритмического и программного обеспечения методов «карманной» и (^-кластеризации

подтверждается проведенными в работе экспериментальными и теоретическими исследованиями, сравнительным анализом результатов кластеризации разными методами, соответствующими актами о внедрении, представлением основных результатов диссертации на международных конференциях и выставках

Реализация и внедрение результатов работы

Научные результаты, полученные в диссертационной работе в виде методов и алгоритмов кластеризации данных выборок больших объемов и их программных реализаций для конечных пользователей, были использованы и внедрены-

• в ООО «Мегагранд XXI век» в маркетинговый процесс для обработки данных исследований потребительского рынка,

• в ЗАО «Академия АйТи» в рамках работы по Федеральной целевой программе развития образования на 2006-2010 годы при проведении многофакторного анализа компетенций в области информационно-коммуникативных технологий (ИКТ),

• в проекте разработки информационно-образовательного портала МИФИ для самостоятельной работы студентов, выполняемый по Инновационной программе инженерно-физического образования для нового этапа развития ядерной науки и промышленности в рамках реализации Приоритетного национального проекта «Образование»

Апробация работы

Основные результаты диссертационного исследования докладывались и обсуждались на международных и всероссийских конференциях и семинарах, в том числе

• Научные сессии МИФИ 2005-2008,

• Х1У-ХУ1 Международные научно-технические семинары «Современные технологии в задачах управления, автоматизации и обработки информации» (г. Алушта, 2005-2007 гг )

Структура работы

Диссертационная работа состоит из введения, четырех глав, заключения, трех приложений, списка использованной литературы и содержит 66 рисунков, 16 таблиц Общий объем без приложений 128 с (вместе с приложениями - 148 с )

Публикации

По материалам диссертации опубликованы 12 печатных работ общим объемом 1,5 печатных листа, в том числе статья в журнале из перечня изданий,

рекомендованных ВАК для опубликования основных результатов диссертационных работ

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе дан обзор имеющейся литературы по теме исследования и рассмотрены научно-методологические и технические аспекты исследуемой проблемы Рассмотрены различные постановки задачи кластеризации, освещены проблемы определения близости наблюдений и приведены основные способы измерения расстояния между кластерами

Рис 1 Классификация методов кластерного анализа

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

Проведенный на основе модели унифицированного описания сравнительный анализ позволил определить условия и границы применимости указанных подходов В частности, были выявлены виды задачи кластеризации, практически не решаемые в рамках традиционных подходов, а именно 1) построение дерева таксономии для выборок больших объемов, 2) построение

кластерного решения, оптимального по нескольким критериям качества, при отсутствии априорной информации об истинном числе кластеров

Полученные в данной работе результаты сравнительного анализа позволили сформулировать формальную постановку указанных выше задач, с учетом следующих определений

1 имеется выборка объектов объема N , характеризуемых M признаками (M «N) о, =(olt,of, ,o"J, где i = ¡777, признаки измеряются в числовой шкале о' е R , где j = 1,М (либо в порядковой шкале),

2 под разбиением С подразумевается множество из к кластеров Ср, где р = , т е с = {с,, с2,. , ct}, S - множество возможных разбиений,

3 под кластером Ср подразумевается множество из N р объектов

¿X =N> р{°х'Оу)<р{о,ог), где о=ох,оу, а ох,оуеср, при o,icp,

p=i

4 под р{ох,оу) подразумевается расстояние (мера близости) между объектами Ох и оу .

Задача построения таксономического дерева формулируется так в указанных обозначениях по данным исходной выборки ( N -103) построить систему вложенных разбиений С,, С2, , , где С; - [с,., и {с* и с* }|/{с *, с *},

ПРИ p{c'p,c'q)=mmp(cp,cq),Vcp,cq g , С, = {о,,. ,oiV}

Задача нахождения кластерного решения, (локально) оптимального по нескольким критериям представляется в виде в указанных обозначениях по данным исходной выборки (/V ~ 103) найти разбиение С*, оптимизирующее значения заданных критериев F (c*)=optF ((7),VCe S, где j = fj

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

Этап снижения размерности исходной задачи опирается на разбиение исходной выборки данных на i выборок одинакового меньшего размера (выборки извлекаются без возвращения) Каждая из этих выборок кластеризуется с помощью метода k-средних при заданном одинаковом значении к На выходе этапа имеются центры тяжести кластеров и N -[iV/i]

наблюдений, не вошедших в рассматриваемые / выборок, и возникающих, если объем выборки ¿V не делится на / нацело.

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

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

1 Первый этап снижение размерности исходной задачи

1 1 Разбиение исходной выборки на I выборок объема [#//]>

1 2 Цикл по всем I выборкам,

1 2 1 Кластеризация выборки 1=1,1 методом к-средних;

2 Второй этап построение таксономического дерева по полученным

кластерам и наблюдениям

21 Иерархическое агломеративное объединение кх1 кластеров и АГ — [А?"//] наблюдений (расстояние ¿между кластерами ср и сц определяется по методу Варда)

Р я

где N р — объем кластера с р, /Ир — центр тяжести кластера ср ',

2 2 Определение оптимального числа кластеров как к =П — Г, где

число г соответствует номеру шага иерархической процедуры, предшествующего скачку расстояния агломерации

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

80

20 -

10 -

О

30

40

SO

СО

70

во

SO

Ширина чашелистика, мм ♦ Irls setosa т Irls versicolor л. Irls vlrglnlca

Рис 2 Диаграмма рассеяния для ирисов Фишера в выбранных координатах

На примере ирисов Фишера (см рис 2) было проведено сравнение «карманной» кластеризации с традиционным итеративным методом к-средних МакКуина Полученные результаты свидетельствуют о большем числе успешно классифицированных объектов (при известной структуре кластеров) в случае применения метода, предложенного автором

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

максимум) и среднего внутрикластерного расстояния (найти локальный минимум)

(2),

(3),

где К - число кластеров, N р - объем /7-ого кластера, - расстояние

между наблюдениями I и ]

На каждой итерации осуществляется последовательное разбиение исходной выборки данных, так чтобы значения обоих критериев не ухудшались

к каждым новым шагом Цель каждой новой итерации состоит в улучшении значений критериев, полученных на предыдущей итерации, до тех пор, пока не будут получены стабильные значения (в смысле заданной точности) Результирующее число и состав кластеров считается окончательным В качестве меры, определяющей точность решения, предлагается использовать функционал следующего вида

<2, = И" {с,)- ^(с,)) )- {с,)) (4)

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

1 Инициализация параметров метода

1 1 Разбить исходную выборку на два кластера - с, объема N -1, и с2 объема 1

1 2 Рассчитать начальные значения критериев (^(0), ^(0)), 1=0

2 Основной цикл по _), пока разница в решениях не станет меньше

заданного порога, т е ^ — | < 8

2 1 Цикл по всем о, е с,, I = 1, N -1 наблюдениям,

211 Рассчитать значения (р'О)» ^(О)- если наблюдение 01 присоединяется к ближайшему кластеру С], где ] — 1, к ,

212 Рассчитать значения (0, ^2(0)> если наблюдение о,

выделяется в новый кластер , 2 13 С помощью метода смещенного идеала выбрать наилучший вариант разбиения по значениям (^'(0. Р] ('))>

(^2(0, Р2(')) и (/^ 0-1), Р 0-])) При выборе текущего «идеала» учитывать рассчитанный на предыдущем шаге

(г^'О-1), ГЛа'0-1))

2 14 Осуществить перенос наблюдения О, в соответствии с выбранным вариантом разбиения

На основе сгенерированных данных была исследована зависимость метода (З-кластеризации от выбора начального разбиения, Результирующие разбиения сравнивались с решениями метола к-средних по значениям рассмотренных критериев качества Метод (¿-кластеризации оказался более эффективным, т к значения критериев были ближе к- оптимальным, чем в случае метода к-средних

Третья глава посвящена решению практической задачи -сегментированию рынка банковских услуг с помощью метода «карманной» кластеризации. Данные о потребителях банковских услуг были получены в ходе соответствующего маркетингового исследования, проведённого компанией МАСМИ (Международного Агентства Маркетинговых и Социальных исследований) в 2003 году.

Рис. 3 Распределение респондентов по кластерам

В рамках исследования было опрошено 2000 респондентов из семи федеральных округов. Для сегментации респондентов были выбраны психографические переменные (степень согласия респондентов с высказываниями о поведенческой реакции). Ввиду большого числа переменных были применен метод главных факторов для сокращения их числа.

Преобразованные таким образом данные были успешно кластеризованы с помощью метода «карманной» кластеризации. В результате было получено четыре кластера респондентов, для которых были построены профили по социально-демографическим переменным и которые были проинтерпретированы с точки зрения средних значений главных факторов.

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

Четвёртая глава посвящена решению практической задачи -исследованию профессиональных компетенций в области ИКТ в рамках Национального проекта «Образование» в 2006 г. по программе «Совершенствование системы повышения квалификации и профессиональной переподготовки педагогических, инженерно-технических кадров общеобразовательных школ в области информационных и коммуникационных технологий (ИКТ) и смежных областей».

В ходе исследования была собрана и обработана информация по применению ИКТ в профессиональной деятельности среди 5500 участников программы из семи федеральных округов, прошедших в 2006г. повышение квалификации. На основании полученных данных был проведён многофакторный анализ с использованием метода (^-кластеризации. Предварительно, с целью сокращения размерности исходной задачи методом главных факторов было сокращено число переменных кластеризации.

32%

а "Инноваторы" ■ "Консерваторы" □ "Колеблющиеся"

Рис. 4 Распределение респондентов по кластерам

На основании полученных результатов среди респондентов был выделен сегмент «инноваторов» (см. рис. 4), способных к применению ИКТ в профессиональной деятельности. Для контроля качества полученных решений была произведена кластеризация методом к-средних, для трёх кластеров, а также разбиение методом (^-кластеризации для половин исходной выборки с последующим сравнением с исходным результатом (см. таб. 1). Таблица I Сравнение кластерных решений по значениям критериев

Критерий р! Критерий Г2

Метод О-кластеризации

Исходное решение 5,036 0,187

Объединённое решение 5,031 0,192

Метод к-средних

Исходное решение 4,089 0,203

По результатам исследований, связанных с накопленным опытом учителей-инноваторов, использования ИКТ в учебном процессе были разработаны: рекомендации по использования электронных образовательных ресурсов в типовом учебном заведении; рекомендации по использованию интернет-порталов (как вертикальных, так и горизонтальных); рекомендации по

использованию хранилищ учебных и методических материалов, рекомендации по использованию программно-технических средств поддержки учебного процесса

По результатам данной программы также были сформированы рекомендации по методическому, программному и технологическому оснащению типовых образовательных учреждений системы общего образования, а также их включении в единую образовательно-информационную систему, основанных на полученном позитивном опыте профессионального и педагогически осознанного применения ИКТ в системе российского образования

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

В приложениях содержатся элементы анкет, использованных при проведении практических исследований, выходные формы программных реализаций предложенных методов, акты о внедрении

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ Среди основных результатов работы можно выделить следующие

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

2 Предложен двухэтапный метод «карманной» кластеризации для решения задачи таксономии на выборках большого объема и построения разбиения с возможностью выбора оптимального числа кластеров Оценка вычислительной сложности показала, что метод «карманной» кластеризации решает задачу таксономии на выборках большого объема за субквадратичное время Использование в методе двухэтапной схемы позволяет получать стабильные кластерные решения независимо от условий проведения первого этапа

3 Реализованный с помощью средств VBA 6 0 для Microsoft Excel метод «карманной» кластеризации использовался для решения задачи сегментации потребителей банковских услуг на данных исследования, проведенного в 2003 году Международным Агентством Социальных и Маркетинговых Исследований (МАСМИ) Разработанное программное обеспечение было внедрено в маркетинговый процесс торговой организации ООО «Мегагранд XXI Век», что подтверждается соответствующим актом о внедрении

4 Предложен метод Q-кластеризации для решения задачи построения оптимального разбиения с учетом нескольких критериев качества разбиения Исследование свойств кластерных решений, получаемых с помощью метода Q-кластеризации, проведенное на сгенерированных тестовых примерах показало, что, в среднем в 70% случаев найденные решения соответствуют истинной структуре данных В частности, адекватно определяется истинное число кластеров

5 Реализованный с помощью средств VBA б 0 для Microsoft Excel метод Q - кластеризации использовался для решения задачи многофакторного анализа и выделения сегмента учителей-новаторов в рамках выполнения Национального проекта «Образование» в 2006 г по программе «Совершенствование системы повышения квалификации и профессиональной переподготовки педагогических, инженерно-технических кадров общеобразовательных школ в области информационных и коммуникационных технологий (ИКТ) и смежных областей» В результате полученных кластерных решений был сформирован пул учителей-инноваторов для дальнейшего использования их методического опыта в области ИКТ, что подтверждено соответствующими актами о внедрении

6 Предложенный метод Q - кластеризации использован в проекте разработки информационно-образовательного портала МИФИ для самостоятельной работы студентов, выполняемый по Инновационной программе инженерно-физического образования для нового этапа развития ядерной науки и промышленности в рамках реализации Приоритетного национального проекта «Образование» (2007)

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1 Киреев В С Алгоритм кластеризации данных с минимаксной оптимизацией критериев качества разбиения /Киреев В С //Информационные технологии - 2007, № 7 - С 47-49

2 Киреев В С Сегментация потребителей банковских услуг с помощью метода Q-кластеризации /Киреев В С, Синицын С В // Информационная математика -2007, № 1(6) - С 81-90

3 Киреев В С Оптимальность кластерных решений, получаемых методом «карманной кластеризации» /Киреев В С , Синицын С В // XVI Международный научно-технический семинар «Современные технологии в задачах управления, автоматики и обработки информации»- сб научных трудов - Алушта, 2007 -С 58

4 Киреев В С Метод усечения матрицы расстояний в решении задачи кластерного анализа /Киреев В С// XV Международный научно-технический семинар «Современные технологии в задачах управления, автоматики и обработки информации» сб научных трудов - Алушта, 2006 -С 73

5 Киреев В С Объединенные итеративный и агломеративный подходы в процедуре кластеризации с априорно неизвестным числом кластеров /Киреев В С , Синицын С В // XIV Международный научно-технический семинар «Современные технологии в задачах управления, автоматики и обработки информации» сб научных трудов - Алушта, 2005 — С 50

6 Киреев В С Информационная поддержка самостоятельной работы студентов система МИФИСТ /Гусева А И , Киреев В С , Тихомирова А Н, Филиппов С А, Цыплаков АС// Научная сессия МИФИ-2008 сб научных трудов -М МИФИ, 2008 -Том 6-С 21-22

7 Киреев В С Разработка информационно-образовательного портала для поддержки самостоятельной работы студентов /Гусева А И, Киреев В С, Тихомирова А Н , Филиппов С А , Цыплаков АС// Научная сессия МИФИ-2008 ХП выставка-конференция «Телекоммуникации и новые информационные технологии в образовании» сб научных трудов -М МИФИ, 2008 - С 13-14

8 Киреев В С «МИФИСТ» информационно-образовательный портал для поддержки самостоятельной работы студентов /Гусева А И, Киреев В С, Маслий, Н П , Тихомирова А Н , Филиппов С А , Цыплаков АС// Научная сессия МИФИ-2008 XII выставка-конференция «Телекоммуникации и новые информационные технологии в образовании» Каталог - М МИФИ, 2008 -С 14

9 Киреев В С Q-алгоритм сегментирования данных при неизвестном исходном числе сегментов /Киреев ВС// Научная сессия МИФИ-2007 сб научных трудов - М МИФИ, 2007 -Том 2 -С 93-95

10 Киреев В С Двухэтапный алгоритм кластеризации данных /Киреев В С , Синицын С В И Научная сессия МИФИ-2006 сб научных трудов - М МИФИ, 2006 -Том 2 -С.14-15

11 Киреев В С Нсйросетевая модель потребителя в маркетинговом ценовом исследовании ВРТО/Киреев В С, Синицын С В // Научная сессия МИФИ-2005 сб научных трудов - М. МИФИ, 2005 -Том 2 -С 142

12 Киреев В С Маркетинг и маркетинговые исследования/Киреев В С , Маковеев Н П //Электронные учебные материалы -М , МИФИ, 2007

Введение.

Глава 1 Сравнительный анализ подходов к решению задачи кластерного анализа.

1.1. Проблема кластеризации данных.

1.1.1. Постановка задачи кластерного анализа.

1.1.2. Измерение расстояния между объектами.

1.1.3. Функционалы качества разбиения.

1.1.4. Подходы к решению задачи кластеризации.

1.2. Методы кластерного анализа.

1.2.1. Методы, основанные на представлении выборки в виде графа.

1.2.1.1. Метод КНП (кратчайшего наименьшего пути).

1.2.2. Иерархические методы.

1.2.2.1. Агломеративные методы.

1.2.2.2. Агломеративные методы на основе свойства редуктивности.

1.2.2.3. Дивизимные методы.

1.2.3. Параллельные итеративные методы.

1.2.3.1. Метод FOREL.

1.2.4. Последовательные итеративные методы.

1.2.4.1. Кластеризация Expectation Maximization.

1.2.4.2. Метод k-средних МакКуина.

1.2.5. Нейросетевые методы.

1.2.5.1. Сети Кохонена.

1.2.5.2. Рекуррентные сети Хопфилда.

1.3. Сравнительный анализ методов кластеризации.

1. 4. Постановка задачи диссертации.

Выводы.

Глава 2. Новые математические методы решения задачи кластеризации.

2.1. Решение задачи таксономии.

2.1.1. Постановка задачи.

2.1.2. Теоретические основы метода «карманной» кластеризации.

2.1.3. Зависимость кластерного решения от значений параметров метода.

2.2. Кластеризация методом многоэкстремальной оптимизации.

2.2.1. Постановка задачи.

2.2.2. Теоретические основы метода Q-кластеризации.

2.1.5. Зависимость кластерного решения от значений параметров метода.

2.1.6. Применимость метода Q-кластеризации.

Выводы.

Глава 3. Кластеризация потребителей рынка банковских услуг в РФ.

3.1. Задача кластеризации потребителей банковских услуг.

3.2 Сокращение пространства признаков выборки.

3.2.1. Поиск оптимального числа факторов.

3.2.2. Интерпретация полученных факторов.

3.3. Сегментация методом «карманной» кластеризации.

3.3.1. Реализация метода «карманной» кластеризации.

3.3.2. Построение кластерного решения.

3.3.3. Построение профилей и интерпретация сегментов.

3.3.4. Управленческие рекомендации по результатам сегментирования.

Выводы.

Глава 4. Исследование профессиональных компетенций ИКТ в рамках Федеральной целевой программы.

4.1. Задача выделения пула учителей-инноваторов.

4.2. Сокращение пространства признаков выборки.

4.2.1. Поиск оптимального числа факторов.

4.2.2. Интерпретация полученных факторов.

4.3. Сегментация методом Q- кластеризации.

4.3.1. Реализация метода Q-кластеризации.

4. 3. 2. Построение оптимального разбиения.

4.3.3. Исследование качества полученного кластерного решения.

4.3.4. Интерпретация сегментов.

4.4. Результаты многофакторного анализа.

4.5. Методы кластерного анализа для определения рейтинга студентов.

Выводы.

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

Задача кластеризации или таксономии впервые была рассмотрена в 1930-х годах. Эту проблему в её различных аспектах изучали как зарубежные, так и отечественные исследователи, в том числе: МакКуин Д., Ланс У., Уильяме Д., Хартиган Д., Вонг М., Кохонен Т., Фрицке Б., и Колмогоров А.Н., Загоруйко Н.Г., Ёлкина В.Н., Айвазян С.А., Мхитарян B.C., Щумский С.А., и другие.

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

Виды задачи разбиения отличаются от приложения к приложению, однако можно выделить несколько общих типов:

• задачи таксономии, в которых требуется построить не просто разбиение данных на кластеры, а иерархию вложенности кластеров друг в друга - таксономическое дерево или, иначе, дендрограмму;

• задачи выделения естественного расслоения исследуемой совокупности на кластеры, причём в такой трактовке задача кластеризации может и не иметь решения; например, может оказаться, что все объекты образуют единственный кластер;: • задачи^ разбиения; выборочной совокупности на несколько: групп, так что объекты, внутри: одной группы обладают сравнительно большим сходством друг с другом, чем с объектами из других групп. Кластеризация данных, как видно из изложенного выше, относится к задачам, содержащим высокую степень неопределённости, как в отношении требуемого результата, так. и в отношении- априорных данных. Эта неопределённость сосредоточена в основном в двух ключевых моментах -способе измерения однородности объектов и оценке качества полученного" кластерного решения. Указанные проблемы- более подробно; освещаются в следующих разделах.

Проблема кластеризации данных обычно рассматривается в двух различных вариантах постановки - нахождения естественного расслоения кластеров и нахождения кластеров в виде групп близких объектов; Первый вариант может и не иметь решения, например, в случае, если - исходные данные представляют собой один большой кластер, однако второй вариант, имеет решение всегда, и представляет .наибольший интерес для, исследователей. Кластерные процедуры для нахождения; схожих объектов; можно разделить на; два общих типа "— агломеративные" (дивизимные) и итеративные. Агломеративные процедуры, такие как древесная кластеризация; применяются для сравнительно-небольших выборок данных — от десятков до сотни объектов, так; как при увеличении числа объектов наглядность и вычислительная эффективность этих процедур резко снижается; На практике же изучаемые выборки обладают объёмом от сотен до нескольких тысяч;, и здесь применяются уже итеративные и кластер-процедуры. В итеративных процедурах на каждом шаге работы рассматривается только один объект и производится его отнесение к одному из кластеров; работа процедуры заканчивается, когда получается устойчивое разбиение на кластеры или достигнуто заданное число итераций.

Основной итеративный метод, реализованный в многочисленных программах обработки данных (Statistica, Statgraphics, SPSS, и т.д.), и описанный в различных публикациях и изданиях, метод k-средних, является достаточно простым и в тоже время позволяет получить разбиение оптимальное в смысле заданного Q - критерия качества. К таким критериям относят в том числе межкластерное расстояние, внутрикластерное рассеяиие и многие другие. Тем не менее, этот метод обладает существенными недостатками: а) необходимость применения процедуры несколько раз для различного числа кластеров К, для выбора разбиения с лучшим значением критерия (или критериев) качества Q; б) стремление метода к выделению сферических кластеров, что не всегда соответствует оптимальному разбиению; в) отсутствие гарантии получения устойчивого разбиения за один цикл просмотра.

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

Таким образом, при решении практических задач возникает острая необходимость в разработке метода (методов), который был бы более простым и менее субъективным (зависящим от параметров, значения которых редко можно предполагать заранее), чем наиболее используемые методы. В этом новом методе должна производиться оптимизация сразу в процессе работы, по возможности учитываться сразу несколько критериев, и окончание работы метода должно достигаться за один цикл просмотра исходной выборки объектов.

Областью исследования являются методы и алгоритмы обработки информации, критерии оценки качества решения задач, а также их программная реализация (паспорт специальности 05.13.01 - п.п. 2.3, 2.4, 2.

Научная новизна работы заключается в следующем.

1. Создана модель унифицированного формального описания наиболее известных методов кластеризации для проведения, их сравнительного анализа. С целью определения областей эффективного использования различных методов определена их вычислительная сложность. Полученные результаты анализа позволили сделать вывод, что эффективность традиционных иерархических методов^ решения задачи таксономии резкое снижается при увеличении объёма исходных данных, а итеративные методы, решающие задачу кластеризации для выборок большого объёма, не в состоянии обеспечить качество решения, соответствующее одновременно нескольким* различным! критериям, характеризующим пространственную кластерную структуру.

2. Впервые предложен метод (3-кластеризации(для решения задачи построения) оптимального разбиения с учетом нескольких критериев качества. Исследование свойств кластерных решений, получаемых с помощью метода Q-кластеризации, проведенное на сгенерированных тестовых примерах показало, что примерно в 70% случаев найденные решения соответствуют истинной структуре кластеров объектов в пространстве признаков. В частности, метод адекватно определяет истинное число кластеров.

3. Впервые предложен метод «карманной» кластеризации для решения задачи* таксономии на выборках большого объёма и построения разбиения с возможностью выбора оптимального числа кластеров. Оценка предложенного метода на предмет вычислительной сложности показала, что метод «карманной» кластеризации решает задачу таксономии на выборках

12). большого объёма за субквадратичное время в отличие от иерархических методов, характеризующихся сложностью o(/v3)

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

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

Практическая значимость. На основе предлагаемых методов кластеризации осуществлено:

• разработка программной реализации метода «карманной» кластеризации;

• решение задачи сегментации потребителей банковских услуг на данных исследования, проведённого в 2003 году Международным Агентством Социальных и Маркетинговых Исследований (МАСМИ -Москва);

• разработка программного приложения на основе метода Q-кластеризации;

• решена задача многофакторного анализа и выделения сегмента учителей-новаторов по использованию информационных и коммуникационных технологий (ИКТ) в профессиональной деятельности среди 8500 участников из семи федеральных округов, прошедших в 2006 г повышения квалификации в рамках совершенствования системы повышения квалификации и профессиональной переподготовки педагогических, инженерно-технических кадров в области информационных и коммуникационных технологий (ИКТ) и смежных областей.

Эксплуатация, указанных программных приложений подтверждена соответствующими актами о внедрении.

Достоверность , математических методов - кластеризации, алгоритмов и программных средств подтверждается, соответствующими, актами; о внедрении, почетным дипломом выставки-конференции

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

На защиту выносятся следующие положения.

1. Новый метод Q-кластеризации для решения задачи: построения оптимального^ разбиения? с учетом: нескольких критериев качества, обеспечивающий^ соответствие кластерных решений: истинной* структуре: распределения объектов в пространстве признаков:

2. Новый; метод «карманной» кластеризации для: решения задачи? таксономии на выборках большого объёма; в котором успешно: комбинируются; характеристики точности иерархических схем, и.* простота реализации итерационных процедур кластеризации: З. Математическое,.алгоритмическое и программное.обеспечение.нового . метода: Q-кластеризации, примененное в ряде образовательных проектов в целях совершенствования образовательного процесса.

4. Математическое, алгоритмическое: и программное обеспечение нового метода- «карманной» кластеризации, примененное для аналитического исследования социально-демографического и; психологического статуса, потребителей банковских услуг с целью, более эффективной работы» банков на финансовом рынке.

5. Содержательные результаты кластеризации данных, полученные в ходе использования программного обеспечения метода Q-кластеризации при реализации программы «Совершенствование системы повышения

Выводы

По результатам, полученным в ходе исследования традиционных методов кластерного анализа, можно сделать следующие выводы.

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

2. Полученные результаты анализа свидетельствуют о том, что результативность традиционных иерархических методов решения задачи таксономии резко снижается при увеличении объёма исходных данных.

3. Итеративные методы, решающие задачу кластеризации для выборок большого объёма, не в состоянии обеспечить качество решения, соответствующее одновременно нескольким различным критериям, характеризующим пространственную кластерную структуру.

4. Приведённые выше результаты определяют актуальность и необходимость разработки новых методов, позволяющих решить задачу многокритериальной оптимизации качества разбиения для выборок большого объёма и решить задачу построения таксономии для выборок большого объёма.

Глава 2. Новые математические методы решения задачи кластеризации 2.1. Решение задачи таксономии

2.1.1. Постановка задачи

Поставим задачу кластеризации следующим образом:

1. имеется выборка объектов объёма N, характеризуемых

Мпризнаками (M«N):o1 =(oll,of,.,ofJ, где i-\,N, признаки измеряются в числовой шкале: о/ е R , где j = \,M (либо в порядковой шкале);

2. под разбиением с подразумевается множество из к кластеров ср, где р = \,к , т.е. С = {с,, с,,., ск}, S — множество возможных разбиений;

3. под кластером с подразумевается множество из Np объектов:

Y,Np = N> p(°x>0},)<p(0>0J, где о=ох,оу, а ох,оу еср, при о:еср; Р=1

4. под р[ог,оу) подразумевается расстояние (мера близости) между объектами ох и оу.

Задачу построения таксономического дерева сформулируем так: в указанных обозначениях по данным исходной выборки (л/ ~ i о3) построить систему вложенных разбиений: Cl,C2,.,CNl, где Су =[суЧ и {с* uc*}J/{c*,c*}, при p{c*p,c*q)~ mmp[cp,cq\^cp,cq еСн, Сх = {о15.,о^}.

2.1.2. Теоретические основы метода «карманной» кластеризации

Произвольное число кластеров К легко получить из иерархической агломеративной схемы, которая не применима для выборки большой размерности, поэтому первым шагом решения должно быть сокращение размерности задачи. Сократить число наблюдений N за приемлемое время можно с помощью итерационных методов, например метода k-средних. Но так как этот метод сильно зависит от начального решения и числа кластеров К, то возможно получение нестабильного решения в результате.

Чтобы снизить влияние этих параметров на результат, предлагается производить кластеризацию не на исходной выборке данных, а на её L выборках меньшего объёма — «карманах», способ подобный бутстрэпингу [12]. Выборки должны содержать равное число наблюдений [n/l], отобранных без возвращения из исходных данных. Таким образом, на выходе первого этапа решения - этапа сокращения размерности задачи по числу наблюдений — имеются центры кластеров ju(Cj ) и их объём Nj, где j = \,Lx К.

Вторым этапом решения задачи является иерархическая агломеративная процедура, причём для учёта объёма кластеров имеет смысл использовать метод Варда в качестве метода измерения расстояния между кластерами:

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

После выбора подходящего решения (например, по графику агломерации) исходные объекты должны быть отнесены к построенным центрам К кластеров. Отнесение осуществляется жёстко - каждое наблюдение О; относится к ближайшему центру с7.

Алгоритм 2.1. «Карманная» кластеризация

1. Провести кластеризацию в L выборках методом k-средних. Получить объёмы и центры кластеров.

1.1.Цикл по всем выборкам Ои\ l-\,L

1.2.Инициализация начального множества эталонов е е Е{1)

1.3. Цикл по всем объектам Vo е 0(!)

1.3.1. Отнесение объекта о к ближайшему эталону:

2.1) где //(с,) — центр тяжести кластера с,

1.3.1.1. em = emyj{o] d(о,em) = mind{o,e) 1.3.2. Если em отличается от эталона предыдущего шага ет, то :

VemJ = kw КI+ )/(к I + 0| J = й?

1.3.2.1. в = \ет\ +1 /W I I W I

132 2 ^ = ' ~ ' ~ ^J = l,M е \ = \е —1

I m I I т\

1.3.3. Пока центры эталонов не перестанут изменяться.

2. Кластеризовать полученные центры в иерархической агломеративной процедуре по методу Варда. Выбрать кластерное решение по скачку расстояния агломерации.

2.1. Инициализация начального множества кластеров: ZZC^Qc^uO^

1=\,L

2.3.Цикл по / = 2,.,|С,=1|

2.4. Поиск пары ближайших кластеров: 2.4.1. (cp.,cq.)\d(cpt,cq,) = min d{cp,cq)

2.5. добавление объединённого кластера в текущее множество кластеров:

2.6. С, = С,, и {ср. vcq>}\ {ср.,cqt}

2.7. Цикл по Vc е С,

2.7.1. Расчёт расстояния по формуле Ланса-Уильямса R(c,cpt ut?>)

3. Разбить исходные наблюдения по полученным К центрам, отнеся каждое наблюдение к ближайшему центру.

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

Если исходить из полученной ранее оценки то окажется, что вычислительная сложность первого этапа зависит от трёх заранее заданных величин - числа выборок L, числа кластеров - к и объёма выборки N. 1

Неизвестным фактором является суммарное число итераций ^ I,, которые

-1 требуются для стабилизации множества эталонов. Чтобы определить, зависит ли это число от указанных выше параметров, были проведены расчёты по первому этапу для модельных выборок различного объёма — от 1 ООО до 2000 наблюдений, с шагом в 50 наблюдений, для фиксированных значений L и к.

В силу того, что вычислительная сложность второго этапа метода «карманной» кластеризации определяется величиной Р = £-£ + |о(/+|)|, причём в нашем случае |o(/'+1)| = res (■%) = (), то были выбраны такие Р, чтобы Р3 было сравнимо с TV по порядку.

Для подтверждения гипотезы о наличии связи между изменением

V 1 , • • объёма выборки и числа итераций был использован дисперсионный анализ. В качестве уровней фактора были выбраны объёмы выборки (и т.д.), в качестве отклика — число итераций. Был использован специально разработанный генератор выборок, содержащих сферические кластеры для получения 200 случайных выборок с последовательно увеличивающимся объёмом (от 90 до 1800 наблюдений, по 10 выборок на каждый объём). По этим выборкам был проведён первый этап «карманной» кластеризации, и рассчитаны суммарные количества итераций и оценено их изменение от фактора - объёма выборок.

Заключение

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

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

2. Впервые предложен двухэтапный метод «карманной» кластеризации для решения задачи таксономии на выборках большого объёма и построения разбиения с возможностью выбора оптимального числа кластеров. Оценка вычислительной сложности показала, что метод «карманной» кластеризации решает задачу таксономии на выборках большого объёма за субквадратичное время. Использование в методе двухэтапной схемы позволяет получать стабильные кластерные решения независимо от условий проведения первого этапа.

3. Реализованный с помощью средств VBA 6.0 для Microsoft Excel метод «карманной» кластеризации использовался для решения задачи сегментации потребителей банковских услуг на данных исследования, проведённого в 2003 году Международным Агентством Социальных и Маркетинговых Исследований (МАСМИ). Разработанное программное обеспечение было внедрено в маркетинговый процесс торговой организации ООО «Мегагранд XXI Век», что подтверждается соответствующим актом о внедрении.

4. Впервые предложен метод Q-кластеризации для решения задачи построения оптимального разбиения с учетом нескольких критериев качества разбиения. Исследование свойств кластерных решений, получаемых с помощью метода Q-кластеризации, проведенное на сгенерированных тестовых примерах показало, что, в среднем в 70% случаев найденные решения соответствуют истинной структуре данных. В частности, адекватно определяется истинное число кластеров.

5. Реализованный с помощью средств VBA 6.0 для Microsoft Excel метод Q -кластеризации использовался для решения задачи многофакторного анализа и выделения сегмента учителей-новаторов в рамках выполнения Национального проекта «Образование» в 2006 г. по программе «Совершенствование системы повышения квалификации и профессиональной переподготовки педагогических, инженерно-технических кадров общеобразовательных школ в области информационных и коммуникационных технологий (ИКТ) и смежных областей». В результате полученных кластерных решений был сформирован пул учителей-инноваторов для дальнейшего использования их методического опыта в области ИКТ, что подтверждено соответствующими актами о внедрении.

6. Предложенный метод Q - кластеризации вошёл как составная часть в проект разработки информационно-образовательного портала МИФИ для самостоятельной работы студентов, выполняемый по Инновационной программе инженерно-физического образования для нового этапа развития ядерной науки и промышленности в рамках реализации Приоритетного национального проекта «Образование» (2007), что подтверждается актом о внедрении.

1. Дюран Б., Одел П. Кластерный анализ — М.: Финансы и статистика, 1977.

2. Мандель И.Д. Кластерный анализ. — М.: Финансы и статистика, 1988.

3. Олденфендер М.С., Блешфилд Р.К. Кластерный анализ /Факторный, дискриминантный и кластерный анализ/ Дж. О. Ким, У. Мюллер У.Р. Клерка и др. М.: Финансы и статистика, 1989.

4. Айвазян С.А., В.М. Бухштабер, И.С. Енюков, Л.Д. Мешалкин Прикладная статистика: Классификация и снижение размерности: Справ. Изд. М: Финансы и статистика, 1989.

5. Айвазян С.А., Мхитарян B.C. Прикладная статистика. Основы эконометрики. В 2 т.Т. 1. Теория вероятностей и прикладная статистика. — М.: ЮНИТИ-ДАНА, 2001.

6. Дубров A.M., Мхитарян B.C., Трошин Л.И. Многомерные статистические методы. — М.: Финансы и статистика, 2001.

7. Дубровский С.А. Прикладной многомерный статистический анализ. — М.: Финансы и статистика, 1982.

8. Мешалкин Л.Д. Локальные методы классификации // Статистические методы классификации. М.: Изд-во МГУ, 1969. - вып. 1. - С. 58-78

9. Браверманн Э.М., Мучник И.Б. Структурные- методы обработки эмпирических данных. М.: Наука, 1983.

10. Ю.Вапник В.Н. Восстановление зависимостей по эмпирическим данным. -М.: Наука, 1979.

11. П.Крянев А.В. Лукин Г.В. Математические методы обработки неопределенных данных. -М.:ФИЗМАТЛИТ, 2003. 216 с.

12. Типология и классификация в социологических исследованиях/Под ред. Андреенкова В.Г. и Ю.Н. Толстовой. — М.: Наука, 1982.

13. Барсегян А.А., Куприянов М.С., Степаненко В.В., Холод И.И. Технологии анализа данных: Data mining, Visual Mining, Text Mining, OLAP. -2-е изд., перераб. и доп. СПб.: БХВ-Петербург, 2007.

14. Гайдышев И. Анализ и обработка данных: специальный справочник — СПб: Питер, 2001.

15. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. -М.: Мир, 1979.

16. Уиллиамс У. Т., Ланс Д. Н. Методы иерархической классификации // Статистические методы для ЭВМ / Под ред. М. Б. Малютов. М.: Наука, 1986.

17. Binder, D. А. (1978), "Bayesian Cluster Analysis," Biometrika, 65, 31-38.

18. Fuzzy Cluster Analysis with Cluster Repulsion, H. Timm, C. Borgelt, C. Doring, R.Kruse, Dept. Of Knowledge Processing and Language Engineering, Otto-von-Guericke-University of Magdeburg, 2001

19. Clustering Methods. Applications of Multivariate Statistical Analysis/ Jiangsheng Yu/ Institute of Computational Linguistics, Peking University, Beijing, 100871

20. Celeux, G., Chaveau, D., and Diebolt, J. (1996), "Stochastic Versions of the EM Algorithm: An Experimental Study in the Mixture Case," Journal of Statistical Computation and Simulation, 55, 287-314.

21. Celeux, G., and Govaert, G. (1992), "A Classification EM Algorithm for Clustering and Two Stochastic Versions," Computational Statistics and Data Analysis, 14, 315-332.

22. Macqueen, J. (1967). Some Methods for Classification and Analysis of Multivariate Observations. In Proc. of the 5th Berkeley Symposium on Mathematical Statistics and Probability (p. 281-297). Berkeley: University of California Press, Vol. 1.

23. Hartigan, J. A., and Wong, M. A. (1978), "Algorithm AS 136: A k-Means Clustering Algorithm," Applied Statistics, 28, 100-108.

24. Назаров A.B., Лоскутов А.И. Нейросетевые алгоритмы для прогнозирования и оптимизации систем. СПб.: Наука и Техника, 2003.31.0совский С. Нейронные сети для обработки информации. — М.: Финансы и статистика, 2004.

25. Галушкин А.И. Теория Нейронных сетей. М.: ИПРЖР, 2000.

26. Т. Kohonen Self-organized formation of topologically correct feature maps Biological Cybernetics, Vol. 43, pp.59-69, 1982

27. T. Kohonen Self-Organizing Maps — Springer, 1995

28. Кохонен Т. Ассоциативная память — М.: Мир, 1980

29. Кохонен Т. Ассоциативные запоминающие устройства — М.: Мир, 1982

30. Фор А. Восприятие и распознавание образов — М.: Машиностроение, 1989.- 272 с

31. Горбань А.Н., Россиев Д.А Нейронные сети на персональном компьютере Новосибирск: Наука (Сиб. отделение), 1996. 276 с

32. Hopfield JJ Neural networks and physical systems with emergent collective computational abilities Proc. Nat. Acad. Sci. USA. 1982. Vol. 79. P.2554-2558

33. Hopfield J.J Neural Networks and Physical systems with emergent collective computational abilities Proc. Nat. Sci. USA. 1982. V.79. P. 2554-2558

34. Уоссермен Ф. Нейрокомпьютерная техника —M.: Мир, 1992

35. А.А.Веденов Итоги науки и техники. Сер. "Физ. и Матем. модели нейронных сетей" -М.: Изд-во ВИНИТИ, 1990-92 Т. 1-5

36. Фролов А.А., Муравьев И.П Нейронные модели ассоциативной памяти М.: Наука, 1987.- 160 с

37. Т.М. Martinetz, S.G. Berkovich, K.J. Schulten Neural-gas network for vector quantization and its application to time-series prediction IEEE Transactions on Neural Networks, Vol. 4, No. 4, p.558-569, 19931

38. Черноруцкий ИГ. Методы принятия решений. Спб.: БХВ-Петербург, 2005.

39. Интрилигатор М. Математические методы оптимизации и экономическая теория — М.: Прогресс, 1975

40. Кузин JI.T. Основы кибернетики. T.l. М.: Энергия, 1973.

41. Салмин И.Д. Математическое программирование. Ч. I. М.: МИФИ, 1978.

42. Салмин И.Д. Математическое программирование. Ч. II. М.: МИФИ, 1979.

43. Киреев B.C. Алгоритм кластеризации данных с минимаксной оптимизацией критериев качества разбиения /Киреев B.C. //Информационные технологии. 2007, № 7. - С.47-49.

44. Киреев B.C. Сегментация потребителей банковских услуг с помощью метода Q-кластеризации /Киреев B.C., Синицын С.В.// Информационная математика. 2007, № 1(6). - С.81-90.

45. Киреев B.C. Информационная поддержка самостоятельной работы студентов: система МИФИСТ /Гусева А.И., Киреев B.C., Тихомирова А.Н., Филиппов С.А., Цыплаков А.С.// Научная сессия МИФИ-2008:сб. научных трудов. М.: МИФИ, 2008. -Том 6 - С.21-22.

46. Киреев B.C. Q-алгоритм сегментирования данных при неизвестном исходном числе сегментов /Киреев B.C.// Научная сессия МИФИ-2007: сб. научных трудов.- М.: МИФИ, 2007-Том 2. -С.93-95.

47. Киреев B.C. Двухэтапный алгоритм кластеризации данных /Киреев B.C., Синицын С.В.// Научная сессия МИФИ-2006: сб. научных трудов. М.: МИФИ, 2006. -Том 2. -С. 14-15.

48. Киреев B.C. Нейросетевая модель потребителя в маркетинговом ценовомхисследовании ВРТО/Киреев B.C., Синицын С.В.// Научная сессия МИФИ-2005: сб. научных трудов М.: МИФИ, 2005. -Том 2. -С.142.

49. Киреев B.C. Маркетинг и маркетинговые исследования/Киреев B.C., Маковеев Н.П. //Электронные учебные материалы.-М., МИФИ, 2007.