3. ПОСТРОЕНИЕ АССОЦИАТИВНОГО ТЕЗАУРУСА

3. ПОСТРОЕНИЕ АССОЦИАТИВНОГО ТЕЗАУРУСА

3.1. Передача словаря из БД, расчет ассоциативных связей и оценка эффективности меры

Передача прямого ассоциативного словаря из БД в модуль построения ассоциативного тезауруса

Построение "компактного" словаря в БД.

Под "компактным" словарем понимается словарь, в котором все вербальные (текстовые) значения полей заменены на числовые коды, т.е. "компактный" словарь содержит всю информацию ассоциативного словаря, но в числовом виде:

<код стимула><код реакции><частота проявления данной ассоциативной пары>

Для его получения нужно: 1) придать каждому слову-реакции собственный код; 2) подсчитать частоту проявления каждой ассоциативной пары; 3) сформировать компактный прямой ассоциативный словарь (числовой ассоциативный словарь).

Кодирование слов-реакций. Сначала создается таблица code_reac_freq (код реакции, слово-стимул, частота проявления данной реакции) путем извлечения из таблицы association нужной информации. Это делается запросом export_assoc, который создает таблицу assoc_only, содержащую множество пар "код стимула, слово-реакция":

export_assoc:

SELECT          association.code_stimulus,

                         association.mot_reaction

INTO               assoc_only

FROM             association

WHERE          (((association.mot_reaction)<>»»));

Затем запускаются запросы make_crf_1 (построить "код_реакция_частота_1"), который вызывает служебные запросы assoc_only_1 и assoc_only_1sub, и make_crf_2, вызывающий assoc_only_2.

Запрос make_crf_1 начинает заполнять code_reac_freq ассоциативными парами, которые проявляются больше одного раза. Запрос make_crf_2 дополняет code_reac_freq ассоциативными парами, которые проявляются ровно один раз. Такое разделение является следствием различия соответствующих операций.

Запрос assoc_only_1sub готовит данные для assoc_only_1, выбирая те ассоциативные пары (код стимула, слово-реакция), которые проявляются больше одного раза:

  assoc_only_1sub

  SELECT DISTINCTROW

    assoc_only.mot_reaction,

    assoc_only.code_stimulus

  FROM

    assoc_only

  WHERE ((

    (assoc_only.mot_reaction)

In

    (SELECT

 [mot_reaction]

     FROM

 [assoc_only] As Tmp

     GROUP BY

 [mot_reaction]

     HAVING

 Count(*)>1 )))

  ORDER BY

    assoc_only.mot_reaction;

Запрос assoc_only_1 группирует этот результат по словам-реакциям и подсчитает частоту проявления пар:

  assoc_only_1

  SELECT DISTINCTROW

    First([mot_reaction]) AS [mot_reaction поле],

    Count([mot_reaction]) AS Повторы

  FROM

    assoc_only_1sub

  GROUP BY

    [mot_reaction]

  HAVING Count([mot_reaction])>1;

Запрос make_crf_2 работает так же, но не использует операцию, реализованную запросом assoc_only_1.

В результате получается таблица code_reac_freq:

1	"ы"	5
2	—	1644
3	Чернобыль	3
4	чернила	5
5	черта	3
6	чертеж	2
7	человек	37
8	человека	2
9	чайник	4
10	чемодан	3
11	часть	2
12	часы	2
13	чинить	3
14	…

Подсчет частот проявления ассоциативных пар. Такой подсчет осуществляется запросом calc_freq_assoc ("calculate frequency associative pairs"). Он группирует ассоциации по коду стимула и слову-реакции, а затем вычисляет значения частот:

calc_freq_assoc

SELECT DISTINCTROW

  First(association.code_stimulus) AS code_stim,

  First(association.mot_reaction) AS mot_reac,

  Count(association.code_stimulus) AS freq_assoc

FROM

  stimulus

INNER JOIN

  association

ON

  stimulus.code_stimulus = association.code_stimulus

GROUP BY

  association.code_stimulus,

  association.mot_reaction

HAVING

  (((First(association.mot_reaction))<>»»));

Формирование числового ассоциативного словаря. Запрос ddcompact должен выдать список "код стимула / код реакции / частота данной ассоциативной пары". Для этого нужны значения полей "код реакции" из таблицы code_reac_freq и "частота" из таблицы calc_freq_assoc. Кроме этого для нормализации частоты, т.е. преобразования ее в процент проявления данной реакции по отношению к общему количеству ассоциаций на данный стимул, нужно поле "число ассоциаций" — nrd из таблицы t_nbr_reac_diff.

ddcompact

SELECT

  calc_freq_assoc.code_stim,

code_reac_freq.code_reac,(100*[calc_freq_assoc].[freq_assoc])

\[t_nbr_reac_diff].[nrd] AS pourcent

FROM

  t_nbr_reac_diff

INNER JOIN

  (code_reac_freq

   INNER JOIN

     calc_freq_assoc

ON

     code_reac_freq.mot_reac = calc_freq_assoc.mot_reac)

ON

t_nbr_reac_diff.cs = calc_freq_assoc.code_stim

