Оглавление
А. Специальная часть проекта 2
1. Введение 2
1.1. Актуальные проблемы кластерного анализа 4
1.2. Задачи кластерного анализа 6
1.3. Этапы кластерного анализа 6
1.4. Цели кластеризации для выработки рекомендаций 7
1.5. Построение ценовых (весовых) моделей 8
2. Техническое задание 9
2.1. Цель и назначение разработки 9
2.2. Этапы разработки 10
2.3. Основные требования к программному обеспечению 10
3. Обзор существующих решений 12
3.1 Иерархические методы кластеризации 12
3.2. Неиерархические (итеративные) методы кластеризации 15
3.3. Сравнительный анализ иерархических и неиерархических методов кластеризации 18
3.4. Сеточные алгоритмы 19
4. Обзор существующих систем кластеризации 23
4.1. Коммерческие инструменты: 23
4.2. Выводы 27
5. Предлагаемые методы и математическое обеспечение 28
5.1. Методы кластеризации 28
5.2. Метод вычисления ценовых моделей 35
Структура системы 36
6.1. Принципиальная схема 36
6.2 Программная реализация библиотеки 37
6.3. Форматы входных и выходных данных: 41
Б. Конструктивно-технологическая часть проекта 42
1. Технология программирования 42
1.1.Модели на основе инженерного подхода 43
1.2.Модели, учитывающие специфику разработки ПО 44
1.3.Современные модели 46
1.4.Модели быстрой разработки. 47
1.5.Адаптированные и комбинированные модели. 50
1.6 Выводы 51
2.Выбор языка программирования 51
2.1. Анализ инструментальных средств 52
В. Охрана труда 56
1.1 Расчет защитного заземления 56
1.2 Электробезопасность рабочего места с ПЭВМ 60
Г. Экологическая часть 64
2.1. Микроклимат 64
2.2 Защита от шума 67
Д. Решение задачи на ЭВМ 73
1. Структура классов 73
2. Пример функционирования 75
Е. Заключение 76
Ж. Список использованной литературы 77
А. Специальная часть проекта 1. Введение
В последнее время информация, растущая в колоссальных объёмах рождает потребность в обработке больших объёмов данных (Big Data). В этом направлении большое место отведено интеллектуальному анализу данных (Data Mining). Это направление включает в себя методы, отличные от классического анализа, основанные на моделировании, вероятностных, и решающие задачи обобщения, ассоциирования и отыскания закономерностей. В большой степени развитию этой дисциплины способствовало проникновение в сферу анализа данных идей, возникших в теории искусственного интеллекта.
В данной работе я хотел бы рассмотреть частную задачу подобного анализа, а именно, задачу кластерного анализа, известную как задача автоматической группировки объектов. Решение планируется использовать для разработки системы рекомендаций в системах принятия решений.
Главной задачей кластерного анализа является выделение необходимого числа групп объектов схожих между собой внутри группы и максимально отличных от экземпляров других классов. Подобный анализ широко применяется в информационных системах для отыскания закономерностей в данных.
Список областей, в которых применяется кластеризация очень большой: это работа с изображениями, маркетинговые исследования, прогнозирование, текстовый анализ, обнаружение мошеннических действий и многие другие[28]. Сегодня кластеризация является первым шагом анализа данных. Задачи кластеризации формируются в различных научных направлениях: в статистике, оптимизации, машинном обучении, что породило множество различных синонимов понятия кластера – класс, таксон, сгущение. Сегодня уже применяются несколько десятков алгоритмов разбиения и множество их модификаций. Зачастую данные с которыми приходится работать этим алгоритмам обусловлены такими особенностями как высокая размерность и сверхбольшой объём данных (миллионы записей в тысячах полей), так же содержание большого количества числовых (numerical), которые способны упорядочиваться в пространстве, и категорийных (categorical), неупорядочивающихся, атрибутов. Атрибуты получают значения согласно типу шкалы, выбор которой является отдельной задачей.
В своей основе алгоритмы кластеризации сравнивают между собой объекты на основе различных мер сходства или близости, величины, имеющей предел и возрастающей по мере схожести объектов. Эти меры сходства выбираются в зависимости от задачи и шкалы измерений[36]. Для числовых атрибутов очень часто применяют евклидово расстояние:  ,
а категорийные атрибуты сравнивают при помощи меры Чекановского-Серенсена и Жаккара  .
Необходимость обрабатывать огромные объёмы данных позволила сформулировать ряд требований для алгоритма кластеризации. Рассмотрим эти требования. Минимизация итераций обращения к данным
Ограниченность ресурсов, в частности памяти системы
Восстанавливаемость алгоритма
Работа алгоритма с базой данных в режиме однонаправленного курсора.
Выполнение данных условий, в особенности второго пункта, определяет алгоритм как масштабируемый. Алгоритм называют масштабируемым, если при неизменной емкости оперативной памяти с увеличением числа записей в базе данных время его работы растет линейно.
Трудно соблюсти баланс между высоким качеством кластеризации и масштабируемостью. Поэтому в идеале в арсенале Data Mining должны присутствовать как эффективные алгоритмы кластеризации микромассивов (Microarrays), так и масштабируемые для обработки сверхбольших баз данных (Large Databases).
1.1. Актуальные проблемы кластерного анализа
Несмотря на большое число исследований в области кластерного анализа, в этой области существует ряд актуальных проблем. Можно сформулировать основные[28]:
Обоснование качества результатов. Проблема заключается в том, что один и тот же объект может быть классифицирован в различные группы вне зависимости от его внутренних свойств, а в связи с различными экспертными данными или различным построением системы. Для избегания этого необходимо разрабатывать и вводить актуальные критерии качества.
Анализ большого числа разнотипных данных порождает методологическую проблему выбора метрик. Так же увеличение числа объектов даже однотипных данных может повлечь за собой неразличимость расстояний.
Нелинейность взаимосвязей. Классические методы снижения размерности в кластерном анализе направлены на линейной взаимосвязи между переменными. Для поиска более сложных зависимостей необходимо переходить к ядерным методам.
Проблема поиска глобального экстремума функции критерия качества. Критерий качества, как правило, является функцией, зависящей от большого числа факторов, нелинейным, обладающим множеством локальных экстремумов. Для нахождения кластеров необходимо решить сложную комбинаторную задачу поиска оптимального варианта классификации. Поэтому алгоритм полного перебора вариантов имеет трудоемкость, экспоненциально зависящую от размерности. Если число групп заранее неизвестно, то переборная задача становится еще сложнее. Таким образом, при увеличении размерности таблиц данных происходит «комбинаторный взрыв». Классические алгоритмы кластерного анализа осуществляют направленный поиск в сравнительно небольшом подмножестве пространства решений, используя различного рода априорные ограничения (на число кластеров или их форму, на порядок включения объектов в группы и т.д.). При этом нахождение строго-оптимального решения не гарантируется. Для поиска оптимального решения применяются более сложные методы, такие как генетические (эволюционные) алгоритмы, нейронные сети и т.д. Существуют экспериментальные исследования, подтверждающие преимущества таких алгоритмов перед классическими алгоритмами. Однако и при использовании эволюционных методов возникают проблемы, связанные со спецификой решаемой задачи кластер-анализа: с трудностью интерпретации используемых операторов рекомбинации и кроссовера.
Неустойчивость результатов кластеризации. Зачастую результаты группировки могут сильно меняться в зависимости от выбора начальных условий, порядка объектов, параметров работы алгоритмов. Различными авторами предлагаются способы повышения устойчивости группировочных решений, основанные на применении ансамблей алгоритмов. При этом используются результаты группировки, полученные различными алгоритмами, или одним алгоритмом, но с разными параметрами настройки, по различным подсистемам переменных и т.д. После построения ансамбля проводится нахождение итогового коллективного решения.
Недостаточность знаний об объекте. Существует проблема трудноформализуемых областей, в которых становится затруднительным создание модели объекта. В таком случае становится затруднительным применение алгоритмов, основывающихся на представлении класса, как набора распределённых в пространстве переменных.
Проблема представления результатов. Помимо хорошей прогнозирующей способности для любого алгоритма анализа данных важно, насколько понятными и интерпретируемыми являются его результаты. Для улучшения интерпретируемости решений можно использовать логические модели. Такого рода модели используются для решения задач распознавания образов и прогнозирования количественных показателей, например, в методах построения решающих деревьев или логических решающих функций.
1.2. Задачи кластерного анализа
Кластерный анализ выполняет следующие основные задачи:
Исследование схем группировки объектов;
Выработка гипотез на базе исследований данных;
Подтверждение гипотез и исследований данных;
Определение присутствия групп внутри данных.
1.3. Этапы кластерного анализа
Независимо от предмета изучения применение кластерного анализа предполагает следующие этапы:
Формирование выборки для кластеризации;
Выделение признакового пространства;
Выбор меры сходства (расстояния) между объектами;
Применение метода кластерного анализа;
Проверка результатов кластеризации.
Существуют два ключевых требования к данным:
Однородность – необходимость гарантировать единую природу всех кластеризуемых сущностей. То есть все объекты должны описываться схожим набором характеристик;
Полнота - содержание данных в достаточном по всей их номенклатуре, необходимые для рационального или оптимального решения конкретной задачи.
1.4. Цели кластеризации для выработки рекомендаций
Разбиение выборки на группы схожих объектов для упрощения понимания кластерной структуры, что упрощает обработку данных и принятие решение, применяя к каждому кластеру свой метод анализа.
Сокращение объёма данных, оставляя по одному или несколько наиболее типичных представителей от каждого класса. В таких задачах важнее обеспечить высокую степень сходства объектов внутри каждого кластера, а кластеров может быть сколько угодно.
Выделение нетипичных объектов, аномалий или выбросов, для определения новизны кластеров или их количества. Наибольший интерес представляют отдельные объекты, не вписывающиеся ни в один из кластеров.
Во всех этих случаях может применяться иерархическая кластеризация, когда крупные кластеры дробятся на более мелкие, те в свою очередь дробятся ещё мельче, и т. д. Такие задачи называются задачами таксономии. Результатом таксономии является древообразная иерархическая структура. При этом каждый объект характеризуется перечислением всех кластеров, которым он принадлежит, обычно от крупного к мелкому.
1.5. Построение ценовых (весовых) моделей
Методы кластеризации и классификации хорошо приспособлены к прогнозированию того, к какой категории относится какой-либо образец. Однако методы в их математическом виде не оптимальны для выборки прогнозов о числовых данных на основании различных атрибутов. Важной задачей так же становится учитывать распределение вероятностей прогноза и интерпретировать данные[29].
Цена - это хороший способ оценки реальной стоимости вещи, а прогнозирование цены является хорошим примером реализации алгоритма, когда учитываются не только цифры, но и степень их влияния. Например диаметр колес автомобиля не коррелирует напрямую с объёмом двигателя или тактовая частота процессора может быть первостепенной при комплектовании компьютера.
Важной частью числового прогнозирования становится определение того, какие переменные существенны и в каком сочетании. Есть переменные влияющие на цену напрямую, а есть, не учитывающиеся вовсе. Кроме того, в каждом конкретном случае приоритеты характеристик для наборов данных могут быть различными.
Но процесс определения наилучших весов переменных можно автоматизировать и применять для выработки рекомендаций по определённым параметрам на основании созданных кластерах или для их создания.
Обычно приходится работать с наборами данных, построенными кем-то другим, поэтому априорной информации о том, какие переменные существенны, а какие – нет, может и не быть.
Иногда бывает, что определенные данные собирать трудно или дорого, и если оказывается, что ценность их на самом деле невелика, то можно избежать лишних затрат. В других случаях одно лишь знание того, какие переменные существенны – особенно в плане влияния на цену, – может определить направление маркетинговых действий или подсказать, как следует изменить дизайн продуктов, чтобы их можно было продать по наивысшей цене.
|
