Образовательная программа: «Прикладная и экспериментальная лингвистика» Профиль: «Компьютерная лингвистика и интеллектуальные технологии»
Скачать 0.71 Mb.
|
Оценка качества кластеризацииНа первый взгляд, оценка качества кластеризации – задача почти тривиальная – достаточно сосчитать количество ошибочно классифицированных объектов. Но это не вполне верно. В первую очередь, оценка не должна зависеть от объема выборки и конкретного кластера. Ведь десяток ошибочных элементов в кластере размером пятьдесят и тысяча – не одно и то же. Есть и другие разумные требование на оптимальную кластеризацию. Если при тестировании алгоритма известна реальная классификация, к которой следует стремиться, то соответствующая оценочная метрика должна отражать, насколько прогнозное разбиение близко к эталонному. На практике чаще всего такая классификация известна лишь для небольшого числа объектов, поэтому разумно использовать другие метрики, которые оценивают качество классификации исходя из ее внутренней структуры. В сущности, они представляют собой разновидность тех самых критериев качества, которые алгоритм кластеризации должен оптимизировать. Рассмотрим ряд таких метрик первого типа. Индекс РандаИтак, пусть имеется эталонная классификация объектов  , с которой требуется сравнить прогнозную кластеризацию  . Дополнительно определим:
Стандартный (смещенный) индекс Ранда (Rand index) задается по следующей формуле:  При совпадении прогнозной кластеризации и эталонной классификации он будет иметь единичный вес. С увеличением числа ошибок значение индекса уменьшается. Эта метрика не зависит от «переименования» кластеров: если два объекта одного класса попали в один кластер, это хорошо вне зависимости от того, какой именно это кластер. Иными словами, не требуется никакого отождествления классов и кластеров для оценки. Использование пар позволяет учитывать размер соответствующих кластеров при подсчете ошибок. Однако кластеризация, которая случайным образом определяет принадлежность к кластеру и никак не учитывает расстояние между объектами, согласно данной метрике будет иметь положительный вес. Естественным было бы требование для такой кластеризации иметь нулевую метрику. Этому условию отвечает несмещенный индекс Ранда (Adjusted Rand index), задаваемый следующим образом:  Он требует неоднократного запуска процесса кластеризации. Существенным достоинством индекса Ранда является то, что он не учитывает форму кластеров, поэтому разные подходы и методы кластеризации тем самым сравнимы между собой. Несмещенный индекс Ранда принимает значения на отрезке  : отрицательная величина говорит о неудачной кластеризации, значения около нуля говорят о том, что данный метод кластеризации не зависит от классификационных признаков. Значения, близкие к единице говорят об удовлетворительной кластеризации. Взаимная информацияОценка взаимной информации – класс широко используемых метрик для измерения корреляции векторов. В рассмотренном случае она используется при сравнении эталонной и прогнозной классификации и характеризует их согласованность. Данный метод, как и предыдущий, не зависит от взаимного соответствия между классами и кластерами. Существует две модификации взаимной информации – нормированная и несмещенная. Первая стала уже традиционной и хорошо описана в литературе, тогда как вторая всё чаще применяется на практике, когда используются приближенные методы кластеризации. Как и индекс Ранда, взаимная информация не зависит от формы и структуры кластеров. Как стандартная взаимная информация, так и ее нормированная модификация являются смещенными оценками. Обозначим два разбиения пространства объектов U и V. Тогда энтропия неравномерности для каждого разбиения задается по формуле:  где  – вероятность того, что случайный элемент попадет в класс  . Аналогичная величина определяется и для  : при этом вероятность попадания случайного элемента в класс  обозначается величиной  .Взаимная информация определяется формулой:  где  – вероятность того, что случайный объект попадет в оба класса и . Сама по себе взаимная информация существенно зависит от абсолютных значений выборки. Поэтому используется нормированный вариант, определяемый следующим образом:  Обе метрики не учитывают стохастической составляющей и, кроме того, их значения возрастают при увеличении числа кластеров, хотя сама по себе кластеризация может быть неудачной. Статистический метод усреднения был предложен в статье [Vinh, Epps & Bailey, 2009]. Нам понадобиться обозначить  ,  . Тогда верна следующая оценка: Используя эту величину, можно вычислить усредненную взаимную информацию:  Точность, полнота и V-мераЕсли известна эталонная классификация объектов, то можно определить ряд естественных метрик, характеризующих степень близости прогнозной классификации. В статье [Rosenberg and Hirschberg, 2007] описываются два интуитивно понятных требования для оценки качества кластеризации. Во-первых, каждый кластер должен содержать элементы одного класса. Во-вторых, все члены одного класса должны попасть в один кластер. Исходя из этого строятся следующие метрики. Для эталонной классификации и прогнозной кластеризация обозначим величину, называемую условной энтропией разбиения: а  – энтропию класса, определенную по формуле: где  – общее число элементов,  и  – число элементов соответственно в классе  и кластере  . Аналогично зададим  и  .Точность (homogeneity), характеризующая величину ошибки первого рода, т.е. количество элементов разных классов, попавших в один кластер, определяется по формуле:  Аналогично полнота (completeness), характеризующая, в свою очередь, величину ошибки второго рода – количество элементов разных классов, оказавшихся в одном кластере, – задается по формуле:  Их комбинация ( -мера), учитывающая и величину полноты, и точности, является средним гармоническим: Все величины имеют значения в пределах от нуля до единицы. Использование данных метрик позволяет более детально оценить проблемы той или иной кластеризации: ошибки первого и второго рода. Это полезно при регулировке параметров алгоритма. С другой стороны, V-мера чувствительна по отношению к шуму (т.е. смещена). Случайное разбиение, таким образом, не всегда имеет нулевую метрику. Кроме того, все три метрики зависит от размера выборки, числа кластеров и структуры классификации. Этой проблемой можно пренебречь, когда объем выборки более тысячи, а число кластеров менее 10. Коэффициент силуэтаКак мы уже замечали, если эталонная классификация неизвестна, следует использовать один из коэффициентов качества, описанных ранее. Такие метрики, естественно, весьма условны. Во-первых, даже эталонная классификация не всегда им удовлетворяет. Во-вторых, всякий алгоритм кластеризации минимизирует тот или иной функционал качества и, являясь эталонным для одного, может и не являться таковым для другого. Как бы то ни было, критерии качества весьма показательны – они позволяют понять, насколько полученное разбиение однозначно. Среди прочих используется и коэффициент силуэта. Задается две величины: a – среднее расстояние между данным элементом и всеми точками соответствующего кластера. b – среднее расстояние между данным элементом и всеми точками другого ближайшего к нему кластера. Сам коэффициент определяется по формуле:  Чаще всего его значение оказывается в пределах отрезка  , однако это выполнено не всегда. Он характеризует, насколько кластеры отделены друг от друга, иными словами, насколько кластеризация однозначна.Он достойно работает, если кластеры выпуклы, но, если они более сложной формы, например, при использовании алгоритма DBSCAN, величина метрики падает, и он перестает отражать реальную ситуацию. Мы достаточно исследовали алгоритмы кластеризации, осталось сказать, как этот чисто математический метод нашел свое применение в лингвистике и позволил решить ранее, казалось бы, неподъемные задачи. |
– число пар объектов, попавших в один класс и в один кластер,
– число пар объектов, попавших в различные классы и различные кластеры,Похожие:
 | Задачи и методы их решения, общие для корпусной лингвистики, машинного перевода и компьютерной лексикографии 8 |  | Прикладная лингвистика: разработка концепции научно-образовательного комплекса «Интеллектуальные энергосистемы (Smart Grid)» |
| Прикладная лингвистика: разработка концепции научно-образовательного комплекса «Интеллектуальные энергосистемы (Smart Grid)» | | Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления подготовки 45.... |
| Прагма-коммуникативный анализ языковой репрезентации улыбки в современной художественной англоязычной литературе | | Нормативные документы для разработки ооп впо по направлению подготовки 035700. 68 Лингвистика и профилю подготовки Межкультурная... |
| Теоретическая лингвистика и судебная лингвистическая экспертиза : монография / К. И. Бринев; под редакцией Н. Д. Голева. – Барнаул... | | Правила подготовки и защиты курсовой работы и выпускной квалификационной работы по образовательной программе «Фундаментальная и прикладная... |
| П. П. Рабочая программа производственной практики для студентов, обучающихся по направлению подготовки 230700. 62 «Прикладная информатика»,... | |