"Частотный анализ текстов и его применение"



Скачать 151.25 Kb.
Дата01.07.2013
Размер151.25 Kb.
ТипКурсовая
МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

имени М.В. ЛОМОНОСОВА

Механико-математический факультет

Кафедра вычислительной математики

Курсовая работа

на тему:

"Частотный анализ текстов

и его применение"

Выполнил:

студент 410 группы

Тарасов Глеб

Научный руководитель:

Ю. Н. Пронкин

2009 год

Содержание


  1. Введение.

        • Постановка задачи.

        • Область применения.

  2. Метрика на пространстве текстов и другие меры близости текстов.

        • Стандартная метрика.

        • Уменьшение размерности с помощью алгоритма выбора ключевых слов.

        • Предвыборка ключевых слов.

        • Морфологический анализ.

        • Удаление слов с высокой частотой.

        • Окончание алгоритма.

  3. Применения полученных мер близости.

      1. Кластеризация текстов с помощью методов кластерного анализа.

          • Итерационный метод (k-средних).

          • Иерархические методы.

      2. Реферирование текста (выборка наиболее емких предложений).

      3. Выдача по запросу (выборка наиболее релевантных предложений).

  4. Заключение.

  5. Список использованных ресурсов.

  6. Приложение.

      1. Результаты выбора ключевых слов.

      2. Результаты применения различных методов кластеризации.

      3. Результаты реферирования и выдачи по запросу.

      4. Результаты вычислений различных мер близости.




I. Введение

1. Постановка задачи

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

Под пространством текстов подразумевается конечномерное пространство, размерность которого равно количеству слов в русском языке, коэффициентами перед базисными векторами для вектора-текста может быть либо 0 (слово не присутствует в тексте), либо 1 (слово есть в тексте). Стандартной нормой на этом векторном пространстве является обычный скалярный квадрат вектора-текста. Однако, такая норма часто не удовлетворяет на практике нужным требованиям. Она не учитывает различную «значимость» слов, которую они привносят в близость текстов. Так, например, одинаковое вхождение слова «на» или «и» не может ничего говорить об одинаковой теме текстов, а одновременное вхождение слов «акция», «гол», «нанотехнологии» могут в какой-то степени нам сообщить о схо­жести текстов.


Таким образом, для улучшения меры близости нам необходимо исключить влияние не меняющих смысл текста слов на величину коэффициента схожести, а также увеличить влияние таких слов, которые влияют на смысл значительно.

Целью данной работы является изучение возможности применения вычисления меры близости текстов исключительно по частотным характеристикам слов в тексте (с применением морфологического анализа), но без сложного семантического анализа текста в целом. Изучить характеристики текстов, на которых эти методы можно применять с удовлетворительными результатами.
2. Область применения.

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

1. Стандартная метрика.

Можно рассматривать пространство текстов как векторное пространство, с базисными векторами - текстами, состоящими из одного слова. В соответствующей координате вектора-текста стоит либо 1 (если соответствующее слово есть в тексте), либо 0 (если этого слова в тексте нет).Тогда мы можем найти метрику (расстояние между двумя текстами), как скалярный квадрат двух векторов. Первичное улучшение метрики - учитывать количество вхождений одного слова в текст, т.е. в соответствующей слову координате стоит количество вхождений этого слова в текст-вектор.
2. Уменьшение размерности с помощью алгоритма выбора ключевых слов.

Основная идея улучшения метрики - удаление «незначительных» слов и увеличение влияния на метрику «значительных» слов. Выбирать ключевые слова мы будем по следующему алгоритму:

  • предвыборка ключевых слов

  • морфологический анализ и приведение к начальному виду оставшихся слов

  • удаление слов с высокой частотой по частотному словарю


3. Предвыборка ключевых слов.

Для каждого типа текстов разные виды слов могут по-разному влиять на схожесть. Далее будем рассматривать методы поиска схожести с упором на поиск похожих новостей. Большинство соображений будут верны и для других типов текстов. Итак, важными при определении схожести текстов являются имена собственные (фамилии, названия фирм, названия различных объектов). Все слова, начинающиеся с большой буквы, но стоящие не в начале предложения мы включаем в предвыборку. Если в тексте на русском языке присутствуют слова из букв другого алфавита, имеет смысл их также включить в предвыборку, т.к. появление этих слов в обоих текстах имеет важное значение.
4. Морфологический анализ.

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

  • приведение прилагательных к существительным, а причастий и деепричастий к глаголам (кошачий - кошка, прыгающий - прыгать)

  • поиск синонимов и лексически похожих слов и добавление их в список ключевых (сидеть - восседать)

  • поиск семантически похожих слов и добавление их в список ключевых (кошка - млекопитащее)

