Классификация древнетибетских текстов с помощью методов спектрального анализа

Размещено на http://www.allbest.ru/

Классификация древнетибетских текстов с помощью методов спектрального анализа



Работа посвящена анализу древнетибетских текстов. Используется аппарат статистического анализа множества исходных текстов на древнетибетском языке, записанных в кодировке 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 имеет мульти дисциплинарный характер.



Рис.1

обработка текст спектральный

Классификация

Задача разбиения множества объектов или наблюдений на априорно заданные группы, называемые классами, внутри каждой из которых они предполагаются похожими друг на друга, имеющими примерно одинаковые свойства и признаки. При этом решение получается на основе анализа значений атрибутов (признаков).

Классификация является одной из важнейших задач Data Mining.

Если число классов ограничено двумя, то имеет место бинарная классификация, к которой могут быть сведены многие более сложные задачи. Например, вместо определения таких степеней кредитного риска, как «Высокий», «Средний» или «Низкий», можно использовать всего две - «Выдать» или «Отказать».

Для классификации в Data Mining используется множество различных моделей: нейронные сети, деревья решений, машины опорных векторов, метод k-ближайших соседей, алгоритмы покрытия и др., при построении которых применяется обучение с учителем, когда выходная переменная (метка класса) задана для каждого наблюдения. Формально классификация производится на основе разбиения пространства признаков на области, в пределах каждой из которых многомерные векторы рассматриваются как идентичные. Иными словами, если объект попал в область пространства, ассоциированную с определенным классом, он к нему и относится.

Рис.2

Рис.3 Решение задачи классификации методом деревьев решений

Рис.4



Регрессия

В теории вероятностей и математической статистике это зависимость среднего значения случайной величины от некоторой другой величины или даже нескольких. В отличие от чисто функциональной зависимости 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, которое само по себе бывает известно заранее. Однако в большинстве случаев приходится определять оптимальное число кластеров исходя из особенностей решаемой задачи.

Кластеризация позволяет добиться следующих целей:

· Улучшает понимание данных за счет выявления структурных групп. Разбиение выборки на группы схожих объектов позволяет упростить дальнейшую обработку данных и принятия решений, применяя к каждому кластеру свой метод анализа.

· Позволяет компактно хранить данные. Для этого вместо хранения всей выборки можно оставить по одному типичному наблюдению из каждого кластера.

· Обнаружение новых нетипичных объектов, которые не попали ни в один кластер.

Рис.5

обработка текст спектральный

Непересекающиеся и пересекающиеся кластеры

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

Алгоритмы, основанные на разделении данных (Partitioning algorithms), в т.ч. итеративные:

· разделение объектов на k кластеров;

· итеративное перераспределение объектов для улучшения кластеризации.

Иерархические алгоритмы (Hierarchy algorithms):

· агломерация: каждый объект первоначально является кластером, кластеры, соединяясь друг с другом, формируют больший кластер и т.д.

Методы, основанные на концентрации объектов (Density-based methods):

· основаны на возможности соединения объектов;

· игнорируют шумы, нахождение кластеров произвольной формы.

Грид-методы (Grid-based methods):

· квантование объектов в грид-структуры.

Модельные методы (Model-based):

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

Ассоциация

Ассоциация - выявление закономерностей между связанными событиями. Примером такой закономерности служит правило, указывающее, что из события X следует событие Y. Такие правила называются ассоциативными. Впервые эта задача была предложена для нахождения типичных шаблонов покупок, совершаемых в супермаркетах, поэтому иногда ее еще называют анализом рыночной корзины (market basket analysis).

Последовательный шаблон. Последовательность вида



где A - событие, или множество событий, t- время. Таким образом, последовательный шаблон это упорядоченная во времени последовательность событий, наблюдаемая настолько часто, что это позволяет говорить о наличии между ними связей. Анализ таких связей позволяет обнаруживать правила, что если в наблюдении появился набор одних событий из шаблона, то это с высокой долей вероятности повлечет за собой появление других событий или события из этого же шаблона. При этом события первой группы называются основными, а события, появление которых ожидается - целевыми. Основным приложением последовательных шаблонов является исследование типичных моделей поведения клиентов.

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

Задача поиска последовательных шаблонов была впервые Р. Агравалом и Р. Срикнатом, авторами популярного алгоритма поиска ассоциативных правил Apriori. Они предложили 3 алгоритма для решения задачи открытия последовательных шаблонов на больших массивах данных - GSP, AprioriSome и AprioriAll.

Нейронная сеть

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

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

Наиболее часто нейронные сети используются для решения следующих задач:

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

· Кластеризация - классификация образов при отсутствии обучающей выборки с метками классов.

· Прогнозирование - предсказание значения y(tn+1) при известной последовательности y(t1), y(t2) ... y(tn).

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

· Память, адресуемая по содержанию (ассоциативная память) - память, доступная при указании заданного содержания.

· Управление - расчет такого входного воздействия на систему, при котором она следует по желаемой траектории.

Метод экспертного статистического анализа

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

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

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

Иерархические агломеративные методы (Agglomerative Nesting, AGNES)

Эта группа методов характеризуется последовательным объединением исходных элементов и соответствующим уменьшением числа кластеров.

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

Иерархические дивизимные (делимые) методы (DIvisive ANAlysis, DIANA)

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

