Тверь, КИИ-2010, 20.сентября КЛАСТЕРИЗАЦИЯ ИНФОРМАЦИОННЫХ РЕСУРСОВ НА ОСНОВЕ ГЕНЕТИЧЕСКОГО АЛГОРИТМА Н. Г. ЯРУШКИНА, А.В. ЧЕКИНА. - презентация

1 Тверь, КИИ-2010, 20.сентября КЛАСТЕРИЗАЦИЯ ИНФОРМАЦИОННЫХ РЕСУРСОВ НА ОСНОВЕ ГЕНЕТИЧЕСКОГО АЛГОРИТМА Н. Г. ЯРУШКИНА, А.В. ЧЕКИНА

2 Тверь, КИИ-2010, 20.сентября 2 План доклада Генетическая кластеризация информационных ресурсов Генетическая оптимизация вычислительных сетей при автоматизированном проектировании Выводы. Особенности промышленных приложений ГА.

3 Тверь, КИИ-2010, 20.сентября КЛАСТЕРИЗАЦИЯ ИНФОРМАЦИОННЫХ РЕСУРСОВ НА ОСНОВЕ ГЕНЕТИЧЕСКОГО АЛГОРИТМА Информационный ресурс – это файл или совокупность файлов, объединенных общей семантикой и имеющих текстовую аннотацию. В частном случае, информационный ресурс – это один или несколько текстовых файлов. Текст аннотации (или текст самого ресурса) однозначно отражает смысловое содержание данного ресурса.

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

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

6 Базовые методы и решения, предложенные в интеллектуальном анализе данных для реляционных баз данных: Кластеризация; Извлечение зависимостей; Прогнозирование временных рядов; Поиск ассоциаций.

7 Обзор программных реализаций Data Miner

8 Классификация систем по методам извлечения знаний из данных

9 Языки спецификации задач извлечения знаний PMML – Predictive Model Markup Language DMQL – Data Mining Query Language MSQL – Minig Strucrured Query Language Microsoft OLE DB for Data Mining specification in SQL Server 2000

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

11

12

13

14

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

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

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

18 Структура хромосомы Хромосома представляет собой массив пар (документ, кластер). Длина такого массива всегда будет такой, сколько документов требуется разбить на кластеры. Эта информация представлена в БД идентификатором информационного ресурса (документа) и номером кластера. Соответственно, если стоит задача разбить информационные ресурсы на N кластеров, то его значения варьируются от 1 до N. Документ … M Кластер35nn-1n-3n-7 …… N

19 Селекция Каждая хромосома оценивается мерой ее «приспособленности» (fitness-function). Наиболее приспособленные особи получают большую возможность участвовать в воспроизводстве потомства. После того, как для каждой хромосомы получено значение Fitness-функции, они упорядочиваются в соответствии с его величиной. В самое начало списка попадают те, мера приспособленности которых наибольшая, в конец - наименьшая. Далее при выборе потенциальных родителей применяется линейно убывающая функция случайного числа. Пропорциональный отбор назначает каждой i-й хромосоме вероятность P(i), равную отношению ее приспособленности к суммарной приспособленности популяции.

20 Кроссовер Многоточечный кроссовер в данной задаче работает следующим образом. Точка разрыва представляет собой границу между соседними элементами массива (т.е. случайным образом выбирается номер документа). Количество их будет на единицу меньше, чем количество генов в хромосоме или количество кластеризуемых документов. Родительские хромосомы разрываются в этих точках на сегменты. Затем соответствующие сегменты различных родителей склеиваются, и получаются генотипы потомков. Документ … m Кластер35nn-1n-3n-7 …… n

21 Мутация После стадии кроссовера выполняется операция мутации, которая в данной задаче представляет собой обмен двух случайных номеров кластеров. Номера документов, для которых значения кластеров меняются местами, выбираются случайным образом. Документ … m Кластер35nn-1n-9n-1n-2 … 1

22 Оценка приспособленности (Fitness-function) Представим информационный ресурс точкой в n-мерном пространстве терминов. Индексатор формирует список слов документа по принципу «каждое слово отделяется от другого пробелом». Для каждого термина рассчитывается его вес в данном информационном ресурсе, т.е. для каждого документа мы можем определить его координату, состоящую из частот встречаемости терминов в ресурсе. Координатными осями в данном случае выступают термины. Число их определяется числом терминов, по которым проводилось взвешивание, т.е. каждому дескриптору x i в документе D ставился в соответствие некоторый неотрицательный вес w i. Документ представлялся точкой в n-мерном пространстве):