WHERE ((

  ((100*[calc_freq_assoc].[freq_assoc])\[t_nbr_reac_diff].[nrd])>=0)

AND

  ((calc_freq_assoc.freq_assoc)>0) AND ((calc_freq_assoc.mot_reac)<>»-»));

Структура данных "ассоциативный словарь" associative_ dictionary

Данные об ассоциативном словаре используются модулем построения тезауруса. В этом модуле ассоциативный словарь представлен в специальном виде, который обеспечивает эффективность построения тезауруса. Кроме этого к данным ассоциативного словаря имеет доступ программа оценки сил связи, которая функционирует на основе меры связи, разрабатываемой исследователем, поэтому их структура должна быть создана так, чтобы было легко в ней разобраться.

Разработанная структура данных типа associative_dictionary предоставляет возможность работать с ней не только как с числовым образом ассоциативного словаря, полученным от ddcompact, но и как с его полным описанием, т.е. со всеми словами, если это нужно. Имеются следующие классы:

· класс word (слово), содержащий код слова и поле для текста самого слова;

· класс reaction (реакция), снабженный полями "код реакции" и "частота проявления данного слова-реакции на данный стимул";

· класс ad_article (словарная ассоциативная статья), состоящий из кода стимула и списка соответствующих реакций (списка объектов типа "reaction");

· класс associative_dictionary (ассоциативный словарь) имеет в качестве атрибутов код, имя, и три списка: список слов-стимулов типа word, список слов-реакций типа word, и список словарных ассоциативных статей типа ad_article. Он может загрузить файл, который передается от запроса ddcompact (метод load).

Импорт словаря из БД

Процедура load открывает указанный файл, читает каждую строку этого файла и анализирует его (процедура line_analyzer). При этом заполняются списки стимулов и реакций, так же как первичный список статьей articles_dummy. Этот первичный список нужно обработать (упорядочить), чтобы сформировать конечный список словарных статей list_articles. Эту обработку (упорядочение) совершает служебная процедура make_list_articles, вызывающаяся самим методом load.

Расчет ассоциативных связей

После загрузки и преобразования во внутреннюю форму ассоциативного словаря можно вычислить силы связи между стимулами и вставить эти величины в матрицу сил связи.

Класс measure (мера)

Этот класс является виртуальным, позволяющим только именовать меру и придать ей код, но ее метод float d (ad_article, ad_article) — расчет ассоциативной силы связи на базе сравнения двух словарных ассоциативных статей — исследователь должен написать в специальном файле plug_in.hpp, как свой класс, наследующий встроенному классу measure. В частности, исследователю надо написать свою собственную процедуру d().

Классы symmatrix (симметричная матрица) и matrix_links (матрица связей)

Множество значений

{d(i,j), (i,j) Î {1..N}2}

удобно представить в виде симметричной матрицы. Класс symmatrix (симметрическая матрица) обобщенный (generic) и в основном предлагает методы get(i,j,x) и set(i,j,x) для чтения/записи из/в матрицу.

Специальный класс matrix_links (матрица связей) наследует классу symmatrix. Класс matrix_links снабжен инструментами для работы с ассоциативными связями.

Заполнение матрицы сил связи

Класс matrix_links имеет следующую конструкцию:

matrix_links(const associative_dictionnary &, const measure &).

Конструкция позволяет автоматически построить матрицу сил связи при задании объектов "ассоциативный словарь" и "мера". При этом сначала резервируется память на Nґ(N—1)/2 для чисел типа float, затем запускается служебная процедура compute (associative_dictionnary, const measure &), которая применяет меру на каждую пару словарных статей и сохраняет результат в соответствующей ячейке матрицы.

Просмотр ассоциативных связей

Исследователю в процессе построения меры связи, как правило, требуется поэтапно настраивать ее параметры, кроме этого необходимо иметь возможность просмотреть результаты ее работы, чтобы узнать, какие связи были установлены и между какими словами-стимулами, и чтобы проверить, соответствуют ли эти связи каким-нибудь смысловым отношениям.

С этой целью готовится документ, показывающий для каждого слова-стимула, какие другие слова-стимулы с ним связаны и с какой силой. Этот документ разрабатывается в БД и автоматически дорабатывается в текстовом редакторе для его наиболее наглядного представления.

Импорт матрицы в БД

Класс matrix_links содержит процедуру для сохранения матрицы сил связи в файл в таком формате, который позволяет его импортировать в базу данных (процедура save_full()). Сама база данных загружает этот файл в таблицу matrix. Матрица сил связи является симметричной, поэтому в файле есть только N´ (N–1)/2 значений меры μ(i,j). Для удобства обработки матрицы в таблицу matrix с помощью запроса sym_matrix добавляются еще N´ (N–1)/2 значений симметричных сил связи μ(j,i).

Составление списка связанных стимулов "svyazi"

Отчет "svyazi" позволяет построить документ, содержащий список слов-стимулов, имеющий следующую структуру:

заголовочное слово—стимул / (связанный стимул1, частота1), (связанный стимул2, частота2), …

Этот документ базируется на работе запроса "svyazi", для каждого слова-стимула указывающего только те слова, для которых мера имеет ненулевое значение силы связи.