Расстояния между объектами предполагает их представление в виде точек m-мерного пространства R^m. В этом случае могут быть использованы различные подходы к вычислению расстояний.

Евклидово расстояние определяется по формуле



где xi1, хj1 -- значения l-го признака у i-го (j-го) объекта (l = 1, 2, ..., k, i,j = 1, 2, .... п).

Расстояние по Хеммингу является просто средним разностей по координатам. Это расстояние вычисляется по формуле

Расстояние Чебышева может оказаться полезным, когда два объекта различаются только по какой-либо одной координате. Расстояние Чебышева вычисляется по формуле

Формально данные меры можно получить из более общей формулы П.С. Урысона:

lij = ()1/p

при p=0 и p->соответственно.

Кластер имеет следующие математические характеристики: центр, радиус, среднеквадратическое отклонение, размер кластера.

Центр кластера - это среднее геометрическое место точек в пространстве переменных.

Радиус кластера - максимальное расстояние точек от центра кластера.

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

Спорный объект - это объект, который по мере сходства может быть отнесен к нескольким кластерам.

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

Алгоритм k-means

Вначале выбирается k произвольных исходных центров - точек в пространстве всех объектов. Дальше итерационно выполняется операция двух шагов.

На первом шаге все объекты разбиваются на k групп, наиболее близких к одному из центров. Близость определяется расстоянием, которое вычисляется одним из описанных ранее способов.

На втором шаге вычисляются новые центры кластеров.

Рассмотренная операция повторяется рекурсивно до тех пор, пока центры кластеров не перестанут меняться.

Алгоритм BIRCH (Balanced Iterative Reducing and Clustering using Hierarchies) В этом алгоритме реализован двухэтапный процесс кластеризации. В ходе первого этапа формируется предварительный набор кластеров. На втором этапе к выявленным кластерам применяются другие алгоритмы кластеризации - пригодные для работы в оперативной памяти.

Алгоритм WaveCluster

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

Используемый метод

В дальнейшем будем называть данный метод - методом экспертного статистического анализа. Его можно описать поэтапно:

- Экспертом формируется начальный кластер (кластеры) в виде произвольного множества объектов, которые, по мнению эксперта, принадлежат кластеру;

-Для кластера строится множество точек, соответствующих выбранным объектам.

-Для данного множества вычисляется «центр» в виде математического ожидания его точек;

-Вычисляется радиус этого кластера как максимальное расстояние от точки множества до «центра».

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

-При исследовании объектов могут образовываться пересекающиеся кластеры. Это означает, что объект (в данной работе текст) относится одновременно к разным темам.

Пример применения метода

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

В рамках данной работы были взяты тексты, тематически схожи (смысловую схожесть текстов определял специалист по тибетским текстам). На основе этих текстов строился спектральный корпус. Затем находился радиус окрестности этого корпуса.

Было отобрано 34 текста одной тематики на древнетибетском языке.

Рис.6

Для дальнейшей работы эти тексты были преобразованы на латиницу.

Рис.7



При обработке каждого текста был создан каталог (в итоге получили 34 каталога). В каждом каталоге находится 4 файла.

Рис.8

В файле 101.txt находится текст на древнетибетском языке. В 101.val.txt текст, преобразованный на латиницу. В 101.table.val.txt находится таблица относительных частот для данного текста с учетом black листа, т.е. эта таблица не содержит слов, не несущих смысловую нагрузку (предлоги, частицы, местоимения, часто употребляемые слова и т.д.).

Рис.9

В файле 1TableFrequency.txt находится спектр исследуемого текста. Для построения этого спектра из таблицы относительных частот были взяты слова с наибольшим количеством вхождений в этот текст. Было подсчитано спектральное расстояние с использованием предварительно построенного спектра корпуса. При вычислении спектральных корпусов использовалось евклидово(квадратичное) расстояние.

Рис.10

Затем был найден радиус окрестности данного корпуса. В качестве радиуса окрестности было взято максимальное расстояние ?0.36596.

Рис.11



Также был произведен эксперимент. Были взяты тексты на древнетибетском тексте с неизвестной тематикой. Для них считались спектры. И затем смотрели, входят ли эти спектры в данный корпус. Оказалось, что все тексты с неизвестной тематикой входят в данный корпус.

Спектр первого текста, не входившего в корпус, близко расположен к 9 тексту из корпуса. Их расстояния почти равны. При визуальном сравнение двух этих текстов, видно, что эти тексты разные.

Рис.12

Спектры второго и третьего текста из эксперимента также находятся в исследуемом корпусе. Они расположены вблизи спектров 30 и 19 текстов соответственно.



Рис.13



Выводы

Данное исследование показало, что:

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

2. Небольшая временная сложность рассматриваемого алгоритма позволяет использовать его при анализе больших объемов данных для систем автоматического перевода с древних языков.



Литература

1.Барсегян А.А., Куприянов М.С., Степаненко В.В., Холод И.И. Методы и модели анализа данных: OLAP и Data Mining. - СПб.:БХВ-Петербург, 2004. - 336 с.:ил.

2.Суворцева Т.Г. Многомерный количественный анализ и классификация текстов на основе лингвостатистических характеристик

3.Data Mining - добыча данных. Режим доступа - http://www.basegroup.ru/library/methodology/data_mining/

4.Чубукова И. Data Mining. Режим доступа - http://www.intuit.ru/studies/courses/6/6/info.

Размещено на Allbest.ru