Классификация древнетибетских текстов с помощью методов спектрального анализа.
М.А. Герасимов, А.А. Носовец
Санкт-Петербург, каф. Информатики СПбГУ
ge@star.math.spbu.ru, nosovecc@gmail.com
Аннотация
древнетибетский текст кодировка семантика
Работа посвящена анализу древнетибетских текстов. Используется аппарат статистического анализа множества исходных текстов на древнетибетском языке, записанных в кодировке UTF-8. Делается попытка использования технологий анализа больших объемов данных для извлечения смысла (семантики) из исходных текстов.
Данная работа направленна на классификацию древнетибетских текстов методом спектрального анализа данных.
О методах анализа текстов
Исследование языка в первую очередь вызвано интересом к естественному интеллекту человека, поэтому такая форма существования языка как письменный текст, также является объектом пристального внимания. Сегодня наблюдается устойчивый интерес к работам, проводимым в этой области.
Задачи по автоматической обработке текста, включают в себя задачи информационного поиска, связанные с нахождением информации в электронных базах знаний, автоматическим извлечением данных и фактов по заданной тематике, автоматическим реферированием электронных документов. Имеются и другие проблемы обработки естественного языка с использованием вычислительной техники: понимание естественного языка, лингвистическое обеспечение информационных систем разных типов и машинный перевод.
При автоматической обработке текстов среди других задач возникают две близкие задачи: классификации и кластеризации текстов. Первая состоит в том, чтобы отнести текст к определенной категории. Вторая -- разбить набор текстов на группы, близкие в некотором смысле. При кластеризации текстов происходит попытка выяснить естественное выделение в группах текстов определенных групп с использованием соответствующих алгоритмов и визуализации. Для каждого текста в любом случае строится набор признаков.
Задача автоматической классификации и кластеризации текстов имеет практическое значение. Соответствующие процедуры применяются при обработке информационных потоков.
Тесно связана с этим задача атрибуции текстов. Атрибуция (от лат. attributio -- приписывание) -- определение атрибутов. Существуют методы, позволяющие проводить атрибуцию текста. Это - отнесение текста к определенному жанру, стилю, времени написания и т. п.
Большинство современных методов определения жанра, стиля, времени написания, так или иначе, основаны на анализе лингвостилистических (числовых) характеристик, вычисляемых по тексту.
Можно выделить следующие характеристики, которые могут быть получены для письменного текста и доступны для последующего анализа:
1. атрибуты, легко вычисляемые по тексту: длина предложений и слов, средняя длина предложений и слов;
2. однородность текста (распределение по тексту составляющих единиц текста);
3. грамматические конструкции языка;
4. морфологические конструкции языка;
5. синтаксические конструкции языка;
6. лексика (богатство лексики, частотные словари, наличие определенных слов);
7. переходы между составляющими единицами текста;
8. анализ дополнительных признаков текста (сокращений, пунктуации, "смайликов", ошибок).
Полученные лингвостилистические характеристики подвергаются анализу с использованием различных математических методов, среди которых можно выделить следующие:
1. статистические методы;
2. изучение переходов между составляющими единицами текста;
3. арифметические методы;
4. методы распознавания образов и искусственного интеллекта.
Анализ больших объемов данных
Развитие методов записи и хранения данных привело к бурному росту объемов собираемой и анализируемой информации. Для того чтобы провести автоматический анализ данных, используется Data Mining.
Data Mining - это процесс обнаружения в сырых данных ранее неизвестных, нетривиальных, практически полезных и доступных интерпретации знаний, необходимых для принятия решений в различных сферах человеческой деятельности.
Суть и цель технологии Data Mining можно охарактеризовать так: это технология, которая предназначена для поиска в больших объемах данных неочевидных, объективных и полезных на практике закономерностей.
Неочевидных - это значит, что найденные закономерности не обнаруживаются стандартными методами обработки информации или экспертным путем.
Объективных - это значит, что обнаруженные закономерности будут полностью соответствовать действительности, в отличие от экспертного мнения, которое всегда является субъективным.
Практически полезных - это значит, что выводы имеют конкретное значение, которому можно найти практическое применение.
Нередко Data Mining отождествляют с Knowledge Discovery in Databases, хотя более правильно считать Data Mining одним из шагов этого процесса.
Data Mining - это не один, а совокупность большого числа различных методов обнаружения знаний. Все задачи, решаемые методами Data Mining, можно условно разбить на пять классов: классификация, регрессия, кластеризация, ассоциация и последовательные шаблоны.
Data Mining имеет мульти дисциплинарный характер.
Классификация
Задача разбиения множества объектов или наблюдений на априорно заданные группы, называемые классами, внутри каждой из которых они предполагаются похожими друг на друга, имеющими примерно одинаковые свойства и признаки. При этом решение получается на основе анализа значений атрибутов (признаков).
Классификация является одной из важнейших задач Data Mining.
Если число классов ограничено двумя, то имеет место бинарная классификация, к которой могут быть сведены многие более сложные задачи. Например, вместо определения таких степеней кредитного риска, как «Высокий», «Средний» или «Низкий», можно использовать всего две - «Выдать» или «Отказать».
Для классификации в Data Mining используется множество различных моделей: нейронные сети, деревья решений, машины опорных векторов, метод k-ближайших соседей, алгоритмы покрытия и др., при построении которых применяется обучение с учителем, когда выходная переменная (метка класса) задана для каждого наблюдения. Формально классификация производится на основе разбиения пространства признаков на области, в пределах каждой из которых многомерные векторы рассматриваются как идентичные. Иными словами, если объект попал в область пространства, ассоциированную с определенным классом, он к нему и относится.
Решение задачи классификации методом линейной регрессии
Решение задачи классификации методом деревьев решений
Решение задачи классификации методом нейронных сетей
Регрессия
В теории вероятностей и математической статистике это зависимость среднего значения случайной величины от некоторой другой величины или даже нескольких. В отличие от чисто функциональной зависимости y = f(x), где каждому значению независимой переменной x соответствует единственное значение зависимой переменной y, регрессионная зависимость предполагает, что каждому значению переменной x могут соответствовать различные значения y, обусловленные случайной природой зависимости. Если некоторому значению величины xi соответствует набор значений величин {yi1, yi2,…,yin}, то зависимость средних арифметических:
от xi и является регрессией в статистическом понимании данного термина.
Изучение регрессии в теории вероятностей основано на том, что случайные величины Х и Y, имеющие совместное распределение вероятностей, связаны вероятностной зависимостью: при каждом фиксированном значении Х = х, величина Y является случайной величиной с определённым (зависящим от значения х) условным распределением вероятностей. Регрессия величины Y по величине Х определяется условным математическим ожиданием Y, вычисленным при условии, что Х = х: Е(Y|х) = u(х). Уравнение у = u(х) называется уравнением регрессии, а соответствующий график -- линией регрессии Y по X. Точность, с которой уравнение Y по Х отражает изменение Y в среднем при изменении х, измеряется условной дисперсией D величины Y, вычисленной для каждого значения X = х: D(Y|х)=D(x). Если D(х) = 0 при всех значениях х, то можно достоверно утверждать, что Y и Х связаны строгой функциональной зависимостью Y = u(X). Если D(х) = 0 при всех значениях х и u(х) не зависит от х, то говорят, что регрессионная зависимость Y по Х отсутствует.
Линии регрессии обладают следующим замечательным свойством: среди всех действительных функций f(х) минимум математического ожидания Е[Y -- f(X)] 2 достигается для функции f(x) = u(х). Это означает, что регрессия Y по Х даёт наилучшее в указанном смысле представление величины Y по величине X. Это свойство позволяет использовать регрессию для предсказания величины Y по X. Иными словами, если значение Y непосредственно не наблюдается и эксперимент позволяет регистрировать только Х, то в качестве прогнозируемого значения Y можно использовать величину Y = u(X). Наиболее простым является случай, когда регрессионная зависимость Y по Х линейна, т.е. Е(Y|x) = b0 + b1x, где b0 и b1 - коэффициенты регрессии. На практике обычно коэффициенты регрессии в уравнении у = u(х) неизвестны, и их оценивают по наблюдаемым данным.
Регрессия широко используется в аналитических технологах при решении различных бизнес-задач, таких как прогнозирование (продаж, курсов валют и акций), оценивания различных бизнес-показателей по наблюдаемым значениям других показателей (скоринг), выявление зависимостей между показателями и т.д.
Кластеризация
Объединение объектов или наблюдений в непересекающиеся группы, называемые кластерами, на основе близости значений их атрибутов (признаков). В результате в каждом кластере будут находиться объекты, похожие по своим свойствам друг на друга и отличающиеся от тех, которые расположены в других кластерах. При этом, чем больше подобие объектов внутри кластера и чем сильнее их непохожесть на объекты в других кластерах, тем лучше кластеризация.
Формальная постановка задачи кластеризации выглядит следующим образом. Пусть заданы множества объектов X = (x1,x2,...,xn) и номеров (имён, меток) кластеров Y = (y1, y2,…yk). Для X определена некоторая функция расстояния между объектами D(x,x'), например, метрика L2. Кроме этого, имеется конечная выборка обучающих примеров Xm = (x1,x2,…,xm) из множества X, которую требуется разбить на Xm на непересекающиеся подмножества (кластеры) так, чтобы каждое из них состояло бы только из элементов, близких по метрике D. При этом каждому объекту xi из множества Xm присваивается номер кластера yj.
Тогда задача будет заключаться в поиске функции f, которая любому объекту x из множества X ставит в соответствие номер кластера y из множества Y, которое само по себе бывает известно заранее. Однако в большинстве случаев приходится определять оптимальное число кластеров исходя из особенностей решаемой задачи.
Кластеризация позволяет добиться следующих целей:
· Улучшает понимание данных за счет выявления структурных групп. Разбиение выборки на группы схожих объектов позволяет упростить дальнейшую обработку данных и принятия решений, применяя к каждому кластеру свой метод анализа.
· Позволяет компактно хранить данные. Для этого вместо хранения всей выборки можно оставить по одному типичному наблюдению из каждого кластера.
· Обнаружение новых нетипичных объектов, которые не попали ни в один кластер.
Непересекающиеся и пересекающиеся кластеры
На сегодняшний день разработано более сотни различных алгоритмов кластеризации. Краткая характеристика подходов к кластеризации.
Алгоритмы, основанные на разделении данных (Partitioning algorithms), в т.ч. итеративные:
· разделение объектов на k кластеров;
· итеративное перераспределение объектов для улучшения кластеризации.
Иерархические алгоритмы (Hierarchy algorithms):
· агломерация: каждый объект первоначально является кластером, кластеры, соединяясь друг с другом, формируют больший кластер и т.д.
Методы, основанные на концентрации объектов (Density-based methods):
· основаны на возможности соединения объектов;
· игнорируют шумы, нахождение кластеров произвольной формы.
Грид-методы (Grid-based methods):
· квантование объектов в грид-структуры.
Модельные методы (Model-based):
· использование модели для нахождения кластеров, наиболее соответствующих данным.
Ассоциация
Ассоциация - выявление закономерностей между связанными событиями. Примером такой закономерности служит правило, указывающее, что из события X следует событие Y. Такие правила называются ассоциативными. Впервые эта задача была предложена для нахождения типичных шаблонов покупок, совершаемых в супермаркетах, поэтому иногда ее еще называют анализом рыночной корзины (market basket analysis).
Последовательный шаблон
Последовательность вида
где A - событие, или множество событий, t- время. Таким образом, последовательный шаблон это упорядоченная во времени последовательность событий, наблюдаемая настолько часто, что это позволяет говорить о наличии между ними связей. Анализ таких связей позволяет обнаруживать правила, что если в наблюдении появился набор одних событий из шаблона, то это с высокой долей вероятности повлечет за собой появление других событий или события из этого же шаблона. При этом события первой группы называются основными, а события, появление которых ожидается - целевыми. Основным приложением последовательных шаблонов является исследование типичных моделей поведения клиентов.