Н-грамм:Пояснение + 2 приложения
Вопрос
Я хочу реализовать некоторые приложения с помощью n-грамм (желательно на PHP).
Какой тип n-грамм более подходит для большинства целей?Н-грамма уровня слова или уровня символов?Как можно реализовать токенизатор n-грамм в PHP?
Во-первых, я хотел бы знать, что такое N-граммы.Это верно?Вот как я понимаю n-граммы:
Предложение:«Я живу в Нью-Йорке».
Биграммы уровня слова (2 для n):«#Я», «Я живу», «живу в», «в Нью-Йорке», «Нью-Йорк#»
Биграммы уровня персонажа (2 для n):«#I», «I#», «#l», «li», «iv», «ve», «e#», «#i», «in», «n#», «#N», «НЙ», «Й#»
Когда у вас есть этот массив из n-граммовых частей, вы удаляете дубликаты и добавляете счетчик для каждой части, указывающий частоту:
Биграммы уровня слова:[1, 1, 1, 1, 1]
Биграммы уровня персонажа:[2, 1, 1, ...]
Это верно?
Кроме того, я хотел бы узнать больше о том, что можно делать с n-граммами:
- Как определить язык текста с помощью n-грамм?
- Можно ли выполнить машинный перевод с использованием n-грамм, даже если у вас нет двуязычного корпуса?
- Как я могу построить спам-фильтр (спам, ветчина)?Объединить n-граммы с байесовским фильтром?
- Как я могу определить тему?Например:Текст о баскетболе или собаках?Мой подход (сделайте следующее со статьей в Википедии о «собаках» и «баскетболе»):построить векторы n-грамм для обоих документов, нормализовать их, вычислить Манхэттенское/Евклидово расстояние, чем ближе результат к 1, тем выше сходство
Что вы думаете о моих подходах к подаче заявок, особенно о последнем?
Я надеюсь, что вы можете мне помочь.Заранее спасибо!
Решение
Н-граммы слов, как правило, будут более полезны для большинства упомянутых вами приложений анализа текста, за исключением, возможно, определения языка, где что-то вроде триграмм символов может дать лучшие результаты.По сути, вы должны создать вектор n-грамм для корпуса текста на каждом языке, который вы хотите обнаружить, а затем сравнить частоты триграмм в каждом корпусе с триграммами в документе, который вы классифицируете.Например, триграмма the
вероятно, встречается гораздо чаще в английском языке, чем в немецком, и может обеспечить некоторый уровень статистической корреляции.Если у вас есть документы в формате n-грамм, у вас есть выбор из множества алгоритмов для дальнейшего анализа, байсовских фильтров, N-ближайшего соседа, машин опорных векторов и т. д.
Из упомянутых вами приложений машинный перевод, вероятно, является самым надуманным, поскольку сами по себе n-граммы не проведут вас слишком далеко.Преобразование входного файла в n-граммное представление — это всего лишь способ преобразовать данные в формат для дальнейшего анализа объектов, но поскольку вы теряете много контекстной информации, это может оказаться бесполезным для перевода.
Следует обратить внимание на то, что недостаточно создать вектор [1,1,1,2,1] для одного документа и вектор [2,1,2,4] для другого документа, если размеры не совпадают.То есть первая запись в векторе не может быть the
в одном документе и is
в другом, иначе алгоритмы не будут работать.В итоге вы получите векторы типа [0,0,0,0,1,1,0,0,2,0,0,1], поскольку большинство документов не будут содержать большинство интересующих вас n-грамм.Такое «выстраивание» функций имеет важное значение, и оно требует от вас «заранее» решить, какие ngrams вы будете включать в свой анализ.Часто это реализуется в виде двухпроходного алгоритма, чтобы сначала определить статистическую значимость различных n-грамм, чтобы решить, что сохранить.Google «выбор функций» для получения дополнительной информации.
Н-граммы на основе слов плюс машины опорных векторов — отличный способ определения тем, но для обучения классификатора вам понадобится большой корпус текста, предварительно классифицированный на «по теме» и «не по теме».Большое количество научных статей, объясняющих различные подходы к этой проблеме, вы найдете на таком сайте, как citeseerx.Я бы не рекомендовал подход к этой проблеме с использованием евклидова расстояния, поскольку он не взвешивает отдельные n-граммы на основе статистической значимости, поэтому два документа, которые оба включают the
, a
, is
, и of
будет считаться более подходящим, чем два документа, оба из которых включают Baysian
.Удаление стоп-слов из интересующих вас n-грамм несколько улучшит ситуацию.
Другие советы
Вы правы относительно определения n-грамм.
Вы можете использовать n-граммы на уровне слов для приложений типа поиска.Н-граммы уровня символов можно использовать больше для анализа самого текста.Например, чтобы определить язык текста, я бы использовал частоты букв по сравнению с установленными частотами языка.То есть текст должен примерно соответствовать частоте встречаемости букв данного языка.
Токенизатор n-грамм для слов в PHP можно выполнить с помощью strtok:
http://us2.php.net/manual/en/function.strtok.php
Для символов используйте разделение:
http://us2.php.net/manual/en/function.str-split.php
Затем вы можете просто разделить массив на любое количество n-грамм.
Байесовские фильтры необходимо подготовить для использования в качестве спам-фильтров, которые можно использовать в сочетании с n-граммами.Однако вам нужно дать ему много информации, чтобы он научился.
Ваш последний подход звучит прилично с точки зрения изучения контекста страницы...Однако это по-прежнему довольно сложно сделать, но n-граммы кажутся хорошей отправной точкой для этого.