MATHEMATICAL MODELS OF FACTUAL INFORMATION OPTIMAL SYSTEMATIZATION

Full Text

Постановка проблемы фактографического поиска В условиях информационного общества основным источником информации для специалиста в сфере науки, техники и экономики является информация из Internet, при этом все большую роль играет фактографическая информация. Понятие фактографической информации в настоящее время находится в стадии становления и допускает различные близкие интерпретации. К примеру, в [1] дается следующее определение фактографической информации: «К фактографическим данным относятся сведения, извлеченные из документов, как первичных, так и вторичных, и получаемые непосредственно из источников их возникновения». В [2] под фактографической информацией называется информация об объектах в тексте на естественном языке, которые однозначно соотносятся с объектами, существующими в действительности. В зарубежных словарях дается более широкое понятие фактографической информации, например в словаре Macmillan [3] под фактографической информацией понимается информация, основанная на фактах или содержащая только факты, а не теории или мнения. Под фактографической информацией будем понимать информацию, представленную в виде «Инфокоммуникационные технологии» Том 12, № 1, 2014 78 Ворошилов В.В., Пиявский С.А. числа (с указанием размерности) с набором терминов, поясняющих объект, характеризуемый этим числом. Такое понимание имеет важное практическое значение, позволяет достаточно просто решить самостоятельную сложную задачу выделения самого факта наличия фактографической информации в тексте на естественном языке. Кроме того, разработанные нами алгоритмы не используют существенно числовой характер фактографической информации и поэтому могут быть использованы и в рамках других интерпретаций. Между тем специальные средства для поиска такой информации лишь разрабатываются (например Wolfram [4]) и тем более не включены в учебный процесс в вузах. В настоящей работе авторы поставили перед собой задачу разработать специальный инструментарий для поиска и систематизации фактографической информации. Технология фактографического поиска на основе формирования атомарной базы данных В основе фактографической информации лежат количественные данные описания фактов, сгруппированных по определенным системообразующим признакам. Таким образом, элементом, единицей фактографической информации является «атом», состоящий из набора числового значения, размерности и набора лексем. Лексема представляет собой словоформу (термин, понятие), используемую из семантического тезауруса. Таким образом, в основе автоматизированного фактографического поиска должна лежать специальным образом организованная база данных фактографической информации (АтБД), представляющая собой совокупность атомов фактографической информации [5]. Система управления такой АтБД должна обеспечивать пополнение БД с выявлением тавтологической и противоречивой информации, а также выдачу, по определенному запросу пользователя, релевантной фактографической информации как в несистематизированном виде (набор атомов упорядочениях по релевантности), так и систематизированной (в виде наиболее плотно заполненных двумерных таблиц). Использование такой формы фактографического поиска требует специального обучения студентов, а это обучение может проходить достаточно эффективно лишь с использованием специальной информационной системы, позволяющей контролировать работу студентов как на аудиторных занятиях, так и во внеучебное время. На основе вышеизложенной структуры данных была реализована атомарная база знаний. Имеются три канала пополнения АтБД. Первый из них - пополнение службой сопровождения БД, оно включает в себя формирование и пополнение базовых наборов лексем, характеризующих различные предметные области, то есть прямое пополнение тезауруса системы базовым набором лексем, характеризующих предметную область. Второй канал пополнения имеет в виду автоматизированный поиск фактографической информации, ее индексирование и ввод в АтБД, который состоит из двух основных этапов. На первом этапе проводится отбор информационных ресурсов из Internet (документов, файлов, веб-страниц) по прямым ссылкам, указанным методологической службой сопровождения, составленных на основе поисковой деятельности пользователей системы, а также отбор с использованием известных поисковых систем и сервисов, по поисковым запросам, составленным методологической службой сопровождения и состоящим из набора лексем, описывающих предметную область. На втором этапе проводится анализ информационного ресурса, полученного в результате поиска, а затем выделение атомов фактографической информации, их индексирование и сохранение в АтБД. Третий канал - это пополнение АтБД в процессе ее использования: пользователями в процессе своей профессиональной поисковой деятельности, студентами по различным дисциплинам в процессе учебной поисковой деятельности, а также студентами при обучении фактографическому поиску на основе АтБД. Пополнение происходит на основе формирования запросов к методологической службе сопровождения о расширении базы поиска в виде указания: поисковых запросов, предметной области, прямых ссылок на документы или веб-страницы. А также в виде указания набора атомов фактографической информации с указанием источника и дополнительной метаинформацией, составленных студентами в процессе обучения фактографическому поиску на основе АтБД. На рис. 1 показана схема использования атомарной базы знаний для поиска фактографической информации. На основе вышеизложенного подхода была разработана и реализована информационная система организации и управления фактографической поисковой деятельностью. Данная система «Инфокоммуникационные технологии» Том 12, № 1, 2014 Ворошилов В.В., Пиявский С.А. 79 Вход / \ Формирование поискового запроса в виде набора лексем из тезауруса системы V_/ Выбор сохраненного поискового запроса Рис. 1. Использование атомарной базы знаний для поиска фактографической информации реализована в виде web-приложения с клиентской частью, обеспечивающей дополнительные возможности. Разработанная система логически разделена на три подсистемы: - подсистема формирования и пополнения АтБД; - подсистема поиска и выдачи фактографической информации по запросу; - подсистема мониторинга и управления учебно-поисковой деятельностью студентов в процессе обучения. Целесообразность включения третьей подсистемы определяется тем, что понятие фактографического поиска недостаточно включено в функционал обычной компьютерной грамотности. Между тем сбор и анализ фактографической информации, особенно для направлений подготовки специалистов в области естественных, технических и экономических наук, приобретает все большее значение. Использование при этом математического аппарата и соответствующих информационных систем в условиях развитой инфокоммуникационной среды вуза является прогрессивной тенденцией [6-10]. Физически информационная система организации и управления фактографической поисковой деятельностью студентов в Internet состоит из трех модулей и двух баз данных: - клиентская часть поиска фактографической информации - используется непосредственно для поиска и анализа информации в интернете, а также фактографического поиска в АтБД; - веб-сайт для работы с фактографической информацией: - всеми пользователями для поиска фактографической информации в АтБД; - методологической и административной службой для формирования и пополнения АтБД; - преподавателями и студентами для контроля и управления поисковой деятельностью в учебном процессе вуза; - атомарная база данных; - база данных учебного процесса. Подсистема формирования и пополнения АтБД реализует следующие возможности: - предоставляет интерфейс ввода фактографической информации как в виде одного, так и множества атомов; - предоставляет интерфейс ввода фактографической информации в виде файлов, поддерживаемые типы файлов: файлы MS Excel, MS Word, Html, PDF. Использование АтБД происходит по средствам использования следующих функций: - поиск и выдача фактографической информации по запросу: - предоставляет интерфейс поиска фактографической информации в виде указания поисковой строки. - предоставляет интерфейс поиска фактографической информации в виде указания набора поисковых лексем. «Инфокоммуникационные технологии» Том 12, № 1, 2014 80 Ворошилов В.В., Пиявский С.А. - вывод результата поиска в виде последовательного набора атомов (сортировка по имени, дате, релевантности). - вывод результата поиска в виде набора наиболее плотных двумерных таблиц. Обычная технология использования системы состоит в следующем. Вначале пользователю необходимо авторизоваться в системе. Затем указать поисковый запрос в виде набора лексем из тезауруса системы или в виде строки, при этом строка поискового запроса автоматически преобразуется в набор лексем из тезауруса системы. При указании поискового запроса существует возможность указать запрос один из сохраненных, ранее используемых пользователем. Далее следует задать лимитные параметры выдачи фактографической информации из АтБД, такие как: - максимальное значение количества атомов в выдаваемом результате; - минимальное значение количества атомов в выдаваемом результате; - максимальное значение количества лексем при поиске информации в АтБД; - минимальное значение количества лексем при поиске информации в АтБД. После указания параметров выдачи проводится поиск в АтБД и в результате предоставляется фактографическая информация в виде набора максимально заполненных двумерных таблиц. Эти таблицы содержат наиболее плотно заполненные кластеры информации (под кластером информации понимается набор атомов). Для количественной оценки степени заполненности кластера введем понятие его информативности. Под информативностью лексемы относительно кластера будем понимать отношение числа атомов, в описании которых содержится данная лексема, к общему числу атомов в кластере. Информативностью кластера будем называть среднюю информативность относительно данного кластера всех лексем, входящих в описание хотя бы одного из атомов этого кластера. Кластер будем называть замкнутым, если входящие в его атомы лексемы не входят в описание других атомов, то есть не входящих в кластер. Затем пользователь имеет возможность провести анализ информации в таблицах на предмет их наполненности. Выявив недостающую информацию по пустотам в таблицах, рекомендуется провести ее поиск с использованием известных пои сковых средств и сервисов и добавить найденную новую информации в АтБД для его пополнения. Математические модели оптимальной систематизации фактографической информации Рассмотрим математическую модель формирования кластера наибольшей информативности. Введем следующие обозначения: N - число атомов в БД; M - число лексем в БД; U. - признак включения лексемы в описание кластера; Vi - признак включения атома в кластер. Тогда N м ^/Vi- число атомов в кластере; число i=1 j=i лексем в описании кластера; п. - число атомов, J N ' в описание которых входит лексема j; /=1 число атомов в кластере, в описание которых входит лексема j. Рассмотрим в качестве примера задачу: найти кластер максимальной удельной информативности на один атом при заданной длине его описаний m. Эта задача сводится к задаче нелинейной оптимизации со следующими целевой функцией и ограничениями: F = 1 N М =i j=1 где Uj > aijVi - условие, что если лексема не выбрана, ее не должно быть ни в одном атоме кластера. Лимитные условия на размер получаемого кластера: м м YU}<maxlex, YUj^mi М 7=1 N N Y/i-max*tom> Y/.-minlex 5 i-1 i'-l Исходные данные этой модели: N = 10 - число атомов; M = 8 - число лексем. Распределение значений между атомами и лексемами показано на таблице 1, где строка - это соответствующий атом (ie [1,N]), а столбец - соответствующая лексема №1,Щ, то есть, например, атом с порядковым номером 1 описывается лексемами 1, 4, 7 и 8, а атом 10 описывается лексемами 3, 5 и 8. Средняя информативность исходной таблицы равна 0,39. В результате решения данной задачи получается кластер, показанный в таблице 2, с максимальной удельной информативностью на «Инфокоммуникационные технологии» Том 12, № 1, 2014 Ворошилов В.В., Пиявский С.А. 81 Таблица 1. Исходная таблица описания атомов набором лексем, информативность 0,39 Лексемы 1 2 3 4 5 6 7 8 Атомы Петя Вася Лев Вес Рост IQ Юность Журнал 1 60 кг 1 1 1 1 2 120 ед 1 1 1 3 50 кг 1 1 1 1 4 110 ед 1 1 1 5 70 кг 1 1 1 6 180 см 1 1 7 170 см 1 1 1 8 150 см 1 1 1 9 130 ед 1 1 1 10 190 см 1 1 1 Таблица 2. Полученный замкнутый кластер наибольшей информативности, информативность 0,58 Лексемы 1 2 4 5 7 8 Атомы Петя Вася Вес Рост Юность Журнал 1 60 кг 1 1 1 1 3 50 кг 1 1 1 1 7 170 см 1 1 1 8 150 см 1 1 1 один атом равной 0,58; вошедшими атомами 1, 3, 7, 8 и лексемами 1, 2, 4, 5, 7, 8. Варьируя максимальными и минимальными ограничениями на размер результирующего кластера, можно получить кластеры разной размерности и разной удельной информативности. В таблице 3 показана зависимость полученной в результате расчета удельной информативности кластера от ограничений на размер результирующего кластера, для данной задачи. Таблица 3. Зависимость информативности кластера от ограничений Ограничения Информативность Lmin А . тт Lmax А лmax 2 2 4 4 0,83 2 2 6 6 0,83 4 4 6 6 0,58 4 4 6 8 0,54 4 6 6 8 0,43 Из таблицы 3 видно, что чем меньше кластер, тем больше информативность, это объясняется тем, что больший по размерности кластер имеет больше лексем, соответственно, для того, чтобы его информативность стремилась к единице, необходимо существование большего количества значений между всеми этими лексемами. Отметим также, что наибольшая информативность равная единице будет достигаться только для маленьких по размерности кластеров, потому что для получения данного результата необходимо, чтобы для каждого атома из кластера существовали все лексемы, включенные в кластер. Математическая модель выделения двумерной таблицы наибольшей информативности Для удобства представления информации, содержащейся в АтБД, большое значение имеет возможность использования табличной формы описания кластера. В такой таблице заголовки строк и столбцов должны содержать названия «Инфокоммуникационные технологии» Том 12, № 1, 2014 82 Ворошилов В.В., Пиявский С.А. лексем, а клетки - числа, входящие в атом информации, описание которого состоит из лексем, отвечающих строке и столбцу, на пересечении ко -торых находятся клетки. Ясно, что такими таблицами могут описываться лишь атомы, в описании которых входит не более двух лексем. За основу возьмем модель, описанную выше, м и добавим ограничение У^а„ < 2 - условие. М что выбираемые атомы содержат не более двух лексем. Рассмотрим решение этой задаче в условиях предыдущего примера. В таблице 4 показан полученный с использованием математической модели замкнутый кластер наибольшей информативности, атомы которого содержат ровно две лексемы. Таблица 4. Полученный замкнутый кластер наибольшей информативности, информативность 1 Лексемы 1 5 Атомы Петя Рост 6 180 см 1 1 Только один атом из исходной таблицы 1 имеет ровно две лексемы. Заметим, что он не является подмножеством максимально информативного кластера, выделенного из АтБД без ограничения на число лексем в описание атомов, поскольку условия этих двух задач различны, хотя математическая модель решения второй задачи получается добавлением к математической модели первой задачи дополнительного условия, что сужает множество допустимых вариантов. В таблице 5 показано описание полученного кластера в виде двумерной таблицы. Таблица 5. Описание полученного кластера в виде двумерной таблицы Рост Петя 180 см Математическая модель выделения двумерной таблицы наибольшей информативности с уточняющими лексемами Требование представления фактографической информации в виде двумерных таблиц достаточно жестко, поскольку распространяется только на атомы, описание которых содержит не более двух лексем. Его можно существенно смягчить, если допустить, чтобы в клетках двумерной таблицы указывалось не только численное значение, но и перечислялись лексемы, входящие в описание соответствующего атома, помимо лексем, записанных в строке, столбце клетки таблицы. Естественно, что общее число таких уточняющих лексем в таблице должно быть ограничено, для того чтобы она носила «удобочитаемый» вид. Пусть Z - признак включения лексемы в кластер как уточняющей лексемы (то есть она не используется в заголовках строк, столбцов, но является поясняющей). Тогда для удобства описания лексемы включаемые признаки U назовем базовыми, и Uj + Zj <1 - условие того, что уточняющая лексема не может входить в название стро- 1 N ки или столбца таблицы; U ■ + Z. >-> a -V 1 1 Nj~{ ,J 1 - условие, что если описание хотя бы одного атома из кластера содержит лексему j, то она должна быть включена в кластер как базовая или уточня-м ющая; j < Zm^ - условие, что общее число уточняющих лексем ограничено величиной Z . J г max Беря за основу модель, описанную выше, необходимо заменить ограничение числа лексем в атомах условием, что выбираемые атомы содержат не более двух базовых лексем: м V.Ya..U.<2. 1 tJ У J 7=1 Рассмотрим решение этой задачи в условиях предыдущего примера. В таблице 6 показан результирующий набор атомов и лексем замкнутой двумерной таблицы, полученных при решении задачи со следующими начальными условиями: L = 5, A = 5, L J min ’ min ’ max = 8, A = 10 и Z = 3. Отметим, что минимальные и max max максимальные ограничения на размер атома (L , A , min min L , A ) имеют средние значения. В полученной таmax max блице курсивом отмечены уточняющие лексемы. Из этого набора можно составить двумерную таблицу, где уточняющие лексемы будут вынесены непосредственно в ячейки вместе со значениями, таблица 7. Таблица 7. Описание полученного кластера в виде двумерной таблицы Вес IQ Петя 60 кг (Юность, Журнал) 120 ед Вася 50 кг (Юность,Журнал) 110 ед Лев 70 кг (Юность) «Инфокоммуникационные технологии» Том 12, № 1, 2014 Ворошилов В.В., Пиявский С.А. 83 Таблица 6. Полученный замкнутый кластер наибольшей информативности Лексемы 1 2 3 4 6 7 8 Атомы Петя Вася Лев Вес IQ Юность Журнал 1 60 кг 1 1 1 1 2 120 ед 1 1 1 3 50 кг 1 1 1 1 4 110 ед 1 1 1 5 70 кг 1 1 1 Заметим, что на полученный результат оказывает сильное влияние ограничение на максимальное количество уточняющих лексем в кластере, параметр Zmax. Рассмотрим решение этой задачи в условиях различных значений этого ограничения. При разрешенной одной уточняющей лексеме (Zmax = 1) и не менее одного атома в кластере (Amin = 1) мы получили кластер с максимальной информативностью равной единице, при этом полученный кластер и двумерная таблица имеют вид, показанный в таблицах 8 и 9. Таблица 8. Полученный замкнутый кластер наибольшей информативности при Z = 1 и A = 1 т г г max min 1 Лексем! 6 >i 7 Атомы Петя IQ Юность 2 120 ед 1 1 1 Таблица 9. Описание полученного кластера в виде двумерной таблицы при Z = 1 и A = 1 ^ А А max min IQ Юность 120 ед (Петя) При разрешенной одной уточняющей лексеме (Z = 1) и не менее двух атомов в кластере (А = v max ' J min 2) мы получили кластер с максимальной информативностью равной 0,67. Результаты показаны в таблицах 10 и 11. При значениях максимального количества уточняющих лексем в кластере равного двум или более (Zmax > 2), это ограничение не оказывает влияния на результирующий набор атомов и лексем. Но, варьируя минимальными параметрами ограничения на количество атомов и лексем в результирующем кластере (Lmin, Amin), можно получить таблицы как разной размерности и удельной информативности, так и с другим содержанием лексем и атомов. Таблица 10. Полученный замкнутый кластер наибольшей информативности при Z = 1 иА = 2 т г г max min Лексемы 3 5 6 8 Атомы Лев Рост IQ Журнал 9 130 ед 1 1 1 10 190 см 1 1 1 Отметим, что информативность полученного кластера составляет 0,67; при этом получилась полностью заполненная двумерная таблица. В таблице 12 показана зависимость построенных двумерных таблиц, полученных в результате расчета удельной информативности кластера, от минимальных ограничений на размер результирующего кластера, для данной задачи, при Zmax = 3. Таблица 11. Описание полученного кластера в виде двумерной таблицы при Z = 1 и А = 2 ^ г max min Рост IQ Лев 190 см (Журнал) 130 ед (Журнал) Заметим, что максимальные ограничения на количество атомов и лексем в результирующем кластере (L , А ) не оказывают существенного max max влияния на результирующий размер кластера. Математическая модель выделения замкнутой двумерной таблицы наибольшей информативности с вынесением уточняющих лексем в шапку Введем q - признак вынесения уточняющей лексемы в шапку, тогда atjVt > - условие, что для любого атома существует лексема, выно- «Инфокоммуникационные технологии» Том 12, № 1, 2014 84 Ворошилов В.В., Пиявский С.А. Таблица 12. Описание полученного кластера в виде двумерной таблицы при разных параметрах модели Ограничения Информативность Результирующая двумерная таблица т . = 9 л ■ =') min **min ^ 0,5 Юность Журнал Вася 110 ед (IQ) Лев 190 см (Рост) т . = 'Х л . = 9 min ^*min ^ 0,67 IQ Рост Петя 120 ед (Юность) 180 см, 170 см (Журнал) j . = 4 А - = 'З min **min 0,67 Журнал Юность Юность 60 кг, (Вес, Петя) 50 кг (Вес, Вася) Рост 170 см (Петя) 150 см (Вася) 0,5 Рост Петя 180 см, 170 см (Журнал) Вася 150 см (Юность) Лев 190 см (Журнал) симая в шапку. Рассмотрим решение данной модели на примере, описанном выше. В результате для данной задачи при различных начальных условиях, ограничениях на размер результирующего кластера (L , А , L , * * J г г V min5 min’ max-- А , Z ) было получено только одно решение с max max информативностью кластера равной 0,49, показанное в таблицах 13 и 14.

About the authors

V. V Voroshilov

Email: vitekio@yandex.ru

S. A Piyavsky

Email: spiyav@mail.ru

References

Supplementary files