Однако, уменьшение скорости работы общего алгоритма не оправдалось улучшением качества, лучшие результаты были показаны с применением только первого пункта.
Весь морфологический анализ проводился с помощью находящейся в свободном доступе библиотеки Solarix - "Грамматическая машина". Описание и компоненты доступны на сайте http://www.solarix.ru/for_users/map/map.shtml
5. Удаление слов с высокой частотой

Для того, чтобы уменьшить влияние частоупотребляемых слов на метрику, – будем убирать слова с частотой по частотному словарю больше заданной. Параметр, при частоте слова больше которого, мы удаляем слова, будем подбирать на практике, исходя из качества алгоритма. Таблица частотного словаря (162000 записей) имеет следующий вид:
804 особенно

803 таким

801 моей

798 думаю

797 две

795 з

792 заметил

790 пред

789 г

778 каким

774 казалось

773 действительно

766 ужасно

761 людей

755 иванович

755 пошел

754 лишь

753 которого

747 вовсе

746 которой

746 сюда

745 слово

742 ночь

741 стороны


Частотный словарь был обработан с помощью морфологического анализа из предыдущего пункта и получен новый словарь (60000 записей), который также учитывается при удалении частоупотребимых слов (можно обратить внимание, как частоты всех форм просуммировались для слова КОТОРЫЙ):
1535 СЕЙЧАС

1566 МНОГО

1771 ПЕРЕД

1528 ТОЧНО

1493 ТОТЧАС

1491 КАЖЕТСЯ

1582 НЕСКОЛЬКИЕ

1476 ВПРОЧЕМ

4462 ДРУГОЙ

2153 БОЛЬШОЙ

7560 КОТОРЫЙ

2612 СТАТЬ

1391 АХ

2799 ДРУГ

2338 СЕРДЦЕ

1893 ИВАН

1363 НАД

2541 МИНУТА

5105 РУКА

1686 ТРИ

1765 ПЕТР

1851 АЛЕКСАНДР

1378 ХОРОШО

1679 СОВЕРШЕНСТВО

5781 ХОТЕТЬ

1305 КОНЕЧНО

2376 СПРОС

4108 ЭТА
6. Окончание алгоритма

Получив для каждого текста векторы ключевых слов (размер которых управляется коэффициентом удаления частоупотребимых слов), мы можем вычислять норму и метрику уже над пространством ключевых слов, размерность которого намного меньше.
На практике выясняется, что более эффективно применять не стандартную метрику, а меру близости, которая с увеличением схожести слов увеличивается. Можно применять различные меры близости:

  • количество общих слов (скалярное произведение векторов с координатами 1 или 0)

  • мера, учитывающая количество вхождений каждого слова (скалярное произведение векторов, координаты - количество вхождений ключевого слова в различных формах в текст)

  • мера, учитывающая размеры текстов (предыдущая мера, деленная на произведение размеров векторов ключевых слов).

После различных экспериментов для дальнейших исследований была выбрана вторая мера близости, показавшая наилучшие результаты на небольших текстах сходных размеров.
III. Применения полученных мер близости.

1. Кластеризация текстов с помощью методов кластерного анализа.

Итерационный метод (k-средних).

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

Иерархические методы.

Реализовано несколько иерархических методов. Первый метод, основанный на объединении кластеров. Построение дендрограммы с остановкой объединения кластеров при достижении расстояния наперед заданного параметра. На тестовых данных не удалось подобрать параметр, при котором алгоритм отработал безошибочно. Наилучшим результатом стало правильное распределение трех кластеров и разделение оставшейся темы на несколько кластеров.

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

Последний метод наиболее простой, но показал хороший результат. Сначала выбираем один текст с наибольшей нормой и добавляем его в список, затем каждый раз ищем текст, ближайший к нашему списку и добавляем его в список. Получаем упорядоченный массив текстов. Теперь анализируя меры близости между соседями, разбиваем по минимальным на кластеры. Этот метод как и k-средних дал стопроцентный результат с некоторым подобранным параметром, однако без указания заранее количества кластеров.
2. Реферирование текста (выборка наиболее емких предложений).

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

Также без особых усилий можно реализовать и выборку по запросу, чуть более релевантную, чем просто полнотекстовый поиск. Находя меру близости между запросом и каждым предложением (или частью предложения), и выбираю несколько наиболее близких - получаем в результате набор наиболее релевантных предложений к запросу. Пример выдачи по запросу можно найти в Приложении.
IV. Заключение.

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

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


  • http://www.artint.ru/projects/frqlist.asp

  • http://www.intuit.ru/department/database/datamining/13/2.html

  • http://www.solarix.ru/for_developers/api/morphology-analyzer-api.shtml

  • http://download.yandex.ru/IMAT2007/kiselev.pdf



V|. Приложение

1. Результаты выбора ключевых слов.



      1. В качестве тестовых текстов использовались новости 4 различных тем по 5 новостей в каждой теме.

      2. Темы: Безработица, Грузия, Спартак, Формула 1.



      3. Исходные тексты проекта и всех используемых материалов можно найти в репозитарии:

      4. http://subversion.assembla.com/svn/GlebTermPaper



      5. Тестовая новость для выбора ключевых слов:

      6. ТБИЛИСИ, 19 апр - РИА Новости. Сторонники грузинской оппозиции, которая требует отставки Михаила Саакашвили с поста президента Грузии, отметили Пасхальное воскресенье за праздничным столом, накрытым прямо у центрального входа в президентскую резиденцию, сообщает агентство "Новости-Грузия".

      7. "Поздравляю всех и желаю всей Грузии, чтобы великий праздник Пасхи стал серьезным началом спасения страны. Мы, все присутствующие здесь, верим в это!", - заявил собравшимся лидер Консервативной партии Грузии Звиад Дзидзигури.

      8. За праздничным столом собралось около 100 человек, в том числе ведущие деятели оппозиции - один из лидеров партии "Движение за единую Грузию" Эка Беселия, лидер Партии народа Коба Давиташвили, видные деятели культуры, в том числе актер Отар Мегвинетухуцеси.

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

      10. Стол, накрытый сторонниками оппозиции, был богато уставлен традиционными праздничными грузинскими блюдами - жареным поросенком, чакапули (вареная баранина со специями), хачапури (лепешки с сыром). Оппозиционеры произносили тосты, запивая кахетинским вином.

      11. Представители властей Грузии также отметили праздник Пасхи под открытым небом, накрыв стол в одном из "итальянских" двориков в старой части Тбилиси. Представители мэрии привезли туда барашков и вино, вместе с десятками жильцов приняли участие в застолье.



      12. Пример выбора ключевых слов без добавления синонимов:

      13. [ТБИЛИСИ, 2], [АПР, 1], [РИА, 2], [НОВОСТЬ, 2], [СТОРОННИК, 2], [ГРУЗИЯ, 8], [МИХАИЛ, 1], [СААКАШВИЛИ, 2], [ПАСХА, 3], [ПРЕЗИДЕНТСКИЙ, 2], [РЕЗИДЕНЦИЯ, 2], [АГЕНТСТВО, 1], [ЛИДЕР, 3], [КОНСЕРВАТИЗМ, 1], [ЗВИАД, 1], [ДЗИДЗИГУРИ, 2], [ДВИЖЕНИЕ, 1], [ЭКА, 1], [БЕСЕЛИЯ, 2], [ПАРТИЯ, 1], [КОБА, 1], [ДАВИТАШВИЛИ, 2], [ОТАРА, 1], [МЕГВИНЕТУХУЦЕСИ, 2], [ЗАСТОЛЬЕ, 2], [АКТИВИСТ, 1], [ТРАДИЦИОННОСТЬ, 1], [ЧАКАПУЛИ, 2], [СПЕЦИЯ, 1], [ХАЧАПУРИ, 2], [ОППОЗИЦИОНЕРЫ, 1], [КАХЕТИНСКИЙ, 1], [МЭРИЯ, 1]



      14. Пример выбора ключевых слов с добавлением синонимов:

      15. [ТБИЛИСИ, 2], [ТБИЛИССКИЙ, 2], [19, 1], [АПР, 1], [РИА, 1], [НОВОСТЬ, 2], [НОВИНКА, 2], [НОВОСТНОЙ, 2], [СТОРОННИК, 2], [ПОБОРНИК, 2], [ПРИВЕРЖЕНЕЦ, 2], [СТОРОННИЦА, 2], [ГРУЗИНСКИЙ, 8], [ГРУЗИЯ, 8], [МИХАИЛ, 1], [МИША, 1], [МИШКА, 1], [ИМЯ, 1], [МАЙКЛ, 1], [МИШЕНЬКА, 1], [СААКАШВИЛИ, 1], [ГРУЗИН, 6], [ГРУЗИНКА, 6], [СТРАНА, 6], [ПАСХАЛЬНЫЙ, 3], [ПАСХА, 3], [ПРЕЗИДЕНТСКИЙ, 2], [ПРЕЗИДЕНТ, 2], [РЕЗИДЕНЦИЯ, 2], [АГЕНТСТВО, 1], [ЛИДЕР, 3], [ЛИДЕРСКИЙ, 3], [КОНСЕРВАТИВНЫЙ, 1], [КОНСЕРВАТОР, 1], [КОНСЕРВАТИЗМ, 1], [КОСНЫЙ, 1], [ЗВИАД, 1], [ДЗИДЗИГУРИ, 1], [100, 1], [ДВИЖЕНИЕ, 1], [ДВИГАТЬ, 1], [ДВИНУТЬ, 1], [ДВИГАТЬСЯ, 1], [ДВИНУТЬСЯ, 1], [ШЕВЕЛЕНИЕ, 1], [ДВИЖУЩИЙСЯ, 1], [ДВИЖУЩИЙ, 1], [ЭКА, 1], [БЕСЕЛИЯ, 1], [ПАРТИЯ, 1], [ПАРТИЙНЫЙ, 1], [БЕСПАРТИЙНЫЙ, 1], [ДВУХПАРТИЙНЫЙ, 1], [КОБА, 1], [ДАВИТАШВИЛИ, 1], [ОТАРА, 1], [МЕГВИНЕТУХУЦЕСИ, 1], [ЗАСТОЛЬЕ, 2], [ЗАСТОЛЬНЫЙ, 2], [АКТИВИСТ, 1], [АКТИВИСТКА, 1], [ACTIVIST, 1], [ТРАДИЦИОННЫЙ, 1], [ТРАДИЦИОННОСТЬ, 1], [ТРАДИЦИЯ, 1], [ЧАКАПУЛИ, 1], [СПЕЦИЯ, 1], [ХАЧАПУРИ, 1], [ОППОЗИЦИОНЕРЫ, 1], [КАХЕТИНСКИЙ, 1], [МЭРИЯ, 1], [МЭР, 1], [МЭРСКИЙ, 1]



      16. 2. Результаты применения различных методов кластеризации.



      17. Алгоритм K-middle с параметром 4, полученные кластеры:

      18. [bezrabotica1 bezrabotica2 bezrabotica3 bezrabotica4 bezrabotica5],

      19. [spartak1 spartak2 spartak3 spartak4 spartak5],

      20. [gruziya1, gruziya2, gruziya3, gruziya4, gruziya5]

      21. [auto1, auto2, auto3, auto4, auto5]



      22. Алгоритм Limit с параметром 0, полученные кластеры:

      23. [spartak4 spartak2 spartak1 spartak3 spartak5],

      24. [auto1, auto3, auto2]

      25. [gruziya5, gruziya2, gruziya4. gruziya3, gruziya1, bezrabotica4],

      26. [bezrabotica1 bezrabotica2 bezrabotica5 bezrabotica3],

      27. [auto4, auto5]









      28. Алгоритм Tree с параметром 47, полученные кластеры:

      29. [bezrabotica1 bezrabotica2 bezrabotica4 bezrabotica3 bezrabotica5],

      30. [spartak1 spartak2 spartak4 spartak3 spartak5],

      31. [gruziya1, gruziya2, gruziya5, gruziya4, gruziya3]

      32. [auto1, auto3, auto2]

      33. [auto4]

      34. [auto5]



      35. Алгоритм Jump с параметром 6, полученные кластеры:

      36. [spartak4 spartak2 spartak3 spartak5 spartak1],

      37. [bezrabotica1 bezrabotica4 bezrabotica2 bezrabotica3 bezrabotica5],

      38. [gruziya4, gruziya5, gruziya3. gruziya2, gruziya1],

      39. [auto2, auto1, auto3, auto5, auto4]



      40. 3. Результаты реферирования и выдачи по запросу.

      41. Реферирование и выдача по запросу тестировалась на переведенной статье Бена Гомеса про работу поиска в Google (ее полный текст можно найти в папке с исходными текстами проекта).



      42. Алгоритм Abstracting с параметром 5:

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

      44. Исправление правописания, описания страниц, ссылки на сайты и уточнение запросов - все это примеры постоянно развивающихся функций, требующих сложнейших алгоритмов

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

      46. Google, вместо этого, показывал те фрагменты страницы, где отображались интересующие пользователя ключевые слова (специалисты в области информационного поиска обычно называют это "показом ключевых слов в контексте")

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









      48. Алгоритм AbstractingQuery с параметром 5:

      49. Запрос: Качественный поиск - залог успеха Google как лидера в области поиска текстов

      50. Результат:

      51. Хотя ранжирование документов в сети - это основа качественной работы Google, но это далеко не все, что нужно для удобства, быстроты и эффективности поиска

      52. Я работаю в Google с 1999 года и занимаюсь вопросами, связанными с поиском, в основном - качеством поиска

      53. Google хорош именно таким, какой он есть - простой, понятный и быстрый

      54. Наш успех, в частности, определяется тем, как быстро вы покидаете Google (надеемся, что с хорошими впечатлениями)





      55. 4. Результаты вычислений различных мер близости.



      56. В таблице приведены вычисленные меры близости для некоторых текстов. Столбцы отображают:



      57. - индекс первой новости

      58. - индекс второй новости

      59. - первая мера близости (число совпадающих ключевых слов)

      60. - вторая мера близости (учитывающая кол-во вхождений каждого ключевого слова)

      61. - третья мера близости (учитывающая размер текстов)

      62. - первая метрика (стандартная метрика через норму)

      63. - вторая метрика (учитывающая кол-во вхождений каждого ключевого слова)

      64. - третья метрика (вторая, деленная на произведение размеров векторов ключевых слов)

