Диссертация (1137218), страница 15

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 15)

Другойособенностьюзадачиявляется«неравносильность»ошибок первого и второго рода. Ошибка первого рода (принятиедвух описаний одного объекта за разные объекты) приводит ктому, что объекты онтологии содержат неполную информацию обобъектах реального мира. Ошибка второго рода (объявление двухразличныхобъектовтождественными)приводиткболеесерьезным последствиям – а именно, к введению в онтологиюневерной информации об объекте.4.2 Алгоритм поиска тождественных денотатовНиже описан разработанный алгоритм поиска тождественныхденотатов в прикладной онтологии, который основан на методаханализа формальных понятий.102Навходалгоритмпринимаетприкладнуюонтологию.Онтология содержит объекты разных классов, объекты могут бытьсвязаны отношениями, соответствующими их классам.

Количествовыявленных признаков и связей объекта может сильно варьироваться.Некоторые объекты описывают один и тот же объект реального мира.На выходе алгоритм выдает списки объектов, которые былиидентифицированы им как тождественные. Выявление объектов вонтологииосуществляетсянаосновеобъединениязамкнутыхмножеств объектов с помощью методов анализа формальных понятий[26].Алгоритм состоит из двух этапов. Первый этап - преобразованиеонтологии в формальный контекст.

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

Множество объектов контекста - это множество O объектовисходной онтологии.2. Множество признаков контекста - это множество M  L  C  R ,где: L - множество атрибутов исходной онтологии, C - множество бинарных признаков, совпадающее с множествомклассов из структуры онтологии, R - множество бинарных признаков, описывающих связи междуобъектами онтологии. Каждая связь ( x, y)  instr (P)( p  P) вонтологии порождает два бинарных признака в контексте:p( x, _) и p(_, y) . Они соответствуют связи p, идущей от объектаx, и связи p, идущей к объекту y. Таким образом, объект x будетобладать признаком p(_, y) , объект y – признаком p( x, _) .3. Каждый объект g получает следующие значения атрибутов: Для признака из исходной онтологии l  L :instl ( L), если attr (l )  inst ( g )l(g)  null в противном случае Для признака c  C :  True, если (inst ( g ), c)  H Cc( g )   False в противном случае,где  H C  - транзитивное рефлексивное замыкание отношенияHC .104 Для атрибута r  R вида p( x, _) : True, если ( x, g )  instr ( p)r(g)   False в противном случае Для атрибута r  R вида p(_, x) : True, если ( g , y)  instr ( p)r(g)   False в противном случаеИными словами, каждый объект получает: Значения своих исходных атрибутов; Специальное значение null для атрибута a, если:o значение данного атрибута для него неизвестно;o атрибут a у данного объекта отсутствует. Бинарныепризнаки,соответствующиеклассуобъектаикаждому его надклассу; Бинарные признаки, соответствующие его связям с другимиобъектами.Данный подход к преобразованию позволяет учесть всюинформацию об объекте, содержащуюся в исходной онтологии.После получения многозначного контекста из онтологии намнеобходимо построить бинарный (формальный) контекст.

Для этогокаждый признак многозначного контекста преобразовывается внесколькобинарныхпризнаков.Данныйпроцессназываетсяшкалированием [28]. Признаки многозначного контекста из множествC и R изначально имеют бинарный вид, поэтому в преобразовании неучаствуют. Признаки из множества L шкалируются в зависимости оттипа признака. Как правило, большая часть признаков описываетнеколичественные свойства объекта (например, имя человека,название компании и т.д.). К тому же многие из количественных или105просто числовых признаков таковы, что приближенное сходство поэтим признакам не говорит о сходстве объектов. К примеру, если дваобъекта-компании имеют значения признака «Год создания» 2005 и2006, то близость (но не совпадение) значений этого признака неповышает уверенность в том, что объекты описывают одну и ту жекомпанию, а скорее дает обратный эффект.

Для таких признаковимеет смысл только совпадение значений признака. Если значенияразличны, то расстояние между ними не имеет значения. Такиепризнаки шкалируются номинальной шкалой, то есть каждомузначению признака соответствует свой бинарный признак. Костальным количественным признакам могут применяться другиетипы шкалирования, такие как: Интервальное: преобразование признака A во множествобинарных признаков вида « a  A  b ». При этом интервалы[a, b) могут быть как непересекающимися, так и с перекрытием. Порядковое: признак A преобразовывается во множествобинарных признаков вида « A  b ». Другие виды шкалирования, которые, по мнению эксперта,могут лучшим образом характеризовать сходство объектов какдублей.В описанных ниже экспериментах на сгенерированных данныхиреальнойонтологиииспользовалосьтолькономинальноешкалирование, однако это не ограничивает общности предложенногоподхода.4.2.2 Построение множества формальных понятийПо полученному формальному контексту строится множествоформальных понятий.

Существует несколько эффективных методов106нахожденияформальныхпонятий.Внашемисследованиииспользовался алгоритм AddIntent [29].Время работы данного алгоритма асимптотически равноO(| L |  | G |2 max(|{g}|, g G)) , где | L | - количество формальныхпонятий контекста, G - множество объектов контекста, |{g}| - числопризнаков, которыми обладает объект.Алгоритм довольно эффективен для работы с контекстами,полученными из онтологий, так как такие контексты содержатотносительно небольшое число формальных понятий и большая частьобъектов имеет всего несколько признаков.Один из альтернативных подходов построения формальныхпонятий основан на построении надпонятий для уже найденныхпонятий. Этот подход реализован, например, в алгоритме Замыкай-поОдному [3].

Его преимуществом является возможность остановкиалгоритма при достижении определенного размера понятий. Этосвойство позволяет порождать не все понятия контекста, а толькопонятия с небольшим объемом, так как большие группы объектовскорее всего не являются дубликатами одного и того же реальногообъекта.4.2.3 Критерии фильтрации формальных понятийПосле построения множества формальных понятий необходимовыделить те формальные понятия, объем которых содержит толькотождественные объекты.При подборе критериев были учтены основные свойства,которыми должны обладать эти понятия. Во-первых, критерийдолжен принимать большее значение, если, при прочих равных,число признаков, которыми отличаются объекты понятия, будет107меньше.Вкачествекритерия,характеризующего"разброс"признаков, был использован следующий индекс:I1 ( A, B) | A || B | gA gМаксимальное значение индекса ( I1  1 ) достигается в случае,если ни один из объектов понятия не обладает признаками, невходящими в содержание понятия.

Значение индекса стремится кнулю при уменьшении содержания понятия и увеличения у объектовпонятия числа признаков вне содержания понятия.Второесвойство,которымдолженобладатькритерий - увеличение значение индекса при увеличении числаобщих признаков (при прочих равных). При этом необходимоучитывать частоту признака. Распространенный признак долженделать меньший вклад в значение критерия, чем редкий, так как чемпризнак более распространен, тем больше шансов, что понятие сданным признаком возникло из-за случайного пересечения признаков.В результате был разработан индекс, обладающий этимсвойством:I 2 ( A, B) mBAmЛегко заметить, что появление нового признака в содержанииформального понятия (при прочих равных) увеличивает значениеиндекса.

Характеристики

Список файлов диссертации