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

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

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

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

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

Послеэтого генерировался входной контекст, включающий в себя уже нетолько уникальные, но и тождественные друг другу объекты. Длякаждого уникального объекта «тождественный» объект в контекстегенерировался следующим образом: каждый признак исходногообъекта с фиксированной вероятностью добавлялся во множествопризнаков нового объекта. Для некоторых исходных объектовподобным образом создавалось несколько объектов.Дляпроведениясравнительногоанализаиспользовалосьнесколько метрик качества метода: полнота, точность, среднеезначение полноты алгоритма при 100% значении точности, MAP.

Вкачестве основных метрик использовались полнота и точностьалгоритма.Для того чтобы корректно определить полноту и точность,рассмотрим задачу поиска тождественных денотатов как задачуудаления из множества объектов онтологии тождественных другдругу объектов. Тогда выделенную алгоритмом группу объектовбудем интерпретировать как удаление из онтологии всех объектовгруппы за исключением одного.

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

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

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

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

Недостаток индекса в том, что он не учитываетразличия объектов. К тому же некоторые признаки встречаются убольшого количества объектов, и наличие их среди общих признаковне дает большого вклада в уверенность, что объекты являютсятождественными.Алгоритм на основе нового индекса (с использованием какодного, так и другого варианта комбинации) показал более высокиерезультаты,чемрассмотренныеальтернативы.Основной120отличительной особенностью метода является небольшое падениеточности алгоритма (до 90%) при росте полноты вплоть до 70%.

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

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

Оптимальные пороги для методов и качество поискаАлгоритмПорог валгоритмеПолнотаТочностьНа основе абсолютного расстояния3.5019.35%98.82%На основе расстояния Хэмминга0.5034.37%86.32%На основе индекса устойчивости0.5022.44%100%На основе нового индекса DII 1.1540.09%99.58%На основе нового индекса DII0.9031.80%99.55%4.4.2 Эксперименты на прикладной онтологии4.4.2.1 Описание прикладной онтологииОнтология, на которой был апробирован предложенныйалгоритм, была построена компанией Авикомп. Онтология строиласьи расширялась автоматически путем семантической обработки потокановостных сайтов программным средством OntosMiner [22].По обработанному документу строится небольшая онтология собъектами и связями, выделенными в тексте. Затем онтологиядокумента сливается с основной онтологией.

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

Она содержит 12006объектов различных классов. Объекты имеют различное количествопризнаков и связей с другими объектами. Количество признаков исвязей с другими объектами распределено по закону Ципфа.123Ванализируемойонтологиибылпроведенпоисктождественных денотатов среди объектов классов «Персона» и«Компания».Такихобъектоввонтологии9821.Признакиформального контекста строились с использованием всех объектов исвязей в онтологии.4.4.2.2 Анализ результатовДля получения точных оценок полноты и точности алгоритмовнеобходимо иметь информацию о том, какие объекты являютсятождественными.

Данную информацию можно получить лишь спомощью экспертной оценки коллекции обработанных документов. Ксожалению, в силу специфики задачи (автоматическое построениеонтологии и большой объем исходных документов), получить точнуюоценку полноты не представляется возможным.Изначально алгоритм на основе индекса DII (использовалсявариант DII  ) выделил около 900 групп объектов. В результатеэкспертной оценки было выявлено несколько ошибок. Алгоритмобъединил объекты с разными именами/фамилиями, которые имелибольшое количество общих связей и признаков (партнеры, коллеги).Ошибка возникает из-за того, что алгоритм не учитывает, чторазличные значения некоторых конкретных признаков говорят о том,что объекты не являются тождественными.

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

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