Похожие:

\"Частотный анализ текстов и его применение\" iconКурс, семестр, 20 часов
Частотный отклик. Импульсный отклик свободного пространства. Линза как фазовый транспарант. Расчет импульсного отклика простейшей...
\"Частотный анализ текстов и его применение\" iconМетод синтактико-семантических шаблонов и его применение в информационной технологии интерпретации текстов
Цель диссертационной работы: совершенствование информационной технологии компьютерной интерпретации текстов на естественном языке...
\"Частотный анализ текстов и его применение\" iconПространственно-частотный спектральный анализ и оптико-электронный спектроанализатор для контроля подлинности защитных голограмм

\"Частотный анализ текстов и его применение\" iconКонцептуальный анализ и проектирование Введение в аппарат ступеней и его применение Концепт Москва 2010 Серия «Концептуальный анализ и проектирование»
С. П. Никаноров. Введение в аппарат ступеней и его применение. Серия «Концептуальный анализ и проектирование». Математический аппарат....
\"Частотный анализ текстов и его применение\" iconКомпьютерная грамматика русского языка
Анализ текста естественным образом разбивается на три этапа: анализ отдельного слова, анализ предложения и анализ связного текста....
\"Частотный анализ текстов и его применение\" iconСистемный анализ корпуса текстов научного знания
Также описан алгоритм поиска в корпусе документов с помощью описанной модели. Рассматривается подход к обработке текстов авторефератов...
\"Частотный анализ текстов и его применение\" iconЛабораторная работа №3 частотный анализ типовых звеньев
Сущность метода частотных характеристик заключается в том, что на вход исследуемой системы подается гармонический сигнал (синусоидальные...
\"Частотный анализ текстов и его применение\" iconСтатья: Анализ ликвидности и его применение при управлении активами и пассивами банка

\"Частотный анализ текстов и его применение\" icon«Филология пред. Собой содружество гуман дисциплин (языкоз., лингвистика, литературовед-е, текстология, источниковед-е и др.), изучающее дух. Культуру чела ч/з языковой и стилист. Анализ письменных текстов» (лэс) Т. О
Культуру чела ч/з языковой и стилист. Анализ письменных текстов (лэс) Т. О. предметом филологии явл-ся слово, язык, тексты. Филология...
\"Частотный анализ текстов и его применение\" iconФизическая оптика
Частотный анализ оптических систем. Интеграл суперпозиции. Импульсный отклик оптической системы. Обобщенная модель оптической системы...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org