23 Оценка приспособленности (Fitness-function) В каждый кластер входит какое-то количество информационных ресурсов. Для определения центра кластера 1, предполагаем, что центр-это первый ЭИР. Рассчитываем сумму расстояний от него до всех остальных информационных ресурсов (документов), входящих в кластер 1. Сохранив полученную величину, предполагаем, что второй ИР из кластера 1 - это центр. Рассчитываем сумму расстояний для него. Сохраняем результат. Проделываем то же самое для каждого ИР, представленного в хромосоме и входящего в кластер 1. Тот документ, для которого сумма расстояний до всех остальных ЭИР выборки будет минимальной, признается центром кластера 1. Аналогично находятся центры остальных кластеров. Фитнесс - функция для каждой хромосомы определяется суммой евклидовых расстояний от каждого ИР до центра соответствующего кластера. Пусть x Ц – координата центра i-го кластера, x ИР - координата i-го информационного ресурса, m - количество информационных ресурсов, которое одновременно определяет и длину хромосомы, n – количество координатных осей, по которым формируется общая координата информационного ресурса. Т.е.

24 Структурно-функциональное решение интеллектуального хранилища Программная система, реализующая идеи интеллектуального хранилища, состоит из следующих подсистем: подсистема индексирования ЭИР (индексатор), подсистема кластеризации ЭИР на основе нейронной сети (нейросетевой кластеризатор), подсистема кластеризации на основе fuzzy-c-means метода (fcm-кластеризатор) и классификатор, подсистема генетической кластеризации. На модуль индексации возложены задачи предобработки текстовых документов или аннотаций к ЭИР и построение частотных словарей встречающихся терминов. Сохранение производится в СУБД MS SQL Далее, в рамках модуля кластеризации и классификации, на основе значений относительных частот должны создаваться предметно-ориентированные кластеры, которые организуются в виде иерархии. В процессе классификации выполняется задача соотнесения вновь заносимого ЭИР с определенным кластером.

25 Реализация интеллектуального проектного репозитария

26 Сравнение алгоритмов кластеризации

27 Эксперимент кластеризации

28 Структура информационного ресурса

29 Структурирование информационных ресурсов ФНПЦ ОАО «НПО «МАРС»

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

31 Тверь, КИИ-2010, 20.сентября Генетическая оптимизация вычислительных сетей при автоматизированном проектировании

32 Тверь, КИИ-2010, 20.сентября АСУ разрабатываемые в ФНПЦ НПО МАРС

33 Тверь, КИИ-2010, 20.сентября 33

34 Тверь, КИИ-2010, 20.сентября 34 Генетическая оптимизация ВС В настоящее время не существует целостного теоретического подхода, комплекса методов, универсального программного средства проектирования ВС, которые были бы способны учесть не только все аспекты физической структуры сети, но и круг задач, программных средств и функций, которые эта сеть должна выполнять, а также могло бы делать прогнозы относительно будущей загрузки сети. Подход к моделированию осуществляется без учета задач, которые сеть должна выполнять, то есть в современных САПР ВС не применяется функциональное моделирование процессов, происходящих в проектируемой сети с использованием каких-либо стандартных диаграмм или моделей.

35 Тверь, КИИ-2010, 20.сентября 35 Модель транспортной схемы ВС (Т-модель) Т-модель является теоретической базой для построения средств автоматизированного проектирования и моделирования ВС, представленной транспортным уровнем. Уровни описания Т-модели: уровень топологии, включающий в себя структуру ВС и схему коммуникационного оборудования (Топ-уровень); уровень генерации, передачи и потребления трафика (Тр-уровень); уровень маршрутизации ВС (М-уровень).

36 Тверь, КИИ-2010, 20.сентября 36 Модель представления прикладных процессов (П-модель) П-модель состоит из двух составных частей: A-уровень (разработаны формализованные модели «тонкого» и «толстого» клиентов), DFD-уровень (описание потоков данных с помощью потоковых диаграмм (Data Flow Diagram) или DFD-диаграмм).

37 Тверь, КИИ-2010, 20.сентября 37 Формирование обобщенной ТП-модели 1.Разработка П-модели для проектирования - описание прикладных задач проектируемой вычислительной сети. На этом этапе составляется модель потоков данных проектируемой сети без привязки к транспортной структуре сети. 2.Разработка Т-модели для проектирования, то есть описание транспортной схемы, структуры ВС. На этом этапе проектировщик описывает саму ВС на уровне узлов сети и каналов связи, устанавливаются взаимосвязи узлов сети через коммутирующие модули, или маршрутизаторы, расставляются серверы. Для каждого узла сети задается таблица маршрутизации. Фактически моделируется процесс составления и настройки реальной локальной сети.

38 Тверь, КИИ-2010, 20.сентября 38 Формирование обобщенной ТП-модели (окончание) 3.Формирование ТП-модели. На этом этапе производится слияние модели прикладных процессов (П-модель) и транспортной модели сети (Т-модель) в обобщенную модель (ТП-модель) и моделирование ВС на основе прогнозных значений трафика, представленного временным рядом нечетких тенденций. 4.Модификация. Заключается во внесении изменений в Т-модель.

39 Тверь, КИИ-2010, 20.сентября 39 Генетическая оптимизация в Т-модели Задачи проектирования ВС, решаемые с помощью генетической оптимизации: Определение состава коммуникационного оборудования Определение пропускной способности каналов Определение размещения коммуникационного оборудования Размещение прикладных сервисов по узлам вычислительной сети

