close

Вход

Забыли?

вход по аккаунту

?

Tatarnikova

код для вставкиСкачать
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное автономное
образовательное учреждение высшего образования
САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
АЭРОКОСМИЧЕСКОГО ПРИБОРОСТРОЕНИЯ
Т. М. Татарникова
АНАЛИЗ ДАННЫХ
В ПРИКЛАДНЫХ ЗАДАЧАХ ОБЕСПЕЧЕНИЯ
ИНФОРМАЦИОННОЙ БЕЗОПАСНОСТИ
Монография
УДК 004.8:519.23
ББК 22.176
Т23
Рецензенты:
доктор технических наук, профессор Е. П. Истомин;
доктор технических наук, профессор А. М. Тюрликов
Утверждено
редакционно-издательским советом университета
в качестве монографии
Татарникова, Т. М.
Т23 Анализ данных в прикладных задачах обеспечения информационной безопасности: монография / Т. М. Татарникова. – СПб.: ГУАП,
2018. – 115 с.
ISBN 978-5-8088-1315-1
Рассмотрены типичные задачи анализа данных. Особое внимание
уделено задачам кластеризации и классификации. Приводится характеристика методов, алгоритмов и этапы решения этих задач. Более подробно рассмотрены примеры применения методов кластерного
анализа, факторного анализа и классификации в прикладных задачах обеспечения информационной безопасности. Демонстрируются
возможности нейронных сетей, как инструмента анализа данных.
Монография предназначена для использования при изучении
дисциплин «Методы моделирования и оптимизации», «Информационно-аналитические системы безопасности», «Теория систем и системный анализ» направления подготовки «Инфокоммуникационные технологии и системы связи», «Информационная безопасность»
и смежных направлений.
УДК 004.8:519.23
ББК 22.176
ISBN 978-5-8088-1315-1
© Санкт-Петербургский государственный
университет аэрокосмического
приборостроения, 2018
ВВЕДЕНИЕ
Анализ данных – относительно новое направление в науке, связанное с изучением и применением методов, технологий и средств
извлечения информации из большого объема данных, поиска закономерностей, извлечения знаний, анализа шаблонов [1, 2].
В настоящее время анализ данных является самостоятельной
прикладной наукой, в которой невозможно выделить строгий математический аппарат, как например в статистике, то есть нет конечного набора базовых функций для решения задач. Более того,
многие современные задачи носят специфический характер, для
их решения появляются новые методы и технологии, под которые
разрабатывается новый математический аппарат. Ярким примером
являются нейронные сети [1].
Основная особенность анализа данных состоит в сочетании широкого математического инструментария и достижений в области
информационных технологий, формализованных методов и методов неформального анализа, количественного и качественного анализа данных [3].
В зарубежной литературе область анализа данных известна как
технология Data Mining. Поэтому в дальнейшем эти понятия будем
считать взаимозаменяемыми.
Термин Data Mining образован от двух понятий: в большом объеме данных (data) добычи (mining) ценной информации. Совмещение этих процессов означает просеивание огромного количества необработанных данных, их анализа и поиска в них ценных данных
и скрытых знаний.
Технологии анализа данных развились по мере роста объемов
данных. Начиная с методов статистического анализа при решении
задач обработки небольших баз данных, в настоящее время анализ
данных является мультидисциплинарной областью, включающей
такие науки как прикладная статистика, распознавание образов,
искусственный интеллект, теория баз данных и другие, в которой
используется множество инструментов и различных методов [4].
Отличие технологии Data Mining от традиционных методов анализа, например, статистических и OLAP методов состоит в том, что
традиционные методы в основном ориентированы на проверку заранее сформулированных гипотез и на «грубый» разведочный анализ,
в то время как Data Mining подразумевает поиск неочевидных закономерностей. Инструменты Data Mining позволяют находить закономерности автоматически, что позволяет в последствии строить
3
гипотезы о взаимосвязях данных, характеризующих изучаемые
объекты или процессы [5].
При всех качествах технологии Data Mining все же они не могут
полностью заменить аналитика. Основная причина заключается в
том, что модель анализа данных не может решить те задачи, решению которых она еще не обучена. Data Mining не может заменить
аналитика, но предоставляет мощный инструмент для того, чтобы
сделать его работу эффективней [6].
Решение задачи анализа данных подразумевает сотрудничество
между аналитиком, являющимся экспертом в предметной области
решаемой задачи и специалистом по инструментам Data Mining.
Успешный анализ требует качественной предобработки данных
и выбора модели анализа данных. По мнению аналитиков процесс
предобработки может занять до 80% времени всего процесса анализа данных.
Несмотря на то, что с помощью анализа данных можно добыть
действительно ценную информацию, нельзя не учитывать тот факт,
что инструменты анализа данных способствуют тому, что можно
сделать множество ложных и не имеющих смысла открытий. Во
избежание этого, необходима проверка адекватности полученных
моделей на тестовых данных, а также осуществлять контроль значимости обнаруженных знаний.
Большинство инструментов анализа данных, предлагаемых на
рынке программного обеспечения, учитывают мультидисциплинарность этой области и реализуют сразу несколько методов решения, например, статистический анализ, визуализацию, кластеризацию, прогнозирование, нейронные сети и другие.
В универсальных прикладных пакетах, таких как SPSS, SAS,
STATGRAPHICS, Statistica и других реализуется широкий спектр
разнообразнейших методов анализа данных [7].
Использование универсальных пакетов при решении задач анализа данных дает преимущество в плане возможности относительно легкого сравнения результатов, полученных различными методами. Например, в пакете Statistica сравнение реализовано на «конкурентной оценке моделей», заключающейся в применении к одним
и тем же данным различных моделей с последующим сравнением
их характеристик и выбора лучшей из них [8].
4
1. ВВЕДЕНИЕ В АНАЛИЗ ДАННЫХ
1.1. Взаимосвязь основных понятий анализа данных
Предназначение технологии Data Mining заключается в практической направленности анализа данных – путь от скрытых данных
к конкретному знанию или то же самое, что путь от постановки задачи к готовому приложению, при поддержке которого можно принимать решения в проблемной области, где необходимо анализировать большие объемы данных [1].
Рассмотрим связь многочисленных понятий, которыми оперирует анализ данных и разнообразных методов, поддерживающих данную технологию.
С одной стороны имеется информационный поток: данные – информация – знания, с другой стороны – инструментальный поток:
задачи – методы решения – приложения. Эти потоки являются отображением одного процесса, результатом которого должно стать
знание и принятие решения [9].
Рассмотрим первый поток (рис. 1.1), где показана связь понятий
«данные», «информация» и «знания», которая возникает в процессе
принятия решений.
Знания
Нуждаются
Поддерживают
Информация
Основаны на
Обеспечивают
Данные
Рис. 1.1. Информационный поток
при анализе данных
5
Приложения
Контроль
качества
Решения
Распознавание
объектов
...
Информация
Действия
Прогностическое
моделирование
Анализ
связей
...
Инструменты
Классификация
Работа
с клиентами
Сегментация
данных
Данные
Кластеризация
...
Прогнозирование
Рис. 1.2. Инструментальный поток анализа данных
Как видно из рис. 1.1, этот процесс итерационный. Для принятия решения требуется информация, которая основана на данных,
а данные в свою очередь обеспечивают информацию, которая поддерживает решения, и т. д. По мере продвижения вверх объемы данных переходят в ценность решений.
Подойдем к этому же процессу с другой стороны. Рассмотрим на
рис. 1.2 все уровни инструментального потока Data Mining.
Верхний – это уровень приложений. На уровне приложений принимаются управленческие решения.
Средний – это уровень действий, который по своей сути является
уровнем информации, именно на нем выполняются действия по анализу данных, например, прогностическое моделирование, сегментация данных, определение связей между параметрами и другие.
Нижний – это уровень определения типа задачи, которая должна быть решена на основе имеющихся данных. Примерами разновидностей задач анализа данных могут быть задачи прогнозирования, классификации, кластеризации и другие.
6
1.2. Типичные задачи Data Mining
Однозначного мнения о том, какие задачи относятся к области
анализа данных, нет. Большинство авторитетных источников к
Data Mining причисляют следующие задачи: классификация, кластеризация, прогнозирование, визуализация, ассоциация, обнаружение отклонений, анализ связей [1, 2, 9].
Наиболее распространенной и простой задачей анализа данных
считается классификация. Результатом ее решения является определение признаков, которые характеризуют группы объектов (классы) из исследуемого набора данных, то есть объекты, принадлежащие одному классу, будут иметь схожие по значению признаки.
Впоследствии новый объект по этим признакам может быть отнесен
к одному из предопределенных классов.
Для решения задачи классификации в зависимости от условия,
уровня ошибки, могут использоваться следующие методы: ближайшего соседа, k-ближайшего соседа, байесовские сети, индукция деревьев решений, нейронные сети.
Кластеризация является логическим продолжением идеи классификации, но представляет собой более сложный процесс, поскольку особенность кластеризации заключается в том, что классы
объектов изначально не предопределены. Результатом кластеризации является разбиение объектов на группы.
Задача кластеризации может быть решена следующими методами: ближайшего соседа, k-ближайшего соседа, самоорганизующиеся карты Кохонена.
При решении задачи прогнозирования на основе особенностей
накопленных данных оцениваются пропущенные или будущие значения целевых численных показателей.
Для прогнозирования применяются методы математической
статистики, нейронные сети и другие.
В результате визуализации создается графический образ анализируемых данных. Решению задачи визуализации способствуют
различные графические методы, демонстрирующие существующие
закономерности в данных.
Применяются такие методы визуализации, как представление
данных в 2D- и 3D-измерениях.
В ходе решения задачи ассоциации выполняется поиск ассоциативных правил, то есть выявляются закономерности между связанными событиями в наборе данных. В отличии от задач классификации и кластеризации поиск закономерностей осуществляется
7
не на основе свойств анализируемого объекта, а между несколькими событиями, которые происходят одновременно или связаны во
времени.
Наиболее известным алгоритмом решения задачи поиска ассоциативных правил является алгоритм Apriori.
Цель решения задачи анализа и обнаружения отклонений или
выбросов состоит в обнаружении и анализе данных, наиболее отличающихся от общего множества данных, а также в выявлении так
называемых нехарактерных шаблонов.
Анализ связей является задачей нахождения зависимостей в наборе данных. Для решения таких задач применяются методы математической статистики.
Все перечисленные задачи анализа данных можно классифицировать по стратегиям их решения на следующие группы задач:
– обучение с учителем;
– обучение без учителя;
– другие.
Обучение с учителем предполагает наличие ретроспективных
(накопленных) данных, которые аналитик делит на обучающую
выборку и тестовую выборку. На первой происходит обучение модели решению задачи, а на второй – оценивается качество обучения.
К группе задач обучения с учителем относятся следующие задачи анализа данных: классификация, прогнозирование.
К группе задач обучения без учителя относится задача кластеризации.
В группу других входят задачи, не включенные в предыдущие
две стратегии.
1.3. Стадии анализа данных
Стадий анализа данных может быть две или три [1]:
Стадия 1. Свободный поиск, в результате которого выявляются
закономерности.
Стадия 2. Прогностическое моделирование, заключающееся в применении выявленных закономерностей для определения неизвестных
значений.
Иногда за стадией свободного поиска дополнительно вводят стадию валидации, цель которой заключается в проверке достоверности найденных закономерностей. Можно считать валидацию частью первой стадии, поскольку в реализации многих методов анализа данных предусмотрено деление множества исходных данных
8
на обучающее и тестовое, где последнее позволяет проверять достоверность полученных результатов.
Стадия 3. Анализ исключений, состоящий в выявлении и объяснении аномалий в найденных закономерностях.
1. На стадии свободного поиска исследуется набор данных с целью поиска скрытых закономерностей. Гипотезы относительно
вида закономерностей на данной стадии не выдвигаются.
Закономерность – это систематически повторяющаяся взаимосвязь, определяющая этапы и формы процесса становления, развития различных явлений или процессов.
При использовании технологий анализа данных на этой стадии
определяются шаблоны, для получения которых в системах OLAP,
например, аналитику необходимо спланировать и создавать серию
запросов. Если аналитик использует технологии анализа данных,
то он освобождается от такой работы, поскольку шаблоны ищет за
него система. Подобный подход необходим при работе с BigData,
где определить закономерность путем создания запросов достаточно сложно, так как это потребует перепробовать множество разнообразных вариантов [10].
Свободный поиск включает следующие шаги:
– выявление закономерностей условной логики;
– выявление закономерностей ассоциативной логики;
– выявление трендов и колебаний.
Допустим, имеется база данных с большим объемом накопленных данных. Для получения какого-либо нового результата необходимо построить соответствующий запрос.
При свободном поиске система сама ищет закономерности, необходимо лишь задать целевую переменную. В результате поиска
закономерностей система сформирует набор логических правил
«Если..., то...».
Свободный поиск выполняется при помощи аппарата:
– индукции правил условной логики, позволяющих решать такие задачи анализа данных, как классификация и кластеризация
объектов.
– индукции правил ассоциативной логики, позволяющих решать задачи ассоциации;
– определения трендов и колебаний, позволяющих решать задачи прогнозирования.
На стадии свободного поиска также осуществляется валидация закономерностей, т. е. проверка их достоверности на выборке данных,
которая не принимала участия в формировании закономерностей.
9
2. На стадии прогностического моделирования используются результаты работы первой стадии. Здесь обнаруженные закономерности применяются непосредственно для прогнозирования.
Прогностическое моделирование включает такие действия:
– предсказание неизвестных значений;
– прогнозирование развития процессов.
Прогностическое моделирование позволяет решать задачи классификации и прогнозирования.
Если решается задача классификации, то результаты работы
первой стадии (индукции правил) используются для отнесения нового объекта, с определенной уверенностью, к одному из предопределенных классов.
Если решается задача прогнозирования, то результаты первой
стадии используются для предсказания неизвестных значений целевой переменной.
Таким образом, на первой стадии – свободном поиске – раскрываются общие закономерности. Закономерности, полученные на
этой стадии, формируются от частного к общему, в результате получаем некоторое общее знание о некотором классе объектов на основании исследования отдельных представителей этого класса. По
своей природе свободный поиск индуктивен.
Прогностическое моделирование, напротив, дедуктивно. Закономерности, полученные на этой стадии, формируются от общего
к частному и единичному. Здесь новое знание о некотором объекте или же группе объектов можно получить на основании знания
класса, к которому принадлежат исследуемые объекты или на основании знания общего правила, действующего в пределах данного
класса объектов.
3. На третьей стадии DataMining анализируются исключения
или аномалии, выявленные в найденных закономерностях.
Действие, выполняемое на этой стадии – выявление отклонений.
Для их выявления необходимо определить норму, которая рассчитывается на стадии свободного поиска.
10
2. КЛАСТЕРНЫЙ АНАЛИЗ
2.1. Постановка задачи кластерного анализа
Предмет кластерного анализа был определен впервые в 1939 г.
математиком Р. Трионом.
Название кластерного анализа происходит от английского слова
cluster – гроздь, скопление.
Кластерный анализ – это один из математических методов, заключающийся в том, что определенный набор объектов разбивают
на группы, которые называются кластерами. В каждом кластере
объекты схожи, а различные кластеры имеют явные отличия.
Главное назначение кластерного анализа – выявить схожие объекты в исследуемой выборке [2].
Методы кластерного анализа можно применять в самых различных случаях, когда речь идет об образовании групп по сходству их
признаков.
Основным достоинством кластерного анализа считается возможность производить разбиение объектов не по одному признаку, а по
целому набору признаков. В отличие от большинства математикостатистических методов кластерный анализ не накладывает ограничений на формат анализируемых объектов и может рассматривать
множество исходных данных практически произвольной природы.
Кластерный анализ позволяет рассматривать большие по объему
массивы данных, сжимая их до кластеров, и таким образом делать
их компактными и понятными для анализа. Далее каждый кластер
может исследоваться индивидуально.
К недостаткам и ограничениям кластерного анализа относятся
следующие:
– количество и объем кластеров зависят от выбранных критериев разбиения;
– кластеризация неизбежно приводит к искажениям и потерям
индивидуальных черт отдельных объектов за счет замены их обобщенными значениями характеристик кластера.
Задача кластерного анализа заключается в том, чтобы на основании данных, содержащихся во множестве Х, разбить множество
объектов G на m кластеров (подмножеств) Q1, Q2, …, Qm, так, чтобы
каждый объект Gj, Gj , j = 1,m принадлежал одному и только одному подмножеству разбиения, объекты, принадлежащие одному и
тому же кластеру, были сходными, в то время как объекты, принадлежащие разным кластерам, были разнородными. Результатом
решения задачи кластерного анализа являются кластеры, удовлет11
воряющие некоторому критерию оптимальности. Критерий оптимальности представляет собой функцию, выражающую уровни желательности различных разбиений на кластеры, которая является
целевой функцией. Например, в качестве целевой функции может
быть взята внутригрупповая сумма квадратов отклонения:
1 n
D=
xj − x =
x 2j −  xj
nj 1
=j 1
=j 1=

n
∑(
n
) ∑
2
∑
2

 ,


(2.1)
где xj – представляет собой числовое значение характеристики (признака) j-го объекта.
Кластер имеет следующие математические характеристики:
– центр,
– радиус,
– среднеквадратическое отклонение,
– размер кластера.
Центр кластера – это среднее геометрическое расположение
всех точек кластера.
Радиус кластера – расстояние от самой удаленной точки кластера до его центра.
Кластеры могут быть перекрывающимися, то есть один или несколько объектов одновременно принадлежат нескольким кластерам. Такие объекты называют спорными. В таких случаях невозможно математическими процедурами однозначно отнести объект
только к одному из нескольких кластеров.
Спорный объект – это объект, который по мере сходства признаков может быть отнесен к нескольким кластерам.
Размер кластера определяется либо его радиусом, либо среднеквадратичным отклонением объектов от центра кластера.
Объект принадлежит кластеру, если расстояние до центра меньше радиуса кластера. Если это условие выполняется для двух и более кластеров, объект определяется как спорный. Неоднозначность
данной задачи может быть устранена аналитиком.
Кластерный анализ базируется на двух предположениях:
– во-первых, кластеризация выполняется по признакам объектов;
– во-вторых, математические характеристики кластеров определяются в соответствии с выбранным масштабом или единицами измерения признаков.
Выбор масштаба в кластерном анализе имеет первостепенное
значение. Предположим, что в наборе данных значения признака х
12
на три порядка больше значения признака у, тогда, при расчете расстояния между объектами, признак х будет полностью доминировать над признаком у. Таким образом, из-за разнородности единиц
измерения признаков будет невозможно корректно оценить расстояния между объектами.
Эта проблема решается процедурой предварительного нормирования признаков. Нормирование приводит значения всех преобразованных характеристик (признаков) к единому диапазону значений
путем выражения через отношение этих значений к некой величине,
отражающей определенные свойства конкретного признака.
Нормализация подразумевает, что все значения признаков приводятся к некоторому диапазону, например, [–1, –1] или [0, 1].
Существуют следующие варианты нормирования исходных данных:
(
)
z = xj − x σ ,
z = x x,
z = x xmax ,
z=
( x − x ) ( xmax − xmin ),
где x, σ – среднее и среднеквадратическое отклонение x соответственно; xmax, xmin – максимальное и минимальное значения x.
Наряду со стандартизацией переменных, существует возможность придать каждой переменной весовой коэффициент, отражающий значимость соответствующей переменной. Роль весов могут
играть экспертные оценки. С учетом неодинакового веса признаков
расстояниями между объектами в многомерном пространстве будут
значения произведений нормированных признаков на соответствующие им веса.
2.2. Меры расстояний в кластеризации
Сходство объектов в кластерном анализе оценивается количественно, с этой целью вводится понятие метрики. Сходство или различие между объектами устанавливается в зависимости от метрического расстояния между этими объектами. Каждый объект может быть представлен точкой в k-мерном пространстве признаков, и
тогда сходство или различие между объектами будет определяться
расстоянием между этими объектами [1].
13
Есть несколько метрик измерения степени схожести объектов.
Для пары объектов xi и xj расстоянием (метрикой) между ними
в пространстве признаков называется величина dij, удовлетворяющая аксиомам:
1. dij ≥0.
2. dij = dji.
3. dij + djc≥ dic.
Мерой близости (сходства) пары объектов xi и xj называется величина mij, имеющая предел и возрастающая с возрастанием близости объектов.
1. mij непрерывна.
2. mij = mji.
3. 1≤mij≤0.
Следующая формула связывает расстояние и меру близости:
m=
1
.
1+ d
Пусть n измерений x1, x2,..., xn представлены матрицей данных
размером p×n:
 x11 x12 ... x1n 


=
X =
x21 x22 ... x2n 
 x p1 x p2 ... x pn 


( x1, x2 , xn ).
Тогда расстояние между парами векторов d(xi, xj) могут быть
представлены в виде симметричной матрицы расстояний:
 0 d12 ... d1n 


D =  d21
0 ... d2n  .
d p1 d p2 ... 0 


Пары значений мер сходства можно объединить в матрицу сходства:
 1
m12 ... m1n 


M = m21
1
... m2n  .
m p1 m p2 ... 1 