svyazi

SELECT

  stimulus.mot AS mot1,

  [stimulus_1].[mot] & ", \\+^p\\" AS mot2,

  matrix.f

FROM

  stimulus AS stimulus_1

INNER JOIN

  (stimulus

   INNER JOIN

     matrix

ON

     stimulus.code_stimulus = matrix.i)

ON

  stimulus_1.code_stimulus = matrix.j

WHERE ((

  (matrix.f)>0)

AND

  ((stimulus.code_stimulus)=[matrix].[i])

AND

  ((stimulus_1.code_stimulus)=[matrix].[j]));

Для получения печатного документа из отчета "svyazi" используется такая же технология экспорта и обработки в среде MicroSoft Word, которая применяется для верстки прямого ассоциативного словаря.

3.2. Проектирование меры связи

Предложение меры связи. Мера "svyaz_M"

Выбранный подход для оценки силы связи между стимулами заключается в обнаружении общих реакций на оба сравниваемых слова-стимула и в вычислении значения меры силы связи (или "сходства", или же "близости") между этими стимулами по некоторому правилу. Например, если респонденты отвечали словом-реакцией "изображение" 3 раза на слово-стимул "цветоделение" и 4 раза на слово-стимул "растр", то это значит, что слово-стимул "цветоделение" и слово-стимул "растр" связаны между собой некой силой, которая является функцией обеих частот встречаемости.

Разработанная мера сходства построена следующим образом: для каждой общей реакции рассчитывается значение некой функции пары частот проявления реакции на каждый стимул. Эта функция симметричная, возрастающая и по каждой отдельной частоте, и по близости частот друг с другом. Итак, если f и f' — частоты проявления некоторой общей реакции как ответ на сравниваемые стимулы, то эта функция M(f,f') рассчитывается как отношение средней величины f и f' к расстоянию между f и f'. Значение меры сходства — это сумма значений M для каждой общей реакции.

Теперь опишем формально, как построена эта мера: пусть S — множество N слов-стимулов и (s,s')Î S² — пара сравниваемых стимулов. В ассоциативном словаре указаны соответствующие списки пар (реакция,частота):

Δ_s={(r₁,f₁)),…,(r_n,f_n)},

Δ_s'={(r₁',f₁')),…,(r_n',f_n')}.

Назовем π_ss’ "пересечением" ассоциативных дефиниций s и s’.

где p — число общих реакций на s и s’.

Тогда можно выбрать в качестве меры оценки силы связи критерий:

где α — вес среднего значения частот, β — вес близости частот.

Эта мера сначала была применена со значениями (α,β) = (1,1).

Улучшение меры связи. Мера "svyaz_MPS"

Для оценки результатов применения этой меры сходства был составлен для каждого стимула список связанных стимулов (документ "svyazi"). Так были выявленные отношения, не лишенные смысла, и в основном их можно считать удовлетворительными. Однако наблюдаются следующие недостатки:

1. В расчете учитываются абсолютные частоты встречаемости реакций (число раз, когда респонденты отмечали данное слово-реакцию). Но не учтено число ответов-пропусков (число раз, когда респонденты не отвечали на стимул).

2. То, что лемматизация слов-реакций не проводилась, безусловно, ослабляет связи. Например, одна статья ассоциативного словаря выглядит так:

АВТОМАТИЗАЦИЯ – (7:) производства, процесса (3:) процесс, процессов, управление, управления.

Мера связи должна учитывать парадигму слов-реакций.

3. Методика приводит к потере информации из-за того, что сравниваются лишь списки реакций. А часто бывает, что слово-стимул используется в качестве реакции. Из этого следует, что получается недопустимо слабая связь между, например, "клавиша" и "клавиатура". Мера μ(клавиша,клавиатура)=1, хотя почти 25% опрошенных отвечали "клавиатура" на стимул "клавиша". Мера μ просто не учитывает такую информацию.

4. Допустим, что проведена лемматизация. Тогда оказывается, что частота реакции "управление" на стимул "автоматизация" равна 6. А на "джойстик" также отвечали 6 раз "управление". Таким образом, M(6,6)=12. А если изменить хотя бы немного одну частоту, M резко падает: M(5,6)=5,5.

5. Заметим, что получаются удивительные отношения. Например, "джойстик"—"автоматизация". Связь становится понятной только тогда, когда выясняется, что она была установлена, потому что существует общая реакция "управление". "Управление" имеет синтагматическое отношение с "автоматизация" (в словосочетании "автоматическое управление"), а с "джойстик" — парадигматическое (отношение цель—способ реализации). Однако такую связь устранить (если в этом есть необходимость) можно только вручную.

6. Другие "странные", на первый взгляд, отношения можно устранить, или по крайней мере ослабить, автоматически: это те, которые основаны на присутствии общей реакции, лишенной смысла. Например, слово "компьютер" является в нашем эксперименте пустым ответом: оно может служить реакцией на любой стимул, несмотря на то (или потому), что оно не носит никакого смысла. Из-за злоупотребления этим словом устанавливаются сильные связи "вирус"—"драйвер", "вирус"—"дисплей" и т.д. Если удалить слово "компьютер" из списка реакций на эти слова-стимулы, то такие связи вообще не существовали бы.

Ниже предложены способы исправления этих недостатков.

1. Вместо абсолютных частот встречаемости f можно учитывать относительные частоты или , где σ — количество ассоциаций на данный стимул, v — число пропусков. Имеется .

2. Кажется целесообразным подвергнуть слова-реакции лемматизации. Методика свертки, которая сводится к устранению гласных слова (кроме в первом слоге), может оказаться достаточной. В самом общем случае следовало бы рассмотреть различные методы лемматизации и выбрать наиболее приемлемые.

3. Рекомендуется особо учитывать "суперсвязи" —те реакции, которые представляют собой непосредственную ссылку к некоторому стимулу. Существование такой "суперсвязи" должно приводить к увеличению значения меры сходства. Однако следует заметить, что такая "суперсвязь" оказывается несимметричной, направленной (например, стимул "удаленный" вызывает реакцию "файл", а стимул "файл" не вызывает реакцию "удаленный"). Предлагается рассчитывать долю "суперсвязи", не деля среднее значение частот на их близость (коэффициент β = 0 для "суперсвязи").

4. Следует управлять значениями параметров α и β. Вес близости частот β должен быть меньше веса среднего значения частот α. Условно предлагаем α/β = 5.

5. Можно было бы подсчитать общее число проявлений каждой реакции V(r) и учитывать частоту реакций в мере сходства — чем чаще слово используется, тем слабее его значение.

С учетом всех этих замечаний, новая мера сходства выглядит следующим образом:

Для настройки достаточно определить параметры α/β и γ. Нужно следить за тем, чтобы значения оставались в диапазоне, соответствующем возможностям употребляемой мантиссы в компьютерной программе.

Инструменты для меры "svyaz_MPS"

Код меры связи "svyaz_MPS" без тел процедур имеет следующий вид:

class svyaz_MPS:public svyaz_M

        protected:

        int **popularite;

        int **superlinks;

        int pop_size;

        int sl_size;

        public:

        float alpha=1;

        float beta=.2;

        float gamma=.2;

        int find_pop(int code_stim);

        float d(ad_article ad1,ad_article ad2);

        void show();

        int load_popularite(char *fpop);

        int load_superlinks(char *fsl);

        svyaz_MPS(float alpha_,float beta_,float gamma_):svyaz_M(alpha_,beta_);

        svyaz_MPS(const int x,const char *s,float alpha_,float beta_,float gamma_)

        :svyaz_M(x,s,alpha_,beta_);

        ~svyaz_MPS();

};

Заметим, что этот класс содержит два метода (load_popularite() и load_superlinks()), позволяющих загрузить дополнительную информацию о реакциях: таблицы popularite ("популярность", т.е. V(r)) и superlinks (суперсвязи). Схема его реализации приведена на риc. 6.

Файл, содержащий суперсвязи, экспортируется из таблицы superlinks базы данных.

Запрос cree_stimstar (создать "stimstar") создает таблицу stimstar, добавляя слева и справа от каждого слова-стимула по символу "звездочка", таким образом, чтобы, например, система считала реакцию "звуковой" непосредственной ссылкой на стимул "звук", ведь предикат ["звуковой" Like "*звук*"] истинный.

cree_stimstar

SELECT

  stimulus.code_stimulus,

  "*" & [mot] & "*" AS motstar

INTO

  stimstar

FROM

  stimulus;

Запрос на создание таблицы superlinks, которая связывает реакции со сходными им стимулами, сравнивает каждое слово-реакцию из code_reac_freq с образцами из stimstar.

cree_superlinks

SELECT

  code_reac_freq.code_reac,

  stimstar.code_stimulus,

  code_reac_freq.mot_reac,

  stimulus.mot

INTO

  superlinks

FROM

  code_reac_freq,

  stimstar

INNER JOIN

  stimulus

ON

  stimstar.code_stimulus = stimulus.code_stimulus

WHERE

  (((code_reac_freq.mot_reac) Like [stimstar].[motstar]));

Однако после выполнения данного запроса необходимо вручную удалить ошибочные строки: например, слово "окно" как последовательность букв находится в слове "оптоволокно", так что запрос выявляет такую суперсвязь "оптоволокно —> окно".

Ниже представлено образец этой таблицы:

Код реакции	Код стимула	Слово-реакция	Слово-стимул
61	2	Алгоритм	алгоритм
66	3	Антивирус	антивирус
69	4	Архив	архив
71	118	Архивировать	архивировать
73	5	база данных	база данных
75	6	Байт	байт
86	8	Бит	бит
101	34	В компьютере	компьютер
119	9	Видеоадаптер	видеоадаптер
122	10	Винчестер	винчестер
123	10	Винчестера	винчестер
124	11	Вирус	вирус
128	34	Внутри компьюте-ра	компьютер
161	12	Гарнитура	гарнитура
163	13	Гибкий диск	гибкий диск
179	15	Данные	данные
194	16	Джойстик	джойстик
201	18	Диск	диск
202	18	Диска	диск

