автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Методика адаптивной кластеризации фактографических данных на основе интеграции методов минимального остовного дерева и нечетких К-средних

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

004614246

Нсйский Иван Михайлович

МЕТОДИКА АДАПТИВНОЙ КЛАСТЕРИЗАЦИИ ФАКТОГРАФИЧЕСКИХ ДАННЫХ НА ОСНОВЕ ИНТЕГРАЦИИ МЕТОДОВ МИНИМАЛЬНОГО ОСТОВНОГО ДЕРЕВА И НЕЧЕТКИХ К-СРЕДНИХ

05.13.17 —Теоретические основы информатики

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

2 5 НОЯ 2010

Москва-2010

004614246

Работа выполнена на кафедре «Системы обработки информации и управления» Московского государственного технического университета им. Н.Э. Баумана

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

Филиппович Андрей Юрьевич

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

Ковшов Евгений Евгеньевич кандидат технических наук, Паклин Николай Борисович

ГОУ ВПО «Петрозаводский государственный Ведущая организация: г '

университет»

Защита диссертации состоится 25 ноября 2010 г. в 13:00 на заседании диссертационного совета Д 212.147.03 при Московском государственном университете печати по адресу: 127550, Москва, ул. Прянишникова, 2а.

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

Автореферат разослан а 03 » октября 2010 г.

Ученый секретарь /

диссертационного совета / л , В.Н. Агеев

д.т.н., профессор /¿л'ЧУ-МЧ

Общая характеристика работы Актуальность работы

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

Изучение проблем и решение задач в этой области активно проводится в направлениях Business Intelligence (Интеллектуальный анализ данных) и Knowledge Management (Управление знаниями). В них выделяются поднаправления: Knowledge Discovery in Databases (Выявление знаний в базах данных), Data Mining (Анализ фактографических данных), Text Mining (Анализ неструктурированных данных) и др.

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

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

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

На сегодняшний день в области кластерного анализа актуально решение следующих проблем: обоснованный выбор наиболее подходящего метода исследования; сложность оценки получаемых разбиений; отсутствие рекомендаций по применению методов в различных предметных областях; определение количества кластеров.

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

Цель работы и задачи исследования

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

Для реализации поставленной цели в работе решаются следующие задачи:

1. Исследование методов и систем интеллектуального анализа данных, используемых для кластеризации фактографических данных.

2. Разработка методики адаптивной кластеризации фактографических данных.

3. Разработка рекомендаций по выбору существующих алгоритмов кластеризации.

4. Разработка метода кластеризации.

5. Разработка метода докластеризации.

6. Разработка программного комплекса для автоматизации предложенного метода кластеризации.

7. Оценка эффективности предложенной методики.

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

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

Научная новизна

Научную новизну работы составляют:

— методика адаптивпой кластеризации фактографических данных;

— метод адаптивной кластеризации фактографических данных смешанного типа на основе интеграции методов минимального остовного дерева и нечетких К-средних (АПАК1>), позволяющий проводить исследования в выбранной прикладной области, определяя количество и состав кластеров;

— метод докластеризации, позволяющий сократить время кластеризации новых объектов;

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

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

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

Практическая ценность

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

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

Основные положения диссертационной работы докладывались и обсуждались в 2006-2010 гг. на заседаниях комиссий по аттестации аспирантов и научных семинарах аспирантов и студентов МГТУ им. Н.Э. Баумана. Апробация работы проводилась па всероссийских и международных конференциях «Телематика 2009», «ИТ в образовании, науке и производстве 2009», «Бизнсс-аналитика. Вопросы теории и практики. Использование аналитической платформы Dcduclor в деятельности учебных заведений 2010»; в рамках научной школы «Компьютерная графика и математическое моделирование»; на семинарах научно-образовательного кластера CLAIM. Материалы работы представлены для ознакомления и обсуждения с 2008 года па web-сайте и в форуме (электронный адрес - www.philippovich.ru).

Структура и объем работы

Диссертационная работа состоит из введения, четырех глав, заключения, списка использованной литературы и приложений. Общий объем текста диссертации составляет 185 страниц и содержит 30 таблиц, 21 схему, 137 источников, из них 43 зарубежных.

Содержание работы

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

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

В работе па основе литературных источников составлена классификация методов кластерного анализа (рис. 1), проведен анализ и сравнение наиболее известных методов:

CURE, BIRCH, MST, к-средних, РАМ, CLOPE, самоорганизующиеся карты Кохонена (SOM), НСМ, Fuzzy C-Means.

Исследование основано на работах таких авторов как: В. Гаити, И. Герке, Г. Гровэ, С. Гуха, Р. Дюбс, В. Дюк, Б. Дюран, JT. Заде, Л. Джэйн, Т. Кормен, Б. Коско, Ч. Лейзер-сон, П. Одел, С. Оссовский, К. Парсайе, Р. Рамакришнан, Р. Растоги, Р. Ривест, А. Синг, Ф. Уоссермеп, С. Хайкин, X. Хэ, К. Шим, К. Штайн и др. (всего более 100 источников).

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

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

На основе проведенного сравнения методов выделены метод MST, который с помощью минимальных остовпых деревьев выделяет кластеры произвольной формы, и метод Fuzzy C-means, который выполняет кластеризацию па основе матрицы нечеткого разбиения, что позволяет распределять объекты по одному и более кластерам на основе их степени принадлежности.

