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

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

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

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

То естьэтот способ делает обязательным наличие у понятия обоих свойств,описанных выше. Неизвестный коэффициент может определяться спомощью экспертной оценки, так как интерпретация обоих индексов,использованных в критерии, достаточно легка для понимания.Другой подход к подбору коэффициента заключается воптимизации критерия качества ранжирования формальных понятий.Алгоритм подбора коэффициента получает на вход множествоформальных понятий одного контекста с разметкой: '1' - все объектыпонятия - дубли, '0' - понятие содержит различные объекты. Далеерассматривается сетка на положительной вещественной оси, и на ней109максимизируется метрика качества ранжирования. Одна из такихметрик - Mean Average Precision (MAP) - более подробно описананиже.4.2.4 Формирование списков тождественных объектовСписки объектов, которые алгоритм будет выдавать в качестветождественных, формируются на основе объемов формальныхпонятий с высоким значением критерия.

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

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

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

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

Использовавшиесяметоды основаны на анализе формальных понятий и попарномсравнении объектов контекста. В качестве методов попарногосравнения объектов были рассмотрены методы на основе расстоянияХэмминга и абсолютного сходства. Данные методы могут бытьприменены к многозначному контексту или напрямую к онтологии, нодля простоты сравнения они будут описаны в применении кбинарному контексту.4.3.1 Метод на основе экстенсиональной устойчивости понятияУстойчивость формального понятия была впервые введена в [4].Позднее в работах [3,9] было предложено различать два типаустойчивости: экстенсиональную и интенсиональную.

В данной112работе использовалась экстенсиональная устойчивость, так какпредполагается, что тождественные объекты должны быть сильносвязаны большим количеством признаков и иметь небольшоеколичествоотдельныхпризнаков,соответственно,формальноепонятие, которое они образуют, должно быть устойчиво к удалениюотдельных признаков.Алгоритмпоискатождественныхобъектованалогиченосновному методу: из множества формальных понятий выделяютсянаиболее(экстенсионально)устойчивыепонятия.Затемпредполагается, что объекты из объема устойчивого формальногопонятия являются тождественными. По множеству выбранныхформальных понятий строится отношение «быть тождественным» R.Затемнаходятсякомпонентысвязностиданногоотношения.Полученные компоненты выдаются на вход в качестве итоговыхсписков объектов.4.3.2 Метод на основе меры абсолютного сходстваДанный метод основан на попарном сравнении объектов.Предполагается,чтообъектыонтологии,являющиесятождественными, имеют большое количество общих признаков.Поэтому в качестве критерия близости объектов используетсяколичество их общих признаков.

Индикатор, основанный на данноймере, представляет собой порог на количество общих признаков.Алгоритм получает на вход квадратную матрицу близостиA : A[i][ j]  k  i-й и j-й объекты имеют k общих бинарных признаков,а также порог t ( N ) .ПоматрицеAипорогустроитсяматрицасмежностиB : A[i][ j]  t  B[i][ j]  1. Матрица смежности (аналогично входной113матрице) является симметричной и описывает некоторое отношениеблизости R. Исходя из того, что отношение «быть тождественным»являетсяотношениемэквивалентностииобладаеттранзитивности, по полученному отношениютранзитивноезамыканиеR .КлассысвойствомR строится егоэквивалентностивRсоответствуют группам тождественных объектов.

Тот же результатможно получить, выделив все компоненты связности отношения R.Асимптотическая сложность алгоритма по времени - O n2  m ,где n - количество объектов в формальном контексте, m - количествопризнаков.4.3.3 Метод на основе расстояния ХэммингаАлгоритм поиска дублей основан на попарном сравненииобъектов. В качестве метрики близости используется расстояниеХэмминга. Вначале составляется квадратная матрица расстояниймежду объектами. Затем, по построенной матрице A и заданномупорогу t ( N ) строится матрица B отношения «быть тождественным»R : A[i][ j ]  t  B[i][ j ]  1, ( xi , x j )  R .Полученноеотношениесимметрично и рефлексивно.

По данному отношению находятсякомпоненты связности. Объекты, попавшие в одну компонентусвязности, считаются тождественными.Асимптотическая временная сложность алгоритма в худшемслучае аналогична сложности алгоритма на основе абсолютногосходства - O n2  m , где n - количество объектов в формальномконтексте, m - количество признаков.1144.4 Экспериментальные исследования4.4.1 Эксперименты на формальных контекстах4.4.1.1 Схема экспериментаДля того чтобы получить статистические оценки качестваразработанного алгоритма, основные эксперименты проводились наискусственносгенерированныхданныхсзаранееизвестнымитождественными объектами.

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

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

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