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



жүктеу 30.48 Mb.
Pdf просмотр
бет33/57
Дата27.12.2016
өлшемі30.48 Mb.
1   ...   29   30   31   32   33   34   35   36   ...   57

ства документов на подгруппы, так что информация в каждом доку-

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

для этого кластера характерной особенности – темы. Выделяют два

типа кластеризации: иерархический и партиционный.

Классификация документов [2] – это задача информационного

поиска. Её цель состоит в том, чтобы, основываясь на содержании до-

кумента отнести его к одной или нескольким категориям. Выделяют

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

которая обуславливается наличием внешнего механизма проверки

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

где отсутствует всякая внешняя вспомогательная информация.

Постановка задачи. Пусть имеется некоторая коллекция доку-

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

английский (китайский или японский, например, не подходят). Зада-

ча в том, чтобы из этого множества документов найти подмножество,

352


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

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

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

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

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

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

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

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

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

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

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

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

ции применяется алгоритм контекстного разбиения на кластеры [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


Каталог: bitstream
bitstream -> С. торайғыровтың публицистикасы
bitstream -> Қ атыстық сын есімдердің лексикалық тіркесімділігі
bitstream -> «Қазақ» газетіндегі ұлт-азаттық көтеріліс туралы мақалалардың маңызы
bitstream -> Бегімбай К. М. Дизайн және бейнелеу өнері салаларына
bitstream -> Грам м атические форм ы вы раж ения ком паративны Х отнош ений в научно-популярной лингвистической литературе
bitstream -> СҮттің Қоректік сапасы және сүттегі микроорганизмдер
bitstream -> Қазақ халқының ою-өрнектерінің Қолданылуы
bitstream -> Л. Н. Гумилев атындағы ЕҰу хабаршысы


Поделитесь с Вашими друзьями:
1   ...   29   30   31   32   33   34   35   36   ...   57


©emirsaba.org 2019
әкімшілігінің қараңыз

    Басты бет