Software & Systems

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

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

Одной из возможных форм представления знаний является атомарная. Знания в этом случае представляются в виде элементарных элементов – атомов знаний.

Атом знания – элементарная семантическая единица, достоверный факт, его конкретное значение, связанное с неограниченным количеством понятий, являющихся метаинформацией для данного значения. В качестве примера приведем следующие атомы.

«Вода» – «Температура кипения» – «100 градусов». В этом примере «100 градусов» – значение (факт), а «Вода» и «Температура» – понятия (метаинформация).

«Вода» – «Температура замерзания» – «0 градусов». В этом примере «0 градусов» – значение, а «Вода», «Температура» и «замерзания» – связанные со значением понятия.

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

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

Знания, представленные в данной форме, легко поддаются различным методам обработки, в том числе кластеризации.

Кластер-анализ – это способ группировки многомерных объектов, основанный на представлении результатов отдельных наблюдений точками подходящего геометрического пространства с последующим выделением групп как сгустков этих точек (кластер – от англ. cluster – сгусток, гроздь, скопление).

Введем определения.

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

Частично заполненный кластер (ЧЗКЗ) – подтаблица исходной матрицы знаний, на пересечении хотя бы одной строки/столбца которой находится ноль, то есть отсутствует информация, характеризующая зависимость соответствующего объекта/характеристики.

К предложенному виду матрицы знаний применимы следующие варианты кластеризации:

-      выделение из заданной таблицы ПЗКЗ максимального размера;

-      выделение из заданной таблицы всех ПЗКЗ, размер которых не меньше заданного;

-      выделение из таблицы ЧЗКЗ с плотностью, не меньше заданной;

-      выделение ЧЗКЗ максимальной плотности при заданном размере кластера.

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

Модели кластеризации табличных знаний

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

Исходные данные/переменные: aij – клетки исходной матрицы знаний; xi – признак включения объекта в кластер; yj  – признак включения характеристики в кластер; qij – признак включения клетки в кластер.

Ограничения: qij ≥xi + yj–1 – клетка должна быть включена в кластер, если включены соответствующие объект и характеристика;  – для включенной клетки необходимо, чтобы соответствующие объект и характеристика были включены в кластер; qij≤aij – можно включить только такую клетку, в которой в исходной матрице стоит оптимизируемая функция на максимум числа клеток, включаемых в кластер (размер кластера): ∑i∑jqij→max.

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

Исходные данные/переменные: aij – клетки исходной матрицы знаний; xi – признак включения объекта в кластер; yj – признак включения характеристики в кластер; qij – признак включения клетки в кластер; n – число строк выделяемого кластера; m – число столбцов выделяемого кластера.

Ограничения: qij≥xi+yj–1 – клетка должна быть включена в кластер, если включены соответствующие объект и характеристика;  – для включенной клетки необходимо, чтобы соответствующие объект и характеристика были включены в кластер; ∑Xi=N – число строк выделяемого кластера должно быть равно заданному; ∑Yi=M – число столбцов выделяемого кластера должно быть равно заданному.

Оптимизируемая функция на максимум числа единиц, включаемых в кластер: ∑aijqij→max.

Реализация моделей

Предложенные модели успешно реализованы на языке C# с использованием библиотеки целочисленного линейного программирования lpsolve55.

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

Для этого выбрана область «Информационные технологии в образовании». В Интернете найдены таблицы, в той или иной мере относящиеся к данной области (табл. 1–2).

В таблице 1 содержатся сведения о количестве поступивших на обучение в 2000 и 2010 году в учебные учреждения различных ступеней образования, в таблице 2 показано состояние процесса интернетизации системы образования г. Оренбурга в 2007–2011 гг.

Таблица 1

Таблица 2

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

Далее заполненная БД была подключена к модулю выделения сгустков знаний. Проведено исследование получаемых из таких данных кластеров знаний. В исходном тезаурусе содержалось большое количество терминов, поэтому на первом этапе были выбраны термины, точно описывающие некоторые значения исходных таблиц (рис. 1): «г. Оренбург», «количество», «компьютеров», «планшетов», «досок», «единиц», «учебном», «процессе», «2009», «2010», «2011».

Был получен кластер знаний, соответствующий данным исходной таблицы 1 до дезинтеграции (рис. 2).

Далее к исходному набору данных добавлены термины «web-сайтов» и «Интернет».

В итоге был получен кластер, объединивший в себе атомы из исходных таблиц 1 и 2, большего размера, чем на первом шаге.

Далее были добавлены термины «2004» и «2003».

В результате исходный отчет остался прежним (рис. 3), так как в системе отсутствовали атомы, связанные с добавленными терминами, информационный шум успешно отсеялся.

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

Литература

1.     Ландэ Д.В. Поиск знаний в Internet. М.: Диалектика, 2005. 265 с.

2.     Информатизация образования. URL: (дата обращения: 10.09.2010).