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

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

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

Множество объектов контекста - это множество O объектовисходной онтологии.2. Множество признаков контекста - это множество M  L  C  R ,где:101 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 . Для атрибута r  R вида p( x, _) : True, если ( x, g )  instr ( p)r(g)   False в противном случае Для атрибута r  R вида p(_, x) : True, если ( g , y)  instr ( p)r(g)   False в противном случае102Иными словами, каждый объект получает: Значения своих исходных атрибутов; Специальное значение null для атрибута a, если:o значение данного атрибута для него неизвестно;o атрибут a у данного объекта отсутствует. Бинарныепризнаки,соответствующиеклассуобъектаикаждому его надклассу; Бинарные признаки, соответствующие его связям с другимиобъектами.Данный подход к преобразованию позволяет учесть всюинформацию об объекте, содержащуюся в исходной онтологии.После получения многозначного контекста из онтологии намнеобходимо построить бинарный (формальный) контекст.

Для этогокаждый признак многозначного контекста преобразовывается внесколькобинарныхпризнаков.Данныйпроцессназываетсяшкалированием [18]. Признаки многозначного контекста из множествC и R изначально имеют бинарный вид, поэтому в преобразовании неучаствуют.

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

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

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

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

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

В данной работе использовалисьследующие способы комбинации:1. Линейная комбинация описанных индексов: DII  k1I1  k2 I 22. Произведениеиндексовсостепеннымикоэффициентами:DII  I1k1  I 2k2Так как абсолютные значения коэффициентов влияют только назначениепорога,акачествофильтрациибудет определяться106соотношением коэффициентов в формуле критерия, можно сузитьсемейство критериев без потери оптимального, взяв 1 в качествезначения одного из коэффициентов. Тогда семейства критериев будутпредставлены в виде формул с одной степенью свободы:DII   I1  kI 2DII  I1  I 2kСледуетотметить,чтоприранжированииспомощьюпроизведения формальные понятия, для которых значения одного изиндексов равны или близки к нулю, окажутся в конце списка.

То естьэтот способ делает обязательным наличие у понятия обоих свойств,описанных выше. Неизвестный коэффициент может определяться спомощью экспертной оценки, так как интерпретация обоих индексов,использованных в критерии, достаточно легка для понимания.Другой подход к подбору коэффициента заключается воптимизации критерия качества ранжирования формальных понятий.Алгоритм подбора коэффициента получает на вход множествоформальных понятий одного контекста с разметкой: '1' - все объектыпонятия - дубли, '0' - понятие содержит различные объекты.

Далеерассматривается сетка на положительной вещественной оси, и на неймаксимизируется метрика качества ранжирования. Одна из такихметрик - Mean Average Precision (MAP) - более подробно описананиже.4.2.4 Формирование списков тождественных объектовСписки объектов, которые алгоритм будет выдавать в качестветождественных, формируются на основе объемов формальныхпонятий с высоким значением критерия.

Алгоритм предусматривает107дварежимаработы:автоматическоепринятиерешенияиполуавтоматический режим с привлечением эксперта-аналитика.В автоматическом режиме подразумевается, что аналитик неучаствует в принятии решения о том, являются ли объектыформального контекста тождественными. Формирование состоит издвух этапов.Первый этап заключается в фильтрации формальных понятий попорогу на разработанный критерий.

На этом шаге могут добавлятьсяразличные эвристики, которые трудно учесть с помощью критерия. Врезультате фильтрации формируется список формальных понятий свысоким значением критерия.Второйэтапзаключаетсявформированиисписковтождественных объектов. Поскольку предполагается, что отношение«быть тождественным» (здесь и далее - на множестве объектов)транзитивное, а объекты отобранного формального понятия связаныэтим отношением друг с другом, задача формирования списков такихобъектов сводится к поиску компонент связности этого отношения намножестве объектов.Построение списков осуществляется следующим образом.Вначале строится симметричное отношение R «быть тождественным».Для каждого формального понятия с объемом {g1,R добавляются пары ( g1, gi ), g  2, gn} в отношениеn .

Затем по построенномуотношению находятся компоненты связности алгоритмом на основеобхода вширину.Полученныекомпонентысвязностибудутсоответствовать спискам объектов, выделенных как тождественныедруг другу.108Альтернативный режим работы алгоритма подразумевает, чторешение о том, являются ли объекты понятия тождественными,принимает аналитик. В этом случае алгоритм предлагает понятияаналитику в порядке уменьшения «уверенности», что его объектытождественны друг другу.Алгоритм последовательно предлагает аналитику оценитьпонятия, упорядоченные по убыванию значений критерия DII.

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

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

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

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