Применение методов машинного обучения в области обработки естественного языка

1. Введение 3
1.1. Формализация и постановка задачи 5
1.2. Обработка текста 6
1.3. Выделение признаков 7
1.4. Методы оценки результата алгоритма 11
2. Наивные алгоритмы 13
2.1. Шар 15
2.2. Максимальное отклонение по координатам 19
2.3. Эвристики 22
2.4. Метод k-ближайших соседей 23
3. Метод опорных векторов 26
3.1. Описание 26
3.2. Формализация 27
3.3. Ядра 30
3.4. Оценка результатов 33
4. Наивный байесовский классификатор 34
4.1. Описание 34
4.2. Формализация 34
4.3. Применение к задаче 36
4.4. Оценка результатов 38
Заключение 39
Список литературы 40
Купить

Если взглянуть на нынешний уровень доступа к информации, то можно обнаружить, что найти нужную информацию без каких-либо специальных средств почти невозможно.
Во многих случаях, чтобы как-то работать с этими данными, прихо­дится сначала их классифицировать или кластеризовывать. У читателя может возникнуть вопрос, что это такое и зачем вообще это нужно?
Определение. Кластеризация (или кластерный анализ) — задача раз­биения множества объектов на группы, называемые кластерами. Внут­ри каждого кластера должны оказаться похожие объекты, а объекты различных групп должны быть как можно более отличны.
Цели кластеризации
• Понимание структуры данных. Разбиение множества объектов на группы позволяет упростить их дальнейшую обработку, напри­мер, зная структуру данных, можно применять какой-то конкрет­ный алгоритм для каждого кластера.
• Обнаружение новизны. Можно найти объект, который невозмож­но отнести ни к одной из групп.
Рис. 1: Кластеризация
Определение. Классификация — задача состоит в присвоении каждо­му объекту из заданного множества, одной из заранее заданных групп.
Цели классификации
Понимание структуры данных нового объекта. Присвоение груп­пы объекту явно определяет его свойства и структуру. Эти свой­ства можно учесть при дальнейшей обработке.
Предсказание данных. На основе известных данных можно пред­сказывать вероятность принадлежности объекта классификации к какому-либо классу.
Рис. 2: Классификация
Отличием кластеризации от классификации является то, что пере­чень групп четко не задан и определяется в процессе работы алгоритма.
Многие крупные корпорации, такие как Яндекс или Google для об­работки данных используют классификацию. Классификация является достаточно простой, но при этом часто решаемой задачей Data Mining. Компания Insecurityinsight, которая занимается мониторингом противо­правных действий в отношении медицинких работников в горячих точ­ках, по запросу которой реализован один из методов, рассмотренных в текущей работе, хочет выделять части преступления из статей(кто? когда? где? совершил преступление). Но для начала, им необходимо научиться понимать, является ли статья криминальной или нет. Далее в этой работе будут рассмотрены только методы, решающие задачу классификации.
1.1. Формализация и постановка задачи
Пусть существует множество классов C = {ci, c2, ... , cm} и мно­жество объектов X = {xi, x2, ... , xi, ...}. Также существует функция f: X ! C, то есть такая функция, которая бы каждому объекту опре­деляла класс. При этом, пусть для некоторых объектов Xi = {x1, ..., Xi} (Xlearning) известны значения yi = f(xi). Тогда все пары (xi, yi) называ­ются обучающей выборкой. Если |С| = 2, то такая задача называется бинарной классификацией.
Возникает следующая проблема - объекты X имеют непредсказуе­мую природу. Элементом множества X может быть изображение, текст и т.д. Так как данная работа ориентируется на NLP(natural language processing), то будем считать, что элемент множества X - это текст (документ). Но к таким объектам нельзя напрямую применить суще­ствующий математический аппарат.
Рассмотрим задачу классификации подробнее. В задаче классифи­кации можно выделить следующие этапы:
• Обработка текста
• Выделение признаков из текста
• Выбор классификатора
• Обучение классификатора и его практическое применение
Именно на этапе выделения признаков производится формирова­ние пространства и перевод каждой статьи в это пространство. После этого математический аппарат использовать уже представляется воз­можным. Рассмотрим каждый из этапов отдельно.
1.2. Обработка текста
Этап обработки текста нужен, чтобы все слова, которые имеют оди­наковую смысловую нагрузку, привести к одному виду, а также уда­лить слова, которые лишь мешают классификации документа. Для это­го используются следующие методы:
• Стемминг слов
• Удаление стоп-слов
• Приведение слов к нижнему регистру
При стемминге происходит приведение слов к их основе. Основа сло­ва - та часть слова, которая выражает его лексическое значение. Так, слова ’’final” и ’’finalize” преобразуются к ’’final”.
Следующим этапом происходит удаление стоп-слов. Стоп-слова - это слова, которые не несут смысловой нагрузки, но при этом часто упо­требляются в тексте. Примером могут служить слова ”be”, ”was”, ’’is” и т.д.
Также стоит приводить слова к одному и тому же регистру, иначе слова ’Victim”, ’victim” и ”ViCtim”, обозначающие одно и тоже, будут считаться разными.
При обработке любого документа в данной работе все слова приво­дятся к нижнему регистру, удаляются стоп-слова и используется стем- мер Портера. Алгоритм Портера последовательно применяет ряд пра­вил для отсечения суффиксов и окончаний слов, основываясь на осо­бенностях языка. Вследствие этого, алгоритм достаточно быстр и при этом имеет достаточно высокую точность. Также любые слова, длина которых меньше либо равна двум символам, будут удалены из этого документа. Это объясняется тем, что в английском языке крайне ма­ло слов, которые бы имели такую длину и при этом могли бы как-то охарактеризовать документ.
1.3. Выделение признаков
Существует множество моделей для преобразования текста в век­тор, принадлежащий n-мерному пространству, лишь некоторые часто используемые:
• Bag of words
• Bag of n-grams
• TF-IDF
После того, как элемент множества X преобразуется через одну из вышеперечисленных моделей, получается n-мерный вектор, который характеризует этот элемент. Теперь, говоря о множестве X, будем по­нимать не первоначальные объекты, а их вектора, т.е. X с Rn.
Bag of words
Этот метод является одним из самых распространенных в практике. Суть метода заключается в том, что каждое слово рассматривается отдельно и ’’кладется в мешок”. Таким образом, теряется первоначаль­ный порядок слов и документ превращается в набор (’’мешок”) слов. При формировании ’’мешка” может учитываться количество вхожде­ний слова, или же просто признак наличия или отсутствия. Также ино­гда применяют нормализацию, т.е. подсчет доли каждого слова во всех словах документа. Важно понимать, что каждому слову соответствует размерность пространства.
Пример. Рассмотрим как из предложения ”Man was seriously injured and he was hospitalized” сформируется bag of words. Каждому слову в этом предложении поставим в соответствие частоту вхождения, т.е. ”Man” = 1, ”was” = 2, ..., ’hospitalized” = 1. Таким образом, это предло­жение преобразуется в вектор (1, 2,1,..., 1).
Bag of n-grams
Подход похож на bag of words, но вместо слов используются n-граммы. n-грамма - последовательность из n слов. Преимущество этого подхода в том, что n-граммы сохраняют семантику. Этот подход имеет смысл использовать только в том случае, если предполагается, что появление текущего слова зависит только от n предыдущих.
Пример. Рассмотрим предложение ”Man was seriously injured and he was hospitalized”. Используем биграммы, тогда ’’мешок” будет состо­ять из [’’Man”, ”Man was”, ”was seriously”, ’’seriously injured”, ..., ”was hospitalized”, ’hospitalized”]. В общем случае n-граммы могут встречать­ся в тексте несколько раз, некоторые алгоритмы классификации могут учитывать эту информацию, другие - нет.
TF-IDF
TF-IDF (от англ. term frequency-inverse document frequency) состоит из трех этапов. После того, как слово проходит через эту модель, полу­чается некоторая оценка этого слова, которая совмещает в себе и его важность, и его частоту вхождений.
Первым этапом выполняется подсчет доли вхождений каждого слова (TF).
TF(word) = W ;
W(word) - количество вхождений слова word в документ;
A - количество всех слов в документе.
Вторым этапом выполняется измерение того, насколько важно это слово (IDF). При вычислении TF все слова считаются одинаково важ­ными. Однако такие слова, как ”say”, ’’just” встречаются в документе достаточно часто, при этом они не характеризуют его.
IDF(word) = log D—ж ;
DW (word)
D - общее число документов;
DW(word) - количество документов, которые содержат слово word.
Третий этап совмещает первые две оценки.
RES (word) = TF (word) * IDF (word)
Пример. Допустим, документ содержит 100 слов, а слово ’’weapon” встретилось в документе 5 раз. TF(”weapon”) = 0.05. Пусть, при этом у нас есть 1000 документов, а слово ’weapon” встретилось всего лишь в 10 из них. IDF(”weapon”) = 4,6. В итоге оценка TF-IDF(”weapon”) = 0.23.
Модель TF-IDF можно применять и к Bag of words, и к Bag of n­grams. В случае с Bag of words ничего не требуется изменять. Если же применять TF-IDF к Bag of n-grams, то во всех формулах нужно заменить word на n-грамму.
Получившееся простраство можно дополнить метрикой. Многие ал­горитмы классификации нуждаются в расстоянии между двумя доку­ментами. Поэтому рассмотрим некоторые функции расстояния, кото­рые в дальнейшем понадобятся.
Метрика Минковского
n d(xyy) = (^хг - yp)p, x,y с Rn i=i
При p = 2, является Евклидовым расстоянием.
Косинусное сходство
ELi x * yi
/'n Д * /'n Id
v 2^i=i xi * V 2щ=1 yi
Расстояние Махаланобиса
d(x, y) = ^ (Xi 2yi ; x,y с Rn
s“ i=i
Здесь si - среднеквадратическое отклонение xi от yi в обучающей вы­борке.
Классификаторы
В данной работе будут рассматриваться и сравниваться следующие классификаторы:
1. Наивные алгоритмы
2. Байесовский классификатор
3. Метод опорных векторов
4. Метод k-ближайших соседей
Все эти классификаторы требуют обучения перед их использовани­ем. Для обучения классификаторов был проанализирован сайт theguardian.com и, с помощью простого парсера, были извлечены все предоставляемые этим сайтом криминальные статьи, а также часть ста­тей, которые не являются криминальными (спорт, технологии, жизнь, стиль).
1.4. Методы оценки результата алгоритма
При работе алгоритмов бинарной классификации может возникнуть одна из следующих ситуаций:
Таблица.
Пусто | Пусто | Настоящие значения
Пусто | Пусто | Криминальные | Не криминальные
Предсказанные значения | Криминальные | True positive | False positive
Предсказанные значения | Не криминальные | False negative | True negative
Конец таблицы.
Введем обозначения, соответствующие всем возможным результа­там:
• tp - количество true positive результатов при классификации;
• fp - количество false positive результатов при классификации;
• tn - количество true negative результатов при классификации;
• fn - количество false negative результатов при классификации.
На основе этих данных можно рассчитать некоторые общие оценки для классификации, которые не зависят от самого алгоритма.
Точность
Эта оценка показывает, насколько точно происходит классификация, т.е. сколько из предсказанных криминальных документов оказалась действительно крминальными. Чем ближе это значение к 1, тем больше true positive результатов в сравнении с false positive.
(формула в виде рисунка)
True positive rate
Показывает, сколько документов из общего числа реальных криминаль­ных документов были отнесены к криминальным. Также TPR часто называют полнотой. Чем ближе значение TPR к 1, тем больше true positive результатов в сравнении с false negative.
TPR = tp/tp + fn
False positive rate
Показывает, сколько документов из общего числа реальных некрими­нальных документов были отнесены к криминальным.
FPR = fP fp + tn
F-мера
Одновременно оценивает оба параметра - Precision и TPR
1 , , : — а 2 (0 1)
Precision + (1 а) * TPR
С помощью а можно увеличивать или уменьшать значимость пара­метров. Если а = 0.5, то такая F-мера называется сбалансированной.
ROC-кривая
Кривая, позволяющая оценить качество бинарной классификации. Она показывает зависимость TPR от FPR. Если классификатор может оце­нить вероятность принадлежности объекта к каждому классу, то будем использовать количественную интерпретацию ROC-кривой - AUC. AUC (англ. area under curve) - количественная оценка, которая означает пло­щадь под ROC-кривой.
Купить