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

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

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

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

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

Матрица смежности (аналогично входнойматрице) является симметричной и описывает некоторое отношениеблизости R. Исходя из того, что отношение «быть тождественным»являетсяотношениемэквивалентностииобладаеттранзитивности, по полученному отношениютранзитивноезамыканиеR .КлассысвойствомR строится егоэквивалентностивRсоответствуют группам тождественных объектов. Тот же результатможно получить, выделив все компоненты связности отношения R.111Асимптотическая сложность алгоритма по времени - 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 - количество признаков.4.4 Экспериментальные исследования4.4.1 Эксперименты на формальных контекстах4.4.1.1 Схема экспериментаДля того чтобы получить статистические оценки качестваразработанного алгоритма, основные эксперименты проводились наискусственносгенерированныхданныхсзаранееизвестнымитождественными объектами.

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

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

Для некоторых исходных объектов создавалось несколькообъектовподобнымобразом.Полученныеобъектысчиталисьтождественными друг другу.Дляпроведениясравнительногоанализаиспользовалосьнесколько метрик качества метода: полнота, точность, среднеезначение полноты алгоритма при 100% значении точности, MAP. Вкачестве основных метрик использовались полнота и точностьалгоритма.Для того чтобы корректно определить полноту и точность,рассмотрим задачу поиска тождественных денотатов как задачуудаления из множества объектов онтологии тождественных другдругу объектов. Тогда выделенную алгоритмом группу объектовбудем интерпретировать как удаление из онтологии всех объектовгруппы за исключением одного. Таким образом, мы определяемполноту и точность алгоритма:Рrecision Rеcall Ddub  DdelDdelDdub  DdelDdubЗдесь Ddub - количество «дублей» (если есть n тождественныхобъектов онтологии, считается, что среди них есть n 1 «дубль»),Ddel - количество удаляемых объектов (если алгоритм выдал группу изn объектов, считается, что мы удаляем n 1 объект; причем если срединих есть k различных по построению объектов, то считается, что k 1объект мы удалили неправильно).114Таккаккачествохарактеризуетсякомбинациейэтихпоказателей, а все сравниваемые алгоритмы имели дополнительныепараметры (пороги), то рассматривались зависимости полнотыалгоритма от точности, путем прогона алгоритмов с различнымивходными параметрами.Такжедляоценкииспользоваласьметрикакачестваранжирования MAP (Mean Average Precision): AveP(Ki )Map( K )  i 1KKAveP(k )  cC (P(c)) ,kCkгде K - множество контекстов, Ck - множество релевантныхформальных понятий контекста k, P(c) - доля релевантных понятийсреди всех понятий, имеющих ранг не ниже, чем у понятия c.4.4.1.2 РезультатыДляоценкиновогометодасначалабылиподобраныоптимальные коэффициенты для индекса.

Коэффициент подбиралсяпо одному из сгенерированных контекстов. Бралась сетка наположительной вещественной оси, и на ней максимизировался индексMAP.Такимобразом,былиполученыкоэффициентыдляиспользовавшихся вариантов индекса DII:DII   I1  0.25I 2DII  I1  I 20.18Алгоритм с данным индексом сравнивался с альтернативнымиметодами. Для построения зависимости точности алгоритма от его115полнотыдлякаждогометодазадавалосьнесколькодесятковразличных порогов, затем рассчитывались полнота и точностьалгоритма при каждом пороге.

Эти показатели рассчитывались длянескольких сгенерированных контекстов, далее определялось среднеезначение полноты и точности для каждого порога. Полученныесоотношения позволяют сравнить использовавшиеся алгоритмы(рисунки 4.1, 4.2).Рис. 4.1. Зависимость точности алгоритмов от полноты.116Рис. 4.2. Зависимость точности от полноты для двух вариантов новогоиндекса DIIМетод на основе экстенсиональной устойчивости показываетхорошие результаты при высоком пороге на индекс. При порогебольше 0.5 отбираются только формальные понятия, содержащиетождественные объекты.

При пороге ниже 0.5 точность алгоритмападает в среднем до 10%, так как большое количество формальныхпонятий с устойчивостью 0.5 - однопризнаковые понятия, которые поопределению не характеризуют тождественные объекты.Алгоритм с использованием расстояния Хэмминга показалсравнительно низкие результаты. Так как расстояние может бытьтолько целым положительным числом, снижение порога на 1добавляет группу новых связей.

При достаточно низком порогеточность близка к 100%, но даже среди объектов, имеющиходинаковый набор признаков, могут быть пары, не являющиеся117тождественными. Как правило, это объекты с 1-2 распространеннымипризнаками. Но расстояние Хэмминга не учитывает количествообщих признаков, а только различия в признаках.Алгоритм на основе абсолютного сходства объектов оказалсянаиболееэффективнымсредирассмотренныхальтернативныхалгоритмов. В большинстве случаев большое количество общихпризнаков у пары объектов говорит о том, что объекты являютсятождественными. Недостаток индекса в том, что он не учитываетразличия объектов.

К тому же некоторые признаки встречаются убольшого количества объектов, и наличие их среди общих признаковне дает большого вклада в уверенность, что объекты являютсятождественными.Алгоритм на основе нового индекса (с использованием какодного, так и другого варианта комбинации) показал более высокиерезультаты,чемрассмотренныеальтернативы.Основнойотличительной особенностью метода является небольшое падениеточности алгоритма (до 90%) при росте полноты вплоть до 70%. Поостальным метрикам данный метод показал высокие результаты.Результаты для DII  и DII оказались весьма схожими. ОтличиемDII стало менее стабильное поведение: иногда ошибаясь прибольшом пороге, в ряде случаев алгоритм не делал ошибок при малыхпорогах, выделяя при этом 42% тождественных объектов.По показателю максимальной полноты без потери точностинаиболееэффективнымоказалсяметоднаосновеиндексаустойчивости, который позволяет, поставив порог на индекс равным0.5, выделять в среднем 22.44% тождественных объектов.

При этоминдекс DII  «отстал» по этому показателю незначительно, в отличиеот методов попарного сравнения. Методы на основе попарного118сравнения показали значительно более низкие результаты по даннойметрике (таблица 4.1).Таблица 4.1. Максимальная полнота алгоритмов при максимальнойточностиАлгоритмМаксимальная полнота приточности 100% (наэкспериментальных данных)Алгоритм на основеабсолютного расстояния6.22%Алгоритм на основерасстояния Хэмминга0.56%Алгоритм на основе индексаустойчивости22.44%Алгоритм на основе новогоиндекса DII 21.78%Алгоритм на основе новогоиндекса DII9.49%При сравнении методов на основе индекса экстенсиональнойустойчивости и вариантов нового индекса DII  и DII по мере MAPочевидное преимущество имеет новый индекс (таблица 4.2).Таблица 4.2. Результаты оценки по мере Mean Average PrecisionАлгоритмMAPАлгоритм на основе индекса устойчивости0.499Алгоритм на основе нового индекса DII 0.935Алгоритм на основе нового индекса DII0.938Для каждого метода был подобран оптимальный порог, прикотором алгоритм имеет оптимальную полноту при минимальныхпотерях точности (таблица 4.3).119Таблица 4.3.

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

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