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

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

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

Методы классификации текстов и определения качества контента

Л.М. Ермакова

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

Ключевые слова: классификация текстов; ранжирование; контент; поисковый спам; поисковая оптимизация.

Введение^{© Л. М. Ермакова, 2011}

По мнению некоторых философов, "следующей после языка и письменности ступенью развития коммуникаций является формирование коммуникационной сети Интернета" [1]. Каждый год объем информации увеличивается в среднем на 30% [1]. Поэтому одной из ключевых задач современного мира является систематизация информации, в т. ч. в Интернете. Поисковая система (search engine) представляет собой систему информационного поиска, предназначенную для поиска информации, хранящейся в компьютерных системах.

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

1.  Понятие классификации документов

Классификация (категоризация, рубрикация) документов (text categorization, text classification, topic spotting) - одна из задач информационного поиска, заключающаяся в отнесении документа к одной из нескольких категорий на основании содержания документа.

Не следует отождествлять классификацию и кластеризацию.

Основным отличием категоризации от кластеризации является то, что рубрики заранее задаются пользователем или экспертом, а кластеры формируются автоматически при анализе коллекции [3].

Классификация документов широко применяется в таких областях, как системы документооборота, фильтрация текстов (например спама), автоматическое аннотирование и реферирование, машинный перевод, составление интернет-каталогов, ограничение области поиска в поисковых системах, определение кодировки и языка текста, классификация новостей и т.д. [3-5].

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

Задача классификации текстов появилась в 1960-х гг. прошлого века, но только в начале 1990-х гг. она стала широко применяться в информационном поиске [4].

Классификация на основе правил широко применялась до начала 1990-х гг. [4]. В соответствии с правилами, написанными экспертами, документ относился к той или иной категории. Часто правила имели форму регулярных выражений. Таким образом, от эксперта требовалось не только знание предметной области, но и навыки написания правил.

Этот подход в некоторых случаях превосходит по точности другие методы, однако для поддержания базы правил в актуальном состоянии необходима постоянная работа эксперта, поэтому в 90-х гг. правила сменились машинным обучением [4].

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

Приведем формальную постановку задачи классификации. Пусть дано конечное множество категорий и конечное множество документов . Целевая функция Ф:, которая для каждой пары <документ, категория> определяет, соответствуют ли они друг другу, не известна. Необходимо найти классификатор Ф^', т.е. функцию, максимально близкую к функции Ф [3]. Если даны две непересекающиеся категории, говорят о бинарной классификации. Разработанный аппарат бинарной классификации широко представлен в фильтрации спама.

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

Автоматической классификации предшествует этап индексирования документов. Индексация - это процесс приведения документа к единому формату. Индексирование включает в себя построение модели документа и уменьшение размерности. Наиболее распространенными моделями документов являются варианты моделей множества слов (bag-of-words), а именно бинарная модель и модель с весами терминов. Бинарная модель учитывает только наличие или отсутствие слова в документе, во взвешенной же модели каждому термину ставится в соответствие его вес.

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

Для выбора признаков существует два противоположных подхода: добавление подходящих признаков и удаление лишних.

Обычно алгоритмы выбора признаков работают по следующей схеме:

1. Для каждого термина вычисляется мера различия между классами.

2. Термины сортируются в порядке убывания этой величины.

3. Выбираются лучшие признаки.

В зависимости от результата различают два типа классификации:

ь Точная, т.е. документ однозначно относится к той или иной категории Ф':.

ь Ранжированная, если документ относится к категории с некоторой вероятностью Ф':.

2. Алгоритмы классификации

Простейшим классификатором является метод ближнего соседа (Nearest Neighbor Classifier). Объект присваивается тому классу, который является наиболее распространенным среди соседей данного элемента. Соседи берутся исходя из множества объектов, классы которых уже известны.

Метод максимальной энтропии (Maximum Entropy) предусматривает распределение, наиболее близкое к равномерному. На основе обучающей выборки формируется множество ограничений модели. Ограничения представляются как ожидаемые значения признаков [5].

