N-граммы: объяснение + 2 приложения - PullRequest
18 голосов
/ 23 июня 2009

Я хочу реализовать некоторые приложения с n-граммами (желательно на PHP).


Какой тип n-грамм более подходит для большинства целей? Уровень слова или уровень персонажа n-грамм? Как вы могли бы реализовать n-грамм-токенизатор в PHP?


Во-первых, я хотел бы знать, что такое N-граммы. Это правильно? Вот как я понимаю н-грамм:

Приговор: "Я живу в Нью-Йорке."

биграммы на уровне слов (2 для n): "# I", "Я живу", "живу в", "в Нью-Йорке", "NY #"

биграммы уровня символов (2 для n): "#I", "I #", "#l", "li", "iv", "ve", "e #", "#i", "in "," n # "," #N "," NY "," Y # "

Если у вас есть этот массив n-граммовых частей, вы отбрасываете дубликаты и добавляете счетчик для каждой части, дающий частоту:

биграммы на уровне слов: [1, 1, 1, 1, 1]

биграммы уровня персонажа: [2, 1, 1, ...]

Это правильно?


Кроме того, я хотел бы узнать больше о том, что вы можете делать с n-граммами:

  • Как я могу определить язык текста, используя n-граммы?
  • Можно ли сделать машинный перевод с использованием n-грамм, даже если у вас нет двуязычного корпуса?
  • Как мне создать спам-фильтр (спам, хам)? Объединить n-грамм с байесовским фильтром?
  • Как я могу сделать поиск темы? Например: текст о баскетболе или собаках? Мой подход (сделайте следующее со статьей из Википедии для «собак» и «баскетбол»): создайте n-граммовые векторы для обоих документов, нормализуйте их, вычислите расстояние Манхэттен / Евклид, чем ближе результат к 1, тем выше сходство

Что вы думаете о моих подходах к приложениям, особенно о последних?


Надеюсь, вы мне поможете. Заранее спасибо!

Ответы [ 2 ]

26 голосов
/ 23 июня 2009

Слово n-граммы, как правило, будет более полезным для большинства приложений анализа текста, о которых вы упомянули, с возможным исключением определения языка, где что-то вроде символьных триграмм может дать лучшие результаты. По сути, вы должны создать 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-грамм. Эта подкладка Важное значение имеет набор функций, и он требует от вас «заранее» решить, какие нграммы вы будете включать в свой анализ. Часто это реализуется в виде двухпроходного алгоритма, чтобы сначала определить статистическую значимость различных n-грамм, чтобы решить, что сохранить. Google "выбор функций" для получения дополнительной информации.

n-граммы на основе слов и вспомогательные векторные машины - отличный способ выполнить выбор темы, но для обучения классификатора необходим большой объем текста, предварительно классифицированный как «по теме» и «не по теме». На сайте, подобном citeseerx , вы найдете большое количество научных статей, объясняющих различные подходы к этой проблеме. Я бы не рекомендовал евклидово дистанционное приближение к этой проблеме, так как он не взвешивает отдельные n-граммы на основе статистической значимости, поэтому два документа, которые включают the, a, is и of, будут считается лучшим совпадением, чем два документа, которые оба включали Baysian. Удаление стоп-слов из ваших n-грамм интереса могло бы несколько улучшить это.

2 голосов
/ 23 июня 2009

Вы правы насчет определения н-граммов.

Вы можете использовать n-граммы на уровне слов для приложений типа поиска. N-граммы уровня символов могут быть использованы больше для анализа самого текста. Например, чтобы определить язык текста, я бы использовал частоты букв по сравнению с установленными частотами языка. То есть текст должен примерно соответствовать частоте встречаемости букв на этом языке.

токенайзер n-граммы для слов в PHP можно сделать с помощью команды strtok:

http://us2.php.net/manual/en/function.strtok.php

Для символов используйте split:

http://us2.php.net/manual/en/function.str-split.php

Тогда вы можете просто разделить массив на любое количество n-грамм.

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

Ваш последний подход звучит достойно, если учить контекст страницы ... это все же довольно сложно сделать, но n-граммы звучат как хорошая отправная точка для этого.

...