Поиск

Полнотекстовый поиск:
Где искать:
везде
только в названии
только в тексте
Выводить:
описание
слова в тексте
только заголовок

Рекомендуем ознакомиться

'Документ'
Со словами «Ветер дует на » ведущий начинает игру. Чтобы участники игры побольше узнали друг о друге, вопросы могут быть следующими: «Ветер дует на то...полностью>>
'Рабочая программа'
Рабочая программа составлена на основе Примерной программы основного общего образования по химии, а также программы курса химии для учащихся 8-9 класс...полностью>>
'Документ'
В соответствии с п. 80 Правил землепользования и застройки Петрозаводского городского округа, п. 5 ст. 33 Градостроительного кодекса РФ инициативная г...полностью>>
'Документ'
В целях совершенствования государственного надзора за безопасностью работ на предприятиях горнорудной и нерудной промышленности, подконтрольных Госгор...полностью>>

Главная > Документ

Сохрани ссылку в одной из сетей:
Информация о документе
Дата добавления:
Размер:
Доступные форматы для скачивания:

Взаимная информация

Оценка взаимной информации – класс широко используемых метрик для измерения корреляции векторов. В рассмотренном случае она используется при сравнении эталонной и прогнозной классификации и характеризует их согласованность. Данный метод, как и предыдущий, не зависит от взаимного соответствия между классами и кластерами.

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

Как стандартная взаимная информация, так и ее нормированная модификация являются смещенными оценками.

Обозначим два разбиения пространства объектов U и V. Тогда энтропия неравномерности для каждого разбиения задается по формуле:

где – вероятность того, что случайный элемент попадет в класс . Аналогичная величина определяется и для :

при этом вероятность попадания случайного элемента в класс обозначается величиной .

Взаимная информация определяется формулой:

где – вероятность того, что случайный объект попадет в оба класса и .

Сама по себе взаимная информация существенно зависит от абсолютных значений выборки. Поэтому используется нормированный вариант, определяемый следующим образом:

Обе метрики не учитывают стохастической составляющей и, кроме того, их значения возрастают при увеличении числа кластеров, хотя сама по себе кластеризация может быть неудачной.

Статистический метод усреднения был предложен в статье [Vinh, Epps & Bailey, 2009]. Нам понадобиться обозначить , . Тогда верна следующая оценка:

Используя эту величину, можно вычислить усредненную взаимную информацию:

Точность, полнота и V-мера

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

В статье [Rosenberg and Hirschberg, 2007] описываются два интуитивно понятных требования для оценки качества кластеризации.

Во-первых, каждый кластер должен содержать элементы одного класса. Во-вторых, все члены одного класса должны попасть в один кластер. Исходя из этого строятся следующие метрики.

Для эталонной классификации и прогнозной кластеризация обозначим величину, называемую условной энтропией разбиения:

а – энтропию класса, определенную по формуле:

где – общее число элементов, и – число элементов соответственно в классе и кластере . Аналогично зададим и .

Точность (homogeneity), характеризующая величину ошибки первого рода, т.е. количество элементов разных классов, попавших в один кластер, определяется по формуле:

Аналогично полнота (completeness), характеризующая, в свою очередь, величину ошибки второго рода – количество элементов разных классов, оказавшихся в одном кластере, – задается по формуле:

Их комбинация (-мера), учитывающая и величину полноты, и точности, является средним гармоническим:

Все величины имеют значения в пределах от нуля до единицы. Использование данных метрик позволяет более детально оценить проблемы той или иной кластеризации: ошибки первого и второго рода. Это полезно при регулировке параметров алгоритма.

С другой стороны, V-мера чувствительна по отношению к шуму (т.е. смещена). Случайное разбиение, таким образом, не всегда имеет нулевую метрику. Кроме того, все три метрики зависит от размера выборки, числа кластеров и структуры классификации.

Этой проблемой можно пренебречь, когда объем выборки более тысячи, а число кластеров менее 10.

Коэффициент силуэта

Как мы уже замечали, если эталонная классификация неизвестна, следует использовать один из коэффициентов качества, описанных ранее. Такие метрики, естественно, весьма условны. Во-первых, даже эталонная классификация не всегда им удовлетворяет. Во-вторых, всякий алгоритм кластеризации минимизирует тот или иной функционал качества и, являясь эталонным для одного, может и не являться таковым для другого.

Как бы то ни было, критерии качества весьма показательны – они позволяют понять, насколько полученное разбиение однозначно. Среди прочих используется и коэффициент силуэта.

Задается две величины:

a – среднее расстояние между данным элементом и всеми точками соответствующего кластера.

b – среднее расстояние между данным элементом и всеми точками другого ближайшего к нему кластера.

Сам коэффициент определяется по формуле:

Чаще всего его значение оказывается в пределах отрезка , однако это выполнено не всегда. Он характеризует, насколько кластеры отделены друг от друга, иными словами, насколько кластеризация однозначна.

Он достойно работает, если кластеры выпуклы, но, если они более сложной формы, например, при использовании алгоритма DBSCAN, величина метрики падает, и он перестает отражать реальную ситуацию.

Мы достаточно исследовали алгоритмы кластеризации, осталось сказать, как этот чисто математический метод нашел свое применение в лингвистике и позволил решить ранее, казалось бы, неподъемные задачи.

    1. Кластеризация в лингвистике

Электронные корпусы текстов позволили широко использовать методы кластеризации для решения самых разных лингвистических задач. Классический пример применения кластеризации – статья [Schütze, 1998], в которой комбинация аггломеративного и EM-алгоритма использовалась для снятия лексической неоднозначности. Основное положение подобных методов заключается в том, что схожесть контекста дает основание считать одинаковым значения обеих лексем. Подобные подходы использовались в работах [Lin, 1998, 2002] и по-прежнему актуальны [McCarthy и др., 2016]. Обзор работ по применению методов кластеризации в задачах снятия лексической неоднозначности можно найти в статье [Navigli, 2009].

Оригинальная идея была предложена в статье [Biemann, 2006]. В ней решалась задача частеречной разметки корпуса на основе контекста и был предложен оригинальный метод графовой кластеризации, оптимизированный для данной задачи.

Нашел свое применение кластерный анализ и в задаче построения тонального словаря [Четверкин, 2013] по корпусу текстов.

Как и в нашей работе, нередко методы кластеризации используются в задачах тематического моделирования [Basu, Murphy, 2013]. В частности, их используют для классификации научных текстов, насыщенных специальной терминологией [Savova и др., 2005].

Особую роль методы кластерного анализа играют в компьютерной текстологии. В рамках исследований по определению силы связей между списками рукописей на основе данных об узлах разночтений, проводимых А.А. Алексеевым, Е.Л. Алексеевой (Кузнецовой) и Д.М. Мироновой, используется вариант аггломеративного кластерного анализа, в процессе которого близкие тексты объединяются в стемму [Миронова 2016].

В завершении главы скажем, что широкое применение кластерного анализа в лингвистике привело к появлению специальных библиотек, адаптированных для работы с текстовыми документами, в частности, уже упомянутой библиотеки Scikit-learn для языка Python, с которой мы работали во время проведения экспериментов.

  1. Лингвистические основания автоматической кластеризации текстов по ключевым словам и конструкциям



Похожие документы:

  1. «Компьютерная лингвистика и интеллектуальные технологии» (1)

    Документ
    ... Кафедра математической лингвистики Направление: «Лингвистика» Образовательная программа: «Прикладная и экспериментальная лингвистика» Профиль: «Компьютерная лингвистика и интеллектуальные технологии» Параллельный конкорданс ...
  2. «Компьютерная лингвистика и интеллектуальные технологии» (2)

    Документ
    ...   Кафедра математической лингвистики Направление: «Лингвистика» Образовательная программа: «Прикладная и экспериментальная лингвистика» Профиль: «Компьютерная лингвистика и интеллектуальные технологии» Выявление информации ...
  3. Как единица устной речи: общая характеристика и прагматический потенциал

    Документ
    ... результаты исследования // Компьютерная лингвистика и интеллектуальные технологии: по материалам ежегодной ... . И. Б. Пересказывательность в русском языке // Компьютерная лингвистика и интеллектуальные технологии: материалы Международной конференции «Диалог ...
  4. Сводные данные международных мероприятий в области образования, науки и инноваций на 20 1 3 – 2015 гг

    Документ
    ... . ноябрь 2013 612 Международная конференция «Компьютерная лингвистика и интеллектуальные технологии» – Диалог 2013 Ин-т проблем ... техни-ческий конгресс по интеллектуальным системам и информационным технологиям Таганрогский технологический ин-т Южного ...
  5. Материал из Semantic Future

    Документ
    ... , к увеличению числа пользователей, активно использующих технологии и сервисы Semantic Web, но революции ... доступ к систематизированным знаниям и данным, относящимся к компьютерной лингвистике, т.е. возможность поиска и получения информации в терминах ...

Другие похожие документы..