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

Алгоритм, который вы только что описали. Программа, которая делает это из коробки с большой кнопкой с надписью «Сделай это» ... Не знаю.

Но позвольте мне быть конструктивным. Я рекомендую вам эту книгу Программирование коллективного разума. Главы 3 и 4 содержат очень прагматичные примеры (на самом деле, никаких сложных теорий, только примеры).

Некоторое время назад я написал полную программу для этого. Я могу загрузить демо позже, когда вернусь домой.

Вот код (asp.net/c#): http: //naspinski.net/post/Findingcounting-Keywords-out-of-a-Text-Document.aspx

Вам понадобится не один, а несколько хороших алгоритмов, как показано ниже.

• игнорирование местоимений осуществляется через список стоп-сигналов.
• сохраняя имена собственные? Вы имеете в виду обнаружение именованных сущностей, таких как ПылесосПлотина, и использование слов «это одно слово» или составных существительных, таких как программированиеязык? Я дам вам подсказку: это сложно, но существуют библиотеки для обоих. Ищите NER (именованное признание сущности) и лексические фрагменты. OpenNLP - это Java-Toolkit, который делает и то, и другое.
• игнорирование переносов? Вы имеете в виду, как при переносе строки? Используйте регулярные выражения и проверьте полученное слово с помощью поиска по словарю.
• обработка множественного числа / стемминг: вы можете посмотреть Стеммер снежка. Он отлично справляется со своей задачей.
• «группирование» прилагательных с их существительными обычно является задачей неглубокий разбор. Но если вы ищете именно качественные прилагательные (хороший, плохой, дерьмовый, потрясающий ...), вас может заинтересовать анализ настроений. LingPipe делает это и многое другое.

Извините, я знаю, что вы сказали, что хотите KISS, но, к сожалению, ваши требования не так-то легко удовлетворить. Тем не менее, для всего этого существуют инструменты, и вы должны иметь возможность просто связать их вместе, и вам не придется выполнять какие-либо задачи самостоятельно, если вы этого не хотите. Если вы хотите выполнить задачу самостоятельно, я предлагаю вам взглянуть на стемминг, это самый простой из всех.

Если вы используете Java, объедините Lucene с набором инструментов OpenNLP. Вы получите очень хорошие результаты, так как в Lucene уже есть встроенный стеммер и множество руководств. С другой стороны, инструментарий OpenNLP плохо документирован, но вам не понадобится слишком много от него. Вас также может заинтересовать НЛТК, написанный на Python.

Я бы сказал, что вы отбросите свое последнее требование, поскольку оно включает в себя неглубокий синтаксический анализ и определенно не ухудшит ваши результаты.

Ах, кстати. точный термин для того документа, который вы искали, называется tf-idf. Это в значительной степени лучший способ узнать, как часто в документе используются термины. Чтобы сделать это правильно, вам не обойтись без многомерных векторных матриц.

... Да, я знаю. После семинара по IR я стал еще больше уважать Google. Однако после того, как я поработал в IR, мое уважение к ним так же быстро упало.

Первая часть вашего вопроса звучит не так уж плохо. Все, что вам в основном нужно сделать, это прочитать каждое слово из файла (или потока w / e) и поместить его в дерево префиксов, и каждый раз, когда вы встречаетесь со словом, которое уже существует, вы увеличиваете значение, связанное с ним. Конечно, у вас будет список игнорирования всего, что вы хотели бы исключить из своих расчетов.

Если вы используете префиксное дерево, вы гарантируете, что для поиска любого слова нужно O (N), где N - максимальная длина слова в вашем наборе данных. Преимущество префиксного дерева в этой ситуации заключается в том, что если вы хотите искать множественное число и корень, вы можете проверить в O (M + 1), если это вообще возможно для слова, где M - длина слова без основы или множественности. (это слово? хе-хе). После того, как вы построили свое префиксное дерево, я бы повторно проанализировал его на предмет основ и прочего и сжал его так, чтобы корневое слово было тем, что содержало результаты.

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

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

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

Я уверен, что есть идеи получше, но я люблю думать об этом.

Добро пожаловать в мир НЛП ^ _ ^

Все, что вам нужно, - это базовые знания и инструменты.

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

$ echo "Without getting a degree in information retrieval, I'd like to know if there exists any algorithms for counting the frequency that words occur in a given body of text." | tree-tagger-english 
# Word  POS     surface form
Without IN  without
getting VVG get
a   DT  a
degree  NN  degree
in  IN  in
information NN  information
retrieval   NN  retrieval
,   ,   ,
I   PP  I
'd  MD  will
like    VV  like
to  TO  to
know    VV  know
if  IN  if
there   EX  there
exists  VVZ exist
any DT  any
algorithms  NNS algorithm
for IN  for
counting    VVG count
the DT  the
frequency   NN  frequency
that    IN/that that
words   NNS word
occur   VVP occur
in  IN  in
a   DT  a
given   VVN give
body    NN  body
of  IN  of
text    NN  text
.   SENT    .

Как вы можете видеть, он идентифицировал «алгоритмы» как форму множественного числа (NNS) слова «алгоритм» и «существует» как спряжение (VBZ) слова «существует». Он также идентифицировал "a" и "the" как "определители (DT)" - другое слово для обозначения статьи. Как видите, POS-теггер также размечал знаки препинания.

Чтобы сделать все, кроме последнего пункта в вашем списке, вам просто нужно пропустить текст через теггер POS, отфильтровать категории, которые вас не интересуют (определители, местоимения и т. д.), И подсчитать частоту базовых форм слова.

Вот несколько популярных тегеров POS:

TreeTagger (только двоичный: Linux, Solaris, OS-X)
GENIA Tagger (C++: скомпилируйте себя)
Стэнфордский POS Tagger (Java)

Чтобы сделать последнее в вашем списке, вам нужно больше, чем просто информация на уровне слов. Самый простой способ начать - считать последовательностиизслова, а не просто сами слова. Они называются н-граммы. Хорошее место для начала - UNIX для поэтов. Если вы готовы вложиться в книгу по НЛП, я бы порекомендовал Основы статистической обработки естественного языка.

Вот пример того, как вы могли бы сделать это в Python, концепции аналогичны на любом языке.

>>> import urllib2, string
>>> devilsdict = urllib2.urlopen('http://www.gutenberg.org/files/972/972.txt').read()
>>> workinglist = devilsdict.split()
>>> cleanlist = [item.strip(string.punctuation) for item in workinglist]
>>> results = {}
>>> skip = {'a':'', 'the':'', 'an':''}
>>> for item in cleanlist:
      if item not in skip:
        try:
          results[item] += 1
        except KeyError:
          results[item] = 1

>>> results
{'': 17, 'writings': 3, 'foul': 1, 'Sugar': 1, 'four': 8, 'Does': 1, "friend's": 1, 'hanging': 4, 'Until': 1, 'marching': 2 ...

Первая строка просто содержит библиотеки, которые помогают с частями проблемы, как и во второй строке, где urllib2 загружает копию «Дьявольского словаря» Амброуза Бирса. Следующие строки составляют список всех слов в тексте без знаков препинания. Затем вы создаете хеш-таблицу, которая в данном случае похожа на список уникальных слов, связанных с числом. Цикл for перебирает каждое слово в книге Бирса, если в таблице уже есть запись этого слова, каждое новое вхождение добавляет единицу к значению, связанному с этим словом в таблице; если слово еще не появилось, оно добавляется в таблицу со значением 1 (что означает одно вхождение). В тех случаях, о которых вы говорите, вы хотели бы уделять гораздо больше внимания деталям, например, используя заглавные буквы. чтобы помочь идентифицировать собственные существительные только в середине предложений и т. д., это очень грубо, но выражает концепцию.

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

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

Все, что вы перечислили, хорошо обрабатывается просторный.

1. Игнорировать некоторые слова - использовать стоп-слова
2. Извлечь тему - используйте часть речевых тегов, чтобы идентифицировать ее (работает из коробки). После анализа предложения найдите «ROOT» - главный глагол предложения. Под навигация по дереву синтаксического анализа вы найдете существительное, относящееся к этому глаголу. Это будет тема.
3. Игнорировать перенос - их токенизатор обрабатывает перенос в большинстве случаев. Его можно легко расширить для обработки большего количества особых случаев.

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