Теория последовательных шаблонов происходит из теории ассоциативных правил. Методы анализа ассоциативных правил и последовательных шаблонов во многом похожи: и в том, и в другом случае используются такие понятия как предметный набор и транзакция, такие числовые характеристики, как поддержка и достоверность, а для обнаружения частых шаблонов применяются различные модификации алгоритма 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 текста одной тематики на древнетибетском языке.
Для дальнейшей работы эти тексты были преобразованы на латиницу.
При обработке каждого текста был создан каталог (в итоге получили 34 каталога). В каждом каталоге находится 4 файла.
В файле 101.txt находится текст на древнетибетском языке. В 101.val.txt текст, преобразованный на латиницу. В 101.table.val.txt находится таблица относительных частот для данного текста с учетом black листа, т.е. эта таблица не содержит слов, не несущих смысловую нагрузку (предлоги, частицы, местоимения, часто употребляемые слова и т.д.).
В файле 1TableFrequency.txt находится спектр исследуемого текста. Для построения этого спектра из таблицы относительных частот были взяты слова с наибольшим количеством вхождений в этот текст. Было подсчитано спектральное расстояние с использованием предварительно построенного спектра корпуса. При вычислении спектральных корпусов использовалось евклидово(квадратичное) расстояние.
Спектр корпуса.
Затем был найден радиус окрестности данного корпуса. В качестве радиуса окрестности было взято максимальное расстояние ?0.36596.
Также был произведен эксперимент. Были взяты тексты на древнетибетском тексте с неизвестной тематикой. Для них считались спектры. И затем смотрели, входят ли эти спектры в данный корпус. Оказалось, что все тексты с неизвестной тематикой входят в данный корпус.
Спектр первого текста, не входившего в корпус, близко расположен к 9 тексту из корпуса. Их расстояния почти равны. При визуальном сравнение двух этих текстов, видно, что эти тексты разные.
Спектры второго и третьего текста из эксперимента также находятся в исследуемом корпусе. Они расположены вблизи спектров 30 и 19 текстов соответственно.
Выводы
Данное исследование показало, что:
1. Метод экспертного статистического анализа применим к классификации древнетибетских текстов, а значит и для анализа больших объемов данных. Видно, что этот метод может быть эффективным и при использовании небольшого корпуса.
2. Небольшая временная сложность рассматриваемого алгоритма позволяет использовать его при анализе больших объемов данных для систем автоматического перевода с древних языков.
Литература
1. Барсегян А.А., Куприянов М.С., Степаненко В.В., Холод И.И. Методы и модели анализа данных: OLAP и Data Mining. - СПб.:БХВ-Петербург, 2004. - 336 с.:ил.
2. Суворцева Т.Г. Многомерный количественный анализ и классификация текстов на основе лингвостатистических характеристик
Режим доступа - Научная библиотека диссертаций и авторефератов disserCat http://www.dissercat.com/content/mnogomernyi-kolichestvennyi-analiz-i-klassifikatsiya-tekstov-na-osnove-lingvostatisticheskik#ixzz2TJXgpfr5
3. Data Mining - добыча данных. Режим доступа - http://www.basegroup.ru/library/methodology/data_mining/
4. Чубукова И. Data Mining. Режим доступа - http://www.intuit.ru/studies/courses/6/6/info