На основе проведенного исследования предметной области выделен и формализован класс задач: количество исходных объектов: КЬ^^КЬ^К^,...,/^^], /е [500;50000]; количество значимых характеристик объектов: АХ, = [^,А:2,...,А:^,/е[70;150]; типы характеристик Т: Т е[числовые, лингвистические]; форма получаемых кластеров - сложная, с пересечениями; количество кластеров ТУ - результат исследования: Л^е[5;30].

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

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

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

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

На основе полученных данных можно разработать контрольный пример (этап 3, рис. 2), который в дальнейшем будет использован для проверки действенности метода. Данный процесс необходимо выполнять с привлечением носителей экспертных знаний в исследуемой области.

На следующем этапе (этап 4, рис. 2) выполняется выбор метода кластерного анализа. При выборе метода проведения исследования есть возможность использовать существующие методы кластеризации или использовать авторский метод адаптивной кластеризации ЛПЛКЬ. Характерной особенностью данного этапа является то, что на основе характеристик полученной выборки и априорным знанием желаемого результата выполняется поиск подходящего метода исследования с промежуточными оценками результатов и накоплением практического опыта по применению различных методов в решаемой практической задаче.

После выбора метода кластерного анализа выполняется кластеризация полного объема данных (этап 5, рис. 2) и получение результата в виде конечного разбиения множества исходных объектов на кластеры.

Рис. 2. Методика адаптивной кластеризации.

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

Выделено восемь критериев выбора метода: объем информации по отношению к времени обработки (СгД размерность информации (Сг2), типы атрибутов сущностей (Сг3), чувствительность к равномерности информации (С/*4), а также априорные (экспертные) представления о форме получаемых кластеров (Сг5), их количестве (Сг6) и пе-рекрывасмости (СУ8). Для исследуемой предметной области установлены следующие приоритеты и значения выделенных критериев: Сгц=«Высокое», Сг6=«Вычисляемая величина», Сг}=«Сложная форма», Сг?=«С пересечениями», Сг2=«Высокая размерность», Сг^«Смешанного типа», Сг1=«Линейпая или логарифмическая зависимость», Сг4=«Низкая чувствительность».

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

Сложностью кластеризации является необходимость получения такой оценки сс результатов, которая позволяет определить возможность использования алгоритма для выбранной предметной области. Оценка качества кластеризации проверяет результаты анализа в качественной и объектной формах. В рамках исследования может выполняться два вида оценки: экспертная и формальная. Экспертная оценка включает ручную проверку, усреднение характеристик объектов и оценку их удаленности, проверку результатов на контрольном примере, добавление новых объектов и оценку стабильности разбиения, использование различных методов и сравнение результатов разбиения. Формальная оценка выполняется на основе формализованных критериев, например, индекса «Хие-Бепи», индекса истинности разбиения, коэффициента разбиения, индекса четкости, показателя компактности и изолированности, индекса эффективности и др.

Аналитическая оценка сложности метода MST зависит от используемого алгоритма построения минимального остовпого дерева: по алгоритму Борувки и Прима -О^Е ■ Log(V) J, по алгоритму Крускала - О^Е ■ /.ос; (7:)], где V - множество вершин

графа, Е- множество их возможных попарных соединений (ребер). Аналитическая оценка метода Fuzzy C-means имеет линейную зависимость относительно количества кластеров и исследуемых объектов, но сложность этой оценки в том, что метод представляет собой циклическую структуру с условием выхода из цикла по параметру останова.

Третья глава посвящена разработке метода адаптивной кластеризации фактографических данных смешанного типа ADAKL па основе дивизимных и итерационных методов. Развивая идеи Загоруйко Н.Г., Елкиной В.Н., Айвазяна С.А., Бсжасвой З.И., за основу метода в части первичного разделения объектов на кластеры взят метод MST, а для уточнения полученных кластеров используется метод Fuzzy C-means. Определяющими факторами в выбранной комбинации является способность при использовании теории графов выделять кластеры произвольной формы и оптимальной структуры, а при использовании математического аппарата нечетких множеств - разделение объектов с лингвистическими атрибутами.

Совокупность использованных методов и алгоритмов позволяет преодолеть недостатки каждого из них: для MST - применение нечеткости позволяет сделать более плавное разбиение, помещая объекты в разные кластеры с разной степенью принадлежности, для Fuzzy C-Means - предварительное использование MST и модифицированного критерия оптимальности позволяет сократить количество итераций исследования входного набора данных, а следовательно, и снизить временные, человеческие и технические затраты на проведение исследований.

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

9

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

Среди входных параметров метода присутствуют:

U = [г/,,м2,...,мтJ, где м( - объекты кластеризации, т — количество объектов кластеризации, i = \,m; и(. = | (Veiling,,/,),(, /2),..., (Value.п,/„)}, где Value„ -значение j атрибута i объекта кластеризации, tj — тип атрибута объекта кластеризации, п - количество атрибутов объекта кластеризации, j = \,п; К = {KitK2,...,Kn}, где А' - весовой коэффициент влияния атрибута объекта, К: e[0;l]; р - размазанность кластеров, /ге(0;10]; w - степень удаленности элементов, we(0;l]; q - максимальное количество кластеров, q < т; к - текущее количество кластеров, k<q.

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

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

Distij =||и; — Wy|| = Metric^u^uj}, где Metric - способ определения расстояния между объектами ui и иj.

Для построения минимального остовного дерева на третьем этапе рекомендуется применять алгоритм Прима.

На основе построенной оптимизированной структуры объектов в виде дерева строится матрица нечеткого разбиения, которая обладает следующими характеристиками: F = е [0,l],/<k,j= \,т, где //; - степень принадлежности / объекта к j клак _

стеру. Матрица разбиения обладает следующими свойствами: Д, = 1,7 = \,т,

i=1

т _

м

На третьем шаге четвертого этапа выполняется первичное выделение центров кластеров с помощью следующего выражения:

Vf = Лу^^и^и,. g C'/jj, где К* - центр кластера i для к итерации расчета, /Ivg -оператор вычисления среднего значения показателей объектов, входящих в кластер /, С* - i кластер для к итерации расчета, i = \,k, j = \,m.

На следующем шаге выполняется расчет матрицы расстояний от объектов до центров кластеров V:

Dixt.j = - = Metric(V*,aj), где Distk - матрица расстояний от объектов до

центров кластеров для к итерации расчета,/ = 1,к, j = \,m, Metric - способ определения информационного расстояния между объектами.

Фактографические данные

Конфигурационные4, параметры метода

Этап 1. Нормализация значений числовых атрибутов

Этап 2. Вычисление матрицы взаимных расстояний между объектами Dista

Этап 3. Построение минимального остовного дерева

JZ

Этап 4. Разделение объектов на кластеры и построение матрицы нечеткого разбиения

Шаг 1. Определение количества кластеров итерации

Шаг 2. Разделение минимального остовного дерева на к кластеров

Шаг 3. Расчет центров кластеров

Шаг 4. Расчет матрицы расстояний от объектов до центров кластеров

Шаг 5. Нормализация матрицы расстояний Dis!*

Шаг 6. Соотнесение объектов к кластерам в соответствии со степенью удаленности элементов ___ кластера

Шаг 7. Расчет степени принадлежности элементов кластеру

Шаг 8. Нормализация матрицы нечеткого разбиения

Шаг 9. Вычисление центров полученных кластеров

Шаг 10. Оценка полученного разбиения

Шаг 11. Уменьшение количества кластеров

Шаг 12. Оценка количества кластеров

Этап 5. Выбор наилучшего разбиения

/Фактографические

данные, распределенные по кластерам

Рис. 3. Основные этапы метода адаптивной кластеризации АйАКи Нормализация матрицы расстояний от объектов до центров кластеров V? выполняется на основе формулы:

Distl

Dist¡ -

.= I)*0;01x1*|м«:(0/у/,') = о|, где нормализованная матрица взаимных расстояний от объектов до центров кластеров для к итерации расчета, / = 1,к, у = \,т.

При соотнесении объектов к кластерам в соответствии со степенью удаленности элементов кластера используется следующее выражение:

Ои^' < н>или О/л/*' = Мш(лЦ'), где г = 1 ,к, у = 1 ,т. После разнесения объектов по кластерам выполняется расчет степеней принадлеж-

ности к кластерам текущей итерации алгоритма:

ч2

= (1 - Ш?/,*') , где I = 1, к, у = \,т.

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

=о[,где /=!,£, У = 1,т.

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

н

У-1

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

ок =

1

т*к2 2

¡=1,*

1 И1 * т м К

Мт^-и^Мах^ ./=1 и^У и\*к к'

где | — количество элементов в кластере г; — = Ме1г1с{у^ — расстояние от центра кластера г до элемента и-; е V* — отражение условия о принадлежности элемента кластеру.

Предложенная оценка является составной:

Область 1 - нацелена на выделение кластеров с наименьшими взаимными расстояниями и наибольшим количеством элементов в кластере по отношению к общему количеству кластеров.

Область 2 - выделяет количество получаемых кластеров и ведет к уменьшению их количества.

Область 3 - нацелена па минимизацию взаимных расстояний между полученным центром кластера и элементами с учетом степени принадлежности.

Выбор наилучшего разбиения по результатам всех итераций выполняется на основе лучшей оценки: 00пт = МЛХ(0'), где / = .

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

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

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

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

\th-M4 \t\B-AvglBf

0,= Ч -г-= ---,|0,-О2И,где

0Г02 - оценочная функция исходного набора данных 1 и 2 соответственно; Л,В -исходные наборы данных 1 и 2 соответственно; г, о - количество объектов в исходных наборах данных 1 и 2 соответственно; 8 - доверительный интервал; ||Д, — - - оператор вычисления расстояния между объектом и

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

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

Распределение элементов расширяющего множества (В) по вычисленному расстоянию до ближайших к объектов (в соответствии с критерием 00пт = МЛХ{0')) из расширяемого множества (Л) выполняется следующим образом:

= (' - 1)1x1*""")*///7 Мах^Ш^^* , где ¡ -=\,к - номер кластера

множества Л; _/ = 1,о - порядковый номер элемента из множества В-, .ч е[1,г] - порядковый элемента из множества А из ближайших к объектов; I — порядковый номер бли-

жайшего элемента из множества А для элемента из множества В, / 6 [1,г];

=1^. - - расстояние между ближайшими элементами из множеств А и В; Мах(ОШу^ - максимальное расстояние от элемента из множества В до элемента из множества Л; цл- степень принадлежности элемента / из множества А к кластеру г.

Итоговые кластеры

Итоговые | кнастеры)

Рис. 4. Докпастеризация исходных данных.

В результате расчета аналитической сложности метода получены следующие оценки: с линейной нормализацией - о{т2 *(а + Ь + Lg{rn) + , со статистической нормализацией- О^т2 *(a + b + Lg[m2} + q^, и докластеризации: О^т + п)2 + где

а - количество входных числовых атрибутов, Ъ - количество входных лингвистических атрибутов, т - количество кластеризуемых объектов набора данных 1, п - количество кластеризуемых объектов набора данных 2, ц — общее количество кластеров. Основным недостатком разработанного метода является квадратичная зависимость аналитической сложности от количества исходных данных по объектам кластеризации.

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

14

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

Четвертая глава посвящена описанию программного решения (ПР), реализующего ADAKL.

Целью реализации метода в виде ПР является автоматизация процесса обработки исходных данных по разработанным алгоритмам для проведения практических исследований. Данное ПР можно отнести к типу интегрированных решений ввиду его функциональных возможностей. Также в этой главе описывается архитектура ПР и основные алгоритмы, реализованные в ПР. Инфологическая/датапогическая модели ПР предусматривают хранение основных сущностей, необходимых для настройки и запуска анализа, а также сущности, которые позволяют сохранить результаты исследования массивов для последующего сравнительного анализа. ПР позволяет сохранять промежуточные, итоговые результаты анализа и используемые данные в следующих форматах: текстовый, гипертекстовой разметки, MS Excel 2003.

Во второй половине главы описываются три основных и одна дополнительная серии по пятьдесят экспериментальных исследований для оценки работоспособности ADAKL в сравнении с другими алгоритмами (SOM, k-средпих, ADAKL). Исследуемые массивы данных имеют следующие характеристики:

Табл. 1. Сводная таблица исследуемых данных.

Характеристика Исследование Общее кол-во исх. данных (шт. записей) Кол-во атрибутов

Числовые (шт.) Текстовые (шт.) Общее (шт.)

1 267 0 101 5(21 5 121

2 533 73 [721 3 131 76 [751

3 267 5(21 4 [21 9 [41

4 450 3 131 2П1 5 141

Оценка результатов кластерного анализа выполнена на основе показателей выполненной кластеризации с помощью индекса истинности разбиения: ^ г \я!к^<к

и = — *< , где д - количество кластеров по итогам кластеризации; г -

п [к/д,д>к

количество элементов, правильно распределенных по соответствующим кластерам; к — исходное количество кластеров; п - количество объектов кластеризации.

В соответствии с полученной итоговой оценкой (табл. 2) наилучшее разбиение на исследованных массивах по сериям экспериментов получено с применением разработанного метода АОАКЬ. Проведенные эксперименты подтвердили, что использование интеграции методов кластеризации (многоэтапная кластеризация) улучшает качество выявления знаний в сравнении с одпоэтапными методами, а также то, что превосходство раз-

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

Табл. 2 Средневзвешенная оценка разбиений.

Оценка Метод Средневзвешенная оценка

Без задания кол-ва кластеров С заданным количеством кластеров (без учета лингвистических атрибутов) С заданным количеством кластеров (с учелгом лингвистических атрибутов) Итоговая

1 0.7913 0.9150 0.9237 0.8767

2 - 0.8232 - 0.8232

3 0.9762 0.9981 0.9990 0.9911

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

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

С помощью ПР решена практическая задача в области брокерского обслуживания по выделению групп клиентов и определена их доля от общего количества клиентов (рис. 5). Последующий анализ экономических показателей полученных групп объектов позволил дать названия кластерам (Кластер 1 «Долгосрочные инвесторы» - 23%, Кластер 2 «Спекулянты» - 47%, Кластер 3 «Потребители» - 16%, Кластер 4 «Паевые фонды» -3%, Кластер 5 «Акционеры» - 11%) и разработать более целевую, направленную на конкретную клиентскую группу, тарифную политику, а также предложить им более выгодные условия по совершаемым видам операций, увеличив количество этих операций и объем комиссионных сборов. Это положительно повлияет на доходность данного направления деятельности кредитной организации.

Основные выводы и результаты диссертационной работы

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

Основные результаты диссертационной работы

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

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

3. На основе литературных источников для выбора метода кластеризации выделено восемь критериев и разработаны рекомендации.

4. Разработан метод адаптивной кластеризации (ЛПЛК1,) па основе интеграции методов минимального остовного дерева и нечетких К-средних, определяющий количество кластеров с помощью локального критерия, обладающий двухэтаппостыо, нечеткостью при распределении объектов по кластерам, возможностью использования объектов с разными типами атрибутов, приемлемым временем работы и конечностью результата.

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

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

7. Разработанный метод АОАКЬ реализован в виде программного решения и проведены серии экспериментов, которые подтверждают аналитическую оценку и состоятельность в сравнении с имеющимися методами (к-средних, 80М).

Публикации

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

1. Нейский, И.М., Филиппович, А.Ю. Методика адаптивной кластеризации фактографических данных на основе интеграции алгоритмов MST и Fuzzy C-means / И.М. Нейский, А.Ю. Филиппович // Известия высших учебных заведений. Проблемы полиграфии и издательского дела. - М.: Изд-во МГУП, 2009. - №3 - С. 48-61.

Другие публикации

2. Нейский, И.М. Характеристика технологий и процессов интеллектуального анализа данных / И.М. Нсйский // Интеллектуальные технологии и системы. Сборник учебно-методических работ и статей аспирантов и студентов. — М.: Изд-во ООО «Эликс+», 2005. - Выпуск 7. - С. И1-122.

3. Нейский, И.М. Классификация и сравнение методов кластеризации / И.М. Нейский // Интеллектуальные технологии и системы. Сборник учебно-методических работ и статей аспирантов и студентов. - М.: НОК «CLAIM», 2006. - Выпуск 8. - С. 130-142.

4. Нейский, И.М., Филиппович, А.Ю. Интеграция дивизимных и итерационных методов для адаптивной кластеризации фактографических данных / И.М. Нсйский, А.Ю. Филиппович //Труды конференции «Телематика^ООЭ» -М.: 2009. - С. 413-414.

5. Нейский И.М. Адаптивная кластеризация па основе дивизимных и итерационных методов / И.М. Нейский // Сборник трудов третьей международной паучно-практической конференции «Информационные технологии в образовании, науке и производстве» под редакцией Ю.А. Ромапенко. - МО.: 2009. - С. 172-175.

6. Нейский И.М. Докластеризация как способ оптимизации времени анализа исходных данных / И.М. Нейский // Научная школа для молодых ученых «Компьютерная графика и математическое моделирование (Visual Computing)»: тезисы и доклады. - М.: 2009.-С. 141-161.

7. Нейский, И.М., Филиппович, А.Ю. Сегментация клиентов брокерского обслуживания / И.М. Нейский, А.Ю. Филиппович // Бизнес-аналитика. Вопросы теории и практики. Использование аналитической платформы Deductor в деятельности учебных заведений: сборник материалов межвуз. науч. практ. конф. - Рязань: Лаборатория баз данных, 2010.-С. 102-111.

8. Нейский, И.М. Экспериментальные исследования адаптивной кластеризации фактографических данных / И.М. Нейский // Материалы научной межвузовской конференции преподавателей, аспирантов, молодых ученых и специалистов «Печатные средства информации в современном обществе (к 80-лстию МГУП)». Секция «Электронные средства информации в современном обществе. Сб. тез. докл. -М.: 2010. - С. 55-58.

Подписано в печать 22.10.2010 г. Формат бумаги 60x90. 1/16. 1 пл. Тираж: 100 экз. Заказ № 354

Типография Aegis-Print 115230, Москва, Варшавское шоссе, д. 42 Тел.: 543-50-32 www.autoref.ae-print.ru

ВВЕДЕНИЕ.

ГЛАВА 1. АНАЛИЗ МЕТОДОВ И СИСТЕМ КЛАСТЕРИЗАЦИИ ФАКТОГРАФИЧЕСКИХ ДАННЫХ.

1-Х- Основные определения.;.

1.2. Методы кластеризации.12'

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

1.2.3. Сравнение методов кластеризации.

1.3. Сравнение аналитических программных комплексов.

1.4. Предметная область исследования.

1.4.1. Структура рынка ценных бумаг.

1.4.2. Виды ценных бумаг.г.

1.4.3. Участники рынка ценных бумаг.

1.4.4. Брокерская деятельность профессионального участника рынка ценных бумаг.

1.4.5. Основные характеристики предметной области исследования.

1.5. Постановка задачи адаптивной кластеризации.

1.6. Выводы.

ГЛАВА 2. ИССЛЕДОВАНИЕ И АДАПТАЦИЯ СУЩЕСТВУЮЩИХ МЕТОДИК КЛАСТЕРИЗАЦИИ ФАКТОГРАФИЧЕСКИХ ДАННЫХ.

2.1. Формализованная модель предметной области.

2.2. Методика адаптивной кластеризации.

2.3. Выбор метода кластеризации.

2.3.1. Выбор метода на основе рекомендаций.

2.3.2. Выбор метода на основе критериев.

2.3.3. Выбор метода по общему алгоритму.

2.4. Адаптация методов кластеризации.50'

2.4.1. Параметрическая настройка методов кластеризации.

2.4.2. Адаптация методов кластеризации к предметной области.

2.5. Оценка кластеризации.

2.6. Выводы.

ГЛАВА 3; АДАПТИВНАЯ КЛАСТЕРИЗАЦИЯ ФАКТОГРАФИЧЕСКИХ ДАННЫХ СМЕШАННОГО ТИПА.1.

3:1. Базовые принципы метода АО АКБ.60 *

3.2. Входные данные метода АПАКЪ.

3.3. Описание метода АБАКЕ.

3.4. Способы построения минимальных остовных деревьев.

3.5. Адаптация метода к предметной области.

3.6. Аналитическая оценка сложности метода.

3.7. Докластеризация исходных данных в процессе исследования.

3.8. Аналитическая оценка сложности докластеризации.

3.9. Достоинства и недостатки адаптивной кластеризации.

3.10. Обоснование локального критерия оценки качества разбиения

3.11. Выводы.

ГЛАВА 4. ПРОГРАММНЫЙ КОМПЛЕКС АДАПТИВНОЙ КЛАСТЕРИЗАЦИИ.

4.1. Общее описание.

4.1.1. Цель, назначение и область применения разработки.

4.1.2. Функциональные возможности программного решения.

4.1.3. Описание сущностей и их атрибутов.

4.2. Основные алгоритмы*.

4.2.1. Алгоритмы построения минимальных остовных деревьев.

4.2.2. Алгоритм вычисления среднего значения атрибута символьного типа.

• 4.3. Форматы выходных данных.99'

4.4; Интерфейс взаимодействиям пользователем.102'

4.4.1. Граф диалога пользовательского интерфейса.

4.5. Описание эксперимента.102!

4.5.1. Описание сравнительных исследований.

4.5.2. Анализ результатов сравнительных исследований.

4.5.3. Описание оценочных исследований.

4.6. Выводы.

Актуальность

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

Изучением проблем и созданием решений в этой области активно занимаются направления Business Intelligence (Интеллектуальный анализ данных) и Knowledge Management (Управление знаниями), в рамках которых выделяются поднаправления Knowledge Discovery in Databases (Выявление знаний в базах данных), Data Mining (Анализ фактографических данных), Text Mining (Анализ неструктурированных данных) и др. В интеллектуальном анализе данных выделены шесть различных классов задач (рис. 1), такие как: классификация, регрессия, кластеризация, выявление ассоциаций, выявление последовательностей, прогнозирование.

Рис. 1. Классы задач ИАД.

Классификация позволяет выявить признаки, характеризующие однотипные группы объектов (классы), для того, чтобы по известным-значениям,этих' характеристик можно было отнести новый объект к тому или иному классу [33].

Регрессия устанавливает зависимости непрерывных выходных переменных от входных переменных [33].

Кластеризация, используя свободный поиск, выделяет в данных признаки, по которым данные можно поделить на группы [33]. Кластеризация неоднозначна, поскольку группировка данных целиком зависит от способа, по* которому измеряется информационное расстояние между записями набора данных. 4

Это задача более сложная, чем классификация, так как классы объектов изначально не предопределены [129]. Еще одним ключевым отличием классификации является то, что каждый объект однозначно относится к соответствующему классу, а при кластеризации объект может относиться к одному, двум и более кластерам (спорный объект). Сложностью кластеризации является необходимость ее оценки.

Ассогщация, в отличие от двух предыдущих задач, определяется не на основе значений свойств одного объекта или события, а имеет место между двумя или несколькими одновременно наступающими событиями [33]. Создаваемые при этом правила указывают на то, что при наступлении одного события с той или иной степенью вероятности наступает другое.

Последовательности, подобно ассоциациям, имеют место между событиями, но наступающими не одновременно, а с некоторым определенным разрывом во времени [33].

Прогнозирование — это особая форма предсказания, которая на основе особенностей поведения текущих и исторических данных оценивает будущие значения определенных численных показателей [33].

В связи с ростом динамики изменений в социально-экономической и научно-производственной среде задача кластеризации актуальна в различных сферах и предметных областях, например: выделение групп клиентов брокерского обслуживания для формирования перечня предлагаемых сервисов; формирование потребительской корзины; принятие решения о выдаче потребительского кредита; сегментирование сферы деятельности с целью повышения эффективности производительности; обработка изображений; тематический анализ биб6 лиотеки документов; оптимизация использования' складских помещений; выявление транзакций, проведенных по поддельным кредитным картам; выявление потенциальных болезней пациентов; построение показательной (репрезентативной) выборки и т.д.

Актуальность.данного направления подтверждается появлением и постоянным увеличением количества прикладного программного обеспечениях (ППО), которое предназначено для решения задач анализа-различных видов и типов данных: в начале 90-х годов рынок ППО насчитывал около десяти поставщиков, а к середине 90-х годов - более пятидесяти компаний малого, среднего и большого размера [92, 129]. Инструменты Интеллектуального Анализа Данных (ИАД)1 могут быть представлены как самостоятельный продукт, а также как составная часть основного программного продукта. Примерами таких программных продуктов являются SPSS (Statistical Package for the Social Sciences, в переводе с англ. - статистический пакет для социальных наук), Statistica (в переводе с англ. - статистика), SAS (Statistical Analysis Software, в переводе с англ. - программное обеспечение для статистического анализа) [46].

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

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

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

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

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

Целью диссертационной работы является разработка методики адаптивной кластеризации фактографических данных на основе интеграции методов минимального остовного дерева и нечетких К-средних.

Для реализации поставленной цели в работе решаются следующие задачи:

1. Исследование методов и систем интеллектуального анализа данных, используемых для кластеризации фактографических данных.

2. Разработка методики адаптивной кластеризации фактографических данных.

3. Разработка рекомендаций по выбору существующих алгоритмов кластеризации.

4. Разработка метода кластеризации.

5. Разработка метода докластеризации.

6. Разработка программного комплекса для автоматизации предложенного метода кластеризации.

7. Оценка эффективности предложенной методики.

Диссертационная работа состоит из введения, четырех глав, заключения, списка использованной литературы и приложений. Общий объем текста диссертации составляет 185 страниц, содержит 30 таблиц, 21 схему, 137 источников, из них 43 зарубежных.

Основные результаты диссертационной работы:

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

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

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

4. Для выбора метода кластеризации на основе литературных источников выделено восемь критериев.

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

6. Разработан метод адаптивной кластеризации (ADAKL) на основе интеграции методов MST и Fuzzy С - Means, определяющий количество кластеров на основе локального критерия, обладающий двухэтапностью, восемью входными параметрами настройки, нечеткостью при распределении объектов по кластерам, возможностью использования объектов с разными типами атрибутов, приемлемым временем работы и конечностью результата.

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

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

9. Разработанный метод АБАКХ реализован в виде программного решения, который подтверждает аналитическую оценку.

10. На основе программного решения проведены экспериментальные исследования и оценка состоятельности разработанного метода в сравнении с имеющимися методами (к - средние, карты Кохонена).

11. Выполнена оценка аналитической сложности разработанных методов.

Заключение

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

1. Abonyi J., Roubos J.A., Babuska R., Szeifert F. Modified Gath-Geva Fuzzy Clustering for Identification of Takagi-Sugeno Fuzzy Models. 2002. Источник: www.fint.vein.hu.

2. Abonyi J., Roubos J.A., Oosterom M., Szeifert F. Compact TS-Fuzzy Models through Clustering and OLS plus FIS Model Reduction. 2001. Источник: www.fint.vein.hu.

3. Agrawal R., Gehrke J., Gunopulos D., Raghavan P. Automatic Subspace Clustering of High Dimensional Data for Data Mining Applications. 1999. Источник: citeseer.ist.psu.edu.

4. Babuska R. Data-Driven Fuzzy Modeling: Transparency and Complexity Issues. 1999. Источник: www.et.tudelft.nl.

5. Babuska R., Verbruggen H.B., Hellendoorn H. Promising Fuzzy Modeling and Control Methodologies for Industrial Applications. 1999. Источник: www.fuzzytech.com.

6. Boriana L. Milenova, Marcos M. Campos O-Cluster: Scalable Clustering of Large High Dimensional Data Sets. 2002. Источник: asun.ifino.ru.

7. Candillier L., Tellier I., Torre F., Bousquet O. SSC: Statistical Subspace Clustering. 2004. Источник: www.grappa.univ-lille3.fr.

8. Charu C. Aggarwal, Cecilia Procopiuc, Joel L. Wolf, Philip S. Fast Algorithms for Projected Clustering. 1999. Источник: citeseer.ist.psu.edu.

9. Eberkart R., Simpson P., Dobbins R. Computational Intelligence PC Tools. -AP Professional, 1996.

10. Entriken R., Vossner S. Genetic algorithms with cluster analysis for production simulation. 1997. Источник: www.informs-cs.org.

11. Fasulo D. An Analysis Of Recent Work on Clustering Algorithms. 1999. Источник: citeseerx.ist.psu.edu.

12. Frawley W. L., Piatetsky-Shapiro G., Matheus C. J. Knowledge discovery in databases: An overview // AI Magazine. 1992. - № 13(3).

13. Fu Y., Sandhu K., Ming-YiShih A Generalization-Based Approach to Clustering of Web Usage Sessions. 2000. Источник: link.springer.de.

14. Ganti V., Ramakrishnan R., Gehrke J. Clustering Large Datasets in Arbitrary Metric Spaces. 1999. Источник: www.datashaping.com.

15. Guha S., Rastogi R., Shim K. CURE An Efficient Clustering Algorithm for Large Databases. 1998. Источник: citeseer.ist.psu.edu.

16. He H., Singh A. Efficient Algorithms for Mining Significant Substructures in Graphs with Quality Guarantees. Department of Computer Science University of California, Santa Barbara, 2004.

17. Hongxing Li, C.L. Philip Chen, Han-Pang Huang Fuzzy Neural Intelligent Systems. Mathematical Foundation and the Annlications in Engineering. CRC Press LLC, 2001.

18. Hung T. Nguyen, Mukaidono M., KreinovichV. Probability Of Implication Logical Version of Bayes Theorem, and Fuzzy Logic Operations. 2007.

19. Jain A.K., Dubes R.C. Algorithms for clustering data. Prentice-Hall, 1988. Источник: lib.mexmat.ru.

20. Jain A.K., Murty M.N., Flynn P.J. Data Clustering: A Review. Источник: csee.umbc.edu.

21. Jang J., Sun Ch., Mizutani E. Neuro-Fuzzy and Soft Computing. A. Computational Approach to Learning and Machine Intelligence. Prentice-Hall, 1997.

22. Jochheim-Richter A., Hillemann Т., Scharf J., Manns M.P., Ott M. Detection of regulated genes by cluster analysis of serial microarraygene expression data in early murineliver development. 2004.

23. Karypis G., Eui-Hong (Sam) Han, Kumar V. Chameleon: Hierarchical Clustering Using Dynamic Modeling. Journal "Computer", University of Minnesota,

24. Dept. of Computer Science and Eng., vol. 32, no. 8, pp. 68-75, 1999. Источник: www2.computer.org.

25. Knowledge Discovery Through Data Mining: What Is Knowledge Discovery? Tandem Computers Inc., 1996.

26. Kogan J., Nicholas C., Teboulle M. Clustering Large and High Dimensional data. Источник: www.csee.umbc.edu.

27. Kosko B. Fuzzy systems as universal approximators. IEEE Transactions on Computers, vol. 43, No. 11 - P. 1329-1333, 1994. Источник: sipi.usc.edu.

28. Kosko B. Optimal Fuzzy Rules Cover Extrema. International Journal of Intelligent Systems, vol. 10, no. 2, pp. 249-255, 1995. Источник: sipi.usc.edu.

29. Krishnapuram R., Joshi A., Yi L. A Fuzzy Relative of the k-Medoids Algorithm 1999. Источник: citeseer.ist.psu.edu.

30. Neel J. Cluster analysis methods for speech recognition. 2005. Источник: www.speech.kth.se.

31. Park J., Han H. Existence and uniqueness theorem for a solution of fuzzy differential equations. Electronic Publishing House, 1996.

32. Parsaye K. A Characterization of Data Mining Technologies and Processes. -DM Review Magazine, no. 11, 1998. Источник: www.dmreview.com.

33. Punj G., Stewart David W. Кластерный анализ в маркетинговых исследованиях: обзор и предпосылки применения. Journal of Marketing Research, Vol. XX, (May 1983), pp.134-148, 1983.

34. STATSOFT Кластерный анализ. Электронный учебник. Источник: www.statsoft.ru.

35. STATSOFT Обобщенные методы кластерного анализа. Электронный учебник. Источник: www.statsoft.ru.

36. Shihab A.I. Fuzzy clustering algorithms and,their application to medical image analysis. 2000. Источник: cism.kingston.ac.uk.

37. Shu-Chuan Chu, John F. Roddick and Jeng-Shyang Pan An Incremental Multi-Centroid, Multi-Run Sampling Scheme for k-medoids-based Algorithms Extended Report. - 2002. Источник: citeseer.ist.psu.edu.

38. Speer N., Merz P., Spieth C., Zell A. Clustering Gene Expression Data with Memetic Algorithms based on Minimum Spanning Trees. University of Tubingen, Center for Bioinformatics. Источник: fs.informatik.uni-tuebingen.de.

39. Spellabs SQL 2005 Data Mining. 2007. Источник: www.spellabs.ru.

40. Spellabs Применение методов интеллектуального анализа данных (Data Mining) в интернет торговле. 2008. Источник: www.spellabs.ru.

41. Sven О. Krumice Algorithmen und Datenstrukturen. Technische Universität Berlin, 2003. Источник: www.zib.de.

42. Tamas F.D., Abonyi J. Trace elements in clinker II. Qualitative identification by fuzzy clustering. - 2002. Источник: www.fint.vein.hu.

43. Vanjukevich O.N., Popov A.A. The F-test by testing of hypotheses about structure variations in the fuzzy regression models. NSTU, 2005. Источник: www.nstu.ru.

44. Wang W. Clustering. COMP 290-90 Research Seminar, Spring 2006.

45. Wright P. Knowledge Discoveiy In Databases: Tools and Techniques. Источник: http://www.acm.org/crossroads/xrds5-2/kdd.html.

46. Zhang Т., Ramakrishnan R., Livny M. BIRCH: An Efficient Data Clustering Method for Very Large Databases. 2006. Источник: citeseer.comp.nus.edu.sg.

47. Абаев JI.4. Выбор вариантов в' нечеткой среде: бинарные отношения и нечеткая декомпозиция. 2006. Источник: www.masters.donntu.edu.ua.

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

49. Алтунин А.Е., Семухин М.В. Модели и алгоритмы принятия решений в нечетких условиях. Источник: www.plink.ru.

50. Андрейчиков A.B., Андрейчикова О.Н. Анализ, синтез, планирование, решений в экономике. М.: Финансы и статистика, 2000:

51. Андрейчиков A.B., Андрейчикова О.Н. Интеллектуальные информационные системы:.Учебник. М;: Финансы и статистика, 2004.

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

53. Бендерская E.H., Жукова C.B. Сравнительный анализ хаотической нейронной сети и нейронной сети Кохонена. 2005.

54. Бендерская E.H., Жукова C.B. Решение задач кластеризации с использованием хаотической нейронной сети. Сборник научных трудов 7-ой всероссийской научно-технической конференции «Нейроинформатика-2005», 4.1. -Москва, с. 54-60, 2005.

55. Бирман Г., Шмидт С. Экономический анализ инвестиционных проектов. М.: Банки и биржи, ЮНИТИ, 1999.

56. Бирюков Е.В., Корнев М.С. Практическая реализация нечеткой нейронной сети при краткосрочном прогнозировании электрической нагрузки. -2005. Источник: library.mephi.ru.

57. Богданов Ю.В., Швандар В.А. Инвестиционный анализ. М.: Юнити, 2000.

58. Борисов А.Н., Алексеев A.B., Крумберг O.A. Модели принятия решений на основе лингвистической переменной. Рига: Зинатне,-1989.

59. Боровиков В.П., Боровиков И.П. STATISTICA. Статистический анализи обработка данных в среде Windows. M.: Филинъ, 1998.

60. Венкатеш Гаити, Иоханнес Герке, Раджу Рамакришнан Добыча данных в сверхбольших базах данных. Открытые системы № 9-10, 1999. Источник: text.marsu.ru.

61. Виттих В. А., Майоров И. В., Скобелев П. О., Сурнин О. JI. Интеллектуальный анализ данных с помощью кластеризации. Источник: www.kg.ru.

62. Вовк О.JI. Иерархический агломеративный алгоритм кластеризации для выделения регионов изображений. 2004. Источник: www.graphicon.ru.

63. Воронцов К.В. Лекции по алгоритмам кластеризации и многомерному шкалированию. 2007. Источник: www.ccas.ru.

64. Галанов В.А. Производные инструменты срочного рынка: фьючерсы, опционы, свопы: Учебник. М.: Финансы и статистика, 2002.

65. Гиляров В.Н, Крюков А.Ю, Бондарчук П.В. Использование Neuro-Fuzzy технологии для генерации и оптимизации эвристических правил программный продукт Лингвогенератор. - 2006. Источник: www.masters. donntu. edu.ua.

66. Гиршов Е. Алгоритмы кластеризации. Источник: logic.pdmi.ras.ru.

67. Гончаров М. Алгоритм Spellabs Regression Clustering. 2005. Источник: www.spellabs.ru.

68. Гончаров М. Кластеризация на основе нечетких отношений. Алгоритм Fuzzy Relation Clastering. 2005. Источник: www.spellabs.ru.

69. Гончаров М. Кластерный анализ. 2008. Источник: www.spellabs.ru.

70. Горшков В. Классификация программных решений. 1998. Источник: www.miracle.ru.

71. Дьяконов В.П., Круглов В.В. MATLAB 6.5 SP1/7/7 SP1/7 SP2 + Simu-link 5/6. Инструменты искусственного интеллекта и биоинформатики. Серия "Библиотека профессионала". М.: СОЛОН-ПРЕСС, 2006.

72. Дюк В. Data Mining состояние проблемы, новые решения. Источник: inftech.webservis.ru.

73. Дюк В.А. Data Mining интеллектуальный анализ данных. Источник: www.olap.ru.

74. Дюк В., Самойленко A. Data Mining: учебный курс. СПб: Изд. Питер, 2001.

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

76. Ежов A.A., Шумский С.А. Нейрокомпьютинг и его применения в экономике и бизнесе / Серия "Учебники экономико-аналитического института, МИФИ" под ред. проф. В.В. Харитонова. М.: МИФИ, 1998.

77. Ефимов A.C., Морёнов O.A. Основы нечеткой логики, логико-лингвистические модели. Материалы семинара ITLab, НГУ им. Н.И.Лобачевского, 2004.

78. Жуков Е.Ф. Рынок ценных бумаг: учеб. пособие для вузов. М.: ЮНИ-ТИ-ДАНА, 2002.

79. Загоруйко Н. Г. Прикладные методы анализа данных и знаний. Новосибирск: ИМ СО РАН, 1999.

80. Загоруйко Н. Г., Ёлкина В. Н., Лбов Г. С. Алгоритмы обнаружения эмпирических закономерностей. Новосибирск: Наука, 1985.

81. Заде Л. Понятие лингвистической переменной и его применение к принятию приближенных решений. М.: Мир, 1976.

82. Иванов А.П. Финансовые инвестиции на рынке ценных бумаг. М.: Издательско-торговая корпорация «Дашков и К», 2004.

83. Иванова H.H., Ярушкина Н.Г. Исследование многошагового нечеткого вывода на примере построения экспертной системы оценки экологической безопасности производственной деятельности. 2006. Источник: www.raai.org.

84. Ивахненко А.Г., Юрачковский Ю.П. Моделирование сложных систем по экспериментальным данным. М.: Радио и связь, 1987.

85. Интегрированные модели и мягкие вычисления в искусственном, интеллекте. М.: Наука, 2001.

86. Киселев М., Соломатин Е. Средства добычи знаний в бизнесе и финансах. Открытые системы № 4 (24), 1997.

87. Колмогоров И.О. Методы и алгоритмы анализа структуры многомерных данных. 2004. Источник: www.codenet.ru.

88. Кормен Томас X., Лейзерсон Чарльз И., Ривест Рональд JL, Штайн Клиффорд Алгоритмы: построение и анализ, 2-е издание. Пер. с англ. М.: Издательский дом "Вильяме", 2005.

89. Котов А., Красильников И. Кластеризация данных. 2006. Источник: aisystem.narod.ru.

90. Кречетов И. Продукты для интеллектуального анализа данных. Рынок программных средств, N14-15, с.32-39, 1997.

91. Круглов В.В., Дли М.И. Интеллектуальные информационные системы: компьютерная поддержка систем нечеткой логики и нечеткого вывода. М.: Физматлит, 2002.

92. Круглов В., Дли М., Голунов Р. Нечеткая логика и искусственные нейронные сети. 2002.

93. Лагутин М.Б. Наглядная математическая статистика. М.: П-центр, 2003.

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

95. Масалович А. Нечеткая логика в бизнесе и финансах. Источник: www.tora-centre.ru.

96. Министерство образования и науки Кластеризация данных при помощи нечетких отношений в Data Mining. Источник: www.ami.nstu.ru.

97. Миркин Я.М. Ценные бумаги и фондовый рынок. М.: Перспектива, 1995.

98. Мусатов В.Т. Фондовый рынок: Инструменты и механизмы. М.: Международные отношения, 1991.

99. Нейский, И.М. Характеристика технологий и-процессов интеллектуального анализа данных. Интеллектуальные технологии и системы. Сборник учебно-методичёских работ и статей аспирантов и студентов. — М.: Изд-воООО -«Эликс+», 2005. Выпуск 7. - С. 111-122.

100. Нейский, И.М. Классификация и сравнение методов кластеризации. Интеллектуальные технологии и системы. Сборник учебно-методических работ и статей аспирантов и студентов. М.: Изд-во ООО "Элике +", 2006. - Выпуск 8.-С. 111-122.

101. Нейский, И.М., Филиппович, А.Ю. Интеграция дивизимных и итерационных методов для адаптивной кластеризации фактографических данных. Труды конференции «Телематика"2009» — М.: 2009. С. 413-414.

102. Нейский И.М. Докластеризация как способ оптимизации времени анализа исходных данных. Научная школа для молодых ученых «Компьютерная графика и математическое моделирование (Visual Computing)»: тезисы и доклады.-М., 2009.-С. 141-161.

103. Осовский С. Нейронные сети для обработки информации. М.: Финансы и статистика, 2004.

104. Паклин Н. Нечеткая логика математические основы. - 2006. Источник: www.basegroup.ru.

105. Паклин Н. Алгоритмы кластеризации на службе Data Mining. 2007. Источник: www.basegroup.ru.

106. Паклин Н. Кластеризация категорийных данных: масштабируемый*алгоритм CLOPE. 2007. Источник: www.basegroup.ru.

107. Пиотровский А.Л., Денисов A.B. Кластерный анализ как инструмент подготовки эффективных маркетинговых решений. Практический маркетинг № 05, 2001.

108. Пустовалова О.С. Искусственные нейронные сети в задачах кластеризации. 2005. Источник: www.usm.md.

109. Романов В.П. Интеллектуальные информационные системы в• экономике: Учебное пособие 7 Под ред. д.э.н., проф: Н:П. Тихомирова. Мл Издательство «Экзамен», 2003.

110. Рукин А. Портфельные инвестиции. Финансово математические методы. - Рынок ценных бумаг, № 18, с. 45-47, 1999.

111. Рутковская Д., Пилиньский М., Рутковский JL Нейронные сети, генетические алгоритмы и нечеткие системы: Пер. с польск. И.Д.Рудинского. М.: Горячая линия - Телеком, 2006.

112. Рухлов А. Принципы портфельного инвестирования. М.: Перспектива, 1997.

113. Рыбаков Г. Построение минимального остовного дерева (алгоритмы Крускала, Прима, Борувки). 2005. Источник: rain.ifino.ru.

114. Соловьев В.Д. Кластерный анализ многофакторных лингвистических понятий. Материалы международной конференции «Диалог», 2000.

115. Стариков А. Использование самоорганизующихся карт в задачах кластеризации. 2006. Источник: www.basegroup.ru.

116. Стариков А. Самоорганизующиеся карты Кохонена математический аппарат. - 2006. Источник: www.basegroup.ru.

117. Столяров JI.H. Введение в теорию дискретного прецедентного анализа динамических систем. 1998. Источник: www.sinc.ru.

118. Тельнов Ю.Ф.4 Интеллектуальные информационные системы в экономике. Учебное пособие. Издание третье, расширенное и доработанное. Серия «Экономика и бизнес». -М.: СИНТЕГ, 2002.

119. Трухачёв A.A. Кластеризация и-визуализация информации с помощьюнейронных сетей. 2003. Источник: www.library.mephi.ru.

120. Уоссермен Ф. Нейрокомпьютерная техника: Теория и практика. Перевод на русский язык, Ю. А. Зуев, В. А. Точенов, 1992.

121. Федотов А. Реализация системы нечеткого вывода. 1999.

122. Хайкин С. Нейронные сети: полный курс, 2-е издание.: Пер. с англ. -М.: Издательский дом «Вильяме», 2006.

123. Царегородцев ВТ. Масштабируемые алгоритмы кластерного анализа: назад в будущее? 2006. Источник: www.neuropro-.ru.

124. Царегородцев В.Г. Пригодность карт Кохонена для визуализации и разведочного анализа данных. 2006. Источник: www.neuropro.ru.

125. Чубукова И.A. Data Mining: Учебное пособие. М.: Интернет-Университет Информационных Технологий; БИНОМ. Лаборатория знаний, 2006.

126. Шиляева Т.Ю., Ищенко И.П., Кулик Г.М., Пономарев Э.Б. Исследование возможностей личностной типизации средствами факторного и кластерного анализа. Источник: www.kurgan-city.ru.

127. Шишлянникова Л.М. Математическое сопровождение научной работы с помощью статистического пакета SPSS for Windows 11.5.0 // Учебно-методическое пособие. М.: МГППУ, 2005. Источник: matlab.mgppu.ru.

128. Штовба С. Д. Введение в теорию нечетких множеств и нечеткую логику. Источник: matlab.exponenta.ru.

129. Щавелёв Л. В. Способы аналитической обработки данных для поддержки принятия решений. Журнал "СУБД", 1998, №4-5.

130. Щавелёв Л. В., Коровкин С. Д., Левенец И. А. Агрегация и интеллектуальный анализ информации Хранилищ Данных. Новые информационные технологии: материалы науч.-практ. семинара / Моск. гос. ин-т электроники и математики. - М., 1998.

131. Ярушкина Н.Г. Основы теории нечетких и гибридных систем. М.: Финансы и статистика, 2004.

132. Ярушкина Н.Г. Гибридные системы, основанные на мягких вычислениях: определения, архитектура, возможности. Программные продукты и системы, № 3, 2002.

133. Яхъяева Г. Э. Нечеткие множества и нейронные сети: Учебное пособие. М.: Интернет-Университет Информационных Технологий; БИНОМ. Лаборатория знаний, 2006.