Математический факультет
ДИПЛОМНАЯ РАБОТА
Проектирование и разработка информационной системы реконструкции когнитивных паттернов восприятия композиции графических текстов
Аннотация
В данной выпускной квалификационной работе рассматривается проблема исследования процессов восприятия и понимания графического текста.
В работе содержится описание особенностей восприятия и понимания графических текстов.
Работа содержит проектирование информационной системы реконструкции когнитивных паттернов восприятия композиции графических текстов. Подробно рассматриваются функциональные возможности системы. Описываются алгоритмы взаимодействия пользователей с системой.
В работе описывается разработка информационной системы реконструкции когнитивных паттернов восприятия композиции графических текстов. Обосновывается выбор средства разработки программного средства, раскрывается процесс и особенности ее реализации. Проведена кластеризация информантов на основе данных, полученных в результате прохождения эксперимента. Обоснованы результаты кластеризации.
Работа выполнена печатным способом на 51 странице с использованием 22 источников, содержит два приложения, в том числе 33 рисунка, 2 таблицы и 22 формулы.
Abstract
In this work the final qualifying research paper considers the problem of perception and understanding of graphical text.
This work describes the features of perception and understanding of graphic texts.
The work includes the design of information system renovation cognitive patterns of perception of the composition of graphic texts. Detail the functionality of the system. Algorithms for users to interact with the system.
This work describes the development of information system renovation cognitive patterns of perception of graphic composition of texts. The choice of development tools, software tools, process and reveals the peculiarities of its realization. Conducted clustering of informants, based on data obtained from transmission experiments. Justified by the results of clustering.
The work was printed way on 51 pages with 22 sources, contains two applications, including 33 figure, 2 tables and 22 formulas.
Содержание
|
Введение ……………………………………………………………………….. |
6 |
|
1 Особенности восприятия и понимания графических текстов ……….……. |
7 |
|
1.1 Особенности восприятия …………………………………………………. |
7 |
|
1.2 Особенности понимания …………………………………………………. |
9 |
|
2 Проектирование информационной системы реконструкции когнитивных паттернов восприятия композиции графических текстов ………………….. |
12 |
|
2.1 Описание системы ………………………………………………………… |
12 |
|
2.2 Функциональные возможности системы ………………………………… |
13 |
|
2.3 Алгоритмы взаимодействия пользователей с системой ……………….. |
15 |
|
3 Разработка информационной системы когнитивных паттернов восприятия графических текстов …………………………………………….. |
20 |
|
3.1 Модульная структура web-приложения ………………………………… |
20 |
|
3.2 Кластеризация информантов на основе данных, полученных в результате проведения эксперимента …………………………………….. |
28 |
|
Заключение …………………………………………………………………… |
44 |
|
Список использованных источников ……………………………………….. |
45 |
|
Приложение А Описательная статистика результатов разбиения множества информантов на четыре кластера …………………………………………… |
47 |
|
Приложение Б Апробация результатов работы …………………………… |
51 |
Введение
Разработка технологии анализа моделирования когнитивных паттернов восприятия и понимания графических текстов является актуальной задачей. Предметная область изучения когнитивных паттернов восприятия и понимания графических текстов сформировалась на пересечении следующих наук: психолингвистики, психосемантики, теории текста, семиотики и лингвосемиотики, а также в когнитивных науках.
Понимание текста представляет собой многоступенчатый процесс, в основе которого находится переход от процесса первичного восприятия, к результатам первичных обобщений, возникших в результате восприятия, а далее - к выстраиванию смысловой структуры из осмысленных воспринимающим сознанием частей (фрагментов) целого текста.
В основе работ, проводимых в данной предметной области, лежит экспериментальный подход, реализованный посредством разных методов: шкалирование, семантический дифференциал, поэтапное восприятие текста, методики выделения ключевых слов, семантического картирования и мн. др. В то же время все эти методы не могут синхронизировать во времени изучения процесса понимания с самим процессом понимания. В то же время представляется возможным разработка инструментария для моделирования процесса понимания в режиме реального времени.
Наиболее разработанным такой инструментарий может быть для изучения процессов понимания текстов графического типа, т.к. данный тип текста в аспекте его восприятия уже являлся предметом анализа в рамках изучения психофизики зрения (характер движения глаз в процессе восприятии картины).
Однако если процесс восприятия графических текстов можно изучать с помощи записи движения глаз, то процесс понимания должен основываться на других инструментах анализа. В качестве такого инструмента предлагается использовать алгоритм последовательного извлечения смыслов из пространства картины.
В дипломной работе рассмотрены отличительные особенности восприятия от понимания графических текстов. Спроектирована и реализована информационная система когнитивных паттернов восприятия композиции графических текстов.
1 Особенности восприятия и понимания графических текстов
1.1 Особенности восприятия
С точки зрения психологии, восприятие представляет собой осмысленный (включающий принятие решения) и означенный (связанный с речью) синтез разнообразных ощущений, получаемых от целостных предметов или сложных, воспринимаемых как целое явлений. Этот синтез выступает в виде образа данного предмета или явления, который складывается в ходе активного их отражения [1]. Выделяют зрительное, слуховое и осязательное восприятие.
В процессе и результате восприятия в сознании человека возникает образ, основными свойствами которого являются предметность, целостность, константность и категориальностъ. Предметность понимается как способность человека воспринимать мир не в виде набора не связанных друг с другом ощущений, а в форме отделенных друг от друга предметов, обладающих свойствами, вызывающими данные ощущения. Целостность восприятия выражается в том, что образ воспринимаемых предметов не дан в полностью готовом виде со всеми необходимыми элементами, а как бы мысленно достраивается до некоторой целостной формы на основе небольшого набора элементов. Это происходит и в том случае, если некоторые детали предмета человеком непосредственно в данный момент времени не воспринимаются. Константность определяется как способность воспринимать предметы относительно постоянными по форме, цвету и величине, ряду других параметров независимо от меняющихся физических условий восприятия. Категориальность человеческого восприятия проявляется в том, что оно носит обобщенный характер, и каждый воспринимаемый предмет обозначается словом-понятием, относим к определенному классу. В соответствии с этим классом в воспринимаемом предмете ищутся и видятся признаки, свойственные всем предметам данного класса и выраженные в объеме и содержании этого понятия [1].
В основном свойства восприятия изучались на примере зрения. При рассматривании разнообразных объектов глаз человека задерживается в основном лишь на некоторых элементах этих объектов. Любое изображение (если оно не является равномерным фоном или какой-то однообразной мозаикой) содержит различные элементы: на одних глаз задерживается особенно долго, на других мало и, наконец, на некоторых задерживается очень мало или вовсе не обращает на них внимания.
Анализ записей движений глаз показывает, что элементы, привлекающие внимание, содержат или могут, по мнению наблюдателя, содержать сведения полезные и нужные в момент восприятия. Элементы, на которых глаз не останавливается, таких сведений не содержат или, по мнению наблюдателя, содержать не могут.
В зрительном процессе большую роль играют контуры и границы воспринимаемых изображений. Сами по себе границы и контуры никакого влияния на характер движений глаз не оказывают. В движениях глаза мы не можем обнаружить аналогий с движением руки слепого, скользящей вдоль границ и контуров. Граница и контур важны для появления зрительного образа, однако когда образ возник и видится непрерывно, у наблюдателя нет необходимости специально интересоваться границами и контурами. Граница и контур всего лишь элементы, из которых наряду с другими, не менее важными элементами складывается наше восприятие и узнавание предмета. Совершенно очевидно, что контур предмета будет привлекать внимание наблюдателя, если в самой форме контура заключены важные и нужные сведения.
Записи движений глаз показывают, что в процессе рассматривания взор наблюдателя обычно задерживается лишь на некоторых элементах изображения. Как уже упоминалось, при изучении таких элементов обнаруживается, что именно они несут сведения, позволяющие раскрыть содержание изображения [7]. Движения глаз отражают процессы человеческого мышления, и поэтому записи их позволяют в какой-то мере судить о мышлении наблюдателя, о мышлении, которым сопровождается рассматривание того или иного объекта. Изучая записи, легко судить о том, к каким элементам, в какой последовательности и как часто обращается глаз (а следовательно, и мысль) наблюдателя.
При рассматривании человеческого лица наблюдатель обычно больше всего внимания уделяет глазам, губам и носу. Остальные части лица он рассматривает довольно бегло. Глаза и губы человека (или глаза и пасть животного) – наиболее подвижные и выразительные элементы лица. Глаза и губы могут сказать наблюдателю о настроении человека и о его отношении к наблюдателю, о том, какие шаги он может предпринять в последующий момент и т.д. Поэтому совершенно естественно и понятно, что именно глаза и губы больше всего привлекают внимание в лице человека [8].
Записи движений глаз после какой-либо инструкции интересны тем, что они позволяют разбирать смысл движений глаз при свободном рассматривании изображения; они наглядно показывают, что значение элементов, несущих те или иные сведения, определяется задачей, стоящей перед наблюдателем, и это значение может меняться в самых широких пределах.
Существенный вклад в понимание того, как из отдельных зрительно воспринимаемых деталей предметов складывается их целостная картина (образ), внесли представители гештальтпсихологии – направления научных исследований, которое сложилось в Германии в начале XX в. М. Вертгеймер предложил классификацию факторов, влияющих на организацию зрительных ощущений в образы. Первым таким фактором является близость друг к другу элементов зрительного поля, вызвавших соответствующие ощущения. Чем ближе друг к другу пространственно в зрительном поле располагаются соответствующие элементы, тем с большей вероятностью они объединяются друг с другом и создают единый образ. В качестве второго фактора М. Вертгеймер называет сходство элементов друг с другом. Это свойство проявляется в том, что похожие элементы обнаруживают тенденцию к объединению. Третий фактор – фактор «естественного продолжения» – проявляется в том, что элементы, выступающие как части знакомых нам фигур, контуров и форм, с большей вероятностью в нашем сознании объединяются именно в эти фигуры, форму и контуры, чем в другие. Наконец, четвертым фактором является замкнутость. Данное свойство зрительного восприятия выступает как стремление элементов зрительного поля создавать целостные, замкнутые изображения [1].
1.2. Особенности понимания
Восприятие более сложных, осмысленных изображений происходит по-другому. Здесь в первую очередь срабатывает механизм влияния прошлого опыта и мышления, выделяющий в воспринимаемом изображении наиболее информативные места, на основе которых, соотнеся полученную информацию с памятью, можно о нем составить целостное представление, то есть в данном случае речь идет о механизмах понимания [2].
Таким образом, если рассматривать процесс восприятия и понимания текста, то на первом этапе происходит встраивание распредмеченных знаков, составляющих текст, в концептуальную систему воспринимающего и понимающего текст субъекта. Однако данный уровень не является собственно пониманием текста - это уровень понимания отдельных его частей, фрагментов. Поэтому следующий уровень понимания состоит в переходе от понимания фрагментов (результат процесса восприятия) к пониманию целого текста как сложной иерархически организованной семантической системы. И центральную роль в понимании целого текста выполняет его композиция как закономерное мотивированное расположение частей относительно друг друга в рамках всего текста. Конечно, процесс понимания не заканчивается на выстраивании читательской проекции, созданной на основе понимания, интерпретации знаков текста и его композиции, функций стилистических средств, используемых автором [5]. Большую роль в процессе понимания текста (особенно художественных произведений) играет историко-культурный контекст эпохи, традиции и новаторство, биографический текст и многое другое. Но эти “глубины понимания” большей частью имеют профессиональную природу, сочетающую как научные методы (например, герменевтический анализ), так и глубокие историко-культурные знания. Нас же, в первую очередь, интересует процесс понимания обыденного сознания - те когнитивные механизмы, которые помогают “двигаясь” по тексту, выделять в нем целостные компоненты, их семантику, связывать выделенные композиционные единицы в целостную систему отношений между ними.
Процесс восприятия и понимания графических текстов изучался в рамках различных научных направлений. Так, например, в рамках психофизики зрения исследовался характер движения глаз в процессе восприятии картины. Анализ записей движений глаз, проведенный А. Л. Ярбусом, показал, что внимание человека концентрируется на участках, несущих в себе наиболее интересную и полезную для воспринимающего информацию. Обнаруживается, что движения глаз фактически отражают процессы человеческого мышления [2]. Например, в процессе рассматривания человеческого лица наблюдатель больше всего внимания уделяет глазам, губам и носу (рисунок 1).
Глаза и губы человека действительно являются наиболее выразительными и подвижными элементами лица, которые «могут сказать наблюдателю о настроении человека и его отношении к наблюдателю, о том, какие шаги он может предпринять в последующий момент и т.д.» [2].
Рисунок 1 – Траектория движения глаза по портрету
Восприятие и понимание исследовалось также при помощи различных экспериментов с привлечением информантов. Так, в рамках психосемантики механизмы понимания изучались в работах В. Ф. Петренко, Е.Ю. Артемьевой, В.П. Серкина и др. Основные проблемы психосемантики включают исследование существования значений в индивидуальном сознании в виде образов, знаков, символов, символических действий, а также влияния на них эмоциональных и мотивационных факторов. Данные психосемантики широко применяются в области рекламы.
Таким образом, процессы восприятия и понимания неизбежно соприкасаются и переходят друг в друга. Восприятие само по себе не может быть целостным, так как представляет собой как бы процесс «скольжения по объекту». Для того, чтобы оценить объект как целое, с учетом его сущности, функций, предназначения, необходимо включение в процесс восприятия механизмов понимания. Если же объектов несколько, и связи между ними образуют определенную систему отношений, то сама эта система отношений предполагает «расшифровку», декодирование, так как несет в себе определенный смысл. В случае графического текста такой системой отношений между объектами является композиция картины, которая, по словам А.Л. Ярбуса, представляет собой «средство, при помощи которого художник может в какой-то мере навязывать зрителю свое восприятие изображаемого» [2].
Нашей целью является разработка технологий в изучении процесса понимания и создание достоверных моделей процесса понимания. В работе Е.А. Подтиховой изучались механизмы межсемиотической трансформации, однако, как описывает автор, в ходе эксперимента информантам предъявлялись сведения в плане наименования объектов и их содержания, что, согласно нашим предположениям, могло оказывать некоторое влияние на ход эксперимента. Например, порядок предъявления наименований объектов экспериментатором мог повлиять на порядок их появления в текстах-описаниях. При помощи разрабатываемого программного средства планируется нивелировать какое-либо влияние на ход эксперимента.
В качестве материала решено взять произведение А. Иванова «Явление Христа народу». На картине изображено множество объектов, многие из которых имеют имя, наименование и несут определенный смысл. В качестве инструмента фиксации последовательности смыслов предлагается использовать движение курсора при наведении на объекты картины. При клике на объект появляется подсказка-характеристика данного объекта (имя, роль, функции). В окне программы предусматривается возможность проводить вербальное описание по картине (письменный текст-описание).
Таким образом, при клике на объект на восприятие “наслаивается” процесс понимания, поскольку зритель знакомится с именем, наименованием объекта, его значением, - и уже относится к изображению не как к безымянной фигуре, выделенной из фона (на этапе восприятия), а как к знаку, который необходимо соотнести с другими знаками для создания целостной интерпретации текста, которая есть путь к пониманию [6].
При фиксации кликов по объектам картины полагаем, что движение курсора (фиксируемое посредством кликов) может быть представлено как реализация когнитивного сценария понимания художественного изображения. Можно выдвинуть гипотезу о нескольких сценариях (траекториях) “обхода” композиционных единиц (объектов картины), в основе которых лежат свои принципы - средства связности между объектами. Такими средствами могут выступать рядоположенность объектов, жестово-мимическая связность (например, один объект жестом указывает на другой объект), цветовая близость или наоборот противоположность, социальный статус субъектов и др [9].
2 Проектирование информационной системы реконструкции когнитивных паттернов восприятия композиции графических текстов
2.1 Описание системы
Для автоматизации задач в области фиксации последовательности смыслов создается «Информационная система реконструкции когнитивных паттернов восприятия композиции графических текстов».
Возможности системы должны позволять загружать изображения, выделять объекты на изображении, вносить в базу данных характеристики объектов (имя, роль, функции), также должны позволять испытуемому открывать изображение на клиенте, проводить вербальное описание по картине (письменный текст-описание).
Информационная система должна функционировать практически на любом компьютере с любой операционной системой. Информационная система должна иметь простой, понятный и удобный интерфейс. Система должна работать стабильно, гарантировать сохранность результатов эксперимента.
Ключевые возможности и особенности ИС:
– регистрация экспериментаторов;
– регистрация информантов;
– возможность размещения изображений, их подготовка для проведения эксперимента;
– проведение эксперимента, который позволит учитывать движения испытуемого, фиксировать время при вербальном описании по картине.
Система состоит из следующих подсистем:
- модуль «Экспериментатор»;
- модуль «Информант».
Модульная система представлена на рисунке 2, где: 1– подтверждение
Рисунок 2 – Модульная структура информационной системы
факта изменения, 2 – критерии запроса, 3, 7 – таблица, список, информация, 4 – критерии запроса, 5 – подтверждение на изменение запроса, 6 – изменяющийся запрос, 8 – поисковый запрос, 9, 10 – информация, 11– данные от полей ввода.
Рассмотрим описание подсистем на примере модуля экспериментатор.
Данный модуль является частью информационной системы. Он предназначен для выполнения следующих функций:
– добавление изображений;
– выделение объектов на картине;
– добавление характеристик объектов (имя, роль, функции).
Информационные объекты системы. Под информационным объектом (информационным элементом) понимается логически однородная единица информации, для хранения которой достаточно одной записи таблицы.
Информационными объектами разрабатываемой ИС могут быть:
- изображения;
- объект на картине;
- характеристика объекта и т.д.
2.2 Функциональные возможности системы
В качестве пользователей в информационной системе реконструкции когнитивных паттернов восприятия композиции графических текстов могут выступать два субъекта, один из которых является экспериментатором, а другой – информантом. Каждый из этих субъектов взаимодействует с рассматриваемой системой и является ее пользователем.
Рассмотрим подробнее, какую роль играют пользователи в проектируемой информационной системе.
Экспериментатор. Целью создания информационной системы является проведение эксперимента в области когнитивных паттернов восприятия композиции графических текстов. Экспериментатор в разрабатываемой информационной системе выполняет ведущую роль.
Перед экспериментатором стоят следующие задачи:
- отобрать картины для проведения эксперимента;
- подготовить картины для проведения эксперимента.
Экспериментатор должен сформировать набор сюжетных художественных произведений, объекты которых имеют культурологическое значение.
Под подготовкой картины к проведению эксперимента подразумевается ее загрузка на сервер информационной системы. Экспериментатор должен «отредактировать» художественное произведение, т.е. ему необходимо выделить наиболее значимые объекты на картине. Выделенный объект необходимо охарактеризовать, т.е. определить его имя, роль, функции и другие его характеристики.
Если при выделении объекта или внесении характеристики были допущены ошибки, необходимо предусмотреть удаление выделенной области или характеристики.
Основными функциями экспериментатора являются:
1) выбор картины для эксперимента;
2) загрузка картины на сервер информационной системы;
3) выделение объектов на картине;
4) внесение характеристик выделенного объекта.
В результате выполнения основных функций экспериментатора получаем набор данных, необходимых для проведения эксперимента.
Представим функциональные возможности экспериментатора в виде диаграммы вариантов использования (рисунке 3). Построим ее при помощи CASE-средства Rational Rose.
Информант. Перед началом проведения эксперимента экспериментатор предоставляет информанту сюжетное художественное произведение, которое было предварительно отредактировано. В процессе проведения эксперимента перед информантом стоят следующие задачи:
- изучить объекты картины;
- провести вербальное описание по картине.
Рисунок 3 – Диаграмма вариантов использования «Работа экспериментатора»
В процессе проведения эксперимента информант изучает картину в целом. Если в процессе изучения картины информанта заинтересовал какой-либо объект, то при клике на него всплывает подсказка-характеристика. При «достаточном» количестве изученных объектов, информант начинает описывать картину. В процессе вербального описания по картине информант может продолжить изучать объекты художественного произведения, при этом дополняя описание.
Во время проведения эксперимента информационная система будет фиксировать координаты точки клика, время клика на объекте картины, введенный текст.
Выделим основные функции информанта:
- клик на объекте;
- описание по картине.
В результате проведения эксперимента получаем набор данных.
На рисунке 4 представлены функциональные возможности информанта в виде диаграммы вариантов использования.
Рисунок 4 – Диаграмма вариантов использования «Работа информанта»
2.3 Алгоритмы взаимодействия пользователей с системой
Рассмотрим алгоритм взаимодействия экспериментатора с системой. Объектами в этом примере являются:
- экспериментатор;
- картина;
- поле ввода для названия объекта;
- поле ввода для характеристик объекта;
- база данных.
На первом этапе располагаем выбранные объекты. Экспериментатор является пользователем – играет активную роль. Он получает фокус управления сразу после появления в системе. Остальные объекты имеют на данном этапе только линию жизни.
Процесс взаимодействия в информационной системе реконструкции когнитивных паттернов восприятия композиции графических текстов начинается с загрузки экспериментатором сюжетного художественного произведения на сервер. Тем самым, он посылает запрос на сохранение в базу данных. Запрос переводит базу данных в активное состояние и вызывает действие – открытие загруженной картины на клиенте. Следующее действие также инициируется экспериментатором – выделение области на картине. После выделения области, картина получает фокус активности и посылается запрос в базу данных на сохранение пути движения курсора. Запрос переводит базу данных в активное состояние, координаты пути движения курсора сохраняются, вызывается следующее действие – сохраненный набор координат отправляется клиенту. Последнее действие инициирует следующее - набор координат отображается на картине в виде выделенной области.
После выделения объекта на картине, экспериментатор вводит основные характеристики объекта (имя, роль, функции) в поля ввода. Поля ввода для названия объекта и характеристик получают фокус активности и посылаются запросы на сохранение введенных характеристик в базу данных.
В результате получаем набор данных, необходимых для проведения эксперимента.
Представим алгоритм взаимодействия экспериментатора с системой в виде диаграммы последовательности действий при помощи CASE-средства Rational Rose. На рисунке 5 представлена диаграмма последовательности действий, моделирующая действия экспериментатора.
Рисунок 5 – Диаграмма последовательности действий экспериментатора
Обобщим выше описанный алгоритм и представим его в виде диаграммы коопераций. На начальном этапе изображаем все объекты и связи между ними на диаграмме кооперации при помощи соответствующих обозначений. В последующем специфицируем все связи на этой диаграмме, указав на их концах необходимую информацию в форме ролей связей. На диаграмму наносим все сообщения, указав их порядок и семантические особенности. Окончательный фрагмент диаграммы изображен на рисунке 6.
Рисунок 6 – Диаграмма кооперации, моделирующая действия экспериментатора
Рассмотрим алгоритм взаимодействия информанта с системой. Объектами в этом примере являются:
- информант;
- картина;
- поле ввода;
- база данных.
На первом этапе располагаем выбранные объекты. Информант является пользователем – играет активную роль. Он получает фокус управления сразу после появления в системе. Остальные объекты имеют на данном этапе только линию жизни.
Экспериментатор предварительно дает указания, с какой картиной будет проводиться эксперимент. Информанту предоставляется доступ к картине. Процесс взаимодействия в информационной системе начинается с изучения информантом картины, ее основных объектов, композиции. Изучив картину, информант наводит указатель мыши на интересующий его объект и кликает по нему. Последнее действие переводит картину в активное состояние, посылается запрос информации об интересующем объекте в базу данных. Запрос переводит базу данных в активное состояние, осуществляется поиск информации об объекте на основе координат клика информанта. Затем вызывается следующее действие – вывод основных характеристик объекта в браузер информанта. Информант может неоднократно кликать на интересующие его объекты и получать информацию о них.
После того, как информант получит «достаточное» количество информации об объектах картины, он начинает описывать художественное произведение. Текст информант вводит в поле ввода. После окончания ввода текста, посылается запрос в базу данных. Запрос переводит базу данных в активное состояние, осуществляется сохранение введенного текста-описания.
В результате получаем набор данных, полученных в результате проведения эксперимента.
На рисунке 7 представлен алгоритм взаимодействия информанта с системой в виде диаграммы последовательности действий.
Рисунок 7 – диаграмма последовательности действий информанта
Обобщим вышеописанный алгоритм и представим его в виде диаграммы коопераций. На начальном этапе изображаем все объекты и связи между ними на диаграмме кооперации при помощи соответствующих обозначений. В последующем специфицируем все связи на этой диаграмме, указав на их концах необходимую информацию в форме ролей связей. На диаграмму наносим все сообщения, указав их порядок и семантические особенности. Окончательный фрагмент диаграммы изображен на рисунке 8.
Рисунок 8 – Диаграмма кооперации, моделирующая действия информанта
3 Разработка информационной системы когнитивных паттернов восприятия графических текстов
3.1 Модульная структура web-приложения
Информационная система реконструкции когнитивных паттернов восприятия композиции графических текстов будет создана для автоматизации задач в области фиксации последовательности смыслов. При ее создании будут преследоваться следующие цели. Во-первых, информационная система должна функционировать практически на любом компьютере с любой операционной системой. Во-вторых, система должна быть удобна в использовании и интуитивно понятна. В-третьих, должен быть автоматизирован процесс подготовки к проведению эксперимента, процесс сбора данных, полученных в результате проведения эксперимента, обработка результатов эксперимента. В-четвертых, система должна работать стабильно, гарантировать сохранность результатов эксперимента.
Для разработки информационной системы был выбран фреймворк Grails, что позволило создать пользовательский графический интерфейс, затратив минимум усилий, и сосредоточиться на функциональной стороне проекта. В основе Grails лежит паттерн MVC(Model-View-Controller). Графический пользовательский интерфейс и весь функционал информационной системы, который выполняется на сервере, был написан на объектно-ориентированном языке программирования Groovy. Функции экспериментатора по подготовке картины к проведению эксперимента, а также процесс проведения эксперимента были реализованы на языке сценариев javascript с использованием следующих библиотек:
- jQuery.js;
- underscore.js;
- backbone.js;
- raphael.js.
Информационная система реконструкции когнитивных паттернов восприятия графических текстов состоит из нескольких взаимосвязанных модулей. Она включает главную страницу web-приложения http:// cognitivepatterns/, вызываемую непосредственно при запуске информационной системы. Для регистрации пользователей в системе был создан модуль, который определяет класс User.groovy. В web-приложении реализован модуль для загрузки изображений, определяемый классом Image.groovy. Класс Experiment.groovy отвечает за подготовку эксперимента. Для проведения эксперимента был создан модуль, который определяют классы TimeMarkerObjects.groovy и TimeMarkerText.groovy.
Рисунок 9 – Схема взаимодействия модулей информационной системы
Модуль регистрации пользователей. Для того чтобы пользователь мог создавать эксперимент, т.е. выступать в роли экспериментатора, либо мог пройти эксперимент, т.е. выступать в роли информанта, ему необходимо зарегистрироваться в информационной системе. Класс User.groovy представляет модель хранения данных о зарегистрированном пользователе. При регистрации необходимо ввести логин, пароль, имя, фамилию, адрес электронной почты и роль, в которой он будет взаимодействовать с информационной системой.
class User {
String login
String password
String name
String surname
String email
String role = "informant"
…
}
Рисунок 10 – Фрагмент кода класса User.groovy
Модуль загрузки изображения. После того, как пользователь зарегистрировался в информационной системе как экспериментатор, он может перейти к созданию эксперимента. Для этого необходимо выбрать сюжетное художественное произведение и загрузить его на сервер информационной системы. Модель хранения изображения определяет класс Image.groovy.
class Image {
byte[] img
String imgType
static belongsTo = [exp: Experiment]
static constraints = {
exp(nullable: true)
img(nullable: false, maxSize: 1073741824)
}
Рисунок 11 – Фрагмент кода класса Image.groovy
Во время загрузки, в контроллере ImageController.groovy преобразуем изображение в массив байтов и записываем полученную информацию в массив img. Также во время загрузки определяем графический формат хранения изображения и сохраняем его в переменной imgType. Указываем, что изображение принадлежит эксперименту.
class ImageController {
def getImage= {
//retrieve photo code here
def image = Image.get(params.id)
response.contentType = image.imgType //'image/jpeg' will do too
response.outputStream << image.img //'myphoto.jpg' will do too
response.outputStream.flush()
return;
}
}
Рисунок 12 – Фрагмент кода класса ImageController.groovy
При загрузке изображения мы должны установить ограничения. Во-первых, форма загрузки изображения не должна быть пустой, т.е. если во время загрузки пользователь не выбрал изображение и нажал кнопку сохранить, то система выведет сообщение об ошибке. Во-вторых, максимальный размер изображения не должен превышать 1073741824 байт, т.е. 1 гигабайт.
Модуль подготовки эксперимента. После того, как было загружено изображение, экспериментатор может приступить к его подготовке для проведения эксперимента. Под подготовкой изображения подразумевается выделение объектов, определение их названия и характеристик. Это осуществляется на основе модели Experiment.groovy.
Для визуализации процесса подготовки изображения к эксперименту было создано представление editimg.gsp. На странице расположены следующие элементы (рисунок):
- изображение, которое будем «редактировать»;
- цветовая палитра, позволяющая менять цвет контура выделенного объекта;
- поле ввода для названия выделенного объекта;
- поле ввода для характеристик выделенного объекта;
- таблица, для списока выделенных объектов;
- кнопка для сохранения выделенной области и введенной информации об объекте.
Рисунок 13 – Визуализация процесса подготовки изображения к проведению эксперимента
При открытии данной страницы в браузере функция editimg() контроллера ExperimentController.groovy преобразует массив байтов в изображение (рисунок 14).
class ExperimentController {
def editimg() {
def experimentInstance = Experiment.get(params.id)
if (!experimentInstance) {
flash.message = message(code: 'default.not.found.message', args: [message(code: 'experiment.label', default: 'Experiment'), params.id])
redirect(action: "list")
return
}
[experimentInstance: experimentInstance]
}
…
}
Рисунок 14 – Фрагмент кода класса ExperimentController.groovy
Для реализации функции выделения объектов использовался язык сценариев javascript и библиотеки jQuery.js, underscore.js, backbone.js и raphael.ls.
Процесс отрисовки контура заключается в следующем. После нажатия левой кнопкой мыши над изображением, мы следим за движением курсора и отрисовываем путь его движения до тех пор, пока экспериментатор не отпустит левую кнопку мыши. Если экспериментатор не сохранил нарисованный контур, то при следующем нажатии левой кнопкой мыши на изображении рисуется новый контур. Описанный процесс отрисовки реализован с использованием библиотек jQuery.js и raphael.ls. Нам необходимо рисовать только на изображении, следовательно, при объявлении холста для рисования указываем идентификатор контейнера <div>, в нашем случаем он называется “plot”.
(function($) {
Paint.prototype = {
init : function (raw_img) {
…
this.node=img.wrap("<div/>").parent().addClass("plot").css({width:width,height:height});
this.raphael = new Raphael(this.node.get(0), width, height);
this.raphael.image(img.attr("src"), 0, 0, width, height);
…
drawLine : function(line) {
var path = this.raphael.path(line)
.attr({stroke:this.color,'stroke-width':1,'stroke-linejoin':'round'});
$(path.node)
.click((function(c) {return function() {self.onLineClick.apply(self, [c]);}})(self.model.length))
.dblclick((function(c) {return function() {self.onLineDblClick.apply(self, [c]);}})(self.model.length))
.mouseover(function() {this.style.cursor = 'crosshair';});
…
},
…
};
Рисунок 15 – Фрагмент кода, реализующий процесс отрисовки контура
Для хранения нарисованных контуров на клиенте, до отправки их на сервер, создается модель backbone. В модели объявляем следующие поля:
- name – для хранения названия выделенного объекта;
- color – для хранения кода цвета нарисованного контура;
- contour – для хранения пути движения курсора;
- description – для хранения введенных характеристик выделенного объекта;
- expid – для хранения идентификатора изображения, с которым работаем.
Объявляем коллекцию моделей ContourCollection. Для того чтобы добавлять, сохранять данные, создаем экземпляр коллекции cc и в дальнейшем работает с объявленным экземпляром.
var Contour = Backbone.Model.extend({
defaults: {
name: "",
color: "",
contour: "",
description : "",
expid: 0
}
});
var ContourCollection = Backbone.Collection.extend({
model: Contour,
url: '/cognitivepatterns/rest/object'
});
var cc = new ContourCollection();
Рисунок 16 – Фрагмент кода, реализующий объявления модели на стороне клиента
Модуль проведения эксперимента. После того, как изображение было загружено на сервер информационной системы, экспериментатор подготовил его, информант может приступить к прохождению эксперимента. При открытии изображения на клиенте засекаем время. Информант начинает изучение картины, в это время он водит курсором мыши, если курсор попадает в зону выделенной области, мы должны подсветить контур выделенного объекта. Если курсор выходит за пределы выделенной области, подсветка контура должна исчезнуть. При нажатии на какой-либо выделенный объект, должны предоставить информанту его название и характеристики, которые ввел экспериментатор при подготовке картины.
Для визуализации данного процесса было создано представление test.gsp (рисунок 17). На странице расположены следующие элементы:
Рисунок 17 – Визуализация процесса прохождения эксперимента
- изображение, на котором расположены области, ранее отмеченные экспериментатором;
- текстовое поле, для отображения названия объекта и его характеристик;
- текстовое поле, для ввода вербального текста-описания по картине.
При открытии данной страницы в браузере функция editimg() контроллера ExperimentController.groovy преобразует массив байтов в изображение (рисунок 18). На стороне клиента создаем модель backbone Contour, коллекцию ContourCollection. При загрузке страницы в браузер коллекцию контуров, которые были сформированы экспериментатором при подготовке изображения к проведению эксперимента, считываем в экземпляр коллекции ContourCollection. Во время инициализации страницы в цикле, который пробегает значения от нуля до длины коллекции, отображаем имеющиеся контуры на холсте Raphael. При этом задаем следующие параметры:
1) fill – задаем цвет заливки замкнутого контура;
2) fill-opacity – задаем значение прозрачности заливки замкнутого контура (задается числом с плавающей точкой от 0 до 1);
3) stroke-opacity – задаем значение прозрачности границы контура (задается числом с плавающей точкой от 0 до 1);
4) stroke – в данный параметр считываем цвет контура из коллекции, полученной с сервера, который выбрал экспериментатор при выделении данного объекта.
var c = this.raphael.path(cc.models[i].attributes.contour)
.attr({
fill: "#333",
'fill-opacity': 0,
'stroke-opacity': 0,
stroke: cc.models[i].attributes.colour
});
Рисунок 18 – Фрагмент кода, осуществляющий считывание контуров в коллекцию
Далее следим, если курсор мыши находится над контуром, то анимируем его отображение на холсте (рисунок 19). При этом указываем параметры:
1) 'stroke-opacity': 1 – непрозрачный контур:
2) 500 – в течение 500 миллисекунд отображает контур на холсте.
c[0].onmouseover = function () {
c.animate({'stroke-opacity': 1}, 500);
c.toFront();
$('#informantText').blur();
};
Рисунок 19 – Фрагмент кода отображения контура
Если курсор мыши выходит за пределы выделенного контура, то, аналогично, анимируем исчезание контура с холста. Параметры анимации:
1) 'stroke-opacity': 0 – контур прозрачный:
2) 500 – в течение 500 миллисекунд контур исчезает с холста.
c[0].onmouseout = function () {
c.animate({'stroke-opacity': 0}, 500);
c.toFront();
$('#descObject').text('');
};
Рисунок 20 – Фрагмент кода, реализующий исчезание контура
При нажатии на выделенную область отображаем в текстовом поле название и характеристики объекта. При этом в модель backbone TimeMarkerObjects сохраняем координаты точки клика, идентификатор выбранного объекта, время клика – разница между временем начала эксперимента и времени точки клика.
c[0].onclick = function (e) {
$('#descObject').text(cc.models[i].attributes.name + "\n" +
+ cc.models[i].attributes.description);
current = cc.models[i];
var X = e.pageX;
var Y = e.pageY;
var timeCl = new Date().getTime() - startTime;
currentModel = new TimeMarkerObjects({
x: X,
y: Y,
obj: current.id,
timeClick: timeCl
});
timeMarkerObjects.add(currentModel);
currentModel.save();
};
Рисунок 21 – Фрагмент кода, отвечающего за сохранение результатов эксперимента
После прохождения эксперимента сохраняем набор данных, полученных в результате рассматривания объектов на картине, и вербальный текст-описание.
3.2 Кластеризация информантов на основе данных, полученных в результате проведения эксперимента
Кластеризация – это автоматическое разбиение элементов некоторого множества на группы в зависимости от их схожести. Элементами множества может быть что угодно, например, данных или вектора характеристик. Сами группы принято назвать кластерами.
Задача кластеризации заключается в следующем. Имеется обучающая выборка и функция расстояния между объектами
. Требуется разбить выборку на пересекающиеся подмножества, называемые кластерами, так, чтобы каждый кластер состоял из объектов, близких по метрике ρ, а объекты разных кластеров существенно отличались. При этом каждому объекту приписывается метка (номер) кластера .
Алгоритм кластеризации — это функция , которая любому объекту ставит в соответствие метку кластера . Множество меток Y в некоторых случаях известно заранее, однако чаще ставится задача определить оптимальное число кластеров, с точки зрения того или иного критерия качества кластеризации.
Решение задачи кластеризации принципиально неоднозначно, и тому есть несколько причин. Во-первых, не существует однозначно наилучшего критерия качества кластеризации. Известен целый ряд достаточно разумных критериев, а также ряд алгоритмов, не имеющих чётко выраженного критерия, но осуществляющих достаточно разумную кластеризацию «по построению». Все они могут давать разные результаты. Во-вторых, число кластеров, как правило, неизвестно заранее и устанавливается в соответствии с некоторым субъективным критерием. В-третьих, результат кластеризации существенно зависит от метрики ρ, выбор которой, как правило, также субъективен и определяется экспертом.
Кластеризация отличается от классификации тем, что метки исходных объектов изначально не заданы, и даже может быть неизвестно само множество Y . В этом смысле задача кластеризации ещё в большей степени некорректно поставленная, чем задача классификации.
Цели кластеризации могут быть различными в зависимости от особенностей конкретной прикладной задачи:
1) понять структуру множества объектов , разбив его на группы схожих объектов. Упростить дальнейшую обработку данных и принятия решений, работая с каждым кластером по отдельности (стратегия «разделяй и властвуй»);
2) сократить объём хранимых данных в случае сверхбольшой выборки , оставив по одному наиболее типичному представителю от каждого кластера;
3) выделить нетипичные объекты, которые не подходят ни к одному из кластеров. Эту задачу называют одноклассовой классификацией, обнаружением нетипичности или новизны.
В первом случае число кластеров стараются сделать поменьше. Во втором случае важнее обеспечить высокую степень сходства объектов внутри каждого кластера, а кластеров может быть сколько угодно. В третьем случае наибольший интерес представляют отдельные объекты, не вписывающиеся ни в один из кластеров.
Во всех этих случаях может применяться иерархическая кластеризация, когда крупные кластеры дробятся на более мелкие, те в свою очередь дробятся ещё мельче, и т. д. Такие задачи называются задачами таксономии. Результатом таксономии является не простое разбиение множества объектов на кластеры, а древообразная иерархическая структура. Вместо номера кластера объект характеризуется перечислением всех кластеров, которым он принадлежит, от крупного к мелкому. Таксономии строятся во многих областях знания, чтобы упорядочить информацию о большом количестве объектов.
Кластеризация данных включает в себя следующие этапы (рисунок 22):
Рисунок 22 – Этапы кластерного анализа
1) Выделение характеристик. На данном этапе происходит выделение характеристик объектов, с которыми оперирует алгоритм кластеризации. Кроме того, целесообразно трансформировать исходные переменные так, чтобы образовать новые, более информативные показатели. Чтобы избежать «доминирования» переменных с большим масштабом измерения, проводят предварительную нормировку исходных переменных.
2) Определение метрики. Для каждой пары объектов измеряется «расстояние» между ними — степень похожести. Существует множество метрик.
3) Разбиение объектов на группы. Основной вычислительный этап, где свою работу выполняет алгоритм кластеризации.
4) Вывод результатов. Данные представляются в виде таблицы (расстояний между кластерами), графика, отображающего древовидную форму представления кластеров, графика средних для каждого кластера.
5) Определение качества полученной группировки. Необходимо удостовериться в том, что сформированные группы действительно отражают внутренние закономерности, характерные для решаемой задачи, способствуют достижению целей анализа, помогают открыть новые свойства изучаемых объектов.
Основные метрики:
1) Евклидово расстояние. Наиболее распространенная функция расстояния. Представляет собой геометрическим расстоянием в многомерном пространстве:
2) Квадрат евклидова расстояния. Применяется для придания большего веса более отдаленным друг от друга объектам. Это расстояние вычисляется следующим образом:
3) Расстояние городских кварталов (манхэттенское расстояние). Расстояние является средним разностей по координатам. В большинстве случаев эта мера расстояния приводит к таким же результатам, как и для обычного расстояния Евклида. Однако для этой меры влияние отдельных больших разностей (выбросов) уменьшается (т.к. они не возводятся в квадрат). Формула для расчета манхэттенского расстояния:
4) Расстояние Чебышева. Это расстояние может оказаться полезным, когда нужно определить два объекта как «различные», если они различаются по какой-либо одной координате. Расстояние Чебышева вычисляется по формуле:
5) Степенное расстояние. Применяется в случае, когда необходимо увеличить или уменьшить вес, относящийся к размерности, для которой соответствующие объекты сильно отличаются. Степенное расстояние вычисляется по следующей формуле:
где r и p – параметры, определяемые пользователем. Параметр p ответственен за постепенное взвешивание разностей по отдельным координатам, параметр r ответственен за прогрессивное взвешивание больших расстояний между объектами. Если оба параметра – r и p — равны двум, то это расстояние совпадает с расстоянием Евклида.
Алгоритмы кластеризации можно классифицировать следующим образом:
1) Иерархические и плоские. Иерархические алгоритмы (также называемые алгоритмами таксономии) строят не одно разбиение выборки на непересекающиеся кластеры, а систему вложенных разбиений. Т.о. на выходе мы получаем дерево кластеров, корнем которого является вся выборка, а листьями — наиболее мелкие кластера. Плоские алгоритмы строят одно разбиение объектов на кластеры.
2) Четкие и нечеткие. Четкие (или непересекающиеся) алгоритмы каждому объекту выборки ставят в соответствие номер кластера, т.е. каждый объект принадлежит только одному кластеру. Нечеткие (или пересекающиеся) алгоритмы каждому объекту ставят в соответствие набор вещественных значений, показывающих степень отношения объекта к кластерам. Т.е. каждый объект относится к каждому кластеру с некоторой вероятностью.
В случае использования иерархических алгоритмов встает вопрос, как объединять между собой кластера, как вычислять «расстояния» между ними. Существует несколько метрик:
1) Одиночная связь (расстояния ближайшего соседа). В этом методе расстояние между двумя кластерами определяется расстоянием между двумя наиболее близкими объектами (ближайшими соседями) в различных кластерах. Результирующие кластеры имеют тенденцию объединяться в цепочки.
2) Полная связь (расстояние наиболее удаленных соседей). В этом методе расстояния между кластерами определяются наибольшим расстоянием между любыми двумя объектами в различных кластерах (т.е. наиболее удаленными соседями). Этот метод обычно работает очень хорошо, когда объекты происходят из отдельных групп. Если же кластеры имеют удлиненную форму или их естественный тип является «цепочечным», то этот метод непригоден.
3) Невзвешенное попарное среднее. В этом методе расстояние между двумя различными кластерами вычисляется как среднее расстояние между всеми парами объектов в них. Метод эффективен, когда объекты формируют различные группы, однако он работает одинаково хорошо и в случаях протяженных («цепочечного» типа) кластеров.
4) Взвешенное попарное среднее. Метод идентичен методу невзвешенного попарного среднего, за исключением того, что при вычислениях размер соответствующих кластеров (т.е. число объектов, содержащихся в них) используется в качестве весового коэффициента. Поэтому данный метод должен быть использован, когда предполагаются неравные размеры кластеров.
5) Невзвешенный центроидный метод. В этом методе расстояние между двумя кластерами определяется как расстояние между их центрами тяжести.
6) Взвешенный центроидный метод (медиана). Этот метод идентичен предыдущему, за исключением того, что при вычислениях используются веса для учета разницы между размерами кластеров. Поэтому, если имеются или подозреваются значительные отличия в размерах кластеров, этот метод оказывается предпочтительнее предыдущего.
В настоящее время существует несколько подходов к решению задачи кластерного анализа, которые основаны на различных представлениях о задаче, использовании специфичной для каждой предметной области дополнительной информации и т.д. Рассмотрим основные подходы:
Вероятностный подход. Предполагается, что каждый объект генеральной совокупности принадлежит одному из K классов, однако номера классов непосредственно ненаблюдаемы. Объекты выбираются из генеральной совокупности случайно и независимо, поэтому переменные, описывающие объекты, случайны. Для каждого класса определено вероятностное распределение заданного семейства; параметры распределения неизвестны. Имеющаяся выборка наблюдений представляет собой реализацию смеси распределений. Необходимо определить наиболее правдоподобные значения параметров, восстановив закон распределения для каждого класса. Существуют приближенные алгоритмы расщепления смеси (ЕМ-алгоритм). Проверка значимости разделения может быть проведена с использованием аппарата проверки статистических гипотез. Известны также алгоритмы, основанные на непараметрических оценках плотности.
Подход, использующий аналогию с центром тяжести. Для каждой группы определяется вектор средних значений показателей, интерпретируемый как «центр тяжести» группы. Используется критерий внутригруппового рассеяния:
где – координата «центра тяжести» k-го кластера по переменной Оптимальная группировка, при заданном K, соответствует минимальному значению критерия.
В алгоритме K-средних группировочное решение формируется динамически из некоторой исходной группировки путем поэтапного перераспределения объектов в группы с ближайшими центрами тяжести. Это перераспределение идет до получения устойчивого разделения. Аналогичная методика используется также в алгоритме FOREL.
Метод максимизации ожидания основан на итеративном перераспределении исходных данных между кластерами с целью максимизации функции правдоподобия данных как случайной выборки.
Алгоритм:
1) разбиваем каким-либо образом элементы входных данных по кластерам;
2) методом максимального правдоподобия вычисляем параметры условной плотности вероятности при известном значении кластера, т.е. определяем функцию для каждого кластера j.
Методом максимального правдоподобия вычисляем функцию , т.е. вероятность попадания произвольного элемента в каждый кластер.
Параметры функции (вектор математического ожидания и матрица ковариаций непрерывных компонент и значения вероятности дискретных компонент) и (вероятности попадания элемента в кластер) образуют параметры модели .
3) Вычисляем совместную плотность распределения:
4) Вычисляем условную плотности вероятности попадания в кластер j при известном значении , т.е. определяем функцию:
5) Вычисляем:
(9)
где
Получаем:
6) Вычисляем условную плотность распределения входных данных
7) Вычисляем совместную плотность распределения
8) Вычисляем функцию плотности распределения входных данных
9) Вычисляем логарифм функции правдоподобия
10) Если увеличился по сравнению с меньше, чем на пороговую величину, останавливаемся.
11) Вычисляем условную плотности вероятности попадания в кластер j при известном значении входного элемента, т.е. определяем функцию
12)
Подход, основанный на теории графов. Суть алгоритмов, основанных на теории графов, заключается в том, что выборка объектов представляется в виде графа G=(V, E), вершинам которого соответствуют объекты, а ребра имеют вес, равный «расстоянию» между объектами. Достоинством графовых алгоритмов кластеризации являются наглядность, относительная простота реализации и возможность вносения различных усовершенствований, основанные на геометрических соображениях. Основными алгоритмам являются алгоритм выделения связных компонент, алгоритм построения минимального покрывающего (остовного) дерева и алгоритм послойной кластеризации.
Иерархический подход. Данное направление также имеет отношение к теоретико-графовому подходу. Результаты группировки представляются в виде дерева группировки (дендрограммы). Алгоритмы, основанные на этом подходе, можно разделить на агломеративные (поэтапно объединяющие ближайшие группы или объекты) и дивизимные (в которых поэтапно осуществляется разделение исходной группы на наиболее удаленные подгруппы; те в свою очередь также разделяются на подгруппы и т.д.). Группировочные решения представляют собой вложенную иерархию подгрупп. Иерархические методы формируют последовательность разбиений исходных данных на кластеры. Каждый шаг этой последовательности разбиений делит данные на различное число кластеров. Иерархические методы либо объединяют кластеры в процессе реализации алгоритма либо разделяют их. Максимальное число кластеров в этих алгоритмах ограничено. К иерархическим моделям также относятся модели, объединяющие элементы исходных данных в кластеры, представляющие собой классы эквивалентности, определяемые по пороговым значениям каких-либо метрик. После получения последовательности таких разбиений, аналитик определяет наиболее интересную и поддающуюся интерпретации модель. Таким образом, иерархические методы кластеризации различаются алгоритмами разбиения или объединения данных в кластеры, в то время как выбор результирующей модели с точки зрения числа полученных кластеров остается за человеком. К недостатку иерархических алгоритмов можно отнести систему полных разбиений, которая может являться излишней в контексте решаемой задачи.
Подход, основанный на понятии ближайшего соседа. Группировка осуществляется последовательно путем приписывания объекта кластеру, в котором находится ближайший объект, при условии, что расстояние до объекта не превышает заданный порог. Существуют различные варианты определения расстояния; при определении меры близости может учитываться и расположение других соседних точек.
Нечеткие алгоритмы кластерного анализа. При использовании данного подхода предполагается, что каждый кластер представляет собой нечеткое множество объектов. К наиболее популярным алгоритмам этого семейства можно отнести алгоритм нечетких C-средних. Он представляет собой модификацию метода k-средних. Шаги работы алгоритма:
1) Выбрать начальное нечеткое разбиение n объектов на k кластеров путем выбора матрицы принадлежности U размера n x k.
2) Используя матрицу U, найти значение критерия нечеткой ошибки:
где – «цент масс» нечеткого кластера k:
3) Перегруппировать объекты с целью уменьшения этого значения критерия нечеткой ошибки.
4) Возвращаться в п. 2 до тех пор, пока изменения матрицы U не станут незначительными.
Этот алгоритм может не подойти, если заранее неизвестно число кластеров, либо необходимо однозначно отнести каждый объект к одному кластеру.
Подход, использующий искусственные нейронные сети, основан на аналогии с процессами, происходящими в биологических нейронных системах. Известно большое число алгоритмов данного семейства. Типичная архитектура представляет собой однослойную сеть, в которой каждый нейрон соответствует некоторому кластеру. В процессе обучения сети происходит итеративное изменение передаточных весов между входными и выходными узлами сети; тем самым осуществляется поиск оптимального значения критерия группировки. Нейронные сети позволяют эффективно использовать параллельные методы вычислений. Привлекательным свойством самоорганизующихся сетей Кохонена является то, что они формируют наглядное двумерное отображение множества объектов. Существует определенное подобие в процессе группировки между алгоритмами, основанными на нейронных сетях и некоторыми классическими методами кластерного анализа.
Эволюционный (генетический) подход. Алгоритмы данного семейства построены на аналогии с природной эволюцией. В них используются понятия популяции – набора различных вариантов группировки (называемых также хромосомами, по аналогии с соответствующими биологическими объектами), и эволюционных операторов – процедур, позволяющих из одной или нескольких родительских хромосом получить одну или несколько хромосом-потомков. Этими процедурами являются: селекция, рекомбинация и мутация. Генетический алгоритм способен осуществлять поиск решения, доставляющего глобальный минимум критерию качества группировки.
В таблице 1 приведен сравнительный анализ вычислительной сложности алгоритмов кластеризации.
Таблица 1 – Вычислительная сложность алгоритмов
|
Алгоритм кластеризации |
Вычислительная сложность |
|
1 |
2 |
|
Иерархический |
|
|
k-средних |
|
|
c-средних |
|
|
Выделение связных компонент |
Зависит от алгоритма |
|
Минимальное покрывающее дерево |
|
|
Послойная кластеризация |
В таблице 2 приведен сравнительный анализ алгоритмов.
Таблица 2 – Сравнительный анализ алгоритмов
|
Алгоритм кластеризации |
Форма кластеров |
Входные данные |
Результаты |
|
1 |
2 |
3 |
4 |
|
Иерархический |
Произвольная |
Число кластеров или порог расстояния для усечения иерархии |
Бинарное дерево кластеров |
|
k-средних |
Гиперсфера |
Число кластеров |
Центры кластеров |
|
c-средних |
Гиперсфера |
Число кластеров, степень нечеткости |
Центры кластеров, матрица принадлежности |
|
Выделение связных компонент |
Произвольная |
Порог расстояния R |
Древовидная структура кластеров |
|
Минимальное покрывающее дерево |
Произвольная |
Число кластеров или порог расстояния для удаления ребер |
Древовидная структура кластеров |
|
Послойная кластеризация |
Произвольная |
Последовательность порогов расстояния |
Древовидная структура кластеров с разными уровнями иерархии |
В дипломной работе для анализа данных, полученных в результате проведения эксперимента, будем использовать кластеризацию методом к-средних.
Метод к-средних основан на минимизации суммы квадратов расстояний между каждым элементом исходных данных и центром его кластера, т.е. функции
где где – метрика, - i-ый элемент данных, а -центр кластера, которому на j-ой итерации приписан элемент .
Алгоритм состоит из следующим шагов:
1) случайно выбрать k-точек, являющихся начальными «центрами масс» кластеров (любые k из n объектов, или вообще k случайных точек);
2) отнести каждый объект к кластеру с ближайшим «центром масс»;
3) пересчитать «центры масс» кластеров согласно текущему членству;
4) если критерий остановки алгоритма не удовлетворен, вернуться к шагу 2.
В качестве критерия остановки обычно выбирают один из двух:
1) отсутствие перехода объектов из кластера в кластер на шаге 2;
2) минимальное изменение среднеквадратической ошибки.
Алгоритм к-средних крайне чувствителен к выбору начальных приближений центров. Случайная инициализация центров на шаге 1 может приводить к плохим результатам кластеризации. Для формирования начального приближения лучше выделить k наиболее удалённых точек выборки: первые две точки выделяются по максимуму всех попарных расстояний; каждая следующая точка выбирается так, чтобы расстояние от неё до ближайшей уже выделенной было максимально.
Кластеризация может оказаться неадекватной и в том случае, если изначально будет неверно угадано число кластеров. Стандартная рекомендация — провести кластеризацию при различных значениях k и выбрать то, при котором достигается резкое улучшение качества кластеризации по заданному функционалу.
Достоинство алгоритма k-средних:
1) простота реализации;
2) интуитивная понятность и прозрачность алгоритма.
Недостатки алгоритма:
1) число кластеров надо знать заранее;
2) зависимость результата от инициализации центров кластеров;
3) вычислительная сложность
Анализ данных, полученных в результате проведения эксперимента, выполнен с помощью пакета «Statistica» по методу к-средних. В эксперименте участвовали 32 информанта. Экспериментатор перед проведением эксперимента выделил на картине 32 объекта. В результате проведения эксперимента был получен набор переходов по картине для каждого информанта, а также вербальный текст-описание. Данные по всем информантам были объединены в одну таблицу. Из полученной таблицы был выбран набор данных, содержащий наиболее частотные переходы по картине. Если мы будем рассматривать весь набор данных, то алгоритм к-средних в результате работы даст неадекватные результаты. Урезанный набор значений для всех информантов был проанализирован несколькими способами.
Было проведено последовательное разбиение на три, четыре, пять и шесть кластеров. Проанализировав результаты кластеризации видим, что разбиение множества информантов на четыре кластера оптимально, т.к. интерпретация наиболее логична и непротиворечива.
В результате разбиения был построен график средних для каждого кластера в пакете Statistica, представленный на рисунке 23.
Рисунок 23 – График средних для каждого кластера
Для анализа результатов удобно использовать описательную статистику по каждому из кластеров, представленную в приложении А. На основе полученных данных были определены наиболее частотные переходы в каждом из кластеров.
Наиболее частыми в первом кластере являются следующие переходы, представленные на рисунке 24:
1) Иоанн Креститель – Иисус Христос;
2) Иисус Христос – Иисус Христос;
3) Отец – Сын;
4) Иоанн Креститель – Группа апостолов;
5) Легионеры на лошадях – Иисус Христос.
После визуализации наиболее частых переходов видим, что при рассматривании картины информантов заинтересовал переход от фигуры Крестителя, стоящего на переднем плане, к Иисусу, стоящему на заднем плане картины. Жестовая артикуляция Крестителя обращена к центральной фигуре картины – фигуре Иисуса Христа. Также можем отметить, что при рассматривании объектов картины задействованы верхнее и нижнее золотое сечение.
В состав первого кластера вошли: информант 2, информант 4, информант 5, информант 6, информант 10, информант 12, информант 13, информант 18, информант 22, информант 26, информант 31.
Рисунок 24 – Наиболее частые переходы первого кластера
Наиболее частыми во втором кластере являются следующие переходы, представленные на рисунке 25:
1) Хозяин-Раб;
2) Иисус Христос-Иоанн Креститель;
3) Отец – Сын;
4) Иоанн Креститель-Хозяин;
5) Раб-Хозяин.
После визуализации выделенных переходов, а также на основе вербальных текстов информантов можно сказать следующее. Из текстов видим, что описание по картине в основном идет слева направо, информантов интересуют объекты переднего плана, находящиеся в явных отношениях социально-духовной иерархии. В данном случае можно отметить также отношения, которым информанты уделили внимание:
1) переход Хозяин – Раб символизирует иерархические социальные отношения, принадлежность разным социальным классам;
2) переход Отец – Сын символизирует иерархические социальные отношения, сложившиеся в семейной сфере;
3) переход Христос – Креститель символизирует отношение духовной иерархии.
В состав второго кластера вошли: информант 3, информант 19, информант 21, информант 23, информант 24, информант 30.
Рисунок 25 – Наиболее частые переходы второго кластера
Наиболее частые в третьем кластере являются следующие переходы, представленные на рисунке 26:
1) Иисус Христос-Иоанн Креститель;
2) Иоанн Креститель-Иисус Христос;
3) Иоанн Креститель-Крест;
4) Иоанн Креститель-Группа апостолов.
Можем заметить, что в левой части картины изображены ближайшие сподвижники Иисуса Христа, на заднем плане правой части картины изображены враги. Частые переходы объектов изображены на картине, охватывают атрибут веры, субъектные (Христос, Креститель, апостолы) и атрибутные (крест) доминанты христианской веры.
В состав третьего кластера вошли: информант 1, информант 14, информант 15, информант 20, информант 27, информант 28, информант 29.
Рисунок 26 – Наиболее частые переходы третьего кластера
Наиболее частые в четвертом кластере являются следующие переходы, представленные на рисунке 27:
1) Иоанн Креститель-Иисус Христос;
2) Иисус Христос-Иоанн Креститель;
3) Легионеры на лошадях-Иисус Христос;
4) Иисус Христос-Группа фарисеев;
5) Иисус Христос-Иисус Христос;
6) Иордан-Иисус Христос;
7) Группа апостолов-Иисус Христос;
8) Группа фарисеев-Иисус Христос.
Частые переходы четвертого кластера символизируют попытку информантов разобраться в сложных отношениях к Христу всех участников картины. Фокус интерпретации сосредоточен на фигуре Иисуса.Указываются сторонники и «противники» веры. Слева группа апостолов – будущие ученики Христа. Иоанн играет роль указывающего на фигуру мессии. Иордан – священная река, в которой осуществлялся обряд крещения Иисуса. Лица фарисеев выражают недоверие и злую иронию. На заднем плане легионеры, надзирающие за поведением верующим людей, в тоже время, обращают внимание на приближающуюся фигуру Христа.
В состав четвертого кластера вошли: информант 7, информант 8, информант 9, информант 11, информант 16, информант 17, информант 25, информант 32.
Рисунок 27 – Наиболее частые переходы четвертого кластера
Заключение
В результате выпускной квалификационной работы была разработана технология анализа процесса понимания текстов графического типа. Осуществлена реализация информационная система реконструкции когнитивных паттернов восприятия графических текстов в виде
web-приложения. При разработке использовался фреймворк Grails, весь функционал серверной части информационной системы был написан на языке программирования Groovy, функционал клиентской части был написан на языке программирования javascript с использованием библиотек jQuery.js, underscore.js, backbone.js, raphael.js.
Была проведена обработка информации, полученной в результате прохождения эксперимента информантами, с помощью пакета «Statistica».
Разработанная информационная система удобна в использовании и интуитивно понятна. В перспективе предполагается создание отдельного модуля, который позволит обрабатывать информацию, полученную в результате прохождения эксперимента. Также предполагается интеграция с системой чтобы полученные в результате эксперимента тексты информантов проходили соответствующую обработку и анализ
Список использованных источников
1 Немов, Р. С. Психология: Учеб. для студ. высш. пед. учеб. Заведений: В 3 кн. — 4-е изд. — М.: Гуманит. изд. центр ВЛАДОС, 2003. - Кн. 1: Общие основы психологии. — 688 с.
2 Ярбус, А. Л. Роль движений глаз в процессе зрения. – М.: Наука, 1965. – 167 с.
3 Петренко, В. Ф. Психосемантика сознания. – М.: Изд-во Моск. гос. Ун-та, 1988. – 208 с.
4 Артемьева, Е. Ю. Основы психологии субъективной семантики / Под ред. И. Б. Ханиной. М.: Наука, Смысл, 1999. – 350 с.,
5 Серкин, В. П. Методы психологии субъективной семантики и психосемантики: Учебное пособие для вузов / В. П. Серкин. — М.: Издательство ПЧЕЛА, 2008. — 382 с.
6 Демьянков, В.З. Понимание как интерпретирующая деятельность // Вопросы языкознания. М., 1983. № 6. С.58–67.
7 Барабанщиков, В. А. Восприятие индивидуально-психологических особенностей человека по изображению целого и частично открытого лица / В. А. Барабанщиков // Экспериментальная психология, 2008. – № 1. С. 62–83.
8 Барабанщиков, В. А. Исследование восприятия эмоционального состояния человека по выражению лица / В. А. Барабанщиков, Т. Н. Малкова // Проблема общения в психологии. М.: Наука, 1981. – С.121–132.
9 Демидов, В. Е. Как мы видим то, что видим / В. Е. Демидов. – М., «Знание», 1979. 208 С. (Наука и прогресс).
10 Davis, S. Getting started with Grails. Second edition. / S. Davis,
J. Rudolph – C4Media Inc, 2010. – 148 с.
11 Смит, Г. Grails. Гибкость Groovy и надежность Java. / Г. Смит, П. Ледбрук: Пер. с англ. – СПб.: Символ-Плюс, 2010. – 656 с.
12 Smith, G. Grails in action. / G. Smith, P. Ledbrook – Manning Publications, 2009. – 536 c.
13 Christopher, M. Beginning Groovy and Grails: From Novice to Professional. / M. Christopher, J. Shingler – Apress, 2008. – 742 c.
14 Кулаичев, А. П. Методы и средства комплексного анализа
данных. — М: ИНФРА-М, 2006. – 375 с.
15 Мандель, И.Д. Кластерный анализ. – М.: Финансы и статистика,
1988. – 176 с.
16 Айвазян, С.А. Прикладная статистика: Классификация и снижение размерности. / С.А. Айвазян, В.М. Бухштабер, И.С. Енюков,
Л.Д. Мешалкин – М.: Финансы и статистика, 1989. – 607 с.
17 Уиллиамс, У. Т. Методы иерархической классификации // Статистические методы для ЭВМ / Под ред. М. Б. Малютов.— М.: Наука,
1986. – С. 269–301.
18 Олдендерфер, М.С. Кластерный анализ / Факторный, дискриминантный и кластерный анализ: пер. с англ.; Под. ред. И.С. Енюкова. - М.: Финансы и статистика, 1989 — 215 с.
19 Жамбю, М. Иерархический кластер-анализ и соответствия. – М.: Финансы и статистика, 1988. – 345 с.
20 Бибо, Б. jQuery. Подробное руководство по продвинутому
javascript. / Б. Бибо, И. Кац. – Символ-Плюс, 2009. – 384 с.
21 Гудман, Д. javascript. Библия пользователя. / Д. Гудман,
М. Моррисон. – Вильямс, 2006. – 1184 с.
22 Флэнаган, Д. javascript. Подробное руководство. – Символ-Плюс, 2008. – 992 с.
Приложение А
Описательная статистика результатов разбиения множества информантов на четыре кластера
Рисунок А.1 – Описательная статистика первого кластера
Рисунок А.2 – Описательная статистика второго кластера
Рисунок А.3 – Описательная статистика третьего кластера
Рисунок А.4 – Описательная статистика четвертого кластера
Скачать: