Процессы управления и устойчивость

в котором присутствует информация по указанной тематике. Пере-

читывать или даже просматривать всю коллекцию или значитель-

ную её часть не представляется возможным. Для того, чтобы создать

правильные и семантически более точные классы документов, необ-

ходимо хотя бы некоторое вмешательство человека. Как уменьшить

долю этого участия и снизить потребление человеческого ресурса

в решении поставленной задачи? В настоящей статье предлагается

подход, который комбинирует различные подходы информационного

поиска и предлагает решение поставленной задачи.

Контекстно-ориентированная кластеризация и описание

группы кластеров. Разрешить задачу можно с помощью алгорит-

мов кластеризации и классификации документов. Для кластериза-

ции применяется алгоритм контекстного разбиения на кластеры [3].

Далее, создаётся краткое описание каждого кластера. На следующем

шаге алгоритма создаётся менее детальное описание группы класте-

ров. Таким образом, создаётся дерево, где на нижнем уровне (наибо-

лее детализированном) и наименее обобщённом присутствуют сами

документы, а на самом верхнем (наиболее обобщённом) присутству-

ют краткие описания группы кластеров. На основе этих обобщённых

описаний (как правило, не более двух-трёх предложений) человеком

создаются классы или основные темы. После описанных действий

уже можно утверждать, что имеет место структура документов, в

которой присутствует строгий порядок. При добавлении документа

в эту структуру над ним производятся те же действия, что и при

формировании структуры. Получаем описание документа на раз-

личных уровнях обобщённости (детализации). По полученным опи-

саниям производится сравнение на самом верхнем уровне, на более

детализированном, и так до тех пор, пока не будет найдено соответ-

ствующее описание для документа. Если в структуре не находится

кластера для документа, что означает новую для этой структуры

тематику, то создаётся новый кластер.

Применение алгоритма на практике. Для эксперимента бы-

ла выкачана коллекция из 3000 документов веба и поставлена зада-

ча: найти множество документов на тему многопоточного програм-

мирования. 500 документов было на тему обзоров игр за послед-

ние 5 лет, 1500 документов – вырезки новостных лент за 2 недели,

1000 документов на тему по программированию за последние 3 го-

353

да. Средний объем документа для обзора новости составлял 2–3 Kb,

10 Kb для статьи по программированию и 8 Kb для обзора игры.

Далее проведена кластеризация и создана обобщающая пирамида

описаний. На верхнем уровне находится самое обобщённое описание

некоторого множества кластеров. По нему были вручную составле-

ны соответствующие классы документов уже непосредственно для

восприятия человеком. Таким образом, обладая довольно скромной

информацией о содержании некоторого множества кластеров (лишь

его кратким описанием), удалось создать адекватную и соответству-

ющую содержательному смыслу структуру документов. Используя

алгоритмы стемирования для любого языка, можно создать струк-

туру документов на произвольно выбранном языке. Определение за-

данного множества было успешным.

Заключение. Таким образом, человек принимает участие толь-

ко на самом верхнем этапе обработки документов, что позволяет

сэкономить человеческий ресурс. Благодаря созданию иерархии на

основе контекстно-ориентированной кластеризации и работе со сжа-

тым представлением кластеров сокращается время поиска нужной

информации. По этому краткому описанию (возможно два-три пред-

ложения) должно быть понятно, какого характера информация со-

держится в документах, принадлежащих выбранному классу.

Литература

1. Jain, Murty and Flynn: Data Clustering: A Review, ACM Comp.

Surv., 1999.

2. Rafael A. Calvo, Jae-Moon Lee and Xiaobo Li. Managing сontent with

automatic document classification // Journal of digital information,

V. 5. Iss. 2, Article № 282, 2004-06-08.

3. Dobrynin V., Patterson D., Rooney N. Contextual document

clustering.

354

Коротких Д.А.

Санкт-Петербургский государственный университет

Системы оценки знаний, основанные на теории

нечетких множеств

Рекомендовано к публикации профессором Андриановым С.Н.

Введение. В данной статье предлагается альтернативный под-

ход к представлению тестовых заданий, основанный на теории нечет-

ких множеств. Подход является весьма гибким и позволяет едино-

образно описывать различные типы заданий.

1. Основные определения. Сформулируем необходимые опре-

деления и понятия.

Определение 1. Пусть имеется множество тестовых заданий

(вопросов) {Q

k

}, k = 1, n, где n – общее число заданий. Для каждого

задания Q

k

существует и определено множество доступных вари-

антов ответов {A

k,j

}, j = 1, m

k

, где m

k

— количество доступных

вариантов ответов для задания Q

k

. Будем представлять множество

верных ответов на задание Q

k

в виде нечеткого множества {R

k

} на

универсальном множестве {A

k,j

}, j = 1, m

k

, с функцией принадлеж-

ности ω

k

(A

k,j

). Пусть также данная функция принадлежности огра-

ничена и ω

k,max

= max(ω

k

(A

k,j

)) – высота множества {R

k

}. Будем

называть функцию ω

k

(A

k,j

) функцией правильности.

«Классический» вариант тестового задания с двумя типами от-

ветов: «верными» и «неверными» возникает в случае, когда ω

k

=

{0, 1}.

При анализе результатов тестирования, в первую очередь, под-

считывается количество верных и неверных ответов. При использо-

вании данной схемы этот процесс видоизменяется, поскольку каждое

задание может иметь не только стопроцентно верные, но и неверные

ответы.

Определение 2. Пусть S

k

– вариант ответа A

k,j

на задачу Q

k

,

который тестируемый счел верным, или S

k

= ∅ в случае, если тести-

руемый счел, что ни один вариант ответа не является правильным..

Обозначив за P

k

общее количество попыток ответа на задачу Q

k

,

можно вычислить две величины:

355

x

k,1

=

P

k

i=1







(ω

k

i

)/(ω

k,max

i

); ω

k,max

i

= 0,

0; ω

k,max

i

= 0, S

k,i

= ∅,

1; ω

k,max

i

= 0, S

k,i

= ∅,

(1)

x

k,2

=

P

k

i=1







(ω

k,max

i

− ω

k

i

)/(ω

k,max

i

); ω

k,max

i

= 0,

1; ω

k,max

i

= 0, S

k,i

= ∅,

0; ω

k,max

i

= 0, S

k,i

= ∅.

(2)

Пусть x

k,1

– коэффициент данных верных ответов на задачу Q

k

,

x

k,2

– коэффициент данных неверных ответов

Отдельно стоит отметить, что в случае, когда ω

k

i

= {0, 1}, эти

величины будут обозначать количество верно и неверно данных от-

ветов соответственно.

Определение 3. Обозначив N

k

= x

k,1

+ x

k,2

, можно вычис-

лить две важные характеристики – меру правильных ответов y

k,1

=

x

k,1

/N

k

и меру неправильных ответов y

k,2

= x

k,2

/N

k

. Произведение

этих величин

d

k

= y

k,1

× y

k,2

(3)

рассматривается в качестве стандартной меры вариации, именуемой

дисперсией задания Q

k

.

Дисперсии тестового задания (3) в совокупности с коэффициен-

том данных верных и неверных ответов (1) и (2) является показате-

лем сложности и дискриминативности тестового задания.

Определение 4. Под дискриминативностью задания подразу-

мевается способность отделять испытуемых с высоким баллом по

тесту от тех, кто получил низкий балл [3].

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

ходимо учитывать, что d

k

зависит от величины P

k

(чем больше число

попыток ответа на задание Q

k

, тем точнее дисперсия). Таким обра-

зом, необходимо хранить историю изменения дисперсии, либо про-

ектировать таблицы хранения результатов так, чтобы существовала

возможность получения значений в разрезе времени или количества

попыток решения данного задания [2].

Определение 5. Будем называть тестом T

i

набор тестовых за-

даний {Q

k

|ψ

i

(Q

k

) = 1}, где ψ

i

(Q

k

) – функция принадлежности те-

356

стового задания к тесту T

i

, имеющая областью определения множе-

ство {Q

k

} и принимающая два значения: 1 – в случае, если задание

входит в тест T

i

и 0 – в противном случае.

2. Разработка структуры хранения данных. Основной отли-

чительной особенностью систем тестирования, основанных на теории

нечетких множеств, является разделение понятий «тест», «тестовое

задание» и «вариант ответа». Каждое из этих понятий представляет

собой по сути дела отдельный класс. Существует по крайней мере

два подхода к проектированию таблиц баз данных.

Первый способ — наиболее простой, но имеет под собой одно (но

немаловажное) ограничение, которое сводится к ограничению ко-

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

словами, на каждое множество {A

k,j

}, j = 1, m

k

, накладывается до-

полнительное ограничение m

k

≤ S, ∀k, где S – константа, жестко

заданная параметрами системы. В данном случае тестовые задания

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

данных и нераздельны. Однако, сами тесты вынесены в отдельную

таблицу и связаны с таблицей тестовых заданий «one-to-many».

Второй способ подразумевает, что вся информация об объектах

«тест», «тестовое задание» и «вариант ответа» хранится в различ-

ных таблицах. Функции принадлежности организованы в виде свя-

зей «many-to-many» с весовыми коэффициентами. Безусловно, это

снижает скорость формирования теста, но не настолько сильно, что-

бы отказаться от этой идеи. Однако, в данном случае система будет

иметь более гибкую структуру, позволяющую в полной мере реали-

зовывать идеологию размытых множеств.

3. Организация методов анализа результатов. В настоящее

время предложено множество методов анализа результатов тестиро-

вания. Большинство систем реализуют только узкий круг подходов,

и если необходимо применить другой метод, то придется это делать

вручную, либо переписывать часть системы, разбираясь в написан-

ном ранее коде.

Однако можно предложить один из способов решения данной

проблемы. Суть идеи заключается в следующем:

• данные о результатах проведения тестирования всегда должны

быть избыточны и содержать всю возможную информацию;

• методы анализа результатов должны быть организованы в виде

357

стандартизованных классов (MathClasses).

Каждый MathClass имеет стандартный конструктор и функции,

отвечающие за выборку данных из таблиц результатов. Имена всех

public функций, а также количество и тип их параметров для каж-

дого подобного класса, жестко заданы и регламентированы.

Модуль, называемый «Analyzer», создает объект необходимого

класса, передает ему параметры инициализации и готовые выборки

из таблицы результатов, а на выходе получает некоторые числен-

ные показатели. Эксперт может варьировать входные параметры и

проводить многосторонний анализ результатов.

Заключение. В настоящее время благодаря стремительному

развитию информационных технологий компьютеры стали необхо-

димым инструментом не только в профессиональной деятельности

и науке, но все чаще используются для получения образования и по-

вышения квалификации [1–3]. Все чаще используются «бесконтакт-

ные» формы взаимодействия преподавателей и студентов. Одной из

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

на основе систем компьютерного тестирования и телекоммуникаци-

онных технологий. Предложенная в данной статье схема организа-

ции подобных систем является гибкой и может быть использована

не только для контроля знаний, но и для тестирования кандидатов

и проверки профессиональных качеств сотрудников организаций.

Литература

1. Прокофьева Н.О., Зайцева Л.В., Куплис У.Г. Компьютерные си-

стемы в дистанционном обучении // ТЕЛЕМАТИКА’2001. СПб.,

2001. С. 109–111.

2. Зайцева Л.В. Некоторые аспекты контроля знаний в дистанцион-

ном обучении // Образование и виртуальность – 2000: Сборник

научных трудов 4-й международной конференции. Харьков – Се-

вастополь: УАДО, 2000. С. 126–131.

3. Минин М.Г. Диагностика качества знаний и компьютерные тех-

нологии обучения. Томск: Изд-во ТГПУ, 2000.

358

Краснова А.Ю.

Санкт-Петербургский государственный университет

Бинарные операции над (0,1)-матрицами

и их моделирование

Рекомендовано к публикации доцентом Хитровым Г.М.

1. (0,1)-матрицы и булева арифметика. Начнем с определе-

ния (0,1)-матриц.

Определение 1. (0,1)-матрицей называется матрица, состоя-

щая только из нулей и единиц.

Чтобы оперировать с (0,1)-матрицами, не выходя за пределы это-

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

булевой ([1], стр. 28). Эти правила отличаются от правил обычной

арифметики тем, что сумма двух единиц дает единицу.

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

го сложения и булевского умножения обладают следующими свой-

ствами сложения:

1. Замкнутость на множестве;

2. Ассоциативность: (a + b) + c = a + (b + c);

3. Коммунативность;

4. Существование нейтрального элемента: существует такой эле-

мент 0, что для любого элемента a из множества (0,1)-матриц

выполняется следующее условие a + 0 = a;

и свойствами умножения:

1. Замкнутость на множестве;

2. Ассоциативность: (a · b) · c = a · (b · c);

3. Коммунативность;

4. Существование нейтрального элемента: для любого элемента

a = 0 из множества (0,1)-матриц существует нейтральный эле-

мент 1 такой, что выполняется условие a · 1 = a.

2. Определение булевских сложения и умножения (0,1)-

матриц. Дадим необходимые понятия.

Определение 2. Обычное сложение (0,1)-матриц, где сложение

элементов ведется по правилам булевой арифметики, будем назы-

вать булевским сложением (0,1)-матриц.

359

Определение 3. Обычное произведение (0,1)-матриц, где умно-

жение и сложение элементов ведется по правилам булевой арифме-

тики, будем называть булевским умножением (0,1)-матриц.

Введем обозначения: ˙