Величину mij также называют коэффициентом сходства.
Существует множество метрик, основные из них:
14
1. Евклидово расстояние.
Наиболее распространенная метрика. Евклидово расстояние является геометрическим расстоянием в многомерном пространстве:
n
∑ ( xi − xj )
E
=
d ij
2
.
i,j =1
2. Квадрат евклидова расстояния.
Применяется с целью придания наиболее удаленным друг от
друга объектам большего веса. Метрика вычисляется по следующей
формуле:
n
∑ ( xi − xj )
QE
=
d ij
2
.
i,j =1
3. Расстояние городских кварталов (манхэттенское расстояние).
Эта метрика определяет среднее разностей по всем координатам.
В большинстве случаев эта метрика приводит к аналогичным с метрикой евклидова расстояния результатам, но при этом уменьшается влияние отдельных выбросов, так как они не возводятся в квадрат. Формула для расчета манхэттенского расстояния:
M
=
d ij
n
∑
i,j =1
xi − xj .
4. Расстояние Чебышева.
Это расстояние имеет значение, когда нужно определить два объекта как «различные» только по одной координате. Расстояние Чебышева вычисляется по формуле
(
)
=
max xi − xj .
d Ch
ij
5. Степенное расстояние.
Применяется в случае, когда необходимо увеличить или уменьшить вес размерности, для которой соответствующие объекты сильно отличаются. Степенное расстояние вычисляется по следующей
формуле:
P
=
d ij
n
r
∑ ( xi − xj )
p
.
i,j =1
где r и p – параметры, задаваемые пользователем. Параметр p определяет постепенное взвешивание разностей по отдельным коорди15
натам, параметр r задает прогрессивное взвешивание больших расстояний между объектами. Если p = r = 2, то это расстояние совпадает с расстоянием Евклида.
Выбор метрики является прерогативой аналитика, поскольку
результаты кластеризации при использовании различных мер могут значительно отличаться.
Перед процедурой кластеризации, когда каждый объект является отдельным кластером, расстояния между объектами характеризуются выбранной мерой. Когда на последующих шагах образуются
кластеры из нескольких объектов, то необходима мера для оценки
расстояния между кластерами. Кластерный анализ предлагает широкий выбор таких мер:
1. Расстояние «Ближайшего соседа» или одиночная связь. Определяется как расстояние между двумя ближайшими объектами,
принадлежащими соответственно двум разным кластерам.
2. Расстояние «Дальнего соседа» или полная связь. Определяется как расстояние между двумя самыми дальними объектами, принадлежащими соответственно двум разным кластерам.
3. Невзвешенное попарное среднее. В этом методе расстояние
между двумя различными кластерами вычисляется как среднее
расстояние между всеми парами объектов в них.
4. Взвешенное попарное среднее. Метод аналогичен методу невзвешенного попарного среднего, за исключением того, что размеры
соответствующих кластеров используется в качестве их весовых коэффициентов. Поэтому этот метод применяют в тех случаях, когда
размеры кластеров предполагаются неравными.
5. Невзвешенный центроидный метод. Расстояние между двумя
кластерами определяется расстоянием между их центрами.
6. Взвешенный центроидный метод (медиана). Этот метод аналогичен предыдущему, за исключением того, что для учета разницы между размерами кластеров используются веса. Поэтому метод
применяют в тех случаях, когда имеются значительные отличия
в размерах кластеров.
7. Метод Варда. В этом методе в качестве целевой функции применяют внутригрупповую сумму квадратов отклонений, которая
есть ни что иное, как сумма квадратов расстояний между каждым
объектом и центром кластера. На каждом шаге объединяются такие два кластера, которые приводят к минимальному увеличению
целевой функции, т. е. внутригрупповой суммы квадратов. Этот
метод направлен на объединение близко расположенных кластеров.
16
2.3. Методы кластерного анализа
Методы кластерного анализа можно разделить на две группы:
– иерархические;
– неиерархические.
Каждая группа представлена множеством алгоритмов. Применяя различные методы, аналитик может получить неодинаковые
результаты для одного и того же набора данных. В кластерном анализе это считается нормальным явлением.
2.3.1. Иерархические алгоритмы
Процесс иерархической кластеризации последовательно объединяет меньшие кластеры в большие (агломеративные методы) или
последовательно разбивает большие кластеры на меньшие (дивизимные методы).
Иерархические агломеративные методы характеризуются последовательным объединением исходных объектов с соответствующим
уменьшением количества кластеров. В исходном состоянии все объекты являются отдельными кластерами. На первом шаге близкие
по метрике объекты (похожие объекты) объединяются в отдельные
кластеры. На последующих шагах объединение продолжается до
тех пор, пока все объекты не будут собраны в один кластер.
Иерархические дивизимные (делимые) методы являются логической противоположностью агломеративным методам. В исходном
состоянии все объекты образуют один кластер, который на последующих шагах разбивается на меньшие кластеры. Разбиение продолжается до тех пор, пока каждый из объектов не будет представлять
собой отдельный кластер.
Принцип работы описанных групп методов в виде дендрограммы
показан на рис. 2.1.
Иерархические алгоритмы связаны с построением дендрограмм,
которые являются результатом иерархического кластерного анализа.
Дендрограмма (от греч. dendron – дерево) описывает близость отдельных объектов и кластеров друг к другу и представляет в графическом виде последовательность объединения/разделения кластеров.
Дендрограмма – древовидная схема из n уровней, соответствующих n шагам процесса последовательного укрупнения кластеров.
Дендрограмму также называют деревом объединения кластеров,
деревом иерархической структуры. Дендрограмма представляет собой вложенную группировку объектов, которая изменяется на различных уровнях иерархии.
17
0
1
2
Агломеративные методы
4
3
Шаги
A
A,B
B
A,B,C,D,E
C
C,D,E
D
D,E
E
Шаги
4
3
2
1
0
Дивизимные методы
Рис. 2.1. Дендрограмма агломеративных
и дивизимных методов
Шаги
В дендрограмме объекты могут располагаться горизонтально,
как на рис. 2.1, или вертикально, как на рис. 2.2.
Числа 11, 10, 3 и т. д. соответствуют номерам объектов исходной
выборки. На первом шаге каждый объект представляет один кластер (вертикальная линия), на втором шаге объединяются такие
объекты, как 11 и 10; 3, 4 и 5; 8 и 9; 2 и 6. На третьем шаге продолжается объединение в кластеры объектов 11, 10, 3, 4, 5 и 7, 8, 9.
Данный процесс продолжается до тех пор, пока все объекты не объединятся в один кластер.
4
3
2
1
0
11 10
3 4
5
1
7
8
9
2 6
Рис. 2.2. Пример вертикальной дендрограммы
18
Поясним логику кластерного анализа на следующем примере.
Рассмотрим совокупность из 6 объектов A, B, C, D, E, F, охарактеризованных по шести признакам альтернативного типа, принимающих одно из двух значений: характерен ( + ) и нехарактерен (–). Получаем матрицу 6×6. Подобное описание объектов по принятым признакам называется прямоугольной матрицей объекты×признаки,
так как количество объектов в анализе может не равняться количеству признаков:
1 2 3 4 5 6
A
B
C
D
E
F
−
−
−
+
+
+
+
+
+
−
−
+
+
−
−
+
−
−
−
−
+
−
+
−
+
−
+
−
−
−
+
+
−
+
+
+
Выбор объектов и описание их по определенному набору признаков соответствуют двум первым этапам кластерного анализа.
Следующий этап – построение квадратной матрицы расстояний
между объектами. Выберем в качестве метрики, например, манхэттенское расстояние и заполним значениями квадратную матрицу
объекты×объекты. Матрица расстояний симметрична относительно
главной диагонали, поэтому можно заполнить только одну половину:
A B F D E F
A
B
C
D
E
F
− 2 3 3
− 3 3
− 6
−
5
3
4
2
−
3
1
4
2
2
−
В данном случае построена матрица различий. Матрица сходства выглядит подобным образом, только на каждой позиции стоит
величина, равная разности между максимальной дистанцией и различию между объектами. Например, для пары объектов A и B сходство составило бы 4 единицы (максимальная дистанция равна 6,
различие между объектами равно 2).
19
Определяем два объекта, которые ближе всего друг к другу. Это
объекты B и F, которые отличаются только по одному признаку,
следовательно, они объединяются в один кластер (BF). Покажем это
на схеме (рис. 2.3), где объекты объединены на уровне, соответствующем расстоянию между ними.
Теперь стало пять объектов, а не шесть, и следует перестроить
квадратную матрицу объекты×объекты. Для этого потребуется
найти метрику от каждого объекта до кластера. Метрика от A до B
составляет 2 единицы, а от A до F – 3 единицы. Определим метрику от A до (BF). Правильный ответ здесь отсутствует. Посмотрим на
рис. 2.4, как расположены друг относительно друга эти три объекта.
Если в качестве расстояния от объекта до группы считать расстояние до ближайшего объекта в группе, то есть, |A(BF)| = |AB|, то это
присоединение по максимальному сходству.
Если в качестве расстояния от объекта до группы считать расстояние до наиболее удаленного объекта в группе, то есть |A(BF)| = |AF|,
то это присоединение по минимальному сходству.
Если в качестве расстояния от объекта до группы считать среднее
арифметическое расстояний до каждого из объектов в группе, то есть
|A(BF)| = (|AB| + |AF|)/2, то это присоединение по среднему сходству.
A
B
C
D
E
F
0
1
2
3
4
5
6
Дистанция присоединения
Рис. 2.3. Первый шаг кластеризации
условного набора из 6 объектов
A
B
F
Рис. 2.4. Взаимное расположение трех объектов
20
Правильными будут все три решения и еще много других, не рассмотренных здесь решений. Отсюда возникает задача выбора решения, более подходящего для той категории, к которой относятся данные. Присоединение по максимальному сходству приводит в результате к получению длинных, «лентовидных» кластеров, а по минимальному – к дроблению кластеров. Из трех приведенных вариантов
чаще используется присоединение по среднему сходству. Применим
этот вариант и тогда после первого шага кластеризации квадратная
матрица расстояний будет выглядеть следующим образом:
A (BF)
A
BF
C
− 2.5
−
D
E
3
3
5
3.5 2.5 2.5
−
6
4
−
2
−
C
D
E
Теперь самой близкой парой объектов являются D и E. Объединим их (рис. 2.5).
Перестроим матрицу расстояний для четырех объектов.
A (BF) C (DE)
A
BF
C
(DE)
− 2.5 3
4
−
3.5 2.5
−
5
−
A
B
C
D
E
F
0
1
2
3
4
5
6
Дистанция присоединения
Рис. 2.5. Второй шаг кластеризации
для 6 объектов
21
Видно, что есть два варианта для объединения на уровне 2,5:
присоединение A к (BF) и присоединение (BF) к (DE). Рассмотрим
оба варианта и сделаем правильный выбор.
Существуют различные варианты выбора. Выбор варианта можно выполнить случайно, можно в соответствии с некоторым формальным правилом, позволяющим сделать выбор, а можно посмотреть все варианты и выбрать лучший из них.
Рассмотрим все варианты и определимся с лучшим из них. Вначале реализуем первую возможность (рис. 2.6).
При выборе этого варианта была построена следующая матрица
расстояний 3×3:
( ABF) C (DE)
( ABF)
C
(DE)
−
3.25 3.25
5
−
−
При выборе второго варианта третьего шага получим следующую картину (рис. 2.7).
Варианту (рис. 2.7) соответствует следующая матрица расстояний 3×3:
A C (BFDE)
A
C
(BFDE)
− 3 3.25
4
−
−
A
B
C
D
E
F
0
1
2
3
4
5
6
Дистанция присоединения
Рис. 2.6. Первый вариант третьего шага кластеризации
для 6 объектов
22
A
B
C
D
E
F
0
1
2
3
4
5
6
Дистанция присоединения
Рис. 2.7. Второй вариант третьего шага кластеризации
для 6 объектов
A
B
C
D
E
F
0
1
2
3
4
5
6
Дистанция присоединения
Рис. 2.8. Четвертый шаг кластеризации
Сравним полученные матрицы 3×3, что позволяет определиться со вторым вариантом, дающим более компактную группировку
объектов.
Конечно, можно сделать следующие шаги (и разделить первый
вариант еще на два подварианта), но, в конце концов, убедились
бы, что лучшим вариантом третьего шага кластеризации является
именно тот, который показан на рис. 2.7. Останавливаемся на нем.
В таком случае следующим шагом является объединение объектов A и C, показанное на рис. 2.8.
Строим матрицу 2×2:
( AÑ) (BFDE)
A
(BFDE)
− 3.625
−
23
Теперь объединим два оставшихся кластера на требуемом уровне. В соответствии с принятой стилистикой построения кластерных
деревьев необходимо добавить «ствол», который тянется до максимально возможного уровня дистанции между объектами (рис. 2.9).
Древовидный граф (рис. 2.9) построен так, что образующие его
линии пересекают друг друга. Граф лучше перестроить так, чтобы
без изменения характера связей между объектами в нем не было таких пересечений (рис. 2.10).
Кластерный анализ рассматриваемого примера закончен. Теперь
необходимо интерпретировать полученный результат.
Однозначного ответа при кластерном анализе нет. Визуализация
кластерного анализа в виде дендрограммы позволяет зарегистрировать, что исходная совокупность из 6 объектов состоит из трех пар.
Однако справедливость такого вывода неочевидна.
Если вернуться к самой первой матрице расстояний 6×6, то можно увидеть, что объект E находился на расстоянии, равном две единицы от объекта F и от объекта D. Близость объектов E и D на итоговой дендрограмме отражена, а то, что объект E был также близок
к объекту F потерялось.
В этом результате кластеризации, который показан на рис. 2.10,
полностью отсутствует информация о дистанции |EF|, там есть только информация о дистанциях |DE| и |(BF)(DE)|.
Если выбрана определенная метрика и способ присоединения
объектов в кластер, то каждой матрице признаков соответствует
только одна матрица расстояний. Однако каждой матрице расстояний может соответствовать несколько матриц признаков. На каждом i-м шаге кластеризации матрице расстояний будет соответствовать матрица расстояний, вычисленная на (i + 1)-м шаге, но, исходя
A
B
C
D
E
F
0
1
2
3
4
5
6
Дистанция присоединения
Рис. 2.9. Четвертый шаг кластеризации
24
A
С
B
F
D
E
0
1
2
3
4
5
6
Дистанция присоединения
Рис. 2.10. Окончательный вид дендрограммы
кластеризации
из матрицы расстояний, полученной на (i + 1)-м шаге невозможно
восстановить матрицу расстояний, которая была получена на i-м
шаге. Это означает, что на каждом очередном шаге необратимо теряется некоторая часть информации о разнообразии исходных значений признаков объектов.
Указанное обстоятельство является одним из серьезных недостатков кластерного анализа.
Рассмотрим следующий пример задачи кластеризации: исследуется рынок потребителей услуги «Подключение к сети Интернет».
С целью выбора оптимального сегмента для позиционирования
услуги на рынке необходимо разделить потребителей на группы
(классы, сегменты) в соответствии с рядом устойчивых признаков.
После проведения классификации требуется построить правила отнесения потребителя к одному из выделенных классов (сегментов). Было опрошено 400 потребителей услуг Интернет, в анкете предлагалось указать следующие данные: возраст; пол (0 – ж,
1 – м); стаж работы в сети Интернет; среднее количество часов использования Интернет в месяц; средний доход в месяц, в тыс. руб.;
профессия (насколько тесно используется сеть Интернет в профессиональной деятельности): 0 – не использую; 1 – использую, но редко; 2 – постоянно использую.
Анкетные данные записываются в базу данных реляционного
типа для последующего проведения анализа (табл. 2.1). Сформулированные правила отнесения потребителя к одному из выделенных
классов будут представлять собой знания, полученные в результате анализа данных, и могут быть использованы в дальнейшем для
25
Таблица 2.1
Анкетные данные
№ п/п
Возраст
Стаж
Кол-во часов
Доход
Профессия
Пол
1
2
3
4
5
6
7
…
400
34
29
24
41
29
25
32
…
27
5,2
5,0
1,1
8,4
3,5
2,2
5,7
…
2,7
36,1
62,9
182,3
16,4
34,3
183,6
63,2
…
63,4
32,6
58,8
29,7
47,6
30,6
28,1
51,2
…
38,6
1
1
2
0
1
2
1
…
1
2
2
2
1
1
2
2
…
2
автоматического отнесения новых потребителей к тому или иному
сегменту рынка для эффективной и целевой работы с ними.
В обработке результатов опроса потребителей с целью кластерного анализа были задействованы иерархические методы, в данном
случае метод tree clustering пакета Statistica13.
В результате кластеризации построена вертикальная дендрограмма (рис. 2.11), соответствующая последовательным шагам процесса укрупнения кластеров. В качестве меры близости между объектами кластера выбран квадрат евклидова расстояния, а расстояние между кластерами – «одиночная связь».
На дендрограмме можно увидеть, что при расстоянии 1000 единиц образовалось три кластера. Из исходных данных, характеризующих потребителей услуги, которые здесь полностью не приводятся, ввиду их большого объема (400 записей), были выявлены следующие кластеры:
1) молодые люди, имеющие маленький стаж работы;
2) потребители с высоким стажем работы;
3) потребители, использующие Интернет в профессии.
Наименования кластерам были даны исходя из признаков, характеризующих объекты, которые вошли в тот или иной кластер.
Теперь можно сформулировать новые знания – правила отнесения нового потребителя услуги к одному из трех кластеров. Например, если возраст потребителя менее 25 лет и стаж работы менее
двух лет, то потребителю предлагать условия подключения услуги в
соответствии с маркетинговой политикой, проводимой для 1-го кластера, 2-го и 3-го кластеров.
26
Рис. 2.11. Пример дендрограммы
Решая данную задачу и другие аналогичные, можно сказать, что
кластерный анализ оказался хорошим методом, позволяющим сделать выводы, к которым невозможно прийти, построив гистограмму средних или посчитать процентное соотношение потребителей.
2.3.2. Неиерархические методы
Наряду с иерархическими методами кластеризации известны
многочисленные итеративные методы кластерного анализа (неиерархические методы). Суть их заключается в том, что перед началом кластеризации должны быть заданы некоторые начальные
условия: количество образуемых кластеров, порог завершения процесса кластеризации и т. д.
Рассмотрим наиболее известный метод этой группы – метод
k-средних, название которого было предложено в 1967 г. Дж. МакКуином. В отличие от иерархических процедур в методе k-средних
не требуется вычисления и хранения матрицы расстояний или
сходств между объектами. Алгоритм предполагает использование
только исходных значений признаков [11].
27
Пусть имеется n объектов, каждый из которых характеризуется
m признаками x1, x2, …, xn. Эти объекты разбиваются на k кластеров. Перед началом кластеризации должны быть выбраны k объектов, которые назначаются центрами кластеров. Выбор объектов
выполняется случайно или задается аналитиком исходя из какихлибо априорных соображений. Эти объекты (точки) принимаются
за эталоны. Каждому центру присваивается порядковый номер, который одновременно является и номером кластера. На первом шаге
из оставшихся (n–k) объектов извлекается точка xi с координатами
(xi1, xi2, …, xim) и вычисляется метрика до каждого из k центров,
например, евклидово расстояние. Для этой xi точки определяется
ближайший центр и проверяемый объект присоединяется к этому
центру. Центр заменяется новым, пересчитанным с учетом присоединенного объекта, а объем кластера увеличивается на единицу.
Если возникает ситуация, при которой получаются два или более
минимальных расстояния, то i-й объект приписывается к кластеру
с наименьшим порядковым номером.
На следующем шаге выбираем точку xi + 1 и для нее повторяются
все процедуры, описанные ранее. Таким образом, через (n–k) шагов
все объекты будут приписаны к одному из k кластеров, но на этом
процесс разбиения еще нельзя считать завершенным.
Для того чтобы добиться устойчивости разбиения по той же метрике, все объекты x1, x2, …, xn опять подсоединяются к полученным
кластерам, при этом веса продолжают накапливаться. Новое разбиение сравнивается с предыдущим. Если они совпадают, то работа алгоритма завершается. В противном случае цикл повторяется.
Окончательное разбиение имеет центры C1, C2, Ck, которые не совпадают с первоначальными. При этом каждый объект xi, x = 1, …, n
будет приписан к такому кластеру l, расстояние до центра которого
минимально.
Возможны две модификации метода k-средних. Первая предполагает, что центр кластера пересчитывается после каждого изменения его состава, а вторая – после завершения просмотра всех
данных. В обоих случаях итеративный алгоритм этого метода минимизирует дисперсию внутри каждого кластера, хотя в явном виде
такой критерий оптимизации не используется.
Пример работы алгоритма k-средних для k = 2 показан на
рис. 2.12.
Результат кластерного анализа методом k-средних подвергается
проверке с помощью оценки отличия кластеров друг от друга. С этой
целью рассчитываются средние значения для каждого кластера. При
28
10
С1
9
k=2
Выбор k объектов
как центров
кластеров
8
7
6
С2
5
4
3
2
1
0
0
1
2
3
4
5
6
7
8
9
10
0
1
2
3
4
5
6
7
8
9
10
10
9
8
7
6
Назначение
каждого объекта
наиболее
подходящему
кластеру
5
4
3
2
1
0
10
9
8
7
6
С2
5
4
С1
3
2
1
Пересчет
центроидов
0
0
1
2
3
4
5
6
7
8
9
10
0
1
2
3
4
5
6
7
8
9
10
7
8
9
10
10
9
8
7
6
5
4
3
2
1
Перераспределение
объектов
0
10
9
8
С1
7
6
5
4
3
С2
2
1
0
0
1
2
3
4
5
6
Рис. 2.12. Пример работы алгоритма k-средних (k = 2)
29
хорошей кластеризации должны быть получены сильно отличающиеся средние для всех измерений или хотя бы большей их части.
Алгоритм k-средних понятен и быстро работает, что является
его положительной стороной, но алгоритм слишком чувствителен к
выбросам, которые могут искажать среднее и может медленно работать на больших базах данных.
Возможным решением проблемы чувствительности к выбросам
является использование модификации алгоритма k-средних – алгоритм k-медианы, то есть центроиды кластеров определяем не как
покоординатное среднее, а как покоординатную медиану.
Выбор числа кластеров является сложным вопросом. Если нет
предположений относительно этого числа, рекомендуют создать
2 кластера, затем 3, 4, 5 и т. д., сравнивая полученные результаты.
Если в рассматриваемой задаче кластеризации количество признаков велико, то это приводит к выделению кластеров нечеткой
структуры. В результате аналитику достаточно сложно интерпретировать полученные кластеры.
Рис. 2.13. График средних значений признаков
по каждому из кластеров
30
Обычно, когда результаты кластерного анализа методом k-средних
получены, можно рассчитать средние для каждого кластера по каждому признаку, чтобы оценить, насколько кластеры отличаются друг
от друга.
Та же самая задача кластеризации рынка потребителей услуги
«Подключение к сети Интернет» решена методом k-средних. График средних значений признаков по каждому из кластеров, полученный методом k-средних приведен на рис. 2.13.
Как и в иерархическом методе, потребители разделились на три
кластера. Кроме того, из графика можно видеть, что наиболее значимым признаком, влияющим на кластеризацию объектов, оказался признак «количество часов», потом «возраст» и только потом «стаж».
Также пакет Statistica13 позволяет оценить математические характеристики кластера, найти значения F-статистики для каждого
объекта, позволяющие оценить, насколько хорошо соответствующий объект дискриминирует кластеры и многое другое.
Более понятные и прозрачные результаты кластеризации могут
быть получены, если вместо множества исходных признаков использовать некие обобщенные переменные или критерии, содержащие в сжатом виде информацию о связях между переменными. Таким образом, возникает задача снижения размерности данных. Она
может решаться при помощи различных методов, одним из наиболее распространенных является факторный анализ.
2.4. Факторный анализ
Факторный анализ – это метод, применяемый для изучения взаимосвязей между значениями переменных.
Критерии, выделенные в результате факторного анализа, содержат в сжатом виде информацию о существующих связях между
переменными. И таким образом большое число признаков объекта
сводится к меньшему числу независимых влияющих величин, которые называются факторами. Таким образом, в один фактор объединяются переменные, которые сильно коррелируют между собой.
Существует множество статистических методов, использующихся для изучения взаимосвязи между независимыми и зависимыми
переменными, но факторный анализ применяется, чтобы понять
закономерность отношений между многими зависимыми переменными, одновременно открывая природу независимых переменных,
которые на них влияют.
31
2.4.1. Методы факторного анализа
Появление факторного анализа связывают с английским ученым Ч. Спирменом. Началом современного этапа факторного анализа принято считать статью Спирмена, опубликованную в 1904 г.
в «Американском психологическом журнале» под названием
«General Intelligence Objectively Determined and Measured», в которой описана теория единственного генерального и некоторого числа
характерных факторов.
Одной из наиболее традиционных форм представления экспериментальных данных является матрица, столбцы которой соответствуют некоторым параметрам, свойствам, признакам и тому подобное, а строки – отдельным образцам, объектам, явлениям, которые можно описать с помощью набора конкретных параметров [12].
На практике число строк может достигать нескольких сотен тысяч,
а число столбцов – нескольких сотен. Прямой анализ матриц такого
размера невозможен, вследствие чего в математической статистике
появилось много подходов и методов, которые предназначены для
сжатия исходной информации, представленной в виде матрицы,
для извлечения из исходной информации наиболее существенной,
отбросив маловажное, случайное.
При анализе данных, представленных в матричной форме, рассматриваются два типа задач. Целью первого типа задач является
получение «краткого описания» распределения объектов, а задачами
второго типа – выявление взаимоотношений между параметрами.
Факторный анализ позволяет работать с данными, представленными в виде корреляционной матрицы [12]. Гипотеза, лежащая в
основе методов факторного анализа, заключается в следующем:
наблюдаемые или измеряемые параметры являются лишь косвенными характеристиками изучаемого объекта или явления, в действительности же существуют скрытые, не наблюдаемые непосредственно, параметры или свойства, число которых мало и которые
определяют значения наблюдаемых параметров. Скрытые параметры принято называть факторами. Таким образом, можно сформулировать задачу факторного анализа так: представить наблюдаемые параметры в виде линейных комбинаций факторов, и, возможно, некоторых дополнительных, несущественных величин – шума.
Примечательным является то, что хотя сами факторы не известны,
такое разложение может быть найдено и такие факторы могут быть
определены, то есть для каждого объекта могут быть указаны значения каждого фактора.
32
В терминах матрицы данных задача факторного анализа может
быть понята как задача приписывания к матрице небольшого числа
новых столбцов, с помощью которых в том или ином смысле хорошо
представляются все столбцы исходной матрицы и определения коэффициентов такого представления.
Факторный анализ предполагает, что наблюдаемые переменные
представляют собой линейную комбинацию некоторых латентных,
иначе скрытых, факторов. Некоторые из них являются уникальными для каждого параметра в отдельности, другие же могут быть
общими для нескольких переменных. Характерные факторы ортогональны друг другу. Таким образом, характерные факторы не вносят вклад в ковариацию между переменными. Иначе говоря, только
общие факторы, число которых предполагается меньшим числа наблюдаемых переменных, влияют на ковариацию между ними [13].
Принимаемая в факторном анализе линейная система такова, что
структура ковариации может быть идентифицирована без ошибок,
если известна матрица нагрузок латентных факторов. Тем не менее
однозначное восстановление латентной факторной структуры исходя из наблюдаемой ковариационной структуры всегда проблематично [12].
В зависимости от задач исследования можно выбрать из двух видов факторного анализа [14].
1. Конфирматорный (подтверждающий) анализ. Моделирование
позволяет проверить определенные гипотезы о структуре и числе
факторов и их нагрузках.
2. Разведочный анализ. Является описательным методом, осуществляется при исследовании скрытой факторной структуры без
предположения о числе факторов и их нагрузках.
В обоих случаях существуют три основных этапа [14]:
– подготовка соответствующей матрицы ковариаций;
– выделение первоначальных факторов;
– вращение с целью получения окончательного решения.
Рассмотрим основные известные методы факторного анализа.
Метод главных компонент
Описание метода главных компонент было опубликовано Г. Хотеллингом в 1933 г., но идея была предложена Пирсоном в 1905 г.
без ее алгебраического обоснования [13].
Рассматриваемый метод позволяет при заданной n-мерной корреляционной матрице найти новую ортогональную n-мерную систему координат так, чтобы максимум полной дисперсии лежал вдоль
33
направления первой главной компоненты, а максимум оставшейся
дисперсии – в направлении второй главной компоненты и так далее.
Сначала представим геометрическую интерпретацию метода.
Пусть измеряются три параметра у n объектов. Данную ситуацию
можно представить в виде, показанном на рис. 2.14: N точек сосредоточены в трехмерном пространстве с тремя осями переменными
X, Y, Z в облаке вокруг единого центра тяжести.
Рассматриваемое облако объектов, в общем случае, имеет овальную форму и называется эллипсоидом. В частном случае, когда дисперсия по величине одинакова во всех трех направлениях получают
шар. На рис. 2.14 изображено овальное тело с тремя секущими плоскостями (различно заштрихованными), проходящими через центр
облака. Оси координат первоначальных данных являются в некоторой степени произвольными. Систему координат XYZ можно было бы
сместить вдоль какой-либо оси, не меняя облако точек как таковое.
Также есть возможность вращения системы координат относительно
начала координат в любом из трех измерений, при этом в известной
степени удерживать облако данных в неизменном состоянии. Таким
образом, очевидно, что существует бесконечно много систем координат, в которых можно представить наблюдаемые точки. Среди них
есть система координат, представляющая особый интерес – система
координат главных компонент. Самый длинный диаметр овального
тела является первой главной компонентой – λ1. Вторая главная компонента – λ2, является самым длинным диаметром в плоскости, орλ2
Y
λ1
λ3
Z
X
Рис. 2.14. Трехмерное распределение точек
с соответствующими главными компонентами [12]
34
тогональной к первой главной компоненте и проходящей через центр
системы, заштрихованной вертикально. Третья главная компонента
λ3 в трехмерном случае перпендикулярна к первой и второй главной
компоненте и проходит через центр облака [12].
В геометрическом смысле метод главных компонент заключается в том, что сначала определяют самую длинную ось эллипсоида,
которая является первой главной компонентой и проходит через
центр тяжести. После устанавливают подпространство – в рассматриваемом случае плоскость, перпендикулярное к первой главной
компоненте и проходящее через центр тяжести. В данном подпространстве находится следующая по величине ось скопления точек и
так далее до тех пор, пока не будут последовательно определены все
главные компоненты. Таким образом, с помощью метода главных
компонент устанавливаются направления этих компонент относительно исходной системы координат [12].
Можно наглядно увидеть ситуацию после выделения первого
главного фактора (рис. 2.15). На нем все точки облака спроецированы на плоскость, которая проходит через центр тяжести перпендикулярно к первой главной компоненте, при этом проецирование
происходит параллельно λ1, как это показано для одной точки.
По координатам точек на этой плоскости ищут вторую главную
компоненту, направление которой снова устанавливается так, чтобы максимум дисперсии лежал в этом же направлении. Третья
главная компонента проходит через центр тяжести перпендикулярно к λ1 и λ2.
λ2
Y
λ1
λ3
Z
X
Рис. 2.15. Ситуация после установления
первой главной компоненты [12]
35
Если все n точек спроецировать параллельно плоскости λ2λ3 на
первую главную компоненту, то распределение точек на этой прямой укажет максимум дисперсии в одном измерении. Аналогичным
способом можно спроецировать точки на любую другую главную
компоненту или на гиперплоскости (подпространства), которые на
них натянуты. Подпространство, натянутое на главные компоненты
λ2 и λ3 на рис. 2.15, расположено таким образом, что проекция всех
точек на нее дает максимум дисперсии в двух измерениях. Изображение рассматриваемой плоскости показано на рис. 2.16. Поскольку полная дисперсия известна, то можно поэтапно установить, какая ее доля содержится в гиперплоскости главных компонент [12].
Случай, когда для описания всех объектов достаточно двух главных компонент показан на рис. 2.17. Точки соответствуют результатам наблюдений по трем переменным – X, Y, Z, которые почти полностью зависят от двух величин. Все точки расположены на одной
плоскости или вблизи нее, при этом данная плоскость наклонена
под некоторым углом к исходной системе координат. Если выбрать
вместо трех измеренных переменных для изображения точек только две, то есть использовать подпространство, натянутое на первую
λ2
λ2
λ1
λ3
λ1
Рис. 2.16. Проекции точек на плоскости,
образованные главными компонентами [12]
36
λ3
Y
λ3
λ1
λ2
Z
X
Рис. 2.17. Распределение результатов наблюдений
λ2 главной компонентыλλ
2 3 [12]
Y
с малым
рассеянием вдоль
λ3
λ1
и вторую главные компоненты, то при малом рассеянии точек вне
λ[12].
λ1
3
плоскости теряется незначительная часть информации
Плоскость, которая представлена на рис. 2.17, показана в проекциях на рис. 2.18. Дисперсия в направлении λ3 мала. Если бы все
точки находились на одной плоскости, λто
2 потребность в третьей
главной компоненте отпала быλ 3совсем. Тогда без потери какой-либо
информации все точки можно было бы располагать не в системе коλ1
ординат XYZ, а в системеZλ1λ2.
Переход от системы координат XYZ к системе λ1λ2λ3 на рис. 2.15–
2.18 соответствуют геометрическому решению задачи выделения
X
факторов с применением метода главных компонент.
λ2
λ2
λ1
λ3
λ3
λ1
Рис. 2.18. Три проекции овального тела
(рис. 2.17) [12]
37
Теперь рассмотрим алгебраическое решение. Основной математический метод нахождения направлений главных компонент основан
на вычислении собственных чисел и собственных векторов матрицы ковариации. Рассмотрим исходный набор векторов X линейного
пространства Lk – образцов. Применение метода главных компонент
позволяет перейти к базису пространства Lm, где m≤k. В этом базисе
первая главная компонента соответствует направлению, вдоль которого дисперсия векторов исходного набора максимальна. Направление второй главной компоненты выбирается так, что дисперсия первоначальных векторов вдоль него является максимальной при условии ортогональности первому вектору базиса. Аналогичным образом
определяются последующие векторы базиса. В итоге направления
векторов базиса выбраны таким образом, чтобы максимизировать
дисперсию исходного набора вдоль первых компонент, называемых
главными компонентами. В результате основная изменчивость векторов первоначальных данных представлена несколькими первыми
компонентами, что дает возможность перейти к пространству меньшей размерности, отбросив менее существенные компоненты [15].
В результате применения метода главных компонент вычисляется
матрица W размера m×k, осуществляющая проекцию векторов пространства Lk на подпространство, натянутое на главные компоненты:
Y = W(X–µ), Y∈Lm, X∈Lk,
где X – вектор из начального набора; Y – координаты вектора в подпространстве главных компонент; µ – математическое ожидание
вектора X исходного набора.
Важно отметить свойства векторов базиса, вычисленных с помощью метода главных компонент: обратная проекция вектора Y в Lk
дает минимальную ошибку реконструкции (минимальное расстояние до образа вектора Y) [15].
Решение задачи методом главных компонент сводится к поэтапному преобразованию матрицы исходных данных X. Пусть размерность матрицы X – n×k, где n – число образцов; k – число признаков.
Тогда Z – матрица центрированных и нормированных значений
признаков, элементы которой вычисляются по формуле
zij =
xij − xj
,
sj
где xij – i-е значение j-й компоненты вектора X=
и i 1=
,n, j 1, k; xj –
оценка математического ожидания j-й компоненты вектора X:
38
∑ xij
xj = i
n
,
Sj – корень квадратный из оценки дисперсии j-й компоненты вектора X:
∑ ( xij − xj )
2
i
sj =
.
n −1
Матрица оценок парных корреляций рассчитывается по формуле
R=
zT ⋅ z
.
n −1
Затем вычисляется диагональная матрица Λ собственных (характеристических) чисел. У матрицы R, размерность которой n×n,
не может быть больше, чем n собственных значений – λj. Множество
решений собственных значений находят решением характеристического уравнения
R − λI =0.
Характеристики вариации λj – это показатели оценок дисперсии
каждой главной компоненты. Суммарное значение собственных
значений – ∑ λ j равно сумме оценок дисперсий элементарных признаков xj. При условии стандартизации первоначальных данных
рассматриваемая сумма равна числу признаков – k.
Решив характеристическое уравнение, находят его корни λ j . Затем вычисляют собственные векторы матрицы R, что означает решение k систем линейных уравнений для каждого j = 1, k. В общем
виде система имеет вид:
(
)
 1 − λ j v 1j +r12v 2 j +r13v 3 j +... + r1kvkj =0

