ISSN 0236-235X (P)
ISSN 2311-2735 (E)

Journal influence

Higher Attestation Commission (VAK) - К1 quartile
Russian Science Citation Index (RSCI)

Bookmark

Next issue

4
Publication date:
09 September 2024

Clustering of atomic knowledge using methods of linear optimization

The article was published in issue no. № 1, 2012 [ pp. 45 - 47 ]
Abstract:The work deals with methods to form compact clusters of factual knowledge from unstructured information stored in the Internet. Some own mathematical models are offered, which allow to solve the problem using the methods of integer linear programming.
Аннотация:Рассматриваются методы, позволяющие формировать плотные кластеры фактологических знаний из неструкту-рированной информации, хранящейся в Интернете. Предложены собственные математические модели для решения задачи с использованием методов целочисленного линейного программирования.
Author: (galeev@netcracker.com) -
Keywords: linear programming, information, knowledge, clusterization
Page views: 10799
Print version
Full issue in PDF (5.33Mb)
Download the cover in PDF (1.08Мб)

Font size:       Font:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Подпись:  Рис. 1. Первый шаг эксперимента Рис. 2. Отчет по кластеризации на первом шаге Рис. 3. Третий шаг экспериментаИсходные данные/переменные: 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

Оборудование, задействованное в учебном процессе

Количество по годам

2007

2008

2009

2010

2011

Компьютеры

1423

2118

2828

3356

4110

Мультимедиа- проекторы

98

141

478

730

946

Интерактивные доски, приставки, планшеты

53

85

211

334

493

Таблица 2

Интернетизация

Количество по годам

2007

2008

2009

2010

2011

Муниципальные образовательные учреждения, подключенные к сети (шт.), в том числе:

86

93

115

124

234

школы

77

81

86

86

86

детские сады

0

2

15

20

130

учреждения дополнительного образования

9

10

14

18

18

Web-сайты образовательных учреждений в сети (ед.)

32

56

67

93

117

Педагоги школ, владеющие информационно-коммуникационными технологиями (%)

23

47

59

75

80

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

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

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

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

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

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

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

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

Литература

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

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


Permanent link:
http://swsys.ru/index.php?page=article&id=3012&lang=&lang=en&like=1
Print version
Full issue in PDF (5.33Mb)
Download the cover in PDF (1.08Мб)
The article was published in issue no. № 1, 2012 [ pp. 45 - 47 ]

Perhaps, you might be interested in the following articles of similar topics: