Программа для иерархической классификации веб-сайтов

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

[Введите текст]

Основные определения, термины и сокращения

Cross-validation - процедура оценивания обобщающей способности алгоритмов машинного обучения;

TF-IDF (Term Frequency - Inverted Document Frequency) - статистическая мера, используемая для оценки важности слова в контексте документа, являющегося частью коллекции документов;

URL (Uniform Resource Locator) -полный путь к размещению ресурса в сети интернет, содержит доменное имя; может содержать путь к конкретной странице или файлу;

Web Mining - применение методов и алгоритмов интеллектуального анализа данных для обнаружения и поиска зависимостей и знаний в сети Интернет;

Ансамбль классификаторов - набор классификаторов применяемых совместно для решения одной задачи классификации;

Дерево - структура данных, эмулирующая древовидную структуру в виде набора связанных узлов. Является связным графом, не содержащим циклы;

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

Обучающая выборка - конечное множество объектов (примеров), для которых известна их принадлежность к тем или иным классам;

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

Стемминг - это процесс нахождения основы слова для заданного исходного слова;

СУБД - система управления базами данных

Тег - элемент языка разметки гипертекста;

Токенизация - выделение слов и границ предложений;

Функция высшего порядка - функция, принимающая в качестве аргумента другие функции;

Шум (шумовой объект, шумовой выброс) - объект, признаковое описание которого аномально отличается от типичного объекта того же класса.



Введение

сайт данные качество валидация

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

Задача иерархической классификации веб-сайтов находится на стыке таких дисциплин как web mining, машинное обучение и обработка естественного языка. В рамках этих дисциплин существуют более популярные и хорошо изученные задачи классификации текстов (в том числе иерархической) и веб-страниц [1] [2] [3] [4] [5]. Однако, несмотря на близость упомянутых задач, иерархическая классификация веб-сайтов имеет ряд особенностей, затрудняющих использование существующих решений в схожих задачах и требующих разработки новых методов для достижения приемлемого качества классификации.

Веб-страницы обладают четкой структурой и гиперссылками, а также специфическим содержанием - элементами управления, навигации, оформления. Такие элементы могут свидетельствовать о важности содержимого каких-либо элементов (например, текст, выделенный жирным шрифтом) или указывать путь к дополнительной информации (гиперссылки). Данные, заключенные в мета теги зачастую гораздо важнее для понимания назначения сайта или страницы, чем информация из других разделов. Однако значительная часть работ в этой области [1] [3] [6] [7] применяет популярные методы из области обработки естественного языка для классификации веб-страниц. Чаще всего в таких случаях страница очищается от всех автоматически сгенерированных элементов (текст разметки, javascript код) и к оставшимся словам применяется метод TF-IDF [8] для оценки важности этих слов и представлении документа (веб-страницы) в виде числового вектора. Недостатки такого подхода в том, что расположение данных на странице, их форматирование и параметры отображения полностью игнорируются. Таким образом, текст рекламного объявления может зачастую получить больший вес, чем текст из мета тега описания страницы.

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

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

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

Отдельный раздел работы посвящен классификации в условиях наличия иерархии категорий. В общем случае, иерархическая модель данных в задачах классификации подразумевает древовидную структуру хранения данных. Однако существуют некоторые различия в правилах, по которым производится классификация. Так, документы в коллекции могут быть организованы как дерево или как ориентированный ациклический граф (например, каталог Yahoo [11]). Каждая категория в обоих случаях может принадлежать только к одной родительской категории (категории верхнего уровня в иерархии) [12] или ко многим родительским категориям [11]. Более того, документы в коллекции могут принадлежать только конечным категориям в иерархии (категориям самого низкого уровня) [12] или они также могут принадлежать и внутренним категориям [13]. Большинство работ в этой области [12] [14] [4] [5] посвящены классификации в условиях, когда объекту классификации может быть присвоена только одна конечная категория.

В силу того, что в качестве обучающего набора данных выбран Яндекс.Каталог [15] в данной работе полагается, что структурой данных коллекции является дерево, каждая категория может принадлежать ко многим родительским категориям, а также допускается принадлежность документов в коллекции к внутренним категориям. Это придает задаче дополнительную сложность, в первую очередь за счет многозначности (политематичености) классификации. Например, сайт habrahabr.ru в Яндекс.Каталоге может принадлежать категориям «Интернет» и «Социальные сети», которые находятся на одном уровне в иерархии [16]. Тот факт, что документ в коллекции может принадлежать не только концевым, но и родительским категориям также затрудняет использование уже существующих алгоритмов иерархической классификации.

На данный момент существует два основных подхода к решению задачи иерархической классификации: плоский (flat) и поэтапный (level based) [17]. Плоский подход предполагает обучение одного классификатора для всех классов [13] [14]. При таком подходе устройство иерархии игнорируется, для классификатора все классы находятся на одном уровне, классификация производится один раз. Поэтапный подход предполагает обучения отдельных классификаторов для каждого уровня в иерархии [12] [18] [19]. В общем случае, сложно сказать о том, какой из подходов лучше - у каждого из них есть свои преимущества и недостатки, которые будут подробно рассмотрены далее. В данной работе предполагается создание ансамбля классификаторов, который бы объединял в себе оба подхода для достижения наилучшего качества классификации.

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

Создать и предварительно обработать обучающую выборку на основе данных Яндекс.Каталога

Изучить различные методы и алгоритмы в области классификации веб-сайтов и иерархической классификации;

Разработать модуль загрузки и отбора необходимой информации о веб-сайте;

Разработать модуль для построения признакового описания веб-сайта с учетом структуры и параметров форматирования веб-страниц;

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

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

Разработать техническую документацию.

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

В приложениях 1-3 приведена документация к программе по ГОСТ: техническое задание, руководство оператора, программа и методика испытаний.



1. Получение и обработка данных о веб-сайте

1.1 Получение данных

В Яндекс.Каталоге веб-сайт представлен названием его домена или поддомена, URL адресом, его кратким описанием, индексом цитирования, тематикой, регионом и адресом в каталоге. Таким образом, имея адрес главной страницы веб-сайта необходимо собрать достаточно полную информацию о сайте, которая бы в то же время не навредила качеству классификации. Как это уже упоминалось, многие исследователи классифицируют сайт, используя только его главную страницу, сводя, таким образом, задачу к задаче классификации веб-страниц. Однако в ряде работ в этой области [20] [21] демонстрируется, что использование информации доступной по гиперссылкам с главной страницы может увеличивать качество классификации. При этом отмечается, что такой подход следует использовать с осторожностью из-за высокой вероятности «зашумленности» таких страниц, наличия информации, не относящейся к тематике сайта. После проведения ряда экспериментов было установлено, что наибольшая эффективность достигается при извлечении информации только из мета тегов со страниц того же сайта, доступных по гиперссылкам, и всей доступной информации с главной страницы.

1.2 Предварительная обработка данных

Загруженные данные о сайте в дальнейшем хранятся в двух вариантах - сырые, с сохранением всего содержимого загруженных веб-страниц, и предварительно обработанные. Второй вариант предполагает очистку страницы от всех элементов разметки, javascript кода и прочего автоматически сгенерированного содержимого. Также производится удаление рекламных элементов, в разметке которых содержатся ссылки на популярные системы рекламной аналитики, такие как «ad.yandex.ru», «adsense», «adserver», «adsys-tem», «adsale», «openx». Далее производится токенизация оставшихся слов, удаление стоп-слов (предлоги, междометия, причастия, частицы), ссылок и пунктуации.

Последним шагом в обработке веб-страницы является стемминг. Одним из самых распространенных алгоритмов стемминга является алгоритм Портера, опубликованный Мартином Портером в 1980 году [22]. Основной идеей алгоритма является отсечение суффиксов и окончаний для достижения основной формы слова. Алгоритм не задействуют каких-либо баз основ слов и ориентируется на особенности языка. Реализация алгоритма Портера для русского и некоторых других языков носит название SnowballStemmer [23].



2. Формирование признаков

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

Как уже упоминалось ранее, одним из самых популярных методов для представления документов в признаковом пространстве является TF-IDF (Term Frequency - Inverted Document Frequency) [8]. Основная идея метода заключается в том, что чем чаще слово встречается в документе, и чем реже оно встречается в других документах, тем более важным оно является для оцениваемого документа. Более формально мера TF-IDF определяется следующим образом:

,

где - частота встречи слова в документе , а - обратная частота встречи слова в документах коллекции D.

Каждый документ в коллекции представляется вектором, где - вектор, соответствующий i-ому документу, - вес j-ого слова в i-ом документе, а n - общее количество уникальных слов в коллекции.

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

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

При использовании предложенного метода вес W i-ого слова на k-ом сайте вычисляется следующим образом:

где это количество сайтов в коллекции, в которых встречается i-ое слово, N - общее количество сайтов в выборке, а вычисляется как:



где T - множество всех тегов сайта , это частота встречи i-ого слова в теге сайта , а в свою очередь вычисляется как:

Далее каждый сайт представляется вектором , где - вес j-ого слова в i-ом сайте, а n - общее количество уникальных слов во всех сайтах коллекции, полученных после проведения полного цикла предобработки. Так осуществляется представление сайта в признаковом пространстве.



3. Иерархическая классификация

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

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

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

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

3.1 Алгоритмы машинного обучения

Машина опорных векторов

В задачах классификации текстов и веб-страниц широкое распространение получил алгоритм машины опорных векторов (SVM) [25]. Основной идеей алгоритма является построение оптимальной разделяющей гиперплоскости в пространстве признакового описания по обучающей выборке.

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

Решающие деревья

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

Рисунок 1 - Пример решающего дерева. [27]

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

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

3.2 Иерархическая классификация

На данный момент существует два основных подхода к решению задачи иерархической классификации: плоский (flat) и поэтапный (level based) [17]. Плоский подход предполагает обучение одного классификатора для всех классов [13] [14]. При таком подходе иерархическая организация категорий и связи между ними игнорируются - для классификатора все категории находятся на одном уровне. Классификация производится в один шаг для всех категорий. Поэтапный подход предполагает обучения отдельных классификаторов для каждого уровня в иерархии [12] [18] [19]. Оба подхода имеют свои существенные недостатки.

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

Основной недостаток плоского классификатора заключается в том, что признаковые описания объектов, находящихся на разных уровнях категории могут быть очень похожи (например, в случае с категорией «Hi-tech/Сети и связь» и ее дочерней категорией «Hi-tech/Сети и связь/Устройство сетей»). В таких ситуациях вероятность ошибки плоского классификатора весьма высока. Другой недостаток плоского подхода заключается в необходимости переобучать весь классификатор даже при небольшом изменении в структуре иерархии, что зачастую требует довольно много ресурсов, т.к. плоская модель классификации обучается на всей выборке целиком.

По условиям задачи сайт может быть отнесен более чем к одной категории, включая родительские. Такое условие придает задаче дополнительную сложность. Большинство упомянутых исследований в этой области [12] [14] [4] [5] посвящены решению задач в более простых условиях - однозначной классификации сайта (может быть отнесен только к одной категории) и отнесения сайта только к концевым категориям. Но даже в таких условиях результаты работы различных существующих решений могли оказаться неудовлетворительными. Это свидетельствует о необходимости разработки нового подхода к решению данной задачи.

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



3.3 Построение ансамбля классификаторов

Поэтапный ансамбль классификаторов

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

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

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

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

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

Иными словами, если вероятность принадлежности объекта текущей и родительским категориям больше вероятности принадлежности к детям текущей категории, то объект остается в текущей категории и наоборот.

Такой подход позволяет уменьшить вероятность отдаления объекта от его истинной категории.

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

Плоские классификаторы

Бэггинг и лес решающих деревьев

Бэггинг - это метод объединения различных классификаторов в один ансамбль, где все классификаторы работают независимо друг от друга. При применении этого метода классификаторы могут обучаться на различных подвыборках, различных подпространствах признаков или использовать различные алгоритмы классификации. Результат классификации определяется путем голосования. Чаще всего используется принцип простого большинства, который присваивает объекту метку того класса, за который проголосовало большинство алгоритмов [28].

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

Плоский классификатор на основе SVM

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

Все рассмотренные модели классификации объединяются в единую модель с помощью простого голосования - для каждой категории решение о присвоении объекту текущей категории принимается большинством голосов.

Подход с объединением различных классификаторов в один ансамбль обладает следующими достоинствами:

недостатки одних подходов к классификации компенсируются за счет других;

ошибка каждого из базовых классификаторов в ансамбле усредняется, что делает ансамбль более устойчивым к случайностям и шуму;

множество возможных гипотез ансамбля расширяется за счет комбинирования гипотез базовых классификаторов, что увеличивает обобщающую способность ансамбля;

снижается риск переобучения за счет независимой работы моделей в ансамбле;

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

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



4. Оценка качества работы модели

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

4.1 Метрики оценки качества

Полная точность (accuracy)

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

Точность, полнота и F-мера

Такие метрики, как точность (precision) и полнота (recall) впервые получили широкое распространение в оценке качества работы систем решающих задачу информационного поиска. Точность системы в пределах одного класса представляет собой долю объектов действительно принадлежащих определенному классу относительно всех объектов отнесенных системой к этому классу. Полнота выражается как доля найденных классификатором объектов принадлежащих классу относительно всех объектов этого класса [29]. Таблица 4 представляет собой таблицу сопряженности отдельного класса, где TP (true positive) - истинно-положительное решение, TN (true negative) - истинно-отрицательное решение, FP (false positive) - ложно-положительное решение и FN (false negative) - ложно-отрицательное решение.

Таблица 1 - Таблица сопряженности класса объектов

	Экспертная оценка (действительные значения класса контрольной выборки)
	Положительная	Отрицательная
Оценка системы	Положительная	TP	FP
	Отрицательная	FN	TN

Таким образом, точность и полнота вычисляются как:

F-мера объединяет в себе информацию о точности и полноте оцениваемого алгоритма. Вычисляется она как гармонические среднее показателей точности и полноты:

В силу того, что F-мера вычисляется отдельно для каждого класса ее удобно использовать для поиска и анализа конкретных ошибок алгоритма, для оценки классификации с несколькими классами. При этом в случае большого числа классов необходима характеристика, которая бы агрегировала полноту и точность по всем классам и характеризовала бы общее поведение системы. В данной работе для этой цели применяется следующие агрегированные величины: макро точность (macro precision), которая вычисляется как среднее арифметическое значения точности по всем классам, макро полнотой (macro recall), которая вычисляется как среднее арифметическое значение полноты по всем классам и макро F-мера (Macro F-score), которая является гармоническим средним между ними [30].

4.2 Кросс-валидация

Одним из наиболее распространенных методов для проведения полноценного тестирования и оценки качества работы различных алгоритмов машинного обучения, является скользящий контроль (cross-validation). Для независимой выборки данный метод позволяет получить несмещенную оценку вероятности ошибки в отличие от средней ошибки на обучаемой выборке, которая может являться смещенной оценкой вероятности ошибки из-за переобучения алгоритма [28]. Другим достоинством данной процедуры является способность получения оценки вероятности ошибки алгоритма, при отсутствии специально разработанной для тестирования контрольной выборки.

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

,



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

Метод получения оценки скользящего контроля заключается в многократном разбиении общей выборки на две непересекающиеся подвыборки , где - обучающая подвыборка длины , - тестовая подвыборка длины , где - номер разбиения. Для каждого из разбиений выполняется построение алгоритма и вычисление значения функционала качества алгоритма . Тогда оценка скользящего контроля вычисляется следующим образом [28]:

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



5. Разработка программы

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

5.1 Структура программы

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

Модуль download предназначен для загрузки веб-сайтов. Взаимодействие с базой данных и сериализация объектов программы производится в модуле db. В модуле feature_extraction реализованы алгоритмы формирования признаков (а именно TF-IDF и Tag Weighting) по собранным с веб-сайта страницам, а также методы предобработки веб-страниц. Модуль classifier содержит класс-оболочку для использования различных моделей классификации. В модуле hierarchical_classification реализовано управлением иерархической классификации с помощью различных моделей. Сами модели находятся в модулях level_based_classifier (реализация поэтапного классификатора) и ova_flat_clf (реализация плоского классификатора). Модуль preprocessing содержит различные методы предобработки обучающей выборки и данных полученных после загрузки веб-сайтов. Модуль tree описывает классы и структуры необходимые для хранения дерева. Тестирование и оценка качества работы модели реализованы в модуле evaluation. Алгоритм жадного поиска для оптимизации гиперпараметров модели находится в модуле grid_search. Анализ обучающей выборке и вывод статистики по ней реализован в модуле analyze_dataset.

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

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

5.2 Инструменты разработки

Программа написана на языке Python 2.7. Выбор этого языка обосновывается наличием широкого набора встроенных инструментов для реализации математических функций, полезных библиотек для решения задач в области анализа данных, а также высокой скоростью разработки. В качестве средств разработки была выбрана среда PyCharm Professional Edition 2016.1.3.

Программа тесно взаимодействует с базой данных MySQL, которая является одной из самых популярных систем управления реляционными базами данных. Данная СУБД является свободно распространяемым программным обеспечением, а также известна своей простотой администрирования и гибкостью в настройках. Благодаря своему широкому распространению MySQL хорошо документирована и обладает большим и развитым сообществом. Основные минусы данной СУБД: MySQL не поддерживает последние стандартны SQL (SQL-98, SQL-2003, SQL-2011) [31], ограниченный функционал различных движков (storage engine) MySQL, ряд архитектурных ограничений [32]. Для взаимодействия с базой данных используется библиотека MySQLdb [33].

Для операций с массивами данных (в частности, с обучающей выборкой) используется библиотека pandas. Основными преимуществами данной библиотеки являются эффективные операции над массивами данных, хранение массива данных в виде структурированной таблицы с индексированием, быстрое и удобное получение данных из файла или из базы данных. Библиотека написана на python и C [34].

Поскольку признаковое описание объекта в данной работе основано на частоте встречаемости слов в документах вектор, описывающий объект, будет иметь значительное количество нулей, даже в случае большой обучающей выборки. Это объясняется известным законом Ципфа, согласно которому при попытке упорядочить все слова языка по убыванию частоты их использования частота n-го слова в таком списке окажется приблизительно обратно пропорциональной его порядковому номеру n [35]. Из этого следует, что в большом корпусе документов большинство слов встречаются один раз. Поэтому для эффективного хранения признаковых описаний объектов следует использовать разреженную матрицу объекты-признаки. Поскольку в ходе обучения и классификации часто требуется получать признаковые описания объектов по индексу, разумным решением выглядит использование матрицы формата compressed sparse row, обеспечивающем быстрый доступ к строкам [36]. В программе используется ее реализация из библиотеки scipy - scipy.sparse.csr_matrix.

Для стемминга используется известная библиотека по работе с естественным языком nltk, для синтаксического разбора веб-страниц используется библиотека BeautifulSoup. Для реализации алгоритмов машинного обучения используется библиотека scikit-learn.

Благодаря использованию python и свободных библиотек написанных на python или на C, программа является кроссплатформенной и может работать как на операционных системах Windows, так и на Mac OS X и системах семейства *nix.