r21v 1j + 1 − λ j v 2 j +r23v3 j + ... + r2kvkj =0
.

...................................................

rk1v 1j +rk2v 2 j +rk3v 3 j +... + 1 − λ j vkj =0
(
)
(
)
Рассматриваемая система объединяет однородные линейные
уравнения, и так как число ее уравнений равно числу неизвестных,
она имеет бесконечное множество решений.
39
После вычисляется матрица A – матрица компонентного отображения, элементы которой являются весовыми коэффициентами –
akj. Вначале матрица A имеет размерность k×k – по числу признаков
xj, затем в анализе остается m наиболее значимых компонент, m≤k.
Значения матрицы компонентного отображения вычисляют по известным данным матрицы собственных чисел Λ и нормированных
собственных векторов V по формуле
A = V Λ.
Матрица главных компонент – G, имеет размерность k×n. Находится по формуле
G = A −1 ZT .
В общем виде записывается следующим образом:
g11 g12
g21 g22
.
.
gk1 gk2
...
...
.
...
g1n
g2n
.
gkn .
Данная матрица содержит значения всего набора главных компонент, число которых равно k. При уменьшении размерности до
Исходные данные
Матрица ковариаций
Собственные числа
Собственные вектора
Матрица компонентного отображения
Главные компоненты
Рис. 2.19. Вычислительная схема
метода главных компонент
40
m главных компонент размер матрицы соответственно будет m×n.
Величина m или назначается пользователем, или определяется по
значениям λj.
В общем виде вычислительная схема метода главных компонент
показана на рис. 2.19.
Метод наименьших квадратов
Метод наименьших квадратов в факторном анализе сводится к
минимизации остаточной корреляции после выделения определенного числа факторов и к оцениванию степени соответствия вычисленных и наблюдаемых коэффициентов корреляции (берется сумма квадратов отклонений) [12]. При взятии количества факторов,
равного числу переменных, рассчитанные и наблюдаемые коэффициенты корреляции совпадут. Также расхождение между ними
уменьшается при увеличении числа предполагаемых факторов. Поэтому при использовании рассматриваемого метода считается, что
число факторов меньше числа переменных.
В обобщенном виде алгоритм состоит в следующем [13].
1. Вводится предположение, что количество факторов есть некоторое k. Есть вариант начать с однофакторной гипотезы, а после,
добавляя факторы, получить приемлемое решение.
2. Производится оценка общностей, то есть применяется квадрат
множественного коэффициента корреляции между рассматриваемой переменной и остальными.
3. Выделяются k факторов, для которых вычисленные коэффициенты корреляции наилучшим образом приближают наблюдаемые корреляции (в смысле минимума суммы квадратов отклонений). На текущем этапе решается уравнение, аналогичное характеристическому уравнению в методе главных компонент.
4. Опять производится оценка общностей с использованием матрицы факторного отображения, полученной на предыдущем шаге.
Процесс повторяется, пока дальнейшее улучшение станет невозможным. Описанный алгоритм известен под названием «Метод
главных факторов с итерациями по общностям».
Метод максимального правдоподобия
Данный метод имеет ту же цель, что и метод наименьших квадратов – найти факторное решение, которое наилучшим образом
объясняет наблюдаемые корреляции [13]. Алгоритм состоит в следующем. Пусть наблюдаемые данные – выборка из генеральной
совокупности, которая точно соответствует k-факторной модели.
41
Совместное распределение переменных, включая факторы, предполагается многомерным нормальным. Неизвестными являются
значения нагрузок для каждой переменной. Задача сводится к оцениванию значений латентных переменных генеральной совокупности, при которых в заданных предположениях функция правдоподобия для распределения элементов корреляционной матрицы максимальна. Несколько иной критерий заключается в нахождении
факторных нагрузок, при которых общие факторы и наблюдаемые
переменные находятся в канонической корреляции, то есть коэффициент корреляции между ними максимален. Третий критерий,
который основан на тех же принципах, сводится к определению
факторных нагрузок, при которых детерминант матрицы остаточных корреляций максимален. Все рассмотренные критерии достаточно сложны для применения на практике, но есть различные
итерационные схемы для получения на их основе решений, которые
значительно отличаются друг от друга с точки зрения вычислительной эффективности.
Все варианты метода максимального правдоподобия сводятся
к решению характеристического уравнения [12], представленного
в виде:
R2 − λI =0,
где R2 определяется соотношением
(
)
R2 =U −1 R − U 2 U −1 =U −1RU −1.
где R2 – редуцированная корреляционная матрица; U2 – оценка
дисперсии характерных признаков.
В отличие от метода наименьших квадратов в вычисляемую на
каждом шаге оценку общностей с большим весом входят корреляции с переменными, имеющими меньшую характерность [13].
Альфа-факторный анализ
Считается, что и в методе наименьших квадратов, и в методе максимального правдоподобия существует генеральная совокупность
объектов, на которую распространяются результаты статистического анализа выборки. В альфа-факторном анализе используемые
переменные считаются выборкой из некоторой совокупности объектов. Таким образом, в рассматриваемом методе выводы носят не
статистический характер, а психометрический [13].
42
Анализ основан на выделении таких факторов, которые имеют
максимальные корреляции с соответствующими факторами генеральной совокупности переменных [12]. С другой стороны, характерные факторы при данном подходе можно рассматривать как
ошибки, обусловленные психометрической выборкой переменных.
Таким образом, оценки общностей в этом контексте имеют смысл
«надежностей».
На первом шаге формируется корреляционная матрица вида:
(
)
=
R3 H−1 R − V2 H−1,
где V2 и H2 – диагональные матрицы характерностей и общностей соответственно; H–1 – диагональная матрица, элементы которой представляют обратные величины к квадратным корням их общностей.
Характеристическое уравнение, связанное с этой матрицей, имеет следующий вид:
R3 − λI =0.
В методе максимального правдоподобия матрица нормируется с
помощью характерностей, а в альфа-факторном анализе – дисперсий общностей. Иначе говоря, в первом случае больший вес имеют
переменные с большей общностью, а во втором – наоборот, с меньшей [12]. В обоих ситуациях решение осложняется пересчетом значений общностей в процессе итераций.
В рассматриваемом методе количество выделяемых факторов
определяется с помощью критерия, который заключается в том, что
соответствующие собственные величины должны быть больше 1.
Данный критерий эквивалентен критерию выделения факторов с
использованием коэффициента обобщенности α – квадрат коэффициента корреляции данного фактора с соответствующими факторами из генеральной совокупности, где α – положителен. При данном
подходе не применяются обычные критерии значимости, так как
совокупность объектов предполагается известной [13].
Канонический факторный анализ
Описание данного метода было опубликована в 1955 г. В какойто степени канонический факторный анализ противоположен методу главных компонент. Рассмотрим принцип этого метода [13].
Есть две группы переменных, которые измеряются у n индивидуумов. Решается вопрос, какое линейное преобразование необхо43
димо применить, чтобы получить две результирующие величины,
которые будут иметь максимальную связь с рассматриваемыми
переменными. Речь идет о так называемой канонической корреляции. Метод отчасти противоположен дискриминантному анализу,
в котором ведется поиск максимального разделения между двумя
группами наблюдений. В каноническом – наибольшая связь между
двумя группами переменных.
По рассматриваемым переменным выделяется фактор, который
имеет наибольший коэффициент корреляции с наблюдаемыми переменными. По остаточной матрице выделяется второй фактор, обладающий тем же свойством и так далее, пока все недиагональные
элементы матрицы R не станут близки к нулю. В методе главных
компонент первый выделенный фактор содержит максимум дисперсии входных данных, а в каноническом методе – факторы представляют гипотетические величины, которые имеют максимальную
связь с наблюдаемыми переменными. Важным вопросом является
оценка и определение факторов по рассматриваемым переменным с
наибольшей точностью.
Аналогично с методом максимального правдоподобия полученные в результате применения канонического анализа факторы
инвариантны относительно изменений масштаба переменных. Увеличение переменных на одинаковую величину или умножение на
постоянную не приводят к изменению результирующих канонических факторов.
Цель исследования определяет выбор метода. Канонический
факторный анализ применяется, если полученный фактор должен
иметь максимальную связь с переменными.
2.4.2. Решение задачи идентификации веществ
методом факторного анализа
Схема процесса идентификации вещества показана на рис. 2.20.
Предполагается, что спектры веществ уже получены и представлены в виде векторов.
Программное обеспечение, автоматизирующее решение задачи
идентификации веществ состоит из следующих модулей:
– функция, реализующая метод кластерного анализа k-средних;
предполагается проверка теории о возможности верного разделения
веществ на кластеры, обнаружения некорректных данных в процессе кластеризации;
– функция, реализующая метод главных компонент;
44
Детектор
Прибор для
получения
спектра вещества
Результат
детектирования
База данных
веществ
Компьютер
Рис. 2.20. Процесс идентификации вещества
– функция для формирования базы данных известных веществ;
– функция, позволяющая идентифицировать вещество.
Работа с данными, представленными в матричной форме, организована в среде MatLab.
Для оценки достоверности решения задачи идентификации веществ полученные результаты сравнивались с работой прибора
«Данник-4» (рис. 2.21).
В приборе «Данник-4» для проведения спектрального анализа
используется источник инфракрасного излучения и неподвижная
дифракционная решетка совместно со специальным матричным
пироприемником. Кроме того, в состав прибора входит электрон-
Рис. 2.21. Прибор «Данник-4» [10]
45
ный блок, обеспечивающий управление и питание прибора, и компактный компьютер для управления и обработки данных.
Исходными данными для создания базы данных, которая будет
использоваться для идентификации образцов, являются спектры
веществ, представленных в виде векторов, длина которых равна
128. Они записаны в текстовый файл в виде матрицы. В процессе
формирования базы данных данная матрица будет дополнена, и на
ее основе будет вычислена матрица главных компонент, по данным
которой и будет производиться идентификация.
Кластерный анализ реализован функцией Clustering(). Входными параметрами являются известные спектры веществ, представленных в виде матрицы, которая записана в файл формата *.txt, и
предполагаемое количество кластеров.
В результате выполнения функции выстраиваются графики образованных кластеров, вектор распределения веществ по кластерам
и вычисленные центры кластеров, записанные в отдельный файл в
виде матрицы.
Рассмотрим результаты работы функции на примере из 75 образцов. Предлагается выделить 5 кластеров. Результаты кластеризации показаны на рис. 2.22.
Для проверки корректности разбиения рассмотрим центры полученных кластеров, которые показаны на рис. 2.23.
Как видно из рис. 2.23, центры сформированных кластеров максимально отличаются друг от друга. Рассмотрим несколько кластеров более подробно. Один из сформированных кластеров показан на
рис. 2.24. В него вошло 15 образцов из исходных данных. Из графи-
Поглощение, %
Кластеризация
100
90
80
70
60
50
40
30
20
10
0
1
21
41
61 81
Номера пикселей
101
121
46
ощение, %
Рис. 2.22. Разбиение исходных образцов на кластеры
100
90
80
70
60
Центры кластеров
100
90
80
70
60
50
40
30
20
10
0
0
1
1
21
Поглощение, %
Поглощение, %
10
0
1
100
90
80
70
60
50
40
30
20
10
0
21
41
61 81
101
Номера пикселей
41
61 81
101
121
Номера пикселей
Центры кластеров
121
Центры кластеров
1
21
21
41
81
101
61
Номера пикселей
41
81
101
121
61
Номера пикселей
121
Рис. 2.23. Центры итоговых кластеров
100
90
100
Поглощение, %
Поглощение, %
90
80
70
60
50
40
70
60
50
40
30
20
30
10
20
0
10
0
80
1
1
21
21
41
61
81
101
Номера пикселей
41
61
81
101
121
Номера пикселей
Образец 1
Образец 2
Образец 1 Образец 3
Образец 2 Образец 4
Образец 3 Образец 5
Образец 4 Образец 6
Образец 5 Образец 7
Образец 6 Образец 8
Образец 7 Образец 9
Образец 8 Образец 10
Образец 9 Образец 11
Образец 10Образец 12
Образец 11Образец 13
Образец 12Образец 14
Образец 13Образец 15
Образец 14Центр кластера
121
Образец 15
Центр кластера
Рис. 2.24. Кластер, полученный на выходе функции
Поглощение, %
Поглощение, %
ка видно, что100
центр кластера представляет собой среднее значение
Образец 1
всех объектов,
вошедших в кластер.
Образец 2
90
100
1 Образец 3
Аналогичным
образом можно описать ситуации,Образец
представлен80
Образец 2 Образец 4
90 рис. 2.25, 2.26.
ные на
Образец 3 Образец 5
70
80
Образец
4 Образец
Метод главных
компонент реализован в функции
Matrix().
На 6
60
Образец 5 Образец 7
вход70подается50файл, в котором записаны известные
спектры
веОбразец 6 Образец 8
60
Образец 7 Образец 9
ществ
в виде матрицы.
Далее происходит поэтапное преобразование
40
Образец 8 Образец 10
50
исходной
матрицы
в
соответствии
с
алгоритмом
выбранного
мето- 11
30
Образец 9 Образец
40
Образец
12
Образец
10
да. Более подробно
эти
преобразования
представлены
на
рис. 2.27.
20
30
Образец 11Образец 13
В итоге имеем
и
матрицу
10 матрицу компонентного отображения
Образец 12Образец 14
20
Образец 13Образец 15
главных компонент.
0
10
0
1
1
21
40
61
81
101
Номера пикселей
61
81
41
101
121
Номера пикселей
21
41
Образец 14Центр кластера
121
Образец 15
Центр кластера47
Образец 1
Поглощение,
Поглощение,
%%
100
100
90
90
80
80
70
70
60
60
50
50
40
40
30
30
20
20
10
10
0
01
1
21
21
61
81
41
101
61 пикселей
81
41Номера
101
Номера пикселей
121
121
Образец 1
Образец
Образец21
Образец
Образец32
Образец
Образец43
Образец
Образец54
Образец
Образец65
Образец
Образец76
Образец
Образец87
Образец
Образец98
Образец
Образец10
9
Образец
Образец11
10
Образец
12
Образец 11
Образец
13
Образец 12
Образец
Образец14
13
Образец
Образец15
14
Центр
кластера
Образец 15
Центр кластера
Поглощение,
Поглощение,
%%
Рис. 2.25. Кластер, полученный на выходе функции
40
40
35
35
30
30
25
25
20
20
15
15
10
10
5
5
0
01
1
21
21
61
81
41
101
61 пикселей
81
41Номера
101
Номера пикселей
121
121
Образец 1
Образец
Образец21
Образец
Образец32
Образец
Образец43
Образец
Образец54
Образец
Образец65
Образец
Образец76
Образец
Образец87
Образец
Образец98
Образец
Образец10
9
Образец
Образец11
10
Образец
Образец12
11
Образец
Образец13
12
Образец
Образец14
13
Образец
Образец15
14
Центр
кластера
Образец
15
Центр кластера
Рис. 2.26. Кластер, полученный на выходе функции
Необходимо отметить важное свойство метода главных компонент. Матрица компонентного отображения рассчитывается один
раз на максимальной базе известных веществ. Для вычисления
главных компонент какого-либо нового объекта требуется лишь умножить спектр рассматриваемого вещества на матрицу компонентного отображения. Это свойство используется при процессе идентификации вещества.
На основе полученных в этом разделе данных будет построена
окончательная база веществ, которая будет использоваться в процессе идентификации.
48
Начало процедуры
Загрузка матрицы
спектров веществ A
Транспонирование матрицы
A → AT
Вычисление собственных значений
и собственных векторов AT
Вычисление матрицы
компонентного отображения В
Вычисление матрицы
главных компонентов С
Сохранение В и С
Конец процедуры
Рис. 2.27. Блок-схема метода главных компонент
Создание базы данных реализовано в функции DataBase(). Исходными данными являются главные компоненты известных веществ. На выходе получаем полностью сформированную базу веществ, по которой можно проводить идентификацию.
При кластеризации веществ были получены значения центров
образовавшихся кластеров – среднее значение спектра для выделенных веществ. Предлагается построить базу данных на правиле
49
стандартного отклонения. В теории вероятностей и статистике это
наиболее распространенный показатель рассеивания значений случайной величины относительно ее математического ожидания. Рассчитывается по формуле
=
s
1 n
2
∑ ( xi − x ) ,
n − 1 i =1
где xi – i-й элемент выборки; n – объем выборки; x – среднее арифметическое выборки.
В качестве выборки рассматриваются спектры веществ, объединенные в один кластер, а средним арифметическим является вычисленное значение центра.
Тогда процедуру формирования базы данных можно представить в виде следующих этапов:
1. Загрузка спектров веществ.
2. Кластеризация на основе вычисления средних значений спектра.
3. Факторный анализ на основе вычисления главных компонент
кластеров.
4. Вычисление стандартного отклонения главных компонент.
5. Добавление вещества в базу данных.
Рассмотрим некоторые значения интервалов главных компонент,
построенных с использованием правила стандартного отклонения.
Отклонения первых 4 главных компонент одного из кластеров показаны на рис. 2.28. Видно, что стандартное отклонение первых компонент мало и постепенно увеличивается. Уже на четвертой компоненте оно принимает большие значения. Это наглядно показывает,
что полученная первая компонента содержит максимум дисперсии
входного набора данных, как и требует метод главных компонент.
В связи с этим выдвигается предположение использовать для
идентификации вещества только первую главную компоненту. Рассмотрим значения первых главных компонент различных кластеров (рис. 2.29).
Из рисунка видно, что интервалы значений первых главных
компонент различных кластеров не пересекаются между собой.
Следовательно, выдвинутое предположение может быть применено
на практике.
Таким образом, для идентификации вещества по сформированной базе данных достаточно проверить, в какой диапазон попадает
первая главная компонента вещества.
50
Значение
Значение
компоненты
компоненты
1,8
min max
1,2
1,4
1
1,2
0,8
1
0,6
0,8
0,4
0,6
0,2
0,4
0
0,2
0
Значение
Значение
компоненты
компоненты
min max
1,6
1,8
1,4
1,6
2 PC
3 PC
4 PC
Номер компоненты
1 PC
2 PC
3 PC
4 PC
Номер главных
компоненты
Рис. 2.28. Интервалы
компонент
2
1,8
2
1,6
1,8
1,4
1,6
1,2
1,4
1
1,2
0,8
1
0,6
0,8
0,4
0,6
0,2
0,4
0
0,2
0
1 PC
внутри кластера
min max
min max
1 gr
1 gr
2gr
3 gr
Номер группы
2gr
3 gr
Номер группы
4gr
5gr
4gr
5gr
Рис. 2.29. Интервалы первых главных компонент
различных кластеров
Алгоритм составления базы веществ на правиле стандартного
отклонения допустим, так как значения интервалов главных компонент различных веществ не пересекаются.
Процедура идентификации вещества реализована в функции
Identification(). Входными параметрами являются матрица компонентного отображения, база данных веществ и спектр идентифицируемого вещества. База и матрица хранятся в матричной форме в
файлах с расширением *.txt. На выходе имеем сообщение о принадлежности вещества к какой-либо группе или же сообщение об отсутствии такового в базе.
51
Загрузка матрицы В
Загрузка база данных веществ
Загрузка спектра
идентифицируемого вещества М
Найти произведение В×М
Сравнить первую главную компоненту
с данными из базы данных
Сообщение
о результатах идентификации
Рис. 2.30. Алгоритм
идентификации вещества
Схематично алгоритм идентификации представлен на рис. 2.30.
Получив спектр идентифицируемого вещества, необходимо умножить его на матрицу компонентного отображения. В результате этого действия получаем главные компоненты вещества. Далее
производится проверка: в какой диапазон из базы данных попадает
первая главная компонента идентифицируемого вещества. При нахождении нужного интервала выводится сообщение с информацией
о принадлежности к определенной группе веществ, иначе сообщение об отсутствии вещества в базе.
Разработанный алгоритм идентификации вещества, основанный на кластерном и факторном анализе имеет высокую скорость
работы. Время работы алгоритма составляет в среднем 15⋅10–2 –
20⋅10–2 с, с учетом экспериментов, в которых вещество не было обнаружено в базе данных. Этот результат на порядок меньше (лучше)
времени идентификации веществ прибором «Данник-4», которое
составляет в среднем 23)⋅10–1 – 30⋅10–1 с.
Предлагаемый алгоритм имеет высокую точность идентификации, что достигнуто с помощью использования метода главных
компонент.
52
3. КЛАССИФИКАЦИЯ
3.1. Постановка задачи классификации
Классификация является наиболее простой и одновременно наиболее часто решаемой задачей анализа данных [1].
Классификация – системное распределение изучаемых предметов, явлений, процессов по родам, видам, типам, по каким-либо существенным признакам для удобства их исследования.
Классификация требует соблюдения следующих правил:
– в каждом акте деления необходимо применять только одно основание;
– деление должно быть соразмерным, то есть общий объем видовых понятий должен равняться объему делимого родового понятия:
Род
(количество равно N)
Вид 1
(количество равно k)
Вид 2
(количество равно N–k)
– члены деления должны взаимно исключать друг друга, их объемы не должны пересекаться;
– деление должно быть последовательным.
В зависимости от выбранных признаков, их сочетания и процедуры деления объектов классификация может быть:
– простой – деление родового понятия только по признаку и
только один раз до раскрытия всех видов; примером такой классификации является дихотомия, при которой членами деления бывают только два понятия, каждое из которых является противоречащим другому по принципу «А и не А»;
– сложной – применяется для деления одного понятия по разным основаниям и синтеза таких простых делений в единое целое;
примером такой классификации является периодическая система
химических элементов.
Классификация относится к задачам, которые решаются по
стратегии обучения с учителем [2].
Задачей классификации часто называют предсказание категориальной зависимой переменной на основе выборки непрерывных и/
или категориальных переменных. Если при этом зависимая переменная может принимать только два значения (например, да или
53
нет, 0 или 1), то этот тип задач относится к задачам бинарной классификации. Если зависимая переменная может принимать значения из некоторого множества предопределенных классов, то это
множественная классификация.
Классификация может быть одномерной (по одному признаку) и
многомерной (по двум и более признакам).
Рассмотрим задачу классификации на простом примере фильтрации электронной почты. Программа фильтрации должна классифицировать входящее сообщение как спам или как письмо. Пусть
решение о классификации принимается на основании частоты появления в сообщении определенных слов, например, имени получателя, безличного обращения, слов и словосочетаний типа «заработать», «приобрести», «выгодное предложение» и т. п. В базе данных
хранится информация о сообщениях электронной почты, которая
может быть использована для обучения и тестирования классификатора. Фрагмент базы данных приведен в табл. 3.1. Соответственно, можно определить два класса: 1 – spam и 2 – mail.
Таблица 3.1
База данных характеристик сообщений электронной почты
Код сообщения Объем, байт Число повторений слова Наличие ссылок Класс
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
54
18
22
30
32
24
25
32
19
22
40
25
27
40
42
42
35
36
37
27
5
10
3
2
5
2
5
4
7
5
8
7
6
7
8
6
6
6
4
∨
∨
∨
∨
1
1
2
2
1
2
2
1
1
2
1
1
2
1
1
1
1
2
2
Объем, байт
45
40
35
30
25
20
15
10
5
0
0
2
4
6
8
10
12
Повторения, слов
Рис. 3.1. Множество объектов базы данных
в двухмерном измерении
Визуализируем информацию из базы данных в виде множества
объектов в двумерном измерении «число повторений – объем». Объекты класса 1 представим квадратным красным маркером, объекты
класса 2 круглым синим маркером. На рис. 3.1 приведены объекты
двух классов.
Требуется определить принадлежность нового сообщения одному из предопределенных классов и соответственно решить, в какую
папку оно попадет. Новое сообщение (рис. 3.1) обозначено кружочком белым маркером.
Для решения поставленной задачи требуется построить модель f,
которая использует имеющиеся (накопленные в базе данных) атрибуты в качестве входных параметров и получает значение зависимого атрибута, в данном случае – номер класса, к которому будет
отнесено новое сообщение, то есть формально:
Класс = f(число повторений, объем).
Для проведения классификации с помощью математических
методов необходимо иметь формальное описание объекта, которым
можно оперировать, используя математический аппарат классификации. Таким описанием в нашем случае выступает база данных.
Каждый объект (запись базы данных) несет информацию о некотором свойстве объекта.
Набор исходных данных (или выборку данных) разбивают на два
множества: обучающее и тестовое.
Обучающее множество – это множество, которое включает данные, использующиеся для обучения (конструирования) модели f.
55
Такое множество содержит входные и выходные (целевые) значения примеров. Выходные значения предназначены для обучения
модели.
Тестовое множество также содержит входные и выходные значения примеров, однако в этом случае выходные значения используются для проверки работоспособности модели.
Процесс классификации состоит из двух этапов: конструирования модели и ее использования.
1. Конструирование модели (рис. 3.2) – описание множества
предопределенных классов, характеризуется следующими особенностями:
– каждый пример базы данных (запись) относится к одному предопределенному классу;
– на этом этапе используется обучающее множество, на нем происходит конструирование модели;
– полученная модель представлена классификационными правилами, деревом решений или математической формулой.
2. Использование модели: тестирование и классификация новых
объектов, характеризуется следующими особенностями:
– происходит оценка правильности (точности) модели (рис. 3.3):
a) известные значения из тестового примера сравниваются с результатами использования полученной модели;
б) уровень точности – процент правильно классифицированных
примеров в тестовом множестве;
в) тестовое множество, то есть множество, на котором тестируется
построенная модель, не должно зависеть от обучающего множества;
Обучающее
множество
Атрибуты
Классификатор
(Модель)
Классификационный
алгоритм
Если «ОБЪЕМ>20 и ЧИСЛО
ПОВТОРЕНИЙ >= 5 и
НАЛИЧИЕ ССЫЛОК=True
и..., то КЛАСС=1
База данных
Рис. 3.2. Конструирование модели
56
Тестовое
множество
Классификатор
(Модель)
– если точность модели допустима, возможно использование модели для классификации новых примеров, класс которых неизвеКлассификатор
стен. Процесс
использованияКлассификационный
обученного
классификатора
показан
Обучающее
(Модель)
алгоритм
на рис. 3.4. множество
Классификатор
Классификационный
Обучающее
Оценка точности
классификации может
помоалгоритмпроводиться при (Модель)
множество
щи кросс-проверки. Кросс-проверка – это процедура оценки точности классификации на данных из тестового множества, которое
Атрибуты
ЕслиТочность
«ОБЪЕМ>20
и ЧИСЛО
также называют кросс-проверочным множеством.
класПОВТОРЕНИЙ >= 5 и
сификации тестового
множества сравнивается с точностью
классиАтрибуты
НАЛИЧИЕ
ССЫЛОК=True
Если «ОБЪЕМ>20
и ЧИСЛО
и...,
то
КЛАСС=1>= 5 и
фикации обучающего множества. Если классификация
тестового
ПОВТОРЕНИЙ
НАЛИЧИЕ
ССЫЛОК=True
множества дает приблизительно такие же результаты
по точности,
и..., то КЛАСС=1
как и классификация
обучающего множества, считается, что данБаза данных
ная модель прошла кросс-проверку.
База данных
Тестовое
множество
Тестовое
множество
Атрибуты
Атрибуты
База данных
База данных
Классификатор
(Модель)
Классификатор
(Модель)
Предсказанный КЛАСС
сравнивается
с сохраненным
КЛАССОМ
Предсказанный
КЛАСС
тестового
множества
сравнивается
с сохраненным КЛАССОМ
тестового множества
Определение уровня точности
классификатора
Определение уровня точности
классификатора
Рис. 3.3. Тестирование классификатора
Классификатор
(Модель)
Классификатор
(Модель)
КЛАСС 1
КЛАСС 1
Новые данные
Новые данные
Если «ОБЪЕМ>20 и ЧИСЛО
ПОВТОРЕНИЙ >= 5 и
НАЛИЧИЕ
ССЫЛОК=True
Если «ОБЪЕМ>20
и ЧИСЛО
и...,
то КЛАСС=1>= 5 и
ПОВТОРЕНИЙ
НАЛИЧИЕ ССЫЛОК=True
и..., то КЛАСС=1
Рис. 3.4. Использование модели
57
Разделение на обучающее и тестовое множества осуществляется путем деления выборки в определенной пропорции, например,
обучающее множество – 75% от генеральной выборки данных, и
тестовое – 25% генеральной выборки данных. Этот способ следует
использовать для выборок с большим количеством примеров. Если
же выборка имеет малые объемы, рекомендуется применять специальные методы, при использовании которых обучающая и тестовая
выборки могут частично пересекаться.
3.2. Методы решения задачи классификации
Для классификации используются различные методы. Основные из них [1]:
– классификация с помощью деревьев решений;
– байесовская (наивная) классификация;
– классификация при помощи искусственных нейронных сетей;
– классификация методом опорных векторов;
– статистические методы, в частности, линейная регрессия;
– классификация при помощи метода ближайшего соседа и многие другие.
3.2.1. Деревья решений
Метод деревьев решений является одним из наиболее популярных методов решения задач классификации. Иногда этот метод также называют деревьями решающих правил, деревьями классификации и регрессии [2].
Впервые деревья решений были предложены C. I. Hovland и E. B.
Hunt в конце 50-х гг. прошлого века.
Метод деревьев находит применение в двух разных задачах анализа данных – это классификация и прогнозирование. В первом случае
– предсказывается класс объекта, а во втором – числовое значение
какого-то признака объекта, который при постановке задачи прогнозирования называют целевой переменной. Или то же самое, но относительно анализируемых данных: если зависимая, то есть целевая
переменная принимает дискретные значения, то при помощи метода
дерева решений решается задача классификации, а если зависимая
переменная принимает непрерывные значения, то дерево решений
устанавливает зависимость этой переменной от независимых переменных, то есть решает задачу численного прогнозирования [10].
Дерево решений визуализируется в виде древовидного графа,
состоящего из узлов и листьев, соединенных между собой дугами.
58
В узлах графа происходит принятие решений, а листья указывают
на классы (рис. 3.5).
Пусть X есть множество объектов, а их количество – есть мощность данного множества |X| = n. Также имеется множество классов
(метки класса):
С = {C1, C2, …, Ck}
(3.1)
и множество признаков:
A = {А1, А2, …, Аm}.
(3.2)
Тогда для решения задачи классификации необходимо задать:
– целевой признак – признак, по которому проводится классификация;
– обучающую выборку – множество объектов, для которых известно значение целевого признака; с помощью этого множества
происходит обучение дерева;
– определить формат ввода обучающей выборки.
Значение 1
Значение 3
Значение 4
≤
Узел 1
≤
Узел 3
Лист 2
>
Лист 3
Лист 1
Значение 2
Корневой
узел
≤
Узел 4
Лист 4
>
Узел 2
>
Лист 5
≤
Узел 5
Лист 6
>
Лист 7
Рис. 3.5. Дерево решений
Таблица 3.2
Структура входных данных алгоритма
№ объекта
Признак 1
Признак 2
…
Признак m
Целевой признак
Объект 1
Объект 2
…
Объект n
59
Данные должны быть представлены в виде табл. 3.2: в строках –
названия или номера объектов, в столбцах – признаки, по которым
происходит разбиение, последний столбец – целевой признак, содержащий метку класса, к которому принадлежит тот или иной объект.
Процесс построения дерева происходит сверху вниз, то есть является нисходящим.
При построении дерева классификации возможны три ситуации:
1. Множество X1 содержит один или более примеров, относящихся к одному классу Ci. Тогда дерево решений для X1 – это лист,
определяющий класс Ci.
2. Множество X1 не содержит ни одного примера, то есть пустое
множество. Тогда это снова лист, и класс, ассоциированный с листом, выбирается из другого множества, отличного от X1, скажем,
из множества X2, ассоциированного с родителем.
3. Множество X1 содержит примеры, относящиеся к разным
классам. В этом случае следует разбить множество X1 на некоторые
подмножества. Для этого выбирается один из признаков, имеющий
два и более отличных друг от друга значений А1, А2,... Аm. X1 разбивается на подмножества X11, X12,... X1n, где каждое подмножество
X1i содержит все примеры, имеющие значение Ai для выбранного
признака. Это процедура будет рекурсивно продолжаться до тех
пор, пока конечное множество не будет состоять из примеров, относящихся к одному и тому же классу.
Описанная процедура лежит в основе многих современных алгоритмов построения деревьев решений, этот метод известен еще под
названием разделения и захвата. Очевидно, что при использовании
данной методики, построение дерева решений будет происходит
сверху вниз.
Задача классификации, решаемая на базе дерева решений, относится к стратегии обучения с учителем, то есть все объекты тренировочного набора данных заранее отнесены к одному из предопределенных классов.
Алгоритмы конструирования деревьев решений состоят из двух
этапов:
1. Построение дерева, на этом этапе решаются вопросы выбора
критерия разбиения дерева на ветви и остановки обучения, если это
предусмотрено алгоритмом.
2. Сокращение дерева, на этом этапе решается вопрос отсечения
некоторых его ветвей.
Качество построенного дерева решения весьма зависит от правильного выбора критерия разбиения. В ходе процесса алгоритм
60
должен найти такой критерий (признак), чтобы разбить множество
на подмножества, которые бы ассоциировались с данным узлом
проверки. Каждый узел проверки должен быть помечен определенным признаком.
Существует правило выбора признака: он должен разбивать исходное множество данных таким образом, чтобы объекты подмножеств,
получаемых в результате этого разбиения, являлись представителями
одного класса или максимально приближались к такому разбиению.
Существуют различные критерии разбиения. Наиболее известные – мера энтропии и индекс Gini. Мера энтропии позволяет выбрать тот признак для разбиения, который обладает наибольшей
информативностью из имеющегося подпространства признаков.
При помощи индекса Gini признак выбирается на основании расстояний между распределениями классов.
Если дано множество Х, включающее примеры из k классов, то
индекс Gini(Х), определяется по формуле
k
Gini(X)= 1 − ∑ pi2 , (3.3)
i =1
где X – текущий узел; pi – вероятность класса i в узле X; k – количество классов.
Большое дерево не означает, что оно точно и качественно классифицирует множество объектов: чем больше частных случаев описано в дереве решений, тем меньшее количество объектов попадает в
каждый частный случай, в результате такие «ветвистые» деревья,
состоящие из неоправданно большого числа узлов и ветвей, теряют
способность к обобщению и не могут давать верные ответы.
В процессе построения дерева, чтобы его размеры не стали чрезмерно большими, используют специальные процедуры, которые позволяют создавать оптимальные по размеру деревья. Оптимальным
считается такое дерево, в котором используется информация, улучшающая качество модели и игнорируется та информация, которая
ее не улучшает.
Для построения оптимального дерева применяются две процедуры, которые используются последовательно или чередуются – это
процедура наращивания дерева до определенного размера, вторая –
процедура сокращения дерева.
Наращивание дерева происходит в соответствии с параметрами,
заданными пользователем, определение параметров может основываться на опыте и интуиции аналитика.
61
Сокращение дерева реализуется путем отсечения ветвей или использования правил остановки обучения. Например, сократить размер дерева можно ограничив глубину дерева. В этом случае построение дерева заканчивается, если достигнута заданная глубина. Еще
один вариант остановки – задание минимального количества примеров, которые будут содержаться в листьях дерева. При этом варианте ветвления продолжаются до того момента, пока все листья
дерева не будут чистыми или будут содержать не более чем заданное
число объектов.
Большинство из известных алгоритмов являются «жадными
алгоритмами». Если выбран признак, по которому произведено разбиение на подмножества, то алгоритм не может вернуться назад и
выбрать другой атрибут, который мог бы дать лучшее разбиение.
Поэтому на этапе построения нельзя заранее сказать даст ли выбранный признак, в конечном итоге, оптимальное разбиение.
В наиболее простом виде дерево решений представляет собой бинарную иерархию, в которой узлы формируют правила разбиения
множества на два подмножества по принципу «ЕСЛИ …, ТО …», а
ветви являются ответами «Да» или «Нет» на ряд вопросов, сформулированных в соответствии с правилами разбиения. В узлах бинарных деревьев ветвление может вестись только в двух направлениях,
то есть существует возможность только двух ответов на поставленный вопрос «Да» или «Нет» [16].
Бинарное дерево решений для задачи классификации электронных сообщений, которая рассмотрена в разд. 3.1, приведено на
рис. 3.6. Целью построения дерева решения для рассматриваемого
примера (рис. 3.6) является определение значения категориальной
зависимой переменной. Корень дерева: «Объем>20?», внутренние
Да
Да
Spam
Число
повторений>=5?
Объем >20?
Нет
Mail
Да
Нет
Есть ссылки?
Spam
Рис. 3.6. Дерево решений классификации
электронных сообщений
62
Нет
Mail
узлы дерева: «Число повторений > = 5?», «Есть ссылки?», листья дерева: два класса (решения) «Spam», «Mail», ветви дерева: «Да», «Нет».
Бинарные деревья являются самым простым, частным случаем
деревьев решений. В остальных случаях ответов и, соответственно, ветвей дерева, выходящих из его внутреннего узла, может быть
больше двух.
Рассмотрим еще один несложный пример, но с помощью него продемонстрируем выбор критерия разбиения по значению энтропии.
База данных, на основе которой в компании сотовой связи принимается решение о необходимости корректировки тарифных планов на основе статистических данных о текущей активности абонентов, приведена в табл. 3.3.
Для начала построения дерева необходимо выделить атрибут,
который можно поместить в корень дерева. Удобнее всего на каждом шаге построения дерева выбирать атрибут, который дает наибольшее количество информации или, другими словами, у которого
наименьшая информационная энтропия. Для оценки информационной энтропии в теории информации определена формула
n
H(x) = − ∑ p(i)log2 p(i),
i =1
где x – случайное событие с n возможными состояниями; p – вероятность выпадения состояния i.
Оценим энтропию для атрибута «Продолжительность исходящих
звонков». Определим граничное значение для разделения объектов
Таблица 3.3
Исходные данные
№
абонента
1
2
3
4
5
6
7
ПродолжиПродолжительность
тельность
исходящих
входящих
звонков
звонков
в месяц, мин в месяц, мин
180
38
215
438
12
96
584
136
26
234
327
458
114
536
Количество
отправленных
sms
35
0
16
29
0
86
18
Интернет- Наличие Приносит
трафик дополни- ли данный
в месяц, тельных
абонент
Мб
опций
прибыль
компании?
4
135
0
896
0
0
2500
да
нет
нет
да
нет
да
нет
Да
Нет
Да
Да
Нет
Нет
Да
63
на группы по данному атрибуту равным 60 мин. Данное значение
может быть определено, например, с помощью метода экспертных
оценок. Тогда по исходным данным можно сказать, что два абонента, продолжительность исходящих разговоров у которых была не
более часа, оказались не прибыльными для компании, а из абонентов, у которых продолжительность исходящих звонков превысила
60 мин, было 4 прибыльных и 1 неприбыльный (рис. 3.7).
Тогда значение энтропии для атрибута (2) – «Продолжительность
исходящих звонков» рассчитывается следующим образом:
2
2 0
0
0,
H(2)≤60 =
− log2 − log2 =
2
2 2
2
1
1 4
4
0,722,
H(2) >60 =
− log2 − log2 =
5
5 5
5
2
5
H(2) = ⋅ 0 + ⋅ 0,722 = 0,5157 áèò.
7
7
Аналогично просчитаем значения энтропии по каждому атрибуту (3) – (6) (рис. 3.8).
H(3) = 0,5157 áèò.
2
2 3
3
H(4)≤30 =
− log2 − log2 =
0,971,
2
2 5
5
1
1 1
1
H(4) >30 =
− log2 − log2 =
1,
2
2 2
2
5
2
H(4) = ⋅ 0,971 + ⋅ 1 = 0,9793 áèò.
7
7
3
3 1
1
0,8113,
H(5) = Äà =
− log2 − log2 =
4
4 4
4
1
1 2
2
0,9323,
H(5) =Íåò =
− log2 − log2 =
3
3 3
3
4
3
H(5) = ⋅ 0,8113 + ⋅ 0,9323 = 0,8632 áèò.
7
7
2
2 1
1
0,9323,
H(6) = Äà =
− log2 − log2 =
3
3 3
3
2
2 2
2
1,
H(6) =Íåò =
− log2 − log2 =
4
4 4
4
3
4
H(6) = ⋅ 0,9323 + ⋅ 1 = 0,971 áèò.
7
7
64
Для разбиения выбирается критерий с минимальным значением
энтропии, в нашем случае два варианта выбора условия для корня
дерева – это длительность исходящих звонков и длительность входящих звонков. Выберем первый. Таким образом, в корень дерева
поместим атрибут «Продолжительность исходящих звонков». Затем
нужно повторить алгоритм выбора условия для разветвления для
левого и правого поддеревьев. Исходные данные для левого и правого поддеревьев представлены в табл. 3.4 и 3.5 соответственно. Далее алгоритм рекурсивно повторяется для всех поддеревьев, пока не
дойдет до листьев, которыми являются значения результирующего
атрибута – «Приносит ли данный абонент прибыль компании».
Да
Нет
Продолжительность
исходящих >60 мин?
5
2
Рис. 3.7. Деление на группы абонентов
по продолжительности исходящих звонков
а)
Да
б)
Продолжительность
входящих >120 мин?
5
Нет
2
в)
Да
4
Да
SMS >30?
Нет
2
5
г)
Интернет-трафик есть?
Нет
3
Да
3
Дополнительные
опции есть?
Нет
4
Рис. 3.8. Деление на группы абонентов по атрибутам:
а) – продолжительность входящих звонков; б) – количество
отправленных sms; в) – интернет-трафик в месяц; г) – наличие
дополнительных опций
65
Из табл. 3.4 видно, что все объекты принадлежат к группе не
приносящих прибыль, поэтому дальнейшего разделения на поддеревья не требуется. По данным табл. 3.5 необходимо просчитать
значение информационной энтропии для выбора следующего атрибута (рис. 3.8).
Таблица 3.4
Исходные данные для поддерева
«Продолжительность исходящих звонков» ≤ 60»
№
абонента
Продолжительность входящих
звонков в месяц,
мин
1
2
26
458
КолиИнтернетчество
трафик
отправлен- в месяц,
ных sms
Мб
0
0
Наличие
дополнительных
опций
Приносит ли
данный абонент
прибыль
компании?
Нет
Нет
Нет
Нет
135
0
Таблица 3.5
Исходные данные для поддерева
«Продолжительность исходящих звонков» > 60
№
абонента
Продолжительность входящих
звонков в месяц,
мин
1
2
3
4
5
136
234
327
114
536
Да
Абонент приносит
прибыль
КолиИнтернетчество
трафик
отправлен- в месяц,
ных sms
Мб
35
16
29
86
18
Наличие
дополнительных
опций
Приносит ли
данный абонент
прибыль компании?
Да
Нет
Да
Да
Нет
Да
Да
Да
Нет
Да
4
0
896
0
2500
Продолжительность
исходящих >60 мин?
Да
Нет
Продолжительность
входящих >120 мин?
Абонент приносит
прибыль
Рис. 3.9. Дерево решений
66
Нет
Абонент не
приносит прибыль
Наименьшее значение энтропии у атрибута «Длительность входящих звонков», поэтому данный критерий выбирается для дальнейшего ветвления дерева. Исходные данные для левого и правого
поддеревьев представлены в табл. 3.6 и 3.7 соответственно.
Видно, что дальнейшего ветвления не требуется, так как все объекты из одной группы. Итак, построено следующее дерево решений
(рис. 3.9), разделяющее исходные данные на две группы – приносит
абонент прибыль или нет.
Построенное дерево должно использоваться многократно для
анализа различных вариантов.
На сегодняшний день существует значительное число алгоритмов, реализующих деревья решений, но наибольшее распространение и популярность получили следующие два:
– CART (Classification and Regression Tree) – алгоритм построения бинарного дерева решений – дихотомической классификационной модели.
– C4.5 – алгоритм построения дерева решений, у которого количество исходящих ветвей узла не ограничено.
Таблица 3.6
Исходные данные для поддерева
«Продолжительность входящих звонков» ≤ 120
№
абонента
Продолжительность входящих
звонков в месяц,
мин
1
114
КолиИнтернетчество
трафик
отправлен- в месяц,
ных sms
Мб
86
0
Наличие
дополнительных
опций
Приносит ли
данный абонент прибыль
компании?
Да
Нет
Таблица 3.7
Исходные данные для поддерева
«Продолжительность входящих звонков» > 120
№
абонента
Продолжительность входящих
звонков в месяц,
мин
1
2
3
4
136
234
327
536
КолиИнтернетчество
трафик
отправлен- в месяц,
ных sms
Мб
35
16
29
18
4
0
896
2500
Наличие
дополнительных
опций
Приносит ли
данный абонент прибыль
компании?
Да
Нет
Да
Нет
Да
Да
Да
Да
67
Ни один алгоритм построения дерева нельзя априори считать
наилучшим или совершенным, подтверждение целесообразности
использования конкретного алгоритма должно быть проверено и
подтверждено экспериментом.
Метод деревьев решений относят к «наивным» методам, но благодаря целому ряду преимуществ он является одним из наиболее
популярных для решения задач классификации [11].
Преимущества деревьев решений заключаются в следующем:
– Интуитивность деревьев решений. Классификационная модель,
представленная в виде дерева решений, является интуитивной и
упрощает понимание решаемой задачи. Результат работы алгоритмов
конструирования деревьев решений, в отличие, например, от нейронной сети, представляющей собой «черный ящик», легко интерпретируется пользователем. Дерево решений позволяет понять и объяснить, почему конкретный объект относится к тому или иному классу.
– Деревья решений дают возможность извлекать правила из
базы данных на естественном языке.
– Деревья решений позволяют создавать классификационные
модели в тех областях, где аналитику достаточно сложно формализовать знания.
– Алгоритм конструирования дерева решений не требует от
пользователя выбора входных признаков объектов. На вход алгоритма можно подавать все существующие признаки и алгоритм сам
выберет наиболее значимые среди них, которые будут использованы для построения дерева.
– Точность моделей, созданных при помощи деревьев решений,
сопоставима с другими методами построения классификационных
моделей.
– Быстрый процесс обучения. На построение классификационных моделей при помощи алгоритмов конструирования деревьев
решений требуется значительно меньше времени, чем, например,
на обучение нейронных сетей.
– Большинство алгоритмов конструирования деревьев решений
имеют возможность специальной обработки пропущенных значений.
– Многие классические статистические методы, при помощи
которых решаются задачи классификации, могут работать только с
числовыми данными, в то время как деревья решений работают и с
числовыми, и с категориальными типами данных.
Качество классификационной модели, построенной при помощи
дерева решений, характеризуется двумя основными признаками:
точностью распознавания и ошибкой.
68
Точность распознавания рассчитывается как отношение объектов, правильно классифицированных в процессе обучения, к общему количеству объектов набора данных, которые принимали участие в обучении.
Ошибка рассчитывается как отношение объектов, неправильно
классифицированных в процессе обучения, к общему количеству
объектов набора данных, которые принимали участие в обучении.
3.2.2. Линейный метод опорных векторов
Метод опорных векторов (Support Vector Machine, SVM) относится к группе граничных методов, в которой классы определяются
при помощи границ областей [1].
При помощи данного метода решаются задачи бинарной классификации.
В основе метода лежит понятие плоскостей решений. Плоскость
разделяет объекты с разной классовой принадлежностью: объекты
двух типов (рис. 3.10). Разделяющая линия задает границу, справа от
которой находятся объекты типа «квадратный», а слева – типа «круглый». Новый объект, попадающий направо, классифицируется как
объект класса «круглый» или как объект класса «квадратный», если
он расположился по левую сторону от разделяющей прямой. В этом
случае каждый объект характеризуется двумя измерениями.
Цель метода опорных векторов состоит в том, чтобы найти плоскость, разделяющую два множества объектов. Метод отыскивает
Опорные
вектора
Опорные
вектора
Опорные
вектора
Плоскость
Поле
Рис. 3.10. Разделение классов прямой линией
69
объекты, находящиеся на границах между двумя классами, то есть
опорные векторы.
Опорными векторами называются объекты множества, лежащие на границах областей. На рис. 3.10 показано шесть векторов,
которые являются опорными для данного множества объектов.
Классификация считается хорошей, если область между границами, которая называется поле, пуста и чем она шире, тем классификация четче.
Решение задачи бинарной классификации при помощи метода
опорных векторов заключается в поиске некоторой линейной функции, которая правильно разделяет набор данных на два класса.
Таким образом, задачу можно сформулировать как поиск функции f(x), принимающей значения меньше нуля для векторов одного
класса и больше нуля для векторов другого класса.
Для поиска функции f(x) используется тренировочный набор
векторов пространства, для которых известна их принадлежность
к одному из классов. Тренировочный набор задается как исходные
данные. Плоскость определена линейным уравнение f(x) = ax + b.
Решение данной задачи показано на рис. 3.11. Функция принимает
значения меньше нуля для векторов одного класса и больше нуля
для векторов другого класса. Для каждого нового объекта отрицательное или положительное значение определяет принадлежность
объекта к одному из классов.
Наилучшей функцией классификации f(x) будет та, для которой
ожидаемый уровень ошибки классификации минимален.
Напрямую оценить ожидаемый уровень ошибки построенной
модели невозможно, это можно сделать при помощи понятия эмпи-
ax + b = −1
ax + b = 1
Рис. 3.11. Линейный метод опорных векторов
70
рического риска. Эмпирический риск – это уровень ошибки классификации, который оценивается на тренировочном наборе данных.
Таким образом, в результате решения задачи методом опорных
векторов для линейно разделяемых данных может быть получена
функция классификации, которая минимизирует верхнюю оценку
ожидаемого риска.
Одна из проблем, связанная с применением метода опорных векторов для решения задач классификации, заключается в том, что
не всегда можно легко найти линейную границу между двумя классами.
Одним из выходов является перенос данных из плоскости в трехмерное пространство, где возможно построить такую плоскость,
которая идеально разделит множество образцов на два класса размерности. Опорными векторами будут объекты из обоих классов,
являющиеся экстремальными. Таким образом, при помощи добавления дополнительных размерностей могут быть найдены границы
между классами в виде гиперплоскостей.
В то же время, сложность построения модели опорных векторов
заключается в том, что чем выше размерность пространства, тем
сложнее с ним работать. Тогда приходится предварительно применять какой-либо метод понижения размерности данных для выявления наиболее существенных компонент, а затем использовать
метод опорных векторов.
Как и любой другой метод, метод опорных векторов имеет свои
сильные и слабые стороны, которые следует учитывать при выборе
данного метода.
Недостаток метода состоит в том, что для классификации используется не все множество образцов, а лишь их небольшая часть,
которая находится на границах, что может приводить к недостаточному качеству решения задачи классификации.
Достоинство метода состоит в том, что для классификации методом опорных векторов, в отличие от большинства других методов,
достаточно небольшого набора данных. При правильной работе модели, построенной на тестовом множестве, вполне возможно применение данного метода на реальных данных.
Рассмотрим задачу биометрической аутентификации, которая
решена методом опорных векторов.
Последовательность решения этой задачи включает следующие
этапы:
– бинаризация изображения, т. е. кодирование каждого пикселя
как 1 или 0 в зависимости от значений его компонент RGB;
71
– построение «скелета» отпечатка на основе полученной бинарной последовательности;
– выделение конечных точек и точек ветвления – создание опорных векторов;
– удаление шумов – близко стоящих конечных точек и точек ветвления;
– принятие решения на основе сравнения опорных векторов гиперплоскости эталонного и сканированного изображений.
Результат решения данной задачи – коэффициент совпадения
сканированного отпечатка и отпечатка из базы эталонных данных,
что позволяет классифицировать (распознать/не распознать) человека и таким образом разрешить ему доступ к системе или заблокировать его.
Реализованное приложение работает с графическими изображениями. В интерфейсном окне визуализируются два изображения –
эталонное и сканированное с сопоставлением конечных точек и точек ветвления, внизу окна – значение коэффициента совпадения, в
процентах (рис. 3.12).
Приложение разработано на языке программирования Python.
При запуске приложения в стартовом окне (рис. 3.13) пользователю предоставляется выбрать эталонное зашифрованное изображение и сканированное. Ключ требуется для дешифровки эталонного
изображения. Также можно зашифровать изображение отпечатка
Рис. 3.12. Пример результата сопоставления
72
Рис. 3.13. Стартовое окно приложения
Рис. 3.14. Пример визуализации сопоставления
пальца для защищенного хранения с помощью алгоритма шифрования AES по введенному ключу.
Коэффициент совпадения вычисляется как отношение количества совпавших опорных векторов на двух изображениях к общему
количеству опорных векторов. Пример, где сравниваются два разных отпечатка пальцев и не совпавшие опорные векторы выделены
красным цветом, показан на рис. 3.14.
На основе величины коэффициента совпадения решается задача
бинарной классификации: человек «распознан» или «не распознан».
73
3.2.3. Метод «ближайшего соседа»
Метод «ближайшего соседа» относится к классу методов, работа которых основывается на сравнении данных, характеризующих
объекты, которые хранятся в памяти (ретроспективные данные), с
данными нового объекта [2]. При появлении нового объекта находятся отклонения между этим объектом и подобными ему сохраненными объектами, и наиболее подобный объект идентифицируется
как ближайший сосед. Новый объект будет приписан тому же классу, что и ближайший сосед.
Метод «ближайшего соседа» может быть распространен на k ближайших соседей. В этом случае выбирается k ближайших соседей
для их рассмотрения в качестве множества ближайших объектов.
Поскольку не всегда удобно хранить все ретроспективные данные,
то метод «k-ближайшего соседа» предлагает хранить только множество типичных случаев. В таком случае используемый метод называют рассуждением по аналогии или рассуждением по прецедентам.
Прецедент – это описание типичной ситуации в сочетании с действиями, предпринимаемыми в данной ситуации. Таким образом,
вывод, основанный на прецедентах, представляет собой такой метод анализа данных, который делает заключения относительно
данной ситуации по результатам поиска аналогий, хранящихся в
базе прецедентов.
Рассмотрим пример решения задачи классификации методом
«k-ближайшего соседа» (рис. 3.15). Пусть известные объекты отмечены классом «квадратный» или «круглый», а новый объект, который требуется классифицировать, обозначен шестиугольником.
Требуется оценить наиболее вероятную классификацию нового
объекта с использованием специально выбранного числа их ближайших соседей.
Для начала рассмотрим случай, когда k = 1. В этом случае новый
объект будет классифицирован как «квадратный», так как ближайший сосед имеет метку «квадратный».
Увеличим число используемых ближайших соседей k = 2. Таким
образом увеличена окрестность нового объекта, граница которой на
рис. 3.15 показана окружностью. На этот раз метод «k-ближайших
соседей» не сможет классифицировать новый объект, поскольку
второй ближайший объект имеет метку «круглый» и количество
объектов, принадлежащих двум классам равноценны.
Далее увеличим окрестность нового объекта до k = 9. Поскольку в окрестности содержатся 6 объектов с меткой «квадратный» и
74
Рис. 3.15. Классификация объектов множества
при разном значении параметра k
3 объекта с меткой «круглый», алгоритм «k-ближайших соседей»
присвоит метку класса «квадратный» новому объекту.
Метод «ближайшего соседа», равно как и «k-ближайшего соседа», относится к категории методов «обучение без учителя», то есть
является самообучающимся. Рабочие характеристики базы прецедентов с течением времени и накоплением примеров улучшаются.
Однако это не означает, что метод автоматически, как в случае «деревьев решений», классифицирует объекты. Последнее остается за
аналитиком, данный метод лишь предлагает возможные варианты
классификации и указывает на наиболее типичный с точки зрения
ближайших объектов.
Преимущества метода «ближайшего соседа»:
– простота использования полученных результатов;
– решения не уникальны для конкретной ситуации, возможно
их использование для других случаев;
– целью классификации является не гарантированно верная
классификация, а лучший вариант из возможных.
Недостатки метода «ближайшего соседа» [1]:
– метод не создает каких-либо моделей, обобщающих предыдущий опыт, в выборе решения метод основывается на всем массиве
доступных ретроспективных данных, поэтому невозможно сказать,
на каком основании строятся ответы;
75
– существует сложность выбора метрики, от которой главным
образом зависит объем множества записей, которые нужно хранить
в памяти для достижения удовлетворительной классификации;
– при использовании метода возникает необходимость полного
перебора прецедентов, вследствие чего возникает вычислительная
трудоемкость;
– типичными задачами метода являются задачи небольшой размерности по количеству классов и объектов.
76
4. НЕЙРОННЫЕ СЕТИ, КАК ИНСТРУМЕНТ
АНАЛИЗА ДАННЫХ
Перспективным инструментом решения задач анализа данных
являются нейронные сети.
Метод нейронных сетей используется для классификации, кластеризации, прогнозирования и распознавания образов.
Одно из главных преимуществ нейронных сетей состоит в том,
что они, по крайней мере, теоретически могут аппроксимировать
любую непрерывную функцию, что позволяет исследователю не
принимать заранее какие-либо гипотезы относительно модели.
К существенным недостаткам нейронных сетей можно отнести тот
факт, что окончательное решение зависит от начальных установок
сети и его практически невозможно интерпретировать в традиционных аналитических терминах.
4.1. Элементы и характеристики нейронной сети
Составляющими элементами нейронной сети являются [17]:
Нейрон – вычислительная единица, которая получает информацию, производит над ней простое вычисление и передает дальше.
Синапсы – однонаправленные входные связи, которые соединены с выходами других нейронов, характеризуются весом.
Текущее состояние нейрона определяется как взвешенная сумма
всех его входов.
Аксон – это выходная связь нейрона, по ней сигнал поступает
прямо на синапсы последующих нейронов.
Общий вид нейрона приведен на рис. 4.1.
Входы
x1
x2
.
.
.
Синапсы
w1
w2
.
.
.
wn
xn
Ядро
нейрона
F(S)
S=
n
Аксон
Выход
Y
Y = F (S)
∑ xiwi
i =1
Рис. 4.1. Математическая модель нейрона
77
На рис. 4.1: X – вектор чисел, которые поступили на вход нейрона; xi , i = 1,n – значение i-го входного параметра; W – вектор весов,
то есть такие числовые значения, которые будут меняться в процессе обучения нейросети; wi , i = 1,n – значение i-го веса входного параметра; S (сумматор) – это такой функциональный блок нейрона,
который будет складывать все входные параметры, то есть числа поступившие на вход нейрона, которые умножаются на соответствующие им веса; F – функция активации нейрона, определяющая
зависимость значения выхода нейрона от того значения, которое
пришло на сумматор S; Y – значение выхода нейрона, которое будет
означать функцию его состояния: Y = F(S).
В том случае, когда нейронная сеть состоит из большого количества нейронов, вводят термин – слой. Соответственно есть входной
слой, который получает информацию; n скрытых слоев, которые ее
обрабатывают, и выходной слой, который выводит результат работы нейронной сети.
Нейроны оперируют с числами в диапазоне [0, 1] или [–1, 1].
Синапс – связь между двумя нейронами. У синапса есть один параметр – это вес. Благодаря весу входная информация изменяется,
когда передается от одного нейрона к другому.
Функция активации – способ нормализации входных данных,
то есть если на входе нейрона будет большое число х, то функция
активации f(х) нормализует его, и на выходе будут значения в нужном диапазоне.
Каждая нейронная сеть имеет свою функцию активации. В основном в нейронных сетях используются три функции активации:
линейная, сигмоидальная, гиперболический тангенс (рис. 4.2).
Нейрон смещения – не обязательный элемент нейронной сети,
однако используемый в большинстве нейросетей. Нейроны данного
типа имеют две особенности:
1. Вход и выход нейрона всегда равняются 1.
2. Нейрон никогда не имеет входных синапсов.
Нейроны смещения могут присутствовать либо по одному на слое
или полностью отсутствовать. Соединения у нейронов смещения такие же, как у обычных нейронов – со всеми нейронами следующего
уровня, за исключением того, что синапсов между двумя нейронами смещения быть не может. Расположение нейрона смещения показано на рис. 4.3.
Нейрон смещения нужен для того, чтобы иметь возможность получать выходной результат путем сдвига графика функции активации вправо или влево. Также нейроны смещения помогают в слу78
а)
F (x) = x
б)
F (x) =
10
1
1 + e− x
–10
–10
1
0
10
в)
F (x) =
1
1 + e− x
–10
1
0
10
–1
Рис. 4.2. Функции активации: а – линейная; б – сигмоидальная;
в – гиперболический тангенс
I1
H1
I2
H2
O1
B1
B2
B3
Рис. 4.3. Расположение нейрона смещения: I – входной нейрон;
H – скрытый нейрон; O – выходной нейрон; B – нейрон смещения
79
чае, когда все входные нейроны получают на вход 0, и независимо
от весов передадут 0 на последующие слои.
Тренировочный сет – последовательность данных, которыми
оперирует нейронная сеть.
Итерация – своеобразный счетчик, который увеличивается после каждого тренировочного сета, другими словами – общее количество тренировочных сетов, пройденных нейронной сетью.
Эпоха – параметр, который устанавливается вручную и влияет
на качество обучения нейронной сети. При инициализации нейронной сети эта величина устанавливается в ноль. Чем больше эпох,
тем лучше натренирована нейронная сеть. Последовательность инкремента эпох и итераций следующая – сначала в n раз увеличивается итерация, а потом эпоха.
Ошибка – это процентная величина, которая отражает расхождение между ожидаемым и полученным ответами. Ошибка формируется в каждую эпоху и должна снижаться. Если этого не происходит, то это означает, что процесс обучения неверен.
Ошибку можно вычислять разными путями:
а) средняя квадратичная ошибка:
n
2
ij − aj
∑
j =1
,
MSE =
(4.1)
n
(
)
где n – количество эпох; ij – ожидаемый ответ; aj – получаемый ответ;
б) корень средней квадратичной ошибки:
n
MSE =
∑ ( ij − aj )
2
j =1
n
;
(4.2)
в) арктангенс
n
MSE =
∑ arctan2 ( ij − aj )
j =1
n
.
(4.3)
Архитектура нейронной сети – способ объединения нейронов.
Архитектура нейронной сети может быть разделена на три типа:
1) сети прямого распространения (backpropagation): одна из наиболее распространенных архитектур, в основном используется в таких областях, как прогнозирование и распознавание образов;
80
2) сети с обратной связью: такие, как дискретная модель Хопфилда, в основном используется для оптимизации вычислений и
ассоциативной памяти;
3) самоорганизующиеся сети: включают модели адаптивной резонансной теории (ART) и модели Кохонена, в основном используются для кластерного анализа.
Выбор архитектуры нейронной сети возможен через экспериментальный подбор параметров. В зависимости от цели задачи анализа
данных подбирается количество нейронов в слоях.
Обучение нейронной сети – это процесс настройки весов нейронной сети, при которых ошибка минимальна.
Современные алгоритмы обучение можно разделить на обучение
с учителем и обучение без учителя [18].
Для реализации первого алгоритма сети предоставляются входные и выходные значения, соответствующие друг другу; а она по некоторому алгоритму подберет весовые коэффициенты. Перед началом обучения синопсические связи инициализируются случайными
значениями в заданном диапазоне. Одна итерация обучения состоит из прямого и обратного прохода. В первом случае сеть работает в
обычном режиме, определяя выходные значения. Далее с помощью
выходных значений, заданных «учителем», определяется величина
ошибки, которая распространяется уже в обратном направлении.
Для реализации второго алгоритма сети предъявляются только
входные параметры, а выходные формируются самостоятельно с учетом входных и производных сигналов. Сеть должна подстраивать весовые коэффициенты таким образом, чтобы при поступлении на вход
близких входных значений система выдавала одинаковые выходы.
Алгоритм обучения с учителем является менее правдоподобным и
даже критикуется из-за этого некоторыми учеными, однако он способен лучше обучить сеть определять требуемые последовательности.
Одним же из наиболее применяемых методов обучения является алгоритм обратного распространения ошибки. Применяется он
только для полносвязных нейронных сетей. Это сети, в которых
каждый из нейронов одного слоя связан со всеми нейронами следующего и предыдущего слоев.
Скорость обучения – гиперпараметр нейронной сети, устанавливающий пороговое значение, при достижении которого нейронная
сеть закончит обучение.
От скорости обучения зависит возможность нейронной сети верно подобрать весовые коэффициенты. Слишком маленькое значение
данного гиперпараметра может привести к тому, что сеть не сможет
81
подобрать подходящие веса. Слишком большое – может привести к
тому, что сеть перескочит этот самый идеальный вес и продолжит
обучаться с увеличением ошибки.
Момент обучения – коэффициент значения веса матрицы связи
на предыдущей итерации.
4.2. Нейронные сети прямого распространения
В настоящее время при анализе данных в основном используются нейронные сети прямого распространения.
4.2.1. Архитектура нейронной сети
прямого распространения
Самой простой архитектурой сети прямого распространения является персептрон.
Персептрон состоит из единственного слоя, как это показано на
рис. 4.4 [17].
В области анализа данных персептрон используется для решения задачи классификации: на вход подаются независимые переменные (параметры), на выходе активизируется yi, соответствующий i-му классу.
Входной слой
Выходной слой
x1
y1
y2
x2
y3
x3
.
.
.
y4
.
.
.
xn
ys
H
Рис. 4.4. Архитектура персептрона
I
82
O
Многослойный персептрон – это нейронная сеть, состоящая из
слоев, каждый из которых состоит из определенного количества
нейронов.
Нейроны в соответствии с принадлежностью к тому или иному
слою делятся на три основных класса: входные I, скрытые H и выходные O нейроны.
Характеристики многослойного персептрона:
Выходной слой количества слоев.
Входной
слой
– Нейронная
сеть
состоит из произвольного
– Нейроны
предыдущеx1 каждого слоя соединяются с нейронами
y1
го слоя и последующего слоев по правилу «каждый с каждым».
– Количество нейронов в слоях может быть любым.
y2
Многослойным
этот тип персептронов называется
не потому, что
x2
состоит из нескольких слоев, ведь входной и выходной слои можно
вообще не оформлять в коде, а потому, что содержит несколько обy3
x3
учаемых скрытых
слоев.
Для входного слоя
исходные данные подаются с консоли, для
.
остальных на вход .каждого нейрона подаетсяy4суммарное значение с
выходов нейронов предыдущего слоя, после чего она нормализуется
.
.
с помощью функции активации, и попадает
на выход.
.
. приведен на рис. 4.5. При неПримерxдвухслойного персептрона
n
обходимости использования сетей более сложной структуры добавляются новые скрытые слои или наращивается
количество нейроys
нов в скрытых слоях.
H
I
O
Рис. 4.5. Архитектура нейронной сети
83
Многослойный персептрон эффективен при решении тех же самых задач, что и однослойный персептрон, но обладает значительно
большей вычислительной способностью в сравнении с однослойным
персептроном. Благодаря этой своей способности нейронная сеть
типа многослойный персептрон может гораздо точнее описывать
многомерные зависимости с большой степенью нелинейности и высоким уровнем перекрестного и группового влияния входных переменных на выходные.
Выбор архитектуры нейронный сети заключается в подборе гиперпараметров. Гиперпараметрами являются такие величины, как:
– количество нейронов во входном и выходном слоях,
– количество скрытых слоев,
– количество нейронов в каждом из скрытых слоев,
– скорость обучения сети,
– момент обучения сети,
– количество эпох, в течение которых сеть будет проходить обучение.
Каждый из этих параметров влияет на определенные характеристики, как обучения, так и работы сети.
Нейронная сеть с большим количеством нейронов в выходном
слое будет способна более точно классифицировать то или иное входное значение, так как у нее будет больший выбор к какому классу
отнести полученные на вход данные [19].
Количество же нейронов во входном слое также влияет на увеличение вероятности правильного решения задачи. Чем больше сеть
знает об объекте, тем с большей вероятностью она сможет его правильно классифицировать.
Количество скрытых слоев влияет на более точную классификацию объекта. Здесь можно провести аналогию с работой головного
мозга. Чем дольше человек изучает объект, тем больше областей
его головного мозга задействуются для более точного описания,
следовательно, и классификации. Если переводить на язык обучения нейронной сети, то это будет звучать следующим образом: чем
больше нейронов будет задействовано в момент классификации, тем
больше вероятность верного решения.
Однако существуют разумные ограничения. Для большинства
задач, решаемых с помощью многослойных персептронов, выбор
структуры нейронной сети должен осуществляться на основе следующего правила: количество настраиваемых в процессе обучения весовых коэффициентов должно быть в 2–5 раз меньше, чем количество примеров обучающей выборки. Если это соотношение меньше
84
2, сеть теряет способность к обобщению обучающей информации,
а при достижении 1 и меньше просто запоминает ответы для каждого обучающего примера. Если же количество обучающих примеров слишком велико для выбранной структуры сети, нейросетевая
модель во многих случаях просто усредняет выходные значения
для различных комбинаций входных векторов, теряя способность
к корректному отклику в отдельных частных случаях и повышая
величину максимальной выборочной ошибки.
Кроме того, при выборе структуры многослойного персептрона
следует задавать количество нейронов в скрытом слое, предшествующем выходному слою, не меньшим, чем количество самих выходов. Например, для классификации объектов на два класса, при наличии трех входов, архитектура сети из 3–5 скрытых слоев по 7–10
нейронов в каждом будет слишком громоздкой и долгоработающей.
Задача обучения многослойных персептронов может быть сформулирована как оптимизационная, в которой целевой функцией
(критерием оптимизации) является общая ошибка, рассчитанная
по обучающей выборке. Соответственно, и решать данную задачу
можно как любую задачу многомерной оптимизации с использованием методов детерминированного, градиентного или стохастического поиска.
Наиболее распространенный метод обучения многослойного персептрона – метод обратного распространения ошибки. 4.2.2. Обучение нейронной сети
и выбор архитектуры
Обучение или тренировка нейронной сети выполняется на некотором тестовом множестве «вход-выход», где при известном множестве входных значений известно множество выходных значений.
Такой процесс обучения называется «обучение с учителем». Очевидно, что чем больше тестовых примеров для обучения, тем лучше
обучена нейронная сеть [20].
Процесс обучения нейронной сети представляет собой итерационный процесс, при котором на каждой итерации на вход нейронной
сети подаются данные, которые, проходя сквозь ее слои, преобразуются в выходные значения. Целью обучения является настройка
весовых коэффициентов нейронной сети таким образом, чтобы разница между выходным истинным результатом тестового множества
и реально получаемым результатом была не больше допустимого
значения. Корректировка весов осуществляется постепенно от ите85
рации к итерации. Допустимое значение определяет качество нейронной сети и устанавливается заранее перед процессом обучения.
Одним из вариантов корректировки весовых коэффициентов является дельта-правило.
Дельта-правило определяет ошибку δ следующим образом:
δ = i-a,
(4.4)
где i – ожидаемый, т. е. истинный вывод нейронной сети; a – реальный вывод нейронной сети.
Помимо нейронов выходного слоя ошибки определяют и для нейронов скрытых слоев. Дельта – правило для скрытых слоев выглядит следующим образом:
∆wik = αδkxi,
(4.5)
где α – норма обучения – задается перед началом обучения; xi – значение (уровень) сигнала, приходящий от i-го нейрона к k-му; δk –
ошибка k-го нейрона.
Одним из распространенных алгоритмов обучения является обратное распространение ошибки.
В соответствии с этим алгоритмом существует два потока – входные
сигналы, распространяясь от входа к выходу, образуют прямой поток,
в результате чего получается величина ошибки. Величина ошибки
распространяется в обратном направлении, в результате происходит
корректировка весовых коэффициентов связей нейронной сети.
Алгоритм обучения состоит из следующих шагов:
Шаг 1. Инициализация случайных значений весов нейронной сети.
Шаг 2. Запись тренировочного сета на вход нейронной сети.
Шаг 3. Запуск нейронной сети в режиме прямого прохода и запись полученной выходной последовательности.
Шаг 4. Определение ошибки отклонения (дельта) выходного слоя:
δâûõ =
(4.7)
( i − a ) F ′ ( x ), где i –целевые значения выходного слоя; a – полученные значения
выходного слоя; F ′ ( x ) – производная функции активации.
Шаг 5. Определение дельты всех скрытых слоев:
n
=
δñêð F ′ ( x ) ∑ wi δi , (4.8)
i =1
где wi – исходящий вес связи; δi – дельта слоя, связанного при помощи первого параметра.
86
Шаг 6. Расчет градиента (j + 1) слоя:
j
F j +1 = δ j +1ij , (4.9)
где δj + 1 – дельта (j + 1) слоя, для которого веса связи являются входными; ij – значения j-го слоя, для которого веса связи являются выходными.
Шаг 7. Корректировка веса:
∆=
wi Efw + ϕ∆wi −1, (4.10)
где E – скорость обучения; fw – градиент веса w; ϕ – момент обучения; ∆wi–1 – значение, на которое изменился вес на предыдущей
итерации.
Шаг 8. Обновление веса:
=
wi wi −1 + ∆wi . (4.11)
Шаг 9. Повторение шагов 2–9, пока сеть не обучится распознавать вещества по запаху с допустимым уровнем среднеквадратичной ошибки MSE:
n
∑ ( ij − aj )
MSE =
2
j =1
n
,
(4.12)
где n – количество итераций (эпох) обучения; ij – ожидаемый ответ.
Для нейронной сети, решающей задачу классификации, применяется метод «обучение с учителем». Данный метод построен на
основе наличия двух выборок одного размера: входных и выходных
данных. Пары выборок поочерёдно предоставляются сети, как бы
показывая ей, что если на вход подаётся одна последовательность,
то на выходе должна быть соответствующая ей.
В качестве же метода обучения будет выбран самый популярный – метод обратного распространения ошибки, использующий
градиентный спуск.
Градиентным спуском называется способ определения локального минимума и максимума функции при помощи движения вдоль
градиента, как показано на рис. 4.6.
На рис. 4.6 видно, что глобальным минимумом является точка
(w2,δ2), следовательно, при весе нейрона, равного w2, ошибка на
выходе нейронной сети будет минимальной. Однако градиентный
спуск также имеет и локальные минимумы. Если функция будет
87
δ
F’(w)
δ1
δ2
w2
w1
w
Рис. 4.6. Градиентный спуск: Обозначения: w – вес нейрона;
δ – ошибка, соответствующая весу w; F’(w) – градиент
δ
δ
Без момента
δ
Слишком малое
значение момента
F’(w)
F’(w)
w
w
Правильное значение
δ
момента
Слишком большое
значение момента
F’(w)
F’(w)
w
w
Рис. 4.7. График градиентного спуска
с разным моментом обучения
иметь слишком маленькую скорость обучения, то не сможет его
преодолеть (рис. 4.7).
Градиент – вектор, определяющий крутизну склона и указывающий его направление относительно какой-либо из точек на поверх88
ности или графике. Для нахождения градиента необходимо взять
производную от графика по данной точке для уменьшения ошибки.
Как было сказано ранее, главным методом обучения сети является метод обратного распространения ошибки. Он получил такое
название, потому что имеет два варианта работы: прямой проход
и обратный. Во время прямого прохода сеть работает в стандартном режиме (от входного слоя к выходному), а во время обратного прохода отправляет значения ошибки, наоборот (от выходного
к входному).
Для сети прямого распространения несмотря на ее простую и понятную архитектуру часто встречающаяся проблема – это медленное обучение, сеть может попасть в локальный минимум, и тогда
трудно определить параметры обучения.
4.2.3. Решение одной задачи классификации
на основе сети прямого распространения
Рассмотрим задачу распознавания угроз по запаху, где задача
классификации запахов решена с помощью нейронной сети.
Существующие технологические решения обнаружения угроз
террористического характера по запаху, например, детектор пороха в аэропорту или система «электронный нос» представляют собой
портативные приборы локального назначения. В 2017 г. моими студентами И. Н. Дзюбенко, И. А. Потаповым была предложена технология построения системы детектирования веществ по запаху,
основанная на концепции Интернета вещей (Internet of Things, IoT)
и реализован ее действующий макет.
На концептуальном уровне система детектирования представляет собой разновидность беспроводной сенсорной сети с топологией
типа «звезда» [21] и состоит из следующих типов узлов: сенсорный
узел (СУ), шлюз, центральный узел (рис. 4.8).
Сенсорное устройство представляет собой прибор передачи, к которому подключен один или несколько датчиков газа, позволяющих обнаруживать различные угрозы. Шлюз – это узел, выполняющий функции агрегации данных, поступающих от множества СУ,
с последующей их передачей на центральный узел и обеспечения
связи между узлами системы. Взаимодействие между сенсорными
узлами и шлюзом осуществляется по технологии Bluetooth, между
шлюзом и центральным узлом – по Wi-Fi, соответственно шлюз должен поддерживать обе технологии. Центральный узел – это узел,
выполняющий функции сервера, представляет собой программное
89
СУ
Центральный
узел
Шлюз
– устройство передачи
– датчики
Облачные
вычисления
– беспроводная связь
– проводная связь
Рис. 4.8. Узлы системы детектирования
обеспечение на компьютере, реализующее доступ к веб-интерфейсу
для оператора системы детектирования.
Предлагаемая система детектирования реализована в виде макета на платформе Genuino 101 и является цепью из сенсорного, агрегирующего и центрального устройств. Набор датчиков представлен
полупроводниковыми датчиками серии MQ производства Winsen
Electronics Technology Co Ltd:
датчик MQ-3 реагирует на пары спирта, что позволяет детектировать такие угрозы как, например, утечка бензола на предприятии
(бензол – крайне опасное летучее вещество, сильный канцероген и
при больших концентрациях в воздухе взрывоопасен);
датчик MQ-5 реагирует на природный газ (бутан, метан, пропан);
датчик MQ-7 реагирует на монооксид углерода (угарный газ) и
водород, что позволяет обнаруживать возгорания на ранней стадии.
Программное обеспечение для СУ написано средствами Arduino
IDE. Данные с датчиков собираются в аналоговом виде и представлены как числа от 0 до 1024. Передача данных происходит через
Bluetooth low energy с помощью библиотеки Genuino 101 CurieBLE.
Аппаратная реализация шлюза выполнена на платформе Intel
Edison, поддерживающей технологии Bluetooth low energy и Wi-Fi,
а программная – средствами программной платформы Node.js.
Центральное устройство реализовано как локальный сервер на
компьютере средствами программной платформы Node.js. Кроме
обработки поступающих данных сервер также обеспечивает работу простого веб-приложения оператора системы детектирования.
Основная функция сервера – распознать запах, представляющий
опасность.
90
Распознавание выполняет нейронная сеть, реализованная как
приложение сервера. Измерение концентрации вещества в воздухе
реализуется изменением отношения Rs/Ro показаний датчика, где
Rs – сопротивление датчика при определении им концентрации газа
в окружающей среде; Ro – сопротивление датчика, измеренное при
определенной концентрации детектируемого газа. Далее сигнал поступает на аналогово-цифровой преобразователь и подается на блок
регистрации, где формируется входной вектор нейронной сети.
Тип нейронной сети – многослойный персептрон. Количество
слоев и нейронов в каждом слое определяется экспериментальным
путем.
Функция активации F(x) нейрона – сигмоидальная:
1
F (x) =
,
1 + e−αx
где x – значение сигнала, приходящего на вход нейрона; α – коэффициент, задающий угол наклона функции. Входами нейронной
сети будут данные, поступающие от сенсорных устройств. Длина
выходной последовательности равна количеству запахов, которые
должна распознавать сеть, плюс один вектор для неизвестного системе запаха.
Алгоритм обучения нейронной сети – обучение с учителем.
Процесс обучения состоит из предъявления на вход нейронной
сети тренировочных сетов, представляющих собой образцы запахов.
Выбор архитектуры нейронной сети заключается в подборе гиперпараметров, таких как:
– количество нейронов во входном I и выходном O слоях,
– количество скрытых слоев H,
– количество нейронов в каждом из скрытых слоев,
– скорость обучения сети,
– момент обучения сети,
– количество эпох, в течение которых сеть будет проходить обучение.
По результатам экспериментов, представленных далее, была построена нейронная сеть со следующей архитектурой: 9 нейронов во
входном слое I, одного скрытого слоя H, включающего в себя 12 нейронов, 4 нейрона в выходном слое O. Согласно результатам экспериментов нейронная сеть с такой архитектурой показала наименьшее
значение MSE из других возможных.
Первая серия экспериментов проводилась с целью подбора значения скорости и момента обучения нейронной сети. В экспериментах
91
участвовали нейронные сети со всеми комбинациями следующих
гиперпараметров:
– количество нейронов во входном слое: {3, 5, 7, 9};
– количество нейронов в выходном слое: {2, 3, 4};
– количество скрытых слоев: 1;
– количество нейронов в скрытом слое: {4, 6, 8, 10, 12, 14};
– скорости обучения: {10–5, 10–4, 10–3, 0.01, 0.05, 0.1, 0.15, 0.5,
0.75};
– моменты обучения: {10–7, 10–6, 10–5, 10–4, 10–3, 0.01, 0.05, 0.1,
0.15, 0.5, 0.75};
– количество эпох: 100 000;
– нейроны смещения присутствуют.
График тенденции изменения MSE от момента обучения ϕ
(рис. 4.9), показывает, что наименьшее конечное MSE получается для ϕ = 0,75, однако разница между конечным и минимальным
MSE гораздо выше, чем у ϕ = 0,5. Это свидетельствует о том, что при
ϕ = 0,75 функция попала в локальный минимум. Таким образом,
лучшим результатом является ϕ = 0,5. Оно же будет являться коэффициентом корректировки весов на предыдущей итерации.
Диаграмма зависимости среднего значения MSE от скорости обучения E (рис. 4.10), показывает, что при E = 10–5 сеть имеет наибольшее значение MSE и наибольшую разницу между средним и
конечным значением MSE. Это может свидетельствовать о том, что
за заданное количество эпох сеть не успела обучиться. В диапазоне
скорости обучения от 0,5 до 0,75 видно, что нейронная сеть дошла до
одного из множества локальных минимумов, однако не смогла обучиться, так как из-за высокой скорости не смогла подобрать веса.
MSE
0,226
0,224
0,222
0,22
Конечное MSE
Минимальное MSE
Среднее MSE
0,218
0,216
0,214
0,212
0,21
1,00E-07
1,00E-05
0,001
0,05
0,15
0,75
ϕ
Рис. 4.9. Диаграмма зависимости среднего значения
среднеквадратичной ошибки от момента обучения
MSE
0,245
92
0,24
0,235
0,23
Конечное MSE
Минимальное MSE
Cреднее MSE
1,00E-07
1,00E-05
0,001
0,05
0,15
0,75
ϕ
MSE
0,245
0,24
Конечное MSE
Минимальное MSE
Cреднее MSE
0,235
MSE
0,23
0,226
0,224
0,225
0,222
0,22
0,22
0,215
0,218
0,00001 0,0001 0,001 0,01 0,05
0,216
0,1
0,15
0,5
Конечное MSE
0,75 EМинимальное MSE
Среднее MSE
0,214 Рис. 4.10. Диаграмма зависимости среднего значения MSE
MSE
0,212
от скорости обучения
0,2205
0,21
ϕ
0,22
1,00E-07 1,00E-05
0,001
0,05
0,15
0,75
Результаты эксперимента показали, что наилучшим выбором для
0,2195
скорости обучения являются значения 0,001 – 0,05.
Конечное
MSE
0,219
Целью второй серии экспериментов было подобрать
количество
Минимальное MSE
MSE
0,2185
скрытых
слоев, количество нейронов в скрытых и входном
слоях.
Cреднее MSE
0,245
Диаграмма
зависимости
среднего
значения
MSE
от
количества
0,218
0,24
скрытых
слоев (рис. 4.11) показывает, что в среднем конечная MSE
0,2175
Конечное MSE
оказалась
ниже, чем у нейронов с большим количеством
слоев,MSE
од0,235
Минимальное
0,217разница между минимальным и конечным достаточно велика,
нако
Cреднее
MSE
0,23
1
2
3
H
чтобы сказать, что сеть близка к обучению. При сравнении графиков
0,225
двух и трех скрытых слоев видно, что разница приблизительно оди0,22
накова,
что свидетельствует о том, что данная архитектура меньше
0,215
подвержена
попаданиям в локальные минимумы. Лучшим варианMSE0,00001 0,0001 0,001 0,01 0,05 0,1 0,15 0,5 0,75 E
том
в
конкретном
эксперименте будет сеть с одним скрытым слоем.
0,226
0,225
MSE
0,224
0,2205
0,223
0,22
0,222
0,2195
0,221
0,219
0,22
Конечное MSE
Минимальное MSE
Cреднее MSE
0,219
0,2185
3
0,218
5
7
Конечное MSE
Минимальное MSE
Cреднее MSE
9
Количество нейронов во входном слое
0,2175
MSE
0,2205
0,217
1
0,22
0,2195
2
3
Рис. 4.11. Диаграмма зависимости среднего значения MSE
Конечное MSE
от количества скрытых слоев
Минимальное MSE
Cреднее MSE
0,219
MSE
0,2185
0,226
0,225
0,218
0,224
H
93
4
6
8
10
Конечное MSE
12
14
Минимальное
MSE
Количество нейронов
в скрытом слое
0,215
0,230,00001 0,0001 0,001 0,01 0,05
0,1
0,15
0,5
0,75 ECреднее MSE
0,225
MSE
0,22
0,2205
Диаграмма, приведенная на рис. 4.12, показывает зависимости
0,215
MSE
от размера
входного
слоя,0,1
из которой
0,00001
0,0001 0,001
0,01 0,05
0,15 0,5 можно
0,75 E определить не0,22
обходимое
число нейронов во входном слое для лучшего обучения.
0,2195
Результаты
говорят о том, что MSE не сильно зависит от количества
MSE
Конечное MSE
0,219
нейронов
во входном слое, однако, чем их больше, тем
по большему
0,2205
Минимальное MSE
0,2185 признаков сеть будет способна распознать объект.
числу
Cреднее MSE
0,22
Диаграмма зависимости среднего значения MSE от количества
0,218
0,2195
нейронов
в скрытом слое (рис. 4.13), показывает, что конечное зна0,2175
Конечноеравным.
MSE
0,219 MSE на всех экспериментах было приблизительно
чение
0,217
Минимальное MSE
В таком
случае
внимание3 на минимальное
значе0,2185
1 следует обратить
2
H
Cреднее MSE
ние
MSE.
Таким
образом,
по
результатам
второго
эксперимента
сле0,218
дует выбирать между шестью и четырнадцатью нейронами.
0,2175
0,217
MSE
0,226
1
2
3
H
0,225
Конечное MSE
Минимальное MSE
Cреднее MSE
0,224
0,223
MSE
0,222
0,226
0,221
0,225
0,22
0,224
0,219
0,223
3
0,222
0,221
MSE
0,22
0,2205
0,219
0,22
5
7
Конечное MSE
Минимальное MSE
Cреднее MSE
9
Количество нейронов во входном слое
Рис. 4.12. Диаграмма зависимости MSE
от размера входного слоя
3
5
7
0,2195
MSE
9
Количество нейронов во входном слое
Конечное MSE
Минимальное MSE
Cреднее MSE
0,2205
0,219
0,22
0,2185
0,2195
0,218
4
6
8
10
Конечное MSE
12
14
Минимальное
MSE
Количество нейронов
в скрытом слое
Cреднее MSE
4
6
8
10
12
14
Количество нейронов в скрытом слое
0,219
0,2185
0,218
Рис. 4.13. Диаграмма зависимости среднего значения MSE
от количества нейронов в скрытом слое
94
Следующим этапом является тестирование. Он позволяет определить качество обучения сети.
Тестирование нейронной сети происходит на тестовых сетах. Тестовые сеты представляют собой специально подготовленные последовательности, отображающие значение на входе нейронной сети
при немного уменьшенной концентрации вещества.
Значения тренировочных сетов, которые использовались при обучении нейронной сети, приведены в табл. 4.1.
По результатам, представленным в табл. 4.1 можно сделать вывод, что при подаче на вход вещества из базы знаний, но с концентрацией меньшей на 2–9%, на сеть будут подаваться входные значения, близкие по величине с тренировочными сетами. Значение MSE
не будет превышать одного процента.
Предложенный подход к построению системы детектирования
опасных веществ по запаху на базе платформы Интернета вещей по
технологии исполнения является новым решением в области разработки физических систем безопасности. Разработанный макет
системы детектирования опасных веществ по запаху продемонстрировал функциональные возможности предлагаемого решения и позволяет обнаруживать такие угрозы как утечка бензола, бутана,
метана, пропана и возгорания на ранней стадии.
Система детектирования может найти применение во многих
отраслях, таких как экология, безопасное производство, охранные
системы и многих других. Для распознавания опасных веществ
Таблица 4.1
Тестовые выборки нейронной сети
Вещество
Концентрация, мг/л
Метан
Метан
Метан
Угарный газ
Угарный газ
Угарный газ
Хлор
Хлор
Хлор
Неизвестный
0,98
0,95
0,91
0,98
0,95
0,91
0,98
0,95
0,91
0,02
Тестовые сеты Тренировочные
Rs/Ro
MSE,%
0,953576739
0,925571325
0,944998448
0,613585345
0,590015396
0,601478379
0,221434676
0,204423444
0,210278622
0,024312478
0,0176
0,4249
0,4718
0,3408
0,4966
0,2504
0,0161
0,4831
0,4845
0,0094
0,934567318
0,934567318
0,934567318
0,592465487
0,592465487
0,592465487
0,213243545
0,213243545
0,213243545
0,024312478
95
по запаху обучена нейронная сеть, архитектура которой выбрана
экспериментальным путем под известное (заданное) количество
распознаваемых запахов, максимальная ошибка обучения составила 0,5%.
4.3. Сеть Хопфилда
Нейронные сети Хопфилда имеют обратную связь между различными слоями нейронов и поэтому называются рекуррентными. Их
отличительная черта состоит в том, что происходит передача сигнала с выходного или скрытого слоя на входной слой [17].
Благодаря обратной связи изменение одного нейрона приводит к
изменению всей сети. Так, в сети появляется переходный процесс,
который формирует некое устойчивое состояние, отличающееся от
предыдущего.
Основное назначение нейронной сети Хопфилда – это решение
задачи распознавания образов.
Образ – классификационная группировка в системе классификации, выделяющая определенную группу объектов по некоторому
признаку.
Распознавание образов, объектов, процессов – это процесс идентификации предъявляемого объекта или каких-то его свойств, для
определения принадлежности этого объекта к какому-то из заранее
выделенных классов объектов [20].
Таким образом, с точки зрения анализа данных сеть Хопфилда
полезна для решения задачи классификации.
4.3.1. Архитектура нейронной сети
Хопфилда
Структура сети Хопфилда представляет собой систему с обратной связью выхода со входом, при этом связь выхода со входом одного и того же нейрона отсутствует [18].
Структура сети Хопфилда показана на рис. 4.14, где S(t) – состояние нейрона в момент времени t; wij – элементы матрицы W весовых
коэффициентов.
Каждый нейрон может находиться в одном из двух состояний:
S(t) ∈ {–1; 1}.
Активации нейрона соответствует + 1, а остановке –1. Дискретность состояний нейрона отражает нелинейный, пороговый характер его функционирования.
96
S1(t)
w12
S (t+1)
1
w1n
S2(t)
.
.
.
Sn(t)
w2n
S (t+1)
w21
.
.
.
Sn(t+1)
wn2
2
wn1
Рис. 4.14. Структура сети Хопфилда
Динамика состояния во времени i-го нейрона в сети из N нейронов описывается дискретной динамической системой:
N

