Сравнение моделей представления слов в задаче очистки текста от обесцененной лексики

Размещено на http://www.allbest.ru/

Правительство Российской Федерации

Федеральное государственное автономное образовательное

учреждение высшего образования

"Национальный исследовательский университет "Высшая школа экономики"

Факультет компьютерных наук

Основная образовательная программа

Прикладная математика и информатика

ВЫПУСКНАЯ КВАЛИФИКАЦИОННАЯ РАБОТА на тему

Сравнение моделей представления слов в задаче очистки текста от обесцененной лексики

Выполнил студент группы БПМИ-122 4 курса,

Котов Георгий Витальевич

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

Черняк Екатерина Леонидовна

Москва

2016

Оглавление

1. Мотивация задачи

2. Формальная постановка задачи

3. Описание данных

4. Описание используемых мер близости

5. Полученные результаты

6. Программная реализация

Заключение

Список использованной литературы

1. Мотивация задачи

Предметом настоящего исследования является сравнение моделей представления слов в задаче очистки текста от обесцененной лексики. Данная тема была выбрана поскольку ее применение в наши дни очень важно и актуально, так как существует множество сфер, где она может быть применена. Актуальность этой темы объясняется тем, что многие из современных авторов или журналистов используют в своих работах нецензурную лексику. Данная манера писать или разговаривать, сегодня, очень популярна и иногда даже приветствуется, но, на мой взгляд, это не правильно. Наш язык очень богат и красив и без обесцененной лексики, которая только портит и оскверняет его. К сожалению, все чаще и чаще ненормативная лексика становится нормой жизни, то есть люди приравнивают ее к своему образу жизни. Они используют ее, не испытывая при этом, какие-либо переживания, например, стыд. Для них ненормативная лексика становиться нормой, в том числе и из-за того, что средства массовой информации не стесняются также ее использовать. Также ненормативная лексика популярна среди подростков. Таким образом, подрастающее поколение пытается утвердиться в глазах своих сверстников или людей, которые немного старше их. Впоследствии, они привыкают к общению на языке обесцененной лексики и это также становится их "стилем" жизни. Собственно, они также интересуются жизнью с помощью средств массовой информации, видят при этом, что использование ненормативной лексики не наказывается, и продолжают ее использовать в своем лексиконе. Так как, согласно российским и европейским исследованиям в настоящее время дети становятся пользователями интернета уже в 9-10 лет. В этом возрасте дети склонны повторять то, что они увидели или прочитали, соответственно их надо постараться максимально оградить от этого. При этом запрещать использовать интернет для родителей это не выход, так как тем или иным способом ребенок сможет это сделать. Например, ребенок сможет выйти в интернет в школе или попросить у сверстника, чтобы тот ему помог. Более того, часто родители не знают о том, что в интернете ребенка может поджидать опасность. Соответственно, чтобы оградить ребенка и не только хотя бы от одного неприятного момента проводилось мое исследование[1].

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

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

2. Формальная постановка задачи

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

· Исследование различных методов поиска обесцененной лексики в текстах и их оптимизация

· Сравнение методов и выбор самого оптимального из них

· Применение методов на ряде документов и текстов

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

· Составление коллекции текстов, содержащих ненормативную лексику

· Разметка составленной коллекции в ручную - далее эта разметка будет использовать как эталон

· Обработка каждого текста: приведение к нижнему регистру и разбиение на слова

· Порождение слов-кандидатов с использованием различных методов

· Сравнение результатов, получаемых по различным методам, по точности и полноте

· Выбор оптимального метода

3. Описание данных

Для выполнения поставленной задачи понадобилось несколько видов данных. Первым и самым главным стал, так называемый "Стоп-лист". Небольшой фрагмент из данного файла можно увидеть на рис. 2.1

Рис. 2.1.

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

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

Для достижения результата мною был выбран специальный интернет ресурс, с помощью которого мне удалось найти статьи, которые были мне необходимы. Адрес этого ресурса: https://lurkmore.to/. На данном сайте практически полностью отсутствует цензура, что и требуется для достижения цели. Далее была создана коллекция из статей, которые впоследствии будут использоваться для анализа методов. Приведем в пример на рис.2.2. небольшой отрывок из одной статьи, чтобы наглядно показать всю аморальность данных статей.

Рис 2.2.

4. Описание используемых мер близости

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

1. Простой поиск по совпадению

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

2. Лемматизация

Второй способ - это лемматизация. Лемматизация - процесс приведения слова к его нормальной (словарной) форме. Так, например, нормальной форма слова "столами" является слово "стол" (то есть, форма единственного числа, именительного падежа). На языке программирования с помощью, которого я реализовываю свою работу, Python 3.4.3 создана специальная библиотека, которая приводит слова к их нормальной форме[4].

Поиск ненормативной лексики осуществляется следующим образом:

· Каждая статья разбивается на слова

· Каждое слово приводится к нормальной форме

· Поиск по совпадению нормальных форм в стоп-листе

То есть сначала происходит лемматизация всей статьи. Так как стоп-лист содержит слава в своей нормальной форме его лемматизировать не требуется. После приведения слов из статьи к их нормальной форме происходит опять поиск по совпадению. Данный метод намного более полный, нежели метод "простого" поиска по совпадению.

3. Стемминг

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

Рис 5.1.

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

4.Редакционное расстояние Левенштейна

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

5. Теоретико-множественная мера Жаккара

Пятый способ - мера Жаккара.

Мера Жаккара -- бинарная мера сходства, предложенная Полем Жаккаром в 1901 году :

где -- общее количество чего-либо в первой составляющей, -- общее количество чего-либо в первой составляющей, -- общее количество чего-либо для первой и второй составляющей, то есть их пересечение. Это первый известный коэффициент сходства. Коэффициент Жаккара в различных модификациях и записях активно используется в экологии, геоботанике, молекулярной биологии, биоинформатике, геномике, протеиномике, информатике и др. направлениях[2].

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

где А - множество частей слова из статьи, B - множество частей слова из стоп-листа. Этот способ также как и предыдущий может допускать ошибки, но так как важна полнота результата этот способ очень актуален для данной работы. Также стоить отметить, что этот способ намного быстрее, чем предыдущий.

6. Метод аннотированного суффиксного дерева

Шестой метод - построение суффиксных деревьев.

Среди большого количества методов анализа текста метод аннотированного суффиксного дерева выделяется тем, что он представляет текст не как последовательность слов, а как последовательность символов. Благодаря этому достигается практически полная независимость от языка анализируемых текстов. В основе данного метода лежит построение аннотированного суффиксного дерева(далее - АСД), с помощью которого можно определить степень вхождения исходных (данных) слов или словосочетаний в анализируемый текст. В моем исследовании использовалась эффективная и быстрая реализация АСД на основе суффиксных массивов [7]. В публикации [7] предлагает построение АСД, как корневого дерева, где все узлы, кроме корня помечены каким-либо символом из алфавита, на котором определена коллекция строк. В моем случае АСД кодирует все суффиксы всех строк, которые представлены в стоп-листе. Каждому узлу соответствует число, которое обозначает сколько раз данный фрагмент вошел в набор текстов. Пример данного дерева можно увидеть на рис. 1.

Рис. 5.2

5. Полученные результаты

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

Табл. 6.1.

Как видно из полученной таблицы, самым эффективным способом оказался способ АСД. Но у него есть существенный недостаток, который можно увидеть в приложении к данной работе. Данный метод выдает очень большое количество, так называемого "мусора", то есть слов, которые на самом деле не являются обесцененной лексикой. Но также у данного метода есть существенное преимущество над его ближайшим соседом (теоретико-множественная мера Жаккара), данный метод работает быстрее, чем его преследователь. Остальные методы работают очень точно, но и при этом очень не полно. Также следует отметить, что худшим методом, с точки зрения полноты оказался простой поиск по совпадению. Но у него также имеются преимущества. Например, очень существенным плюсом данного метода является то, что его точность максимальна, то есть, если он выдает слово, то оно обязательно входит в стоп-лист, то есть является обесцененной лексикой. Нельзя обойти стороной тот факт, что при применении метода "Расстояние Левенштейна" было проверено лишь треть коллекции данных. Это было сделано из-за того, что данный метод работает очень долго. На основе проверенных статей можно сделать вывод, что его полнота близка к полноте метода "теоретико-множественная мера Жаккара", но при этом, как было сказано ранее, данный метод слишком медлителен, экспериментально был сделан вывод о том, что данный метод не является лучшим.

В данном исследовании главным фактором сравнения методов будет являться полнота[5]. Введем формальное определение полноты. В данном исследование полнота - это количество нецензурных слов из статей, которые были найдены в ручную. Полнота всех методов рассчитывалась по формуле:

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

Необходимо найти все нецензурные слова в тексте, иначе очистка от нецензурной лексики не будет иметь смысла. Точность при этом менее важна: не так страшно, что несколько слов ошибочно будут признаны нецензурными. Пропустить же нецензурное слово гораздо хуже. Таким образом, главным критерием оптимизации в данной работе является полнота. Точность важна, но не настолько сильно. Приведем пример: первый способ работает очень точно, но при этом он выдает далеко не всю, а если быть откровенным, то максимум 50% от того, что на самом деле содержит статья. При этом в моем исследовании есть 4 достаточно полных метода.

Другим немаловажным критерием для сравнения методов является время работы. Допустим, что разрабатывается некий онлайн-сервис для очистки текстов от нецензурной лексики. Его эффективность и польза от него получаемая напрямую зависит от скорости его работы. Два из рассмотренных методов, теоретико-множественная мера Жаккара и стемминг, работают быстро, а один, расстояние Левенштейна, хоть он и полный, но времени затрачивает очень много. В результате этих суждений нужно можно сделать вывод о том, что самым эффективным и при этом, что не мало важно, самым быстрым методом оказался метод АСД.

6. Программная реализация

Все методы за исключением одного (метода АСД) реализованные в данной работе были написаны с помощью языка программирования Python 3.4.3. Этот язык был выбран вследствие того, что он является одним из самых удобных при обработке или работе с текстовыми файлами. Также одним из критериев выбора данной платформы было то, что в ней реализованы библиотеки, которые были необходимы для выполнения данного исследования. Приведем пример схемы работы программы, реализованной для простого поиска по совпадению. На вход подается стоп-лист и статья, в которой должна быть найдена ненормативная лексика. Далее нужно сравнить каждое слово из статьи с каждым словом из стоп-листа, если они при этом совпадают, отметить совпадающее слово в статье определенными тегами, чтобы зафиксировать его "ненормативность". Лемматизация и Стеммер работают по тому же принципу, за исключением того, что на начальном этапе статья подвергается форматированию, с использование стандартной библиотеки Python 3.4.3 (pymystem3) в случае метода лемматизации и с использованием библиотеки, созданной моим научным руководителем, в случае стемминга. Также, стоит отметить то, что в случае стемминга необходимо "отстеммить" стоп-лист, чтобы сравнение слов из статьи и стоп-листа происходило правильно. В случае лемматизации в этом нет необходимости, так как слова в стоп-листе написаны в своей словарной форме. Способ "расстояние Левенштейна" и "теоретико-множественная мера Жаккара" также использовали сравнение каждого слова из статьи с каждым словом из стоп-листа, но после сравнения применялись формулы и действия, которые описаны выше, чтобы определить подходит слово под определение нецензурной лексики или нет.

Единственный метод, который реализовывался с помощью языка программирования Python 2.7.9 - это метод АСД. Это делалось из-за того, что библиотека, которая понадобилась для реализации данного метода (east.asts), была реализована только для этой версии. Данная библиотека была применена к каждому слову из стоп-листа, то есть определенным образом каждое слово было разбито на суффиксы (см. рис.5.2) Далее считался результат опять же с использованием данной библиотеки и если этот результат был выше определенного порога, в моем случае это 10% (такой маленький процент брался специально для полноты метода) слово отбиралось для дальнейшего анализа.

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

Заключение

В данной работе проводится сравнение эффективности 6 методов поиска по однословному запросу. В качестве запроса выступает слов из стоп-листа - списка нецензурных слов, запрещенных для использование в СМИ РФ. Поиск осуществляется в коллекции текстов с сайта lurkmore, изобилующих нецензурной лексикой. Главная цель поиска - найти все нецензурные слова, однако, в отличии от традиционной постановки задачи поиска по запросу, главной мерой качества в данной задаче является полнота, а не точность. Важна также скорость работы алгоритма. В работе сравниваются 6 различных моделей поиска: простой поиск по совпадению, поиск по нормальной форме, поиск по стему - основе слова, поиск с помощью оценки сходства по мере Жаккара на биграммах, по мере Левенштейна, по мере, основанной на аннотированных суффиксных деревьях. удаление нецензурный текст программный

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

Некоторые трудности при проведении исследования были связаны с недостаточным объемом данным: несмотря на неоспоримую актуальность задачи, у нас не получилось найти размеченных коллекций текстов, поэтому, пришлось размечать небольшое количество текстов в ручную.

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

Список использованной литературы

1. Chandrinos K. V. et al. Automatic web rating: Filtering obscene content on the web //Research and Advanced Technology for Digital Libraries. - Springer Berlin Heidelberg, 2000. - С. 403-406.

Wilcox W. Method and system for filtering obscene content from electronic books and textualized media : заяв. пат. 13/167,241 США. - 2011.

Солдатова Г. У., Рассказова Е. И. Как им помочь //Ребенок в интернете: запрещать, наблюдать или объяснять. - 2012. - С. 26-33.

2. Cheetham A. H., Hazel J. E. Binary (presence-absence) similarity coefficients //Journal of Paleontology. - 1969. - С. 1130-1136.

3. Gomaa W. H., Fahmy A. A. A survey of text similarity approaches //International Journal of Computer Applications. - 2013. - Т. 68. - №. 13.

4. Manning C. D., Schьtze H. Foundations of statistical natural language processing. - Cambridge : MIT press, 1999. - Т. 999.

5. Mirkin B. Core concepts in data analysis: summarization, correlation and visualization. - Springer Science & Business Media, 2011.

6. Porter M. F. An algorithm for suffix stripping //Program. - 1980. - Т. 14. - №. 3. - С. 130-137

7. Дубов М., Черняк Е. Аннотированные суффиксные деревья: особенности реализации //Foresight. - 2013.

Миркин Б. Г., Черняк Е. Л., Чугунова О. Н. Метод аннотированного суффиксного дерева для оценки степени вхождения строк в текстовые документы //Бизнес-информатика. - 2012. - №. 3 (21).

Размещено на Allbest.ru