5.3 Параллельные вычисления

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

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

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

В языке python существуют различные способы для выполнения многопоточных и мультипроцессорных программ. Так, существует библиотека threading, реализующая все стандартные методы многопоточного программирования - различного рода блокировки, семафоры, события. Эта библиотека хорошо подходит для реализации асинхронных действий, однако при попытке увеличить быстродействие программы данная библиотека сталкивается с ограничением известным как GIL (Global Interpreter Lock) [37]. Основная идея GIL заключается в том, что в любой момент времени только один поток python может выполняться процессором. GIL позволяет однопоточным программам выполняться значительно быстрее и позволяет обеспечить определенную потокобезопасность, однако он ограничивает возможности и эффективность параллельных вычислений. Более того, из-за конкурирования потоков в попытке перехватить GIL выполнение однопоточной программы может быть значительно быстрее ее многопоточного аналога.

Из-за ограниченности многопоточного выполнения в python необходимо прибегнуть к мультипроцессорному выполнению. Для этого в языке python существует библиотека multiprocessing, которая позволяет обходить ограничение, накладываемое GIL, за счет использования подпроцессов вместо потоков. Таким образом, удается достичь значительной нагрузки на процессоры многоядерных компьютеров. При этом API библиотеки multiprocessing практически аналогично библиотеке threading, что облегчает переключение между ними.

5.4 Загрузка веб-сайтов

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

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

def download_urls(urls): # создаем директорию кеширующую загруженные страницы

if not os.path.exists(CACHE_DIRECTORY): os.makedirs(CACHE_DIRECTORY)

logging.info('cache downloaded directory created')

pool = Pool(multiprocessing.cpu_count())

bodies = pool.map(download, urls)

pool.close()

pool.join()

return bodies

В функции download_urls, принимающей на вход список УРЛ адресов, создается директория кеширующая загруженные страницы (если на момент вызова метода ее не существует). Далее создается объект Pool, в параметрах которого задается количество рабочих процессов в пуле. В данном случае этот параметр задается функцией multiprocessing.cpu_count(), возвращающей максимальное количество процессов, которое может быть запущено в данный момент. При вызове метода pool.map запускаются все рабочие процессы, которые параллельно выполняют функцию download для элементов из списка urls.

В функции download входящий УРЛ адрес проверяется на корректность, далее проверяется был ли он скачен до этого (с помощью кеширующей директории), далее отправляется запрос к сайту. Предусмотрено некоторое количество ошибок и различных ситуаций при отправке запроса и получении ответа от сайта. Так, сайты, которые возвращают код состояния HTTP больший или равный 400, удаляются из обучающей выборки. При этом для сайтов, код состояния которых равен 408 (истекло время ожидания), 434, 444, 503 (сервис недоступен) или 504 (шлюз не отвечает), программа пытается выполнить повторную загрузку.

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

Для автоматического определения кодировки в данной работе используется следующий метод: в случае, если кодировка не указана явно в теле страницы, проверяются первые несколько байт файла (там может быть указан BOM символ, свидетельствующий о принадлежности к конкретной кодировке). После этого производится анализ частоты наиболее часто используемых символов. В случае, когда анализ частот не позволяет сделать вывод о кодировке, то используется класс UnicodeDammit из библиотеки BeautifulSoup, который использует морфологический анализ и модель n-gram для определения кодировки с некоторой вероятностью. Отметим, что в настоящий момент абсолютно точное определение кодировки неизвестного текста считается невозможным [38]. Однако распознавание широко используемых кириллических или латинских кодировок производится с почти 98% точностью.

5.5 Построение дерева иерархии

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

<имя_категории_верхнего_уровня>/<имя_подкатегории>/…/<имя_категории_сайта>;<URL адрес сайта>

Пример содержимого файла:

Hi-Tech/Компьютеры/Компьютерная помощь/;http://www.bvg-group.ru/

Hi-Tech/Интернет/Создание сайтов/Веб-дизайн/;http://www.bweb.ru/