40 Тверь, КИИ-2010, 20.сентября 40 Алгоритмическая реализация целевой функции генетического алгоритма моделирования ВС Преимущества алгоритма: сравнительная простота реализации, независимость от структуры ВС. ДЛЯ каждого взаимодействия в сети: Определить источник и получатель трафика; Начать проведение трафика от источника ПОКА не достигнут получатель трафика Распространять трафик ко каналам ВС КОНЕЦ Определить каналы, в которых продолжается распространение трафика ПОКА есть каналы, в которых распространяется трафик Продолжать распространение трафика КОНЕЦ

41 Тверь, КИИ-2010, 20.сентября 41 ТП-уровень Т-модели: нечеткий гиперграф

42 Тверь, КИИ-2010, 20.сентября СТЕПЕНЬ УВЕРЕННОСТИ НСВ P 1 А1А1 А2А2 А3А3 P2P2 P 1,P 3 P2P2 P2P2

43 Тверь, КИИ-2010, 20.сентября КОДИРОВКА СТЕПЕНИ УВЕРЕННОСТИ Базовое значение НСВ Степень уверенности НСВ «низкий»«средний»«высокий» «точно» {1,0,0}{0,1,0}{0,0,1} «скорее» {0.75,0.25,0}{0.125,0.75,0.125}{0,0.25,0.75} «возможно» {0.5,0.35,0.15}{0.25,0.5,0.25}{0.15,0.35,0.5}

44 Тверь, КИИ-2010, 20.сентября ИМИТАЦИОННОЕ МОДЕЛИРОВАНИЕ ТРАФИКА «скорее высокий» {«низкий»/0, «средний»/0.25, «высокий»/0.75} Tr, (лингв.) высокий средний низкий t1t1 t2t2 tt1t1 t2t2 t3t3 t4t4 t5t5 t6t6

45 Метод распределения прикладных сервисов по транспортной схеме ВС Взаимосвязь прикладной и транспортной схем проектируемой сети является завершающим этапом процесса проектирования и здесь важно, чтобы окончательный результат был близок к оптимальному. Фактически взаимосвязь моделей заключается в распределении блоков диаграммы прикладных процессов по физической структуре модели с учетом расписания и генерируемого трафика. Для оптимизации этого процесса предлагается использовать стандартный ГА. Хромосомой для стандартного ГА (СГА) является один набор расположения блоков относительно физической структуры. Популяция таких наборов генерируется на начальном этапе работы СГА. Структура хромосомы СГА: блока диаграммы;IP-адрес соответствующего Такая кодировка хромосомы состоит из двух частей: изменяемой и неизменяемой. Неизменяемой частью является последовательность IP-адресов, а изменяемой – последовательность блоков диаграммы NDFD.

46 Метод распределения прикладных сервисов по транспортной схеме ВС Целевая функция СГА является аддитивной и состоит из трех слагаемых:. Первая часть целевой функции отвечает за распределение трафика: где i – номер текущей хромосомы СГА; j – номер сетевого канала; а Tr – суммарный трафик на одном канале. Вторая часть функции отвечает за распределение вычислительной загрузки в сети: где i – номер текущей хромосомы СГА; j – номер узла сети; Vz – суммарная вычислительная загрузка на узле сети. Третья часть целевой функции отвечает за качество группировки блоков диаграммы на физической структуре сети. Вычисление происходит в несколько этапов. Вначале определяется общее количество групп, заданных проектировщиком – i. Затем по каждой из групп строится массив IP-адресов. В этом массиве вычисляется максимальное количество повторяющихся элементов – Ni. Значение вычисляется следующим образом:

47 Метод распределения прикладных сервисов по транспортной схеме ВС Блок оптимизации проекта Интерфейсный модуль Графический редактор DFD, и структуры ВС Общий интерфейс системы Базовая структура данных Модуль хранения данных Моделирующая системаСтандартный генетический алгоритм Общая структура модуля ModLan

48 График изменения суммарного трафика ВС в процессе генетической оптимизации

49 График изменения суммарной вычислительной загрузки на узлах ВС в процессе генетической оптимизации

50 График изменения качества группировки процессов диаграммы на физической структуре ВС в процессе генетической оптимизации

51 График изменения аддитивной целевой функции, включающей в себя три выше рассмотренные компоненты

52 Тверь, КИИ-2010, 20.сентября 52 Заключение. Генетическая кластеризация является эффективным инструментом для следующих направлений Интеллектуальный анализ данных и текстов (Data and Text Mining); Построение интеллектуальных информационных систем. Генетическая оптимизация вычислительных сетей при автоматизированном проектировании результативно решает задачи: 1.Определение состава коммуникационного оборудования 2. Определение пропускной способности каналов 3. Определение размещения коммуникационного оборудования 4. Размещения сервисов на топологии вычислительной сети

53 Тверь, КИИ-2010, 20.сентября Nadezhda Yarushkina