Метод Роччио применяется в линейных классификаторах, представляющих документ в виде весов терминов. Профайл , т.е. список взвешенных терминов, отличающих одну категорию от другой, рассчитывается по формуле

,

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

Деревья решений представляют собой следующий алгоритм:

1) выбирается термин;

2) документы, содержащие этот термин, кладутся слева, не содержащие - справа;

3) выбирается новый термин и все повторяется.

Термины можно выбирать исходя из коэффициента полезности [3].

Линейный online классификатор рассчитывается по формуле

или

Обучение можно проводить за пределами обучающей выборки при наличии обратной связи.

Алгоритм выбора координат :

1. Выбирается тривиальный вектор .

2. При неудаче в координаты категории, соответствующей терминам неправильно определенного документа, прибавляется заранее выбранная положительная константа, если полученное значение меньше целевого; в случае, если больше целевого; , вычитается, в общем случае, иное положительное число позволяет сделать вывод о значимости термина для классификации. Линейный online классификатор допускает модификацию поправок:

· Мультипликативные поправки (умножать на константу или ).

· Поправки при удачной классификации.

· Поправки неактивных терминов (например, пропорционально увеличивать координаты используемых терминов и уменьшать координаты неиспользуемых).

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

1. Матрица документов размера | где строка - документ, а столбец - термин.

2. Матрица ответов размера | где строка - документ, столбец - категория, а пересечение i-ой строки и j-го столбца - значение.

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

Алгоритм нахождения M:

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

2. Разложить полученную проекцию по базису столбцов .

3. Это разложение и будет вектором , характеризующим данную категорию.

ДНФ-классификатор является системой правил вида

ДНФ - дизъюнктивная нормальная формула.

Для каждой категории, состоящей из документов , выписывается формула

ДНФ-классификатор правильно работает на обучающей выборке, но не применим для других наборов. Кроме того, длина правил слишком велика.

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

Метод опорных векторов (SVM - support vector machines) - это набор схожих алгоритмов на основе обучения с учителем, применяющийся для анализа данных и распознавания образов в задачах классификации и регрессионном анализе. SVM является линейным классификатором. На основе обучающей выборки алгоритм помогает предсказать, в какую из двух заранее заданных категорий попадает элемент, подлежащий классификации.

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

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

· Простое большинство: выбираем результат, полученный большинством методов.

· Взвешенная линейная комбинация (степень доверия классификатору).

· Динамический выбор классификатора (для каждого классификатора выбираются категории, где он наиболее надежен).

· Динамическая комбинация классификаторов (в зависимости от категории определяется степень доверия классификатору) [3].

Существует четыре основных критерия для оценки классификаторов:

1) точность (проверяется сравнением классификации, проведенной человеком и компьютером);

2) скорость и масштабируемость в пакетном режиме;

3) простота, скорость и масштабируемость при добавлении / удалении / изменении документа, а также при переносе большого числа документов из одного класса в другой;

4) простота диагностики, интерпретации результатов и обратной связи.

В зависимости от задачи документ может быть отнесен к одному классу или некоторому подмножеству классов [5].

3. Определение качества контента

Основной задачей поисковой машины является предоставление качественных результатов, т.е. наиболее важных релевантных страниц [2].

Компания "Яндекс" дает следующее определение поискового спама:

Поисковый спам -- это попытки обмана поисковой системы и манипулирования ее результатами с целью завышения позиции сайтов (страниц) в результатах поиска [6].

Поисковый спам можно разделить на две категории: контентный и ссылочный спам [2].

3.1 Контентный спам

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

Спамеры могут попытаться сделать страницу релевантной для многих запросов, включив большое число различных терминов в документ, или повысить релевантность при помощи увеличения количества вхождений ключевых слов [2]. Однако современные поисковые системы умеют определять подобный вид спама и снижают рейтинг, если плотность встречаемости ключевых слов превышает "нормальную" [7].

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

Иногда спамеры копируют тексты, например новости, с других сайтов [2]. Но многие поисковики стараются не индексировать "сайты, копирующие или переписывающие информацию с других ресурсов и не создающие оригинального контента" [7]. Текст может копироваться не полностью, а по предложениям [2]. Спамеры могут вводить невидимый текст с единственной целью манипуляции поисковой системой. Также распространенным приемом является использования дорвеев. Дорвеи (doorway, portal pages, jump pages, gateway pages, entry pages) - страницы, содержащие ключевые слова, предназ-наченные для поисковиков, и перенаправляющие пользователей на другие страницы. Простейший способ - создание отдельных страниц на каждый запрос.

Следующий уровень - создание дорвеев, которые индексируются поисковиками, но не отображаются в браузерах. Третий метод - клоакинг (cloaking): поисковые машины и пользователи видят разный контент [8]. Поисковые машины также определяют редирект и обычно индексируют только ту страницу, куда был переадресован пользователь [9]. Еще один вид недобросовестной оптимизации - свопинг (code swapping) - замена или значительное изменение контента, когда нужное положение страницы в индексе уже достигнуто [9].

Активно разрабатываются методы обнаружения автоматически сгенерированного контента. Одни из первых алгоритмов для фильтрации поискового спама были основаны на эвристиках: анализ гиперссылок, DNS, автоматическая кластеризация документов и выявление практически одинаковых страниц [10]. Предлагались статистические методы обнаружения массовых текстов: количество слов на странице (эффективно, если спамеры пытаются увеличить покрытие запросов), количество слов в заголовке, средняя длина слова (метод нацелен на запросы, в которых ключевые слова не разделены пробелами), анализ отображаемого текста гиперссылок (применяется для страниц, цель которых поднять релевантность других страниц), доля отображаемого текста по отношению ко всему контенту, определение меры избыточности страниц на основе шинглов или коэффициента сжатия, доля стоп-слов, условное и безусловное n-граммное сходство, анализ частей речи (Corleon), использование General Inquirer (относит текст к одной из 182 категорий) [10]. Из машинного перевода пришли методы сравнения языковых моделей, т.е. вероятности встречаемости строки в языке [11]. Если некоторые страницы уже были помечены как спам, можно выявить похожие на них страницы. Помимо лингвистических подходов, применяется также анализ оформления страниц. Этот метод опирается на предположение, что страницы генерируются по одним и тем же шаблонам [12].

Широкое распространение получили методы генерации текстов на основе цепей Маркова. Поскольку подобные генераторы обучаются на выборках на естественном языке, для подобного спама не применимы методы, опирающиеся на "неестественность" последовательности слов. Однако современные генераторы не могут обеспечить полную связность текста и стилистическое единство, что может быть применено для выявления спама [13]. контентный ссылочный спам страница

Многие поисковые системы умеют распознавать неуникальный контент [6, 7]. Поэтому последнее время широкое распространение получили такие методы поисковой оптимизации (search engine optimization), как рерайтинг (rewriting) и копирайтинг (copywriting) (article spinning).

3.2 Ссылочный спам

Существует два основных алгоритма, рассчитывающих рейтинг страницы на основе ссылок: HITS и PageRank [2].

HITS-алгоритм (Hyperlink-Induced Topic Search), или алгоритм Клейнберга, ранжирует страницы в зависимости от темы [14]. Значимость страницы-первоисточника (authority) рассчитывается как сумма весов страниц-посредников (hub), указывающих на нее, а вес страницы-посредника, в свою очередь, - как сумма значений весов страницы-перво-источника, ссылки на которые она содержит [14]. Hub-рейтинг можно легко увеличить, добавив ссылки на "хорошие" страницы. Authority-рейтинг можно поднять за счет исходящих ссылок со страниц, имеющих высокий hub-рейтинг. Кроме того, можно добавлять ссылки на блоги, форумы и т.д., т.е. на страницы, содержание которых спамер может модифицировать [2].

PageRank исходит из предположения, что количество ссылок на страницу отражает популярность этой страницы среди пользователей [15]. Для манипуляции этим алгоритмом спамеры используют так называемые линкофермы (фермы ссылок, линкфармы, link farm) - "фермы" для разведения ссылок. При этом группа веб-сайтов содержит ссылки на другие сайты в группе. Обычно эти сайты не несут полезного контента, а созданы для увеличения индекса цитирования другого сайта путем размещения ссылок на него. Привлечение пользователей на подобные сайты может осуществляться копированием "полезного" контента с чужих страниц [2].

Наличие на веб-странице большого количества внешних гиперссылок и малое количество или полное отсутствие внутрен-них гиперссылок может быть сочтено за ссылочный спам [9].

Существуют компании, занимающиеся продвижением сайтов, как "белым", так и "черным". Можно встретить объявления о покупке ссылок со страниц с релевантным текстом, возможности генерации текстов статей по шаблонам, пакетной загрузки уникализированных статей, автоматической уникализации текстов статей и т.д. (см. http://www.seozavr.ru/).

Современные алгоритмы обнаружения ссылочного спама опираются на такие признаки, как наличие определенных слов в окрестности ссылки, наличие блоков ссылок, ссылки на рекламных брокеров, отсутствие тематической близости между ссылкой и контентом страницы или соседними ссылками, анализ местоположения ссылки, наличие идентичных по коду ссылок, изменение ссылок без изменения основного содержания страницы и т.д. [16].

Выводы

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

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

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

Список литературы

1. Миронов В.В. Современные философские проблемы естественных, технических и соци-ально-гуманитарных наук. Гардарики, 2007.

2. Gyцngyi Z. Garcia-Molina H. Web spam taxonomy. 2005.

3. Лифшиц Ю. Классификация текстов Алго-ритмы для Интернета. 2005. URL: http://yury.name/internet/

4. Sebastiani Fabrizio. Machine learning in automated text categorization Journal ACM Computing Surveys. 2002. Vol. 34, 1.

5. Chakrabarti S. Mining the Web: Discovering Knowledge from Hypertext Data. 2003.

6. Лицензия на использование поисковой системы Яндекса. Компания Яндекс 1997-2011. URL: http://company.yandex.ru/legal/termsofuse/

7. Советы вебмастеру. Компания Яндекс 1997-2011. URL: http://help.yandex.ru/webmaster/id=

995298#995342.

8. Sew S. What Are Doorway Pages? Search Engine Watch 2007. URL:

http://searchenginewatch.com/article/2048653

/What-Are-Doorway-Pages.

9. Виды поискового спама ANTULA. URL: http://www.antula.ru/rang-search_spam2.htm

10. Ntoulas A., Manasse M. Detecting spam web pages through content analysis In Proceedings of the World Wide Web conference. 2006.

11. Mishne G., Carmel D. and Lempel R. Blocking blog spam with language model disagreement In Proceedings of the First International Workshop on Adversarial Infor-mation Retrieval on the Web. 2005.

12. Urvoy T., Chauveau E., Filoche P. Tracking Web Spam with HTML Style Similarities ACM Transactions on the Web. 2006.

13. Павлов А.С., Добров Б.В. Метод опреде-ления массово порождаемых неестествен-ных текстов // Компьютерная лингвистика и интеллектуальные технологии. 2010.

14. Kleinberg J. Authoritative Sources in a Hyperlin-ked Environment Journal of the ACM 46. 1999. 5.

15. Page L., Brin S., Motwani R., Winograd T. The PageRank citation ranking: Bringing order to the web. Technical report: Stanford University. 1998.

16. Шарапов Р.В., Шарапова Е.В. Алгоритм

обнаружения ссылочного спама // Компью-терная лингвистика и интеллектуальные технологии: по материалам ежегодной междунар. конф. "Диалог 2009". 2009.

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