Мера "svyaz_MPS" использует и другие данные: она читает файл, составленный из списка частот встречаемости реакций, который создается запросом "popularite". На самом деле он предоставляет и эту частоту, и частоту другого типа, условно называемую "популярность" — число слов-стимулов, в ассоциативных дефинициях которых встречается данная реакция.

popularite

SELECT

  code_reac_freq.code_reac,

  code_reac_freq.mot_reac,

  code_reac_freq.freq,

  Count(ddcompact.code_stim) AS popularite

FROM

  code_reac_freq

INNER JOIN

  ddcompact

ON

  code_reac_freq.code_reac = ddcompact.code_reac

GROUP BY

  code_reac_freq.code_reac,

  code_reac_freq.mot_reac,

  code_reac_freq.freq,

  ddcompact.code_reac

HAVING

  (((ddcompact.code_reac)=[code_reac_freq].[code_reac]));

В результате выполнения запроса получается таблица, представленная на рис. 7.

Рис.7

3.3. Подготовка данных к кластерному анализу

Поиск независимых подсетей проходом по цепочкам ненулевых связей

Цепочка связей

Напоминаем, что речь здесь идет об обнаружении отдельных подмножеств (подсетей), имеющих следующие свойства: во-первых, между двумя словами, принадлежащими одной и той же подсети, существует последовательность слов, связанных ненулевой силой; во-вторых, между двумя словами, принадлежащими разным подсетям, связь нулевая и не существует последовательности слов, связанных ненулевой силой.

Последовательности слов, связанных друг с другом ненулевым значением меры оценки силы ассоциативной связи, будем называть цепочками.

Функционирование метода разделения множества стимулов на подсети matrix_links::separate()

Сначала опишем роль служебного класса perevodtchik:

Класс perevodtchik ("переводчик") — это таблица, которая инициируется с последовательностью от 0 до max_size. Процедура disable() позволяет удалить из последовательности одно из этих чисел. Процедура I(i) выдает i-й элемент таблицы.

Если P — объект типа perevodtchik и M — матрица, то сначала M(P.I(i),P.I(j)) = M(i,j) для любой пары (i,j). А операция P.disable(k) логически удаляет k-ю строку и k-й столбец матрицы.

Итак, обращение к матрице через "переводчик" позволяет поэтапно вычеркивать строки, такая последовательность операций необходима во избежание замыканий при построении цепочки.

Функционирование метода разделения множества стимулов на подсети matrix_links::separate():

Процедура создает таблицу для хранения очередной подсети и туда записывает как первый элемент значение P.I(0). Вызов процедуры group() приносит в эту таблицу все связанные элементы и изменяет внутреннюю таблицу "переводчика", так как по ходу формирования подсети осуществлялось логическое удаление найденных элементов с помощью P.disable().

int matrix_links::separate(chained_list &tlist)

  int retval=0;

  int newelem;

  perevodtchik P(size);

  while (P.get_size())

    ordtable newtable(P.get_size());

    newelem=P.I(0);

    newtable.put(newelem);

    P.disable(newelem);

    group(P,newtable,newelem);

    tlist.add_tail(newtable);

};

  return retval;

Параметрами процедуры matrix_links::group() являются perevodtchik P, ordtable table и int daddy. Структура данных ordtable инкапсулирует упорядоченную таблицу целых чисел, и предоставляет инструменты записи и чтения.

Рекурсивная процедура group() находит все элементы, связанные ненулевым значением с текущим элементом daddy, записывает их в таблице table, вычеркивает daddy-ю строку (и тем самым daddy-й столбец, так как матрица симметричная) и последовательно запускает себя на найденные элементы.

int matrix_links::group(perevodtchik &p,ordtable &table,int daddy)

  int retval=0;

  int i;

  float a;

  int put_ret;

  ordtable littletable(p.get_size());

  for (i=0;i0.0)

put_ret=table.put(p.I(i));

if (put_ret>-1)

  littletable.put(p.I(i));

};

};

    if (littletable.get_size())

    int sony;

    for (i=0;i <  littletable.get_size();i++)

littletable.get(i,sony);

p.disable(sony);

group(p,table,sony);

};

};

    return retval;

};

Итак, в результате работы метода matrix_links::separate() имеются подсети стимулов, которые уже составляют разбиение. Если оно считается достаточным, то не нужно использовать прочие инструменты, т.е. инструменты для проведения кластерного анализа.

Заметим, что в наших экспериментальных данных подсетей как таковых не нашлось. Это значит, что любые два слова-стимула соединены какой-нибудь цепочкой.

Установление псевдосвязей

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

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

Предложение функции оценки цепочки

//функция оценки цепочки связей delta0, delta1, ...

//Значения связи содержатся в объекте path.

float path_value(const path &p)

  float pv;

  float a=0.7;     //коэффициент [<1]   float b=1.5;     //экспонент величины 1/(длины_цепочки) [>1]

  float delta,deltamax,sum;

  sum=0;

  deltamax=0;

  int i;

      //расчет суммы связей цепочки (sum)

     //и поиск самой сильной связи(deltamax)

  for (i=0;ideltamax)

deltamax=delta;

    sum+=delta;

};

  pv=a*pow(p.size,-b)*sum/deltamax;

  return pv;

};

Функционирование метода расчета псевдосвязи между двумя словами-стимулами

Процедура matrix_links::psl() выдает значение псевдосвязи между стимулами i и j в результате построения всех возможных цепочек и выбора той, которая имеет самую низкую оценку.

Цепочка от слова i к слову j получается следующим образом: либо ненулевым является элемент матрицы (i,j), и процесс закончен; либо существует ненулевой элемент (i,k), тогда k записывается как очередной элемент цепочки, вычеркивается k-я строка матрицы и запускается процесс на нахождение цепочки между словами k и j.

Предусмотрен способ ограничения поиска самой лучшей цепочки: текущая цепочка не должна быть длиннее самой короткой из уже рассмотренных.

int matrix_links::psl(int i,int j,perevodtchik P,path putj,

     float path_value(const path &),int max_pathlen,float &best_link)

  int retval=0;

  if (putj.size>max_pathlen)

    //конец рекурсии: достигнута максимальная допустимая длина цепочки.

    //Текущая цепочка отбракуется.

  else if (i==j)

    //конец рекурсии. Дошли до j.

    float my_link;

    //оценка цепочки:

    my_link=path_value(putj);

    if (my_link < best_link)

best_link=my_link;

  else

    //очередной шаг вперед

    float d;

    int k;

    path newputj(putj.maxsize);

    int vsize;

    P.disable(i);

    vsize=P.get_size();

    for (k=0;k < vsize;k++)

//читать каждое значение силы связи с остальными объектами, запустить psl

get(i,P.I(k),d);

if (d!=0)

  newputj=putj;

  newputj.add(d);

  //рекурсивный вызов

  psl(P.I(k),j,P,newputj,path_value,max_pathlen,best_link);

};

};

};

  return retval;

Модуль установления псевдосвязей

Оперативную процедуру psl вызывает метод установления псевдосвязи между двумя стимулами float pseudolink([стимул1], [стимул2], [функция оценки цепочки]). Пользователь запускает весь процесс путем вызова процедуры matrix _ links::set _ pseudolinks([функция оценки цепочки]), которая из матрицы Z, содержащей нулевые элементы, вычисляет новую матрицу Z’:

for (i=0;i < size;i++)

  for (j=i+1;j < size;j++)

    get(i,j,link);

    if (link==0)

link=pseudolink(i,j,path_value);

    Zshtrikh.set(i,j,link);

};

};

return Zshtrikh;

Преобразование матрицы сил связи в матрицу расстояний

Эту задачу выполняет метод matrix_links::normalize().

Функция преобразования

В качестве убывающей функции преобразования значения меры близости в расстояние была выбрана гиперболическая функция

Если все прямые (ассоциативные) связи значительно больше 1 и все косвенные (псевдосвязи) связи значительно меньше 1, то получатся для первого класса связей короткие расстояния, а для второго — большие.

Нормализация

Пользователь может указать диапазон [dmin, dmax], в котором должны быть все расстояния. Для удовлетворения такого требования процедура normalize находит в массиве расстояний самое маленькое и самое большое значения dmin' и dmax'. Достаточно тогда осуществить простое линейное преобразование.

3.4. Модуль кластеризации

Общее описание алгоритма кластеризации

Построение дерева форм распределения

Алгоритм ищет оптимальное разбиение, создавая все возможные группировки и распределения объектов по кластерам, при этом оценивает их с помощью некой функции стоимости T. Число кластеров K задается в качестве параметра.

Сначала нужно определить возможные формы распределения, т.е. перечислить возможные последовательности размеров кластеров (s₁..s_K), где Σs_i = N. Например, если N=6 и К=3, то имеются следующие формы распределения:

{ 4 1 1 }: первый кластер содержит 4 объекта, остальные — по одному

{ 3 2 1 }: первый кластер содержит 3 объекта, второй — 2, третий — 1

{ 2 2 2 }: каждый из трех кластеров имеет по два объекта

Можно получить все варианты форм распределения, используя следующее рекурсивное правило: если N≥K>0 и A(N,K) обозначает множество возможных форм распределения, то A(N,K) = {{s, A(N– –s,K–1)}, где Sup(N/K)≤ s ≤ N–K+1 }. Здесь Sup(x) — самое маленькое целое число, большее или равное x.

Формы распределения строятся в виде дерева.

Например, для (N,K)=(7,4)

В этом дереве формы распределения читаются от корня до листа:

{3 2 2}

{3 3 1}

{4 2 1}

Проход по дереву и построение кластеров

Построение кластеров осуществляется по путям от корня к листьям дерева форм распределения (ДФР). В каждом узле ДФР читается размер s очередного кластера и создаются все возможные группы размером s путем отбора s объектов среди тех, которые еще не были включены в какой-нибудь из предыдущих кластеров.

Создание кластера данного размера также может быть описано как рекурсия:

пусть С(X,s) — множество возможных подмножеств размером s множества X, если s>0, то

C(X,s) = {{x , C(X–{x}, s–1) } | xÎ X }

Описание классов модуля кластеризации

Класс "кластеризация"

Структура данных "кластеризация" (clusterization) является представлением текущего состояния распределения объектов по классам. Она представляет собой таблицу, каждый элемент которой имеет какое-то (целое) значение k в диапазоне [0..К]. Если i-й элемент таблицы равен k, это значит, что в данной кластеризации i-й объект принадлежит k-му кластеру. "Нулевой кластер" есть на самом деле множество свободных объектов.

class clusterization

  protected:

  short int *table;                               //таблица

  short int n_objects;                            //текущий объем (сколько объектов уже охвачено)

  short int size;                                 //максимальный объем

  public:

  int find(const short int,const short int);      //найти позицию данного объекта

  short int read(const short int);                //чтение

  int write(const short int,const short int);     //запись

  short int get_nbr_of_objects();

  short int get_size();

  int display();

  int display_soft();

int operator==(const clusterization &);

  clusterization &operator=(const clusterization &);

  clusterization(const short int);

  clusterization();

  ~clusterization();

};

Класс "состояние"

"Состояние" (state) соединяет объект типа "кластеризация" с его оценкой (стоимостью).

class state

  public:

  clusterization klasterizatsia;

  float stoimost;

  int operator==(const state &);

  int display();

  int display_soft();

  state &operator=(const state &);

  state(const state &);

  state();

};

Класс "узел формы распределения"

Класс "узел формы распределения" (disp_shape_node) как структура данных состоит из двух полей:

поле данных	размер кластера (cluster_size);
поле структуры	список указателей подчиненных узлов (chained_list <disp_shape_node *> nodelist)

Класс как набор процедур содержит в основном метод Е(), который рекурсивно создает ДФР, поставляет правильное значение в поле cluster_size, создает подчиненные узлы и вызывает себя над ними.

class disp_shape_node

  public:

  short int cluster_size;                    //размер кластера

  chained_list nodelist;                     //ссылки к подчиненным узлам

  int E(int n,int m,int pred);               //метод построения ДФР

  int operator==(const disp_shape_node &);

  int display();

  disp_shape_node();

};

Класс "кластеризатор"

Класс "кластеризатор" (clusterizator) является средой проведения кластерного анализа. Он содержит: матрицу расстояний между объектами (matrix), функцию оценки плотности кластера на основе матрицы (transition_cost), корень ДФР (dispshape_tree), процедуру построения кластеров заданного размера (potomstvo), процедуру создания возможных кластеров и отбора лучшего варианта (F), головную процедуру запуска кластерного анализа и выдачи результата (clusterize), процедуру сохранения результатов кластеризации в файл (save).

class clusterizator

  protected:

  symmatrix matrix;                          //матрица расстояний

  int nbr_of_objects;                        //количество объектов

  int nbr_of_clusters;                       // количество кластеров

  long int nbr_of_dispshapes;                // количество разных форм

                                                распределения

  state local_best;

  disp_shape_node *dispshape_tree;           //ДФР

  chained_list final_states;

  public:

  state absolute_best;                       //оптимальное разбиение

  int potomstvo(const short int,const int,const int,state);

  int F(disp_shape_node *,state,int);

int best_state(chained_list &,state &);

  //функция оценки компактности кластера

  float transition_cost(chained_list);

  int save(char *);

  int clusterize();

  int clusterize(clusterization &);

  int clusterize(clusterization &,chained_list);

  clusterizator(const symmatrix &,const int);

  ~clusterizator();

};

Описание функционирования модуля кластеризации

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

Функционирование алгоритма кластеризации с одной формой распределения

Общее описание.

Каждый шаг алгоритма направлен на нахождение оптимального кластера размером ‘clustersize’, состоящего из свободных объектов, которые обозначены присутствием нуля на соответствующем месте в ‘кластеризации’; clustersize является очередным элементом формы распределения.

Изначально можно сказать, что ширина ДФР равна единице, или то, что вместо дерева имеется только список размеров кластеров. Сначала создаётся пустое состояние S (его стоимость нулевая, и его ‘кластеризация’ состоит из нулей).

Запускается рекурсивная процедура F(состояние, номер шага) со значениями ‘состояние’ = S и ‘номер шага’ = 1. Процедура F вызывает себя на проработанном состоянии и на следующем номере шага. В конце рекурсий кластеризация по данной форме распределения считается завершенной и оптимальной по принятой эвристике. Схема головной процедуры запуска кластерного анализа и выдачи результата (clusterize) представлена на рис. 8.

Процедура создания нового наилучшего кластера с заданным размером — F()

Рекурсивный модуль процедуры F(состояние, номер шага) записывает в текущем состоянии current_state новый наилучший кластер размером, указанном в рассматриваемом узле (node) ДФР. При этом увеличивается "стоимость" состояния. Схема процедуры приведена на рис. 9.

Подчеркнем, что ‘состояние’ содержит текущий результат процесса группировки. Работа F состоит из следующих моментов:

а) из формы распределения ‘clustersize’ читается размер кластера, номер которого соответствует номеру шага;

б) создаётся ‘kids’, пустой список состояний, в котором будут фиксироваться новые созданные состояния;

