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

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

По некоторым данным, в мире каждые семь месяцев происходит удвоение объема знаний, при этом только в Интернет ежедневно добавляется более 5 млн. веб-страниц. При этом обостряетсяпроблемаинформационногошума, особенно в научно-исследовательской деятельности и обучении, поскольку новые знания, ко- торые еще не включены в общепринятые классификационные системы, могут быть найдены во многом лишь на основе интуитивных механизмов. Важнейшим способом подключения интуиции пользователя является визуализация информации баз знаний, так как из различных источников известно, что 80-90% всей информации, воспринимаемой человеком, поступают именно через зрительные каналы. Отсюда вытекает актуальность разработки визуальных методов представления и использования информации в базах знаний и эффективной структуризации на этой основе пространства знаний [1].

В статье предлагается информационная технология формирования геометрического образа знаний, изначально структурированных в виде таблиц. При этом используется тот факт,что в таблицах конкретные данные (содержимое ячеек таблиц) связываются с понятиями - названиями соответствующих строк, столбцов, заголовки строк,столбцов и таблиц, а понятия рассматриваются как совокупность составляющих их терминов. Это позволяет определить информационные единицы (ИЕ) знаний как данные,связанные с парами понятий,включенных в семантическую сеть [2].На базе этой сети вводятся расстояния между терминами,понятиями,источни-ками знаний (таблицами),а затем решается задача формирования двухмерных или трехмерных геометрических образов, отображающих содержащиеся в базе знаний термины, понятия или источники зна-ний.Эти образы представляют собой совокупность точек,расположенных так,что евклидовы расстояния между ними в наибольшей степени соответствуют введенным расстояниям между их прообразами – элементами соответствующих семантических сетей. Предоставление пользователю в процессе информационного поиска таких геометрических образов знаний и средств навигации в соответствующих пространствах позволяет задействовать его интуитивные механизмы и расширить горизонты поиска.

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

• 1)    сканирование основных информационных серверов («программа - спайдер»);

• 2)    выбор знаний, представленных в виде таблиц;

• 3)    приведение таблиц к нормативному виду в полуавтоматическом режиме;

• 4)    опознание новых терминов, расчет близости между ними;

• 5)    опознание новых понятий и расчет ассоциативной близости между ними;

• 6)    опознание источников информации и расчет ассоциативной близости между ними;

• 7)    выделение из таблиц информационных единиц;

• 8)    формирование Единой Базы Знаний информационных единиц на базе семантических метризованных сетей понятий, терминов,источников;

• 9)    оптимальное иерархическое размещение объектов в двухмерном и трехмерном пространстве;

• 10)    визуализация и навигация в геометризован-ном,иерархическом пространстве знаний (терминов, понятий, источников).

Реализация данного алгоритма предполагает решение нескольких математических задач. Первая из них состоит в количественной оценки степени близости ρ объектов описанной семантической сети. Рассмотрим алгоритм оценки близости на примере понятий. Понятия участвуют в двух видах связей: по совпадению входящих в них терминов (с учетом синонимии)и в ассоциативных связях (по совместному вхождению в таблицы)[3].

Общий коэффициент близости ρ определим соотношением:

р = а • к1 + (а -1) ■ к2, а е [0...1], где k1 и k2 – коэффициенты близости по терминам и ассоциативным связям, α – назначаемый пользователем в процессе информационного поиска коэффициент смешивания. Здесь ,    2 • m k1 =----, где m - количество совпадающих

n терминов в двух понятиях (с учетом синонимии), а n - общее количество терминов в этих понятиях;

• 2 l

к 2 =---, где l - количество общих таблиц для

q двух понятий (т.е. количество таблиц, которые включают в себя оба понятия), а q – количество таблиц, включающих в себя хотя бы одно из понятий. Коэффициент близости в общем случае:

2 • m , 1Х 2 • I р = а--+ (а -1)--, nq

где а е [0...1].

Введем расстояния R между понятиями фор-

1 мулой R =   .

ρ

Полученные базы знаний содержат десятки тысяч семантических узлов и, соответственно, должны отображать десятки тысяч точек геометрического пространства. Для облегчения восприятия этих образов человеком необходимо создать иерархическую систему навигации, которая позволяет «агрегировать» сгущения точек в некоторые элементарные образы (кластеры), причем при необходимости – в несколько уровней.

Предлагается следующая модель оптимальной кластеризации. Пусть a _ij – расстояние между объектами i и j , u _j – признак того, что объект j является центром кластера. N – число, ограничивающее количество кластеров (оптимизируемый параметр):

N =∑uj, N →min;

j=1

f – число, ограничивающее радиус кластера;

b _ij – признак вхождения j объекта в кластер:

b ■■ ij

' 1, a ij ^ f

' 0, a ij > f vi – признак того, что объект i исключен из рассмотрения и не будет входить ни в один кластер

(объект отброшен):

v _i

1, object i discarded

0, object i reviewed

K – число, ограничивающее количество объек- тов, которые можно исключить из рассмотрения (не входят ни в один кластер):

n

∑vi≤K.

i=1

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

n

E bijui+v -1.

j=1

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

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

Для реализации указанного алгоритма предложены еще две математические модели:

• -    оптимального размещения геометрических образов объектов знаний,

• -    наиболее компактного табличного представления информации.

Цель первой модели – разместить объекты в пространстветак,чтобыгеометрическаяблизость между ними в наибольшей степени соответствовала матрице расстояний. Введем минимизируемый критерий оптимизации F для задачи оптимальной визуализации набора из n понятий:

n- 1    n J---------------------------------------------------

F=EE4(xt-xj) +(y-Vj) +(z--zj) -aij)

i=1j=i+i где (xi , yi , zi ) и (xj , yj , zj ) – координаты по осям x , y и z понятий i и j , соответственно.

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

Компактное представление знаний, выявленных в результате информационного поиска, является важнейшей задачей настоящей работы. Для ее реализации рассмотрим математическую модель формирования оптимально компактных выходных таблиц. N – общее количество понятий, aij , (i, j = 1..N ) – матрица значений, определяемых парой понятий i и j . Введем обозначения bij

/ 0, a ij =0] 1 a _M *0_

U _i , i = 1..N – булева переменная, признак включения понятия i в выходную таблицу; V _j ; j = 1..N – булева переменная, признак включения понятия j в выходную таблицу.

Сформируем ограничения:

∑Ui = p,

i где p – число строк, назначаемых пользователем;

∑j Vj =k, где k – число столбцов, назначаемых пользователем.

Критерий оптимальности представления результатов поиска в выходной таблице:

F = — У У bjVU; ^ max.

_pk ∑ _i ∑ _jij i j

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

• -    средняя плотность заполнения строки столбцами:

Ui' ≤ k1 ∑j bijVj , j=1..N.

• -    средняя плотность заполнения столбца строками:

Vj'≤ 1∑bijUi, i=1..N, pi где Ui' ≤ Ui, Vj' ≤ Vj .

Критерий оптимальности примет вид:

1       1

F= ¹ ⎜ ¹ U ^' + ¹ 2 ^⎜⎝ p ^∑ i ⁱ k

∑ _j V _j ^' _⎟⎟_⎠^⎞ → max .