+ – булевское сложение (0,1)-матриц; ˙

× –

булевское умножение (0,1)-матриц.

Нетрудно видеть, что операция булевского сложения (0,1)-матриц

замкнута, ассоциативна и коммутативна. Относительно неё сущест-

вует нейтральный элемент — нулевая матрица.

Операция булевского умножения (0,1)-матриц замкнута и ассо-

циативна.

Пусть множество OI

n

– множество квадратных (0,1)-матриц раз-

мерности n. В этом множестве относительно операции булевского

умножения существует нейтральный элемент – это обычная единич-

ная матрица.

Доказательство перечисленных свойств булевских операций сло-

жения и умножения (0,1)-матриц почти очевидно, поскольку они

определяются через обычные операции сложения и умножения мат-

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

множестве {0, 1} по правилам булевой арифметики.

Заметим, что относительно операции ˙

× множество OI

n

образу-

ет полугруппу с единицей (единичная матрица), т.е. OI

n

является

моноидом.

Множество OI

n

содержит в себе множество матриц перестано-

вок n-го порядка, которое будем обозначать через Π

n

. Напомним,

что матрицей перестановки называется квадратная (0,1)-матрица, у

которой в каждой строке и каждом столбце имеется один элемент

равный единице, а остальные элементы равны нулю. Из-за такой

структуры матриц перестановок их обычное произведение совпада-

ет с булевским. Напомним также, что обратная матрица к матрице

перестановки является ее транспонированной, т.е. Π

n

образует ор-

тогональную группу относительно обычного, а, следовательно, и бу-

левского умножения матриц. Другими словами, Π

n

∈ OI

n

и является

подгруппой моноида OI

n

.

Сказанное выше показывает, что множество OI

n

относительно

операций ˙

+ и ˙

× образует достаточно богатую структуру и оправды-

вает пристальное внимание к этой структуре. Это тем более важно

из-за теснейшей связи между множеством OI

n

и бинарными отно-

шениями на конечном множестве мощности n.

360

3. Бинарные отношения и (0,1)-матрицы.

Определение 4 ([2], стр. 15). Бинарным отношением R на мно-

жестве X = {x

1

, . . . , x

n

} называется подмножество R = X × X, т.е.

подмножество упорядоченных пар декартова произведения множе-

ства X на себя.

Если важно подчеркнуть, что бинарное отношение R задано

на множестве X, то будем обозначать это бинарное отношение

< R, X >. Принадлежность пары < x

i

, x

j

> подмножеству R в тео-

рии бинарных отношений записывается, как x

i

Rx

j

, и читается, как

«x

i

находится в отношении R с x

j

».

Сопоставим каждой паре < x

i

, x

j

> элемент a

ij

следующим об-

разом:

a

ij

=

1, если < x

i

, x

j

>∈ R;

0, если < x

i

, x

j

> /

∈ R.

Из элементов a

ij

построим матрицу, которую будем обозначать

через A(R) и называть матрицей бинарного отношения R. Очевидно,

что A(R) ∈ OI

n

, и между различными бинарными отношениями R

на множестве X и матрицами A(R) ∈ OI

n

существует взаимноодно-

значное соответствие. При этом операциям над бинарными отноше-

ниями будут соответствовать некоторые операции над матрицами и

эти соответствия будут также взаимнооднозначными.

Определение 5 ([2], стр. 20). Объединением отношений R

1

и

R

2

(обозначается R

1

R

2

) называется отношение, определяемое объ-

единением соответствующих подмножеств из X × X.

Определение 6 ([2], стр. 22–23). Произведением отношений R

1

и R

2

называется отношение, определяемое следующим образом: xR

1

·

R

2

y, если существует z ∈ X, для которого xR

1

z и zR

2

y, где R

1

· R

2

– символ произведения отношений.

Очевидно, что после того как определено произведение двух от-

ношений, так сразу же определено произведение любого числа отно-

шений, когда сначала умножается пара отношений, затем произведе-

ние умножается на третье отношение, полученный результат умно-

жается на следующее отношение и т.д. Нетрудно показать, что про-

изведение отношений ассоциативно, т.е. (R

1

· R

2

) · R

3

= R

1

· (R

2

· R

3

).

Действительно, если x(R

1

· R

2

) · R

3

y, то существует z такое, что

xR

1

· R

2

z и zR

3

y. Из того, что xR

1

· R

2

z, следует, что существует u

такое, что xR

1

u и uR

2

z. Далее, из uR

2

z и zR

3

y следует, что uR

2

·R

3

y.

А из xR

жүктеу/скачать 30,48 Mb.

Достарыңызбен бөлісу: