Автореферат (Разработка вычислительных методов анализа текстов с использованием аннотированных суффиксных деревьев), страница 3

На первом шаге этого метода строится непосредственно суффиксное дерево. На втором шаге, обходя дерево снизу и зная, что9частота каждого листового узла равна единице, аннотируем дерево. Использование этого модифицированного метода предполагает добавление терминальныхсимволов к концу строк. Для построения АСД по тексту требуется предварительное представление текста как совокупности строк последовательно идущих слов.Строки строятся следующим образом: первая строка начинается с первого словав тексте и заканчивается 2м, 3м или 4м словом в тексте; вторая начинается со второго слова и заканчивается соответственно на 3-5 слове.

При этом учитываютсяграницы предложений. Такое представление существенно ограничивает глубину и, следовательно, сложность формируемого АСД, зато существенно сокращает вычисления. Количество слов в строке определяется в зависимости от задачи.Таблица релевантности «строка – текст» строится помощью метода нормированного АСД. В этой таблице строки соответствуют отдельным входным строкам,столбцы – отдельным текстам, а элементы – оценки релевантности строк соответствующим текстам.В третьей, четвертой и пятой главах рассматриваются примеры использования теоретико-множественной модели коллекции текстовых методов и ассоциированного метода вычисления релевантности, использующего нормированное аннотированное суффиксное дерево: задача рубрикации аннотаций научныхпубликаций темами таксономии, задача пополнения научной таксономии и задача фильтрации обсценной лексики, соответственно.В третьей рассмотрена задача рубрикации научных статей.

Задача рубрикации научных статей заключается в категоризации статей в системе рубрик,заданных классификатором или таксономией (корневым деревом тематическихединиц) соответствующей области знания или технологии. Для решения задачикатегоризации в режиме без учителя мы предлагаем формировать РСТ таблицутаксономическая тема – текст, после чего каждый текст категоризуется таксономическими темами, получившими наивысшие оценки релевантности.

Авторомсоставлен и проведен эксперимент по сравнению относительных преимуществиспользования различных мер релевантности в проблеме рубрикации научныхстатей. Входные данные эксперимента:– 5079 аннотации научных статей из журналов ACM, хранящиеся в свободном доступе в электронной библиотеке ACM Digital Library;– Таксономия ACM CCS 2012, состоящая из 2074 таксономических тем инасчитывающая 6 уровней;– Авторские темы, приписанные аннотациям научных статей их авторами– 2-3 таксономические темы низших уровней, а также все темы, лежащиена пути от корня до них в дереве таксономии ACM CCS.В эксперименте рассматриваются наиболее популярные в международнойлитературе меры релевантности, и производится сравнение результатов их использования с результатами использования введенной нами меры средней условной вероятности символа в совпадении (СУВСС).

Полный список рассмотренных мер релевантности приведен в Таблице 1.10Таблица 1 — Обозначения мер релевантности в задаче рубрикации научныхстатейОбозначениеМера релевантностиcosineКосинусная мера релевантностиLSINКосинусная мера релевантности со снижениемдо N размерностей методом LSILDANМера релевантности, основанная на ЛРД с Nтемамиokapibm25Мера релевантности BM25Jaccardкоэффициент Жаккара на множестве буквенных n-граммconstantXмера СУВСС с константной шкалирующейфункцией и очисткой шума от уровня XlinearXмера СУВСС с линейной шкалирующей функцией и очисткой шума от уровня XsquareXмера СУВСС с шкалирующей квадратичнойфункцией и очисткой шума от уровня XrootXмера СУВСС с линейной шкалирующей функцией корень квадратный и очисткой шума отуровня XlogXмера СУВСС с логарифмической шкалирующей функцией и очисткой шума от уровня XlogitXмера СУВСС с логистической шкалирующейфункцией и очисткой шума от уровня XsigmoidXмера СУВСС с шкалирующей функцией сигмоид и очисткой шума от уровня XВ эксперименте использовались различные способы предобработки текстов.

Косинусная мера релевантности и мера релевантности BM25 предполагают представление текста в виде мешка термов – неупорядоченного набора термов, использование меры Жаккара – в виде множеств n-грамм, использованиеСУВСС – в виде набора строк.Для оценки результатов две популярные характеристики точности: MAP(Mean Average Precision) и nDCG (normalized discounted cumulative gain), а такжепредложенные автором меры I(k) и J(k), имеющие смысл доли количества статей, верно аннотированных хотя бы одной темой и доли таксономических единиц, формирующих верные аннотации.11Таблица 2 — Результаты эксперимента: меры MAP и nDCGMAP5MAP10 MAP15 nDCG5 nDCG10косинусная мера релевантностиwords0.1775 0.2073 0.2242 0.0478 0.1073stems0.1874 0.2206 0.2368 0.0482 0.1146lemmas0.1970 0.2302 0.2464 0.0478 0.11414gram0.2202 0.2569 0.2733 0.0516 0.1242мера релевантности BM25words0.0294 0.0372 0.0423 0.0062 0.0222stems0.0602 0.0724 0.0789 0.0185 0.0442lemmas0.0455 0.0556 0.0629 0.0127 0.03404gram0.1247 0.1407 0.1489 0.0309 0.0613мера релевантности, основанная на АСДlinear00.2734 0.3071 0.3221 0.0508 0.1162linear10.2742 0.3075 0.3233 0.0500 0.1142root00.2854 0.3226 0.3369 0.0534 0.1268root10.2826 0.3170 0.3324 0.0548 0.1221sigmoid0 0.2904 0.3258 0.3400 0.0576 0.1264sigmoid1 0.2873 0.3207 0.3359 0.0591 0.1257nDCG150.17700.18060.18060.19140.04390.07090.06430.09610.17860.17930.18700.18680.18480.1874Использование нечетких мер релевантности, основанных на аннотированных суффиксных деревьях в полтора раза увеличивает точность по сравнению состальными мерами релевантности, при этом, вид шкалирующей функции (квадратичная, корень квадратный, линейная или сигмоид) не играет особой роли(за исключением логарифмической или логистической).

