Содержание к диссертации
Введение
Глава 1. Обзор основных функций PDM-систем 13
1.1. Место PDM-систем в САПР 13
1.1.1. Распространенные PDM-системы 15
1.1.2. Основные функции PDM-систем 15
1.1.2.1. Хранение и управление данными . 17
1.1.2.2. Управление классификацией и кластеризацией 19
1.1.3. Недостатки современных PDM-систем 19
1.2. Обзор методов кластеризации 20
1.2.1. Классификация методов кластеризации 20
1.2.2. Общая схема кластеризации 22
1.2.2.1. Определение множества признаков . 23
1.2.2.2. Выбор меры сходства 23
1.2.2.3. Проверка достоверности результатов . 24
1.2.3. Нечеткие методы кластеризации 25
1.2.3.1. FCM алгоритм 26
1.2.3.2. Gustafson-Kessel алгоритм 27
1.2.4. Выбор метода для применения к задаче кластери зации электронных информационных ресурсов . 28
1.3. Варианты ускорения fuzzy c-means 29
1.3.1. Параллельные реализации fuzzy c-means алгоритма 29
1.3.2. Обзор программного обеспечения для создания вычислительного кластера 31
1.3.2.1. Apache Hadoop 32
1.3.2.2. GridGain 35
1.3.3. Обоснование выбора программного продукта для создания кластера 39
1.4. Выводы по главе и постановка исследования 40
1.4.1. Выводы по главе 40
1.4.2. Постановка исследования 42
Глава 2. Модели и средства кластеризации электронных информационных ресурсов 43
2.1. Адаптированный fuzzy c-means 43
2.1.1. Описание объекта кластеризации 43
2.1.2. Адаптация к входным данным 44
2.1.3. Возможность иерархической кластеризации . 45
2.1.4. Уточнённый алгоритм FCM 47
2.1.4.1. Шаг 1. Инициализация 47
2.1.4.2. Шаг 2. Вычисление центров кластеров . 49
2.1.4.3. Шаг 3. Вычисление степеней принадлежности 50
2.1.4.4. Шаг 4. Проверка условий остановки ал- горитма 51
2.1.4.5. Шаг 5. Сохранение результатов 52
2.2. Метод организации поисковой системы на основе результатов кластеризации 52
2.2.1. Матрица принадлежностей как основа для ассоциативного поиска 52
2.2.2. Алгоритм поиска 54
2.3. Вариант параллельного выполнения алгоритма FCM . 55
2.4. Вариант выполнения алгоритма FCM на вычислительном кластере 56
2.4.1. Вычисление центров кластеров 60
2.4.2. Вычисление матрицы принадлежности 61
Глава 3. Реализация приложений 63
3.1. Программное обеспечение и технологические средства . 63
3.2. Структуры данных 64
3.2.1. Структура входных данных 64
3.2.2. Структура выходных данных 66
3.3. Кластеризатор 70
3.3.1. Варианты использования 70
3.3.2. Функции по работе с базой данных 71
3.3.3. Выполнение кластеризации 75
3.3.4. Работа с отчетами 78
3.3.5. Редактирование иерархии кластеров 79
3.3.6. Сервисные функции 80
3.4. Приложение поиска 87
3.4.1. Варианты использования 87
3.4.2. Диаграмма компонентов 90
Глава 4. Вычислительные эксперименты по кластеризации 92
4.1. Эксперименты по качеству кластеризации '92
4.1.1. План экспериментов 92
4.1.2. Математическая модель оценки качества кластеризации 93
4.1.3. Результаты экспериментов 94
4.2. Эксперименты по производительности кластеризатора . 97
4.2.1. Производительность параллельной реализации адап тированного FCM алгоритма 97
4.2.1.1. Вычисление центров кластеров 98
4.2.1.2. Вычисление матрицы принадлежности 100
4.2.1.3. Общее время выполнения 103
4.2.2. Производительность кластерной реализации адап тированного FCM алгоритма 104
4.2.2.1. Вычисление центров кластеров 106
4.2.2.2. Вычисление матрицы принадлежности 109
4.2.3. Сравнение многопоточной и кластерной реализаций 109
Заключение 116
Литература 118
Приложение
- Выбор метода для применения к задаче кластери зации электронных информационных ресурсов .
- Метод организации поисковой системы на основе результатов кластеризации
- Сервисные функции
- Эксперименты по производительности кластеризатора
Введение к работе
Актуальность проблемы.
За последнее десятилетие отмечается интенсивное развитие методов автоматизированного проектирования, поддерживающих коллективы разработчиков, рассредоточенных территориально. Основным инструментом работы таких коллективов проектировщиков являются проектные репозитории. Современные проектные репозитории должны отличаться от традиционных архивов проектной документации значительным объемом хранимых документов и малым временем отклика. Данные свойства проектных репозиториев нельзя обеспечить с помощью традиционных (ручных) методов идентификации предметной рубрики документа. Необходимо развивать автоматизированные методы управления хранилищем информационных проектных ресурсов, в том числе, учитывающие проблемную область (смысл) документов.
Таким образом, современный проектный репозитории должен обладать свойствами интеллектуальной системы. Задача идентификации проблемной области проектного документа представляет собой прежде всего задачу кластеризации документов. Для сложных проектных документов часто бывает невозможно отнести документ только к одной проблемной области. Одновременная принадлежность документа к ряду предметных рубрик подразумевает сохранение условий неопределенности, что делает актуальным разработку и использование нечетких алгоритмов кластеризации.
Значительные объемы хранимых документов (тысячи) на один средний проект предъявляют дополнительные требования к быстродействию алгоритмов их кластеризации. Подобные требования делают актуальными разработку параллельных алгоритмов кластеризации.
Цель диссертационной работы.
Целью диссертации является разработка методов, быстродействующих
алгоритмов, средств множественной кластеризации проектных документов в репозитории проекта.
Задачи исследования.
В соответствии с целью работы актуальными будем считать следующие задачи исследования:
провести сравнительный анализ существующих методов и систем кластеризации проектных документов;
разработать адаптированный для работы с текстами нечеткий алгоритм кластеризации проектных информационных ресурсов;
разработать методику иерархической кластеризации;
разработать систему поиска документов, релевантных проекту на основе мер (расстояний) в пространстве проектных документов;
разработать параллельный нечеткий алгоритм кластеризации проектных документов;
разработать параллельный нечеткий алгоритм кластеризации проектных документов для реализации на вычислительном кластере;
разработать и реализовать программные средства интеллектуального проектного репозитория, провести вычислительные эксперименты по исследованию их эффективности и быстродействия, внедрить их в практику проектной организации.
Методы исследования:
современная теория неопределенности, неточности и нечеткости;
теория кластеризации.
Научная значимость работы.
Автор защищает: разработанные модели построения проектных репози-ториев; результаты теоретических, экспериментальных и практических разработок, внедрение в промышленную и опытно-промышленную эксплуатацию.
Научная новизна. Впервые:
Разработан модифицированный нечеткий алгоритм на базе FCM-мето-да, адаптированный к задаче кластеризации проектных документов.
Предложена методика использования модифицированного нечеткого алгоритма на базе FCM-метода, адаптированного к задаче кластеризации проектных документов, обеспечивающая иерархическую кластеризацию.
Разработан быстродействующий параллельный алгоритм модифицированного FCM-метода.
Разработан быстродействующий параллельный алгоритм модифицированного FCM-метода для выполнения на вычислительном кластере.
Разработана программная система кластеризации проектных документов.
Практическая ценность и внедрение результатов.
Созданная программная система кластеризации проектных документов практически используется на производстве и позволяет достичь улучшенных техническо-экономических показателей объектов проектирования.
Практическая ценность состоит в том, что разработанные модели и алгоритмы реализованы в форме программной системы и внедрены в деятельность ФНПЦ ОАО «НПО Марс» (г. Ульяновск). Практическое использование
результатов диссертационной работы подтверждено соответствующими документами о внедрении.
Основания для выполнения работы.
Данная научная работа выполнялась в рамках тематического плана научных исследований Федерального агентства по образованию в 2005, 2006, 2007, 2008 г., была поддержана грантами РФФИ № 06-01-02012 и 06-01014087 в 2006 г., № 08-01-97006 в 2008 г., ряд задач исследования решался в рамках х/д НИР № 100/05 УлГТУ по заказу ФНПЦ ОАО «НПО МАРС».
Достоверность результатов диссертационной работы.
Достоверность научных положений, выводов и рекомендаций подтверждена результатами экспериментов, а так же результатами использования материалов диссертации и разработанной системы в проектной организации.
Основные положения, выносимые на защиту:
Модифицированный нечеткий алгоритм на базе FCM-метода, адаптированный к задаче кластеризации проектных документов, эффективно решает задачу идентификации проблемной области проектного документа.
Предлагаемая методика использования модифицированного нечеткого алгоритма на базе FCM-метода, адаптированного к задаче кластеризации проектных документов, обеспечивает иерархическую кластеризацию проектных документов.
Разработанный параллельный алгоритм модифицированного FCM-метода обеспечивает необходимое быстродействие.
Разработанный параллельный алгоритм модифицированного FCM-метода, для реализации на вычислительном кластере, обеспечивает необходимое быстродействие.
5. Разработанная программная система кластеризации проектных документов позволяет реализовать интеллектуальный проектный репозито-рий, функционирующий в автоматизированном режиме.
Апробация работы.
Основные положения и результаты диссертации докладывались, обсуждались и получили одобрение на второй всероссийской научной конференции с международным участием «Нечеткие системы и мягкие вычисления НСМВ — 2008» (г. Ульяновск, 2008 год); одиннадцатой национальной конференции по искусственному интеллекту с международным участием КИИ — 2008 (г. Дубна, 2008 г.); международной «конференции по логике, информатике, науковедению» (г. Ульяновск, 2007 г.); 42 — ой научно-технической конференции (г. Ульяновск, 2008 г.); научно-практической конференции студентов, аспирантов, молодых ученых и специалистов «Интегрированные модели, мягкие вычисления, вероятностные системы и комплексы программ в искусственном интеллекте ИММВИИ — 2009» (г. Коломна, 2009 г.); V -ой международной научно — практической конференции «Интегрированные модели и мягкие вычисления в искусственном интеллекте» (г. Коломна, 2009 г.); XI научно-практической конференции «Реинжиниринг бизнес-процессов на основе современных технологий. Системы управления знаниями» (РБП-СУЗ-2008).
Публикации. По материалам диссертации опубликовано 14 печатных работ, из них 2 статьи - в журналах из списка рекомендованных ВАК, получено свидетельство о государственной регистрации программы для ЭВМ.
Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения, списка литературы из 106 наименований, трех приложений, содержит 135 страницы машинописного текста, 36 рисунков и 19 таблиц.
Выбор метода для применения к задаче кластери зации электронных информационных ресурсов .
Из всех рассмотренных методов, алгоритм нечеткой кластеризации fuzzy c-means более остальных подходит для решения задачи кластеризации электронных информационных ресурсов по следующим причинам: нечеткая кластеризация позволяет отнести один документ одновременно к нескольким группам схожих объектов, что более «естественно», чем отношение к одному конкретному кластеру. Это наиболее важно для документов, находящихся на границе кластеров и документов, имеющих отношение сразу к нескольким проблемным областям. Результат кластеризации — матрица принадлежности документов кластерам, по которой легко организовать интеллектуальный поиск документов по степени их близости. Возможность применения алгоритма к вычисляемым индикаторам встречаемости терминов. По сравнению с другими методами нечеткой кластеризации, например, алгоритмом Густафсона-Кесселя, fuzzy c-means имеет меньшую вычислительную сложность и более пригоден к кластеризации больших массивов данных чем его аналоги.
Большие объемы документов и признакового пространства существенно увеличивают время кластеризации. При выполнении алгоритма на компьютере с многоядерном процессором (процессорами) имеет смысл выполнять процессы распараллеливания. Под параллельным или многопоточным выполнением алгоритма подразумевается, что какие-то его части выполняются одновременно, каждый в своем потоке. В идеальном случае распараллеливать нужно независимые друг от друга участки кода.
Уже существуют варианты параллельных реализаций алгоритма FCM. Например, в работе [31] предлагается алгоритм, схема которого представлена на рис.1.4.
Данная реализация не является оптимальной, ввиду того обстоятельства, что не все шаги алгоритма параллельны: вычисление центров кластеров и нормы разности матриц принадлежности вычисляются в одном потоке.
Второй существующий вариант распараллеливания алгоритма FCM описан в работе [32], ноютсутствует конкретное описание процессов вы числения центров кластеров и матрицы принадлежности, за исключением указания того факта, что вычисление происходит параллельно. Кроме того, в данном решении используется вычисление фактора компактности и отделимости сформированных кластеров, что для нечетких кластерных алгоритмов невсегда применимо, так как границы кластеров являются нечеткими, и сам алгоритм FCM подразумевает перекрытие сформированных кластеров.
Более существенное сокращение времени кластеризации может обеспечить вычислительный кластер. На сегодняшний день существует достаточно много вариантов его построения. Для выбора конкретного продукта необходимо определить требования к кластерной системе.
Далеко не каждое предприятие или организация имеют в своем распоряжении большие вычислительные мощности, поэтому одним из требований к системе является возможность построения кластера па обычных персональных компьютерах. Второе — программный продукт должен быть свободно распространяемым. На сегодняшний день подобные продукты получают всё большую популярность и практически каждое коммерческое приложение имеет свой свободно распространяемый аналог. Третье требование — возможность построения кластера в гетерогенной-среде, то есть узлы системы должны иметь возможность работать в различных операционных системах, как минимум, в наиболее распространенных, таких как Windows и Linux. Настоящее требование необходимо, так как большинство организаций пытаются переходить на свободно распространяемое программное обеспечение, но, ввиду различных причин, не весь парк компьютерной техники может быть полностью переведен на какую-то определенную операционную систему, тогда как такие машины потенциально могут быть узлами кластера. Четвертое требование — программный продукт для построения кластера должен поддерживать язык JAVA, так как именно он в соответствии с техническими требованиями используется для разработки приложений. Итак, определены следующие требования к кластерной системе
Метод организации поисковой системы на основе результатов кластеризации
Результатом применения fuzzy c-means метода является матрица принадлежности ресурсов кластерам: (2.12)
Данная матрица позволяет определить с какой степенью принадлежности тот или иной ЭИР относится к заданному кластеру, что позволяет выделить среди множества ресурсов наиболее соответствующие определенной предметной области.
Каждый ресурс ХІ характеризуется множеством термов Т[, что, совместно с матрицей принадлежности, позволяет выделить следующие типы поисковых запросов: по множеству ключевых слов (или их частей); по степени похожести ресурсов.
Поиск по множеству ключевых слов. Пусть Т -множество ключевых слов (частей слов), по которым необходимо осуществить поиск. Тогда результатом будет множество ресурсов X С X, удовлетворяющее следующуму условию:
Поиск по степени похожести ресурсов. Под похожими ресурсами в настоящей работе подразумеваются ЭИР, относящиеся к одной и той же предметной области, т.е. находящиеся в одном кластере. Пусть Х ,Х С X— определенное множество ресурсов, принадлежащие множеству кластеров V , тогда множество Y ресурсов считается похожим на X , если выполняются следующие условия:
Алгоритм поиска начинается с указания пользователем терма, набора термов или частей термов (например, только начало слова). Затем происходит выбор из базы данных всех электронных информационных ресурсов, содержащих в себе указанные термы. Для каждого ЭИР также выбираются сами искомые термы и показатели их встречаемости в нем. Следующий этап — сортировка ресурсов по частоте встречаемости в них найденных термов. Для отображения предметных областей, к которым относится тот или иной ЭИР, осуществляется выборка кластеров, к которым они относятся. Для каждого ресурса кластеры сортируются в порядке уменьшения степени принадлежности.
В результате работы алгоритма будут получены следующие данные: список ресурсов, отсортированный в порядке уменьшения частоты встречаемости искомых в них термов; для каждого ресурса: — список искомых термов с показателями встречаемости; — список кластеров в порядке уменьшения степени принадлежности ему ресурса.
Адаптированный алгоритм FCM, описанный в настоящей работе, имеет два основных этапа вычислений: 1. Вычисление центров кластеров; 2. Вычисление степеней принадлежности.
Вычисление степеней принадлежностей зависит от этапа вычисления центров кластеров. Прежде чем выполнять второй этап вычислений, необходимо дождаться завершения первого, так как в вычислении участвуют все параметры кластеров. Однако, каждый из этих этапов целесообразно распараллелить. На рис.2.2 представлена одна итерация варианта параллельного выполнения адаптированного к задаче кластеризации ЭИР алгоритма fuzzy c-means.
На этапе вычисления матрицы принадлежности каждый ЭИР обрабатывается отдельно, на этапе вычисления центров кластера—каждый кластер. Так же как и в последовательном алгоритме выполнения, часть вычислений нормы разности матриц принадлежности на соседних итерациях происходит на этапе вычисления новой матрицы.
Сервисные функции
Пользователь может перемещать ресурсы между кластерами простым перетаскиванием документа (документов) из одного кластера в другой. В этом случае возможны несколько вариантов поведения. Рассмотрим каждый из них отдельно. Перемещение ресурса в пределах одного уровня иерархии. В этом случае степень принадлежности ресурса кластеру, в который он перемещается, ставится равной 1, а степень принадлежности всем другим кластерам этого уровня устанавливается в 0. Перемещение ресурса между уровнями иерархии. В этом случае степень принадлежности ресурса кластеру,,в который он перемещается ставиться равной 1,, а всем другим кластерам этого уровня иерархии устанавливается в 0. Степень принадлежности кластеру, из которого ресурс перемещается устанавливается в 0, затем происходит процедура нормализации значений степени принадлежности всем другим кластерам того же уровня. Таким образом, сохраняется условие равенства единице суммы всех степеней принадлежности ресурса кластерам. Приложение имеет следующие сервисные функции: информация о ресурсе; информация о кластере; матрица принадлежности; список загруженных ресурсов; назначить имена кластерам. Просмотр списка загруженных ресурсов. Позволяет просмотреть список ресурсов, подлежащих кластеризации, с указанием количества проиндексированных термов (рис. 3.9). Просмотр информации о ресурсе. Отображает данные ресурса с полным описанием его параметров: код; наименование; количество проиндексированных термов; список термов и их частоты в документе. На рис.3.10 представлено окно приложения, в котором доступна такая возможность. Просмотр информации о кластере. Отображает данные кластера с полным описанием его параметров: код; наименование; список параметров со значениями, характеризующими центр кластера; список ресурсов, относящихся к данному кластеру со степенями принадлежности.
Просмотр информации о модели кластеризации. Отображает данные модели кластеризатора (одного уровня в иерархии кластеров). Содержит следующую информацию: код модели в БД (если модель ранее сохранялась); наименование модели. Если просматривается корневая модель, т.е. первый уровень иерархии, наименование модели - «корень». Если модель на других уровнях иерархии, наименование совпадает с именем кластера, который эта модель кластеризует. Возможно назначение имени непосредственно пользователем. пользовательские параметры модели: — максимальное количество итераций; — порог останова; - экспоненциальный вес; - порог включения в дерево; параметры выполнения модели: - достигнутый уровень точности; — количество выполненных итераций; матрицу принадлежности ресурсов кластерам. Данная функциональность также доступна во время работы кластеризатора, при этом все изменения в модели и кластерах автоматически отображаются Просмотр процесса кластеризации.
Визуализатор процесса кластеризации содержит в себе 4 компонента: 1. Дерево моделей/кластеров/ресурсов. Дерево кластеров автоматически изменяется и отображаются в процессе кластеризации ресурсов. 2. Просмотр информации о кластере. В окне просмотра информации о кластере можно наблюдать текущие изменения в кластере (параметры центра, наименование, степени принадлежности ресурсов кластеру); 3. Просмотр информации о модели. Просмотр текущего состояния матрицы принадлежности ресурсов кластерам. 4. Сводная таблица всех запущенных моделей.
Позволяет просматривать список всех запущенных, ожидающих запуска или завершенных моделей кластеризации с отображением основных параметров процесса: наименование модели; количество ресурсов, участвующих в процессе; количество уникальных термов набора ресурсов; заданное пользователем количество кластеров, на которые разбивается набор ресурсов; экспоненциальный вес, заданный пользователем; заданный пользователем уровень точности; максимальное количество итераций; текущая норма разности матриц принадлежности (значение для сравнения с порогом останова); статус модели (готов, выполняется, завершен).
Эксперименты по производительности кластеризатора
Реализованный параллельный алгоритм состоит из двух последовательных частей, выполняющихся параллельно: 1. Вычисление центров кластеров; 2. Вычисление матрицы принадлежности. Рассмотрим как ведет себя многопоточный алгоритм при выполнении каждого из этих шагов отдельно. Входные данные для тестирования: число документов: 5113; число уникальных термов: 6722; число кластеров для разбиения: 10. Для тестирования производительности алгоритма использовался двухпроцессорный сервер, каждый процессор состоит из четырех ядер, таким образом, в распоряжении имеется 8 ядер. Каждый центр кластера вычисляется в отдельном потоке.
Приложение создает пул потоков фиксированного размера, размер этого пула задается пользователем. Так можно ограничивать число одновременно выполняющихся потоков. На рис.4.1 представлен график зависимости времени выполнения вычисления центра кластера в зависимости от числа созданных потоков, а в табл.4.2 значения, по которым и построен этот график. Причем в таблице используется максимальное время выполнения, т.е. рассматривается наихудший результат. Как из табл.4.2, так и по рис.4.1 видно, что с увеличением количества потоков происходит уменьшение времени выполнения алгоритма, но до определенных пределов. Начиная с 6 потоков максимальное время выполнения стабилизируется. Объясняется это следующими обстоятельствами. Деление происходит на 10 кластеров, т.е. в очереди на выполнение находится 10 потоков. При размере пула потока (число потоков, которые могут выполняться одновременно) равного пяти — сначала параллельно выполняются первые пять потоков, а по мере их завершения — добавляются на выполнению другие пять потоков из очереди.
Ввиду того, что каждый параллельный поток выполняется примерно одинаковый промежуток времени, первые пять потоков закончат работу одновременно, а затем запустится второй набор из пяти потоков. Таким образом, каждое ядро вычислителя должно обработать последовательно 2 потока. В случае одновременного выполнения 6, 7 или 8 потоков, время обработки будет примерно такое же, как и в случае пяти потоков, так как какие-то из ядер вычислителя все равно должны будут обработать последовательно 2 потока., Девять, десять и более потоков будут работать примерно такое же время, как и восемь потоков потому, что доступно только 8 вычислителей (8 процессорных ядер), а одно ядро не может одновременно выполнять несколько вычислений, следовательно, остальные потоки будут простаивать в ожидании своей очереди на выполнение. При вычислении матрицы принадлежности также используется пул потоков, однако, в каждом потоке происходит обработка ни одного кластера, как в предыдущем случае, а одного ресурса. вычисления степени принадлежности одного ресурса всем кластерам в зависимости от числа созданных потоков, а в табл.4.3—значения, по которым и построен этот график.
Так же, как и в случае вычисления центров кластеров, используется максимальное время выполнения, т.е. рассматривается наихудший результат. Так же, как и при вычислении центров кластера, по табл.4.3 и рис.4.2 виден прирост производительности вычисления при добавлении вычислителей. При значениях числа потока больше, чем число вычислителей, время выполнения стабилизируется, так как остальные потоки находятся в ожидании свободных ресурсов. При сложении описанных выше этапов получим следующие результаты, отраженные в табл.4.4 и на рис.4.3. По рис.4.3 и табл.4.4 видно, что с увеличением числа потоков до числа вычислителей (процессоров, ядер), время выполнения итерации уменьшается, отсюда, можно сделать вывод о целесообразности распараллеливания адаптированного FCM алгоритма.
В параллельном алгоритме, выполняющемся на одном компьютере, с загрузкой всех необходимых данных в оперативную память, время выполнения одной итерации состоит собственно из самого вычисления, однако, при выполнении на вычислительном кластере это не так. Время выполнения одной итерации кластерной реализации адаптированного алгоритма FCM складывается из следующих основных компонент: вычисление центров кластеров: — время загрузки данных; — время вычисления; — время сохранения данных; вычисление матрицы принадлежности: — время загрузки данных; — время вычисления; — время сохранения данных. При использовании вычислительного кластера, как правило, возникают следующие вопросы: когда следует использовать вычислительный кластер, а не параллельную обработку на одном компьютере; каков прирост производительности с добавлением нового узла кластера;