Hi-Tech/Программы/Операционные системы/;http://www.debian.org/

Hi-Tech/Программы/Операционные системы/FreeBSD/;http://community.livejournal.com/ru_freebsd

Таким образом, каждому URL адресу соответствует полный путь к его категории.

Для хранения информации о конкретном узле (категории) в иерархии применяется следующий класс:

class TreeNode: def __init__(self, parent_name, own_name, level_classifier): self.parent_name = parent_name self.level_classifier = level_classifier self.name = own_name self.has_children = False self.vertical_classifier = None def level_fit(self, train_sample, labels): self.level_classifier.fit(train_sample, labels) def vertical_fit(self, train_sample, labels, vertical_clf_object): # если мы тренируем вертикальный классификатор значит у категории есть дети self.has_children = True self.vertical_classifier = vertical_clf_object self.vertical_classifier.fit(train_sample, labels) def stay_here(self, object): ''' определяет оставлять ли объект в этой категории''' if self.has_children: if self.vertical_classifier.predict(object): return True else: return False else: return True def level_choose(self, object): if self.level_classifier.predict(object): return True else: return False def __eq__(self, other): return self.name == other.name

В этом классе parent_name это путь к родительской категории, name это путь к текущей категории, поле has_children указывает на наличие или отсутствие потомков у категории. Поле level_classifier содержит экземпляр класса Classifier - горизонтальный классификатор, определяющий принадлежит ли объект текущей категории или одной из «братских» категорий (т.е. категорий имеющих ту же родительскую категорию). Для определения принадлежности нового объекта к текущей категории предназначен метод level_choose.

Как уже упоминалось, по условию задачи сайт может принадлежать не только к листьям дерева (концевым категориям), но и к внутренним (промежуточным) категориям в иерархии. Поэтому, для каждой не концевой категории, обучается vertical_classifier, также являющийся экземпляром класса Classifier. Метод stay_here служит для вызова vertical_classifier для нового объекта классификации.

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

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

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

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

Выполняется построение дерева иерархии;

Выполняется загрузка данных с веб-сайтов из обучающей выборки;

На основе загруженных данных формируется матрица объекты-признаки (каждому объекту соответствует строка с его признаковым описанием);

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

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

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

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

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

for url in input_urls: for top_category_node in tree[ROOT_CATEGORY]: if top_category_node.level_choose(url): stage_res[url].append(get_categories(top_category_node, tree, url))

где рекурсивная функция get_categories выглядит так:

def get_categories(node, tree, url): if node.stay_here(url): return node.name for child_node in tree[node.name]: if child_node.level_choose(url): get_categories(child_node, tree, url)

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

В итоге объекту присваиваются те категории, которые присутствуют хотя бы в двух результирующих списках моделей классификации из трех.

Хранение данных

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

В программе предусмотрено два способа хранения данных: взаимодействие с базой данных MySQL или использование локальных файлов.

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

Чаще всего задачу сохранения обученных классификаторов на python решают с помощью встроенного модуля pickle, который сериализует объект классификатора (вместе со всей сохраненной статистикой). После этого сериализованный файл можно сохранить в базу данных или оставить в локальной файловой системе. Однако в данной работе такой подход сильно затруднен из-за большого числа категорий (их количество в Яндекс.Каталоге приближается к двум тысячам) и больших объемов обучающих выборок, в результате обработки которых получаются сотни тысяч уникальных слов, которые выступают в качестве признаков. Поэтому матрицы коэффициентов (размерность которых задается числом категорий и количеством признаков) хранящиеся в объектах классификаторов требуют достаточно большого объема памяти. Сериализация и десериализация объектов, содержащих такие матрицы, может занять длительное время. Более того, в случае, когда нет уверенности в достоверности сериализованного файла, его десериализация может повлечь за собой запуск вредоносного или ошибочного кода. Еще одним недостатком pickle является возможность ошибки из-за различия версий используемых библиотек при сериализации и десериализации.