По мерам nDCG@15и M AP @15 результаты АСД-релевантности в среднем в полтора раза лучше результатов по мере Жаккара, косинусной мере и мере BM25, в том числе, с учетомснижения размерности. По абсолютным показателям I(k) и J(k), результаты использования АСД, в среднем на 30 - 40 единиц превосходят результаты по мереЖаккара, косинусной мере и мере BM25 , в том числе, с учетом снижения размерности.12Таблица 3 — Результаты эксперимента: меры I(k) и J(k)I5I10 I15 J5J10 J15косинусная мера релевантностиwords333 543 741 239 348 427stems344 578 766 238 352 439lemmas350 584 773 253 365 4474gram387 644 835 276 399 477мера релевантности BM25words53107 165 4486138stems120 207 285 97154 197lemmas87168 236 72134 1834gram237 330 426 194 242 287мера релевантности, основанная на АСДlinear0429 662 839 321 423 491linear1427 656 841 322 424 498square0401 621 796 306 409 480square1406 624 799 308 411 479root0451 711 881 328 446 515root1452 691 874 332 438 511log043117 180 3698143log166114 136 6191105logit0103 197 284 84154 217logit1426685385566sigmoid0 467 712 878 332 453 509sigmoid1 468 703 879 337 440 51313Рис.

3 — Схема пополнения таксономии. В прямоугольниках находятся темыосновы таксономии, в скругленный прямоугольниках – достроенные категориии подкатегории Википедии. Листья достроенной таксономии – названия статейВикипедии – помещены в овалы. В облачках находятся уточнения листьев.В четвертой главе рассмотрена проблема автоматизации построения таксономий – весьма актуальная как для обработки текстов, так и информационного поиска. Метод построения таксономии, предложенный автором, состоит издвух шагов. На первом шаге задается основа таксономии, два или три уровня,построенных вручную, основываясь на официальных документах и определениях из паспортов специальностей ВАК.

Второй шаг заключается в пошаговомпополнении этой основы детализирующими материалами интернета. В качестветаковых рассматриваются фрагменты дерева категорий и статей русскоязычнойВикипедии. Для соотнесения категорий, названий статей, таксономических теми статей и очистки дерева категорий Википедии от шума используется мера релевантности СУВСС и аппарат РСТ таблиц. Структура результирующей таксономии представлена на Рис. 3.

Метод проиллюстрирован применением к двум областям математики – теории вероятностей и математической статистики (ТВиМС)и численным методам (ЧМ).Данные, извлеченные из Википедии, необходимо предварительно очистить от шума. Требуется удалить циклы из дерева категорий, если они в неместь, и оставить в дереве только такие подкатегории и статьи, которые имеютлогическую и смысловую связь с родительскими категориями.

Второй шаг метода состоит из следующих этапов:1. Извлечение дерева категорий и статей из Википедии2. Очистка дерева категорий от нерелевантных статей3. Очистка дерева категорий от нерелевантных подкатегорий4. Достраивание категорий Википедии к темам таксономии5.

Формирование промежуточных уровней таксономии6. Использование названий статей Википедии в качестве листьев в получаемой таксономии7. Излечение ключевых слов и словосочетаний из статей Википедии дляиспользования их в качестве уточнений листьев.14Таблица 4 — Качество очистки от шумаАСДшумне шумэкспертышум не шум7316721264Таблица 5 — Качество достраивания категорий Википедии к темам таксономиии формирования промежуточных уровнейэкспертыродитель не родительродитель40351АСДне родитель 9578Оценка построенной таксономии ТВиМС была проведена при помощи экспертов.

Для них был составлен специальный опросник, в первой части которогоэкспертов просили определить шумовые темы, а во второй – указать для даннойтемы родительскую тему. Таким образом, при помощи первой части опросникабыла проверена точность очистки от шума, а при помощи второй части опросника – точность и корректность достраивания промежуточных уровней таксономии.В экспертной оценке построенной таксономии ТВиМС участвовали дваэксперта. Полученные результаты представлены в Таблицах 4 и 5.Аккуратность accuracy очистки от шума составляет 0.91, достраивания категорий Википедии к темам таксономии и формирования промежуточных уровней – 0.76.Достоверность проведенного экспертного оценивания определяется независимо для обеих частей исследования.

Согласованность ответов экспертов навопросы из Части 1 определяется с помощью коэффициента κ Коэна, на вопросы из Части 2 – долей несовпавших ответов. Коэффициент согласованности κКоэна ответов на вопросы из Части 1 составляет 0.319, т.е., в принципе, ответыэкспертов можно считать согласованными. Доля несовпавших ответов на вопросы из Части 2 составляет 12%.Предложенный метод пополнения таксономии ReTAST-w позволяет построить качественную таксономию: доля полученных ошибок не велика, экспертные оценки, подтверждающие высокое качество таксономии, – достаточновысоки и согласованы на приемлемом статистическом уровне. Фрагменты достроенных таксономий представлены на Рис. 4 и Рис. 5.В пятой главе используется аналогия между задачей поиска по однословному ключу и фильтрации нежелательной (в данном случае – обсценной) лексики.. Утверждается, что несмотря на то, что для решения этих задач могут бытьиспользованы одинаковые методы, оптимизируются разные критерии качества,которые влияют на выбор конкретного метода.