=
=
Si (t + 1) F  ∑
wij S(t) , i, j 1, N,  j =1



(4.13)
где wij – весовой коэффициент, описывающий взаимодействие синапсов i-го нейрона с аксонами j-го нейрона.
Стоит отметить, что wij , i, j = 1, N, и случай
N
∑ wij S(t) = 0
не рас-
j =1
сматриваются.
Также у нейронной сети Хопфилда существуют два режима работы:
1. Асинхронный. В этом режиме сети состояние нейронов в следующий момент времени изменяется последовательно. Сначала для
первого нейрона исследуется локальное поле в момент времени t, затем последовательно для второго нейрона, с учетом нового состояния первого нейрона и так далее для всех остальных нейронов.
2. Синхронный. В этом режиме нейроны также просматриваются последовательно, однако состояния этих нейронов не меняются,
пока все нейроны не будут просмотрены. Затем одновременно меняются состояния всех нейронов.
4.3.2. Обучение нейронной сети Хопфилда
Обучение нейронной сети Хопфилда отличается от обучения по
принципу обратного распространения ошибки. В случае сети Хопфилда процедура обучения для одного входного образа X (процеду97
ра сохранения образа) сводится к вычислению значений элементов
матрицы W [17].
Формально можно описать процесс обучения следующим образом: пусть необходимо обучить нейронную сеть распознавать M образов, обозначенных xk , k = 1, M. Входной образ xi представляет собой:
(4.14)
x=
k xk + ξ, где ξ – шум, наложенный на исходный образ xk.
Фактически, обучение нейронной сети – определение нормы в
пространстве образов xk − xk < δ. Тогда, очистку входного образа от
шума можно описать как минимизацию этого выражения.
Важной характеристикой нейронной сети является отношение
числа образов M, которые должны быть распознаны и соответственно запомнены, к числу нейронов сети N: α = M/N. Для сети Хопфилда значение α не больше 0,14.
Вычисление квадратной матрицы для ключевых образов производится по правилу Хебба:
=
wij
1 M
∑ x ik ⋅x jk , N k=1
(
)
(4.15)
где xjk означает j-й элемент образа k.
Стоит отметить, что в силу коммутативности операции умножения, соблюдается равенство wij = wji.
Входной образ, который предъявляется для распознавания, соответствует начальным данным для системы, служащий начальным условием для динамической системы (4.13):
Si = xk . (4.16)
Уравнения (4.13) – (4.16) полностью определяют процесс обучения нейронной сети Хопфилда.
Пусть нашей задачей является сохранение образа X = [1,–1,1,1].
На первом этапе определяем весовые значения сети Хопфилда, а затем убедимся, что сеть сможет восстановить сохраненный образец
при подаче на вход искаженного вектора X =[ −1, −1,1,1].
Определяем весовую матрицу по формуле (4.15)
1
 −1