в) запускается рекурсивная процедура potomstvo(start_pos, clustersize, step, daddy, kids) со следующими значениями параметров: start_pos = 0, clustersize = clustersize, step = номер шага, daddy = состояние, kids = kids; при этом в списке kids фиксируются новые варианты кластеризации, т.е. варианты, с теми же самыми кластерами, как и в ‘состояние’, но содержащие в каждом из них новый кластер из возможных;

г) для списка kids выполняется процедура best_state() (процедура выбора состояния, минимизирующего стоимость в заданном списке состояний), т.е. отбирается то состояние, у которого стоимость минимальна; это состояние теперь считается текущим и переписывается в переменную ‘состояние’ (схема процедуры best_state() приведена на рис. 10, однако описывать ее не будем, ведь она тривиальна);

д) если форма распределения исчерпана (т.е. если номер шага равен количеству кластеров — иными словами, последний кластер сформировался), то рекурсия заканчивается; в этом случае наилучшая кластеризация по заданной форме распределения найдена, её содержит переменная ‘состояние’; в противоположном случае, когда нужно создать ещё кластеры, вызывается процедура F(состояние, номер шага + 1).

Процедура potomstvo()

Функционирования рекурсивной процедуры создания всех возможных новых кластеров potomstvo(start_pos, clustersize, step, daddy, kids_list)) направлено на формирование новых возможных состояний kids_list, исходя из заданного состояния daddy. Схема процедуры приведена на рис. 11.

Значение параметра step не изменяется в течение процесса рекурсии и просто передаётся от одного рекурсивного вызова к другому, ведь step означает номер формирующегося кластера.

Процедура создания новых кластеров начинается с того, что рассчитывается количество свободных объектов. По результатам расчетов могут сложиться две ситуации:

1. Если это количество равно значению переменной ‘clustersize’, то рекурсия прекращается, так как остаётся всего лишь один способ включить объекты в кластер — включить все объекты. Таким образом, получается, что текущий кластер сформирован и описан в таблице состояния ‘klasterizatsia’. Вычислив стоимость кластера, её добавляют к стоимости состояния. В завершение процедура присоединяет ‘состояние’ к списку возможных состояний ‘kids_list’.

2. Если количество свободных объектов не равно значению переменной ‘clustersize’, то это означает, что осталось несколько различных вариантов для выбора очередного объекта, входящего в состав создаваемого кластера. Для каждого из этих вариантов делается копия текущего состояния, в каждую копию включается в кластер по одному объекту, и для этих копий, рассматриваемых как новые состояния, вызывается процедура potomstvo(). Рекурсия так продолжается до тех пор, пока не сложится ситуация 1.

Функционирование алгоритма кластеризации с конкретным ДФР

Изменения, расширяющие возможности алгоритма кластеризации, относятся только к главной процедуре clusterize и процедуре F, ибо только их касаются формы распределения.

Необходимые изменения F заключаются в том, что на каждом шаге может существовать более одного варианта размера кластера. Назовём F’ новой версией процедуры F. Для того чтобы решить проблему внесения изменений, достаточно добавить один параметр в заголовок F' — адрес узла ДФР. Таким образом, F’ работает, так же как и F, на каждом из возможных значений размера кластера. Рекурсивный вызов F осуществляется на каждом из дочерних узлов дерева.

В главную процедуру clusterize от F' передается множество оптимальных состояний, каждое из которых соответствует одной форме распределения. В связи с этим приходится выбирать самое лучшее из них.

Построения ДФР

Построение ДФР осуществляется рекурсивной процедурой Е(). Схема процедуры приведена на рис. 12. При каждом вызове процедуры создается один узел ДФР. Ее параметрами являются: количество объектов, которые остается распределить по кластерам (n); количество кластеров, размер которых остается определить (m); служебный параметр (p).

Процедура Е() записывает в текущем узле размер i соответствующего кластера, создает подчиненный узел и вызывает себя на него с параметрами (n–i, m–1, i), так как действительно остались n–i объектов и m–1 кластеров, i принимает все зачения диапазона [min(n—m+1,p), крыша(n/m)]. Рекурсия заканчивается, когда m=0.

3.5. Представление результата процесса кластерного анализа в виде ассоциативного тезауруса

Экспорт кластеров к БД

Модуль кластеризации "clusterizator" снабжен процедурой сохранения полученной кластеризации во внешний файл. Информация записывается в следующем формате: <код слова-стимула>; <номер кластера>. В базе данных необходимо загрузить этот файл в таблицу cluster.

Составление тезауруса: отчет "кластеры"

Отчет "кластеры" представляет слова-стимулы в группах соответственно данным, присутствующим в таблице cluster. Нужно экспортировать этот результата в текстовой редактор для того, чтобы там осуществить конечную обработку по технологии, аналогичной той, которая применяется для верстки ассоциативного словаря.

Отчет базируется на следующем запросе:

SELECT DISTINCTROW

  [clusters].[code_stim], [clusters].[cluster], [stimulus].[code_stimulus],

  [stimulus].[mot]

FROM

  ([stimulus]

  INNER JOIN

    [clusters]

  ON [stimulus].[code_stimulus] =[clusters].[code_stim]);