W =   ⋅ 1 −1 1 1 =
1
 
1
98
 1 −1 1 1 
 −1 1 −1 −1

.
 1 −1 1 1 


 1 −1 1 1 
Обнуляем диагональные элементы матрицы:
 0 −1 1 1 
 −1 0 −1 −1
.
W=
 1 −1 0 1 


 1 −1 1 0 
Весовые значения рассчитаны – сеть обучена, подадим на вход
вектор X и посмотрим, как поведут себя нейроны нашей сети.
Комбинированный ввод первого нейрона будет равен:
S1 =(−1) ⋅ 0 + (−1) ⋅ (−1) + 1 ⋅ 1 + 1 ⋅ 1 =3.
Поскольку S1 > 0, то нейрон 1 будет находиться в состоянии + 1.
Для второго нейрона:
S2 =(−1) ⋅ (−1) + (−1) ⋅ 0 + 1 ⋅ (−1) + 1 ⋅ (−1) =−1.
Нейрон 2 окажется в состоянии -1.
S3 =(−1) ⋅ 1 + (−1) ⋅ (−1) + 1 ⋅ 0 + 1 ⋅ 1 =1.
Нейрон 3 в состоянии + 1.
S4 =(−1) ⋅ 1 + (−1) ⋅ (−1) + 1 ⋅ 1 + 1 ⋅ 0 =1.
Нейрон 4 в состоянии + 1.
Таким образом, получен вектор X
= [1, −1,1,1], что соответствует
тому образу X, который был запомнен в примере, что демонстрирует работоспособность обученной сети. Если теперь еще раз произвести расчет состояний нейронов в соответствии с теми состояниями,
которые они приняли после прохождения вектора X по взвешенным связям, то увидим, что состояния не изменится, то есть сеть
оказалась в устойчивом положении.
4.3.3. Пример решения задачи распознавания образов
на основе сети Хопфилда
Пусть образом является черно-белое изображение размера 7×7
пикселей, то есть входной вектор X представляет собой черно-белые
изображения образов размера 7×7 пикселей. Изображения образов
представляются как одномерные векторы со значениями 1 и –1, где
1 – это черный пиксель; –1 – белый пиксель.
Студентами 4-го курса разработано приложение, которое реализует процесс распознавания образов, так как это делает сеть Хопфилда.
99
Решение поставленной задачи включает следующие шаги:
1. Создание базы эталонных образов.
2. Построение весовой матрицы W.
3. Распознавание образов: классификация нового образа путем поиска максимально похожего на него из набора эталонных
образов.
4. Вывод результата: изображение образа, который максимально
похож на распознаваемый, либо сообщение о том, что искомый образ в наборе эталонных образов отсутствует.
Приложение работает сначала в режиме обучения – пользователь записывает и сохраняет ряд эталонных образов, а потом в режиме распознавания – пользователь подает изображение образа,
в том числе искаженного, с целью классификации этого образа.
Режим обучения сети включает:
– Преобразование каждого эталонного изображения образа в одномерный вектор X, таким образом сохраняется набор эталонов.
– Вычисление весовой матрицы W по полученным одномерным
векторам.
– Обнуление главной диагонали матрицы W.
Режим распознавания включает:
– Преобразование распознаваемого изображения в одномерный
вектор X* .
– Определение комбинированного ввода каждого нейрона: умножение транспонированного вектора X* на матрицу W: Si =X T ⋅W, i =1,49.
Si =X T ⋅W, i =1,49.
– Определение функции активации для нейрона и оценка состояния нейрона Si ∈ {–1; 1}.
– Получение результирующего вектора изображения X.
– Сравнение X и Х, в результате сравнения возможен один из вариантов:
1.  X − X < δ, получим ответ в виде искомого эталонного образа.
2.  X − X ≥ δ, результат пока не найден, и проводится серия итераций до получения устойчивого состояния сети. Когда сеть достигнет устойчивого состояния, то снова проверяется X − X < δ : если
результат совпал с одним из имеющихся эталонных образов, то получим ответ в виде искомого эталонного изображения, в противном
случае выведем сообщение о невозможности распознать образ.
Блок-схема алгоритма разработанного приложения приведена
на рис. 4.15.
100
Искаженное
изображение
Ряд
эталонных образов
Перевод изображений
в одномерный вектор
Транспонирование
векторов
1
Умножение
исходного вектора на
транспонированный
Вектор
умножается
на W
Суммирование
результатов
умножения
Использование
функции
активации
В результате имеется
матрица весов W
(обнуление главной
диагонали)
Умножение
Использование функции
активации
Совпадает
Результат
в виде
искомого
образа
Сравнение
результата
с эталонными
образами
Не равны
Сравнение
выходного вектора
со входным
Равны
Не совпадает
Совпадает
Сравнение
результата
с эталонными
образами
Не совпадает
Результат в виде
искомого образа
Нет
совпадений
1
Рис. 4.15. Схема алгоритма решения
Для проверки устойчивости обученной сети Хопфилда проведен
ряд экспериментов, позволивших оценить значение δ, при котором
образы перестанут распознаваться.
101
Графический интерфейс приложения показан на рис. 4.16. Кнопка «Добавить образ» реализует функцию преобразования изображения образа в двумерный массив и добавление его в базу данных
эталонных образов.
Кнопка «Посмотреть все образы» реализует функцию последовательного показа в интерфейсном окне всех добавленных изображений (рис. 4.17). На консоли отображается порядковый номер изображения и общее количество изображений в списке.
Кнопка «Удалить все образы» реализует функцию удаления из
списка всех образов.
Кнопка «Очистить поле» реализует функцию очистки интерфейсного окна от изображения.
Кнопка «Распознать образ» реализует функцию распознавания
текущего изображения по заданному пользователем списку эталонных изображений и определения уровня искажения в процентах:
100c
δ=
, где c – количество отличающихся позиций; 49 – длина
49
вектора X.
Рис. 4.16. Интерфейс приложения
102
Рис. 4.17. Демонстрация коллекции эталонных образов
Для демонстрации работы сети Хопфилда рассмотрим три латинские буквы «L» – образ 1; «T» – образ 2; «X» – образ 3, сохраненные
в базе эталонных образов.
В качестве искаженного образа X использован зашумленный
образ буквы «L», как, например, показано на рис. 4.18.
Как видно из рис. 4.18, такой искаженный образ буквы «L» сеть
распознала. Далее в табл. 4.2 приведены результаты серии разнообразных искажений образа буквы «L», с целью определения уровня δ, при котором сеть не сможет определить искаженный образ.
Рис. 4.18. Искаженный вариант
буквы «L»
103
Таблица 4.2
Результаты первого эксперимента
Искаженный пример буквы «L»
Результат работы сети
Увеличим количество эталонных образов до пяти латинских
букв: «L» – образ 1; «T» – образ 2; «X» – образ 3; «O» – образ 4; «N» –
образ 5 (рис. 4.19). В качестве искаженного образа использована
буква «T». Результаты распознавания показаны в табл. 4.3.
104
Таблица 4.3
Результаты второго эксперимента
Искаженный пример буквы «T»
Результат работы сети
105
Рис. 4.19. Демонстрация коллекции пяти эталонных образов
латинских букв
В первом эксперименте эталонных образов было 3, и также подавался на вход искаженный образ в различных вариациях. Уровень
определения образа был достаточно высокий, максимальное значение отклонения от эталонного образа составило 41% в силу небольшого количества эталонных изображений.
Стоит заметить, что чем сильнее искажен необходимый объект,
а не прочие искажения за объектом, тем слабее происходит распознавание.
Аналогичный результат получился во втором эксперименте.
Можно заметить, что если сам объект на искаженном изображении
не зашумлен, а зашумлен «фон», то нейронная сеть ее распознает
достаточно хорошо.
Как показывает теория и практика применения нейронных сетей, задача поиска изображения по образцу является той задачей,
которая решается сетью Хопфилда.
Наиболее известные задачи распознавания образов, которые решаются с применением сети Хопфилда:
– распознавание текста или отдельных букв (символов);
– распознавание лиц, отпечатков пальцев и других биометрических характеристик;
– распознавание отдельных объектов на изображении;
– распознавание автомобильных номеров.
Основной недостаток сети Хопфилда заключается в том, что смещение или поворот объекта на изображении относительно его эталонного
образа может привести к тому, что объект может быть не распознан.
Казалось бы, выходом из такой ситуации может быть пополнение базы эталонных образов одного и того же объекта с разным
смещением и поворотами. Однако даже если подать в качестве искаженного изображения один из эталонных образов, сеть его не
распознает. Это связано с относительно маленьким объемом памяти
сети Хопфилда, в результате чего эталонные изображения образов
начинают «перекрывать» друг друга.
106
4.4. Сеть Кохонена
Нейронная сеть Кохонена в отличие от рассмотренных ранее сетей обучается без учителя и носит название самоорганизующейся
карты Кохонена [20].
Сеть Кохонена может решать задачу кластеризации данных, а
также устанавливать близость классов.
Если классы изначально заданы, то сеть Кохонена может решать
задачи классификации.
Другая возможная область применения – обнаружение новых
явлений, то есть если в сеть Кохонена подается набор данных, непохожий ни на один из известных образцов, то она не сможет классифицировать такой набор и тем самым выявит его новизну.
4.4.1. Архитектура сети Кохонена
Сеть Кохонена имеет всего два слоя: входной и выходной. Каждый нейрон входного слоя соединяется с каждым нейроном выходного слоя и, все связи имеют определенный вес, который корректируется в процессе обучения. Выходной слой называют также слоем
топологической карты. Элементы топологической карты располагаются в некотором пространстве – как правило, двумерном. Поэтому
сеть Кохонена чаще изображают в виде топологической карты, то
есть только нейроны выходного слоя (рис. 4.20) [17].
Карты Кохонена имеют набор входных элементов, количество
которых совпадает с размерностью подаваемых на вход векторов, и
набор выходных элементов, каждый из которых соответствует одному кластеру (группе). Если анализируются объекты по 4 признакам, то, соответственно, сеть имеет 4 входа, по одному для каждого
Входной слой
Выходной слой
x1
y1
x2
x3
.
.
.
.
.
.
Топологическая карта
y1
y2
...
y2
ys
ys
xn
Рис. 4.20. Архитектура сети Кохонена
107
признака, а в качестве входного вектора выступает один из объектов, где его координатами являются значения его признаков.
Обычно стараются задавать количество выходных элементов
меньшим, чем количество входных, в таком случае сеть позволяет
получить упрощенную характеристику объектов для дальнейшей
работы с ними.
Суть работы сети Кохонена заключается в следующем. При подаче некоторого вектора X на вход, сеть должна определить, к какому
из кластеров этот вектор ближе всего. В роли кластера выступает
выходной нейрон, а в качестве критерия близости может быть выбрана метрика квадрата евклидова расстояния.
Вектор X представляет собой точку в n-мерном пространстве, где
n – количество координат вектора, которые подаются на вход нейронов сети. Вычисление расстояния между этой точкой и центрами
разных кластеров позволяет определить кластер, расстояние до которого окажется минимальным. Тогда этот кластер и соответствующий ему выходной нейрон объявляется победителем.
Центр кластера определяется как точка, координатами которой в
n-мерном пространстве являются величины весов всех связей, которые приходят к данному выходному нейрону от входных нейронов.
Метрика квадрата евклидова расстояния:
=
dij
n
∑ ( xik − yjk )
2
,
(4.17)
k =0
где dij – квадрат расстояния между точкой X и кластером Y. Координаты точки X – xi1, xi2, …, xin, а координаты центра кластера Y – yj1,
yj2, …, yjn.
Итак, карты Кохонена решают задачу классификации следующим образом: подав вектор на вход сети, будет получен один кластер-победитель, который определяет принадлежность входного
вектора к этому кластеру.
4.4.2. Обучение сети Кохонена
Обучается сеть Кохонена методом последовательных приближений. Основной итерационный алгоритм обучения сети Кохонена последовательно проходит одну за другой ряд эпох, при этом на
каждой эпохе он обрабатывает каждый из обучающих примеров в
следующей последовательности [18]:
– выбрать выигравший нейрон, то есть тот, который расположен
ближе всего к входному примеру;
108
– скорректировать выигравший нейрон так, чтобы он стал более
похож на этот входной пример, вычислив квадрат евклидова расстояния между центром выигравшего нейрона и обучающего примера.
При вычислении центра нейрона-победителя используется постепенно убывающий коэффициент скорости обучения, с тем чтобы на каждой новой эпохе коррекция становилась все более тонкой.
В результате положение центра установится в некоторой позиции,
которая удовлетворительным образом представляет те наблюдения,
для которых данный нейрон оказался выигравшим.
В результате такой итеративной процедуры обучения сеть организуется таким образом, что элементы, соответствующие центрам,
расположенным близко друг от друга в пространстве входов, будут
располагаться близко друг от друга и на топологической карте.
Свойство топологической упорядоченности достигается в алгоритме с помощью дополнительного использования понятия окрестности [19].
Окрестность – это несколько нейронов, окружающих выигравший нейрон, называется радиусом R окрестности (рис. 4.21). Подобно скорости обучения, размер окрестности убывает со временем, так
что вначале к ней принадлежит довольно большое число нейронов
(возможно, почти вся топологическая карта). На самых последних
этапах окрестность становится нулевой, т. е. состоящей только из
самого выигравшего нейрона.
R
Рис. 4.21. Окрестность кластера
109
Результатом такого изменения окрестностей является то, что
изначально довольно большие участки сети «перетягиваются» в
сторону обучающих примеров. Сеть формирует грубую структуру
топологического порядка, при которой похожие наблюдения активируют группы близко лежащих нейронов на топологической карте. С каждой новой эпохой скорость обучения и радиус окрестности
уменьшаются, тем самым внутри участков карты выявляются все
более тонкие различия, что, в конце концов, приводит к тонкой настройке каждого нейрона.
Таким образом, в отличие от обучения с учителем, рассмотренного ранее, суть обучения сети Кохонена состоит не в том, чтобы сравнивать вывод сети с идеальным выводом, а в подстройке весов всех
связей для максимального совпадения с входными данными.
Обобщим алгоритм процесса обучения сети Кохонена и запишем
как последовательность шагов:
Шаг 1. Для входного вектора X подсчитываем значения координат нейронов выходного слоя, вычисляем квадрат евклидова расстояния dij от него до каждого из кластерных элементов сети.
Шаг 2. Находим минимальное dij из полученных значений, определяем элемент-победитель.
Шаг 3. Для нейрона-победителя, а также для тех нейронов, которые попали в заданный радиус, выполняем корректировку весов
связей:
(
)
wij (t=
+ 1) wij (t) + ∆(t) xi − wij (t) , (4.18)
где wij (t + 1) – вес на шаге t + 1; wij (t) – вес на шаге t; ∆ – скорость
обучения; xi – координата входного вектора.
Шаг 3. Обновляем значения нормы обучения и радиуса.
Шаг 4. Продолжить обучение, пока не выполнено условие остановки обучения.
Остановка обучения происходит в том случае, если величины изменения весов становятся очень маленькими.
Часто обучение умышленно разбивают на две фазы: более короткую, с большой скоростью обучения и большими окрестностями, и
более длинную, с малой скоростью обучения и нулевыми или почти
нулевыми окрестностями.
При решении задач классификации в сетях Кохонена используется так называемый порог доступа [20]. Ввиду того, что в такой
сети уровень активации нейрона есть расстояние от него до входного
примера, порог доступа играет роль максимального расстояния, на
110
котором происходит распознавание. Если уровень активации выигравшего нейрона превышает это пороговое значение, то сеть считается не принявшей никакого решения. Поэтому, когда все нейроны
помечены, а пороги установлены на нужном уровне, сеть Кохонена
может служить как детектор новых явлений (она сообщает о непринятии решения только в том случае, если поданный ей на вход случай значительно отличается от всех радиальных элементов).
После того как сеть обучена распознаванию структуры данных,
ее можно использовать как средство визуализации анализа данных.
С помощью неоднократного запуска работы сети Кохонена можно
определить, разбивается ли карта на отдельные кластеры. Можно
также обрабатывать отдельные наблюдения и смотреть, как при
этом меняется топологическая карта, – это позволяет понять, имеют ли кластеры какой-то содержательный смысл. После того, как
кластеры выявлены, нейроны топологической карты помечаются
содержательными по смыслу метками. После того, как топологическая карта построена, на вход сети можно подавать новые наблюдения. Если выигравший при этом нейрон был ранее помечен именем
класса, то сеть осуществляет классификацию. В противном случае
считается, что сеть не приняла никакого решения.
111
ЗАКЛЮЧЕНИЕ
В монографии рассматриваются различные задачи и инструменты анализа данных, которые при развитии технологии больших
данных становятся актуальными практически во всех областях человеческой деятельности.
Особенностью анализа данных является комплексное применение математического инструментария и информационных технологий. Учитывая данное обстоятельство материал монографии структурирован по наиболее типичным задачам анализа данных.
В первой главе рассматривается связь многочисленных понятий,
которыми оперируют при анализе данных, дается характеристика
типичных задач анализа данных и разнообразных методов, поддерживающих решение этих задач.
Вторая глава посвящена кластерному анализу. В ней обсуждаются иерархические и неиерархические методы кластеризации.
Приводятся основные метрические характеристики, применяемые
в процессе кластеризации, и выражения для их вычисления. Рассмотрены примеры применения кластерного анализа при построении системы идентификации веществ по спектру.
В третьей главе рассматривается задача классификации, приводятся этапы ее решения и характеристика методов, позволяющих
решать подобные задачи. Более подробно рассмотрен пример применения метода опорных векторов при организации биометрической
системы доступа по отпечатку пальца.
Четвертая глава демонстрирует возможности нейронные сетей,
как инструмента анализа данных для решения задач классификации и кластеризации.
Монография содержит результаты исследований, проводимыми
студентами магистратуры по направлении 10.04.01 – Информационная безопасность. Это объясняет появление в монографии примеров решения задач анализа данных применительно к области
информационной безопасности. Все исследования доведены до программной реализации, что демонстрирует взаимосвязь информационного и инструментального потоков анализа данных, рассматриваемых в первой главе.
112
Библиографический список
1. Анализ данных и процессов / А. А. Барсегян, И. И. Холод,
М. Д. Тесс, М. С. Куприянов, С. И. Елизаров. СПб.: БХВ-Петербург,
2009. 512 с.
2. Мхитарян В. С. Анализ данных: учебник. М.: Юрайт, 2016. 490 с.
3. Информационные процессы и технологии / Б. Я. Советов,
М. О. Колбанев, Т. М. Татарникова. 2014. СПб.: ГУАП. 239 с.
4. Ian H. Witten, Eibe Frank and Mark A. Hall. Data Mining:
Practical Machine Learning Tools and Techniques. 3rd Edition. Morgan
Kaufmann, 2011. 664 р.
5. Конотопов П. Ю., Курносов Ю. В. Аналитика: методология,
технология и организация информационно-аналитической работы.
М.: РУСАКИ, 2004. 512 с.
6. Паклин Н. Б., Орешков В. И. Бизнес-аналитика: от данных к
знаниям. СПб.: Питер, 2009. 624 с.
7. Боровиков В. П. Популярное введение в современный анализ
данных в системе STATISTICA: учеб. пособие для вузов. М.: РиС,
2015. 288 c.
8. Черткова Е. А. Статистика. Автоматизация обработки информации: учеб. пособие. М.: Юрайт, 2016. 195 с.
9. Миркин Б. Г. Введение в анализ данных: учебник и практикум. Люберцы: Юрайт, 2016. 174 c.
10. Лесковец Ю., Раджараман А. Анализ больших данных. М.:
ДМК. 498 с.
11. Вьюгин В. Математические основы теории машинного обучения и прогнозирования. М.: МЦМНО, 2013. 390 с.
12. Харманн Г. Современный факторный анализ. М.: Статистика, 1972. 489 с.
13. Иберла К. Факторный анализ. М.: Статистика, 1980. 387 с.
14. How to Reduce Number of Variables and Detect Relationships,
Principal Components and Factor Analysis / StatSoft, Inc. Electronic
Statistics Textbook. Tulsa, OK, 2013. URL: https://www.statsoft.com/
Textbook/Principal-Components-Factor-Analysis (дата обращения:
20.08.2018).
15. Многомерные статистические методы / Е. Е. Иванов, Д. А. Шустов, С. А. Перешивкин, 2010. URL: http://ecocyb.narod.ru/513/MSM/
msm3_3.htm (дата обращения: 17.05.2017).
16. Larose Daniel T., Larose Chantal D. Discovering knowledge in
data: an introduction to data mining. John Wiley & Sons Limited, New
Jerscy. 2014. 336 р.
113
17. Тархов Д. А. Нейросетевые модели и алгоритмы. Справочник.
М.: Радиотехника, 2014. 349 с.
18. Рутковская Д., Пилиньский М., Рутковский Л. Нейронные
сети, генетические алгоритмы и нечеткие системы. М.: Горячая линия – Телеком, 2013. 384 с.
19. Рассел С., Норвиг П. Искусственный интеллект. Современный
подход. М.: Вильямс, 2006. 1408 c.
20. Алпайдин Э. Машинное обучение: новый искусственный интеллект. М.: Альпина Паблишер: Точка, 2017. 208 с.
21. Варгаузин В. А. Радиосети для сбора данных от сенсоров, мониторинга и управления на основе стандарта IEEE 802.15.4//ТелеМультиМедиа. №6. 2005. С. 23–27.
114
Содержание
Ведение..................................................................................... 1. Введение в анализ данных ........................................................ 1.1. Взаимосвязь основных понятий анализа данных.................... 1.2. Типичные задачи Data Mining............................................. 1.3. Стадии анализа данных...................................................... 2. Кластерный анализ ................................................................. 2.1. Постановка задачи кластерного анализа............................... 2.2. Меры расстояний в кластеризации....................................... 2.3. Методы кластерного анализа .............................................. 2.3.1. Иерархические алгоритмы......................................... 2.3.2. Неиерархические методы .......................................... 2.4. Факторный анализ............................................................. 2.4.1. Методы факторного анализа....................................... 2.4.2. Решение задачи идентификации веществ методом
факторного анализа........................................................... 3. Классификация....................................................................... 3.1. Постановка задачи классификации...................................... 3.2. Методы решения задачи классификации............................... 3.2.1. Деревья решений...................................................... 3.2.2. Линейный метод опорных векторов............................. 3.2.3. Метод «ближайшего соседа»....................................... 4. Нейронные сети, как инструмент анализа данных........................ 4.1. Элементы и характеристики нейронной сети......................... 4.2. Нейронные сети прямого распространения............................ 4.2.1. Архитектура нейронной сети прямого распространения. 4.2.2. Обучение нейронной сети и выбор архитектуры............. 4.2.3. Решение одной задачи классификации на основе сети
прямого распространения................................................... 4.3. Сеть Хопфилда.................................................................. 4.3.1. Архитектура нейронной сети Хопфилда....................... 4.3.2. Обучение нейронной сети Хопфилда............................ 4.3.3. Пример решения задачи распознавания образов
на основе сети Хопфилда..................................................... 4.4. Сеть Кохонена................................................................... 4.4.1. Архитектура сети Кохонена........................................ 4.4.2. Обучение сети Кохонена............................................. Заключение............................................................................... Библиографический список.......................................................... 3
5
5
7
8
11
11
13
17
17
27
31
32
44
53
53
58
58
69
74
77
77
82
82
85
89
96
96
97
99
107
107
108
112
113
115
Научное издание
Татарникова Татьяна Михайловна
АНАЛИЗ ДАННЫХ
В ПРИКЛАДНЫХ ЗАДАЧАХ ОБЕСПЕЧЕНИЯ
ИНФОРМАЦИОННОЙ БЕЗОПАСНОСТИ
Монография
Редактор В. П. Зуева
Компьютерная верстка С. Б. Мацапуры
Сдано в набор 13.09.18. Подписано к печати 26.11.18.
Формат 60×84 1/16. Усл. печ. л. 6,8. Уч.-изд. л. 7,3.
Тираж 500 экз. (1-й завод – 100 экз.). Заказ № 527.
Редакционно-издательский центр ГУАП
190000, Санкт-Петербург, Б. Морская ул., 67
Документ
Категория
Без категории
Просмотров
8
Размер файла
5 427 Кб
Теги
tatarnikova
1/--страниц
Пожаловаться на содержимое документа